代碼參考《妙趣橫生的算法.C語言實現》

---

前言

本章總結：鏈表的定義、創建、銷毀，結點的插入與刪除

---

1、鏈表基礎

鏈表的物理存儲結構是用一組地址任意的存儲單元存儲數據的。
在鏈表結構中，每個數據元素記錄都存放在鏈表的一個結點node中，而每個結點之間由指針將其連接到一起。
每個結點由指針域(存放后繼結點的位置)、數據域構成。
一個鏈表通常有一個表頭，是一個指針變量，用來存放第一個結點地址。
鏈表的最后一個結點的的指針域要置空，表示為鏈表的尾結點。

鏈表特點：
1、每個結點包括兩個部分：數據域和指針域
數據域用來存放數據元素本身信息，指針域用來存放后繼結點的地址
2、鏈表邏輯上是連續的，但物理上不一定是連續存儲結點。
3、只要獲取鏈表的頭結點，就可以通過指針遍歷整條鏈表
一個鏈表結點可以描述為：

typedef struct node{ElemType data;		//數據域struct node *next;	//指針域
}LNode,*LinkList;

每個結點的類型是LNode
*LinkList是指向LNode類型數據的指針類型定義。
所以 LNode *L 與 LinkList L; 是等價的。

2、創建一個鏈表

LinkList GreatLinkList(int n)
{//建立一個長度為n的鏈表LinkList p,r,list=NULL;		//p:相當于每次新建結點的暫存器，r:相當于插入結點的上一個結點,永遠指向原先鏈表的最后一個結點。list鏈表的頭指針ElemType elem;				//獲取暫存數據int i;						//定義累加器for(i=0;i<n;i++){scanf("%d",&elem);p=(LinkList)malloc(sizeof(LNode));	//分配內存，并將首地址送到pp->data=elem;			//置入數據p->next =NULL;			//指針指向NULL，暫時不考慮下一個結點if(!list)				//如果鏈表為空，則新創建的結點就是該鏈表的第一個結點list=p;else					//如果鏈表不為空，則將新建立的結點連接到之前鏈表的尾部r->next=p;r=p;					//將p結點的數據賦給r}return list;				//將鏈表的頭指針返回主調函數，通過list就可以訪問鏈表中的每個結點，并進行操作	
}

3、插入結點

步驟描述：
1、創建新節點，用指針p指向該結點
2、將q指向結點的next域的值賦值給p指向結點的next域
3、將p的值賦值給q的next域

代碼描述：

void insertList(LinkList *list,LinkList q,ElemType e)
{//向鏈表中由指針q指向的結點后面插入結點，結點數據位eLinkList p;p=(LinkList)malloc(sizeof(LNode));		//生成一個新節點，由p指向它p->data=e;if(!*list)				//如果鏈表為空{*list=p;p->next=NULL;}						//當鏈表為空的時候，q沒有意義，只能在頭結點后面插入第一個元素else{//當鏈表不為空的時候，認為q指向的結點一定存在//將q指向的結點的next域的值賦給p指向的結點的next域p->next=q->next;q->next=p; }
}

通過這個算法同樣可以創建一個鏈表，因為鏈表為空時，list==NULL，可以自動創建一個結點。在下面創建其他結點時，只要始終將指針q指向鏈表的最后一個結點，就可以創建出一個鏈表

4、刪除結點

從非空鏈表中刪除q所指的結點。
考慮三個情況：1、q指向的是鏈表的第一個結點
2、q指向的結點的前驅結點的指針已知
3、q指向的結點的前驅結點的指針未知
步驟：
1：將q所指的結點的指針域next的值賦給頭指針list，讓list指向第二個結點，再釋放掉q所指的結點即可。
2：假設前驅指針為r，將q所指的結點的指針域next的值賦給r的指針域next，釋放掉q所指結點
3：當q所指的結點的前驅結點的指針未知，需要通過鏈表頭指針list遍歷鏈表，找到q的前驅結點，并將該指針賦值給變量r，再按照第二種情況去做即可

情況1、2的代碼描述：

void delLink(LinkList *list,LinkList r,LinkList q)
{if(q==*list)		//情況1：q指向鏈表的第一個結點*list=q->next;else				//情況2：q指向的結點前驅結點的指針已知r->next=q->next;free(q);
}

情況1、3的代碼描述：

