1.什么是鏈表

鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指 針鏈接次序?qū)崿F(xiàn)的。

2.為什么要使用鏈表

在未學(xué)習(xí)鏈表時，我們常用的存儲數(shù)據(jù)的方式無非就是數(shù)組。使用數(shù)組存儲數(shù)據(jù)的好處就是查詢快，但是它的弊端也很明顯：

1.使用前需聲明數(shù)組的長度，一旦聲明長度就不能更改

2.插入和刪除操作需要移動大量的數(shù)組元素，效率慢

3. 只能存儲一種類型的數(shù)據(jù)

順序表就是在計算機中內(nèi)存以數(shù)組的形式保存的線性表，因此這些弊端同理

而鏈表則可以實現(xiàn)以上這些數(shù)組所不具備的功能，此時引入了結(jié)構(gòu)體來實現(xiàn)創(chuàng)建鏈表的操作

?n個節(jié)點離散分配

每一個節(jié)點之間通過指針相連

每一個節(jié)點有一個前驅(qū)節(jié)點和一個后繼節(jié)點

首節(jié)點沒有前驅(qū)節(jié)點，尾節(jié)點沒有后繼節(jié)點

創(chuàng)建單鏈表?

//帶頭結(jié)點單鏈表，邏輯相鄰，物理不一定相鄰，為了找到下一個結(jié)點，就必須增加下一個結(jié)點的地址 //尾結(jié)點；最后一個結(jié)點，在單鏈表中，尾結(jié)點的next為NULL，NULL是單鏈表的結(jié)尾標志 //頭結(jié)點；其數(shù)據(jù)域不使用或者存放鏈表長度，其作用相當(dāng)于標桿，簡化整個操作typedef int ElemType; typedef struct Node {ElemType data;//數(shù)據(jù)struct Node* next;//后繼指針 }Node,*List; //typedef Node* List;//List==Node * //List本質(zhì)是Node*,但含義不同,List表示一條鏈表,Node*表示一個節(jié)點的地址

首節(jié)點：存放第一個有效數(shù)據(jù)的節(jié)點

頭節(jié)點：在單鏈表的第一個結(jié)點之前附設(shè)一個結(jié)點，它沒有直接前驅(qū)，稱之為頭結(jié)點，頭結(jié)點的數(shù)據(jù)域可以不存儲任何信息，指針域指向第一個節(jié)點（首節(jié)點）的地址。頭結(jié)點的作用是使所有鏈表（包括空表）的頭指針非空

頭指針：指向頭節(jié)點的指針

尾節(jié)點：存放最后一個有效數(shù)據(jù)的節(jié)點

尾指針：指向尾節(jié)點的指針

?

?

?基本函數(shù)：

//初始化plist void InitList(List plist);//頭插 往plist中頭部插入數(shù)字val bool Insert_head(List plist, ElemType val);//尾插 往plist中尾部插入數(shù)字val bool Insert_tail(List plist, ElemType val);//刪除plist中第一個val bool DeleteVal(List plist, ElemType val);//在plist中查找val值找到返回該結(jié)點地址，失敗返回NULL Node* Search(List plist, ElemType val);//判斷plist是否為空鏈表（沒有數(shù)據(jù)結(jié)點） bool IsEmpty(List plist);//獲取plist長度，數(shù)據(jù)結(jié)點的個數(shù) int GetLength(List plist);//獲取plist鏈表的pos位置(下標)的值 bool GetElem(List plist, int pos, int* rtval);//輸出參數(shù)rtval//獲取val前驅(qū) Node* Prior(List plist, ElemType val);//獲取val后繼 Node* Next(List plist, ElemType val);//打印 void Show(List plist);//清空數(shù)據(jù) void Clear(List plist); //銷毀 void Destroy(List plist);

?3.基本操作

初始化單鏈表plist(帶頭結(jié)點):

