第C語言實現(xiàn)動態(tài)鏈表的示例代碼目錄結(jié)構(gòu)體定義已經(jīng)函數(shù)聲明函數(shù)實現(xiàn)創(chuàng)建一個鏈表判斷鏈表是否為空獲得鏈表中節(jié)點的個數(shù)在某個特定的位置插入一個元素獲得指定下標的節(jié)點的元素刪除一個節(jié)點鏈表逆序鏈表的清空鏈表的銷毀鏈表的遍歷按特定的元素查找節(jié)點按某些特定的條件刪除所有符合情況的節(jié)點鏈表的排序總結(jié)鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點（鏈表中每一個元素稱為結(jié)點）組成，結(jié)點可以在運行時動態(tài)生成。每個結(jié)點包括兩個部分：一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域，另一個是存儲下一個結(jié)點地址的指針域。

結(jié)構(gòu)體定義已經(jīng)函數(shù)聲明

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

typedefstructSNode{

void*pdata;//存儲數(shù)據(jù)，這個數(shù)據(jù)可以是任意類型

structSNode*next;//節(jié)點的下一個節(jié)點地址

}SNode;

typedefstructSNode*SLink;//定義一個鏈表

函數(shù)聲明

//創(chuàng)建一個鏈表

SLinkcreate_slink();

//初始化一個鏈表

voidinit_slink(SLink*link);

//判斷鏈表是否為空

boolis_empty(SLinklink);

//獲得鏈表存儲的個數(shù)

size_tsize(SLinklink);

//插入元素元素存儲在pdata,一共size個字節(jié)

intinsert(SLinklink,size_tindex,void*pdata,size_tsize);

//獲得指定下標的節(jié)點元素，并且返回其地址

void*get(SLinklink,size_tindex);

//刪除一個節(jié)點

intremove_data(SLinklink,size_tindex);

//鏈表逆序

SLinkreverse(SLinklink);

//清空鏈表

voidclear(SLinklink);

//銷毀鏈表

voiddestroy(SLinklink);

//遍歷鏈表(通過函數(shù)指針完成用戶需要的要求)

voidforeach(SLinklink,void(*func)(constvoid*));

//通過值查找某個節(jié)點

void*find(SLinklink,void*pdata,int(*compare)(constvoid*,constvoid*));

//通過值刪除所有需要刪除的節(jié)點

intremove_all(SLinklink,void*pdata,int(*compare)(constvoid*,constvoid*));

//鏈表排序，通過冒泡排序

voidsort(SLinklink,int(*compare)(constvoid*,constvoid*));

函數(shù)實現(xiàn)

創(chuàng)建一個鏈表

首先動態(tài)鏈表一般有一個頭結(jié)點(也不是必須有，但是頭結(jié)點可以讓后面的算法變得簡單些)，這個頭結(jié)點不存儲數(shù)據(jù)，只存放第一個節(jié)點(存放數(shù)據(jù)的節(jié)點，也叫作首節(jié)點)的地址，所以我們可以讓節(jié)點的pdata為null。

具體實現(xiàn)如下:

首先我們寫一個函數(shù)實現(xiàn)生成一個節(jié)點，這樣在我們以后只要有插入節(jié)點的操作就可以用這個靜態(tài)方法來實現(xiàn)；這個函數(shù)我們需要傳數(shù)據(jù)的地址，數(shù)據(jù)的大小(這樣我們才能把數(shù)據(jù)拷貝到節(jié)點里面去)，還有下一個節(jié)點的地址；

