計(jì)導(dǎo)課件-14 chap12鏈表

1第12章鏈表212.2自引用結(jié)構(gòu)12.4鏈表

12.4.1鏈表結(jié)構(gòu)

12.4.2鏈表的創(chuàng)建、結(jié)點(diǎn)的插入和刪除

12.4.3鏈表基本操作提綱3

自引用結(jié)構(gòu)包含一個(gè)指針成員，該指針指向與自身同一個(gè)類型的結(jié)構(gòu)。如：

structnode{ intdata; structnode*nextPtr;}；

structnode就是自引用結(jié)構(gòu)。nextPtr稱為鏈節(jié)（link），用于把一個(gè)structnode類型的結(jié)構(gòu)變量和另一個(gè)同類型的結(jié)構(gòu)變量鏈在一起。structnoden1，n2；n1.nextPtr=&n2;n1n2自引用結(jié)構(gòu)412.2自引用結(jié)構(gòu)12.4鏈表

12.4.1鏈表結(jié)構(gòu)

12.4.2鏈表中結(jié)點(diǎn)的訪問

12.4.3鏈表基本操作提綱512.4.1鏈表結(jié)構(gòu)問題的引出1號(hào)書206301號(hào)抽屜2號(hào)書403206號(hào)抽屜3號(hào)書403號(hào)抽屜301抽屜向管理員申請(qǐng)三個(gè)抽屜放三本書，分配的抽屜號(hào)是不連續(xù)的.看書順序:必須要先看1號(hào)書,再看2號(hào)書,再看3號(hào)書.問題：怎么能依次拿到這三本書？612.4.1鏈表結(jié)構(gòu)解決方案：把第一本書所在抽屜號(hào)記錄在一張紙上；把第二本書所在抽屜號(hào)記錄在一張紙，放到第一本書所在抽屜里；把第三本書所在抽屜號(hào)記錄在一張紙，放到第二本書所在抽屜里；712.4.1鏈表結(jié)構(gòu)一個(gè)類比：如果有多個(gè)學(xué)生記錄需要存放到內(nèi)存，而存放記錄的內(nèi)存通常是不連續(xù)的，如何能訪問到這些記錄？812.4.1鏈表結(jié)構(gòu)structstudent{/*學(xué)生信息結(jié)構(gòu)類型*/charno[7];/*學(xué)號(hào)*/charname[9];/*姓名*/};main(){charno[7];structstudent*ptr;

printf("請(qǐng)輸入學(xué)生學(xué)號(hào)");gets(no);//讀入學(xué)號(hào)

while(strcmp(no,"0000")!=0){ptr=malloc(sizeof(structstudent));strcpy(ptr->no,no);//學(xué)號(hào)復(fù)制到內(nèi)存中

printf("請(qǐng)輸入學(xué)生姓名");gets(ptr->name);//讀取姓名到內(nèi)存中

printf("請(qǐng)輸入學(xué)生學(xué)號(hào)");gets(no);}...}讀入若干個(gè)學(xué)生的信息并進(jìn)行處理。由于學(xué)生個(gè)數(shù)未知，因此用動(dòng)態(tài)分配的內(nèi)存來(lái)存放學(xué)生信息，代碼如左所示。存在問題：由于是動(dòng)態(tài)分配內(nèi)存來(lái)存放學(xué)生信息，因此存放每個(gè)學(xué)生信息的內(nèi)存通常是不連續(xù)的，如何能訪問到這些學(xué)生信息？912.4.1鏈表結(jié)構(gòu)類比書－－－學(xué)生信息抽屜－－－存放學(xué)生信息的內(nèi)存記錄第一本書所在抽屜號(hào)的紙張－－－指針記錄下一本書所在抽屜號(hào)的紙張－－－結(jié)構(gòu)變量里的指針成員1012.4.1鏈表結(jié)構(gòu)學(xué)生信息10022FF8A學(xué)生信息20023FF80學(xué)生信息30022FF7C0022FF7C0022FF8A0023FF80動(dòng)態(tài)申請(qǐng)3個(gè)結(jié)構(gòu)變量存儲(chǔ)3個(gè)學(xué)生的信息，3個(gè)結(jié)構(gòu)變量通過指針“鏈”在了一起，具有前驅(qū)和后繼關(guān)系。第一個(gè)結(jié)構(gòu)變量的地址單獨(dú)記錄在一個(gè)指針里。11171947…h(huán)eadPtr鏈表是用鏈節(jié)指針鏈在一起的自引用結(jié)構(gòu)變量（稱為結(jié)點(diǎn)）的線性集合，是線性表的一種存儲(chǔ)結(jié)構(gòu)。（1）headPtr──指向鏈表首結(jié)點(diǎn)的指針變量。（2）每個(gè)結(jié)點(diǎn)由2個(gè)域組成：數(shù)據(jù)域──存儲(chǔ)結(jié)點(diǎn)本身的信息。指針域──存儲(chǔ)指向后繼結(jié)點(diǎn)的指針。（3）尾結(jié)點(diǎn)的指針域置為NULL(用反斜杠表示)，作為鏈表結(jié)束的標(biāo)志。12.4.1鏈表結(jié)構(gòu)1212.4.1鏈表結(jié)構(gòu)鏈表的特點(diǎn)：鏈表是一種存儲(chǔ)結(jié)構(gòu)，用于存放線性表；鏈表的結(jié)點(diǎn)是根據(jù)需要調(diào)用動(dòng)態(tài)內(nèi)存分配函數(shù)進(jìn)行分配的，因此鏈表可隨需要伸長(zhǎng)縮短，在要存儲(chǔ)的數(shù)據(jù)個(gè)數(shù)未知的情況下節(jié)省內(nèi)存；鏈表的結(jié)點(diǎn)在邏輯上是連續(xù)的，但是各結(jié)點(diǎn)的內(nèi)存通常是不連續(xù)的，因此不能立即被訪問到，只能從頭結(jié)點(diǎn)開始逐結(jié)點(diǎn)訪問。171947…h(huán)eadPtr1312.2自引用結(jié)構(gòu)12.4鏈表

