鏈表說課講解

1、 鏈表鏈表 自引用結(jié)構(gòu)包含一個指針成員，該指針指向與自自引用結(jié)構(gòu)包含一個指針成員，該指針指向與自身同一個類型的結(jié)構(gòu)。如：身同一個類型的結(jié)構(gòu)。如：struct node int data; struct node * nextPtr; ； struct node 就是自引用結(jié)構(gòu)。就是自引用結(jié)構(gòu)。nextPtr稱為鏈節(jié)稱為鏈節(jié)（link），用于把一個），用于把一個struct node類型的結(jié)構(gòu)變類型的結(jié)構(gòu)變量和另一個同類型的結(jié)構(gòu)變量鏈在一起。量和另一個同類型的結(jié)構(gòu)變量鏈在一起。struct node n1，n2；n1.nextPtr=&n2;n1n2自引用結(jié)構(gòu) 12.2 自引用結(jié)構(gòu)自引用

2、結(jié)構(gòu)12.4 鏈表鏈表 12.4.1 鏈表結(jié)構(gòu)鏈表結(jié)構(gòu) 12.4.2 鏈表中結(jié)點的訪問鏈表中結(jié)點的訪問 12.4.3 鏈表基本操作鏈表基本操作提綱提綱 12.4.1 鏈表結(jié)構(gòu)鏈表結(jié)構(gòu)問題的引出問題的引出1號書號書206301號抽屜號抽屜2號書號書403206號抽屜號抽屜3號書號書403號抽屜號抽屜301抽抽屜屜向管理員申請三個抽屜放三本書，分配的抽屜號是不連續(xù)的向管理員申請三個抽屜放三本書，分配的抽屜號是不連續(xù)的.看書順序看書順序:必須要先看必須要先看1號書號書,再看再看2號書號書,再看再看3號書號書.問題：怎么能依次拿到這三本書？問題：怎么能依次拿到這三本書？ 12.4.1 鏈表結(jié)構(gòu)鏈表結(jié)構(gòu)

3、 解決方案：解決方案： 把第一本書所在抽屜號記錄在一張紙上；把第一本書所在抽屜號記錄在一張紙上； 把第二本書所在抽屜號記錄在一張紙，放到把第二本書所在抽屜號記錄在一張紙，放到第一本書所在抽屜里；第一本書所在抽屜里； 把第三本書所在抽屜號記錄在一張紙，放到把第三本書所在抽屜號記錄在一張紙，放到第二本書所在抽屜里；第二本書所在抽屜里； 12.4.1 鏈表結(jié)構(gòu)鏈表結(jié)構(gòu) 一個類比：一個類比： 如果有多個學(xué)生記錄需要存放到內(nèi)存，而存如果有多個學(xué)生記錄需要存放到內(nèi)存，而存放記錄的內(nèi)存通常是不連續(xù)的，如何能訪問放記錄的內(nèi)存通常是不連續(xù)的，如何能訪問到這些記錄？到這些記錄？ 12.4.1 鏈表結(jié)構(gòu)鏈表結(jié)構(gòu)st