//初始化plist void InitList(List plist) {assert(plist != NULL);//頭結(jié)點的數(shù)據(jù)不使用plist->data,可以不處理plist->next = NULL; }//另一種寫法(會出現(xiàn)二級指針不推薦) void InitList(List* pplist) {assert(pplist != NULL);*pplist = (Node*)malloc(sizeof(Node));//動態(tài)創(chuàng)建頭結(jié)點assert(*pplist != NULL);if (*pplist == NULL)return;(*pplist)->next = NULL; }

?插入操作:

1.頭插

//頭插 往plist中頭部插入數(shù)字val //時間復(fù)雜度O(1) bool Insert_head(List plist, ElemType val) {//1.動態(tài)創(chuàng)建一個新結(jié)點Node* p = (Node*)malloc(sizeof(Node));assert(p != NULL);if (p == NULL)return false;//2.把數(shù)據(jù)val存放到新結(jié)點p->data = val;//3.把新結(jié)點插入在頭結(jié)點的后面p->next = plist->next;plist->next = p;return true; }

2.尾插

//尾插 往plist中尾部插入數(shù)字val bool Insert_tail(List plist, ElemType val)//時間復(fù)雜度O(n) {//1.動態(tài)創(chuàng)建新結(jié)點Node* p = (Node*)malloc(sizeof(Node));assert(p != NULL);if (p == NULL)return false;//2.把值存放到新結(jié)點p->data = val;//3.找到鏈表尾巴Node* q;for (q = plist; q->next != NULL; q = q->next);//4.把新結(jié)點插在尾結(jié)點后面p->next=q->next;//p->next=NULLq->next = p;return true; }

?打印函數(shù):

//打印 void Show(List plist) {for (Node* p = plist->next; p != NULL; p = p->next) //遍歷所有的數(shù)據(jù)結(jié)點{printf("%d ", p->data);}printf("\n"); }

上面三個函數(shù)測試用例：