12.4.1鏈表結(jié)構(gòu)

12.4.2鏈表的創(chuàng)建、結(jié)點(diǎn)的插入和刪除

12.4.3鏈表基本操作提綱141.鏈表的創(chuàng)建從無(wú)到有，結(jié)點(diǎn)逐個(gè)創(chuàng)建、加入，構(gòu)成鏈表171947headPtr鏈表中的結(jié)點(diǎn)內(nèi)存是動(dòng)態(tài)分配的:newPtr=malloc(sizeof(structnode))；newPtr->data=10;鏈表結(jié)點(diǎn)的動(dòng)態(tài)分配決定了結(jié)點(diǎn)在內(nèi)存的位置不一定是連續(xù)的！152.鏈表中結(jié)點(diǎn)的訪問如何訪問鏈表中的結(jié)點(diǎn)：由于鏈表中結(jié)點(diǎn)的內(nèi)存是動(dòng)態(tài)分配的，無(wú)法通過名稱去訪問，因此只能通過結(jié)點(diǎn)的地址去訪問。某結(jié)點(diǎn)的地址記錄在其前驅(qū)結(jié)點(diǎn)的地址域里，因此要想訪問第n個(gè)結(jié)點(diǎn)，必須先得訪問第n-1個(gè)結(jié)點(diǎn)，讀取該結(jié)點(diǎn)的地址域；而要想訪問第n-1個(gè)結(jié)點(diǎn)，必須先得訪問第n-2個(gè)結(jié)點(diǎn)；以此類推，一直推到訪問第1個(gè)結(jié)點(diǎn)。而第1個(gè)結(jié)點(diǎn)是由指針headPtr指向的，因此能訪問第1個(gè)結(jié)點(diǎn)，從而也就能訪問第2個(gè)結(jié)點(diǎn)，第3個(gè)結(jié)點(diǎn)……16訪問頭結(jié)點(diǎn)：printf(“%d”，headPtr->data);訪問第二個(gè)結(jié)點(diǎn)：currentPtr=headPtr->nextPtr; printf(“%d”,currentPtr->data);訪問第三個(gè)結(jié)點(diǎn)：currentPtr=currentPtr->nextPtr;

printf(“%d”,currentPtr->data); 171947…h(huán)eadPtr2.鏈表中結(jié)點(diǎn)的訪問currentPtr37只要知道指向鏈表頭結(jié)點(diǎn)的指針變量headPtr，就可以從頭結(jié)點(diǎn)開始依次訪問各個(gè)結(jié)點(diǎn)。這樣借助于currentPtr“順藤摸瓜”，就能逐個(gè)訪問鏈表中的結(jié)點(diǎn)。可見鏈表結(jié)點(diǎn)不能立即被訪問到。173.鏈表結(jié)點(diǎn)的動(dòng)態(tài)增加和刪除171947headPtr27

newPtr171947headPtr9鏈表中結(jié)點(diǎn)的插入和刪除不需要移動(dòng)其他結(jié)點(diǎn)，比較方便插入刪除18鏈表和數(shù)組存儲(chǔ)線性表的比較數(shù)組的優(yōu)點(diǎn)：數(shù)組中的元素在內(nèi)存中是連續(xù)存放的，能根據(jù)數(shù)組的首地址計(jì)算出各數(shù)組元素的內(nèi)存地址，所以可以直接用下標(biāo)訪問到數(shù)組元素；而鏈表中的元素在內(nèi)存中通常是不連續(xù)存放的，因此不能被立即訪問到。鏈表的優(yōu)點(diǎn)：1、可伸縮性：數(shù)組一旦在內(nèi)存分配空間之后，大小就不能改變；而鏈表是動(dòng)態(tài)的，在需要的時(shí)候可以增加或刪減結(jié)點(diǎn)；數(shù)組的空間可能很快就用完，而鏈表只有在系統(tǒng)沒有足夠的內(nèi)存滿足動(dòng)態(tài)分配存儲(chǔ)空間的請(qǐng)求時(shí)才會(huì)達(dá)到全滿的狀態(tài)；2、插入和刪除操作：數(shù)組的插入和刪除涉及到移動(dòng)元素的操作，因此比較費(fèi)時(shí)；而鏈表的插入和刪除比較簡(jiǎn)單；1912.2自引用結(jié)構(gòu)12.4鏈表

12.4.1鏈表結(jié)構(gòu)

12.4.2鏈表的創(chuàng)建、結(jié)點(diǎn)的插入和刪除

12.4.3鏈表基本操作提綱20對(duì)鏈表的基本操作有：創(chuàng)建鏈表、檢索（查找）結(jié)點(diǎn)、插入、刪除結(jié)點(diǎn)和修改結(jié)點(diǎn)等。（1）創(chuàng)建鏈表是指：從無(wú)到有地建立起一個(gè)鏈表，即往空鏈表中依次插入若干結(jié)點(diǎn)，并保持結(jié)點(diǎn)之間的前驅(qū)和后繼關(guān)系。（2）檢索操作是指：按給定的結(jié)點(diǎn)索引號(hào)或檢索條件，查找某個(gè)結(jié)點(diǎn)。（3）插入操作是指：在結(jié)點(diǎn)ki-1與ki之間插入一個(gè)新的結(jié)點(diǎn)k。（4）刪除操作是指：刪除結(jié)點(diǎn)ki，使線性表的長(zhǎng)度減1。12.4.3鏈表基本操作2112.4.3鏈表基本操作typedefstructlistNode

LISTNODE;typedefLISTNODE*

