鏈表的物理存儲結構是用一組地址任意的存儲單元存儲數據的。不像順序表占據連續的一段內存空間，而是將存儲單元分散在內存的任意地址上。
?
鏈表結構中，每個數據元素記錄都存放到鏈表的一個節點（node）中，而每個節點之間由指針將其連接在一起，形成了”鏈“的結構、
鏈表每個節點中，都必須有一個專門用來存放指針（地址）的域，用這個指針域來存放后繼結點的地址，這樣就達成了連接后繼結點的目的。
一條鏈表通常有1個”表頭“，是一個指針變量，用來存放第一個節點地址。此外，一條鏈表的最后一個節點的指針域要置空（NULL），表示該節點為鏈表的尾節點，因為它之沒有后繼結點了。
?
鏈表特征：
1）每個節點包括兩部分：數據域和指針域。其中數據域用來存放數據元素本身的信息，指針域用來存放后繼結點的地址。
2）鏈表邏輯上是連續的，而物理上不一定連續存儲節點、
3）只要獲得鏈表的頭節點，就可以通過指針遍歷整條鏈表。
?
實例：編寫一個程序，要求：從終端輸入一組整數（大于10個數），以0作為結束標志，將這一組整數存放在一個鏈表中，（結束標志0不包括在內），打印出該鏈表中的值。然后刪除該鏈表中的第五個元素，打印出刪除后的結果。最后在內存中釋放掉該鏈表。
?
#include"stdio.h"
#include"stdlib.h"
typedef int ElemType;typedef struct node{ElemType data;struct node *next;
}LNode,*LinkList;LinkList GreatLinkList(int n) { //創建一個長度為n的鏈表 LinkList p,r,list=NULL;ElemType e;int i;for(i=1;i<=n;i++) {scanf("%d",&e); //輸入結點的內容 p=(LinkList)malloc(sizeof(LNode));//為新建的結點開辟內存空間 p->data=e; //元素賦值 p->next=NULL;if(!list)list=p; //賦值鏈表頭指針 elser->next=p; //將結點連入鏈表 r=p;}return list; //返回鏈表頭指針
}void insertList(LinkList *list,LinkList q,ElemType e) {//向鏈表中插入結點 e LinkList p;p=(LinkList)malloc(sizeof(LNode));//為新建的結點開辟新的內存空間 ，生成一個新結點，由p指向它 p->data=e; //向該結點的數據域賦值e if(!*list) {*list=p; //list內容為NULL時，表示該鏈表為空，賦值鏈表頭指針 p->next=NULL;} //當鏈表為空時q沒有意義，只能在頭結點后面插入第一個元素 else {p->next=q->next;//當鏈表不為空時，認為q指向的結點一定存在，將q指向的結點的next域的值賦給p指向結點的next域q->next=p; }
}void delLink(LinkList *list,LinkList q) { //刪除鏈表的某結點 LinkList r;if(q==*list) { //如果刪除第一個結點 *list=q->next;free(q);}else { //刪除其他結點 for(r=*list;r->next!=q;r=r->next)if(r->next!=NULL) {r->next=q->next;free(q);}}
}void destroyLinkList(LinkList *list) { //銷毀一個鏈表 LinkList p,q;p=*list;while(p) { //循環釋放掉每一個鏈表結點 q=p->next;free(p);p=q;}*list=NULL;//將*list的內容置為NULL，這樣主函數中的鏈表list就為空，防止了list變為野指針，而且鏈表在內存中也完全被釋放掉了。
}int main() {int e,i;LinkList l,q;q=l=GreatLinkList(l);//創建一個鏈表結點，q和l都指向該結點 scanf("%d",&e);while(e) { //循環輸入數據，同時插入新生成的結點 insertList(&l,q,e);q=q->next;scanf("%d",&e);}q=l;printf("the content of the linklist\n");while(q) { //輸出鏈表中的內容 printf("%d",q->data);q=q->next;}q=l;printf("\nDelete the fifth element");for(i=0;i<4;i++) { //將指針q指向鏈表的第五個元素 if(q==NULL) { //確保此時鏈表的長度大于等于5，否則將是非法操作 printf("the length of the linklist is smaller than 5!");}q=q->next;}delLink(&l,q); //找到鏈表中第五個元素，用q指向它，再刪除q所指的結點 q=l;while(q) { //打印出刪除后的結果 printf("%d",q->data);q=q->next;}destroyLinkList(&l); //銷毀該鏈表 return 0;
}
創建鏈表注意：
（1）用malloc()函數在內存的動態存儲區（堆內存）中開辟一塊大小為sizeof(LNode)的空間，并將其地址賦給LinkList類型變量p，（LinkList為指向LNode變量的類型，LNode為前面定義的鏈表結點類型）。然后將數據e存入該結點的數據域data，指針域存放NULL。
（2）若指針變量list為空，說明本次生存的結點是第一個結點……
（3）若指針變量list不為空，說明本次生存的結點不是第一個結點，將p賦給r->next。此處的r是一個LinkList類型變量，永遠指向原先鏈表的最后一個結點，也就是要插入結點的前一個結點。
（4）再將p賦值給r，目的是使r再次指向最后的結點，以便生成鏈表的下一個結點，即保證r永遠指向原先鏈表的最后一個結點。
（5）重復（1）~（4）n次，生成n個結點的鏈表
（6）最后生成的鏈表的頭指針list返回主調函數，通過list就可以訪問到該鏈表的每一個結點。
?
刪除鏈表注意：
從非空鏈表刪除q所指的結點，考慮3種情況：
（1）q所指向的是鏈表的第一個結點
（2）q所指向的結點的前驅結點的指針已知
（3）q所指向的結點的前驅結點的指針未知
?
銷毀鏈表注意
鏈表使用完建議銷毀，因為鏈表本身會占用內存空間。若一個系統中使用很多鏈表，而使用完又不及時銷毀，那么這些垃圾空間積累過多，最終導致內存的泄露甚至程序的崩潰。
?
————————————————————————
————————————————————————
程序運行時候，刪除第5個元素，沒有顯示出預期結果。運行環境在DEV。
協議（翻譯稿）)
