1，為什么要用到鏈表
數組作為存放同類數據的集合，給我們在程序設計時帶來很多的方便，增加了靈活性。但數組也同樣存在一些弊病。如數組的大小在定義時要事先規定，不能在程序中進行調整，這樣一來，在程序設計中針對不同問題有時需要3 0個大小的數組，有時需要5 0個數組的大小，難于統一。我們只能夠根據可能的最大需求來定義數組，常常會造成一定存儲空間的浪費。
我們希望構造動態的數組，隨時可以調整數組的大小，以滿足不同問題的需要。鏈表就是我們需要的動態數組。它是在程序的執行過程中根據需要有數據存儲就向系統要求申請存儲空間，決不構成對存儲區的浪費。
鏈表是一種復雜的數據結構，其數據之間的相互關系使鏈表分成三種：單鏈表、循環鏈表、雙向鏈表，下面將逐一介紹。
2，單向鏈表
單鏈表有一個頭節點head，指向鏈表在內存的首地址。鏈表中的每一個節點的數據類型為結構體類型，節點有兩個成員：整型成員（實際需要保存的數據）和指向下一個結構體類型節點的指針即下一個節點的地址（事實上，此單鏈表是用于存放整型數據的動態數組）。鏈表按此結構對各節點的訪問需從鏈表的頭找起，后續節點的地址由當前節點給出。無論在表中訪問那一個節點，都需要從鏈表的頭開始，順序向后查找。鏈表的尾節點由于無后續節點，其指針域為空，寫作為NULL。
如圖所示：
上圖還給出這樣一層含義，鏈表中的各節點在內存的存儲地址不是連續的，其各節點的地址是在需要時向系統申請分配的，系統根據內存的當前情況，既可以連續分配地址，也可以跳躍式分配地址。
3，單向鏈表程序的實現
（1），鏈表節點的數據結構定義
struct node { int num; struct node *p; } ; 在鏈表節點的定義中，除一個整型的成員外，成員p是指向與節點類型完全相同的指針。
在鏈表節點的數據結構中，非常特殊的一點就是結構體內的指針域的數據類型使用了未定義成功的數據類型。這是在C中唯一規定可以先使用后定義的數據結構。
（2），鏈表的創建、輸出步驟
單鏈表的創建過程有以下幾步：
1 ) 定義鏈表的數據結構;
2 ) 創建一個空表;
3 ) 利用malloc ( )函數向系統申請分配一個節點;
4 ) 將新節點的指針成員賦值為空。若是空表，將新節點連接到表頭；若是非空表，將新
節點接到表尾;
5 ) 判斷一下是否有后續節點要接入鏈表，若有轉到3 )，否則結束;
單鏈表的輸出過程有以下幾步
1) 找到表頭;
2) 若是非空表，輸出節點的值成員，是空表則退出;
3 ) 跟蹤鏈表的增長，即找到下一個節點的地址;
4) 轉到2 ).
（3），程序代碼例子：
創建一個存放正整數單鏈表，輸入0或小于0的數，結束創建鏈表，并打印出鏈表中的值，程序如下：
#include <stdlib.h> /*含ma l l o c ( ) 的頭文件*/ #include <stdio.h> //①定義鏈表數據結構 struct node { int num; struct node *next; }; //函數聲明 struct node *creat(); void print(); main( ) { struct node *head; head=NULL; //②建一個空表 head=creat(head);/*創建單鏈表*/ print(head);/*打印單鏈表*/ } /******************************************/ struct node*creat(struct node *head)/*返回的是與節點相同類型的指針*/ { struct node*p1,*p2; int i=1; //③利用malloc ( )函數向系統申請分配一個節點 p1=p2=(struct node*)malloc(sizeof(struct node));/*新節點*/ printf("請輸入值，值小于等于0結束，值存放地址為：p1_ADDR= %d/n",p1); scanf("%d",&p1->num);/*輸入節點的值*/ p1->next=NULL;/*將新節點的指針置為空*/ while(p1->num>0)/*輸入節點的數值大于0*/ { //④將新節點的指針成員賦值為空。若是空表，將新節點連接到表頭；若是非空表，將新節點接到表尾; if(head==NULL) head=p1;/*空表，接入表頭*/ else p2->next=p1;/*非空表，接到表尾*/ p2=p1; p1=(struct node*)malloc(sizeof(struct node));/*下一個新節點*/ i=i+1; printf("請輸入值，值小于等于0結束，值存放地址為：p%d_ADDR= %d/n",i,p2); scanf("%d",&p1->num);/*輸入節點的值*/ //⑤判斷一下是否有后續節點要接入鏈表，若有轉到3 )，否則結束; } //==============原來程序更正部分：（多謝@daling_datou提醒）================================ free(p1); //申請到的沒錄入，所以釋放掉 p1=NULL; //使指向空 p2->next = NULL; //到表尾了，指向空 printf("鏈表輸入結束（END）/n"); //============================================== return head;/*返回鏈表的頭指針*/ } /*******************************************/ void print(struct node*head)/*出以head為頭的鏈表各節點的值*/ { struct node *temp; temp=head;/*取得鏈表的頭指針*/ printf("/n/n/n鏈表存入的值為：/n"); while(temp!=NULL)/*只要是非空表*/ { printf("%6d/n",temp->num);/*輸出鏈表節點的值*/ temp=temp->next;/*跟蹤鏈表增長*/ } printf("鏈表打印結束!!"); } 
在鏈表的創建過程中，鏈表的頭指針是非常重要的參數。因為對鏈表的輸出和查找都要從鏈表的頭開始，所以鏈表創建成功后，要返回一個鏈表頭節點的地址，即頭指針。
程序執行流程：
4，單鏈表操作基礎示例
#include <stdio.h> #include <malloc.h> #define LEN sizeof(NODE) typedef struct _NODE//節點聲明 { int val; struct _NODE* next; } NODE, *PNODE; void print(PNODE head){//打印所有節點 while (head) { printf("%3d",head->val); head = head->next; } printf("/n"); } void insertHead(PNODE *pHead, int val){//頭插法 PNODE n = (PNODE)malloc(LEN); n->val = val; n->next = *pHead; *pHead = n; } void insertTail(PNODE *pHead, int val){//尾插法 PNODE t = *pHead; PNODE n = (PNODE)malloc(LEN); n->val = val; n->next = NULL; if (*pHead == NULL) { n->next = *pHead; *pHead = n; }else{ while (t->next) { t = t->next; } t->next = n; } } void deleteHead(PNODE *pHead){//刪除頭 if (*pHead == NULL) { return; } else { PNODE t = *pHead; *pHead = (*pHead)->next; free(t); } } void deleteTail(PNODE *pHead){//刪除尾 PNODE t = *pHead; if (t == NULL) { return; } else if (t->next == NULL) { free(t); *pHead = NULL; } else{ while (t->next->next != NULL) { t = t->next; } free(t->next); t->next = NULL; } } PNODE findByVal(PNODE head, int val){//根據值找到滿足條件的第一個節點 while (head != NULL && head->val != val) { head = head->next; } return head; } PNODE findByIndex(PNODE head, int index){//根據索引找節點 if (index == 1) { return head; } else { int c = 1; while (head != NULL && index != c) { head = head->next; c++; } } return head; } void insertByIndex(PNODE *pHead, int index, int val){//根據索引插入節點 if (index == 1) { insertHead(pHead, val); } else { PNODE t = findByIndex(*pHead,index - 1); if (t == NULL) { return; } else { PNODE n = t->next; t->next = (PNODE)malloc(LEN); t->next->next = n; t->next->val = val; } } } void deleteByIndex(PNODE *pHead, int index)//根據結點索引刪除結點 { if (index == 1) { deleteHead(pHead); } else { PNODE t= findByIndex(*pHead, index - 1); if (t == NULL || t->next == NULL) { return; }else{ PNODE n = t->next->next; free(t->next); t->next = n; } } } void deleteByVal(PNODE *pHead, int val)//根據值刪掉第一個滿足條件的 { if (*pHead == NULL)//如果空表退出 { return; } else { if ((*pHead)->val == val)//如果第一個就是，刪頭 { deleteHead(pHead); } else { PNODE t = *pHead; while (t->next != NULL && t->next->val != val)//遍歷，若t的next為空或者next是要找的節點則退出 { t = t->next; } if (t->next)//如果t指向要找的結點的上一個節點 { PNODE n = t->next->next;//刪除要找的結點 free(t->next); t->next = n; } } } } void clear(PNODE *pHead)//清除鏈表 { while ((*pHead) != NULL) { deleteHead(pHead);//從頭刪除 } } void main() { PNODE head = NULL; insertTail(&head,1); deleteHead(&head); insertTail(&head,2); insertTail(&head,3); insertTail(&head,4); insertTail(&head,5); insertTail(&head,6); print(head); insertByIndex(&head, 6, 9); print(head); //deleteByIndex(&head,3); deleteByVal(&head, 2); print(head); clear(&head); print(head); insertByIndex(&head,1,12); print(head); } 新聞熱點
疑難解答
圖片精選
