C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之單向鏈表詳解

第C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之單向鏈表詳解目錄鏈表靜態(tài)鏈表動(dòng)態(tài)鏈表定義鏈表節(jié)點(diǎn)創(chuàng)建鏈表創(chuàng)建一個(gè)空節(jié)點(diǎn)尾插法頭插法指定位置插入一個(gè)結(jié)點(diǎn)遍歷鏈表獲取鏈表長(zhǎng)度鏈表搜索鏈表數(shù)據(jù)排序反轉(zhuǎn)鏈表刪除節(jié)點(diǎn)數(shù)據(jù)銷毀鏈表測(cè)試

鏈表

鏈表實(shí)現(xiàn)了，內(nèi)存零碎數(shù)據(jù)的有效組織。比如，當(dāng)我們用malloc來(lái)進(jìn)行內(nèi)存申請(qǐng)的時(shí)候，當(dāng)內(nèi)存足夠，但是由于碎片太多，沒(méi)有連續(xù)內(nèi)存時(shí)，只能以申請(qǐng)失敗而告終，而用鏈表這種數(shù)據(jù)結(jié)構(gòu)來(lái)組織數(shù)據(jù)，就可以解決上類問(wèn)題。

靜態(tài)鏈表

#includestdio.h

//1.定義鏈表節(jié)點(diǎn)

typedefstructnode{

intdata;

structnode*next;

}Node;

intmain(intargc,char*argv[]){

//2.創(chuàng)建鏈表節(jié)點(diǎn)

Nodea;

Nodeb;

Nodec;

//3.初始化節(jié)點(diǎn)數(shù)據(jù)

a.data=1;

b.data=3;

c.data=5;

//4.鏈接節(jié)點(diǎn)

a.next=

b.next=

c.next=NULL;

//5.創(chuàng)建鏈表頭

Node*head=

//6.使用鏈表

while(head!=NULL){

intcurrentData=head-data;

printf("currentData=%i\n",currentData);

head=head-next;//指向下一個(gè)節(jié)點(diǎn)

return0;

}

動(dòng)態(tài)鏈表

靜態(tài)鏈表的意義不是很大，主要原因，數(shù)據(jù)存儲(chǔ)在棧上，棧的存儲(chǔ)空間有限，不能動(dòng)態(tài)分配。所以鏈表要實(shí)現(xiàn)存儲(chǔ)的自由，要?jiǎng)討B(tài)的申請(qǐng)堆里的空間。

有頭鏈表

無(wú)頭鏈表

單向鏈表有有頭節(jié)點(diǎn)和無(wú)頭節(jié)點(diǎn)兩種列表,有頭節(jié)點(diǎn)在列表的刪除,反轉(zhuǎn),插入等操作會(huì)比無(wú)頭節(jié)點(diǎn)簡(jiǎn)單,但是不好之處就是多占用些空間,而且在多個(gè)鏈表結(jié)合處理的時(shí)候有頭鏈表每次都需要過(guò)濾頭節(jié)點(diǎn),而無(wú)頭鏈表直接完美融合,而且很多高級(jí)語(yǔ)言都是無(wú)頭鏈表的便于日后的擴(kuò)展,下面都是依據(jù)無(wú)頭節(jié)點(diǎn)進(jìn)行演示

定義鏈表節(jié)點(diǎn)

//1.定義鏈表節(jié)點(diǎn)

typedefstructnode{

void*data;

structnode*next;

}Node;

創(chuàng)建鏈表

