鏈表課件-《C語言程序設(shè)計(jì)》同步教學(xué)

C語言程序設(shè)計(jì)

2023翻轉(zhuǎn)課堂實(shí)用教程10.4鏈表123鏈表的鏈?zhǔn)酱鎯︽湵淼墓?jié)點(diǎn)鏈表的組織形式鏈表的基本操作知識點(diǎn)鏈表案例分析案例分析鏈表相關(guān)練習(xí)題練習(xí)題前面章節(jié)中，學(xué)生會候選人、應(yīng)屆畢業(yè)生的信息采用什么方式存儲？若進(jìn)行刪除、插入的操作，會涉及到非常多移動的操作，降低了程序執(zhí)行的效率。C語言提供了一種采用動態(tài)存儲分配的構(gòu)造數(shù)據(jù)類型——鏈表，大大提高了程序解決此類問題的時(shí)間效率。10.4.1鏈表知識點(diǎn)結(jié)構(gòu)體數(shù)組的存儲方式優(yōu)點(diǎn)：便于對信息進(jìn)行查詢、修改、輸出操作。如何更好解決刪除、插入的問題？鏈條示意圖10.4.1鏈表知識點(diǎn)先看下鏈條：由多個金屬環(huán)串聯(lián)在一起的前一個金屬環(huán)扣住下一個金屬環(huán)。鏈表就是一種鏈?zhǔn)酱鎯Φ慕Y(jié)構(gòu)，由多個相同結(jié)構(gòu)體類型的節(jié)點(diǎn)串聯(lián)一起節(jié)點(diǎn)之間相互關(guān)聯(lián)鏈表分為單向鏈表和雙向鏈表，本節(jié)只講解單向鏈表。10.4.1鏈表知識點(diǎn)每個節(jié)點(diǎn)都是一個結(jié)構(gòu)體類型的變量，兩部分組成：①

節(jié)點(diǎn)本身的數(shù)據(jù)部分，稱為數(shù)據(jù)域；②

