第C++深入分析講解鏈表目錄鏈表的概述1、數(shù)組特點(diǎn)2、鏈表的概述3、鏈表的特點(diǎn)靜態(tài)鏈表鏈表的操作1、鏈表插入節(jié)點(diǎn)頭部之前插入節(jié)點(diǎn)尾部之后插入節(jié)點(diǎn)有序插入節(jié)點(diǎn)2、遍歷鏈表節(jié)點(diǎn)3、查詢指定節(jié)點(diǎn)4、刪除指定節(jié)點(diǎn)5、釋放鏈表6、鏈表的翻轉(zhuǎn)7、鏈表的排序

鏈表的概述

1、數(shù)組特點(diǎn)

1、空間連續(xù)、元素類型相同、通過下標(biāo)快速訪問

2、靜態(tài)數(shù)組：空間一旦確定不能更改（動(dòng)態(tài)數(shù)組除外）

3、靜態(tài)、動(dòng)態(tài)數(shù)組插入刪除元素需要移動(dòng)大量數(shù)據(jù)

2、鏈表的概述

鏈表是一種物理存儲(chǔ)上非連續(xù)，數(shù)據(jù)元素的邏輯連續(xù)通過鏈表節(jié)點(diǎn)中的指針變量保存下個(gè)節(jié)點(diǎn)的地址，實(shí)現(xiàn)的一種線性存儲(chǔ)結(jié)構(gòu)。

3、鏈表的特點(diǎn)

鏈表由一系列節(jié)點(diǎn)（鏈表中每一個(gè)元素稱為節(jié)點(diǎn)）組成，節(jié)點(diǎn)在運(yùn)行時(shí)動(dòng)態(tài)生成（malloc，calloc），每個(gè)節(jié)點(diǎn)包括兩個(gè)部分：

數(shù)據(jù)域：存放節(jié)點(diǎn)數(shù)據(jù)（核心）

指針域：結(jié)構(gòu)體指針變量保存下一個(gè)節(jié)點(diǎn)的地址

靜態(tài)鏈表

#includestdio.h

//設(shè)計(jì)節(jié)點(diǎn)類型

typedefstructstu

//數(shù)據(jù)域

intnum;

charname[32];

floatscore;

//指針域

structstu*next;

}STU;

intmain(intargc,charconst*argv[])

//靜態(tài)鏈表的節(jié)點(diǎn)不是從堆區(qū)申請(qǐng)

STUnode1={100,"lucy",77.7f};

STUnode2={101,"bob",66.7f};

STUnode3={102,"tom",55.7f};

STUnode4={103,"hehe",74.7f};

STUnode5={104,"xixi",73.7f};

//構(gòu)建成鏈表

STU*head=NULL;

head=node1;

node1.next=node2;

node2.next=node3;

node3.next=node4;

node4.next=node5;

node5.next=NULL;

//遍歷鏈表(從頭節(jié)點(diǎn)逐個(gè)節(jié)點(diǎn)遍歷)

STU*pb=head;

while(pb!=NULL)

printf("%d%s%f\n",pb-num,pb-name,pb-score);

//移動(dòng)到下一個(gè)節(jié)點(diǎn)

pb=pb-next;

return0;

}

鏈表的操作

增、刪、改、查

學(xué)生管理系統(tǒng)講解鏈表

1、鏈表插入節(jié)點(diǎn)

幫助信息函數(shù)：

voidhelp(void)

printf("******************************\n");

printf("*insert:插入鏈表節(jié)點(diǎn)*\n");

printf("*printf:遍歷鏈表節(jié)點(diǎn)*\n");

printf("*search:查詢鏈表節(jié)點(diǎn)*\n");

printf("*delete:刪除鏈表節(jié)點(diǎn)*\n");

printf("*free:釋放鏈表節(jié)點(diǎn)*\n");

printf("*quit:遍歷鏈表節(jié)點(diǎn)*\n");

printf("******************************\n");

return;

}

頭部之前插入節(jié)點(diǎn)

STU*insert_link(STU*head,STUtmp)

//為插入的節(jié)點(diǎn)申請(qǐng)空間

STU*pi=(STU*)calloc(1,sizeof(STU));

//給空間賦值

*pi=tmp;

pi-next=NULL;

//判斷鏈表是否存在

if(NULL==head)//空

head=pi;

//returnhead;

else//非空

pi-next=head;

head=pi;

//returnhead;

returnhead;

}

尾部之后插入節(jié)點(diǎn)

//尾部插入節(jié)點(diǎn)

STU*insert_link(STU*head,STUtmp)

//為插入的節(jié)點(diǎn)申請(qǐng)空間

STU*pi=(STU*)calloc(1,sizeof(STU));

//給空間賦值

*pi=tmp;

pi-next=NULL;

//判斷鏈表是否存在

if(NULL==head)

head=pi;

returnhead;

else

//尋找尾部節(jié)點(diǎn)

STU*pb=head;

while(pb-next!=NULL)

