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

C語言程序設(shè)計

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

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

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

物理上：是隨機存放的。每個節(jié)點的內(nèi)存空間，通過動態(tài)存儲分配的。使用stdlib.h頭文件中函數(shù)。malloc：動態(tài)分配內(nèi)存空間free：釋放用malloc動態(tài)分配的內(nèi)存空間鏈表的基本操作10.4.1鏈表知識點（1）malloc和free函數(shù)malloc函數(shù)原型如下： void*malloc(unsignedintsize);在動態(tài)存儲區(qū)分配一個大小為size字節(jié)的連續(xù)空間。成功：返回分配好的存儲空間的首地址；失敗：返回值NULL 鏈表的基本操作舉例：double*pd=(double*)malloc(sizieof(double));1、增加程序可移植性2、強制轉(zhuǎn)化為需要的類型10.4.1鏈表知識點（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鏈表知識點（2）單向鏈表的新建

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

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

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

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

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

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

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

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

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

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

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

while(curNode!=NULL){ if(needData==curNode->data){ returncurNode; } p=curNode; curNode=p->next; } returnNULL;}10.4.1鏈表知識點（8）單向鏈表的修改鏈表的基本操作/*在鏈表中查找數(shù)據(jù)值為oldData的節(jié)點，找到后修改成newData，找到了則返回該節(jié)點的地址，否則返回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)