C語(yǔ)言深入講解鏈表的使用

第C語(yǔ)言深入講解鏈表的使用目錄一、鏈表的概念二、鏈表的分類1.單向或者雙向鏈表2.帶頭或者不帶頭(是否有自帶哨兵位頭結(jié)點(diǎn))3.循環(huán)或者非循環(huán)鏈表4.無(wú)頭單向非循環(huán)鏈表和帶頭雙向循環(huán)鏈表3、鏈表的實(shí)現(xiàn)(代碼和注釋)4、鏈表oj題(小試牛刀)總結(jié)現(xiàn)實(shí)生活中的火車(chē)就像一個(gè)完整的鏈表，現(xiàn)在我們來(lái)深入理解一下鏈表這個(gè)數(shù)據(jù)結(jié)構(gòu)。

一、鏈表的概念

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

注：

1、從上圖中可看出，鏈?zhǔn)浇Y(jié)構(gòu)在邏輯上是連續(xù)的，但是在物理上不一定連續(xù)。

2、從現(xiàn)實(shí)中的結(jié)點(diǎn)一般是通過(guò)malloc函數(shù)申請(qǐng)的，所以其內(nèi)存分配是在堆區(qū)。

3、從堆上申請(qǐng)的空間，是按照一定的策略來(lái)分配的，則一個(gè)節(jié)點(diǎn)的大小為8個(gè)字節(jié)。

二、鏈表的分類

實(shí)際中鏈表的結(jié)構(gòu)非常多樣，以下情況組合起來(lái)就有8種鏈表結(jié)構(gòu)：

1.單向或者雙向鏈表

2.帶頭或者不帶頭(是否有自帶哨兵位頭結(jié)點(diǎn))

第二個(gè)鏈表的d1指向了我們的哨兵位頭結(jié)點(diǎn)。

3.循環(huán)或者非循環(huán)鏈表

4.無(wú)頭單向非循環(huán)鏈表和帶頭雙向循環(huán)鏈表

1.無(wú)頭單向非循環(huán)鏈表：結(jié)構(gòu)簡(jiǎn)單，一般不會(huì)單獨(dú)用來(lái)存數(shù)據(jù)。實(shí)際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。

2.帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，一般用在單獨(dú)存儲(chǔ)數(shù)據(jù)。實(shí)際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。另外這個(gè)結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實(shí)現(xiàn)以后會(huì)發(fā)現(xiàn)結(jié)構(gòu)會(huì)帶來(lái)很多優(yōu)勢(shì)，實(shí)現(xiàn)反而簡(jiǎn)單了。

3、鏈表的實(shí)現(xiàn)(代碼和注釋)

無(wú)頭+單向+非循環(huán)鏈表增刪查改實(shí)現(xiàn)

頭文件：

#pragmaonce

#includestdio.h

#includestdlib.h

#includeassert.h

//要求存儲(chǔ)的數(shù)據(jù)從0開(kāi)始，依次存儲(chǔ)

//靜態(tài)的順序表

//問(wèn)題：開(kāi)小了，不夠用，開(kāi)大了，存在浪費(fèi)。

//structSeqList

//inta[N];

//intsize;//記錄存儲(chǔ)了多少個(gè)數(shù)據(jù)。

typedefintSLDateType;//宏定義我們的SLDateType是int類型的

//動(dòng)態(tài)的順序表

typedefstructSeqList

SLDateType*a;

intsize;//存儲(chǔ)數(shù)據(jù)個(gè)數(shù)

intcapacity;//存儲(chǔ)空間大小

}SL,SeqList;

voidSeqListPrint(SeqList*psl);//鏈表的打印

voidSeqListInit(SeqList*psl);//鏈表的初始化

voidSeqListDestroy(SeqList*psl);//鏈表的銷毀

voidSeqListCheckCapacity(SeqList*psl);//檢查內(nèi)存空間是否足夠

//時(shí)間復(fù)雜度是o(1)

voidSeqListPushBack(SeqList*psl,SLDateTypex);//鏈表的尾插

voidSeqListPopBack(SeqList*psl);//鏈表的尾刪

//時(shí)間復(fù)雜度是o(n)

voidSeqListPushFront(SeqList*psl,SLDateTypex);//鏈表的頭插

voidSeqListPopFront(SeqList*psl);//鏈表的頭刪

voidSeqListInsert(SeqList*psl,size_tpos,SLDateTypex);

//刪除pos位置的數(shù)據(jù)

voidSeqListErase(SeqList*psl,size_tpos);

//順序表查找

intSeqListFind(SeqList*psl,SLDateTypex);

鏈表的函數(shù)實(shí)現(xiàn)部分的代碼：

#include"SeqList.h"

#includeassert.h

voidSeqListPrint(SeqList*psl)//結(jié)構(gòu)體指針傳參

for(inti=0;ipsl-size;++i)

printf("%d",psl-a[i]);

printf("\n");

voidSeqListInit(SeqList*psl)

assert(psl);//斷言psl不為空

psl-a=NULL;//a就相當(dāng)于是鏈表的頭

psl-size=0;

psl-capacity=0;

voidSeqListDestroy(SeqList*psl)//鏈表的刪除

assert(psl);