LISTNODEPTR;/*LISTNODEPTR：指向LISTNODE指針*/171947…h(huán)eadPtrLISTNODE類型LISTNODEPTR類型structlistNode{ intdata; structlistNode*nextPtr;};22171947…h(huán)eadPtr例1、讀入一批數(shù)，以-1結(jié)束。將輸入的數(shù)據(jù)組成先進(jìn)先出的鏈表并輸出，最后釋放鏈表。要求：設(shè)計(jì)一個(gè)函數(shù)LISTNODEPTRcreateFIFOList()；函數(shù)功能：讀入一批數(shù)（以－1結(jié)束），將輸入的數(shù)組成 先進(jìn)先出的鏈表，并返回指向鏈表頭結(jié)點(diǎn)的 指針。基本操作1－創(chuàng)建鏈表依次讀入17、19、…、47之后創(chuàng)建的鏈表23171947headPtr假設(shè)輸入的數(shù)據(jù)為{17,19,47,-1}，則數(shù)據(jù)組織成先進(jìn)先出鏈表的過程：基本操作1－創(chuàng)建鏈表讀取一個(gè)數(shù)后：動(dòng)態(tài)申請(qǐng)結(jié)點(diǎn)內(nèi)存，存放數(shù)據(jù)；如果新增結(jié)點(diǎn)是頭接點(diǎn)，則令headPtr指向該結(jié)點(diǎn)；如果新增不是頭接點(diǎn)，則將該結(jié)點(diǎn)追加到鏈表尾結(jié)點(diǎn)后面；如果新增結(jié)點(diǎn)是尾結(jié)點(diǎn)，則鏈節(jié)指針賦值為NULL。24基本操作1－創(chuàng)建鏈表LISTNODE*createFIFOList(){//變量定義；

//變量初始化；

scanf(“%d”,&num);while(num!=-1){currentPtr=malloc(sizeof(LISTNODE));if(currentPtr!=NULL){currentPtr->data=num;//將新結(jié)點(diǎn)插入鏈表；

} scanf(“%d”,&num);}

returnheadPtr；}251747headPtrcurrentPtr37lastPtr若創(chuàng)建的是頭結(jié)點(diǎn)，則由headPtr指向；否則，新增的結(jié)點(diǎn)追加到鏈表尾結(jié)點(diǎn)后面；為了讓新增結(jié)點(diǎn)能方便地追加到鏈表尾結(jié)點(diǎn)后面，需要設(shè)計(jì)一個(gè)指針lastPtr來(lái)指向鏈表尾結(jié)點(diǎn)；追加過程為：lastPtr->nextPtr=currentPtr;

修正lastPtr，使之指向鏈表尾結(jié)點(diǎn)：lastPtr=currentPtr；1914currentPtr26LISTNODE*createFIFOList1(){ intnum; LISTNODEPTRheadPtr=NULL,lastPtr=NULL,currentPtr=NULL; printf("inputpositivenumbers,-1toend\n"); scanf("%d",&num); while(num!=-1){ currentPtr=malloc(sizeof(LISTNODE));/*分配結(jié)點(diǎn)內(nèi)存*/ if(currentPtr!=NULL){/*插入結(jié)點(diǎn)*/ currentPtr->data=num;

if(headPtr==NULL){/*若currentPtr是頭結(jié)點(diǎn)*/ headPtr=currentPtr;lastPtr=currentPtr;} else{ lastPtr->nextPtr=currentPtr;/*將結(jié)點(diǎn)連上鏈表尾結(jié)點(diǎn)*/ lastPtr=currentPtr;/*使lastPtr指向當(dāng)前鏈表的最后一個(gè)結(jié)點(diǎn)*/}}scanf("%d",&num); } lastPtr->nextPtr=NULL;/*設(shè)置鏈表結(jié)束標(biāo)記*/ returnheadPtr;}【源程序】27main(){LISTNODEPTRheadPtr=NULL；

createFIFOList2(&headPtr);/*創(chuàng)建鏈表，鏈表頭結(jié)點(diǎn) 地址寫入headPtr中*/}voidcreateFIFOList2(LISTNODEPTR*sPtr){……}鏈表頭結(jié)點(diǎn)不通過返回值返回：171947headPtrmain函數(shù)創(chuàng)建鏈表函數(shù)sPtrif(*sPtr==NULL){/*若是頭結(jié)點(diǎn)*/

*sPtr=currentPtr;

lastPtr=currentPtr;}else{。。。}28基本操作1－創(chuàng)建鏈表總結(jié)：當(dāng)定義一個(gè)對(duì)鏈表進(jìn)行處理的函數(shù)時(shí)，如果在該函數(shù)中可能會(huì)修改鏈表的頭結(jié)點(diǎn)，則往往可以在函數(shù)中設(shè)置一個(gè)參數(shù)sPtr，用于接收指向鏈表頭結(jié)點(diǎn)的指針headPtr地址。在函數(shù)中通過*sPtr來(lái)間接訪問headPtr，修改headPtr的值。sPtr171947headPtrvoidchainOp(LISTNODEPTR*sPtr)

函數(shù)調(diào)用：chainOp(&headPtr)main函數(shù)chainOP函數(shù)29基本操作1－創(chuàng)建鏈表練習(xí)：讀入一批整數(shù){17,19,47,-1}

