C++超詳細講解單鏈表的實現(xiàn)

第C++超詳細講解單鏈表的實現(xiàn)目錄單鏈表的實現(xiàn)(從入門到熟練)概念和結(jié)構鏈表的實現(xiàn)增刪查改接口節(jié)點結(jié)構體創(chuàng)建節(jié)點開辟數(shù)據(jù)打印鏈表尾插數(shù)據(jù)頭刪鏈表數(shù)據(jù)查找鏈表pos位置前插數(shù)據(jù)鏈表pos位置后插數(shù)據(jù)鏈表pos位置數(shù)據(jù)刪除鏈表節(jié)點釋放鏈表與順序表區(qū)別鏈表的優(yōu)缺點順序表的優(yōu)缺點

單鏈表的實現(xiàn)(從入門到熟練)

概念和結(jié)構

概念：鏈表是一種物理存儲結(jié)構上非連續(xù)、非順序的存儲結(jié)構

數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的

圖示：

注意：

鏈表結(jié)構在邏輯上為連續(xù)的，但是物理上（內(nèi)存中）不一定連續(xù)

鏈表節(jié)點都是在堆上申請出來的，申請空間按一定策略分配

結(jié)構種類

鏈表具有多種結(jié)構：單向\雙向，帶頭\不帶頭，循環(huán)\非循環(huán)

實際上最常用的是：無頭單向非循環(huán)鏈表，帶頭雙向循環(huán)鏈表

鏈表的實現(xiàn)

注意：這里實現(xiàn)的是無頭單向非循環(huán)鏈表

增刪查改接口

//動態(tài)申請一個節(jié)點

SListNode*BuySListNode(SLTDateTypex);

//單鏈表打印

voidSListPrint(SListNode*plist);

//單鏈表尾插

voidSListPushBack(SListNode**pplist,SLTDateTypex);

//單鏈表的頭插

voidSListPushFront(SListNode**pplist,SLTDateTypex);

//單鏈表的尾刪

voidSListPopBack(SListNode**pplist);

//單鏈表頭刪

voidSListPopFront(SListNode**pplist);

//單鏈表查找

SListNode*SListFind(SListNode*plist,SLTDateTypex);

//單鏈表在pos位置之后插入x

voidSListInsertAfter(SListNode*pos,SLTDateTypex);

//單鏈表刪除pos位置之后的值

voidSListEraseAfter(SListNode*pos);

節(jié)點結(jié)構體創(chuàng)建

typedefintSLTDateType;

typedefstructSListNode

SLTDateTypedata;

structSListNode*next;

}SListNode;

節(jié)點開辟

對于鏈表來說，每需要空間就需要進行開辟，這里我們將之封裝成一個函數(shù)，便于后續(xù)調(diào)用直接使用（開辟的同時進行賦值）

參考代碼：

//鏈表節(jié)點開辟

SLTNode*BuySListNode(SLTDateTypex)

//動態(tài)分配一個節(jié)點

SLTNode*newnode=(SLTNode*)malloc(sizeof(SLTNode));

if(newnode==NULL)

//分配失敗則打印錯誤信息并結(jié)束進程

perror("newnodefail:");

exit(-1);

//成功則進行賦值

newnode-data=x;

newnode-next=NULL;

//返回節(jié)點地址，以便后續(xù)操作

returnnewnode;

數(shù)據(jù)打印

注意：

1.對于不帶頭的鏈表來說，打印數(shù)據(jù)不需要修改鏈表首節(jié)點地址（故只要傳鏈表指針）

2.用循環(huán)遍歷鏈表，每打印數(shù)據(jù)，需要指向下一個節(jié)點

3.依靠尾節(jié)點的址域為NULL來結(jié)束循環(huán)

代碼：

//鏈表數(shù)據(jù)打印

voidSListPrint(SLTNode*phead)//一級指針接收一級指針（打印不需改變指針本身內(nèi)容）

//創(chuàng)建一個尋址指針

SLTNode*cur=phead;

while(cur!=NULL)//后續(xù)還有節(jié)點

//打印數(shù)據(jù)并指向下一個節(jié)點

printf("%d-",cur-data);

cur=cur-next;

//最后打印空指針

printf("NULL\n");

return;

鏈表尾插數(shù)據(jù)

要尾插數(shù)據(jù)則需要遍歷找到鏈表的尾節(jié)點

對于不帶頭鏈表，尾插數(shù)據(jù)也可能是插在鏈表首元素的地址（當鏈表為空），需要修改鏈表指針的內(nèi)容（故需要傳入鏈表指針的地址）

插入數(shù)據(jù)要開辟節(jié)點

代碼：

//鏈表尾插數(shù)據(jù)

voidSListPushBack(SLTNode**pphead,SLTDateTypex)//二級指針接收一級指針（尾插存在需改變鏈表指針本身內(nèi)容）

//避免傳入錯誤(直接報錯便于找到錯誤位置)

assert(pphead);

//接收新節(jié)點的地址

SLTNode*newnode=BuySListNode(x);

//頭節(jié)點為空

if(*pphead==NULL)

*pphead=newnode;

else

//找尾節(jié)點

SLTNode*tail=*pphead;//創(chuàng)建尋址節(jié)點

//兩個及以上節(jié)點的情況

while(tail-next!=NULL)

//指向下一個節(jié)點

tail=tail-next;

//找到了

tail-next=newnode;

return;

注意代碼中的assert的作用：

正確傳入鏈表指針的地址是不會為空的

但是對于非正常傳入鏈表指針（不是鏈表指針的地址）且此時鏈表指針為空則會發(fā)生報錯（assert報錯會告訴錯誤位置），告訴程序員應該傳入鏈表指針的地址

頭刪

注意：