pb=pb-next;

//將pi插入到尾節(jié)點(diǎn)后

pb-next=pi;

returnhead;

returnhead;

}

有序插入節(jié)點(diǎn)

//有序插入節(jié)點(diǎn)

STU*insert_link(STU*head,STUtmp)

//為插入的節(jié)點(diǎn)申請(qǐng)空間

STU*pi=(STU*)calloc(1,sizeof(STU));

//給空間賦值

*pi=tmp;

pi-next=NULL;

//判斷鏈表是否存在

if(NULL==head)

head=pi;

returnhead;

else

//尋找插入點(diǎn)

STU*pf=NULL,*pb=NULL;

pf=pb=head;

//從小---大排序

while((pb-numpi-num)(pb-next!=NULL))

pf=pb;

pb=pb-next;

if(pb-num=pi-num)//頭部插入、中部插入

if(pb==head)//頭部插入

pi-next=head;

head=pi;

else//中部插入

pf-next=pi;

pi-next=pb;

elseif(pb-next==NULL)//尾部插入

pb-next=pi;

returnhead;

}

2、遍歷鏈表節(jié)點(diǎn)

voidprintf_link(STU*head)

//1、判斷鏈表是否存在

if(NULL==head)

printf("鏈表不存在\n");

return;

else//2、鏈表存在，逐個(gè)節(jié)點(diǎn)遍歷鏈表

STU*pb=head;

while(pb!=NULL)

printf("%d%s%f\n",pb-num,pb-name,pb-score);

//pb指向下一個(gè)節(jié)點(diǎn)

pb=pb-next;

return;

}

3、查詢指定節(jié)點(diǎn)

STU*search_link(STU*head,char*name)

//判斷鏈表是否存在

if(NULL==head)

printf("鏈表不存在\n");

returnNULL;

else//鏈表存在

//逐個(gè)節(jié)點(diǎn)查詢

STU*pb=head;

while((strcmp(pb-name,name)!=0)(pb-next!=NULL))

pb=pb-next;

if(strcmp(pb-name,name)==0)//找到

returnpb;

else

printf("未找到相關(guān)節(jié)點(diǎn)信息\n");

returnNULL;

returnNULL;

}

4、刪除指定節(jié)點(diǎn)

STU*delete_link(STU*head,char*name)

//判斷鏈表是否存在

if(NULL==head)

printf("鏈表不存在\n");

returnhead;

else

STU*pf=NULL,*pb=NULL;

pf=pb=head;

//尋找刪除點(diǎn)

while((strcmp(pb-name,name)!=0)(pb-next!=NULL))

pf=pb;

pb=pb-next;

//找到刪除點(diǎn)

if(strcmp(pb-name,name)==0)

if(head==pb)//頭部刪除

head=head-next;

else//中尾部刪除

pf-next=pb-next;

//釋放pb

if(pb!=NULL)

free(pb);

pb=NULL;

else//未找到刪除點(diǎn)

printf("未找到刪除的相關(guān)節(jié)點(diǎn)信息\n");

returnhead;

}

5、釋放鏈表

STU*free_link(STU*head)

//判斷鏈表是否存在

if(NULL==head)

printf("鏈表不存在\n");

returnhead;

else//鏈表存在

STU*pb=head;

while(pb!=NULL)

//head紀(jì)錄下一個(gè)節(jié)點(diǎn)的位置

head=head-next;

//釋放pb指向的節(jié)點(diǎn)

if(pb!=NULL)

free(pb);

pb=NULL;

//pb指向下一個(gè)節(jié)點(diǎn)

pb=head;

printf("鏈表節(jié)點(diǎn)已經(jīng)完全釋放\n");

returnhead;

}

6、鏈表的翻轉(zhuǎn)

STU*reverse_link(STU*head)

//判斷鏈表是否存在

if(NULL==head)

printf("鏈表不存在\n");

returnhead;

else

STU*pb=head-next;

STU*pn=NULL;

//將頭結(jié)點(diǎn)指針域指向NULL

head-next=NULL;

//逐個(gè)節(jié)點(diǎn)翻轉(zhuǎn)

while(pb!=NULL)

//pn紀(jì)錄pb-next的節(jié)點(diǎn)

pn=pb-next;

//進(jìn)行反向連接

pb-next=head;

//移動(dòng)head到pb上

head=pb;

//pb指向pb的節(jié)點(diǎn)

pb=pn;

returnhead;

}

7、鏈表的排序

//選擇法對(duì)鏈表排序

voidsort_link(STU*head)

//判斷鏈表是否存在

if(NULL==head)

printf("鏈表不存在\n");

return;

else

STU*p_i=head,*p_j=head;//inti=0,j=0;

while(p_i-next!=NULL)//for(i=0;ii++)

STU*p_min=p_i;//intmin=i;

p_j=p_min-next;//j=min+1

while(p_j!=NULL)//jn

if(p_min-nump_j-num)//if(arr[min]arr[j])

p_min=