4、ruct student /*學(xué)生信息結(jié)構(gòu)類型學(xué)生信息結(jié)構(gòu)類型*/ char no7; /*學(xué)號學(xué)號*/ char name9; /*姓名姓名*/ ; main() char no7; struct student * ptr; printf(請輸入學(xué)生學(xué)號請輸入學(xué)生學(xué)號); gets(no);/讀入學(xué)號讀入學(xué)號 while(strcmp(no,0000)!=0) ptr = malloc(sizeof(struct student) ; strcpy(ptr-no,no);/學(xué)號復(fù)制到內(nèi)存中學(xué)號復(fù)制到內(nèi)存中 printf(請輸入學(xué)生姓名請輸入學(xué)生姓名); gets(ptr-name); /讀

5、取姓名到內(nèi)存中讀取姓名到內(nèi)存中 printf(請輸入學(xué)生學(xué)號請輸入學(xué)生學(xué)號); gets(no); . 讀入若干個學(xué)生的信息讀入若干個學(xué)生的信息并進行處理。由于學(xué)生并進行處理。由于學(xué)生個數(shù)未知，因此用動態(tài)個數(shù)未知，因此用動態(tài)分配的內(nèi)存來存放學(xué)生分配的內(nèi)存來存放學(xué)生信息，代碼如左所示。信息，代碼如左所示。存在問題：由于是動態(tài)存在問題：由于是動態(tài)分配內(nèi)存來存放學(xué)生信分配內(nèi)存來存放學(xué)生信息，因此存放每個學(xué)生息，因此存放每個學(xué)生信息的內(nèi)存通常是不連信息的內(nèi)存通常是不連續(xù)的，如何能訪問到這續(xù)的，如何能訪問到這些學(xué)生信息？些學(xué)生信息？ 12.4.1 鏈表結(jié)構(gòu)鏈表結(jié)構(gòu)類比類比 書學(xué)生信息書學(xué)生信息 抽屜存放

6、學(xué)生信息的內(nèi)存抽屜存放學(xué)生信息的內(nèi)存 記錄第一本書所在抽屜號的紙張指針記錄第一本書所在抽屜號的紙張指針 記錄下一本書所在抽屜號的紙張結(jié)構(gòu)記錄下一本書所在抽屜號的紙張結(jié)構(gòu)變量里的指針成員變量里的指針成員 12.4.1 鏈表結(jié)構(gòu)鏈表結(jié)構(gòu)學(xué)生信學(xué)生信息息10022FF8A學(xué)生信學(xué)生信息息20023FF80學(xué)生信學(xué)生信息息30022FF7C0022FF7C0022FF8A0023FF80動態(tài)申請動態(tài)申請3個結(jié)構(gòu)變量存儲個結(jié)構(gòu)變量存儲3個學(xué)生的信息，個學(xué)生的信息，3個結(jié)構(gòu)變量個結(jié)構(gòu)變量通過指針通過指針“鏈鏈”在了一起，具有前驅(qū)和后繼關(guān)系。第一個在了一起，具有前驅(qū)和后繼關(guān)系。第一個結(jié)構(gòu)變量的地址單獨記錄在

7、一個指針里。結(jié)構(gòu)變量的地址單獨記錄在一個指針里。 17 19 47 headPtr鏈表是用鏈節(jié)指針鏈在一起的自引用結(jié)構(gòu)變量（稱為結(jié)點）鏈表是用鏈節(jié)指針鏈在一起的自引用結(jié)構(gòu)變量（稱為結(jié)點）的線性集合，是線性表的一種存儲結(jié)構(gòu)。的線性集合，是線性表的一種存儲結(jié)構(gòu)。（1）headPtr指向鏈表首結(jié)點的指針變量。指向鏈表首結(jié)點的指針變量。（2）每個結(jié)點由）每個結(jié)點由2個域組成：個域組成：數(shù)據(jù)域數(shù)據(jù)域存儲結(jié)點本身的信息。存儲結(jié)點本身的信息。指針域指針域存儲指向后繼結(jié)點的指針。存儲指向后繼結(jié)點的指針。（3）尾結(jié)點的指針域置為）尾結(jié)點的指針域置為NULL(用反斜杠表示用反斜杠表示)，作為鏈表，作為鏈表結(jié)束的標

8、志。結(jié)束的標志。12.4.1 鏈表結(jié)構(gòu)鏈表結(jié)構(gòu) 12.4.1 鏈表結(jié)構(gòu)鏈表結(jié)構(gòu)鏈表的特點：鏈表的特點：鏈表是一種存儲結(jié)構(gòu)，用于存放線性表；鏈表是一種存儲結(jié)構(gòu)，用于存放線性表；鏈表的結(jié)點是根據(jù)需要調(diào)用動態(tài)內(nèi)存分配函數(shù)進行分鏈表的結(jié)點是根據(jù)需要調(diào)用動態(tài)內(nèi)存分配函數(shù)進行分配的，因此鏈表可隨需要伸長縮短，在要存儲的數(shù)據(jù)配的，因此鏈表可隨需要伸長縮短，在要存儲的數(shù)據(jù)個數(shù)未知的情況下節(jié)省內(nèi)存；個數(shù)未知的情況下節(jié)省內(nèi)存；鏈表的結(jié)點在邏輯上是連續(xù)的，但是各結(jié)點的內(nèi)存通鏈表的結(jié)點在邏輯上是連續(xù)的，但是各結(jié)點的內(nèi)存通常是不連續(xù)的，因此不能立即被訪問到，只能從頭結(jié)常是不連續(xù)的，因此不能立即被訪問到，只能從頭結(jié)點開始

9、逐結(jié)點訪問。點開始逐結(jié)點訪問。17 19 47 headPtr 12.2 自引用結(jié)構(gòu)自引用結(jié)構(gòu)12.4 鏈表鏈表 12.4.1 鏈表結(jié)構(gòu)鏈表結(jié)構(gòu) 12.4.2 鏈表的創(chuàng)建、結(jié)點的插入和刪除鏈表的創(chuàng)建、結(jié)點的插入和刪除 12.4.3 鏈表基本操作鏈表基本操作提綱提綱 1.鏈表的創(chuàng)建鏈表的創(chuàng)建 從無到有，結(jié)點逐個創(chuàng)建、加入，構(gòu)成鏈表從無到有，結(jié)點逐個創(chuàng)建、加入，構(gòu)成鏈表17 19 47 headPtr鏈表中的結(jié)點內(nèi)存是動態(tài)分配的鏈表中的結(jié)點內(nèi)存是動態(tài)分配的:newPtr=malloc(sizeof(struct node)；newPtr-data=10;鏈表結(jié)點的動態(tài)分配決定了結(jié)點在內(nèi)存的位鏈表結(jié)

10、點的動態(tài)分配決定了結(jié)點在內(nèi)存的位置不一定是連續(xù)的！置不一定是連續(xù)的！ 2.鏈表中結(jié)點的訪問鏈表中結(jié)點的訪問 如何訪問鏈表中的結(jié)點：由于鏈表中結(jié)點的內(nèi)如何訪問鏈表中的結(jié)點：由于鏈表中結(jié)點的內(nèi)存是動態(tài)分配的，無法通過名稱去訪問，因此存是動態(tài)分配的，無法通過名稱去訪問，因此只能通過結(jié)點的地址去訪問只能通過結(jié)點的地址去訪問。 某某結(jié)點的地址記錄在其前驅(qū)結(jié)點的地址域結(jié)點的地址記錄在其前驅(qū)結(jié)點的地址域里，里，因此要想訪問第因此要想訪問第n個結(jié)點，必須先得訪問第個結(jié)點，必須先得訪問第n-1個結(jié)點，讀取該結(jié)點的地址域；而要想訪問第個結(jié)點，讀取該結(jié)點的地址域；而要想訪問第n-1個結(jié)點，必須先得訪問第個結(jié)點，必須

11、先得訪問第n-2個結(jié)點；以此個結(jié)點；以此類推，一直推到訪問第類推，一直推到訪問第1個結(jié)點。而第個結(jié)點。而第1個結(jié)點個結(jié)點是由指針是由指針headPtr指向的，因此能訪問第指向的，因此能訪問第1個結(jié)個結(jié)點，從而也就能訪問第點，從而也就能訪問第2個結(jié)點，第個結(jié)點，第3個結(jié)個結(jié)點點 訪問頭結(jié)點：訪問頭結(jié)點： printf(“%d”，headPtr-data);訪問第二個結(jié)點：訪問第二個結(jié)點：currentPtr=headPtr-nextPtr; printf(“%d”, currentPtr-data);訪問第三個結(jié)點：訪問第三個結(jié)點： currentPtr=currentPtr-nextPtr;

12、printf(“%d”, currentPtr-data);17 19 47 headPtr2. 鏈表中結(jié)點的訪問鏈表中結(jié)點的訪問currentPtr37 只要知道指向鏈表頭結(jié)點的指針變量只要知道指向鏈表頭結(jié)點的指針變量headPtr，就可以從頭結(jié)，就可以從頭結(jié)點開始依次訪問各個結(jié)點。點開始依次訪問各個結(jié)點。這樣借助于這樣借助于currentPtr“順藤順藤摸瓜摸瓜”，就能逐個訪問鏈表，就能逐個訪問鏈表中的結(jié)點。可見鏈表結(jié)點不中的結(jié)點?？梢婃湵斫Y(jié)點不能立即被訪問到。能立即被訪問到。 3.鏈表結(jié)點的動態(tài)增加和刪除鏈表結(jié)點的動態(tài)增加和刪除17 19 47 headPtr27 newPtr17 19

13、 47 headPtr9 鏈表中結(jié)點的插入和刪除不需要移動鏈表中結(jié)點的插入和刪除不需要移動其他結(jié)點，比較方便其他結(jié)點，比較方便插入插入刪除刪除 鏈表和數(shù)組存儲線性表的比較鏈表和數(shù)組存儲線性表的比較數(shù)組的優(yōu)點：數(shù)組的優(yōu)點： 數(shù)組中的元素在內(nèi)存中是連續(xù)存放的，能根據(jù)數(shù)組的數(shù)組中的元素在內(nèi)存中是連續(xù)存放的，能根據(jù)數(shù)組的首地址計算出各數(shù)組元素的內(nèi)存地址，所以可以直接首地址計算出各數(shù)組元素的內(nèi)存地址，所以可以直接用下標訪問到數(shù)組元素；而鏈表中的元素在內(nèi)存中通用下標訪問到數(shù)組元素；而鏈表中的元素在內(nèi)存中通常是不連續(xù)存放的，因此不能被立即訪問到。常是不連續(xù)存放的，因此不能被立即訪問到。鏈表的優(yōu)點：鏈表的優(yōu)點

14、：1、可伸縮性：數(shù)組一旦在內(nèi)存分配空間之后，大小就不、可伸縮性：數(shù)組一旦在內(nèi)存分配空間之后，大小就不能改變；而鏈表是動態(tài)的，在需要的時候可以增加或能改變；而鏈表是動態(tài)的，在需要的時候可以增加或刪減結(jié)點；數(shù)組的空間可能很快就用完，而鏈表只有刪減結(jié)點；數(shù)組的空間可能很快就用完，而鏈表只有在系統(tǒng)沒有足夠的內(nèi)存滿足動態(tài)分配存儲空間的請求在系統(tǒng)沒有足夠的內(nèi)存滿足動態(tài)分配存儲空間的請求時時 才會達到全滿的狀態(tài)；才會達到全滿的狀態(tài)；2、插入和刪除操作：數(shù)組的插入和刪除涉及到移動元素、插入和刪除操作：數(shù)組的插入和刪除涉及到移動元素的操作，因此比較費時；而鏈表的插入和刪除比較簡的操作，因此比較費時；而鏈表的插入

15、和刪除比較簡單；單； 12.2 自引用結(jié)構(gòu)自引用結(jié)構(gòu)12.4 鏈表鏈表 12.4.1 鏈表結(jié)構(gòu)鏈表結(jié)構(gòu) 12.4.2 鏈表的創(chuàng)建、結(jié)點的插入和刪除鏈表的創(chuàng)建、結(jié)點的插入和刪除 12.4.3 鏈表基本操作鏈表基本操作提綱提綱 對鏈表的基本操作有：創(chuàng)建鏈表、檢索（查找）結(jié)點、對鏈表的基本操作有：創(chuàng)建鏈表、檢索（查找）結(jié)點、插入、刪除結(jié)點和修改結(jié)點等。插入、刪除結(jié)點和修改結(jié)點等。（1）創(chuàng)建鏈表是指：從無到有地建立起一個鏈表，即往）創(chuàng)建鏈表是指：從無到有地建立起一個鏈表，即往空鏈表中依次插入若干結(jié)點，并保持結(jié)點之間的前驅(qū)空鏈表中依次插入若干結(jié)點，并保持結(jié)點之間的前驅(qū)和后繼關(guān)系。和后繼關(guān)系。（2）檢索操

16、作是指：按給定的結(jié)點索引號或檢索條件，）檢索操作是指：按給定的結(jié)點索引號或檢索條件，查找某個結(jié)點。查找某個結(jié)點。（3）插入操作是指：在結(jié)點）插入操作是指：在結(jié)點ki-1與與ki之間插入一個新的結(jié)之間插入一個新的結(jié)點點k 。（4）刪除操作是指：刪除結(jié)點）刪除操作是指：刪除結(jié)點ki，使線性表的長度減，使線性表的長度減1。12.4.3 鏈表基本操作鏈表基本操作 12.4.3 鏈表基本操作鏈表基本操作typedef struct listNode LISTNODE;typedef LISTNODE * LISTNODEPTR;/*LISTNODEPTR：指向：指向LISTNODE指針指針*/17 19

17、 47 headPtrLISTNODE類型類型LISTNODEPTR類型類型struct listNodeint data;struct listNode *nextPtr; ; 17 19 47 headPtr例例1、讀入一批數(shù)，以、讀入一批數(shù)，以-1結(jié)束。將輸入的數(shù)據(jù)組成先進先結(jié)束。將輸入的數(shù)據(jù)組成先進先 出出的鏈表并輸出，最后釋放鏈表。的鏈表并輸出，最后釋放鏈表。 要求：設(shè)計一個函數(shù)要求：設(shè)計一個函數(shù)LISTNODEPTR createFIFOList( )；函數(shù)功能：讀入一批數(shù)（以函數(shù)功能：讀入一批數(shù)（以1結(jié)束），將輸入的數(shù)組成結(jié)束），將輸入的數(shù)組成 先進先出的鏈表，并返回指向鏈表頭結(jié)

18、點的先進先出的鏈表，并返回指向鏈表頭結(jié)點的 指針。指針?；静僮骰静僮?創(chuàng)建鏈表創(chuàng)建鏈表依次讀入依次讀入17、19、47之后創(chuàng)建的鏈表之后創(chuàng)建的鏈表 17 19 47 headPtr假設(shè)輸入的數(shù)據(jù)為假設(shè)輸入的數(shù)據(jù)為17,19,47,-1，則數(shù)據(jù)組織成先進先出鏈表，則數(shù)據(jù)組織成先進先出鏈表的過程：的過程：基本操作基本操作1創(chuàng)建鏈表創(chuàng)建鏈表讀取一個數(shù)后：讀取一個數(shù)后：動態(tài)申請結(jié)點內(nèi)存，存放數(shù)據(jù)；動態(tài)申請結(jié)點內(nèi)存，存放數(shù)據(jù)；如果新增結(jié)點是頭接點，則令如果新增結(jié)點是頭接點，則令headPtr指向該結(jié)點；指向該結(jié)點；如果新增不是頭接點，則將該結(jié)點追加到鏈表尾結(jié)點后面；如果新增不是頭接點，則將該結(jié)點追加

19、到鏈表尾結(jié)點后面；如果新增結(jié)點是尾結(jié)點，則鏈節(jié)指針賦值為如果新增結(jié)點是尾結(jié)點，則鏈節(jié)指針賦值為NULL。 基本操作基本操作1創(chuàng)建鏈表創(chuàng)建鏈表LISTNODE * createFIFOList( ) /變量定義；變量定義； /變量初始化；變量初始化； scanf(“%d”,&num); while(num != -1) currentPtr = malloc(sizeof(LISTNODE); if(currentPtr != NULL) currentPtr-data = num; /將新結(jié)點插入鏈表；將新結(jié)點插入鏈表； scanf(“%d”,&num); return hea

20、dPtr； 17 47 headPtrcurrentPtr37 lastPtr若創(chuàng)建的是頭結(jié)點，則由若創(chuàng)建的是頭結(jié)點，則由headPtr指向；指向；否則，新增的結(jié)點追加到鏈表尾結(jié)點后面；否則，新增的結(jié)點追加到鏈表尾結(jié)點后面； 為了讓新增結(jié)點能方便地追加到鏈表尾結(jié)點后面，需要設(shè)為了讓新增結(jié)點能方便地追加到鏈表尾結(jié)點后面，需要設(shè)計一個指針計一個指針lastPtr來指向鏈表尾結(jié)點；來指向鏈表尾結(jié)點； 追加過程為：追加過程為：lastPtr-nextPtr=currentPtr; 修正修正lastPtr，使之指向鏈表尾結(jié)點：，使之指向鏈表尾結(jié)點：lastPtr=currentPtr；19 14 cur

21、rentPtr LISTNODE * createFIFOList1()int num; LISTNODEPTR headPtr=NULL,lastPtr=NULL,currentPtr=NULL;printf(input positive numbers,-1 to endn); scanf(%d,&num); while(num!=-1) currentPtr=malloc(sizeof(LISTNODE); /*分配結(jié)點內(nèi)存分配結(jié)點內(nèi)存*/ if (currentPtr!=NULL)/*插入結(jié)點插入結(jié)點*/ currentPtr-data=num; if (headPtr=NUL

22、L) /*若若currentPtr是頭結(jié)點是頭結(jié)點*/ headPtr=currentPtr; lastPtr=currentPtr; else lastPtr-nextPtr=currentPtr; /*將結(jié)點連上鏈表尾結(jié)點將結(jié)點連上鏈表尾結(jié)點*/ lastPtr=currentPtr; /*使使lastPtr指向當前鏈表的最后一個結(jié)點指向當前鏈表的最后一個結(jié)點*/ scanf(%d,&num); lastPtr-nextPtr=NULL;/*設(shè)置鏈表結(jié)束標記設(shè)置鏈表結(jié)束標記*/ return headPtr; 【源程序】 main() LISTNODEPTR headPtr=NUL

23、L； createFIFOList2(&headPtr); /*創(chuàng)建鏈表，鏈表頭結(jié)點創(chuàng)建鏈表，鏈表頭結(jié)點 地址寫入地址寫入headPtr中中*/void createFIFOList2(LISTNODEPTR * sPtr)鏈表頭結(jié)點不通過返回值返回：鏈表頭結(jié)點不通過返回值返回：17 19 47 headPtrmain函數(shù)函數(shù)創(chuàng)建鏈表函數(shù)創(chuàng)建鏈表函數(shù) sPtrif (*sPtr=NULL)/*若是頭結(jié)點若是頭結(jié)點*/ *sPtr=currentPtr; lastPtr=currentPtr; else。 基本操作基本操作1創(chuàng)建鏈表創(chuàng)建鏈表總結(jié)：總結(jié)： 當定義一個對鏈表進行處理的函數(shù)時，

24、如果在該函數(shù)當定義一個對鏈表進行處理的函數(shù)時，如果在該函數(shù)中可能會修改鏈表的頭結(jié)點，則往往可以在函數(shù)中設(shè)中可能會修改鏈表的頭結(jié)點，則往往可以在函數(shù)中設(shè)置一個參數(shù)置一個參數(shù)sPtr，用于接收指向鏈表頭結(jié)點的指針，用于接收指向鏈表頭結(jié)點的指針headPtr地址。在函數(shù)中通過地址。在函數(shù)中通過*sPtr來間接訪問來間接訪問headPtr，修改修改headPtr 的值。的值。 sPtr17 19 47 headPtrvoid chainOp(LISTNODEPTR * sPtr) 函數(shù)調(diào)用：函數(shù)調(diào)用：chainOp(&headPtr)main函數(shù)函數(shù)chainOP函數(shù)函數(shù) 基本操作基本操作1創(chuàng)

25、建鏈表創(chuàng)建鏈表 練習(xí)：讀入一批整數(shù)練習(xí)：讀入一批整數(shù)17,19,47,-1 ，以，以-1結(jié)束。結(jié)束。將輸入的數(shù)據(jù)組成先進后出的鏈表將輸入的數(shù)據(jù)組成先進后出的鏈表 。47 19 17 headPtr LISTNODEPTR createFILOList() int num; LISTNODEPTR headPtr=NULL,currentPtr=NULL; printf(input the numbers,-1to endn); scanf(%d,&num); while(num!=-1) currentPtr=malloc(sizeof(LISTNODE); if (currentPt

26、r!=NULL) currentPtr-data=num; if (headPtr=NULL)/創(chuàng)建的是第一個結(jié)點 headPtr=currentPtr; headPtr-nextPtr=NULL; else currentPtr-nextPtr=headPtr; /鏈接 headPtr=currentPtr; scanf(%d,&num); return headPtr; void createFILOList(LISTNODEPTR * sPtr int num; LISTNODEPTR currentPtr=NULL;printf(input positive numbers,-

27、1 to endn); scanf(%d,&num); while(num!=-1) currentPtr=malloc(sizeof(LISTNODE); if (currentPtr!=NULL) currentPtr-data=num; if (*sPtr=NULL)/*若若currentPtr是第一個結(jié)點是第一個結(jié)點*/ currentPtr-nextPtr=NULL; *sPtr=currentPtr; else currentPtr-nextPtr=*sPtr; *sPtr=currentPtr; scanf(%d,&num); 17 19 47 headPtrcu

28、rrentPtr37 函數(shù)設(shè)計考慮：要想訪問鏈表，只需知道鏈表頭結(jié)點的地址，函數(shù)設(shè)計考慮：要想訪問鏈表，只需知道鏈表頭結(jié)點的地址，就可以就可以 “順藤摸瓜順藤摸瓜”，依次訪問各個結(jié)點。，依次訪問各個結(jié)點。函數(shù)接口設(shè)計：函數(shù)接口設(shè)計：void printList(LISTNODEPTR currentPtr) currentPtr用于接收鏈表頭結(jié)點地址。用于接收鏈表頭結(jié)點地址。函數(shù)調(diào)用：函數(shù)調(diào)用：printList(headPtr)基本操作基本操作2遍歷鏈表（打印）遍歷鏈表（打?。?17 19 47 headPtrcurrentPtr37 函數(shù)接口設(shè)計：函數(shù)接口設(shè)計：void printList

29、(LISTNODEPTR currentPtr)鏈表結(jié)點的訪問：通過鏈表結(jié)點的訪問：通過currentPtr依次訪問鏈表各結(jié)點。訪問完依次訪問鏈表各結(jié)點。訪問完當前指向的結(jié)點后，讓當前指向的結(jié)點后，讓currentPtr指向下一個結(jié)點：指向下一個結(jié)點： currentPtr=currentPtr-nextPtr基本操作基本操作2遍歷鏈表（打?。┍闅v鏈表（打印） 基本操作基本操作2遍歷鏈表（打?。┍闅v鏈表（打印）while(？) printf(“%d-,currentPtr-data); currentPtr=currentPtr-nextPtr; /*指向下一結(jié)點指向下一結(jié)點*/ 17 19

30、47 headPtrcurrentPtr37 currentPtr!=NULL void printList(LISTNODEPTR currentPtr) if (currentPtr=NULL) printf(the list is emptyn); else printf(the list is:n); while(currentPtr!=NULL) printf(“%d-,currentPtr-data); currentPtr=currentPtr-nextPtr; printf(NULLnn); 基本操作基本操作2遍歷鏈表（打?。┍闅v鏈表（打印）17 19 47 headPtrcu

31、rrentPtrmain() LISTNODEPTR headPtr； headPtr=createFIFOList1(); printList(headPtr)； 函數(shù)設(shè)計考慮：要釋放鏈表各個結(jié)點，只需要函數(shù)設(shè)計考慮：要釋放鏈表各個結(jié)點，只需要知道鏈表頭結(jié)點地址，就可以知道鏈表頭結(jié)點地址，就可以 “順藤摸瓜順藤摸瓜”，依次釋放各個結(jié)點。依次釋放各個結(jié)點。 函數(shù)接口設(shè)計：函數(shù)接口設(shè)計：void destroyList(LISTNODEPTR headPtr)參數(shù)參數(shù)headPtr用于接收鏈表頭結(jié)點地址用于接收鏈表頭結(jié)點地址基本操作基本操作2遍歷鏈表（釋放鏈表）遍歷鏈表（釋放鏈表） 17 19

32、47 headPtrheadPtrtempPtr思考：若用語句思考：若用語句free(headPtr)來釋放鏈表頭結(jié)點，會有什么后果？來釋放鏈表頭結(jié)點，會有什么后果？后果：第二個結(jié)點的地址也就丟失了，從而無法釋放后續(xù)結(jié)點！后果：第二個結(jié)點的地址也就丟失了，從而無法釋放后續(xù)結(jié)點！解決方法：設(shè)置指針變量解決方法：設(shè)置指針變量tempPtr。要釋放。要釋放headPtr指向的結(jié)點之前，指向的結(jié)點之前，先將先將headPtr 值賦給值賦給tempPtr ，然后，然后headPtr指向下一結(jié)點，然后執(zhí)指向下一結(jié)點，然后執(zhí)行行free(tempPtr)基本操作基本操作2遍歷鏈表（釋放鏈表）遍歷鏈表（釋放鏈

33、表） 基本操作基本操作2遍歷鏈表（釋放鏈表）遍歷鏈表（釋放鏈表）while (？) tempPtr=headPtr; headPtr=headPtr-nextPtr;/*headPtr指向下一個要指向下一個要刪除的結(jié)點刪除的結(jié)點*/ free(tempPtr);/*釋放當前結(jié)點釋放當前結(jié)點*/17 19 47 headPtrtempPtrheadPtr!=NULL void destroyList(LISTNODEPTR headPtr) LISTNODEPTR tempPtr; while (headPtr!=NULL) tempPtr=headPtr; headPtr=headPtr-ne

34、xtPtr;/*headPtr指向下一個要指向下一個要刪除的結(jié)點刪除的結(jié)點*/ free(tempPtr); main() LISTNODEPTR headPtr； headPtr=createFIFOList1(); printList(headPtr)； destroy(headPtr); headPtr=NULL;基本操作基本操作2遍歷鏈表（釋放鏈表）遍歷鏈表（釋放鏈表） 基本操作基本操作3鏈表結(jié)點的檢索鏈表結(jié)點的檢索17 19 47 headPtr currentPtr9 LISTNODEPTR find(LISTNODEPTR currentPtr, int value) while

35、(currentPtr!=NULL & currentPtr-data !=value) currentPtr=currentPtr-nextPtr; return currentPtr； 基本操作基本操作3鏈表結(jié)點的檢索鏈表結(jié)點的檢索 鏈表結(jié)點檢索固有思路：當鏈表結(jié)點檢索固有思路：當currentPtr指向結(jié)指向結(jié)點不滿足條件，就繼續(xù)查找點不滿足條件，就繼續(xù)查找LISTNODEPTR find(LISTNODEPTR currentPtr, ) while(currentPtr!=NULL & currentPtr-data 不滿足條件不滿足條件) currentPtr=cu

36、rrentPtr-nextPtr; return currentPtr； 例例2、定義一個函數(shù)，將一個正數(shù)插入到升序排列的鏈表中，、定義一個函數(shù)，將一個正數(shù)插入到升序排列的鏈表中，要求插入后的鏈表還是升序的。要求插入后的鏈表還是升序的。 void insert(LISTNODEPTR * sPtr, int value);/* sPtr 用于接收鏈表頭結(jié)點的地址，用于接收鏈表頭結(jié)點的地址，value是插入結(jié)點的值是插入結(jié)點的值*/ 函數(shù)調(diào)用：函數(shù)調(diào)用：insert(&headPtr, num);基本操作基本操作4鏈表結(jié)點的插入鏈表結(jié)點的插入 void insert(LISTNODEPT

37、R * sPtr, int value) /*為新結(jié)點申請內(nèi)存空間為新結(jié)點申請內(nèi)存空間*/ newPtr=(LISTNODEPTR)malloc(sizeof(LISTNODE); if (newPtr!=NULL) /*分配成功分配成功*/ newPtr-data=value; newPtr-nextPtr=NULL; 確定新結(jié)點的插入位置確定新結(jié)點的插入位置; 插入新結(jié)點插入新結(jié)點； 基本操作基本操作4鏈表結(jié)點的插入鏈表結(jié)點的插入 17 19 47 headPtr sPtrpreviousPtr currentPtr27 newPtr要將要將newPtr指向結(jié)點插入指向結(jié)點插入curren

38、tPtr指向結(jié)點前，還必須能訪指向結(jié)點前，還必須能訪問到問到currentPtr指向結(jié)點的前驅(qū)結(jié)點。指向結(jié)點的前驅(qū)結(jié)點。插入操作：插入操作：previousPtr-nextPtr=newPtr; newPtr-nextPtr=currentPtr;因此，因此，確定新結(jié)點的插入位置確定新結(jié)點的插入位置就是要確定就是要確定previousPtr和和currentPtr的值。的值。 17 19 47 headPtr sPtr/*尋找新結(jié)點插入位置，新結(jié)點尋找新結(jié)點插入位置，新結(jié)點將插在將插在*previousPtr和和*currentPtr之間之間*/ previousPtr=NULL; curre

39、ntPtr=*sPtr; /*currentPtr指向鏈表頭結(jié)點指向鏈表頭結(jié)點*/while(currentPtr!=NULL & currentPtr-datanextPtr; 27 newPtrpreviousPtr currentPtr這兩條件不能調(diào)換順序！ 17 19 47 headPtr sPtrcurrentPtrpreviousPtr10 newPtr查找結(jié)果查找結(jié)果1：新結(jié)點插在鏈表頭結(jié)點前面：新結(jié)點插在鏈表頭結(jié)點前面previousPtr=NULL; currentPtr=*sPtr;while(currentPtr!=NULL & currentPtr-da

40、tanextPtr=currentPtr; *sPtr=newPtr; /*修改修改headPtr*/previousPtrcurrentPtr10 newPtr 17 19 47 headPtr sPtr60 newPtr查找結(jié)果查找結(jié)果2：新結(jié)點插在鏈表尾結(jié)點后面：新結(jié)點插在鏈表尾結(jié)點后面previousPtr=NULL; currentPtr=*sPtr;while(currentPtr!=NULL & currentPtr-datanextPtr;新結(jié)點插在鏈表尾結(jié)點后面新結(jié)點插在鏈表尾結(jié)點后面: if (currentPtr= =NULL)或者或者if (previousPt

41、r-nextPtr=NULL)currentPtrpreviousPtr 17 19 47 headPtr sPtrif (previousPtr=NULL)/*若插在最前面若插在最前面*/ else if (currentPtr=NULL) /*若插在最后面若插在最后面*/ previousPtr-nextPtr=newPtr; newPtr-nextPtr=NULL; /注意不要遺漏本語句注意不要遺漏本語句 currentPtrpreviousPtr60 newPtr插入新結(jié)點插入新結(jié)點: 17 19 47 headPtr sPtr20 newPtr查找結(jié)果查找結(jié)果3：新結(jié)點插在鏈表中間：

42、新結(jié)點插在鏈表中間previousPtr=NULL; currentPtr=*sPtr;while(currentPtr!=NULL & currentPtr-datanextPtr;previousPtr currentPtr新結(jié)點插在鏈表中間新結(jié)點插在鏈表中間:if (previousPtr!=NULL & currentPtr!=NULL) /*若插在中間若插在中間*/ if (previousPtr=NULL) /*若插在最前面若插在最前面*/ else if (currentPtr=NULL) /*若插在最后面若插在最后面*/ else /*若插在中間若插在中間*/

43、previousPtr-nextPtr=newPtr; newPtr-nextPtr=currentPtr; 17 19 47 headPtrpreviousPtr currentPtr27 newPtr sPtr void insertNode(LISTNODEPTR * sPtr,int value) LISTNODEPTR newPtr, previousPtr, currentPtr; newPtr=malloc(sizeof(LISTNODE); if (newPtr!=NULL) newPtr-data=value; /*查找插入位置，結(jié)點將插在查找插入位置，結(jié)點將插在*previ

44、ousPtr和和*currentPtr之間之間*/ previousPtr=NULL; currentPtr=*sPtr; /*currentPtr指向鏈表頭結(jié)點指向鏈表頭結(jié)點*/while(currentPtr!=NULL & valuecurrentPtr-data) previousPtr=currentPtr; currentPtr=currentPtr-nextPtr; 基本操作基本操作4鏈表結(jié)點的插入鏈表結(jié)點的插入 /*插入新結(jié)點插入新結(jié)點*/ if (previousPtr=NULL) /*若插在最前面若插在最前面*/ newPtr-nextPtr=currentPtr;

45、 *sPtr=newPtr; else if (currentPtr=NULL) /*若插在最后面若插在最后面*/ previousPtr-nextPtr=newPtr; newPtr-nextPtr=NULL; else /*若插在中間若插在中間*/ previousPtr-nextPtr=newPtr; newPtr-nextPtr=currentPtr; 基本操作基本操作4鏈表結(jié)點的插入鏈表結(jié)點的插入 例例3：創(chuàng)建一個函數(shù)：創(chuàng)建一個函數(shù)： LISTNODEPTR createSortList() 功能：讀入一批數(shù)，以負數(shù)結(jié)束。將輸入的數(shù)據(jù)功能：讀入一批數(shù)，以負數(shù)結(jié)束。將輸入的數(shù)據(jù)組成升序

46、排序的有序鏈表并返回鏈表表頭結(jié)點指組成升序排序的有序鏈表并返回鏈表表頭結(jié)點指針。針。創(chuàng)建有序鏈表創(chuàng)建有序鏈表1/3 /*讀取正整數(shù)，以讀取正整數(shù)，以1結(jié)束，組成升序鏈表，返回指向鏈表頭結(jié)結(jié)束，組成升序鏈表，返回指向鏈表頭結(jié)點的指針點的指針*/LISTNODEPTR createSortList() int num; LISTNODEPTR headPtr=NULL; printf(input positive numbers,-1 to endn); scanf(%d,&num); while(num!=-1) insertNode(&headPtr, num);/*插入結(jié)點插

47、入結(jié)點*/ scanf(%d,&num); return headPtr;創(chuàng)建有序鏈表創(chuàng)建有序鏈表2/3 main() LISTNODEPTR headPtr=NULL; headPtr=createSortList(); /*創(chuàng)建有序鏈表創(chuàng)建有序鏈表*/ printList(headPtr); /*輸出鏈表輸出鏈表*/ destroyList(headPtr); /*釋放鏈表釋放鏈表*/創(chuàng)建有序鏈表創(chuàng)建有序鏈表3/3 基本操作基本操作5鏈表結(jié)點的刪除鏈表結(jié)點的刪除/*函數(shù)功能：刪除鏈表中值為函數(shù)功能：刪除鏈表中值為value的結(jié)點，的結(jié)點，sPtr接收接收指向鏈表頭結(jié)點的指針的地址，

48、若刪除成功，返回指向鏈表頭結(jié)點的指針的地址，若刪除成功，返回value，否則返回，否則返回-1*/int deleteNode(LISTNODEPTR * sPtr, int value) 查找待刪除的結(jié)點；查找待刪除的結(jié)點； 刪除結(jié)點；刪除結(jié)點； 基本操作基本操作5鏈表結(jié)點的刪除鏈表結(jié)點的刪除第第1步：查找待刪除結(jié)點：需要有指針指向待刪結(jié)步：查找待刪除結(jié)點：需要有指針指向待刪結(jié)點以及前驅(qū)結(jié)點點以及前驅(qū)結(jié)點17 19 47 headPtrpreviousPtr currentPtr9 sPtrpreviousPtr=NULL; currentPtr=*sPtr; /*currentPtr指向鏈

49、表頭結(jié)點指向鏈表頭結(jié)點*/*查找待刪除結(jié)點查找待刪除結(jié)點*/ while(currentPtr!=NULL & value!=currentPtr-data) previousPtr=currentPtr; currentPtr=currentPtr-nextPtr; 第第2步（步（1）：刪除結(jié)點）：刪除結(jié)點若刪除的是頭結(jié)點若刪除的是頭結(jié)點 int deleteNode(LISTNODEPTR * sPtr, int value)17 19 47 headPtrcurrentPtr9 刪除頭結(jié)點（刪除頭結(jié)點（if (currentPtr=*sPtr)）： *sPtr=currentPt

50、r-nextPtr基本操作基本操作5鏈表結(jié)點的刪除鏈表結(jié)點的刪除 sPtr 第第2步（步（2）：刪除結(jié)點）：刪除結(jié)點若刪除的是尾結(jié)點若刪除的是尾結(jié)點 int deleteNode(LISTNODEPTR * sPtr, int value)17 19 47 headPtr9 刪除尾結(jié)點刪除尾結(jié)點( if (currentPtr-nextPtr=NULL) )： previousPtr -nextPtr=NULL基本操作基本操作5鏈表結(jié)點的刪除鏈表結(jié)點的刪除 sPtrpreviousPtr currentPtr 第第2步（步（3）：刪除結(jié)點）：刪除結(jié)點若刪除的是中間結(jié)點若刪除的是中間結(jié)點 int

51、 deleteNode(LISTNODEPTR * sPtr, int value)17 19 47 headPtrpreviousPtr currentPtr9 刪除的是中間結(jié)點：刪除的是中間結(jié)點： previousPtr-nextPtr=currentPtr-nextPtr基本操作基本操作5鏈表結(jié)點的刪除鏈表結(jié)點的刪除 sPtr 基本操作基本操作5鏈表結(jié)點的刪除鏈表結(jié)點的刪除進一步分析：進一步分析：刪除的是尾結(jié)點：刪除的是尾結(jié)點： previousPtr -nextPtr=NULL 此時此時currentPtr-nextPtr值為值為NULL， 因此可寫為因此可寫為previousPtr

52、-nextPtr= currentPtr-nextPtr刪除的是中間結(jié)點：刪除的是中間結(jié)點： previousPtr-nextPtr=currentPtr-nextPtr因此，刪除尾結(jié)點和刪除中間結(jié)點的操作可以統(tǒng)一成：因此，刪除尾結(jié)點和刪除中間結(jié)點的操作可以統(tǒng)一成： previousPtr-nextPtr=currentPtr-nextPtr 基本操作基本操作5鏈表結(jié)點的刪除鏈表結(jié)點的刪除/*刪除值為刪除值為value的結(jié)點，若成功刪除，返回結(jié)點數(shù)據(jù)域值；否則的結(jié)點，若成功刪除，返回結(jié)點數(shù)據(jù)域值；否則返回返回1。sPtr用于接收指向鏈表頭接點指針的地址用于接收指向鏈表頭接點指針的地址*/int

53、 deleteNode(LISTNODEPTR * sPtr,int value) LISTNODEPTR previousPtr,currentPtr; previousPtr=NULL; currentPtr=*sPtr;/*將頭接點地址賦給將頭接點地址賦給currentPtr*/ /*查找待刪除結(jié)點，若找到，則由查找待刪除結(jié)點，若找到，則由currentPtr指向該結(jié)點指向該結(jié)點*/ while (currentPtr!=NULL & currentPtr-data!=value) previousPtr=currentPtr; currentPtr=currentPtr-nex

54、tPtr; 基本操作基本操作5鏈表結(jié)點的刪除鏈表結(jié)點的刪除 if (currentPtr!=NULL) /*如果找到要刪除的結(jié)點如果找到要刪除的結(jié)點*/ if ( previousPtr=NULL) /*刪除的是頭結(jié)點刪除的是頭結(jié)點*/ *sPtr=currentPtr-nextPtr;/*更新頭結(jié)點更新頭結(jié)點*/ else/*刪除的是中間結(jié)點或者尾結(jié)點刪除的是中間結(jié)點或者尾結(jié)點*/ previousPtr-nextPtr= currentPtr-nextPtr; free(currentPtr); /*釋放結(jié)點內(nèi)存釋放結(jié)點內(nèi)存*/ return value; else return -1;/

55、沒有找到符合條件的結(jié)點沒有找到符合條件的結(jié)點 帶頭結(jié)點的單鏈表操作帶頭結(jié)點的單鏈表操作 學(xué)習(xí)建立一個頭結(jié)點的方式簡化鏈表操作學(xué)習(xí)建立一個頭結(jié)點的方式簡化鏈表操作 頭結(jié)點中的數(shù)據(jù)成員無具體含義頭結(jié)點中的數(shù)據(jù)成員無具體含義 有了頭結(jié)點創(chuàng)建、插入、刪除時可以不用判斷有了頭結(jié)點創(chuàng)建、插入、刪除時可以不用判斷headptr是否為空是否為空 查找、輸出遍歷、排序鏈表從查找、輸出遍歷、排序鏈表從headptr-nextptr開始操作開始操作17 19 47 headPtr0 headPtr0 帶頭結(jié)點的空鏈表帶頭結(jié)點的空鏈表 練習(xí)練習(xí)1：編寫一個遞歸函數(shù)，逆序打印鏈表；編寫一個遞歸函數(shù)，逆序打印鏈表； 編寫

56、一個遞歸函數(shù)，順序打印鏈表；編寫一個遞歸函數(shù)，順序打印鏈表； 編寫一個遞歸函數(shù)，求鏈表中最大值所在結(jié)點；編寫一個遞歸函數(shù)，求鏈表中最大值所在結(jié)點； 遞歸逆序遍歷鏈表遞歸逆序遍歷鏈表/*函數(shù)功能：遞歸函數(shù)功能：遞歸逆序逆序遍歷鏈表，打印各結(jié)點的值。遍歷鏈表，打印各結(jié)點的值。 參數(shù)說明：指向結(jié)點的指針，接收鏈表頭接點的地址參數(shù)說明：指向結(jié)點的指針，接收鏈表頭接點的地址*/void printList(LISTNODEPTR headPtr)/思路：先打印后續(xù)結(jié)點，再打印頭結(jié)點思路：先打印后續(xù)結(jié)點，再打印頭結(jié)點 if(headPtr-nextPtr=NULL)/若這是最后一個結(jié)點若這是最后一個結(jié)點

57、這里這里headPtr不能為不能為NULL printf(%d,headPtr-data); else printList(headPtr-nextPtr);/先打印后面先打印后面 printf(“%d-”,headPtr-data); /最后打印頭結(jié)點最后打印頭結(jié)點 遞歸順序遍歷鏈表遞歸順序遍歷鏈表/*函數(shù)功能：遞歸函數(shù)功能：遞歸順序順序遍歷鏈表，打印各結(jié)點的值。遍歷鏈表，打印各結(jié)點的值。 參數(shù)說明：指向結(jié)點的指針，接收鏈表頭接點的地址參數(shù)說明：指向結(jié)點的指針，接收鏈表頭接點的地址*/void printList(LISTNODEPTR headPtr)/思路：思路：先打印頭結(jié)點，再打印后續(xù)

58、結(jié)點先打印頭結(jié)點，再打印后續(xù)結(jié)點 if(headPtr-nextPtr=NULL)/若這是最后一個結(jié)點若這是最后一個結(jié)點 printf(%d,headPtr-data); else printf(%d-,headPtr-data); printList(headPtr-nextPtr); 遞歸求鏈表中最大值所在結(jié)點遞歸求鏈表中最大值所在結(jié)點LISTNODEPTR findMax(LISTNODEPTR headPtr) LISTNODEPTR maxPtr ; if(headPtr-nextPtr=NULL)/若這是最后一個結(jié)點若這是最后一個結(jié)點 return headPtr; else ma

59、xPtr=findMax(headPtr-nextPtr);/*找后續(xù)結(jié)點中的最找后續(xù)結(jié)點中的最 大結(jié)點，由大結(jié)點，由maxPtr指向指向*/ return maxPtr-dataheadPtr-data? maxPtr:headPtr; 例例4：鏈表的逆序組織（要求通過修改指針域?qū)崿F(xiàn)）：鏈表的逆序組織（要求通過修改指針域?qū)崿F(xiàn)） LISTNODEPTR reverseList(LISTNODEPTR headPtr) 函數(shù)調(diào)用：函數(shù)調(diào)用：headPtrreverseList(headPtr);17 19 47 headPtr47 19 17 解題思路解題思路1：依次：依次讓讓currentPt

60、r指向鏈表指向鏈表的頭結(jié)點的頭結(jié)點;headPtr指向指向下一個結(jié)點；下一個結(jié)點；2. currentPtr指向結(jié)點組裝指向結(jié)點組裝到新鏈表中作為頭結(jié)點到新鏈表中作為頭結(jié)點;headPtr LISTNODEPTR reverseList(LISTNODEPTR headPtr) LISTNODEPTR newHeadPtr=NULL,currentPtr=NULL; while(headPtr!=NULL) /讓讓currentPtr指向鏈表的頭結(jié)點指向鏈表的頭結(jié)點;headPtr指向下一個結(jié)點指向下一個結(jié)點 currentPtr=headPtr; headPtr=headPtr-nextPtr; / currentPtr指向結(jié)點組裝到新鏈表中作為頭結(jié)點指向結(jié)點組裝到新鏈表中作為頭結(jié)點 if(newHeadPtr=NULL) newHeadPtr= currentPtr