C語言數(shù)據(jù)結構之單向鏈表詳解

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

鏈表

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

靜態(tài)鏈表

#includestdio.h

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

typedefstructnode{

intdata;

structnode*next;

}Node;

intmain(intargc,char*argv[]){

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

Nodea;

Nodeb;

Nodec;

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

a.data=1;

b.data=3;

c.data=5;

//4.鏈接節(jié)點

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;//指向下一個節(jié)點

return0;

}

動態(tài)鏈表

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

有頭鏈表

無頭鏈表

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

定義鏈表節(jié)點

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

typedefstructnode{

void*data;

structnode*next;

}Node;

創(chuàng)建鏈表

/**

*創(chuàng)建鏈表

Node*createList(){

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

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

root-data=NULL;

root-next=NULL;

//返回頭節(jié)點

returnroot;

創(chuàng)建一個空節(jié)點

/**

*創(chuàng)建一個空節(jié)點

Node*createNode(){

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

node-data=NULL;

node-next=NULL;

returnnode;

}

尾插法

/**

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

*@paramhead需要插入的頭指針

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

voidinsertEndNode(Node*node,void*data){

Node*head=node;

//找到數(shù)據(jù)為空的節(jié)點,沒有節(jié)點那么就擴展

while(head-data!=NULL){

//擴容

if(head-next==NULL){

Node*pNode=createNode();

head-next=pNode;

head=pNode;

break;

head=head-next;

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

head-data=data;

}

頭插法

/**

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

*@paramhead需要插入的頭指針

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

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

Node*pNode=createNode();

pNode-data=data;

pNode-next=*node;

*node=pNode;

指定位置插入一個結點

簡單來說就是先找到需要插入的位置,然后將當前位置節(jié)點和他前一個節(jié)點連接到需要插入的節(jié)點就行了

/**

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

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

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

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

Node*pNode=node;

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

while(pNode!=NULL){

if(pNode-data==insertionPoint){

break;

pre=pNode;//保留當前節(jié)點

pNode=pNode-next;

//如果沒有找到那么就插入到最后

if(pNode==NULL){

insertEndNode(node,data);

return;

Node*dataNode=createNode();

dataNode-data=data;

pre-next=dataNode;

dataNode-next=pNode;

}

遍歷鏈表

因為我們值存儲是使用無類型的指針,所以需要轉換為插入時候的類型才行

/**

*@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;

獲取鏈表長度

/**

*@brieflistLength計算鏈表長度

*@paramhead鏈表頭指針

*@return鏈表長度

intlistLength(Node*head){

intcount=0;

head=head;

while(head){

count++;

head=head-next;

returncount;

鏈表搜索

/**

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

*@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ù)排序

因為我們存儲數(shù)據(jù)類型是使用無類型的指針,那么在排序的時候需要轉換為指定類型才行

/**

*@briefbubbleSort對鏈表值進行排序小到大

*@paramhead鏈表頭指針

voidsortDouble(Node*head){

//1.計算鏈表長度

intlen=listLength(head);

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

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;

}

反轉鏈表

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

/**

*@briefreverseList反轉鏈表

*@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é)點數(shù)據(jù)

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

/**

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

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

Node*head=*root;

//根節(jié)點單獨處理

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

*root=head-next;

free(head-data);

free(head);

return;

Node*head1=head-next;

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

while(head1!=NULL){

if(head1-data==key){

pre-next=head1-next;

free(head1-data);

free(head1);

break;

pre=head1;//當前節(jié)點

head1=head1-next;//下一個節(jié)點

}

銷毀鏈表

/**

*@bri