，以負(fù)數(shù)結(jié)束。將輸入的數(shù)據(jù)組成先進(jìn)后出的鏈表。471917headPtr30LISTNODEPTRcreateFILOList(){intnum;LISTNODEPTRheadPtr=NULL,currentPtr=NULL;printf("inputthenumbers,-1toend\n");scanf("%d",&num);while(num!=-1){currentPtr=malloc(sizeof(LISTNODE));if(currentPtr!=NULL){currentPtr->data=num;

if(headPtr==NULL){//創(chuàng)建的是第一個(gè)結(jié)點(diǎn)

headPtr=currentPtr;headPtr->nextPtr=NULL;}else{currentPtr->nextPtr=headPtr;//鏈接

headPtr=currentPtr;}}scanf("%d",&num);}returnheadPtr;}31voidcreateFILOList(LISTNODEPTR*sPtr{ intnum; LISTNODEPTRcurrentPtr=NULL; printf("inputpositivenumbers,-1toend\n"); scanf("%d",&num); while(num!=-1){ currentPtr=malloc(sizeof(LISTNODE)); if(currentPtr!=NULL){ currentPtr->data=num; if(*sPtr==NULL){/*若currentPtr是第一個(gè)結(jié)點(diǎn)*/ currentPtr->nextPtr=NULL;*sPtr=currentPtr; } else{ currentPtr->nextPtr=*sPtr; *sPtr=currentPtr;}}scanf("%d",&num);}}32171947…h(huán)eadPtrcurrentPtr37函數(shù)設(shè)計(jì)考慮：要想訪問鏈表，只需知道鏈表頭結(jié)點(diǎn)的地址，就可以“順藤摸瓜”，依次訪問各個(gè)結(jié)點(diǎn)。函數(shù)接口設(shè)計(jì)：voidprintList(LISTNODEPTRcurrentPtr)currentPtr用于接收鏈表頭結(jié)點(diǎn)地址。函數(shù)調(diào)用：printList(headPtr)基本操作2－遍歷鏈表（打?。?3171947…h(huán)eadPtrcurrentPtr37函數(shù)接口設(shè)計(jì)：voidprintList(LISTNODEPTRcurrentPtr)鏈表結(jié)點(diǎn)的訪問：通過currentPtr依次訪問鏈表各結(jié)點(diǎn)。訪問完當(dāng)前指向的結(jié)點(diǎn)后，讓currentPtr指向下一個(gè)結(jié)點(diǎn)： currentPtr=currentPtr->nextPtr基本操作2－遍歷鏈表（打?。?4基本操作2－遍歷鏈表（打?。﹚hile(？){ printf(“%d-->",currentPtr->data);currentPtr=currentPtr->nextPtr;/*指向下一結(jié)點(diǎn)*/}171947…h(huán)eadPtrcurrentPtr37currentPtr!=NULL35voidprintList(LISTNODEPTRcurrentPtr){if(currentPtr==NULL) printf("thelistisempty\n");else{ printf("thelistis:\n"); while(currentPtr!=NULL){ printf(“%d-->",currentPtr->data);currentPtr=currentPtr->nextPtr;}printf("NULL\n\n");}}基本操作2－遍歷鏈表（打?。?71947headPtrcurrentPtrmain(){LISTNODEPTRheadPtr；

headPtr=createFIFOList1();

printList(headPtr)；}36函數(shù)設(shè)計(jì)考慮：要釋放鏈表各個(gè)結(jié)點(diǎn)，只需要知道鏈表頭結(jié)點(diǎn)地址，就可以“順藤摸瓜”，依次釋放各個(gè)結(jié)點(diǎn)。函數(shù)接口設(shè)計(jì)：

voiddestroyList(LISTNODEPTRheadPtr)

參數(shù)headPtr用于接收鏈表頭結(jié)點(diǎn)地址基本操作2－遍歷鏈表（釋放鏈表）37171947headPtrheadPtrtempPtr思考：若用語(yǔ)句free(headPtr)來(lái)釋放鏈表頭結(jié)點(diǎn)，會(huì)有什么后果？后果：第二個(gè)結(jié)點(diǎn)的地址也就丟失了，從而無(wú)法釋放后續(xù)結(jié)點(diǎn)！解決方法：設(shè)置指針變量tempPtr。要釋放headPtr指向的結(jié)點(diǎn)之前，先將headPtr值賦給tempPtr，然后headPtr指向下一結(jié)點(diǎn)，然后執(zhí)行free(tempPtr)基本操作2－遍歷鏈表（釋放鏈表）38基本操作2－遍歷鏈表（釋放鏈表）while(？){tempPtr=headPtr;headPtr=headPtr->nextPtr;/*headPtr指向下一個(gè)要 刪除的結(jié)點(diǎn)*/free(tempPtr);/*釋放當(dāng)前結(jié)點(diǎn)*/}171947headPtrtempPtrheadPtr!=NULL39voiddestroyList(LISTNODEPTRheadPtr){LISTNODEPTRtempPtr;while(headPtr!=NULL){tempPtr=headPtr;headPtr=headPtr->nextPtr;/*headPtr指向下一個(gè)要 刪除的結(jié)點(diǎn)*/free(tempPtr);}}main(){LISTNODEPTRheadPtr；

headPtr=createFIFOList1();printList(headPtr)；

destroy(headPtr);headPtr=NULL;}基本操作2－遍歷鏈表（釋放鏈表）40基本操作3－鏈表結(jié)點(diǎn)的檢索171947headPtrcurrentPtr9LISTNODEPTRfind(LISTNODEPTRcurrentPtr,intvalue){while(currentPtr!=NULL&¤tPtr->data!=value)currentPtr=currentPtr->nextPtr;

returncurrentPtr；}41基本操作3－鏈表結(jié)點(diǎn)的檢索鏈表結(jié)點(diǎn)檢索固有思路：當(dāng)currentPtr指向結(jié)點(diǎn)不滿足條件，就繼續(xù)查找LISTNODEPTRfind(LISTNODEPTRcurrentPtr,……){while(currentPtr!=NULL&¤tPtr->data不滿足條件)currentPtr=currentPtr->nextPtr;

returncurrentPtr；}42例2、定義一個(gè)函數(shù)，將一個(gè)正數(shù)插入到升序排列的鏈表中，要求插入后的鏈表還是升序的。

voidinsert(LISTNODEPTR*sPtr,intvalue);/*sPtr用于接收鏈表頭結(jié)點(diǎn)的地址，value是插入結(jié)點(diǎn)的值*/

函數(shù)調(diào)用：insert(&headPtr,num);基本操作4－鏈表結(jié)點(diǎn)的插入43voidinsert(LISTNODEPTR*sPtr,intvalue){/*為新結(jié)點(diǎn)申請(qǐng)內(nèi)存空間*/newPtr=(LISTNODEPTR)malloc(sizeof(LISTNODE));if(newPtr!=NULL)/*分配成功*/{ newPtr->data=value;newPtr->nextPtr=NULL;

確定新結(jié)點(diǎn)的插入位置;

插入新結(jié)點(diǎn)；

}}基本操作4－鏈表結(jié)點(diǎn)的插入44171947headPtr

