動態記憶體配置

 

  實 習 內 容



1. 練習使用 malloc 及 free 動態配置 1 維陣列

2. 指標與陣列語法的共通性

3. 練習使用 malloc 及 free 動態配置 2 維陣列

1

背景

資料指標以及函數指標都是為了增加程式的彈性而設計的語法, 請參考下列文件說明: 指標介紹

動態配置記憶體 配合指標的語法可以讓程式設計者自己調整記憶體的使用, 程式執行的時候需要使用多少記憶體才去請求那些記憶體的使用權, 通常可以用來在程式執行時根據需求決定陣列的大小, 或是 實作比較有彈性的資料結構, 例如 串列 (list), 樹狀結構 (tree)...。

在這個實習裡, 我們著重於練習動態配置 1 維與 2 維陣列, 以及這種陣列的使用方法。

2

使用 malloc 及 free 動態配置 1 維陣列:

我們常常會需要在函數中定義一個陣列, 例如:

    void fun(void)
    {
        char name[11]; // 在系統堆疊上定義一個佔據 11 個位元組的陣列變數
            .
            .
        scanf("%s", name); // 使用
            .
            .
    } // 在執行到 return 敘述之後自動銷毀 name 陣列

考慮下面三個使用陣列衍生的問題:

  1. 在寫上面這種函數的時候, 我們需要根據程式的使用環境估計這個陣列變數需要多大, 然後設定一個大小, 例如上面的 name 陣列, 我們預計最大的名字有五個中文字, 每個中文字兩個位元組, 所以陣列 name 設計成 11 個位元組的大小 , 萬一使用者需要更大的空間存放姓名, 程式只好跟使用者說抱歉...沒有辦法繼續執行下去!
  2. 還有另一個尷尬的狀況, 如果在這個函數裡設定了這個陣列的內容, 在執行完return 之後, 陣列就消失了, 不能夠保留下來...
  3. 如果你在函數裡面需要一個 1024 x 1024 的 double 型態陣列, 這個陣列在記憶體裡面需要 8 MB 來存放, 而函數的區域變數是放在系統堆疊上的, 堆疊上通常沒有辦法提供你很大的記憶體

以上三種問題都可以運用動態的記憶體配置來解決,

    int length = 20;
    char *name = (char *) malloc(length*sizeof(char)); // 動態配置
        .
        .
    scanf("%s", name); // 使用
        .
        .
    free(name); // 釋放所配置的記憶體

在上面這個範例裡, 第一個問題很明顯得到解決, 因為陣列的大小可以在執行的時候根據 length 變數裡的數值來決定

第三個問題也自動獲得解決, 因為動態記憶體不在系統堆疊上, 而在空間比較充裕的 Heap 區域中, 現在的執行環境中如果你要配置 109 位元組應該都是允許的

至於二個問題, 因為陣列所使用的記憶體沒有規定在離開函數的時候一定要釋放, 所以只要程式裡不呼叫 free() 函數, 那一段使用 malloc 動態配置的記憶體就歸這個程式使用, 你只要把記憶體位址記錄在指標變數裡面, 不要不小心覆蓋掉了, 就一直可以用到你呼叫 free() 函數釋放為止, 動態配置的記憶體的生命期由程式設計者來控制! 例如, 下面程式中回傳的字元陣列就可以在函式之外使用, 不過用完以後記得要呼叫 free() 函數釋放:

char *duplicate(const char original[])
{
    int len=0;
    char *copy;

    while (original[len] != '\0')
        len++;
    if (len == 0) return 0;

    copy = (char *) malloc((len+1)*sizeof(char));    
    for (i=0; i<len; i++)
        copy[i] = original[i];
    copy[len] = '\0';

    return copy;
}

請將下列程式中的陣列以動態記憶體配置改寫:

#include <stdio.h>
#include <stdlib.h>
#define MAX 200

typedef struct 
{
    char name[20];
    double salaryPerHour;
    int numberOfDays;
    int workHoursPerDay[31];
} Employee;

int main(void)
{
    int i, numEmployee;
    Employee employee[MAX];

    printf("請輸入員工的人數 > ");
    scanf("%d", &numEmployee);

    for (i=0; i<numEmployee; i++)
    {
        scanf("%s", name);
        scanf("%lf", &employee[i].salaryPerHour);
        scanf("%d", &employee[i].numberOfDays);
        for (j=0; j<employee[i].numberOfDays; j++)
            scanf("%d", &employee[i].workHoursPerDay[j]);
    }

    system("pause");
    return 0;
}

在改寫 employee[MAX] 時, 你只需要配置 numEmployee 個元素, 每一個元素都是一個 Employee 型態的結構, 所以需要 sizeof(Employee) 個位元組; 然後請把 employee 陣列換成 Employee* 型態的指標, 加上 malloc 及 free 函數的呼叫

改寫 name 陣列時, 你需要把 Employee 結構裡的 name 欄位改成 char * 的指標, 在迴圈裡面由鍵盤讀取姓名時, 還沒讀進來前不曉得到底有幾個字元, 所以你需要準備一個比較大的字元陣列, 例如 char buf[100]; 先把姓名讀進這個陣列裡, 然後計算有幾個字元, 才能夠配置足夠大的記憶體, 最後把姓名由 buf 陣列中拷貝到新配置的 name 陣列中, 在釋放整個 employee 陣列前, 也需要先釋放所配置的 name 陣列;

