程式語言教學誌 FB, YouTube: PYDOING: C 語言初學教材

我們已經有了記錄單筆通訊錄資料的結構 friendData ，現在需要考慮如何進行多筆資料的處理。只使用變數可以嗎？可以的，但是比須先宣告變數名稱，而且不太能任意加入或刪除新的資料。那使用結構陣列呢？也就是資料型態為結構 friendData 的陣列。

這是可以的，我們宣告的陣列大小會成為通訊錄資料筆數的上限，類似記錄帳號及密碼的 userID[][] 及 userCode[][] 兩個二維字元陣列。可以這樣做，卻不是個好方法，因為一旦宣告型態為 friendData 的陣列，就必須配置符合所宣告大小的記憶體空間，容易造成不必要的浪費。

利用動態記憶體配置會是避免浪費記憶體空間的良策，需要新增資料時，呼叫標準函數庫 stdlib.h 的函數 malloc() ，向作業系統要求可以利用的記憶體空間即可。但這樣一來會產生另一個新問題，我們要怎麼把每一筆新增的資料連接起來，好方便刪除、查詢、印出列表等各種功能？

C 語言把資料連接起來的方式為指標，指標儲存的是某一筆資料的記憶體位址，所以如果我們在結構中設定一個成員，讓這個成員指向另一個結構，透過這種模式，我們便可以新增資料，就把新的資料與舊的資料串連在一起，藉此組織所有的資料。電腦科學把在記憶體中組織資料的方法歸為「資料結構」的課程，在此，我們從眾多資料結構中選出一種基本，而且容易理解的鏈結串列來當作我們所用的資料結構。

鏈結串列的資料組織方式，可用下圖表示

黑色為每個結構的起始位置，深灰色為結構中有哪些成員，當然，要定義幾種成員可自由決定，這邊用 data 及指標變數 nextPtr 兩個成員舉例說明。這張圖也說明了一點，利用結構相連組成的資料結構，這些資料可以分散在記憶體的各個不同空間，而非連續的記憶體空間。

以下我們另外定義專門處理鏈結串列的結構 linkedListNode ， friendData 為其 data 成員

struct linkedListNode {
    struct friendData data;
    struct *linkedListNode nextPtr;
};

我們用一個例子示範鏈結串列的使用，完整的範例程式碼及編譯執行，請參考

這個例子是一個簡單示範，利用指向結構 linkedListNode 的指標 startPtr 作為鏈結串列的起點。大體上分成兩部份，第一個部份從第 29 行到第 70 行，其中在第 30 行，程式剛開始執行， startPtr 指向的是 NULL ，虛無的指標

startPtr = NULL;

也就是說

接下來要求使用者依序輸入五筆好友資料，其中，第 33 行

// 向作業系統要求新的記憶體空間
newPtr = malloc(sizeof(LinkedListNode));

這是程式向作業系統要求新的記憶體空間。第 35 行到第 43 行，依須輸入每筆資料的各個成員，第 45 行到第 50 行則是將好友資料拷貝到剛才取得的記憶體空間之中，也就是向作業系統要來足夠放下結構 linkedListNode 的空間。第 52 行到第 67 行，這部份則是將資料加入鏈結串列之中

// 將資料加入鏈結串列
if (startPtr == NULL) {
    startPtr = newPtr;
}
else {
    currentPtr = startPtr;
          
    while (currentPtr != NULL) {
        if (currentPtr->nextPtr == NULL) {
            currentPtr->nextPtr = newPtr;
            break;
        }
                       
        currentPtr = currentPtr->nextPtr;
    }
}

上面可分成 if 跟 else 兩部份來看， if 陳述為真，就是說整個鏈結串列中還沒有資料， newPtr 所指向的記憶體空間為第一筆資料，因此將 newPtr 所指向的值給 startPtr ，這是說

因為每個結構 linkedListNode 的指標成員 nextPtr ，其初值都被給於 NULL ，因此若是某筆資料的成員 nextPtr 為 NULL ，便表示這是鏈結串列的最後一筆資料。因此我們這裡用 currentPtr 在鏈結串列中遊走，把 currentPtr->nextPtr 給 currentPtr ，便能走到鏈結串列的下一個位置，直到 currentPtr 是 NULL 為止。