動態記憶體配置

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

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

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

背景

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

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

在這個實習裡, 我們著重於練習動態配置 1 維與 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 區域中, 現在的執行環境中如果你要配置 10⁹ 位元組應該都是允許的

至於第二個問題, 因為陣列所使用的記憶體沒有規定在離開函數的時候一定要釋放, 所以只要程式裡不呼叫 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;
}

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

在 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 是一個不能更改內容的指標變數 */
    {
        ...
    }

使用 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 中測試一下