數據結構--單向鏈表

C語言中，我們在使用數組時，會需要對數組進行插入和刪除的操作，這時就需要移動大量的數組元素，但在C語言中，數組屬於靜態內存分配，數組在定義時就必須指定數組的長度或者初始化。這樣程序一旦運行，數組的長度就不能再改變，若想改變，就只能修改源代碼。實際使用中數組元素的個數也不能超過數組元素的最大長度，否則就會發生下標越界的錯誤（這是新手在初學C語言時肯定會遇到的問題，相信老師也會反覆強調！！！但這種問題肯定會遇到，找半天找不到錯誤在哪，怪我咯？？？）。另外如果數組元素的使用低於最大長度，又會造成系統資源的浪費，會導致降低空間使用效率。

那有沒有更合理的使用系統資源的方法呢？比如，但需要添加一個元素時，程序就可以自動的申請內存空間並添加新的元素，而當需要減少一個元素時，程序又可以自動地釋放該元素佔用的內存空間。我們聰明的祖先早就意識到了這個問題，於是就有了動態數據結構--鏈表結構（Linked list）。它主要是利用動態內存分配、使用結構體並配合指針來實現的一種數據結構。

鏈表有三種不同的類型：單向鏈表，雙向鏈表以及循環鏈表。今天我們只對單向鏈表做詳細的說明。

鏈表中最簡單的一種是單向鏈表，它包含兩個域，一個信息域和一個指針域。這個鏈接指向列表中的下一個節點，而最後一個節點則指向一個空值（NULL）。

單向鏈表的存儲結構