指向下一個節(jié)點(diǎn)的指針，稱為指針域。以保存29478490這4個數(shù)據(jù)為例。鏈表的組織形式——節(jié)點(diǎn)10.4.1鏈表知識點(diǎn)例如：定義structnode結(jié)構(gòu)體類型作為鏈表節(jié)點(diǎn)的類型名，定義如下：typedefstructnode{ intdata;//數(shù)據(jù)域的值 structnode*next;//指針域的值，next指向下一個鏈表節(jié)點(diǎn)}Node;typedef用法？next指針的類型？鏈表的組織形式——節(jié)點(diǎn)datanext10.4.1鏈表知識點(diǎn)（1）頭指針，鏈表一般使用頭指針head來表示，方便后續(xù)對鏈表的訪問和操作。（2）節(jié)點(diǎn)，節(jié)點(diǎn)分為第一個節(jié)點(diǎn)和其他節(jié)點(diǎn)。無頭節(jié)點(diǎn)的單向鏈表：帶頭節(jié)點(diǎn)的單向鏈表：涉及的概念：第一個節(jié)點(diǎn)，為頭結(jié)點(diǎn)。存儲第一個實(shí)際數(shù)據(jù)的節(jié)點(diǎn)，為首元節(jié)點(diǎn)。最后一個節(jié)點(diǎn)稱為尾節(jié)點(diǎn)，尾節(jié)點(diǎn)后續(xù)沒有節(jié)點(diǎn)，其指針域的值為NULL。鏈表包括頭指針和節(jié)點(diǎn)10.4.1鏈表知識點(diǎn)（1）malloc和free函數(shù)鏈表中的節(jié)點(diǎn)，邏輯上：連續(xù)的，

物理上：是隨機(jī)存放的。每個節(jié)點(diǎn)的內(nèi)存空間，通過動態(tài)存儲分配的。使用stdlib.h頭文件中函數(shù)。malloc：動態(tài)分配內(nèi)存空間free：釋放用malloc動態(tài)分配的內(nèi)存空間鏈表的基本操作10.4.1鏈表知識點(diǎn)（1）malloc和free函數(shù)malloc函數(shù)原型如下： void*malloc(unsignedintsize);在動態(tài)存儲區(qū)分配一個大小為size字節(jié)的連續(xù)空間。成功：返回分配好的存儲空間的首地址；失?。悍祷刂礜ULL 鏈表的基本操作舉例：double*pd=(double*)malloc(sizieof(double));1、增加程序可移植性2、強(qiáng)制轉(zhuǎn)化為需要的類型10.4.1鏈表知識點(diǎn)（1）malloc和free函數(shù)free函數(shù)原型如下： voidfree(void*p);釋放掉指針p指向的內(nèi)容空間。free函數(shù)要和malloc函數(shù)成對使用。

鏈表的基本操作舉例：structnode*curNode=(structnode*)malloc(sizieof(structnode));…free(curNode);maloc函數(shù)申請的空間，不會自動釋放。必須由free函數(shù)來釋放。10.4.1鏈表知識點(diǎn)（2）單向鏈表的新建

鏈表的基本操作創(chuàng)建單鏈表，保存29478490這4個數(shù)據(jù)。頭結(jié)點(diǎn)headrear29首元結(jié)點(diǎn)curNoderear->next47rear->next10.4.1鏈表知識點(diǎn)//生成含頭節(jié)點(diǎn)的單向鏈表for(i=0;i<N;i++){//創(chuàng)建新節(jié)點(diǎn)curNode，為其動態(tài)分配存儲空間Node*curNode=(Node*)malloc(sizeof(structnode));curNode->data=array[i];//此時(shí)rear指向當(dāng)前鏈表的尾節(jié)點(diǎn)rear->next=curNode;//將新節(jié)點(diǎn)curNode加入到鏈表中//curNode成為了新的尾節(jié)點(diǎn)，更新rear指向curNoderear=curNode;}rear->next=NULL;returnhead;//將頭指針返回}typedefstructnode{ intdata;//存儲數(shù)據(jù)域的值 structnode*next;//存儲指針域的值，next指向下一個鏈表節(jié)點(diǎn)}Node;#defineN4Node*initLink(){inti=0;intarray[N]={29,47,84,90};//創(chuàng)建頭結(jié)點(diǎn)Node*head=(Node*)malloc(sizeof(structnode));//聲明一個rear指針，指向鏈表的尾節(jié)點(diǎn) Node*rear=head;（2）單向鏈表的新建，代碼段

10.4.1鏈表知識點(diǎn)（3）判斷單向鏈表是否為空帶頭結(jié)點(diǎn)單向鏈表只有頭節(jié)點(diǎn)，沒有后續(xù)節(jié)點(diǎn)時(shí)，被認(rèn)為單向鏈表為空

intemptyLink(Node*head){ return(head->next==NULL);}鏈表的基本操作NULLheaddatanext頭結(jié)點(diǎn)10.4.1鏈表知識點(diǎn)（4）單項(xiàng)鏈表的插入兩個節(jié)點(diǎn)A和B間插入一個新節(jié)點(diǎn)C時(shí)，讓C與A和B分別建立邏輯聯(lián)系。

步驟如下：將C節(jié)點(diǎn)的next指針指向B節(jié)點(diǎn)將A節(jié)點(diǎn)的next指針指向C節(jié)點(diǎn)鏈表的基本操作head8429A結(jié)點(diǎn)9047頭結(jié)點(diǎn)B結(jié)點(diǎn)35C結(jié)點(diǎn)第一步第二步節(jié)點(diǎn)間是如何建立邏輯聯(lián)系？通過前節(jié)點(diǎn)next指針指向下一個節(jié)點(diǎn)，建立邏輯聯(lián)系NULL10.4.1鏈表知識點(diǎn)//在第position個位置處插入數(shù)據(jù)newData,position從1開始計(jì)數(shù)Node*insertLink(Node*head,intnewData,intposition){ //因?yàn)椴迦霐?shù)據(jù)時(shí)，需要知道插入位置的前一個節(jié)點(diǎn)，定義p為前一個節(jié)點(diǎn)指針

Node*p=head,*newNode; inti=1; //先找到插入位置的前一個節(jié)點(diǎn)

while(i<position){ p=p->next;if(p==NULL){printf("插入位置無效\n");returnhead;}i++; } //找到插入位置，此時(shí)p為插入位置的前一個節(jié)點(diǎn)

newNode=(Node*)malloc(sizeof(structnode)); newNode->data=newData; newNode->next=p->next; p->next=newNode; returnhead;}（4）單向鏈表的插入，代碼段