/**

*創(chuàng)建鏈表

Node*createList(){

//1.創(chuàng)建頭節(jié)點(diǎn)

Node*root=(Node*)malloc(sizeof(Node));

root-data=NULL;

root-next=NULL;

//返回頭節(jié)點(diǎn)

returnroot;

創(chuàng)建一個(gè)空節(jié)點(diǎn)

/**

*創(chuàng)建一個(gè)空節(jié)點(diǎn)

Node*createNode(){

Node*node=(Node*)malloc(sizeof(Node));

node-data=NULL;

node-next=NULL;

returnnode;

}

尾插法

/**

*@briefinsertEndNode尾插法插入節(jié)點(diǎn)

*@paramhead需要插入的頭指針

*@paramdata需要插入的數(shù)據(jù)

voidinsertEndNode(Node*node,void*data){

Node*head=node;

//找到數(shù)據(jù)為空的節(jié)點(diǎn),沒(méi)有節(jié)點(diǎn)那么就擴(kuò)展

while(head-data!=NULL){

//擴(kuò)容

if(head-next==NULL){

Node*pNode=createNode();

head-next=pNode;

head=pNode;

break;

head=head-next;

//插入數(shù)據(jù)

head-data=data;

}

頭插法

/**

*@briefinsertHeadNode頭插法插入節(jié)點(diǎn)

*@paramhead需要插入的頭指針

*@paramdata需要插入的數(shù)據(jù)

voidinsertHeadNode(Node**node,void*data){

Node*pNode=createNode();

pNode-data=data;

pNode-next=*node;

*node=pNode;

指定位置插入一個(gè)結(jié)點(diǎn)

簡(jiǎn)單來(lái)說(shuō)就是先找到需要插入的位置,然后將當(dāng)前位置節(jié)點(diǎn)和他前一個(gè)節(jié)點(diǎn)連接到需要插入的節(jié)點(diǎn)就行了

/**

*@briefinsertNOde將數(shù)據(jù)節(jié)點(diǎn)插入到指定數(shù)據(jù)位置節(jié)點(diǎn),指定數(shù)據(jù)節(jié)點(diǎn)向后移動(dòng),如果沒(méi)有找到插入的位置,那么就插入到最后

*@paraminsertionPoint指定的數(shù)據(jù)節(jié)點(diǎn)

*@paramdata需要插入的數(shù)據(jù)

voidinsertNode(Node*node,void*insertionPoint,void*data){

Node*pNode=node;

Node*pre=pNode;//父節(jié)點(diǎn)

while(pNode!=NULL){

if(pNode-data==insertionPoint){

break;

pre=pNode;//保留當(dāng)前節(jié)點(diǎn)

pNode=pNode-next;

//如果沒(méi)有找到那么就插入到最后

if(pNode==NULL){

insertEndNode(node,data);

return;

Node*dataNode=createNode();

dataNode-data=data;

pre-next=dataNode;

dataNode-next=pNode;

}

遍歷鏈表

因?yàn)槲覀冎荡鎯?chǔ)是使用無(wú)類型的指針,所以需要轉(zhuǎn)換為插入時(shí)候的類型才行

/**

*@briefprintNodeListDouble遍歷鏈表

*@paramnode鏈表指針頭

voidprintNodeListDouble(Node*node){

Node*head=node;

while(head!=NULLhead-data!=NULL){

double*currentData=head-data;

printf("currentData=%f\n",*currentData);

head=head-next;

獲取鏈表長(zhǎng)度

/**

*@brieflistLength計(jì)算鏈表長(zhǎng)度

*@paramhead鏈表頭指針

*@return鏈表長(zhǎng)度

intlistLength(Node*head){

intcount=0;

head=head;

while(head){

count++;

head=head-next;

returncount;

鏈表搜索

/**

*@briefsearchList查找指定節(jié)點(diǎn)

*@paramhead鏈表頭指針

*@paramkey需要查找的值

*@return

Node*searchList(Node*head,void*key){

head=head;

while(head){

if(head-data==key){

break;

}else{

head=head-next;

returnhead;

}

鏈表數(shù)據(jù)排序

因?yàn)槲覀兇鎯?chǔ)數(shù)據(jù)類型是使用無(wú)類型的指針,那么在排序的時(shí)候需要轉(zhuǎn)換為指定類型才行

/**

*@briefbubbleSort對(duì)鏈表值進(jìn)行排序小到大

*@paramhead鏈表頭指針

voidsortDouble(Node*head){

//1.計(jì)算鏈表長(zhǎng)度

intlen=listLength(head);

//2.定義變量記錄前后節(jié)點(diǎn)

Node*cur=head;

while(cur!=NULL){

Node*cur1=cur-next;

while(cur1!=NULL){

//比較大小,然后交換數(shù)據(jù)

if(*((double*)cur-data)*((double*)cur1-data)){

double*temp=(double*)cur-data;

cur-data=cur1-data;

cur1-data=temp;

cur1=cur1-next;

cur=cur-next;

}

反轉(zhuǎn)鏈表

斷開(kāi)鏈表頭，然后以頭插法的方式將原鏈表的數(shù)據(jù)添加鏈表。

/**

*@briefreverseList反轉(zhuǎn)鏈表

*@paramhead鏈表頭指針

voidreverseList(Node**root){

Node*head=*root;

Node*pre=head,*cur=head-next;

pre-next=NULL;

while(cur!=NULL){

Node*node=cur-next;

cur-next=pre;

pre=cur;

cur=node;

*root=pre;

}

刪除節(jié)點(diǎn)數(shù)據(jù)

先找到需要?jiǎng)h除的節(jié)點(diǎn),之后將后一個(gè)結(jié)點(diǎn)賦值給前一個(gè)結(jié)點(diǎn)的next,然后將刪除位置的結(jié)點(diǎn)釋放即可

/**

*@briefdelNode刪除指定節(jié)點(diǎn)

voiddelNode(Node**root,void*key){

Node*head=*root;

//根節(jié)點(diǎn)單獨(dú)處理

if(head-data==keyhead-next!=NULL){

*root=head-next;

free(head-data);

free(head);

return;

Node*head1=head-next;

Node*pre=head;//根節(jié)點(diǎn)

while(head1!=NULL){

if(head1-data==key){

pre-next=head1-next;

free(head1-data);

free(head1);

break;

pre=head1;//當(dāng)前節(jié)點(diǎn)

head1=head1-next;//下一個(gè)節(jié)點(diǎn)

}

銷毀鏈表

/**

*@bri