/*單向鏈表的代碼表示*/struct node{ int data; // 數據域 struct node *next; // 指向下一個節點的指針};

接下來進入正題，分別詳細講一下單向鏈表的插入、刪除節點以及插入節點操作。

1. 單向鏈表的建立

建立一個單向鏈表，我們可以使用向鏈表中添加節點的方式。首先，要為新建的節點動態申請內存空間，讓指針變數指向這個新建節點，然後將新建節點添加到鏈表中，這時，我們需要考慮以下兩種情況：

（1）若原鏈表為空，則將新建節點設置為頭節點

（2）若原鏈表為非空，則將新建節點添加到表尾

具體代碼如下：

#include "stdio.h"#include "stdlib.h"struct link *AppendNode(struct link *head);void DisplayNode(struct link *head);void DeleteMemory(struct link *head);struct link { int data; struct link *next;};int main(int argc, char const *argv[]){ int i = 0; char c; struct link *head = NULL; //鏈表頭指針 printf("Append a new node(y/n)?"); scanf("%c", &c); while(c == Y || c == y){ head = AppendNode(head); //向head為頭指針的鏈表末尾添加節點 DisplayNode(head); printf("Append a new node(y/n)?"); scanf(" %c", &c); i++; } printf("%d new nodes have been appened!
"); DeleteMemory(head); return 0;}// 新建一個節點並添加到鏈表末尾，返回添加節點後的鏈表的頭指針struct link *AppendNode(struct link *head){ struct link *p = NULL, *pr = head; int data; p = (struct link *)malloc(sizeof(struct link)); // 通過malloc函數動態的申請內存，注意結構體佔用內存的大小只能用sizeof()獲取 if (p == NULL){ printf("No enough memory to allocate!
"); exit(0); } if (head == NULL){ //原鏈表為空 head = p; }else{ // 原鏈表為非空，則將新建節點添加到表尾 while(pr->next != NULL){ // 如果pr指向的不是表尾，則移動pr直到指向表尾 pr = pr->next; } pr->next = p; } printf("Input node data:"); scanf("%d",&data); // 輸入新建節點的數據 p->data = data; p->next = NULL; // 將新建節點置為表尾 return head;}// 顯示鏈表中所有的節點void DisplayNode(struct link *head){ struct link *p = head; int j = 1; while(p != NULL){ // p不在表尾，循環列印節點的值 printf("%5d%10d
", j, p->data); p = p->next; j++; }}//釋放head指向的鏈表中所有節點佔用的內存void DeleteMemory(struct link *head){ struct link *p = head, *pr = NULL; while(p != NULL){ // p不在表尾，釋放節點佔用的內存 pr = p; // 在pr中保存當前節點的指針 p = p->next; // p指向下一個節點 free(pr); // 釋放pr指向的當前節點佔用的內存 }}

代碼運行結果如下：

2. 單向鏈表的刪除操作

鏈表的刪除操作就是將待刪除的節點從鏈表中斷開，那麼待刪除節點的上一個節點就成為尾節點。在刪除節點時，我們要考慮一下4種情況：

（1）若原鏈表為空，則不執行任何操作，直接退出程序

（2）若待刪除節點是頭節點，則將head指向當前節點的下一個節點，再刪除當前節點

（3）若待刪除節點不是頭節點，則將前一節點的指針域指向當前節點的下一節點，即可刪除當前節點。當待刪除節點是尾節點時，由於p->next=NULL，因此執行pr->next = p->next後，pr->next的值也變為了NULL，從而使pr所指向的節點由倒數第二個節點變成尾節點。

（4）若待刪除的節點不存在，則退出程序

注意：節點被刪除後，只表示將它從鏈表中斷開而已，它仍佔用著內存，必須要釋放這個內存，否則會出現內存泄漏。

刪除一個節點的代碼如下：

// 從head指向的鏈表中刪除一個節點，返回刪除節點後的鏈表的頭指針struct link *DeleteNode(struct link *head, int nodeData){ struct link *p = head, *pr = head; if (head == NULL) // 若原鏈表為空，則退出程序 { printf("Linked Table is empty!
"); return head; } while(nodeData != p->data && p->next != NULL) // 未找到待刪除節點，且沒有到表尾 { pr = p; // 在pr中保存當前節點的指針 p = p->next; // p指向當前節點的下一節點 } if (nodeData == p->data) // 若當前節點就是待刪除節點 { if (p == head) // 若待刪除節點為頭節點 { head = p->next; // 將頭指針指向待刪除節點的下一節點 } else // 若待刪除節點不是頭節點 { pr->next = p->next; // 讓前一節點的指針指向待刪除節點的下一節點 } free(p); // 釋放為已刪除節點分配的內存 } else // 沒有找到節點值為nodeData的節點 { printf("This Node has not been found!
"); } return head; // 返回刪除節點後的鏈表頭指針}

3. 單鏈表的插入操作

向一個鏈表中插入一個新節點時，首先要新建一個節點，並將新建節點的指針域初始化為空NULL，然後在鏈表中尋找適當的位置執行節點插入操作，此時需要考慮下面4種情況：

（1）若原鏈表為空，則將新建節點p作為頭節點，讓head指向新節點p

（2）若原鏈表為非空，折按新建節點的值的大小（假設原鏈表已按節點值升序排列）確定插入新節點的位置。若在頭結點前插入新節點，則將新節點的指針域指向原鏈表的頭結點，並且讓head指向新節點p

（3）若在原鏈表中間插入新節點，則將新節點p的指針域指向下一節點，並且讓前一節點的指針域指向新建節點p

（4）若在表尾插入新節點，則將尾節點的指針域指向新節點p

具體代碼如下：

// 在已按升序排列的鏈表中插入一個新節點，返回插入節點後的鏈表頭指針struct link *InsertNode(struct link *head, int nodeData){ struct link *pr = head, *p = head, *temp = NULL; p = (struct link *)malloc(sizeof(struct link)); // 給新建節點動態申請內存空間 if (p == NULL) // 若動態申請內存失敗，則退出程序 { printf("No enough memory!
"); exit(0); } p->next = NULL; // 將新建節點的指針域初始化為空 p->data = nodeData; // 將新建節點的數據域初始化為nodeData if (head == NULL) // 若原鏈表為空 { head = p; // 將新建節點作為頭節點 } else // 若原鏈表為非空 { // 未找到新建節點的插入位置並且沒有到尾節點 while(pr->data < nodeData && pr->next != NULL) { temp = pr; // 在temp中保存當前節點pr的指針 pr = pr->next; // pr跳到下一節點 } // 找到需要插入的位置 if (pr->data >= nodeData) { if (pr == head) // 若當前節點為頭節點，則將新建節點插入頭節點之前 { p->next = head; // 將新節點的指針域指向原鏈表的頭節點 head = p; // head指向新建節點 } else // 在原鏈表中插入新節點 { pr = temp; p->next = pr->next; // 新建節點的指針域指向當前節點的下一節點 pr-next = p; // 當前節點的下一節點指向新節點 } } else // 新建節點的值為最大值，插在原鏈表尾部 { pr->next = p; // 原鏈表的尾節點指向新節點 } } return head; // 返回插入新節點後的鏈表的頭指針}

到此，對於單鏈表的操作已經介紹完了。通過寫這篇博客，我也深刻學習了單鏈表的結構和一些主要操作，在寫作的過程中也翻閱了很多資料，讓我意識到數據結構的重要性，不懂數據結構，你永遠只能當一個碼農。

共勉！

哦，忘了今天是聖誕節，也是那個賣火柴的小女孩凍死170周年 :（

----最後編輯於2016/12/25----