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 為止。



第二個部份從第 72 行到第 84 行,其為印出所建立的好友資料,在鏈結串列中由走的方式亦同。


問題與討論
  1. 為什麼要另外定義一個專門處理鏈結串列的結構?
  2. 解釋 startPtr 在鏈結串列中的用途,如果不用 startPtr ,有其他方法可以取代嗎?




1 則留言:

提到...

第一行「我們已經有了記錄單筆通訊錄資料的結構 friendData」的結構的連結錯了哦。