int main() {Node head;//創(chuàng)建頭結(jié)點InitList(&head);//for (int i = 0; i < 10; i++) //....4 3 2 1 0頭插//{// Insert_head(&head, i); //}for (int i = 0; i < 10; i++) //0 1 2 3 4....尾插{Insert_tail(&head, i);}Show(&head); }

?查找函數(shù)(在plist中查找val值,找到返回該結(jié)點地址，失敗返回NULL):

//在plist中查找val值,找到返回該結(jié)點地址，失敗返回NULL Node* Search(List plist, ElemType val) {for (Node* p = plist->next; p != NULL; p = p->next){if (p->data ==val)//找到了return p;}return NULL;//沒找到 }

獲取任意值val的前驅(qū):

//獲取val前驅(qū) Node* Prior(List plist, ElemType val) {for (Node* p = plist; p ->next!= NULL; p = p->next){if (p->next->data == val)return p; //找到了}return NULL;//失敗了 }

獲取任意值val的后繼:

//獲取val后繼 Node* Next(List plist, ElemType val) {for (Node* p = plist->next; p != NULL; p = p->next){if (p->data == val)return p->next;}return NULL; }

刪除操作(刪除plist中第一個val值):

//刪除plist中第一個val bool DeleteVal(List plist, ElemType val) {//1.找到需要刪除的結(jié)點前驅(qū)Node* p= Prior(plist,val);//指向前驅(qū)結(jié)點 調(diào)用找前驅(qū)函數(shù)if (p == NULL)//沒有valreturn false;Node* q = p->next;//標記需要刪除的結(jié)點p->next = q->next;//將q從鏈表中剔除free(q); //釋放結(jié)點return true; }

判空操作:

//判斷plist是否為空鏈表（沒有數(shù)據(jù)結(jié)點） bool IsEmpty(List plist) {return plist->next == NULL;//等同于/*if (plist->next == NULL)return true;elsereturn false;*/}

?獲取長度(獲取plist長度，數(shù)據(jù)結(jié)點的個數(shù)):

//獲取plist長度，數(shù)據(jù)結(jié)點的個數(shù) int GetLength(List plist) {int count = 0;for (Node* p = plist->next; p != NULL; p = p->next){count++;}return count; }

獲取鏈表下標位置的值(獲取plist鏈表的pos位置(下標)的值)：

//獲取plist鏈表的pos位置(下標)的值 bool GetElem(List plist, int pos, int* rtval)//輸出參數(shù)rtval {if (pos < 0 || pos >= GetLength(plist))//下標不存在return false;Node* p=plist->next;for (int i=0;i < pos; p = p->next, i++){;}*rtval= p->data;return true; }

銷毀操作:

//銷毀 void Destroy(List plist) {/*第一種寫法if (plist == NULL || plist->next == NULL)return;Node* p = plist->next;Node* q;plist->next = NULL;while (p != NULL){q = p->next;free(p);p = q;}*///第二種寫法Node* p;//指向第一個數(shù)據(jù)結(jié)點while (plist->next != NULL)//還有數(shù)據(jù)結(jié)點{p = plist->next;plist->next = p->next;//剔除pfree(p);}}

?清空數(shù)據(jù):

//清空數(shù)據(jù) 把所有的數(shù)據(jù)刪除 void Clear(List plist) {Destroy(plist); }

完整代碼:

#pragma oncetypedef int ElemType; typedef struct Node {ElemType data;//數(shù)據(jù)struct Node* next;//后繼指針 }Node,*List; //typedef Node* List;//List==Node * //List本質(zhì)是Node*,但含義不同,List表示一條鏈表,Node*表示一個節(jié)點的地址//初始化plist void InitList(List plist); //頭插 往plist中頭部插入數(shù)字val bool Insert_head(List plist, ElemType val); //尾插 往plist中尾部插入數(shù)字val bool Insert_tail(List plist, ElemType val); //刪除plist中第一個val bool DeleteVal(List plist, ElemType val);//在plist中查找val值找到返回該結(jié)點地址，失敗返回NULL Node* Search(List plist, ElemType val); //判斷plist是否為空鏈表（沒有數(shù)據(jù)結(jié)點） bool IsEmpty(List plist); //獲取plist長度，數(shù)據(jù)結(jié)點的個數(shù) int GetLength(List plist); //獲取plist鏈表的pos位置(下標)的值 bool GetElem(List plist, int pos, int* rtval);//輸出參數(shù)rtval//獲取val前驅(qū) Node* Prior(List plist, ElemType val); //獲取val后繼 Node* Next(List plist, ElemType val);//打印 void Show(List plist); //清空數(shù)據(jù) void Clear(List plist); //銷毀 void Destroy(List plist); #include<stdio.h> #include<stdlib.h> #include<assert.h> #include"list.h" //初始化plist void InitList(List plist) {assert(plist != NULL);//頭結(jié)點的數(shù)據(jù)不使用plist->data,可以不處理plist->next = NULL; } //書上的寫法 void InitList(List* pplist) {assert(pplist != NULL);*pplist = (Node*)malloc(sizeof(Node));//動態(tài)創(chuàng)建頭結(jié)點assert(*pplist != NULL);if (*pplist == NULL)return;(*pplist)->next = NULL; } //頭插 往plist中頭部插入數(shù)字val// O(1) bool Insert_head(List plist, ElemType val) {//1.動態(tài)創(chuàng)建一個新結(jié)點Node* p = (Node*)malloc(sizeof(Node));assert(p != NULL);if (p == NULL)return false;//2.把數(shù)據(jù)val存放到新結(jié)點p->data = val;//3.把新結(jié)點插入在頭結(jié)點的后面p->next = plist->next;plist->next = p;return true; } //尾插 往plist中尾部插入數(shù)字val bool Insert_tail(List plist, ElemType val)//O(n) {//1.動態(tài)創(chuàng)建新結(jié)點Node* p = (Node*)malloc(sizeof(Node));assert(p != NULL);if (p == NULL)return false;//2.把值存放到新結(jié)點p->data = val;//3.找到鏈表尾巴Node* q;for (q = plist; q->next != NULL; q = q->next);//4.把新結(jié)點插在尾結(jié)點后面p->next=q->next;//p->next=NULLq->next = p;return true; }//在plist中查找val值,找到返回該結(jié)點地址，失敗返回NULL Node* Search(List plist, ElemType val) {for (Node* p = plist->next; p != NULL; p = p->next){if (p->data ==val)//找到了return p;}return NULL;//沒找到 } //刪除plist中第一個val bool DeleteVal(List plist, ElemType val) {//1.找到需要刪除的結(jié)點前驅(qū)Node* p= Prior(plist,val);//指向前驅(qū)結(jié)點if (p == NULL)//沒有valreturn false;Node* q = p->next;//標記需要刪除的結(jié)點p->next = q->next;//將q從鏈表中剔除free(q); //釋放結(jié)點return true; }//判斷plist是否為空鏈表（沒有數(shù)據(jù)結(jié)點） bool IsEmpty(List plist) {return plist->next == NULL;//等同于/*if (plist->next == NULL)return true;elsereturn false;*/}//獲取plist長度，數(shù)據(jù)結(jié)點的個數(shù) int GetLength(List plist) {int count = 0;for (Node* p = plist->next; p != NULL; p = p->next){count++;}return count; }//獲取plist鏈表的pos位置(下標)的值 bool GetElem(List plist, int pos, int* rtval)//輸出參數(shù)rtval {if (pos < 0 || pos >= GetLength(plist))//下標不存在return false;Node* p=plist->next;for (int i=0;i < pos; p = p->next, i++){;}*rtval= p->data;return true;}//獲取val前驅(qū) Node* Prior(List plist, ElemType val) {for (Node* p = plist->next; p ->next!= NULL; p = p->next){if (p->next->data == val)return p; //找到了}return NULL;//失敗了 } //獲取val后繼 Node* Next(List plist, ElemType val) {for (Node* p = plist->next; p != NULL; p = p->next){if (p->data == val)return p->next;}return NULL; }//打印 void Show(List plist) {for (Node* p = plist->next; p != NULL; p = p->next) //遍歷所有的數(shù)據(jù)結(jié)點{printf("%d ", p->data);}printf("\n"); }//清空數(shù)據(jù) 把所有的數(shù)據(jù)刪除 void Clear(List plist) {Destroy(plist); } //銷毀 void Destroy(List plist) {/*if (plist == NULL || plist->next == NULL)return;Node* p = plist->next;Node* q;plist->next = NULL;while (p != NULL){q = p->next;free(p);p = q;}*/Node* p;//指向第一個數(shù)據(jù)結(jié)點while (plist->next != NULL)//還有數(shù)據(jù)結(jié)點{p = plist->next;plist->next = p->next;//剔除pfree(p);}}//測試用例 int main() {Node head;//創(chuàng)建頭結(jié)點InitList(&head);//for (int i = 0; i < 10; i++) //....4 3 2 1 0頭插//{// Insert_head(&head, i); //}for (int i = 0; i < 10; i++) //0 1 2 3 4....尾插{Insert_tail(&head, i);}Show(&head);DeleteVal(&head, 3);Show(&head);printf("長度為:%d\n", GetLength(&head));int rtval;for (int i = 0; i < 10; i++){if (GetElem(&head, i, &rtval))printf("%d %d\n", i, rtval);}for (int i = -1; i < 10; i++){Node* p = Next(&head, i);//沒有后繼if (p == NULL)printf("%d沒有后繼\n", i);elseprintf("%d的后繼數(shù)據(jù)為%d\n", i, p->data);}if (IsEmpty(&head))printf("空");elseprintf("不空");return 0; }

看到這里了不妨點個贊!創(chuàng)作不易

總結(jié)

以上是生活随笔為你收集整理的数据结构-单链表基本操作带图完整详解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。