五,、功能的實(shí)現(xiàn)

1）打印單鏈表

//打印單鏈表voidSLTPrint(SLTNode*phead);

voidSLTPrint(SLTNode*phead){SLTNode*cur=phead;//(1)while(cur!=NULL)//(2){printf('%d->',cur->data);cur=cur->next;//(3)}printf('NULL\n');}

(1)這里也可以直接用phead進(jìn)行循環(huán)，但是像這樣創(chuàng)建一個(gè)“當(dāng)前節(jié)點(diǎn)”（cur源自單詞current）會(huì)比較“美觀”,。（But如果這個(gè)函數(shù)內(nèi)部后面還需要用頭節(jié)點(diǎn)的話就不能直接用phead,，否則會(huì)找不到頭）

(2)控制結(jié)束的條件

(3)遍歷

2）創(chuàng)建新節(jié)點(diǎn)

鏈表的結(jié)點(diǎn)：按需分配,，隨用隨創(chuàng)

鏈表的頭插,、尾插（只要是插入）都需要?jiǎng)?chuàng)建一個(gè)新節(jié)點(diǎn)，然后插到對(duì)應(yīng)位置,。所以我們可以直接把“創(chuàng)建新節(jié)點(diǎn)”封裝成一個(gè)函數(shù),，以便后面直接調(diào)用：?