staticSNode*create_node(void*pdata,size_tsize,SNode*next){

SNode*node=malloc(sizeof(SNode));//先用malloc申請一塊動態(tài)內(nèi)存

if(pdata==NULL){//如果傳進來的數(shù)據(jù)地址為null

node-pdata=NULL;

}else{

node-pdata=malloc(size);//否則為數(shù)據(jù)也申請一塊大小為size的動態(tài)內(nèi)存，

memcpy(node-pdata,pdata,size);//把pdata指向的數(shù)據(jù)通過memcpy拷貝到node-pdata里去，拷貝size個字節(jié)

node-next=next;//讓節(jié)點指向下一個節(jié)點

returnnode;//返回這個節(jié)點

所以有了上面這個靜態(tài)方法，后面的創(chuàng)建一個鏈表還是插入一個節(jié)點就變得很簡單了

因為我們剛開始創(chuàng)建的是一個空鏈表，即只有一個頭結(jié)點，因此不傳數(shù)據(jù)

SLinkcreate_slink(){

//returncreate_node(NULL,0,NULL);

SNode*head=create_node(NULL,0,NULL);

returnhead;

除了創(chuàng)建一個鏈表，我們還可以初始化一個鏈表，(即在其他函數(shù)里先定義一個節(jié)點)再給它初始化。

這里我們傳進來一個鏈表的地址,鏈表類型為SNode*,它的地址即為SNode**類型，因為只有傳遞一個元素得地址，我們才能在一個函數(shù)中改變這個元素得值(函數(shù)間的傳參是值賦值）。

voidinit_slink(SLink*link){

*link=create_node(NULL,0,NULL);//同樣調(diào)用生成節(jié)點的靜態(tài)方法

判斷鏈表是否為空

所謂空鏈表就是指只有一個頭結(jié)點,這個頭結(jié)點并不存儲數(shù)據(jù)，只是記錄首節(jié)點的地址，如果這個首節(jié)點的地址為空，那么這就是一個空鏈表

boolis_empty(SLinklink){

returnlink-next==NULL;

獲得鏈表中節(jié)點的個數(shù)

鏈表中的節(jié)點是指存儲了元素的節(jié)點，所以不能包含頭結(jié)點，我們只需要把這個節(jié)點遍歷一遍，如果某個節(jié)點的下一個地址(next)為空，那這個節(jié)點就是尾結(jié)點

}

size_tsize(SLinklink){

size_tcnt=0;//用來記錄節(jié)點個數(shù)

SNode*node=link-next;//從首節(jié)點開始算起

while(node!=NULL){//遍歷這個鏈表

++cnt;

node=node-next;

returncnt;

在某個特定的位置插入一個元素

在index的位置插入一個元素，就是我們需要把index的位置變成我們新插入的節(jié)點。

在鏈表中插入一個節(jié)點，并不像在線性表(數(shù)組)中那么復(fù)雜，在線性表中插入一個元素我們需要把插入節(jié)點后面的元素都往后移，這樣增加了很多負擔，但是在鏈表中的插入節(jié)點(或者刪除節(jié)點)，都只需要改變一下附近節(jié)點的指針指向就OK了，所以操作變得簡單了很多，下面我們來詳細講解一下如何插入一個節(jié)點。

首先肯定是找到我們插入的位置

如上圖所示，我們需要在下標為3的位置插入一個節(jié)點，那我們該怎么做呢

是的我們可以想辦法獲得下標為2這個節(jié)點，然后斷開2和3之間的連線,再把new節(jié)點插入進去

如圖，我們把2節(jié)點的next指向了新插入的new節(jié)點，把new的next指向了3的節(jié)點,那2和3之間的連系就順利成章的斷掉了,那我們的插入就算完成了。

所以我們來看一下代碼

首先當然是獲得我們需要插入位置的前一個節(jié)點,即上圖的2節(jié)點

staticSNode*get_prev_node(SLinklink,size_tindex){//獲得前一個節(jié)點

SNode*node=link;//從頭結(jié)點開始找，比如我們插入在鏈表首插入一個節(jié)點就是插入到頭結(jié)點后面

//我們在鏈表尾插入一個節(jié)點就是當node-next為null的時候插入

size_ti;

for(i=0;iindexnode!=NULL;i++){

node=node-next;

returnnode;//這里的返回值可能為null,比如當node為尾結(jié)點的時候,它的node-next就為null

插入操作

intinsert(SLinklink,size_tindex,void*pdata,size_tsize){

if(pdata==NULL){//如果沒有傳進來數(shù)據(jù)，那就插入失敗

return-1;

SNode*prev=get_prev_node(link,index);

if(prev==NULL){//獲得插入位置的前一個節(jié)點,當它為Null時也不能插入數(shù)據(jù)，

return-1;

SNode*node=create_node(pdata,size,prev-next);//調(diào)用生成節(jié)點的靜態(tài)方法生成一個節(jié)點,

//并且傳入pdata,size,如上圖所示,新插入的節(jié)點的next指向的是原本前一個節(jié)點prev的next

prev-next=node;//把prev-next重新指向新插入的節(jié)點,這樣插入就完成了

//完成了new節(jié)點旁邊兩條線的鏈接工作

//prev-next=create_node(pdata,size,prev-next);

return0;

關(guān)于在鏈表首或者鏈表尾插入數(shù)據(jù)

這里其實很簡單，就是新插入的節(jié)點的前一個節(jié)點為頭結(jié)點或者尾結(jié)點的問題，大家可以自己寫一下

獲得指定下標的節(jié)點的元素

這個操作比較簡單，只需要在滿足條件下把這個下標遍歷完就可以了，沒有什么難點

void*get(SLinklink,size_tindex){

SNode*node=link-next;//這里我們不能從頭結(jié)點開始遍歷，因為頭結(jié)點并不存儲數(shù)據(jù)所以只能從首節(jié)點開始遍歷

size_ti;

for(i=0;iindexnode!=NULL;i++){

node=node-next;

if(node==NULL){

returnNULL;

returnnode-pdata;//遍歷完成并且返回這個數(shù)據(jù)的地址即可

刪除一個節(jié)點

刪除可以說是插入的反過來的操作

比如上圖，我們需要刪除3這個節(jié)點,那我們該怎么辦呢？其實比插入更簡單，我們只需要讓2的next指向需要刪除節(jié)點的next(也就是3的next)，并且把3節(jié)點給釋放掉，把里面的數(shù)據(jù)也釋放掉就OK了

首先我們也可以寫一個靜態(tài)方法來實現(xiàn)刪除某個節(jié)點

staticvoidremove_node(SNode*prev){//這里的prev為需要被刪除的節(jié)點的前一個節(jié)點

SNode*node=prev-next;//記錄被刪除的節(jié)點

SNode*next=node-next;//記錄被刪除的節(jié)點的下一個節(jié)點

free(node-pdata);

free(node);

prev-next=next;

然后刪除節(jié)點的操作

intremove_data(SLinklink,size_tindex){

SNode*prev=get_prev_node(link,index);//獲得被刪除節(jié)點的前一個節(jié)點

if(link==NULL||prev==NULL||prev-next==NULL){

//如果鏈表不存在或者被刪除節(jié)點的前一個節(jié)點不存在或者被刪除的節(jié)點不存在，那就刪除失敗

return-1;

remove_node(prev);

return0;

大家自己也可以寫一下刪除首節(jié)點或者尾結(jié)點

鏈表逆序

所謂鏈表逆序就是將鏈表的存儲順序反過來，

比如上圖，它的逆序結(jié)果是什么呢？

我們來看一下，就是讓5節(jié)點的next指向4節(jié)點,4指向3,3指向2,2指向1,1的next指向NULL，然后再把頭結(jié)點指向5，就完成了逆序,如下圖所示

那我們該怎么用代碼實現(xiàn)呢？

SLinkreverse(SLinklink){

if(link==NULL||link-next==NULL||link-next-next==NULL){

//如果鏈表不存在或者只存在頭結(jié)點或者只存在一個節(jié)點,那么我們就不需要進行逆序操作

returnlink;

SNode*prev=link-next;//記錄第一個節(jié)點

SNode*curr=link-next-next;//記錄第二個節(jié)點

SNode*next;

while(curr!=NULL){//只要當前節(jié)點不為空就繼續(xù)執(zhí)行下去

next=curr-next;//記錄curr的下一個節(jié)點

curr-next=prev;//讓指針反過來指向，即當前節(jié)點的指針指向前一個節(jié)點

prev=curr;//然后往后移

curr=next;

//最后還有兩條線沒有連上

//即以前的首節(jié)點（即上圖的節(jié)點1）的next應(yīng)該指向null,首節(jié)點再變?yōu)閜rev，即上圖的節(jié)點5

link-next-next=NULL;//

link-next=prev;

returnlink;

鏈表的清空

清空鏈表只需要一個一個的遍歷，把節(jié)點里的數(shù)據(jù)釋放掉，再釋放掉該節(jié)點

voidclear(SLinklink){

SNode*node=link-next;//從首節(jié)點開始遍歷

while(node!=NULL){

SNode*next=node-next;//記錄需要被釋放的節(jié)點的下一個節(jié)點

free(node-pdata);

free(node);

node=next;

link-next=NULL;

鏈表的銷毀

這個更為簡單，只需要先清空里面的節(jié)點，在把頭結(jié)點釋放掉即可

voiddestroy(SLinklink){

clear(link);

free(link);

鏈表的遍歷

鏈表的遍歷也無需多說，我們只需要從首節(jié)點開始遍歷，并且把節(jié)點的數(shù)據(jù)傳給函數(shù)指針，這樣也更加靈活，一直遍歷到null為止

voidforeach(SLinklink,void(*func)(constvoid*)){

SNode*node=link-next;//從首節(jié)點開始遍歷

for(;node!=NULL;node=node-next){

func(node-pdata);//把節(jié)點的數(shù)據(jù)傳給func這個函數(shù)，

//然后用戶需要對這個數(shù)據(jù)進行什么樣的處理由用戶自己決定，不僅僅是局限于把這些數(shù)據(jù)給打印出來

//這樣的好處是對數(shù)據(jù)的處理更加靈活了

按特定的元素查找節(jié)點

我們也是從首節(jié)點開始遍歷，對首節(jié)點里的數(shù)據(jù)進行比較，如果找到相同的數(shù)據(jù)，那就返回這個數(shù)據(jù)的地址

void*find(SLinklink,void*pdata,int(*compare)(constvoid*,constvoid*)){

SNode*node=link-next;//從首節(jié)點開始查找

for(;node!=NULL;node=node-next){

if(compare(node-pdata,pdata)==0){//如果該節(jié)點的數(shù)據(jù)和帶查找的數(shù)據(jù)相等

returnnode-pdata;//那就返回這個數(shù)據(jù)的地址

returnNULL;//如果沒有找到就返回null

這里的compare也是函數(shù)指針，都是同樣的道理，對于需要找什么由用戶自己決定，不在局限于查找某個特定的元素

比如在一個學生信息的結(jié)構(gòu)體中，我們可以按學號進行查找，也可以按姓名進行查找，也可以按年齡、班級、等等進行查找，讓這些使用起來更加靈活

比如我給大家寫一個查找的函數(shù),就按學生的學號進行查找

intcompare(constvoid*v1,constvoid*v2){

Stu*stu1=(Stu*)v1;

Stu*stu2=(Stu*)v2;

returnv1-no-v2-

按某些特定的條件刪除所有符合情況的節(jié)點

這個刪除的操作其實和上面的刪除特定下標的節(jié)點的操作大同小異，都是找到待刪除節(jié)點的前一個節(jié)點，然后進行操作，這里找到后并不急于退出，而是繼續(xù)往下查找，直到找完整個鏈表并且刪除所有符合條件的節(jié)點

intremove_all(SLinklink,void*pdata,int(*compare)(constvoid*,constvoid*)){

SNode*prev=link;

intcnt=0;

while(prev-next!=NULL){

if(compare(prev-next-pdata,pdata)==0){//找到待刪除節(jié)點的前一個節(jié)點

remove_node(prev);//刪除該節(jié)點

cnt++;//刪除的個數(shù)++

}else{

prev=prev-next;//否則沒找到就是往下繼續(xù)查找

returncnt00:-1;

鏈表的排序

排序我這里選擇冒泡排序，如果大家想看更多的排序方法也可以看我以前寫的博客，我總共寫了12種排序方法

這里的排序和我以前寫的幾乎一模一樣，我就不再多說了，唯一需要講解的還是函數(shù)指針的應(yīng)用，比如我們可以選擇對學生的學號進行排序，也可以對學生的