第C語言數(shù)據(jù)結(jié)構(gòu)之單鏈表的實現(xiàn)目錄一.為什么使用鏈表二.鏈表的概念三.鏈表的實現(xiàn)3.1創(chuàng)建鏈表前須知3.2定義結(jié)構(gòu)體3.3申請一個節(jié)點(diǎn)3.4鏈表的頭插3.5鏈表的尾插3.6鏈表的尾刪3.7鏈表的頭刪3.8尋找某節(jié)點(diǎn)3.9在指定節(jié)點(diǎn)前插入節(jié)點(diǎn)3.10刪除指定節(jié)點(diǎn)前的節(jié)點(diǎn)3.11鏈表的銷毀

一.為什么使用鏈表

在學(xué)習(xí)鏈表以前，我們存儲數(shù)據(jù)用的方式就是數(shù)組。使用數(shù)組的好處就是便于查找數(shù)據(jù)，但缺點(diǎn)也很明顯。

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

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

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

為了解決上述的問題，我們就可以使用鏈表來存儲數(shù)據(jù)。

二.鏈表的概念

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

三.鏈表的實現(xiàn)

3.1創(chuàng)建鏈表前須知

結(jié)點(diǎn):鏈表中每一個元素稱為結(jié)點(diǎn)，每個結(jié)點(diǎn)都應(yīng)包括兩個部分：一為用戶需要用的實際數(shù)據(jù)；二為下一個結(jié)點(diǎn)的地址，

頭結(jié)點(diǎn)：在單鏈表的第一個結(jié)點(diǎn)之前附設(shè)一個結(jié)點(diǎn)，這個節(jié)點(diǎn)不存儲數(shù)據(jù)，稱之為頭結(jié)點(diǎn)

3.2定義結(jié)構(gòu)體

#includestdio.h

#includestdlib.h

#includeassert.h

typedefintSLDateType;//鏈表中存儲的數(shù)據(jù)類型，可換成其他

typedefstructSListNode

SLDateTypedate;

structSListNode*next;//指向下一個節(jié)點(diǎn)的指針

}SListNode;

3.3申請一個節(jié)點(diǎn)

SListNode*BuyListNode(SLDateTypex)

SListNode*newNode=(SListNode*)malloc(sizeof(SListNode));

if(NULL==newNode)

printf("mallocerror\n");//內(nèi)存開辟失敗

exit(-1);

else

newNode-date=x;//給新節(jié)點(diǎn)賦值

newNode-next=NULL;

returnnewNode;

3.4鏈表的頭插

voidSListPushFront(SListNode**pphead/*要改動頭指針，所以要傳遞二級指針*/,SLDateTypex)

SListNode*newNode=BuyListNode(x);//申請節(jié)點(diǎn)

newNode-next=*pphead;

*pphead=newNode;

3.5鏈表的尾插

voidSListPushBack(SListNode**pphead,SLDateTypex)

SListNode*newNode=BuyListNode(x);

if(*pphead==NULL)//若頭指針為空，則鏈表為空鏈表，直接將新節(jié)點(diǎn)接到頭指針后

*pphead=newNode;

else

SListNode*tail=*pphead;

while(tail-next!=NULL)//找鏈表的尾部

tail=tail-next;

tail-next=newNode;//將新節(jié)點(diǎn)接到尾部

3.6鏈表的尾刪

voidSListPopBack(SListNode**pphead)

assert(pphead);

if(*pphead==NULL)//鏈表為空，則不進(jìn)行任何操作

return;

elseif((*pphead)-next==NULL)//鏈表只有一個節(jié)點(diǎn)

free(*pphead);

*pphead=NULL;

else//其余情況

SListNode*tail=*pphead;//鏈表的尾部節(jié)點(diǎn)

SListNode*pre=NULL;//鏈表尾的前一個節(jié)點(diǎn)

while(tail-next!=NULL)//找尾

pre=tail;

tail=tail-next;

pre-next=tail-next;//將尾節(jié)點(diǎn)的指針域賦值給前一個節(jié)點(diǎn)的指針域

free(tail);

3.7鏈表的頭刪

voidSListPopFront(SListNode**pphead)

assert(pphead);

if(*pphead==NULL)//鏈表為空什么也不做

return;

else

SListNode*head=*pphead;//記錄原本的第一個節(jié)點(diǎn)

*pphead=head-next;//讓頭指針指向第二個節(jié)點(diǎn)

free(head);//釋放第一個節(jié)點(diǎn)

}

3.8尋找某節(jié)點(diǎn)

SListNode*SListFind(SListNode*phead,SLDateTypex)

SListNode*cur=phead;

while(cur!=NULL)

if(cur-date==x)//找到則返回該節(jié)點(diǎn)

returncur;

cur=cur-next;

returnNULL;//未找到則返回空

}

3.9在指定節(jié)點(diǎn)前插入節(jié)點(diǎn)

voidSListInsert(SListNode**pphead,SListNode*pos/*要插入的位置*/,SLDateTypex)

assert(pphead);

assert(pos);

if(*pphead==pos)

SListPushFront(pphead,x);

else

SListNode*cur=*pphead;//當(dāng)前所指向的位置

SListNode*pre=NULL;//前一個節(jié)點(diǎn)

while(cur!=pos)

pre=cur;

cur=cur-next;

SListNode*newNode=BuyListNode(x);

pre-next=newNode;

newNode-next=cur;

3.10刪除指定節(jié)點(diǎn)前的節(jié)點(diǎn)

voidSListErase(SListNode**pphead,SListNode*pos/*要插入的位置*/)

assert(pphead);

assert(pos);

if(*pphead==pos)

SListPopFront(pphead);

else

SListNode*cur=*pphead;

SListNode*pre=*pphead;

while(cur!=pos)

pre=cur;

cur=cur-next;

pre-next=cur-next;

free(cur);

3.11鏈表的銷毀

voidSLis