SLTNode*BuySLTNode(SLTDataTypex){SLTNode*newnode=(SLTNode*)malloc(sizeof(SLTNode));//(1)if(newnode==NULL)//(2){perror('mallocnewnodefail:');return;}//(3)給新節(jié)點(diǎn)賦值newnode->x;newnode->next=NULL;returnnewnode;//別忘了返回newnode}

(1)動(dòng)態(tài)開辟一個(gè)新節(jié)點(diǎn)，.h頭文件里要包含

(2)判斷開辟是否成功,，如果不成功則輸出錯(cuò)誤并返回

(3)給新節(jié)點(diǎn)的數(shù)據(jù)域賦值,，指針域賦為空：NULL，這樣做的好處是：不需要最后對(duì)鏈表尾結(jié)點(diǎn)的指針域置空,。

3）尾插

在鏈表尾部插入一個(gè)節(jié)點(diǎn)

先看這段代碼：

voidSLTPushBack(SLTNode**pphead,SLTDataTypex);{SLTNode*newnode=BuySLTNode(x);SLTNode*tail=*pphead;while(tail->next!=NULL){tail=tail->next;}tail->next=newnode;}

上面這段代碼的前提是,，我們已經(jīng)假定這個(gè)鏈表有>=1個(gè)節(jié)點(diǎn)，但是如果*pphead為空呢,？

如果為空,，則只執(zhí)行：

SLTNode*newnode=BuySLTNode(x);SLTNode*tail=*pphead;

初始化：SLTNode*phead=NULL;

傳參：SLTPushBack(&phead,x);）

當(dāng)phead為NULL時(shí)，也就不存在tail->next了

所以切記要先判斷*pphead是否為空：

voidSLTPushBack(SLTNode**pphead,SLTDataTypex){SLTNode*newnode=BuySLTNode(x);if(*pphead==NULL){*pphead=newnode;}else{SLTNode*tail=*pphead;//找原鏈表的尾結(jié)點(diǎn)while(tail->next!=NULL){tail=tail->next;}tail->next=newnode;}}

點(diǎn)擊加載圖片

4）尾刪

尾刪比較麻煩,，因?yàn)橐袛噫湵硎欠駷榭找约胺智闆r討論結(jié)點(diǎn)個(gè)數(shù),。

先看這段代碼：

voidSLTPopBack(SLTNode**pphead){assert(pphead&&*pphead);//(1)SLTNode*tail,*tailpre;//(2)tail=*pphead->next;tailpre=*pphead;while(tail->next){tail=tail->next;tailpre=tailpre->next;}free(tail);//(3)tailpre->next=NULL;//(4)}

(1)pphead（二級(jí)指針）和*pphead絕對(duì)不可以為空，最好斷言一下

(2)定義tail和tail前一個(gè)結(jié)點(diǎn)tailpre,，目的是釋放tail后,，直接得到新的尾結(jié)點(diǎn)，方便置空

(3)沒必要再把tail置空：tail=NULL;因?yàn)閠ail是局部變量,，函數(shù)結(jié)束就自動(dòng)銷毀了

(4)釋放后,，新的尾結(jié)點(diǎn)的next置空

看似沒什么毛病·······

但是，上面沒有考慮只有一個(gè)結(jié)點(diǎn)的情況??！

?如果只有一個(gè)結(jié)點(diǎn)，tail=*pphead->next;后,，tail為NULL,，下面的執(zhí)行就出大問題了

解決辦法是判斷一下：

voidSLTPopBack(SLTNode**pphead){assert(pphead&&*pphead);if((*pphead)->next==NULL)//只有一個(gè)結(jié)點(diǎn){free(*pphead);*pphead=NULL;}else//>=2個(gè)結(jié)點(diǎn){SLTNode*tail,*tailpre;tail=*pphead->next;tailpre=*pphead;while(tail->next){tail=tail->next;tailpre=tailpre->next;}free(tail);tailpre->next=NULL;}}

5）頭插

按照尾插的路子,，可能會(huì)這樣寫：

voidSLTPushFront(SLTNode**pphead,SLTDataTypex){assert(pphead);SLTNode*newnode=BuySLTNode(x);if(*pphead==NULL){*pphead=newnode;}else{newnode->next=*pphead;*pphead=newnode;}}

當(dāng)然沒有錯(cuò)，但是仔細(xì)想一想,，其實(shí)沒有必要判斷*pphead是否為空,，因?yàn)榧词?pphead為空,，執(zhí)行else部分依然沒毛?。?/p>

化簡(jiǎn)為：

voidSLTPushFront(SLTNode**pphead,SLTDataTypex){assert(pphead);SLTNode*newnode=BuySLTNode(x);newnode->next=*pphead;*pphead=newnode;}

6）頭刪

頭刪相比較尾刪很簡(jiǎn)單,，因?yàn)椴恍枰裎矂h一樣找tail前一個(gè)結(jié)點(diǎn),。

頭刪可以直接刪：

voidSLPopFront(SLTNode**pphead){assert(pphead&&*pphead);SLTNode*next=(*pphead)->next;//臨時(shí)存一下第二個(gè)元素的結(jié)點(diǎn)free(*pphead);*pphead=next;}

7）查找

查找鏈表中的某個(gè)元素，只需遍歷一遍鏈表,。返回data==要查找的元素第一次出現(xiàn)的節(jié)點(diǎn)的地址,；如果鏈表中沒有要查找的元素，返回NULL,。

<注意,，空鏈表也可以查找，返回NULL即可>↓

SLTNode*SLFind(SLTNode*phead,SLDataTypex){SLTNode*cur=phead;while(cur){if(cur->data==x)returncur;cur=cur->next;}returnNULL;}

8）刪除

分兩種情況：鏈表只有一個(gè)節(jié)點(diǎn),、鏈表有多個(gè)節(jié)點(diǎn),。

1、只有一個(gè)節(jié)點(diǎn)：如果*pphead==pos,，相當(dāng)于頭刪,，直接調(diào)用前面的函數(shù)即可。

2,、有多個(gè)節(jié)點(diǎn)：遍歷鏈表,，直到找到地址為pos的結(jié)點(diǎn)，按照尾刪的思路,，刪除即可,。

voidSLErase(SLTNode**pphead,SLTNode*pos){assert(pphead&&*pphead&&pos);//都不能為空if(*pphead==pos){SLPopFront(pphead);}else{SLTNode*cur=*pphead;while(cur->next!=pos){cur=cur->next;}SLTNode*next=cur->next->next;cur->next=next;free(pos);//一定要free}}

9）插入結(jié)點(diǎn)

在pos前插入：

voidSLInsert(SLTNode**pphead,SLTNode*pos,SLDataTypex){assert(pphead&&pos);if(pos==*pphead){SLPushFront(pphead,x);}else{SLTNode*cur=*pphead;while(cur->next!=pos){cur=cur->next;}SLTNode*insnode=BuyNode(x);cur->next=insnode;insnode->next=pos;}}

10）銷毀

對(duì)于銷毀鏈表，如果只free掉*pphead行么,？

當(dāng)然不行?。?/p>

因?yàn)閱捂湵碛梢粋€(gè)一個(gè)的結(jié)點(diǎn)連接起來的,。如果只free(*pphead),，頭結(jié)點(diǎn)是釋放了，但是后面的節(jié)點(diǎn)沒被釋放,，還占用著空間但是已經(jīng)找不到他們的地址了,。

所以應(yīng)該逐個(gè)釋放?

voidSLDestroy(ListNode**pphead){ListNode*cur=*pphead;while(cur){ListNode*next=cur->next;free(cur);cur=next;}*pphead=NULL;//最后別忘了置空}

銷毀完后最好把*pphead置空，防止銷毀鏈表后對(duì)鏈表誤操作而導(dǎo)致的野指針問題,。