單鏈表的定義

線性表的鏈式存儲又稱為單鏈表，它是指通過一組任意的存儲單元來存儲線性表中的數據元素。 為了建立起數據元素之間的線性關系，對每個鏈表結點，除了存放元素自身的信息之外，還需要存放一個指向其后繼的指針。

每個結點包括數據域和指針域。節點是一個結構體，看一下結構體的定義：

typedef struct LNode{ElemType data;struct LNode *next; }LNode,*LinkList;

注意這是節點而不是整個單鏈表。
節點的第一個部分是數據域data。
第二個部分是指針next，指向的類型是節點的類型，表示指向下一個節點。
節點的名字取為LNode。
結構體的指針類型記作LinkList。

那么如何表示一個單鏈表呢？

單鏈表的兩種建表方法

頭結點和頭指針的區別？

不管帶不帶頭結點，頭指針始終指向鏈表的第一個結點，而頭結點是帶頭結點鏈表中的第一個結點，結點內通常不存儲信息。

為什么要設置頭結點？

處理操作起來方便 例如：對在第一元素結點前插入結點和刪除第一結點起操作與其它結點的操作就統一了

無論鏈表是否為空，其頭指針是指向頭結點的非空指針，因此空表和非空表的處理也就統一了。

如何建立單鏈表？按照插入位置分為兩種方式：

1.頭插法建立單鏈表：

建立新的節點分配內存空間，將新節點插入到當前鏈表的表頭

LinkList CreatList1(LinkList &L) {LNode *s; //輔助指針int x; //儲存插入節點的數據的值L=(LinkList)malloc(sizeof(LNode));//創建頭節點L->next=NULL; //初始為空鏈表scanf("%d",&x); //輸入節點的值while(x!=9999){ //輸入9999表示結束（要根據實際題目來確定終止條件）s=(LNode*)malloc(sizeof(LNode)); //創建新節點s->data=x; //對新節點的數據域進行賦值s->next=L->next; //**新節點的后繼指向第一個節點**L->next=s; //**頭節點的后繼指向新節點**scanf("%d",&x); //讀入下一個節點值}return L; //返回建好的鏈表的頭指針L }

頭插法建立單鏈表，讀入數據的順序與生成的鏈表中元素的順序是相反的。

2.尾插法建立單鏈表

建立新的結點分配內存空間，將新結點插入到當前鏈表的表尾。
需要增加一個指向表尾元素的尾指針。

LinkList CreatList2(LinkList &L) {int x;L=(LinkList)malloc(sizeof(LNode)); //帶頭節點的鏈表LNode *s,*r=L; //r為表尾指針 指向表尾scanf("%d",&x); //輸入結點的值while(x!=9999){ //輸入9999表示結束s=(LNode*)malloc(sizeof(LNode));s->data=x;r->next=s;r=s; //r指向新的表尾結點scanf("%d",&x);}r->next=NULL; //尾結點指針置空return L; }

尾插法建立單鏈表，讀入數據的順序與生成的鏈表中元素L 的順序是相同的。

單鏈表的基本操作

按序號查找

在單鏈表中從第一個結點出發，順指針next域逐個往下搜索，直到找到第i個結點為止,否則返回最后一個結點指針域NULL。

因為是查找結點，所以函數的返回類型是指向結點的指針類型。
參數有兩個，是鏈表L和結點序號i（只需對鏈表進行讀取，不需修改，所以不必設置引用類型）

LNode *GetElem(LinkList L,int i) {int j=1; //計數，初始為1LNode *p=L->next; //第一個結點指針賦給pif(i==0) //若i等于0，則返回頭結點return L; if(i<1) //若i無效，則返回NULLreturn NULL;while(p&&j<i) //從第1個結點開始找，查找第i個結點 （此處一定要判斷p不為空）{p=p->next;j++;}return p; //返回第i個結點的指針，如果i大于表長，直接返回p即可 }

按值查找

從單鏈表第一個結點開始，由前往后依次比較表中各結點數據域的值，若某結點數據域的值等于給定值e，則返回該結點的指針；若整個單鏈表中沒有這樣的結點，則返回NULL。

LNode *LocateElem(LinkList L,ElemType e) {LNode *p=L->next;while(p!=NULL&&p->data!=e) //從第1個結點開始查找data域為e的結點（此處一定要判斷p不為空）p=p->next;return p; //找到后返回該結點指針，否則返回NULL }

插入

插入操作是將值為x的新結點插入到單鏈表的第i個位置上。先檢查插入位置的合法性，然后找到待插入位置的前驅結點，即第i?1個結點，再在其后插入新結點。
算法思路：

取指向插入位置的前驅結點的指針
① p=GetElem(L,i-1);

令新結點s的指針域指向p的后繼結點
② s->next=p->next;

令結點p的指針域指向新插入的結點s
③ p->next=s;

bool ListFrontInsert(LinkList L,int i,ElemType e) {LinkList p=GetElem(L,i-1);if(NULL==p){return false;}LinkList s=(LNode*)malloc(sizeof(LNode));//為新插入的結點申請空間s->data=e;s->next=p->next;p->next=s;return true; }

刪除

刪除操作是將單鏈表的第i個結點刪除。先檢查刪除位置的合法性，然后查找表中第i?1個結點，即被刪結點的前驅結點，再將其刪除。
算法思路：

取指向刪除位置的前驅結點的指針 p=GetElem(L,i-1);

取指向刪除位置的指針 q=p->next;

p指向結點的后繼指向被刪除結點的后繼 p->next=q->next

釋放刪除結點 free(q);

bool ListDelete(LinkList L,int i) {LinkList p=GetElem(L,i-1);if(NULL==p){return false;}LinkList q;q=p->next;p->next=q->next;free(q);return true; }

參考資料

https://www.bilibili.com/video/av36895433/?p=11

總結

以上是生活随笔為你收集整理的【数据结构】线性表的链式存储-单链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。