改寫 workHoursPerDay 陣列和 name 陣列的步驟一樣

另外, 動態配置的陣列在使用時的語法和一般的陣列一模一樣, 請參考下一步驟的說明

參考程式:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct 
{
    char *name;
    double salaryPerHour;
    int numberOfDays;
    int *workHoursPerDay;
} Employee;

int main(void)
{
    int i, numEmployee;
    Employee *employee;
    char buf[100];

    printf("請輸入員工的人數 > ");
    scanf("%d", &numEmployee);

    employee = (Employee *) malloc(numEmployee * sizeof(Employee));
    for (i=0; i<numEmployee; i++)
    {
        scanf("%s", buf);
        employee[i].name = (char *) malloc((strlen(buf)+1)*sizeof(char));
        scanf("%lf", &employee[i].salaryPerHour);
        scanf("%d", &employee[i].numberOfDays);
        employee[i].workHoursPerDay = 
            (int *) malloc(employee[i].numberOfDays*sizeof(int));
        for (j=0; j<employee[i].numberOfDays; j++)
            scanf("%d", &employee[i].workHoursPerDay[j]);
    }

    for (i=0; i<numEmployee; i++)
    {
        free(employee[i].name);
        free(employee[i].workHoursPerDay);
    }
    free(employee)
    system("pause");
    return 0;
}

3

動態配置的陣列與一般陣列在使用時的共通性:

在 C/C++ 語言中陣列根本就是用指標的概念實作的, 所以宣告成指標的變數其實使用方法和陣列一模一樣, 概念是一致的, 例如:

資料存取:

    int length = 20;
    char buf;
    char *name = (char *) malloc(length*sizeof(char)); // 動態配置
        .
        .
    scanf("%s", name); // 使用起來和 char name[20] 的 name 一模一樣
                      // 其實應該說是陣列變數的使用和指標變數一模一樣
    name[10] = 'a';         // *(name+10) = 'a';
    printf("%c", name[5]);  // printf("%c", *(name+5));
    buf = name[0];          // buf = *(name+0); 或是 buf = *name;
        .
        .
    free(name); // 釋放所配置的記憶體

函數參數傳遞:

    void fun(int array[20])
    {
        ...
    }

或是

    void fun(int array[])
    {
        ...
    }

或是

    void fun(int *array)
    {
        ...
    }

或是

    void fun(int *const array) /* array 是一個不能更改內容的指標變數 */
    {
        ...
    }

4

使用 malloc 及 free 動態配置 2 維陣列:

基本的 2 維陣列範例如下:

int matrix[2][3] = {{1, 2, 3}, {4, 5, 6}};

...

matrix[1][2] = matrix[0][1] * 2;

以下為第一種動態配置的 2 維陣列:

int i, j;
int *matrix[2]; /* 指標陣列: 每一個元素都是指標的陣列 */
for (i=0; i<2; i++)
{
    matrix[i] = (int *) malloc(3*sizeof(int));
    for (j=0; j<3; j++)
        matrix[i][j] = i*3+j+1;
}
   ...
matrix[1][2] = matrix[0][1] * 2;
   ...
for (i=0; i<2; i++)
    free(matrix[i]);

以下為第二種動態配置的 2 維陣列:

int i, j, **matrix; /* 雙重指標 */
matrix = (int **) malloc(2*sizeof(int *));
for (i=0; i<2; i++)
{
    matrix[i] = (int *) malloc(3*sizeof(int));
    for (j=0; j<3; j++)
        matrix[i][j] = i*3+j+1;
}
   ...
matrix[1][2] = matrix[0][1] * 2;
   ...
for (i=0; i<2; i++)
    free(matrix[i]);
free(matrix);

下面這個使用的人比較少, 基本上配置一大段連續的記憶體 (1 維的陣列 data) 來存放 2 維陣列, 另外以一個指標陣列 matrix 來維持原先二維的陣列存取語法:

int i, j;
int *data, **matrix;
data = (int *) malloc(2*3*sizeof(int));
matrix = (int **) malloc(2*sizeof(int *));
for (i=0; i<2; i++)
{
    matrix[i] = &data[3*i];
    for (j=0; j<3; j++)
        matrix[i][j] = i*3+j+1;
}
   ...
matrix[1][2] = matrix[0][1] * 2;
   ...
free(matrix);
free(data);

傳遞基本的二維陣列進入函數時宣告方法如下:

    void fun(int matrix[20][30])
    {
        ...
    }

或是

    void fun(int matrix[][30])
    {
        ...
    }

或是

    void fun(int (*matrix)[30])
    {
        ...
    }

傳遞前面這三種動態配置的二維陣列進入函數時宣告方法如下:

    void fun(int *matrix[2])
    {
        ...
    }

或是

    void fun(int *matrix[])
    {
        ...
    }

或是

    void fun(int **matrix)
    {
        ...
    }

請練習組合上述程式片段成為完整的程式, 在 devcpp 中測試一下

計算機程式設計實習 首頁

製作日期: 2012/11/26 by 丁培毅 (Pei-yih Ting)
E-mail: pyting@ntu.edu.tw