sPtrpreviousPtrcurrentPtr27

newPtr要將newPtr指向結(jié)點(diǎn)插入currentPtr指向結(jié)點(diǎn)前，還必須能訪問到currentPtr指向結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。插入操作：previousPtr->nextPtr=newPtr; newPtr->nextPtr=currentPtr;因此，確定新結(jié)點(diǎn)的插入位置就是要確定previousPtr和currentPtr的值。45171947headPtrsPtr/*尋找新結(jié)點(diǎn)插入位置，新結(jié)點(diǎn)將插在*previousPtr和*currentPtr之間*/

previousPtr=NULL;currentPtr=*sPtr;/*currentPtr指向鏈表頭結(jié)點(diǎn)*/ while(currentPtr!=NULL&¤tPtr->data<value){/*若找到一個(gè)值比value大的結(jié)點(diǎn)或者找到最后還沒找著則跳出循環(huán)*/previousPtr=currentPtr;currentPtr=currentPtr->nextPtr;}27

newPtrpreviousPtrcurrentPtr這兩條件不能調(diào)換順序！46171947headPtrsPtrcurrentPtrpreviousPtr10

newPtr查找結(jié)果1：新結(jié)點(diǎn)插在鏈表頭結(jié)點(diǎn)前面previousPtr=NULL;currentPtr=*sPtr;while(currentPtr!=NULL&¤tPtr->data<value){}新結(jié)點(diǎn)插在鏈表頭結(jié)點(diǎn)前面:if(currentPtr==*sPtr)或者if(previousPtr==NULL)47171947headPtrsPtr/*若插在最前面*/if(currentPtr==*sPtr){/*若插在最前面*/newPtr->nextPtr=currentPtr; *sPtr=newPtr;/*修改headPtr*/}previousPtrcurrentPtr10

newPtr48171947headPtrsPtr60

newPtr查找結(jié)果2：新結(jié)點(diǎn)插在鏈表尾結(jié)點(diǎn)后面previousPtr=NULL;currentPtr=*sPtr;while(currentPtr!=NULL&¤tPtr->data<value){previousPtr=currentPtr;currentPtr=currentPtr->nextPtr;}新結(jié)點(diǎn)插在鏈表尾結(jié)點(diǎn)后面:

if(currentPtr==NULL)或者if(previousPtr->nextPtr==NULL)currentPtrpreviousPtr49171947headPtrsPtrif(previousPtr==NULL)/*若插在最前面*/……elseif(currentPtr==NULL){/*若插在最后面*/previousPtr->nextPtr=newPtr;newPtr->nextPtr=NULL;//注意不要遺漏本語(yǔ)句}currentPtrpreviousPtr60

newPtr插入新結(jié)點(diǎn):50171947headPtrsPtr20

newPtr查找結(jié)果3：新結(jié)點(diǎn)插在鏈表中間previousPtr=NULL;currentPtr=*sPtr;while(currentPtr!=NULL&¤tPtr->data<value){previousPtr=currentPtr;currentPtr=currentPtr->nextPtr;}previousPtrcurrentPtr新結(jié)點(diǎn)插在鏈表中間:if(previousPtr!=NULL&¤tPtr!=NULL)51/*若插在中間*/if(previousPtr==NULL)/*若插在最前面*/……elseif(currentPtr==NULL)/*若插在最后面*/……else{/*若插在中間*/previousPtr->nextPtr=newPtr;newPtr->nextPtr=currentPtr; }171947headPtrpreviousPtrcurrentPtr27

newPtrsPtr52voidinsertNode(LISTNODEPTR*sPtr,intvalue){ LISTNODEPTRnewPtr,previousPtr,currentPtr; newPtr=malloc(sizeof(LISTNODE)); if(newPtr!=NULL){ newPtr->data=value;/*查找插入位置，結(jié)點(diǎn)將插在*previousPtr和*currentPtr之間*/ previousPtr=NULL; currentPtr=*sPtr;/*currentPtr指向鏈表頭結(jié)點(diǎn)*/ while(currentPtr!=NULL&&value>currentPtr->data){ previousPtr=currentPtr; currentPtr=currentPtr->nextPtr;}

基本操作4－鏈表結(jié)點(diǎn)的插入53/*插入新結(jié)點(diǎn)*/ if(previousPtr==NULL){/*若插在最前面*/newPtr->nextPtr=currentPtr; *sPtr=newPtr;}elseif(currentPtr==NULL){/*若插在最后面*/ previousPtr->nextPtr=newPtr; newPtr->nextPtr=NULL;}else{/*若插在中間*/previousPtr->nextPtr=newPtr; newPtr->nextPtr=currentPtr; }}}基本操作4－鏈表結(jié)點(diǎn)的插入54例3：創(chuàng)建一個(gè)函數(shù)：

LISTNODEPTRcreateSortList()

功能：讀入一批數(shù)，以負(fù)數(shù)結(jié)束。將輸入的數(shù)據(jù)組成升序排序的有序鏈表并返回鏈表表頭結(jié)點(diǎn)指針。創(chuàng)建有序鏈表1/355/*讀取正整數(shù)，以－1結(jié)束，組成升序鏈表，返回指向鏈表頭結(jié)點(diǎn)的指針*/LISTNODEPTRcreateSortList(){intnum;LISTNODEPTRheadPtr=NULL; printf("inputpositivenumbers,-1toend\n"); scanf("%d",&num); while(num!=-1){ insertNode(&headPtr,num);/*插入結(jié)點(diǎn)*/ scanf("%d",&num); }returnheadPtr;}創(chuàng)建有序鏈表2/356main(){ LISTNODEPTRheadPtr=NULL;

headPtr=createSortList();/*創(chuàng)建有序鏈表*/ printList(headPtr);/*輸出鏈表*/ destroyList(headPtr);/*釋放鏈表*/ }創(chuàng)建有序鏈表3/357基本操作5－鏈表結(jié)點(diǎn)的刪除/*函數(shù)功能：刪除鏈表中值為value的結(jié)點(diǎn)，sPtr接收指向鏈表頭結(jié)點(diǎn)的指針的地址，若刪除成功，返回value，否則返回-1*/intdeleteNode(LISTNODEPTR*sPtr,intvalue){

查找待刪除的結(jié)點(diǎn)；刪除結(jié)點(diǎn)；

}58基本操作5－鏈表結(jié)點(diǎn)的刪除第1步：查找待刪除結(jié)點(diǎn)：需要有指針指向待刪結(jié)點(diǎn)以及前驅(qū)結(jié)點(diǎn)171947headPtrpreviousPtrcurrentPtr9sPtrpreviousPtr=NULL;currentPtr=*sPtr;/*currentPtr指向鏈表頭結(jié)點(diǎn)*//*查找待刪除結(jié)點(diǎn)*/while(currentPtr!=NULL&&value!=currentPtr->data){previousPtr=currentPtr;currentPtr=currentPtr->nextPtr;}59第2步（1）：刪除結(jié)點(diǎn)－若刪除的是頭結(jié)點(diǎn)

intdeleteNode(LISTNODEPTR*sPtr,intvalue)171947headPtrcurrentPtr9刪除頭結(jié)點(diǎn)（if(currentPtr==*sPtr)）：*sPtr=currentPtr->nextPtr基本操作5－鏈表結(jié)點(diǎn)的刪除sPtr60第2步（2）：刪除結(jié)點(diǎn)－若刪除的是尾結(jié)點(diǎn)

intdeleteNode(LISTNODEPTR*sPtr,intvalue)171947headPtr9

刪除尾結(jié)點(diǎn)(if(currentPtr->nextPtr==NULL))：

previousPtr->nextPtr=NULL基本操作5－鏈表結(jié)點(diǎn)的刪除sPtrpreviousPtrcurrentPtr61第2步（3）：刪除結(jié)點(diǎn)－若刪除的是中間結(jié)點(diǎn)

intdeleteNode(LISTNODEPTR*sPtr,intvalue)171947headPtrpreviousPtrcurrentPtr9刪除的是中間結(jié)點(diǎn)：

previousPtr->nextPtr=currentPtr->nextPtr基本操作5－鏈表結(jié)點(diǎn)的刪除sPtr62基本操作5－鏈表結(jié)點(diǎn)的刪除進(jìn)一步分析：刪除的是尾結(jié)點(diǎn)：

previousPtr->nextPtr=NULL

此時(shí)currentPtr->nextPtr值為NULL，因此可寫為previousPtr->nextPtr=currentPtr->nextPtr刪除的是中間結(jié)點(diǎn)：

previousPtr->nextPtr=currentPtr->nextPtr因此，刪除尾結(jié)點(diǎn)和刪除中間結(jié)點(diǎn)的操作可以統(tǒng)一成：

previousPtr->nextPtr=currentPtr->nextPtr63基本操作5－鏈表結(jié)點(diǎn)的刪除/*刪除值為value的結(jié)點(diǎn)，若成功刪除，返回結(jié)點(diǎn)數(shù)據(jù)域值；否則返回－1。sPtr用于接收指向鏈表頭接點(diǎn)指針的地址*/intdeleteNode(LISTNODEPTR*sPtr,intvalue){LISTNODEPTRpreviousPtr,currentPtr;

previousPtr=NULL;currentPtr=*sPtr;/*將頭接點(diǎn)地址賦給currentPtr*/

/*查找待刪除結(jié)點(diǎn)，若找到，則由currentPtr指向該結(jié)點(diǎn)*/while(currentPtr!=NULL&¤tPtr->data!=value){previousPtr=currentPtr;currentPtr=currentPtr->nextPtr;}

64基本操作5－鏈表結(jié)點(diǎn)的刪除if(currentPtr!=NULL){/*如果找到要?jiǎng)h除的結(jié)點(diǎn)*/ if(previousPtr==NULL)/*刪除的是頭結(jié)點(diǎn)*/ *sPtr=currentPtr->nextPtr;/*更新頭結(jié)點(diǎn)*/else/*刪除的是中間結(jié)點(diǎn)或者尾結(jié)點(diǎn)*/previousPtr->nextPtr=currentPtr->nextPtr; free(currentPtr);/*釋放結(jié)點(diǎn)內(nèi)存*/returnvalue;}else return-1;//沒有找到符合條件的結(jié)點(diǎn) }65帶頭結(jié)點(diǎn)的單鏈表操作學(xué)習(xí)建立一個(gè)頭結(jié)點(diǎn)的方式簡(jiǎn)化鏈表操作頭結(jié)點(diǎn)中的數(shù)據(jù)成員無(wú)具體含義有了頭結(jié)點(diǎn)創(chuàng)建、插入、刪除時(shí)可以不用判斷headptr是否為空查找、輸出遍歷、排序鏈表從headptr->nextptr開始操作171947headPtr0headPtr0帶頭結(jié)點(diǎn)的空鏈表66練習(xí)1： 編寫一個(gè)遞歸函數(shù)，逆序打印鏈表；編寫一個(gè)遞歸函數(shù)，順序打印鏈表；編寫一個(gè)遞歸函數(shù)，求鏈表中最大值所在結(jié)點(diǎn)；67遞歸逆序遍歷鏈表/*函數(shù)功能：遞歸逆序遍歷鏈表，打印各結(jié)點(diǎn)的值。參數(shù)說(shuō)明：指向結(jié)點(diǎn)的指針，接收鏈表頭接點(diǎn)的地址*/voidprintList(LISTNODEPTRheadPtr){ //思路：先打印后續(xù)結(jié)點(diǎn)，再打印頭結(jié)點(diǎn)

if(headPtr->nextPtr==NULL)//若這是最后一個(gè)結(jié)點(diǎn)

printf("%d",headPtr->data); else{printList(headPtr->nextPtr);printf("%d-->",headPtr->data);}}68遞歸順序遍歷鏈表/*函數(shù)功能：遞歸順序遍歷鏈表，打印各結(jié)點(diǎn)的值。參數(shù)說(shuō)明：指向結(jié)點(diǎn)的指針，接收鏈表頭接點(diǎn)的地址*/voidprintList(LISTNODEPTRheadPtr){ //思路：先打印后續(xù)結(jié)點(diǎn)，再打印頭結(jié)點(diǎn)

if(headPtr->nextPtr==NULL)//若這是最后一個(gè)結(jié)點(diǎn)

printf("%d",headPtr->data); else{printf("%d-->",headPtr->data);printList(headPtr->nextPtr);}}69遞歸求鏈表中最大值所在結(jié)點(diǎn)LISTNODEPTRfindMax(LISTNODEPTRheadPtr){LISTNODEPTRmaxPtr;if(headPtr->nextPtr==NULL)//若這是最后一個(gè)結(jié)點(diǎn)

returnheadPtr;else{maxPtr=findMax(headPtr->nextPtr);/*找后續(xù)結(jié)點(diǎn)中的最 大結(jié)點(diǎn)，由maxPtr指向*/returnmaxPtr->data>headPtr->data?maxPtr:headPtr;}}70例4：鏈表的逆序組織（要求通過修改指針域?qū)崿F(xiàn)）

LISTNODEPTRreverseList(LISTNODEPTRheadPtr)

函數(shù)調(diào)用：headPtr＝reverseList(headPtr);171947headPtr471917解題思路1：依次讓currentPtr指向鏈表的頭結(jié)點(diǎn);headPtr指向下一個(gè)結(jié)點(diǎn)；2.currentPtr指向結(jié)點(diǎn)組裝到新鏈表中作為頭結(jié)點(diǎn);headPtr71LISTNODEPTRreverseList(LISTNODEPTRheadPtr){LISTNODEPTRnewHeadPtr=NULL,currentPtr=NULL;while(headPtr!=NULL){//讓currentPtr指向鏈表的頭結(jié)點(diǎn);headPtr指向下一個(gè)結(jié)點(diǎn)

currentPtr=headPtr;headPtr=headPtr->nextPtr;

//currentPtr指向結(jié)點(diǎn)組裝到新鏈表中作為頭結(jié)點(diǎn)

if(newHeadPtr==NULL){newHeadPtr=currentPtr;newHeadPtr>nextPtr=NULL;}else{currentPtr->nextPtr=newHeadPtr;newHeadPtr=currentPtr;}}returnnewHeadPtr;}72鏈表逆序-思路2171927headPtr47問題的本質(zhì)是要修改除第一個(gè)結(jié)點(diǎn)之外的其他結(jié)點(diǎn)的nextPtr的值，使其指向前一個(gè)結(jié)點(diǎn)。7317192747previousPtrcurrentPtr必須設(shè)置指針（currentPtr

）指向nextPtr要被修改的結(jié)點(diǎn)，設(shè)置指針（previousPtr

）指向的前一個(gè)結(jié)點(diǎn)連接：currentPtr->nextPtr=previousPtr鏈表逆序-思路274鏈表逆序-思路275previousPtr鏈表逆序-思路2headPtrcurrentPtr123previousPtrheadPtrcurrentPtr123posteriorPtrheadPtrcurrentPtr123posteriorPtrpreviousPtr76鏈表逆序-思路2LISTNODEPTRreverseList(LISTNODEPTRheadPtr){LISTNODEPTRpreviousPtr,currentPtr,posteriorPtr;

previousPtr=headPtr;currentPtr=previousPtr->nextPtr;previousPtr->nextPtr=NULL;//很重要，反向后的鏈表的結(jié)束位置

while(currentPtr!=NULL){ posteriorPtr=currentPtr->nextPtr; currentPtr->nextPtr=previousPtr;/*連接*/ previousPtr=currentPtr; currentPtr=posteriorPtr;}returnpreviousPtr;/*返回頭結(jié)點(diǎn)*/}77鏈表逆序－思路3(遞歸)LISTNODEPTRreverseList(LISTNODEPTRheadPtr){if(是最后一個(gè)結(jié)點(diǎn)){returnheadPtr;}else{/*1.當(dāng)前鏈表頭結(jié)點(diǎn)從鏈表中拆除，由lastPtr指向，將成為逆序后的鏈表尾結(jié)點(diǎn)。headPtr指向下一結(jié)點(diǎn)*//*2.遞歸調(diào)用，將headPtr指向的鏈表逆序，由newHeadPtr指向*//*3.將lastPtr指向結(jié)點(diǎn)鏈接到newHeadPtr指向鏈表的尾結(jié)點(diǎn)之后*/

returnnewHeadPtr;}}78鏈表逆序－思路3(遞歸)LISTNODEPTRreverseList(LISTNODEPTRheadPtr){LISTNODEPTRlastPtr=NULL,currentPtr=NULL,newHeadPtr=NULL;

if(headPtr->nextPtr==NULL){//若是最后一個(gè)結(jié)點(diǎn)，則直接返回

returnheadPtr;}else{/*1.當(dāng)前鏈表頭結(jié)點(diǎn)從鏈表中拆除，由lastPtr指向，將成為逆序后的鏈表尾結(jié)點(diǎn)。headPtr指向下一結(jié)點(diǎn)*/lastPtr=headPtr;headPtr=headPtr->nextPtr;lastPtr->nextPtr=NULL;/*2.遞歸調(diào)用，將headPtr指向的鏈表逆序，由newHeadPtr指向*/newHeadPtr=reverseList(headPtr);/*3.將lastPtr指向結(jié)點(diǎn)鏈接到newHeadPtr指向鏈表的尾結(jié)點(diǎn)之后*/currentPtr=newHeadPtr;while(currentPtr->nextPtr!=NULL)//若不是最后結(jié)點(diǎn)

currentPtr=currentPtr->nextPtr;currentPtr->nextPtr=lastPtr;//將尾結(jié)點(diǎn)鏈接到鏈表

returnnewHeadPtr;}}79例5：猴子選大王：有N只猴子圍成一圈，每只猴子從1到N依次編號(hào)。打算從中選出一個(gè)大王，經(jīng)過協(xié)商，決定出選大王的規(guī)則：從第一個(gè)猴子開始循環(huán)報(bào)數(shù)，數(shù)到M的猴子出圈，最后剩下來(lái)的就是大王。②①③④⑤⑥若數(shù)到4的猴子出圈，則出圈的猴子編號(hào)依次是：4、2、1、3、6編號(hào)為5的猴子即為大王。80猴子選大王問題分析：1.如何存儲(chǔ)圍成一圈的猴子編號(hào)12headPtr7…先建立單向鏈表，然后形成循環(huán)鏈表：

lastPtr->nextPtr=headPtr;lastPtr2headPtr2.如何判斷鏈表中是否只剩一個(gè)結(jié)點(diǎn)：headPtr->nextPtr=headPtr;81猴子選大王1－創(chuàng)建循環(huán)鏈表LISTNODEPTRcreateList(intn)//n只猴子編號(hào)存儲(chǔ)到循環(huán)鏈表中{LISTNODEPTRheadPtr=NULL,lastPtr,currentPtr;inti;for(i=1;i<=n;i++){currentPtr=malloc(sizeof(LISTNODE));if(currentPtr！=NULL){ currentPtr->data=i; if(headPtr==NULL){/*若是作為頭結(jié)點(diǎn)*/ headPtr=currentPtr; lastPtr=currentPtr; } else{/*將結(jié)點(diǎn)追加到鏈表末尾*/ lastPtr->nextPtr=currentPtr; lastPtr=currentPtr;}} }//for循環(huán)結(jié)束

lastPtr->nextPtr=headPtr;/*形成循環(huán)鏈表*/returnheadPtr;}82猴子選大王2－選大王83選大王(1/2)voidselectKing(LISTNODEPTRheadPtr,intn)/*n>=2*/{ LISTNODEPTRprePtr=NULL,currentPtr,lastPtr; intcount;/*循環(huán)初始化*/ count=0;

/*使currentPtr指向循環(huán)鏈表的最后一個(gè)結(jié)點(diǎn)*/ currentPtr=headPtr; while(currentPtr->nextPtr!=headPtr) currentPtr=currentPtr->nextPtr;

while(currentPtr!=currentPtr->nextPtr){/*若鏈表中多于一個(gè)結(jié)點(diǎn)*/

/*往后數(shù)一個(gè)猴子*/

prePtr=currentPtr; currentPtr=currentPtr->nextPtr; count++;84選大王(2/2) if(count%n==0){//若數(shù)到n，則淘汰currentPtr指向的猴子

//從headPtr指向鏈表中拆下currentPtr指向的結(jié)點(diǎn)

prePtr->nextPtr=currentPtr->nextPtr; printf(“%d”,currentPtr->data);free(currentPtr);

//currentPtr指向上一個(gè)結(jié)點(diǎn)，為下一次數(shù)數(shù)做準(zhǔn)備

currentPtr=prePtr;}//endofif }//endofwhileprintf("大王是：%d\n",currentPtr->data);

free(currentPtr); }

85例5：有序(升序)鏈表的歸并3847headPtr13560headPtr178歸并后的鏈表57headPtr26047863847headPtr157headPtr260previous1Ptrcurrent1Ptr思路：當(dāng)鏈表2結(jié)點(diǎn)未完全歸并到鏈表1的情況下重復(fù)做如下操作：1.查找鏈表2結(jié)點(diǎn)在鏈表1中的插入位置：根據(jù)鏈表2的頭結(jié)點(diǎn)（5所在結(jié)點(diǎn)）找到在鏈表1的插入位置（8所在結(jié)點(diǎn)之前），由current1Ptr指向；current1Ptr指向結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)由previous1Ptr指向。將插入previous1Ptr和current1Ptr指向的結(jié)點(diǎn)之間。872.若插入到鏈表1尾部，則鏈表2直接連到鏈表1上；若插入到鏈表1頭結(jié)點(diǎn)前或中間位置，則進(jìn)一步確定鏈表2中要插入的結(jié)點(diǎn)(left2Ptr指向結(jié)點(diǎn)一直到previous2Ptr指向的結(jié)點(diǎn)),并歸并到鏈表1中，同時(shí)修改headPtr2的值。

3847headPtr157headPtr260previous1Ptrcurrent1Ptrcurrent2Ptrprevious2Ptrleft2Ptr如何在鏈表2中找到數(shù)據(jù)域小于8的最大結(jié)點(diǎn)：在鏈表2中找到數(shù)據(jù)域大于8的第1個(gè)結(jié)點(diǎn)（current2Ptr指向）及其前驅(qū)結(jié)點(diǎn)previous2Ptr指向，則previous2Ptr指向結(jié)點(diǎn)即為要找的結(jié)點(diǎn)。88有序(升序)鏈表的歸并函數(shù)設(shè)計(jì)1.LISTNODEPTRmergeSortList(LISTNODEPTRhead1Ptr,LISTNODEPTRhead2Ptr)

參數(shù)：head1Ptr指向鏈表1頭結(jié)點(diǎn)的指針；

head2Ptr指向鏈表2頭結(jié)點(diǎn)的指針；返回值：指向歸并后鏈表頭接點(diǎn)的指針89有序(升序)鏈表的歸并LISTNODEPTRmergeSortList(LISTNODEPTRhead1Ptr,LISTNODEPTRhead2Ptr){while(head2Ptr!=NULL){

查找鏈表2結(jié)點(diǎn)在鏈表1中的插入位置：確定previous1Ptr和 current1Ptr;if(current1Ptr==NULL){//若插入到鏈表1尾部

鏈表2直接連到鏈表1尾部；

head2Ptr=NULL;}else{//若插入到鏈表1中間或最前面

確定鏈表2中要插入的結(jié)點(diǎn)：由leftPtr2和previous2Ptr指