頭節(jié)點(diǎn)的存在，不管新插入的節(jié)點(diǎn)，是在首元節(jié)點(diǎn)前、還是中間的位置，還是在尾節(jié)點(diǎn)后，操作步驟都是一樣的。10.4.1鏈表知識點(diǎn)（5）單項(xiàng)鏈表的遍歷從鏈表頭開始，依次訪問單向鏈表中的每個節(jié)點(diǎn)，并將節(jié)點(diǎn)的數(shù)據(jù)值輸出，直到鏈表尾。鏈表的基本操作head84299047NULLp

voiddisplayLink(Node*head){ Node*p=head->next;//p指向首元節(jié)點(diǎn) while(p!=NULL){//當(dāng)p不為空，則沒有到達(dá)鏈表尾 printf("%d",p->data); p=p->next; } printf("\n");}10.4.1鏈表知識點(diǎn)（6）單項(xiàng)鏈表的刪除假設(shè)其前驅(qū)節(jié)點(diǎn)為A節(jié)點(diǎn)，則對C節(jié)點(diǎn)的刪除，需要三步操作步驟：①遍歷單向鏈表，找到需要刪除的節(jié)點(diǎn)C，并記錄前驅(qū)節(jié)點(diǎn)A。②A節(jié)點(diǎn)的next指針指向C節(jié)點(diǎn)的next指針③刪除C節(jié)點(diǎn)鏈表的基本操作head8429A結(jié)點(diǎn)9047頭結(jié)點(diǎn)35C結(jié)點(diǎn)第一步第二步NULL第②、③步能顛倒嗎？第三步不能！10.4.1鏈表知識點(diǎn)//刪除鏈表中數(shù)據(jù)值為delData的節(jié)點(diǎn)。voiddelNode(Node*head,intdelData){ Node*p=head,*curNode=head->next;//curNode指向首元節(jié)點(diǎn)

while(curNode!=NULL){ if(delData==curNode->data){//此時(shí)p指向A節(jié)點(diǎn)，curNode指向C節(jié)點(diǎn) p->next=curNode->next; free(curNode); curNode=p->next; }else{ p=curNode; curNode=p->next; } }}（6）單向鏈表的刪除，代碼段

10.4.1鏈表知識點(diǎn)（7）單向鏈表的查找遍歷單向鏈表的過程中，比較某個節(jié)點(diǎn)的值是否和被查找數(shù)據(jù)一致，直到找到或者遍歷到鏈表尾（某個節(jié)點(diǎn)NULL）結(jié)束。鏈表的基本操作//在鏈表中查找數(shù)據(jù)值為needData的節(jié)點(diǎn)，找到了則返回該節(jié)點(diǎn)的地址，否則返回NULLNode*searchNode(Node*head,intneedData){ Node*p=head,*curNode=head->next;//p指向首元節(jié)點(diǎn)

while(curNode!=NULL){ if(needData==curNode->data){ returncurNode; } p=curNode; curNode=p->next; } returnNULL;}10.4.1鏈表知識點(diǎn)（8）單向鏈表的修改鏈表的基本操作/*在鏈表中查找數(shù)據(jù)值為oldData的節(jié)點(diǎn)，找到后修改成newData，找到了則返回該節(jié)點(diǎn)的地址，否則返回NULL*/Node*modifyNode(Node*head,intoldData,intnewData){ Node*p=head,*curNode=head->next; while(curNode!=NULL){ if(oldData==curNode->data){ curNode->data=newData; returncurNode; } p=curNode; curNode=p->next; } returnNULL;}10.4.1鏈表案例分析案例10.4.1用鏈表結(jié)構(gòu)來存儲候選人信息，根據(jù)學(xué)號查看某個候選人的信息，再修改指定候選人的票數(shù)。要求：輸入候選人的信息，包括學(xué)號、姓名、班級、得票數(shù)，直到輸入一個-1結(jié)束輸入。再輸入一個候選人學(xué)號，編寫函數(shù)，查詢該候選人的信息，發(fā)現(xiàn)