void delLink(LinkList *list,LinkList r,LinkList q)
{if(q==*list)//情況1：q指向鏈表的第一個結點{*list=q->next;  free(q);}else				//情況3：q指向的結點前驅結點的指針未知{for(r=*list;r->next!=q;r=r->next);	//遍歷鏈表，找到q的前驅結點的指針if(r->next!=NULL){r->next=q->next;			//從鏈表中刪除q指向的結點free(q);}} 
}

5、銷毀鏈表

使用鏈表之后需要銷毀它，因為鏈表本身會占用內存。
code描述：

void destroyLinkList(LinkList *list)
{LinkList p,q;p=*list;while(p){q=p->next;free(p);p=q;}*list=NULL;
}

6、實例分析

要求：
輸入一組整數(大于10個數),以0作為結束標志，將這組整數存放到一個鏈表中(結束標志0不包括在內)，打印出該鏈表中的值。然后刪除該鏈表中的第5個元素，打印出刪除后的結果。最后在內存中釋放掉該鏈表。

#include "stdio.h"
#include "malloc.h"
#include "conio.h"typedef int ElemType;
//指針定義
typedef struct node {ElemType data;		//數據域struct node* next;	//指針域
}LNode, * LinkList;//***********創建鏈表******************//
//
LinkList GreatLinkList(int n)
{//建立一個長度為n的鏈表LinkList p, r=NULL, list = NULL;		//p:相當于每次新建結點的暫存器，r:相當于插入結點的上一個結點,永遠指向原先鏈表的最后一個結點。list鏈表的頭指針ElemType elem;				//獲取暫存數據int i;						//定義累加器for (i = 0;i < n;i++){scanf("%d", &elem);p = (LinkList)malloc(sizeof(LNode));	//分配內存，并將首地址送到pp->data = elem;			//置入數據p->next = NULL;			//指針指向NULL，暫時不考慮下一個結點if (!list)				//如果鏈表為空，則新創建的結點就是該鏈表的第一個結點list = p;else					//如果鏈表不為空，則將新建立的結點連接到之前鏈表的尾部r->next = p;r = p;					//將p結點的數據賦給r}return list;				//將鏈表的頭指針返回主調函數，通過list就可以訪問鏈表中的每個結點，并進行操作	
}//*************插入結點************//
//
void insertList(LinkList* list, LinkList q, ElemType e)
{//向鏈表中由指針q指向的結點后面插入結點，結點數據位eLinkList p;p = (LinkList)malloc(sizeof(LNode));		//生成一個新節點，由p指向它p->data = e;if (!*list)				//如果鏈表為空{*list = p;p->next = NULL;}						//當鏈表為空的時候，q沒有意義，只能在頭結點后面插入第一個元素else{//當鏈表不為空的時候，認為q指向的結點一定存在//將q指向的結點的next域的值賦給p指向的結點的next域p->next = q->next;q->next = p;}
}
//通過這個算法同樣可以創建一個鏈表，因為鏈表為空時，list==NULL，可以自動創建一個結點。在下面創建其他結點時，只要始終將指針q指向鏈表的最后一個結點，就可以創建出一個鏈表//刪除結點
void delLink(LinkList* list, LinkList q)
{LinkList r;if (q == *list)//情況1：q指向鏈表的第一個結點{*list = q->next;free(q);}else				//情況3：q指向的結點前驅結點的指針未知{for (r = *list;r->next != q;r = r->next);	//遍歷鏈表，找到q的前驅結點的指針if (r->next != NULL){r->next = q->next;			//從鏈表中刪除q指向的結點free(q);}}
}//銷毀鏈表
void destroyLinkList(LinkList* list)
{LinkList p, q;p = *list;while (p){q = p->next;free(p);p = q;}*list = NULL;
}void print_linklist(LinkList show_list)
{while (show_list){printf("%d ",show_list->data);show_list = show_list->next;}
}
int main()
{int elem = 0;   //定義中間變量數據int i = 0;      //定義累加器LinkList L, q;  q = L = GreatLinkList(1);       //創建1個鏈表結點，q和L指向該結點scanf("%d",&elem);while (elem)                    //循環地輸入數據，同時插入新生成的結點，結束條件：輸入數據為0{insertList(&L,q,elem);q = q->next;scanf("%d", &elem);}q = L;printf("The content of the linklist\n");print_linklist(q);q = L;printf("\n Delete the fifth element\n");for (i=0;i<4;i++)           //將指針q指向第五個元素{if (q == NULL)     //確保此時鏈表的長度大于等于5，否則是非法操作{printf("The length of the linklist is smaller than 5");_getche();return 0;}q = q->next;}delLink(&L,q);q = L;print_linklist(q);destroyLinkList(&L);return 0;
}

result: