中職C語言程序設(shè)計(jì)模塊十一課件

1、(中職）C語言程序設(shè)計(jì)模塊十一課件鏈表模塊1111.1鏈表的基本概念及要點(diǎn)11.1.1鏈表的基本概念（1）將若干數(shù)據(jù)項(xiàng)按一定的原則連接起來的表就稱為鏈表。（2）鏈表中的數(shù)據(jù)稱為結(jié)點(diǎn)（或節(jié)點(diǎn)）。任何結(jié)點(diǎn)都由兩部分組成：數(shù)據(jù)域（data）。指針域（next）。（3）鏈表的鏈接原則：前一個(gè)結(jié)點(diǎn)指向下一個(gè)結(jié)點(diǎn)，即前一個(gè)結(jié)點(diǎn)指針域保存下一個(gè)結(jié)點(diǎn)地址。只有通過前一個(gè)結(jié)點(diǎn)才能找到下一個(gè)結(jié)點(diǎn)。頭結(jié)點(diǎn)（也稱頭指針）一般不存放有效數(shù)據(jù)，只保存第1個(gè)結(jié)點(diǎn)的地址。頭結(jié)點(diǎn)不存放有效數(shù)據(jù)，主要是為了方便插入和刪除運(yùn)算的實(shí)現(xiàn)。若頭結(jié)點(diǎn)存放了有效數(shù)據(jù)，則其為事實(shí)上的第1個(gè)結(jié)點(diǎn)。通常把除頭結(jié)點(diǎn)外的其他結(jié)點(diǎn)稱為數(shù)據(jù)結(jié)點(diǎn)，第1數(shù)據(jù)

2、結(jié)點(diǎn)也稱為首結(jié)點(diǎn)。通常只對(duì)存放實(shí)際數(shù)據(jù)的數(shù)據(jù)結(jié)點(diǎn)進(jìn)行編號(hào)（從1開始）。11.1鏈表的基本概念及要點(diǎn)11.1.1鏈表的基本概念（4）頭結(jié)點(diǎn)是鏈表的起始結(jié)點(diǎn)，結(jié)點(diǎn)標(biāo)號(hào)為0。11.1鏈表的基本概念及要點(diǎn)11.1.1鏈表的基本概念（5）最末結(jié)點(diǎn)指針域值為“”，表示其指針值為空（NULL）。（6）結(jié)點(diǎn)空間由malloc()函數(shù)動(dòng)態(tài)獲取并進(jìn)行結(jié)點(diǎn)的創(chuàng)建。（7）頭結(jié)點(diǎn)是關(guān)鍵點(diǎn)，“抓住”了頭結(jié)點(diǎn)，就“抓住”了整個(gè)鏈表。鏈表示意圖如圖11-1所示。圖11-1鏈表11.1鏈表的基本概念及要點(diǎn)11.1.2鏈表結(jié)構(gòu)的定義及內(nèi)存空間的申請(qǐng)struct LNodeint data;/*數(shù)據(jù)域*/struct LNode

3、*next;/*指針域*/;struct LNode *p,*t; /*定義了兩個(gè)鏈表指針*/p=(struct LNode *)malloc(sizeof(struct LNode);/*申請(qǐng)內(nèi)存空間*/t=(struct LNode *)malloc(sizeof(structLNode);鏈表結(jié)構(gòu)（也稱結(jié)點(diǎn)結(jié)構(gòu)）定義示例。示例1：11.1鏈表的基本概念及要點(diǎn)11.1.2鏈表結(jié)構(gòu)的定義及內(nèi)存空間的申請(qǐng)typedef struct LNodeint data;/*數(shù)據(jù)域*/struct LNode *next;/*指針域*/NODE;/*定義了一個(gè)鏈表結(jié)構(gòu)類別名NODE*/NODE *p,*

4、t; /*用類別名定義兩個(gè)鏈表指針*/p=(NODE *)malloc(sizeof(NODE);/*申請(qǐng)內(nèi)存空間*/t=(NODE *)malloc(sizeof(NODE);示例2：11.1鏈表的基本概念及要點(diǎn)11.1.3鏈表的基本操作要點(diǎn)鏈表的操作主要靠“-”運(yùn)算符和指針域來實(shí)現(xiàn)。設(shè)若有模塊11.1.2的示例1和示例2的鏈表結(jié)構(gòu)，可以做以下簡(jiǎn)化的理解：（1）左為指針域，右為指向下一個(gè)結(jié)點(diǎn)：“t-next=p-next;”意為把p指向的下一個(gè)結(jié)點(diǎn)的地址保存到t的指針域?！皃=p-next;”意為指針p下移。（2）當(dāng)出現(xiàn)雙重“-”運(yùn)算符時(shí)：“p-next-data=3；”意為把常值3賦給p指

5、向的下一結(jié)點(diǎn)的數(shù)據(jù)域?！皃-next-datadata;”意為p指向的下一結(jié)點(diǎn)的數(shù)據(jù)域值小于t指向結(jié)點(diǎn)的數(shù)據(jù)域值。“p-next-datat-next-data;”意為p指向的下一結(jié)點(diǎn)的數(shù)據(jù)域值大于t指向的下一結(jié)點(diǎn)的數(shù)據(jù)域值。（3）鏈表操作往往須借助于多個(gè)鏈表指針，單一指針是不可能完成復(fù)雜操作的。11.2單鏈表11.2.1單鏈表的建立尾插法所謂尾插法，就是把剛創(chuàng)建的結(jié)點(diǎn)插入前一結(jié)點(diǎn)之后，最后給最末結(jié)點(diǎn)指針域賦空值即可。為了便于讀者學(xué)習(xí)、理解，在后面的學(xué)習(xí)中直接把鏈表指針稱為結(jié)點(diǎn)，事實(shí)上是指針指向結(jié)點(diǎn)。11.2單鏈表11.2.1單鏈表的建立尾插法【例11-1】學(xué)生成績(jī)鏈表頭結(jié)點(diǎn)為第1個(gè)數(shù)據(jù)結(jié)點(diǎn)。

6、#include #include struct LNode/*定義鏈表結(jié)構(gòu)(也可稱為結(jié)點(diǎn)結(jié)構(gòu)體)，數(shù)據(jù)域有姓名、班級(jí)和成績(jī)*/char name8;int class;int score4; /*語數(shù)外加專業(yè)4科成績(jī)*/struct LNode *next; /*指針域,指針域存放下一個(gè)結(jié)點(diǎn)的存儲(chǔ)位置(指針)*/;/*創(chuàng)建鏈表指針函數(shù)，返回鏈表指針，實(shí)際上是返回鏈表的頭指針*/struct LNode *create(int n)struct LNode *h,*p,*t; /*鏈表的創(chuàng)建一般來說需3個(gè)鏈表指針，一個(gè)頭（如h），一個(gè)尾（如t），一個(gè)動(dòng)態(tài)指針（如p），用于動(dòng)態(tài)獲取內(nèi)存空間*/1

7、1.2單鏈表11.2.1單鏈表的建立尾插法char xm8;/*對(duì)應(yīng)鏈表結(jié)構(gòu)中的數(shù)據(jù)域姓名成員*/int clas,a4;/*對(duì)應(yīng)鏈表結(jié)構(gòu)中的數(shù)據(jù)域班級(jí)和成績(jī)成員*/int i,j;h=NULL;/*關(guān)鍵句1：頭指針賦空值*/printf(Please input name,class and 4 score:n);for(i=n;i0;-i)p=(struct LNode *)malloc(sizeof(struct LNode); /*分配內(nèi)存空間,建立結(jié)點(diǎn)*/scanf(%s%d,xm,&clas);for(j=0;jname,xm);p-class=clas;for(j=0;jscor

8、ej=aj;11.2單鏈表11.2.1單鏈表的建立尾插法if(h=NULL)/*下面兩句為關(guān)鍵語句2*/h=p;/*理解為：如果頭為空，就把剛創(chuàng)建的結(jié)點(diǎn)轉(zhuǎn)為頭結(jié)點(diǎn)*/t=p;/*理解為：并把剛創(chuàng)建的結(jié)點(diǎn)轉(zhuǎn)為尾結(jié)點(diǎn)?？梢姷?個(gè)新結(jié)點(diǎn)必須具備雙重身份：既為頭又為尾。這兩句僅執(zhí)行1次，目的就是創(chuàng)建頭結(jié)點(diǎn)*/elset-next=p; /*這兩句為關(guān)鍵語句3：從第2次創(chuàng)建的結(jié)點(diǎn)開始，其地址保存于上一結(jié)點(diǎn)指針域*/t=p;/*新建結(jié)點(diǎn)又轉(zhuǎn)為尾結(jié)點(diǎn)*/t-next=NULL;/*關(guān)鍵語句4：結(jié)點(diǎn)創(chuàng)建完畢，給最后一個(gè)結(jié)點(diǎn)指針域賦空*/return h;/*關(guān)鍵語句5：必須返回頭結(jié)點(diǎn)*/11.2單鏈表11.2

9、.1單鏈表的建立尾插法int main()int n,j;struct LNode *q;/*定義一個(gè)鏈表指針,用于接收函數(shù)返回來的值*/printf(Input you want to create point:);scanf(%d,&n);q=create(n);/*調(diào)用create()函數(shù),上面函數(shù)返回的是頭指針值*/printf(nametclasstChinesetMathstEnglisetProfessialn);while(q)printf(%st%dt ,q-name,q-class); /*輸出數(shù)據(jù)域*/for(j=0;jscorej);putchar(n);q=q-nex

10、t; /*關(guān)鍵語句6：指針位移指向下一結(jié)點(diǎn)*/printf(n);free(q);11.2單鏈表11.2.1單鏈表的建立尾插法Input you want to create point:3Please input name,class and 4 score:Lucy 3 89 87 85 65Jack 3 69 78 95 64Lily 3 87 68 92 91name class Chinese Maths English ProfessionLucy 3 89 87 85 65Jack 3 69 78 95 64Lily 3 87 68 92 91創(chuàng)建3個(gè)結(jié)點(diǎn)，輸入/輸出數(shù)據(jù)如下：1

11、1.2單鏈表11.2.1單鏈表的建立尾插法上述鏈表尾插法創(chuàng)建過程如圖11-2所示。創(chuàng)建上面的學(xué)生鏈表時(shí)，若要保持頭結(jié)點(diǎn)數(shù)據(jù)域?yàn)榭?，?yīng)怎么修改呢？【例11-1】是把整個(gè)新建的結(jié)點(diǎn)轉(zhuǎn)為了頭結(jié)點(diǎn)，因而頭結(jié)點(diǎn)成了事實(shí)上的第1個(gè)數(shù)據(jù)結(jié)點(diǎn)。現(xiàn)在要保持其為空，就不能這樣操作，應(yīng)該把新建的結(jié)點(diǎn)地址保存在頭結(jié)點(diǎn)的指針域，這樣就避免了整體轉(zhuǎn)換，頭結(jié)點(diǎn)有了新建結(jié)點(diǎn)的地址，而其數(shù)據(jù)域仍然為空。圖11-2【例11-1】鏈表尾插法示意圖11.2單鏈表11.2.1單鏈表的建立尾插法#include #include struct LNodechar name8;int class;int score4;struct LNo

12、de *next;struct LNode *create(int n)struct LNode *h,*p,*t;char xm8;int clas,a4;int i,j;h-next=NULL;/*關(guān)鍵語句1：給頭結(jié)點(diǎn)指針域賦空*/11.2單鏈表11.2.1單鏈表的建立尾插法printf(Please input name,class and 4 score:n);for(i=n;i0;-i)p=(struct LNode *)malloc(sizeof(struct LNode); scanf(%s%d,xm,&clas);for(j=0;jname,xm);p-class=clas;f

13、or(j=0;jscorej=aj;if(h-next=NULL)h-next=p;/*關(guān)鍵語句2：新建結(jié)點(diǎn)地址保存到頭結(jié)點(diǎn)指針域。僅第1次新建時(shí)執(zhí)行*/t=p;11.2單鏈表11.2.1單鏈表的建立尾插法elset-next=p; t=p; t-next=NULL;return h;int main()int n,j;struct LNode *q;printf(Input you want to create point:);scanf(%d,&n);q=create(n);q=q-next;/*關(guān)鍵語句3：頭結(jié)點(diǎn)數(shù)據(jù)域?yàn)榭?，因而要從?個(gè)數(shù)據(jù)結(jié)點(diǎn)開始*/11.2單鏈表11.2.1單鏈表的

14、建立尾插法printf(nametclasstChinesetMathstEnglisetProfessialn);while(q)printf(%st%dt ,q-name,q-class);for(j=0;jscorej);putchar(n);q=q-next;printf(n);11.2單鏈表11.2.1單鏈表的建立尾插法頭結(jié)點(diǎn)為空的尾插法創(chuàng)建過程如圖11-3所示。圖11-3頭結(jié)點(diǎn)為空的尾插法創(chuàng)建過程11.2單鏈表11.2.2單鏈表的建立頭插法所謂頭插法，就是把新建結(jié)點(diǎn)依次插入前一結(jié)點(diǎn)之前，則原頭結(jié)點(diǎn)變?yōu)樽钅┙Y(jié)點(diǎn)，最后建立的結(jié)點(diǎn)變?yōu)榈?結(jié)點(diǎn)。這個(gè)過程剛好與尾插法是相反的。頭插法的結(jié)點(diǎn)排

15、列按照堆的從低到高的生長(zhǎng)方向，輸出時(shí)將按從高到低的地址輸出，即輸入時(shí)的反序輸出。11.2單鏈表11.2.2單鏈表的建立頭插法【例11-2】編寫一個(gè)鏈表，讀入一行字符，每個(gè)字符存入一個(gè)結(jié)點(diǎn)，按輸入的順序建立一個(gè)鏈表的結(jié)點(diǎn)序列，然后按相反的順序輸出，并釋放全部結(jié)點(diǎn)。該題用頭插法即可實(shí)現(xiàn)：#include #include struct Nodechar ch;struct Node *next;struct Node *h=NULL; /*關(guān)鍵語句1： 頭已賦空，將作為最末結(jié)點(diǎn)*/struct Node *create()char c;struct Node *p;while(c=getchar(

16、)!=n)p=(struct Node*)malloc(sizeof(struct Node);p-ch=c;11.2單鏈表11.2.2單鏈表的建立頭插法p-next=h; /*關(guān)鍵語句2：頭保存到新建結(jié)點(diǎn)指針域*/h=p;/*關(guān)鍵語句3：新建結(jié)點(diǎn)轉(zhuǎn)為新的頭*/return h;int main()struct Node *q,*t;q=create();printf(The result is:n);while(q)printf(%c ,q-ch);free(q);/如輸入 abcde，則輸出e d c b aq=q-next;11.2單鏈表11.2.2單鏈表的建立頭插法頭插法創(chuàng)建鏈表示意圖

17、如圖11-4所示。圖11-4頭插法創(chuàng)建鏈表示意圖11.2單鏈表11.2.3單鏈表結(jié)點(diǎn)逆置所謂單鏈表結(jié)點(diǎn)逆置，指的是把結(jié)點(diǎn)倒轉(zhuǎn)，頭變尾，尾變頭。例如，輸入“2 4 1”，輸出“1 4 2”。#include #include typedef struct LNode int data;struct LNode *next;Node;/*鏈表結(jié)構(gòu)類別名，定義類別名，可以省不少事*/ Node *h;/*尾插法鏈表建立（創(chuàng)建步驟同前，略）*/Node *create(int n)11.2單鏈表11.2.3單鏈表結(jié)點(diǎn)逆置 /*-創(chuàng)建鏈表逆置函數(shù)-*/Node *reverse(Node *h)/*在以

18、h為頭結(jié)點(diǎn)的鏈表中實(shí)現(xiàn)逆序*/Node *p,*t;p=h;/*關(guān)鍵語句1：先安排p在頭結(jié)點(diǎn)位置*/t=p-next;/*關(guān)鍵語句2：再把p指向的下一結(jié)點(diǎn)用t來表示*/p-next=NULL;/*關(guān)鍵語句3：把p(此時(shí)尚未進(jìn)入循環(huán),實(shí)際就是頭結(jié)點(diǎn))的指針域賦空,斷掉其與后面結(jié)點(diǎn)的連接。事實(shí)上,它將變?yōu)樽詈笠粋€(gè)結(jié)點(diǎn)*/while(t)/*開始循環(huán)*/p=t;/*關(guān)鍵語句4：先把t轉(zhuǎn)換為p*/t=t-next;/*關(guān)鍵語句5：t再變?yōu)橄乱唤Y(jié)點(diǎn)*/p-next=h;/*關(guān)鍵語句6：把頭結(jié)點(diǎn)的地址(如100)保存到p的指針域*/h=p;/*關(guān)鍵語句7： 再把p轉(zhuǎn)為新的頭結(jié)點(diǎn)*/return h;/*返

19、回頭結(jié)點(diǎn)，此時(shí)的h已不是原鏈表的頭結(jié)點(diǎn)了*/11.2單鏈表11.2.3單鏈表結(jié)點(diǎn)逆置int main()int n;Node *q;printf(Input you want to create point:); scanf(%d,&n);q=create(n);q=reverse(q);/*結(jié)點(diǎn)逆置*/printf(The result is:);while(q)printf(%d ,q-data);q=q-next; 輸入/輸出示例：Input you want to create point:5Input number:1 5 6 2 4The result is:4 2 6 5 111

20、.2單鏈表11.2.3單鏈表結(jié)點(diǎn)逆置單鏈表逆置實(shí)現(xiàn)原理如圖11-5所示。圖11-5單鏈表逆置實(shí)現(xiàn)原理11.2單鏈表11.2.4單鏈表結(jié)點(diǎn)查詢、插入和刪除1.單鏈表結(jié)點(diǎn)查詢【例11-3】結(jié)點(diǎn)查詢實(shí)例。在一個(gè)頭為空的單鏈表中查詢某個(gè)數(shù)值。找到便輸出該結(jié)點(diǎn)的位置和查找的值，找不到便提示“Can not find your need!”。#include #include typedef struct LNodeint data;struct LNode *next;NODE;NODE *h;/*建立頭為空的鏈表*/NODE *create(int n)NODE *p,*t;int a,i;h=(NO

21、DE *)malloc(sizeof(NODE);11.2單鏈表11.2.4單鏈表結(jié)點(diǎn)查詢、插入和刪除h-next=NULL;printf(Input every data:);for(i=n;i0;-i)p=(NODE *)malloc(sizeof(NODE);scanf(%d,&a);p-data=a;if(h-next=NULL)h-next=p; t=p; elset-next=p; t=p; t-next=NULL;return h;11.2單鏈表11.2.4單鏈表結(jié)點(diǎn)查詢、插入和刪除/*-結(jié)點(diǎn)查詢函數(shù)的實(shí)現(xiàn)，返回地址，為指針函數(shù)-*/void *search(NODE *h,in

22、t score ）/*在以h為頭的鏈表中查找值等于score的結(jié)點(diǎn)*/NODE *p;int i=0;/*頭為空，標(biāo)號(hào)為0*/p=h;/*借助指針p*/while(p!=NULL&p-data!=score)/*關(guān)鍵語句1：循環(huán)條件*/p=p-next; /*關(guān)鍵語句2：指針下移。如果有匹配的值，p將剛好到達(dá)這個(gè)結(jié)點(diǎn)*/i+;11.2單鏈表11.2.4單鏈表結(jié)點(diǎn)查詢、插入和刪除if(p-data!=score)printf(Can not find you need!n);elseprintf(Result is:NO.%djd-%d,i,p-data);putchar(n);int main

23、()int n,score;NODE *q;printf(Input you want to create point:);scanf(%d,&n);q=create(n);printf(nInput you want to find score:);scanf(%d,&score);search(h,score);輸入/輸出如下：Input you want to create point:3Input every data:478 524 586Input you want to find score:524Result is:NO.2jd-52411.2單鏈表11.2.4單鏈表結(jié)點(diǎn)查詢、

24、插入和刪除2.單鏈表結(jié)點(diǎn)插入【例11-4】在一個(gè)頭為第1數(shù)據(jù)結(jié)點(diǎn)的單鏈表中的指定位置插入一個(gè)新的結(jié)點(diǎn)。#include #include #include typedef struct LNodechar name10;int class;int data;struct LNode *next;NODE;NODE *h;11.2單鏈表11.2.4單鏈表結(jié)點(diǎn)查詢、插入和刪除/*-鏈表創(chuàng)建函數(shù)略-*/ NODE *create(int n)/*-插入一個(gè)結(jié)點(diǎn)的實(shí)現(xiàn)-*/int insert(NODE *h,int i)/*在以h為頭的鏈表中，在第i處插入一個(gè)結(jié)點(diǎn)*/int j; NODE *p,*

25、t;p=(NODE *)malloc(sizeof(NODE); printf(Please input name,class,data:);scanf(%s%d%d,p-name,&p-clas,&p-data); /*給新結(jié)點(diǎn)數(shù)據(jù)域輸入數(shù)據(jù)*/if(i1)return 0;t=h;/*關(guān)鍵語句1*/j=1;11.2單鏈表11.2.4單鏈表結(jié)點(diǎn)查詢、插入和刪除while(t!=NULL&ji-1)/*關(guān)鍵語句2：注意這里條件的變化jnext;j+;if(t=NULL)return 0;if(i=1)/*關(guān)鍵語句3：如果要插在頭結(jié)點(diǎn)前*/p-next=t;h=p;else/*關(guān)鍵語句4：其他情

26、況的統(tǒng)一插入法*/p-next=t-next;t-next=p;printf(The new order is:n);printf(NametClasstScoren);11.2單鏈表11.2.4單鏈表結(jié)點(diǎn)查詢、插入和刪除t=h;/*關(guān)鍵語句5：因?yàn)轭^是首結(jié)點(diǎn)，故需從頭開始*/while(t)printf(%st%dt%dn,t-name,t-class,t-data);t=t-next;return 1;int main()int n,i,c;NODE *q;printf(Input you want to create point:);scanf(%d,&n);q=create(n);pr

27、intf(Input you want to insert place:);scanf(%d,&i);c=insert(h,i);printf( return %d-Insert successful!n,c);else11.2單鏈表11.2.4單鏈表結(jié)點(diǎn)查詢、插入和刪除printf( return %d-Insert fail!n,c);插入示例如下：Input you want to create point:3Input name,class and score:Jack 3 547Input name,class and score:Lucy 3 654Input name,class

28、 and score:Lily 3 624Input you want to insert place:2Please input name,class，data:David 3 586The new order is:NameClassScoreJack3547David3586Lucy3654Lily3624return 1 -Insert successful!11.2單鏈表11.2.4單鏈表結(jié)點(diǎn)查詢、插入和刪除結(jié)點(diǎn)插入示意圖如圖11-6所示。圖11-6結(jié)點(diǎn)插入示意圖11.2單鏈表11.2.4單鏈表結(jié)點(diǎn)查詢、插入和刪除3.單鏈表的結(jié)點(diǎn)刪除【例11-5】在一個(gè)頭為第1數(shù)據(jù)結(jié)點(diǎn)的鏈表中刪除指

29、定位置的結(jié)點(diǎn)。#include #include #include typedef struct LNodechar name10;int class;int data;struct LNode *next; NODE;NODE *h;/*-鏈表創(chuàng)建函數(shù)略-*/ NODE *create(int n)11.2單鏈表11.2.4單鏈表結(jié)點(diǎn)查詢、插入和刪除/*-刪除一個(gè)結(jié)點(diǎn)的實(shí)現(xiàn)-*/int delnode(NODE *h,int i)NODE *p,*t;int j;if(i1）return 0;t=h;j=1;while(t!=NULL&jnext;j+;11.2單鏈表11.2.4單鏈表結(jié)點(diǎn)查

30、詢、插入和刪除if(t=NULL）return 0;if(i=1) h=h-next;elsep=t-next;t-next=p-next;printf(The new order is:n);printf(NametClasstScoren);t=h;while(t)printf(%st%dt%dn,t-name,t-class,t-data);t=t-next;free(p);return 1;11.2單鏈表11.2.4單鏈表結(jié)點(diǎn)查詢、插入和刪除ain()int n,i,c;NODE *q;printf(Input you want to create point:);scanf(%d,&

31、n);q=create(n);printf(Input you want to delete jd:);scanf(%d,&i);c=delnode(h,i);if(c=1) printf( return %d-Delete successful!n,c);else printf( return %d-Delete fail!n,c);11.2單鏈表11.2.4單鏈表結(jié)點(diǎn)查詢、插入和刪除刪除示例如下：Input you want to create point:3Input name,class and score:Jack 2 56Input name,class and score:Luc

32、y 2 65Input name,class and score:Lily 3 67Input you want to delete jd:3The new order is:NameClassScoreJack 2 56Lucy 2 65return 1-Delete succesful!11.2單鏈表11.2.4單鏈表結(jié)點(diǎn)查詢、插入和刪除結(jié)點(diǎn)刪除示意圖如圖11-7所示。圖11-7結(jié)點(diǎn)刪除示意圖11.2單鏈表11.2.5單鏈表的排序【例11-6】用尾插法建立一個(gè)簡(jiǎn)單的鏈表,并將鏈表中的數(shù)據(jù)按升序輸出到顯示器上。程序的思路是：遍歷鏈表，找到最小結(jié)點(diǎn)；把找到的結(jié)點(diǎn)放入有序鏈表；把找到的結(jié)點(diǎn)從原鏈

33、表中刪除。循環(huán)執(zhí)行這三個(gè)步驟直到工作完成。#include #include typedef struct LNode int data;struct LNode *next;Node; Node *h;/*-創(chuàng)建鏈表-*/Node *create(int n)Node *p,*t; int a,i;11.2單鏈表11.2.5單鏈表的排序h=NULL;printf(Input number:);for(i=n;i0;-i)p=(Node *)malloc(sizeof(Node); scanf(%d,&a);p-data=a;if(h=NULL)h=p;t=p;elset-next=p; t=

34、p; t-next=NULL;return h;/*-創(chuàng)建排序函數(shù)-*/Node *line(Node *h)/*在以h為頭結(jié)點(diǎn)的鏈表中排序*/11.2單鏈表11.2.5單鏈表的排序Node *top;/*排序后有順序鏈表的表頭指針*/Node *p_tail;/*排序后有順序鏈表的表尾指針*/Node *pmin_before;/*保留數(shù)值最小的結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的指針*/Node *pmin;/*用于存儲(chǔ)最小結(jié)點(diǎn)*/Node *p;/*當(dāng)前比較的結(jié)點(diǎn)*/top=NULL;/*新表頭指針賦空值*/while(h!=NULL)/*在while里要循環(huán)完成三個(gè)步驟*/*第一個(gè)步驟，遍歷，找到最小結(jié)點(diǎn)

35、*/for(p=h,pmin=h;p-next!=NULL;p=p-next)/*關(guān)鍵語句1：循環(huán)遍歷原鏈表*/if(p-next-datadata）/*如果p指向的下一個(gè)結(jié)點(diǎn)的數(shù)據(jù)域小于當(dāng)前數(shù)據(jù)域值*/pmin_before=p; /*關(guān)鍵語句2：數(shù)值最小的結(jié)點(diǎn)的前一結(jié)點(diǎn)p保存到pmin_before*/pmin=p-next;/*關(guān)鍵語句3：數(shù)值最小的結(jié)點(diǎn)保存到pmin*/ 11.2單鏈表11.2.5單鏈表的排序/*第二步驟，把找到值放入有序鏈表中，其過程與新建鏈表一致*/if(top=NULL)top=pmin;p_tail=pmin;elsep_tail-next=pmin;p_tai

36、l=pmin;/*第三步驟:根據(jù)判斷安排該結(jié)點(diǎn)離開原鏈表*/if(pmin=h)/*關(guān)鍵語句4：如果找到的最小結(jié)點(diǎn)就是第一個(gè)結(jié)點(diǎn)*/h=h-next;/*刪除第一個(gè)結(jié)點(diǎn)：第二個(gè)結(jié)點(diǎn)代替第一個(gè)結(jié)點(diǎn)*/elsepmin_before-next=pmin-next; /*關(guān)鍵語句5：最小結(jié)點(diǎn)后面的那個(gè)結(jié)點(diǎn)（跳過最小結(jié)點(diǎn)）直接保存到最小結(jié)點(diǎn)之前的那個(gè)結(jié)點(diǎn)*/*while外循環(huán)結(jié)束處*/if(top!=NULL)11.2單鏈表11.2.5單鏈表的排序p_tail-next=NULL;/*得到有序鏈表top(頭指針),給最后一個(gè)結(jié)點(diǎn)的next域賦空*/h=top;/*把新鏈表頭指針轉(zhuǎn)換為h*/return

37、 h;int main()int n;Node *q; printf(Input you want to create point:);scanf(%d,&n);q=create(n);printf(Output old order:n);while(q)printf(%d,q-data);q=q-next;printf(n);q=line(h);11.2單鏈表11.2.5單鏈表的排序printf(Output new order:n);while(q)printf(%d,q-data);q=q-next; printf(n); 輸入/輸出示例如下：Input you want to crea

38、te point:5Input number:9 1 4 7 3Output old order:91473Output new order:1347911.2單鏈表11.2.5單鏈表的排序鏈表排序三步法圖示如圖11-8所示。圖11-8鏈表排序三步法圖示11.3雙 向 鏈 表雙向鏈表的建立單向鏈表只能單向下指，只有一個(gè)方向，雙向鏈表則不然，雙向鏈表具有三部分：（1）前驅(qū)指針域：該指針域存放前一結(jié)點(diǎn)的地址。（2）數(shù)據(jù)域。（3）后繼指針域：存放下一結(jié)點(diǎn)的地址。相對(duì)于單向鏈表，雙向鏈表多了一個(gè)指針域：前驅(qū)指針域，如圖11-所示。圖11-9雙向鏈表11.4循 環(huán) 鏈 表循環(huán)鏈表與單鏈表的操作方法僅有細(xì)

39、微的差別。（1）在創(chuàng)建鏈表時(shí)，最后一個(gè)結(jié)點(diǎn)的指針域保存的是頭結(jié)點(diǎn)地址(不再是空值)。（2）若頭不為空，輸出時(shí)先輸出首結(jié)點(diǎn)；若頭為空，正常輸出。（3）循環(huán)遍歷鏈表結(jié)點(diǎn)時(shí)的判斷值不再以NULL為條件，而是以不等于鏈表的頭指針為條件。循環(huán)鏈表圖示如圖11-10所示。圖11-10循環(huán)鏈表圖示11.4循 環(huán) 鏈 表【例11-7】循環(huán)鏈表的創(chuàng)建與輸出（頭為第1數(shù)據(jù)結(jié)點(diǎn)）。#include #include typedef struct LNodeint data;struct LNode *next; Node;Node *h;Node *create(int n)Node *p,*t;int a;int

40、 i;h=NULL;printf(Input number:);for(i=n;i0;-i)p=(Node *)malloc(sizeof(Node);11.4循 環(huán) 鏈 表scanf(%d,&a);p-data=a;if(h=NULL)h=p;t=p;elset-next=p; t=p;t-next=h; /*關(guān)鍵語句1：創(chuàng)建鏈表時(shí)末結(jié)點(diǎn)指針域保存頭的地址*/return h;int main()int n;Node *q;printf(Input you want to create point:);scanf(%d,&n);q=create(n);11.4循 環(huán) 鏈 表h=q;print

41、f(The result is:);printf(%d ,q-data); /*關(guān)鍵語句2：頭為第一數(shù)據(jù)結(jié)點(diǎn)，先輸頭*/q=q-next; /*關(guān)鍵語句3：指針移到第2結(jié)點(diǎn)位置*/while(q!=h)/*關(guān)鍵語句4*/printf(%d ,q-data);q=q-next;（1）結(jié)構(gòu)體數(shù)組各成員在內(nèi)存中是連續(xù)存儲(chǔ)的，即其地址是連續(xù)的，因而方便查詢，但是不方便插入和移動(dòng)。（2）鏈表各結(jié)點(diǎn)是離散存儲(chǔ)的，方便移動(dòng)和插入，但不方便查詢。11.5鏈表和結(jié)構(gòu)體數(shù)組的區(qū)別11.5鏈表和結(jié)構(gòu)體數(shù)組的區(qū)別【例11-8】結(jié)構(gòu)體中的指針成員。struct nodeint n;struct node *next;x=10,x+1,20,x