刪除前需要保存當前節(jié)點的址域（即保存下個節(jié)點的空間地址，以防丟失）

前刪數(shù)據(jù)即刪除當前鏈表首節(jié)點，即需修改鏈表指針的內(nèi)容（故需傳入鏈表指針的地址）

刪除后修改鏈表指針內(nèi)容，指向新的首節(jié)點

如果鏈表為空時無法刪除（保存下個節(jié)點地址會造成非法訪問）

代碼：

//鏈表前刪數(shù)據(jù)

voidSListPopFront(SLTNode**pphead)

//避免傳入錯誤(直接報錯便于找到錯誤位置)

assert(pphead);

//鏈表為空的情況

if(*pphead==NULL)

return;

//創(chuàng)建指針保存第二個節(jié)點地址

SLTNode*next=(*pphead)-next;

//釋放當前頭結(jié)點空間

free(*pphead);

//更新頭結(jié)點數(shù)據(jù)

*pphead=next;

return;

鏈表數(shù)據(jù)查找

注意：

查找時用循環(huán)遍歷鏈表

對于查找數(shù)據(jù)不用修改鏈表指針的內(nèi)容，故只需傳入鏈表指針就行了

查找到時則返回節(jié)點地址，否則返回NULL

代碼：

//鏈表數(shù)據(jù)查找

SLTNode*SListFind(SLTNode*phead,SLTDateTypex)

//創(chuàng)建尋址指針

SLTNode*cur=phead;

while(cur!=NULL)

if(cur-data==x)//找到數(shù)據(jù)符合節(jié)點

returncur;//返回節(jié)點地址（好處：以便后續(xù)再尋找或修改）

else

//找下一個節(jié)點

cur=cur-next;

//未找到數(shù)據(jù)符合節(jié)點

returnNULL;

鏈表pos位置前插數(shù)據(jù)

注意：

想要pos位置前插數(shù)據(jù)，不僅需要找到pos位置，還需要記錄pos的前一個節(jié)點位置

傳入的pos為NULL則報錯

進行修改前節(jié)點的址域成新節(jié)點，并讓新節(jié)點的址域修改成pos，這才是一個成功的pos位置前插數(shù)據(jù)

循環(huán)遍歷鏈表查找pos位置，沒有找到pos位置則什么也不干

代碼：

//鏈表pos位置往前插入(較難)（還有在pos位置之后插入，簡單點）

voidSListInsert(SLTNode**pphead,SLTNode*pos,SLTDateTypex)

//避免傳入錯誤(直接報錯便于找到錯誤位置)

assert(pphead);

assert(pos);

SLTNode*newnode=BuySListNode(x);

//首結(jié)點符合的情況

if(*pphead==pos)

newnode-next=*pphead;

*pphead=newnode;

else

//創(chuàng)建尋址指針

SLTNode*cur=*pphead;

while(cur!=NULL)

if(cur-next!=pos)

cur=cur-next;//找到下一節(jié)點

else//找到對應空間

cur-next=newnode;

newnode-next=pos;

return;//結(jié)束尋找（否則會一直插入，造成死循環(huán)）

//未找到則什么也不干

return;

鏈表pos位置后插數(shù)據(jù)

注意：

后插則不用關注是否為首節(jié)點

也不用找到遍歷找到前節(jié)點的位置

后插則先將新節(jié)點址域改成pos后節(jié)點地址再將pos的址域改成新節(jié)點地址

ps:一定要注意修改鏈接節(jié)點址域的先后，避免地址的丟失

代碼：

//鏈表pos位置往后插入

voidSListInsert(SLTNode**pphead,SLTNode*pos,SLTDateTypex)

SLTNode*newnode=BuySListNode(x);

newnode-next=pos-next;

pos-next=newnode;

return;

鏈表pos位置數(shù)據(jù)刪除

注意：

考慮刪除首節(jié)點的情況，可能修改鏈表指針的內(nèi)容，故需要傳入鏈表指針的地址

對于刪除節(jié)點，需要先保存pos位置下一個節(jié)點地址，將pos位置釋放，再將pos位置前節(jié)點的址域改成pos位置后節(jié)點的地址，這才是成功的刪除pos位置節(jié)點

循環(huán)找pos位置，沒找到則什么也不干

參考代碼:

//鏈表pos位置刪除

voidSListErase(SLTNode**pphead,SLTNode*pos)

//避免傳入錯誤(直接報錯便于找到錯誤位置)

assert(pphead);

assert(pos);

//頭結(jié)點符合的情況

if(*pphead==pos)

*pphead=(*pphead)-next;

free(pos);

else

//創(chuàng)建尋址指針

SLTNode*cur=*pphead;

while(cur!=NULL)

if(cur-next!=pos)

cur=cur-next;//找到下一節(jié)點

else//找到對應空間

SLTNode*next=cur-next-next;

free(cur-next);

cur-next=next;

return;//結(jié)束尋找

//未找到則什么也不干

return;

鏈表節(jié)點釋放

注意:

對于動態(tài)開辟的內(nèi)存空間，在使用后一定要記得的進行釋放（避免造成內(nèi)存泄漏）

因為鏈表節(jié)點是一個個開辟的，同樣的釋放也需要一個個進行釋放

循環(huán)遍歷釋放當前節(jié)點前需保存后一個節(jié)點的地址，避免地址丟失無法釋放

釋放完后，還需將鏈表指針給置空（避免使用野指針）

參考代碼:

//鏈表節(jié)點釋放

voidSListDestory(SLTNode**pphead)

//避免傳入錯誤(直接報錯便于找到錯誤位置)

assert(pphead);

//遍歷釋放

SLTNode*cur=*pphead;

while(cur)

//保存下一個地址

SLTNode*next=cur