free(psl-//free掉鏈表中a這個(gè)節(jié)點(diǎn)的位置

psl-a=NULL;//將a指向空

psl-capacity=psl-size=0;//將鏈表的內(nèi)存大小置為0

voidSeqListCheckCapacity(SeqList*psl)//檢查鏈表的內(nèi)存，如果不夠就增容。

assert(psl);

if(psl-size==psl-capacity)

//capacity==0,所以要先特判一下capacity的值

size_tnewCapacity=psl-capacity==04:psl-capacity*2;//初始節(jié)點(diǎn)數(shù)為4，如果內(nèi)存現(xiàn)在為0就擴(kuò)大一倍

SLDateType*tmp=realloc(psl-a,sizeof(SLDateType)*newCapacity);//申請(qǐng)空間

if(tmp==NULL)

printf("reallocfail\n");

exit(-1);

else

psl-a=tmp;

psl-capacity=newCapacity;//原來(lái)的空間變?yōu)樾驴臻g

voidSeqListPushBack(SeqList*psl,SLDateTypex)

//如果滿了，要擴(kuò)容

if(psl-size==psl-capacity)

//capacity==0,所以要先特判一下capacity的值

size_tnewCapacity=psl-capacity==04:psl-capacity*2;

SLDateType*tmp=realloc(psl-a,sizeof(SLDateType)*newCapacity);

if(tmp==NULL)

printf("reallocfail\n");

exit(-1);

else

psl-a=tmp;

psl-capacity=newCapacity;

psl-a[psl-size]=x;

psl-size++;

voidSeqListPopBack(SeqList*psl)

assert(psl);

if(psl-size0)

psl-size--;//尾刪就size--就好了

voidSeqListPushFront(SeqList*psl,SLDateTypex)

assert(psl);

SeqListCheckCapacity(psl);

intend=psl-size-1;

while(end=0)//所有的數(shù)據(jù)往后挪1位

psl-a[end+1]=psl-a[end];

--end;

psl-a[0]=x;//兩種操作是等價(jià)的

psl-size++;

//SeqListInsert(psl,0,x);在頭部插入。

voidSeqListPopFront(SeqList*psl)

assert(psl);

if(psl-size0)

intbegin=1;

while(psl-sizebegin)

psl-a[begin-1]=psl-a[begin];

++begin;

--psl-size;

voidSeqListInsert(SeqList*psl,size_tpos,SLDateTypex)

//暴力檢查

assert(psl);

//溫和檢查

if(pospsl-size)

printf("pos越界：%d\n",pos);

return;

//exit(-1);

//暴力檢查

//assert(pos=psl-size);

SeqListCheckCapacity(psl);

//intend=psl-size-1;

//while(end=(int)pos)

//psl-a[end+1]=psl-a[end];

//--end;

size_tend=psl-size;

while(endpos)

psl-a[end]=psl-a[end-1];

--end;

psl-a[pos]=x;

psl-size++;

}

4、鏈表oj題(小試牛刀)

1、leetcode203移除鏈表元素力扣

包含三種情況

畫(huà)個(gè)圖分析：

思路：情況一和情況二都可以用prev和cur指針遍歷數(shù)組的兩個(gè)元素，ifcur指針不等于6，prev指針和cur指針都往前走，如果cur=6，prev跳到cur的下一個(gè)位置

如果是第三種情況，則需先找到head!=val的位置，再重復(fù)進(jìn)行如上操作。

代碼示例：

structListNode*removeElements(structListNode*head,intval)

structListNode*prev=NULL;

structListNode*cur=head;

while(cur)

if(cur-val!=val)//當(dāng)cur這個(gè)位置的值不等于val時(shí)往下走

prev=cur;//prev跳到cur位置

cur=cur-next;//cur指針繼續(xù)往下走

else

structListNode*next=cur-next;//定義一個(gè)新的指針

if(prev==NULL)//頭刪，head為空的狀態(tài)

free(cur);

head=next;//繼續(xù)往后面走

cur=next;

else

free(cur);//free掉cur這個(gè)節(jié)點(diǎn)

prev-next=next;//跳過(guò)了cur這個(gè)點(diǎn)

cur=next;//cur繼續(xù)往后走

returnhead;

}

2、leetcode206反轉(zhuǎn)鏈表力扣

思路1：反轉(zhuǎn)指針?lè)较?/p>

思路二：用三個(gè)指針，n1,n2,n3分別存放NULL,head,head-next;

代碼示例：

structListNode*reverseList(structListNode*head)

if(head==NULL)returnNULL;

structListNode*n1,*n2,*n3;

n1=NULL;

n2=head;

n3=n2-next;//n3的地址是n2的下一位

while(n2)

n2-next=n1;//n2的下一位指向n1;起到掉頭的作用

n1=n2;

n2=n3;

if(n3)

n3=n3-next;

returnn1;

}

方法2：頭插法

殊途同歸。newhead相當(dāng)于之前的n1,cur=n2,next=n3;

structListNode*reverseList(structListNode*head)

structListNode*NewHead=NULL;

structListNode*cur=head;

while(cur)

structListNode*next=cur-next;

//頭插

cur-next=NewHead;//代表鏈表的指向方向。

NewHead=cur;//接著把地址傳過(guò)來(lái)(更新)

cur=next;//（更新）

returnNewHead;

}

3、leetcode876鏈表的中間結(jié)點(diǎn)力扣

思路：快慢指針?lè)?/p>

structLis