鏈表是一種物理存儲(chǔ)單元上非連續(xù)垂券、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(diǎn)（鏈表中每一個(gè)元素稱為結(jié)點(diǎn)）組成于微，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成蹋嵌。每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域育瓜，另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域。
1.png
一栽烂、鏈表的創(chuàng)建操作
剛開始躏仇，鏈表為空恋脚。咱們需要?jiǎng)?chuàng)建一個(gè)頭節(jié)點(diǎn)。頭節(jié)點(diǎn)可以用來存儲(chǔ)節(jié)點(diǎn)數(shù)據(jù)焰手，也可以不存儲(chǔ)節(jié)點(diǎn)數(shù)據(jù)糟描。咱們這里以不存儲(chǔ)數(shù)據(jù)為例。
（1）創(chuàng)建頭節(jié)點(diǎn)
因?yàn)轭^節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)书妻，所以頭節(jié)點(diǎn)的數(shù)據(jù)域可初始化為0或-1船响，也可以不用初始化，系統(tǒng)會(huì)自動(dòng)分配一個(gè)隨機(jī)數(shù)驻子。
2.png
（2）插入第一個(gè)節(jié)點(diǎn)
3.png
上面這個(gè)圖也可以簡化表示為：
4.png
（3）插入第二個(gè)節(jié)點(diǎn)
這里咱們假定不用考慮節(jié)點(diǎn)數(shù)據(jù)域值的大小順序灿意，直接插到鏈表的末尾即可。若要按數(shù)據(jù)域大小排序崇呵，插入時(shí)加個(gè)判斷即可缤剧。
5.png
實(shí)現(xiàn)代碼：
#include<stdio.h>
#include<malloc.h>
typedef int ElementType; // 定義數(shù)據(jù)類型,可根據(jù)需要進(jìn)行其他類型定義
// 定義鏈表結(jié)點(diǎn)
typedef struct ListNode
{
ElementType Element; // 數(shù)據(jù)域，存放數(shù)據(jù)
ListNode* Next; // 指向下一個(gè)鏈表節(jié)點(diǎn)
}Node, *PNode;
// 鏈表創(chuàng)建函數(shù)定義
PNode createList(void)
{
// 創(chuàng)建分配一個(gè)頭節(jié)點(diǎn)內(nèi)存空間域慷，頭節(jié)點(diǎn)相當(dāng)于鏈表的哨兵荒辕，不存放數(shù)據(jù)
PNode pHead = (PNode)malloc(sizeof(Node));
if (pHead == NULL) // 判斷是否分配成功
{
printf("空間分配失敗 \n");
exit(-1);
}
PNode pTail = pHead; // 鏈表的末尾節(jié)點(diǎn)，初始指向頭節(jié)點(diǎn)
pTail->Next = NULL; // 最后一個(gè)節(jié)點(diǎn)指針置為空
int len ; // 用于定義鏈表長度
int val ; // 用于存放節(jié)點(diǎn)數(shù)值
printf("請輸入節(jié)點(diǎn)個(gè)數(shù)：");
scanf("%d", &len); // 輸入節(jié)點(diǎn)個(gè)數(shù)
for (int i = 0; i < len; i++)
{
PNode pNew = (PNode)malloc(sizeof(Node)); // 分配一個(gè)新節(jié)點(diǎn)
if (pNew == NULL)
{
printf("分配新節(jié)點(diǎn)失敗\n");
exit(-1);
}
printf("請輸入第 %d 個(gè)節(jié)點(diǎn)的數(shù)據(jù)：", i + 1);
scanf("%d", &val); // 輸入鏈表節(jié)點(diǎn)的數(shù)據(jù)
pNew->Element = val; // 把數(shù)據(jù)賦值給節(jié)點(diǎn)數(shù)據(jù)域
pTail->Next = pNew; // 末尾節(jié)點(diǎn)指針指向下一個(gè)新節(jié)點(diǎn)
pNew->Next = NULL; // 新節(jié)點(diǎn)指針指向?yàn)榭? pTail = pNew; // 將新節(jié)點(diǎn)復(fù)制給末尾節(jié)點(diǎn)
}
printf("創(chuàng)建鏈表成功\n");
return pHead; // 返回頭節(jié)點(diǎn)
}
int main()
{
createList(); //創(chuàng)建一個(gè)指針犹褒，使其指向新創(chuàng)建的鏈表的頭指針
return 0;
}
運(yùn)行結(jié)果：
請輸入節(jié)點(diǎn)個(gè)數(shù)：5
請輸入第 1 個(gè)節(jié)點(diǎn)的數(shù)據(jù)：10
請輸入第 2 個(gè)節(jié)點(diǎn)的數(shù)據(jù)：20
請輸入第 3 個(gè)節(jié)點(diǎn)的數(shù)據(jù)：30
請輸入第 4 個(gè)節(jié)點(diǎn)的數(shù)據(jù)：40
請輸入第 5 個(gè)節(jié)點(diǎn)的數(shù)據(jù)：50
創(chuàng)建鏈表成功
二抵窒、鏈表的遍歷操作
實(shí)現(xiàn)代碼：
// 定義鏈表遍歷函數(shù)
void traverseList(PNode head)
{
PNode P = head->Next; // 首節(jié)點(diǎn)賦值給臨時(shí)節(jié)點(diǎn)P
printf("遍歷鏈表的值為：");
if (P == NULL)
{
printf("鏈表為空");
}
while (P != NULL) // 當(dāng)臨時(shí)節(jié)點(diǎn)P不為尾節(jié)點(diǎn)時(shí)，輸出當(dāng)前節(jié)點(diǎn)值
{
printf("%d ", P->Element);
P = P->Next;
}
printf("\n");
}
三叠骑、鏈表的查詢操作
// 定義鏈表查詢函數(shù)
PNode findNode(PNode head)
{
PNode P = head->next; // 定義臨時(shí)指針P指向首節(jié)點(diǎn)的地址
int num = 0; // 用于記錄鏈表節(jié)點(diǎn)位置
int val = 0; // 用于存放要查詢的值
printf("請輸入要查詢的數(shù)：");
scanf("%d", &val); // 輸入要查詢的數(shù)值
while (P != NULL && P->Element != val)
{
P = P->Next;
++num;
}
if (P != NULL)
{
printf("找到的節(jié)點(diǎn)為：%d", num + 1);
}
else
{
printf("找不到該節(jié)點(diǎn)");
}
printf("\n");
return P;
}
四李皇、鏈表的插入操作
假設(shè)要插入到節(jié)點(diǎn)p和q之間，則需要執(zhí)行兩步操作：
（1）s-> next = q宙枷，這是讓s的next指向q掉房；
（2）p->next = s，這是讓s成為p的下一個(gè)結(jié)點(diǎn)慰丛，此時(shí)p的next不再指向q卓囚。
6.png
上面這個(gè)圖也可簡化表示為：
7.png
實(shí)現(xiàn)代碼：
// 定義鏈表插入函數(shù)
// 在鏈表位置第pos節(jié)點(diǎn)前插入包含數(shù)據(jù)val的節(jié)點(diǎn)
void insertNode(PNode head, int pos, int val)
{
int position = 0;
PNode P = head; // 定義節(jié)點(diǎn)p指向頭節(jié)點(diǎn)
// 尋找pos節(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)
while (P != NULL&&position<pos - 1)
{
P = P->Next;
++position;
}
PNode tmp = (PNode)malloc(sizeof(Node)); // 分配一個(gè)臨時(shí)節(jié)點(diǎn)用來存儲(chǔ)要插入的數(shù)據(jù)
if (tmp == NULL)
{
printf("內(nèi)存分配失敗诅病！");
exit(-1);
}
// 插入節(jié)點(diǎn)
tmp->Element = val;
tmp->Next = P->Next;
P->Next = tmp;
}
五哪亿、鏈表的刪除操作
（一）刪除整個(gè)鏈表
實(shí)現(xiàn)代碼：
// 定義刪除整個(gè)鏈表函數(shù)
void deleteList(PNode head)
{
PNode P, tmp;
P = head->Next; //定義指針P指向鏈表要?jiǎng)h除的鏈表List的第一個(gè)點(diǎn)節(jié)點(diǎn)
List->Next = NULL;
while (P != NULL)
{
tmp = P->Next; //臨時(shí)Tmp指向要?jiǎng)h除的節(jié)點(diǎn)的下個(gè)節(jié)點(diǎn)
free(P); //釋放指針P指向的節(jié)點(diǎn)
P = tmp; //重新賦值
}
printf("刪除鏈表成功！\n");
}
（二）刪除鏈表中的節(jié)點(diǎn)
假如要?jiǎng)h掉s節(jié)點(diǎn)贤笆，則需要做兩步操作：
（1）p->next = s->next蝇棉，讓s的下一個(gè)節(jié)點(diǎn)即q，變成p的下一個(gè)節(jié)點(diǎn)芥永；
8.png
（2）free(s)银萍，把s節(jié)點(diǎn)從內(nèi)存里釋放。
9.png
實(shí)現(xiàn)代碼：
// 定義刪除鏈表元素函數(shù)
// 刪除鏈表中的第pos個(gè)節(jié)點(diǎn)
void deleteNode(PNode head, int pos)
{
int position = 0;
PNode P = head; // 定義一個(gè)指針p指向鏈表頭節(jié)點(diǎn)
// 尋找pos節(jié)點(diǎn)位置的前驅(qū)節(jié)點(diǎn)
while (P != NULL&&position < pos - 1)
{
P = P->Next;
++position;
}
// 刪除節(jié)點(diǎn)
PNode tmp = P->Next; // 定義臨時(shí)指針Tmp指向要?jiǎng)h除的節(jié)點(diǎn)
P->Next = tmp->Next; // 使要?jiǎng)h除節(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)指向其后驅(qū)節(jié)點(diǎn)
free(tmp); // 釋放刪除節(jié)點(diǎn)的內(nèi)存空間恤左，防止內(nèi)存泄漏
tmp = NULL; // 使q指向空指針贴唇，防止產(chǎn)生野指針
}
六、完整代碼實(shí)現(xiàn)
#include<stdio.h>
#include<malloc.h>
typedef int ElementType; // 定義數(shù)據(jù)類型,可根據(jù)需要進(jìn)行其他類型定義
// 鏈表節(jié)點(diǎn)的定義
typedef struct ListNode
{
ElementType Element; // 數(shù)據(jù)域飞袋，存放數(shù)據(jù)
ListNode* Next; // 指向下一個(gè)鏈表節(jié)點(diǎn)
}Node, *PNode;
// 函數(shù)聲明
PNode createList(void); // 聲明創(chuàng)建鏈表函數(shù)
void traverseList(PNode head); // 聲明遍歷鏈表函數(shù)
void insertNode(PNode head, int pos, int val); // 聲明鏈表插入函數(shù)
void deleteList(PNode head); // 聲明刪除整個(gè)鏈表函數(shù)
void deleteNode(PNode head, int pos); // 聲明刪除鏈表元素函數(shù)
PNode findNode(PNode head); // 聲明鏈表查詢函數(shù)
int main()
{
PNode head = createList(); // 創(chuàng)建一個(gè)指針戳气，使其指向新創(chuàng)建的鏈表的頭指針
traverseList(head); // 遍歷鏈表
findNode(head); // 鏈表查詢
insertNode(head, 3, 100); // 鏈表插入，在第三個(gè)位置插入數(shù)值100
traverseList(head);
deleteNode(head, 3); // 刪除鏈表第三個(gè)節(jié)點(diǎn)
traverseList(head);
deleteList(head); // 刪除整個(gè)鏈表
traverseList(head);
return 0;
}
// 創(chuàng)建鏈表函數(shù)定義
PNode createList(void)
{
int len ; // 用于定義鏈表長度
int val ; // 用于存放節(jié)點(diǎn)數(shù)值
PNode pHead = (PNode)malloc(sizeof(Node)); // 創(chuàng)建分配一個(gè)頭節(jié)點(diǎn)內(nèi)存空間
if (pHead == NULL) // 判斷是否分配成功
{
printf("空間分配失敗 \n");
exit(-1);
}
PNode pTail = pHead; // 鏈表的末尾節(jié)點(diǎn)巧鸭，初始指向頭節(jié)點(diǎn)
pTail->Next = NULL; // 最后一個(gè)節(jié)點(diǎn)指針置為空
printf("請輸入節(jié)點(diǎn)個(gè)數(shù)：");
scanf("%d", &len); // 輸入節(jié)點(diǎn)個(gè)數(shù)
for (int i = 0; i < len; i++)
{
PNode pNew = (PNode)malloc(sizeof(Node)); // 分配一個(gè)新節(jié)點(diǎn)
if (pNew == NULL)
{
printf("分配新節(jié)點(diǎn)失敗\n");
exit(-1);
}
printf("請輸入第 %d 個(gè)節(jié)點(diǎn)的數(shù)據(jù)：", i + 1);
scanf("%d", &val); // 輸入鏈表節(jié)點(diǎn)的數(shù)據(jù)
pNew->Element = val; // 把數(shù)據(jù)賦值給節(jié)點(diǎn)數(shù)據(jù)域
pTail->Next = pNew; // 末尾節(jié)點(diǎn)指針指向下一個(gè)新節(jié)點(diǎn)
pNew->Next = NULL; // 新節(jié)點(diǎn)指針指向?yàn)榭? pTail = pNew; // 將新節(jié)點(diǎn)復(fù)制給末尾節(jié)點(diǎn)
}
printf("創(chuàng)建鏈表成功\n");
return pHead; // 返回頭節(jié)點(diǎn)
}
// 定義鏈表遍歷函數(shù)
void traverseList(PNode head)
{
PNode P = head->Next; // 首節(jié)點(diǎn)賦值給臨時(shí)節(jié)點(diǎn)P
printf("遍歷鏈表的值為：");
if (P == NULL)
{
printf("鏈表為空");
}
while (P != NULL) //當(dāng)臨時(shí)節(jié)點(diǎn)P不為尾節(jié)點(diǎn)時(shí)瓶您，輸出當(dāng)前節(jié)點(diǎn)值
{
printf("%d ", P->Element);
P = P->Next;
}
printf("\n");
}
// 定義鏈表查詢函數(shù)
PNode findNode(PNode head)
{
PNode P = head->Next; // 定義臨時(shí)指針P指向首節(jié)點(diǎn)的地址
int num = 0; // 用于記錄鏈表節(jié)點(diǎn)位置
int val = 0; // 用于存放要查詢的值
printf("請輸入要查詢的數(shù)：");
scanf("%d", &val); // 輸入要查詢的數(shù)值
while (P != NULL&&P->Element != val)
{
P = P->Next;
++num;
}
if (P != NULL)
{
printf("找到的節(jié)點(diǎn)為：%d", num + 1);
}
else
{
printf("找不到該節(jié)點(diǎn)");
}
printf("\n");
return P;
}
// 定義鏈表插入函數(shù)
// 在鏈表位置第pos節(jié)點(diǎn)前插入包含數(shù)據(jù)val的節(jié)點(diǎn)
void insertNode(PNode head, int pos, int val)
{
int position = 0;
PNode P = head; // 定義節(jié)點(diǎn)p指向頭節(jié)點(diǎn)
// 尋找pos節(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)
while (P != NULL&&position<pos - 1)
{
P = P->Next;
++position;
}
PNode tmp = (PNode)malloc(sizeof(Node)); // 分配一個(gè)臨時(shí)節(jié)點(diǎn)用來存儲(chǔ)要插入的數(shù)據(jù)
if (tmp == NULL)
{
printf("內(nèi)存分配失敗纲仍！");
exit(-1);
}
// 插入節(jié)點(diǎn)
tmp->Element = val;
tmp->Next = P->Next;
P->Next = tmp;
}
//定義刪除整個(gè)鏈表函數(shù)
void deleteList(PNode head)
{
PNode P, tmp;
P = head->Next; //定義指針P指向鏈表要?jiǎng)h除的鏈表List的第一個(gè)點(diǎn)節(jié)點(diǎn)
head->Next = NULL;
while (P != NULL)
{
tmp = P->Next; //臨時(shí)Tmp指向要?jiǎng)h除的節(jié)點(diǎn)的下個(gè)節(jié)點(diǎn)
free(P); //釋放指針P指向的節(jié)點(diǎn)
P = tmp; //重新賦值
}
printf("刪除鏈表成功呀袱！\n");
}
// 定義刪除鏈表元素函數(shù)
// 刪除鏈表中的第pos節(jié)點(diǎn)
void deleteNode(PNode head, int pos)
{
int position = 0;
PNode P = head; // 定義一個(gè)指針p指向鏈表頭節(jié)點(diǎn)
// 尋找pos節(jié)點(diǎn)位置的前驅(qū)節(jié)點(diǎn)
while (P != NULL&&position < pos - 1)
{
P = P->Next;
++position;
}
// 刪除節(jié)點(diǎn)
PNode tmp = P->Next; // 定義臨時(shí)指針Tmp指向要?jiǎng)h除的節(jié)點(diǎn)
P->Next = tmp->Next; // 使要?jiǎng)h除節(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)指向其后驅(qū)節(jié)點(diǎn)
free(tmp); // 釋放刪除節(jié)點(diǎn)的內(nèi)存空間，防止內(nèi)存泄漏
tmp = NULL; // 使q指向空指針郑叠，防止產(chǎn)生野指針
}
運(yùn)行結(jié)果：
請輸入節(jié)點(diǎn)個(gè)數(shù)：5
請輸入第 1 個(gè)節(jié)點(diǎn)的數(shù)據(jù)：10
請輸入第 2 個(gè)節(jié)點(diǎn)的數(shù)據(jù)：20
請輸入第 3 個(gè)節(jié)點(diǎn)的數(shù)據(jù)：30
請輸入第 4 個(gè)節(jié)點(diǎn)的數(shù)據(jù)：40
請輸入第 5 個(gè)節(jié)點(diǎn)的數(shù)據(jù)：50
創(chuàng)建鏈表成功
遍歷鏈表的值為：10 20 30 40 50
請輸入要查詢的數(shù)：30
找到的節(jié)點(diǎn)為：3
遍歷鏈表的值為：10 20 100 30 40 50
遍歷鏈表的值為：10 20 30 40 50
刪除鏈表成功夜赵！
遍歷鏈表的值為：鏈表為空
了解少兒編程、信息學(xué)競賽請加微信307591841或QQ群581357582乡革，關(guān)注公眾號(hào)請掃描二維碼qrcode_for_kidscode_258.jpg
