前言
上一篇我們已經(jīng)完成了順序表的實(shí)現(xiàn)和基本操作<元素的增加、刪除和查找>
(鏈接直達(dá)：線性表元素的基本操作（C語(yǔ)言）【數(shù)據(jù)結(jié)構(gòu)】-CSDN博客)
我們知道順序表支持隨機(jī)訪問(wèn)，可以通過(guò)下標(biāo)來(lái)直接訪問(wèn)，同時(shí)也可以進(jìn)行排序等優(yōu)點(diǎn)；但是仍存在局限性，對(duì)順序表的中部進(jìn)行增加或刪除元素的時(shí)間復(fù)雜度高，均為O(n)；同時(shí)要求大片連續(xù)空間進(jìn)行存儲(chǔ)，改變?nèi)萘恳膊皇呛芊奖恪?/p>
因?yàn)槲覀円胄碌木€性表——鏈表。
單鏈表
一、單鏈表的基本概念
單鏈表（Singly Linked List）是一種常用的數(shù)據(jù)結(jié)構(gòu)，它由若干個(gè)結(jié)點(diǎn)組成，每個(gè)結(jié)點(diǎn)包含兩部分：數(shù)據(jù)域和指針域。數(shù)據(jù)域用于存儲(chǔ)數(shù)據(jù)，而指針域則用于指向下一個(gè)節(jié)點(diǎn)的地址。單鏈表中每個(gè)結(jié)點(diǎn)只有一個(gè)指針域，指向下一個(gè)結(jié)點(diǎn)，最后一個(gè)結(jié)點(diǎn)的指針域指向 NULL，表示鏈表的結(jié)尾。
從這里我們可以很清楚的看見(jiàn)每個(gè)結(jié)點(diǎn)分為數(shù)據(jù)域和指針域。
//在結(jié)構(gòu)體中定義數(shù)據(jù)域和指針域
typedef struct LNode {
int data; //每個(gè)節(jié)點(diǎn)存放一個(gè)數(shù)據(jù)元素
struct LNode *next; //指針指向下一個(gè)節(jié)點(diǎn)
}LNode, *LinkList;相比于順序表，單鏈表的存儲(chǔ)不要求大片連續(xù)存儲(chǔ)空間，因此改變?nèi)萘渴址奖恪?/p>
對(duì)比下圖便可直觀感受到單鏈表易更改性。
二、單鏈表的實(shí)現(xiàn)
1.單鏈表的創(chuàng)建
單鏈表的創(chuàng)建分為頭插法和尾插法。
(1)頭插法：
輸入的數(shù)據(jù)次序生成的鏈表結(jié)點(diǎn)次序相反，例如：按{1,2,3}順序進(jìn)行頭插之后，最終排序卻變成了{(lán)3,2,1}，換言之就是逆序插入。
以下便是代碼圖解，e為需要插入到單鏈表L中的結(jié)點(diǎn)
頭插法代碼實(shí)現(xiàn)：
//利用頭插法創(chuàng)建鏈表
LNode *Init_LinkList_head(LinkList L) {
//創(chuàng)建頭結(jié)點(diǎn)
LinkList head = (LinkList) malloc(sizeof(LinkList));
//保證頭結(jié)點(diǎn)沒(méi)有存儲(chǔ)臟數(shù)據(jù)
head->next = NULL;
//創(chuàng)建輸入數(shù)據(jù)的常量
int val = -1; //定義-1表示輸入結(jié)束標(biāo)志
int len = 0; //觀察單鏈表的長(zhǎng)度
while (true) {
printf("請(qǐng)輸入鏈表中的元素：");
scanf("%d", &val);
if (val == -1) {
break;
}
//創(chuàng)建新的結(jié)點(diǎn)
LinkList s = (LinkList) malloc(sizeof(LinkList));
s->data = val; //將輸入的數(shù)據(jù)賦值到新結(jié)點(diǎn)的數(shù)據(jù)域中
s->next = head->next;
head->next = s; //將新結(jié)點(diǎn)連接到頭指針中
len++;
}
printf("鏈表的長(zhǎng)度為：%d\n", len);
return head; //返回單鏈表
}
int main() {
LinkList L = Init_LinkList_head(L);
PrintLinkList(L);
return 0;
}例：向空鏈表中插入{10，20，30，40，50，60}構(gòu)成新的單鏈表。
(2)尾插法：
輸入的數(shù)據(jù)次序生成的鏈表結(jié)點(diǎn)次序相同，例如：按{1,2,3}順序進(jìn)行頭插之后，最終排序還是{1,2,3}，換言之就是順序插入。
以下便是代碼圖解，e為需要插入到單鏈表L中的結(jié)點(diǎn)
尾插法的代碼實(shí)現(xiàn)：
在此方法中我們添加了一個(gè)尾結(jié)點(diǎn)，設(shè)置尾結(jié)點(diǎn)的目的是為了提高插入操作的效率。如果沒(méi)有尾結(jié)點(diǎn)，每次進(jìn)行尾插入操作時(shí)，都需要遍歷整個(gè)鏈表找到最后一個(gè)結(jié)點(diǎn)，然后再進(jìn)行插入操作。這樣的時(shí)間復(fù)雜度是O(n)，其中n是鏈表的長(zhǎng)度。
而如果設(shè)置了尾結(jié)點(diǎn)，每次進(jìn)行尾插入操作時(shí)，只需要直接將新結(jié)點(diǎn)插入到尾結(jié)點(diǎn)之后，并更新尾結(jié)點(diǎn)的指針即可，不需要遍歷整個(gè)鏈表。這樣的時(shí)間復(fù)雜度是O(1)，效率更高。
//利用尾插法創(chuàng)建鏈表
LinkList Init_LinkList_tail(LinkList L) {
//創(chuàng)建頭結(jié)點(diǎn)
LinkList head = (LinkList) malloc(sizeof(LinkList));
//頭結(jié)點(diǎn)的指針域置空，說(shuō)明當(dāng)前鏈表是空的
head->next = NULL;
int val = -1;
int len = 0;
//創(chuàng)建尾節(jié)點(diǎn)
LinkList ptr = (LinkList) malloc(sizeof(LinkList));
ptr = head; //開(kāi)始時(shí)指向頭節(jié)結(jié)點(diǎn)，中間沒(méi)有數(shù)據(jù)
//循環(huán)的向鏈表中添加元素，直至找到結(jié)束標(biāo)志后退出輸入環(huán)節(jié)
while (true) {
printf("請(qǐng)輸入鏈表中的元素：");
scanf("%d", &val);
if (val == -1) { //輸入結(jié)束標(biāo)志
break;
}
LinkList s = (LinkList) malloc(sizeof(LinkList)); //申請(qǐng)新的結(jié)點(diǎn)
s->data = val;
s->next = NULL;
ptr->next = s; // 將新的結(jié)點(diǎn)鏈接到尾結(jié)點(diǎn)中
ptr = s; //更新尾結(jié)點(diǎn)，添加完新的結(jié)點(diǎn)后將新的結(jié)點(diǎn)設(shè)為尾結(jié)點(diǎn)
len++;
}
printf("鏈表的長(zhǎng)度為：%d\n", len);
return head;
}
int main() {
LinkList L = Init_LinkList_tail(L);
PrintLinkList(L);
return 0;
}例：向空鏈表中插入{10，20，30，40，50，60}構(gòu)成新的單鏈表。
一般地，頭插法的重要應(yīng)用便是鏈表的逆置，尾插法可能多用于自己的學(xué)習(xí)研究，接下來(lái)單鏈表的基本操作我們均以尾插法來(lái)創(chuàng)建鏈表并加以闡述。
2.單鏈表的查找
單鏈表的查找分為按值查找和按位查找。
我們這里默認(rèn)討論帶頭結(jié)點(diǎn)的單鏈表。
(1)按位查找
單鏈表不具備“隨機(jī)訪問(wèn)“的特性，只能依次掃描每個(gè)結(jié)點(diǎn)并對(duì)比數(shù)據(jù)域中是否為目標(biāo)值。
基本思路：從單鏈表中的第一個(gè)結(jié)點(diǎn)出發(fā)，順時(shí)針next域逐個(gè)往下搜索，直到找到第i個(gè)結(jié)點(diǎn)為止，否則返回最后一個(gè)結(jié)點(diǎn)指針域NULL。
平均時(shí)間復(fù)雜度：O(n)
創(chuàng)建一個(gè)指針P，并從頭結(jié)點(diǎn)開(kāi)始遍歷單鏈表，直至找到目標(biāo)元素。
代碼實(shí)現(xiàn)：
//按位查找元素
void Search_LinkList_site(LinkList L) {
//創(chuàng)建新的結(jié)點(diǎn)
LinkList p = (LinkList) malloc(sizeof(LinkList));
//結(jié)點(diǎn)p從頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)開(kāi)始遍歷，即第一個(gè)存儲(chǔ)數(shù)據(jù)的結(jié)點(diǎn)開(kāi)始遍歷
p = L->next;
int j = 1;
printf("請(qǐng)輸入想要查找元素的位置：");
int i;
scanf("%d", &i);
while (p != NULL && j < i) { // p若為空則說(shuō)明鏈表已遍歷結(jié)束
j++;
p = p->next; //依次指向下一個(gè)結(jié)點(diǎn)
}
int elem = p->data; //獲取目標(biāo)位置的元素
printf("鏈表中第%d元素是%d\n", i, elem);
}
例：查找鏈表{10,20,30,40,50,60}中第3位元素。
(2)按值查找
基本思路：從單鏈表中的第一個(gè)結(jié)點(diǎn)出發(fā)，順時(shí)針next域逐個(gè)往下搜索，直到找到第i個(gè)結(jié)點(diǎn)的數(shù)據(jù)域與目標(biāo)值相等為止，否則返回最后一個(gè)結(jié)點(diǎn)指針域NULL。
平均時(shí)間復(fù)雜度：O(n)
創(chuàng)建一個(gè)指針p，從單鏈表的第一個(gè)結(jié)點(diǎn)開(kāi)始遍歷，每次比較結(jié)點(diǎn)的數(shù)據(jù)域和目標(biāo)值。
代碼實(shí)現(xiàn)：
//按值查找元素
void Search_LinkList_value(LinkList L) {
LinkList p = (LinkList) malloc(sizeof(LinkList));
p = L->next;
int cnt = 1;
int e;
printf("請(qǐng)輸入需要查找的元素：");
scanf("%d", &e);
while (p != NULL && p->data != e) { //比較每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域是否為目標(biāo)值
cnt++;
p = p->next;
}
printf("元素%d是鏈表中第%d位元素。\n", e, cnt);
}例：查找鏈表{10,20,30,40,50,60}中{60}元素所在位置。
單鏈表的查找主要思想是遍歷整個(gè)鏈表，從而找到目標(biāo)數(shù)值或目標(biāo)位置。
3.單鏈表的元素插入
單鏈表的插入分為按位序插入和按指定結(jié)點(diǎn)插入兩大類。
(1)按位序插入
在單鏈表L中的第i個(gè)位置上插入指定元素e。要在第i個(gè)位置上插入指定元素，那就應(yīng)該要找到第i-1個(gè)結(jié)點(diǎn)，并將新結(jié)點(diǎn)插入其后。
過(guò)程分析：
1.要找到第i-1個(gè)結(jié)點(diǎn)；(若i=2,就需要找到i=1的第一個(gè)結(jié)點(diǎn))
2.然后需要用malloc函數(shù)申請(qǐng)一個(gè)新的結(jié)點(diǎn)s;
3.將數(shù)據(jù)元素e存入到這個(gè)結(jié)點(diǎn);
4.假設(shè)第i-1的結(jié)點(diǎn)為*p;
5.新結(jié)點(diǎn)s的指針域指向p的后繼結(jié)點(diǎn)；
6.令p的指針域指向新插入結(jié)點(diǎn)s; (5與6的順序不能顛倒)
7.按位序插入成功；
代碼實(shí)現(xiàn)：
//按位序插入
void Insert_LinkList_appoint(LinkList L) {
LinkList p = (LinkList) malloc(sizeof(LinkList));
p = L;
int j = 0;
int site;
printf("請(qǐng)輸入需要插入的位置：");
scanf("%d",&site);
//通過(guò)循環(huán)找到指定元素的前驅(qū)
while (p != NULL && j < site - 1) {
j++;
p = p->next;
}
//判斷接下來(lái)插入位置是否合法
if (p == NULL) {
//site值不合法，超出鏈表長(zhǎng)度，說(shuō)明第site-1個(gè)結(jié)點(diǎn)不存在
printf("插入的位置不合法！\n");
} else {
printf("請(qǐng)輸入需要插入的元素：");
//創(chuàng)建需要插入的節(jié)點(diǎn)
LinkList s = (LinkList) malloc(sizeof(LinkList));
scanf("%d", &(s->data));
s->next = p->next;
p->next = s;
}
}例：向鏈表{10,20,40,50,60}中的第3號(hào)位置插入元素{30}。
健壯性測(cè)試：輸入的site值不合法，例在鏈表{10,20,30}的第8號(hào)位置插入元素。
(2)按指定結(jié)點(diǎn)的插入操作
a.在指定結(jié)點(diǎn)之后插入（后插）
后插操作：給定一個(gè)指定結(jié)點(diǎn)，在此結(jié)點(diǎn)之后插入一個(gè)數(shù)據(jù)元素e。單鏈表的結(jié)點(diǎn)結(jié)構(gòu)使得單鏈表的鏈接指針只能往后尋找，所以如果給定一個(gè)指定結(jié)點(diǎn)p,那么p結(jié)點(diǎn)之后的結(jié)點(diǎn)都是可知的，p結(jié)點(diǎn)之前的結(jié)點(diǎn)都是未知的。
代碼實(shí)現(xiàn)：
//后插操作，在p結(jié)點(diǎn)之后插入元素e.
bool InsertNextNode(LinkList p,int e){
if(p==NULL) //結(jié)點(diǎn)p不合法
return false;
LinkList s = (LinkList) malloc(sizeof(LinkList));//申請(qǐng)新結(jié)點(diǎn)
s->data=e; //在新結(jié)點(diǎn)中存入數(shù)據(jù)元素e
s->next =p->next; //結(jié)點(diǎn)p的下一個(gè)結(jié)點(diǎn)由新結(jié)點(diǎn)s來(lái)鏈接；
p->next=s;
return true; //插入成功！
}實(shí)現(xiàn)之后的效果：
后插操作主要找到指定結(jié)點(diǎn)之后便可以直接執(zhí)行插入操作，因此時(shí)間復(fù)雜度是O(1)。
b.在指定結(jié)點(diǎn)之前插入（前插）
在指定某一結(jié)點(diǎn)的前面插入一個(gè)新的結(jié)點(diǎn)。由于單鏈表只能從頭向尾遍歷，那么我們?cè)趺凑业街付ńY(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)呢？（后面的雙鏈表可以直接指向p-prior）
此時(shí)我們可以傳入一個(gè)頭指針，利用頭指針循環(huán)查找結(jié)點(diǎn)p；找到p的前驅(qū)結(jié)點(diǎn)q，再對(duì)結(jié)點(diǎn)q進(jìn)行后插；從而完成結(jié)點(diǎn)q的前插操作。
時(shí)間復(fù)雜度：O(n)
代碼實(shí)現(xiàn)：
//前插操作，在p結(jié)點(diǎn)之前插入元素e.
bool InsertPriorNode(LinkList p,int e){
if(p==NULL) //結(jié)點(diǎn)p不合法
return false;
LinkList s = (LinkList) malloc(sizeof(LinkList));//申請(qǐng)新結(jié)點(diǎn)
s->next=p->next;
p->next=s; //將新結(jié)點(diǎn)連接到p之后
s->data=p->data; //將p中元素復(fù)制到s中
p->data=e; //將p中元素被覆蓋為e
return true; //插入成功！
}4.單鏈表的元素刪除
單鏈表的刪除分為按位序刪除和指定結(jié)點(diǎn)的刪除。
(1)按位序刪除
找到第i-1個(gè)結(jié)點(diǎn)，將其指針指向第i+1個(gè)結(jié)點(diǎn)，并釋放第i個(gè)結(jié)點(diǎn)
檢查刪除位置的合法性；
查找表中的第i-1個(gè)結(jié)點(diǎn)——被刪結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)
修改指針域和返回被刪數(shù)據(jù)域的元素
刪除成功!
最壞、最好時(shí)間復(fù)雜度：O(n)
最好時(shí)間復(fù)雜度：O(1)——被刪結(jié)點(diǎn)是第一個(gè)結(jié)點(diǎn)。
代碼實(shí)現(xiàn)：
//按位序刪除
void ListDelete(LinkList L) {
//判斷L是否存在元素
if (L == NULL) {
printf("鏈表為空，無(wú)法刪除結(jié)點(diǎn)\n");
return;
}
LinkList p = (LNode *) malloc(sizeof(LinkList));
p = L; //指針P指向當(dāng)前結(jié)點(diǎn)
int j = 0;
int site;
printf("請(qǐng)輸入需要?jiǎng)h除結(jié)點(diǎn)的位置：");
scanf("%d",&site);
while (p != NULL && j < site - 1) { //通過(guò)循環(huán)遍歷到site - 1的結(jié)點(diǎn)處
p = p->next;
j++;
}
// 如果位置超出鏈表長(zhǎng)度
if (p == NULL || p->next == NULL) {
printf("位置超出鏈表長(zhǎng)度，無(wú)法刪除結(jié)點(diǎn)\n");
return;
}
LinkList q = (LNode *) malloc(sizeof(LinkList));
q = p->next->next; //令q指向被刪除的結(jié)點(diǎn)
int e = p->next->data; //獲取被刪除結(jié)點(diǎn)的數(shù)據(jù)
free(p->next); //釋放結(jié)點(diǎn)的存儲(chǔ)空間
p->next = q;
printf("成功刪除元素%d\n", e);
}例：將鏈表{10，20，30，40，50}中的第4個(gè)結(jié)點(diǎn)進(jìn)行刪除。
健壯性測(cè)試：若輸入的位置超過(guò)鏈表的長(zhǎng)度則會(huì)刪除失敗！
(2)指定結(jié)點(diǎn)刪除
刪除單鏈表中指定結(jié)點(diǎn)的基本原理如下：
- 遍歷鏈表，找到要?jiǎng)h除的結(jié)點(diǎn)以及其前驅(qū)結(jié)點(diǎn)。
- 將前驅(qū)結(jié)點(diǎn)的
next指針指向要?jiǎng)h除結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，跳過(guò)要?jiǎng)h除的結(jié)點(diǎn)。 - 釋放要?jiǎng)h除的結(jié)點(diǎn)的內(nèi)存空間，防止內(nèi)存泄漏。
代碼實(shí)現(xiàn)：
//指定結(jié)點(diǎn)刪除操作
void ListDelete_point(LinkList L) {
//初始化兩個(gè)指針p和s，分別指向鏈表的頭結(jié)點(diǎn)和空指針。
LinkList p = (LNode *) malloc(sizeof(LinkList));
LinkList s = (LNode *) malloc(sizeof(LinkList));
p = L;
s = NULL;
//定義目標(biāo)結(jié)點(diǎn)的值
int key;
printf("請(qǐng)輸入需要目標(biāo)結(jié)點(diǎn)的值：");
scanf("%d",&key);
//頭結(jié)點(diǎn)便是目標(biāo)位置的情況，直接將頭指針指向下一個(gè)結(jié)點(diǎn)
if(p != NULL && p->data == key){
L = p->next;
free(p);
return;
}
//遍歷鏈表直到找到要?jiǎng)h除的結(jié)點(diǎn)
while (p != NULL && p->data != key){
s = p;
p = p->next;
}
if(p == NULL){
printf("沒(méi)有找到目標(biāo)結(jié)點(diǎn)的值，刪除失??！\n");
return;
}
s->next = p->next; //跳過(guò)要?jiǎng)h除的結(jié)點(diǎn)
free(p); //釋放要?jiǎng)h除的結(jié)點(diǎn)的內(nèi)存空間
printf("刪除成功！\n刪除后的鏈表為：");
}例：將鏈表{10，20，30，40，50}中的數(shù)據(jù)域?yàn)?0的結(jié)點(diǎn)進(jìn)行刪除。
如果整個(gè)鏈表中都沒(méi)有找到目標(biāo)值則會(huì)返回查找失??！
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-847038.html
注意區(qū)分這兩種刪除的區(qū)別：文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-847038.html
- 指定結(jié)點(diǎn)刪除是根據(jù)結(jié)點(diǎn)的數(shù)值來(lái)確定要?jiǎng)h除的結(jié)點(diǎn)，即刪除具有特定數(shù)值的結(jié)點(diǎn)。
- 按照位序刪除是根據(jù)結(jié)點(diǎn)在鏈表中的位置（位序）來(lái)確定要?jiǎng)h除的結(jié)點(diǎn)，即刪除鏈表中的第n個(gè)結(jié)點(diǎn)。
到了這里，關(guān)于單鏈表——單鏈表的定義及基本操作（頭插法尾插法建表、查找、插入、刪除等）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
