C程序設(shè)計(jì)第九章ppt西工大

1第9章鏈表快速排序法A[1]A[N]2關(guān)鍵數(shù)據(jù)一趟快速排序：將所有比關(guān)鍵數(shù)據(jù)小的數(shù)據(jù)放在它左邊，所有比關(guān)鍵數(shù)據(jù)大的數(shù)據(jù)放在它右邊i=1，j=N33456781233719ij1）利用j從后向前掃描，找到第一個(gè)比關(guān)鍵數(shù)據(jù)小的數(shù)，交換1956781233734ij2）利用i從前向后掃描，找到第一個(gè)比關(guān)鍵數(shù)據(jù)大的數(shù)，交換19

34781233756ij3）重復(fù)（1）即利用j從后向前掃描，找到第一個(gè)比關(guān)鍵數(shù)據(jù)小的數(shù)，交換19

778123334

56419

778123334

5619

7

34123378

5619

7

331234

78

56條件i<j不滿足了，一趟排序結(jié)束19

7

331234

78

56遞歸遞歸5voidquicksort(inta[],intleft,intright){

inti,j,temp;i=left;j=right;temp=a[left];

if(left>=right)return;while(i<j){

while(a[j]>=temp&&j>i)j--;

if(j>i)a[i++]=a[j];

while(a[i]<=temp&&j>i)i++;

if(j>i)a[j--]=a[i];

}

a[i]=temp;

quicksort(a,left,i-1);

quicksort(a,i+1,right);}6intmain()

{

inta[7]={17,2,6,12,1,9,5};

inti;

quicksort(a,0,6);

/*排好序的結(jié)果*/

for(i=0;i<7;i++)

printf("%4d",a[i]);return0;

}7第9章鏈表9.1鏈表概述9.2鏈表的創(chuàng)建9.3鏈表的運(yùn)算9.4結(jié)點(diǎn)的插入與刪除8本知識(shí)點(diǎn)在本課程知識(shí)體系中地位鏈表是一種常見的重要的數(shù)據(jù)結(jié)構(gòu)，它是動(dòng)態(tài)的進(jìn)行內(nèi)存存儲(chǔ)分配的一種結(jié)構(gòu)，存儲(chǔ)空間能動(dòng)態(tài)進(jìn)行增長(zhǎng)或縮小的數(shù)據(jù)結(jié)構(gòu)。鏈表主要用于兩個(gè)目的：一是建立不定長(zhǎng)度的數(shù)組。二是鏈表可以在不重新安排整個(gè)存儲(chǔ)結(jié)構(gòu)的情況下，方便且迅速地插入和刪除數(shù)據(jù)元素。9例如：建立一個(gè)學(xué)生管理程序，要求實(shí)現(xiàn)學(xué)生的數(shù)據(jù)動(dòng)態(tài)錄入、查詢和刪除鏈表概述2006-2007學(xué)年第二學(xué)期成績(jī)表序號(hào)姓名性別高等數(shù)學(xué)大學(xué)英語(yǔ)大學(xué)物理平均分總評(píng)1李亦錚女89969493.0優(yōu)秀2李凌飛男98878991.3優(yōu)秀3馬云燕女84938687.7優(yōu)秀4陳牧笛女84898686.3優(yōu)秀5林溢洋女85868184.0良好插入新數(shù)據(jù)刪除問題特點(diǎn)：事先不確定學(xué)生人數(shù)，如果采用事先確定長(zhǎng)度的存儲(chǔ)結(jié)構(gòu)，將會(huì)帶來存儲(chǔ)空間的浪費(fèi)必須用動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)存放數(shù)據(jù)10程序中存放大量數(shù)據(jù)：鏈表和數(shù)組數(shù)組存放數(shù)據(jù)：必須事先定義固定的長(zhǎng)度（即元素個(gè)數(shù)數(shù)組存放數(shù)據(jù)：物理存儲(chǔ)單元要求在內(nèi)存中分配連續(xù)存儲(chǔ)空間鏈表存放數(shù)據(jù)：可以根據(jù)需要，動(dòng)態(tài)開辟內(nèi)存單元。鏈表存放數(shù)據(jù)：物理存儲(chǔ)單元非連續(xù)，非順序的存儲(chǔ)結(jié)構(gòu)11鏈表：是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。節(jié)點(diǎn)節(jié)點(diǎn)：數(shù)據(jù)+指針數(shù)據(jù):存放數(shù)據(jù)存儲(chǔ)單元指針：指示后繼元素存儲(chǔ)位置129.1.1鏈表的概念一種稱為結(jié)點(diǎn)（node）的數(shù)據(jù)類型：這個(gè)結(jié)構(gòu)體類型中，data成員表示數(shù)據(jù)域，代表結(jié)點(diǎn)的數(shù)據(jù)信息。typedefstructtagNODE{//結(jié)點(diǎn)數(shù)據(jù)類型

ElemTypedata;//數(shù)據(jù)域

structtagNODE*link;//指針域}NODE;例如：節(jié)點(diǎn)的構(gòu)成上圖每個(gè)節(jié)點(diǎn)具有如下結(jié)構(gòu)體類型：

structtagSTU{longnum;floatscore;structertagSTU*next;};//鏈節(jié)成員其中：成員num、score用于存放一個(gè)節(jié)點(diǎn)的具體數(shù)據(jù)；成員next是指針類型，用于存放下一節(jié)點(diǎn)指針，最后一個(gè)節(jié)點(diǎn)的next成員存放空指針NULL；成員next是指向與自身同一類型的結(jié)構(gòu)，這種結(jié)構(gòu)稱為自引用結(jié)構(gòu)。(只有指針成員可自引用)動(dòng)態(tài)鏈表的節(jié)點(diǎn)是在運(yùn)行時(shí)動(dòng)態(tài)生成的。

動(dòng)態(tài)內(nèi)存分配和釋放建立和維護(hù)動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)需要實(shí)現(xiàn)動(dòng)態(tài)內(nèi)存分配；如在鏈表中插入節(jié)點(diǎn)需要先申請(qǐng)一段存儲(chǔ)區(qū)域，而刪除一個(gè)節(jié)點(diǎn)需要釋放該節(jié)點(diǎn)原先占用的存儲(chǔ)區(qū)域，這可由標(biāo)準(zhǔn)函數(shù)實(shí)現(xiàn)。內(nèi)存分配函數(shù)原形：

void*malloc(unsignedsize);功能：申請(qǐng)長(zhǎng)度為size個(gè)字節(jié)的內(nèi)存空間；若申請(qǐng)成功，返回存儲(chǔ)塊起始指針，該指針類型為

void*；否則返回空指針(NULL)。內(nèi)存釋放函數(shù)原形：voidfree(void*p);功能：釋放p所指向的內(nèi)存塊。包含文件：malloc.h、stdlib.h中均有其原型聲明。鏈表的類型單鏈表：每個(gè)節(jié)點(diǎn)只有一個(gè)指向后繼節(jié)點(diǎn)的指針雙向鏈表：每個(gè)節(jié)點(diǎn)有兩個(gè)用于指向其它節(jié)點(diǎn)的指針；一個(gè)指向前趨節(jié)點(diǎn)，一個(gè)指向后繼節(jié)點(diǎn)循環(huán)鏈表：使最后一個(gè)節(jié)點(diǎn)的指針指向頭節(jié)點(diǎn)鏈表構(gòu)造方式用多個(gè)結(jié)構(gòu)體變量可構(gòu)成——靜態(tài)鏈表將動(dòng)態(tài)申請(qǐng)空間而建立的節(jié)點(diǎn)鏈接——?jiǎng)討B(tài)鏈表采用動(dòng)態(tài)鏈表的意義與定長(zhǎng)數(shù)據(jù)結(jié)構(gòu)數(shù)組相比，鏈表能更好地利用內(nèi)存，按需分配和釋放存儲(chǔ)空間。在鏈表中插入或刪除一個(gè)節(jié)點(diǎn)，只需改變某節(jié)點(diǎn)“鏈節(jié)”成員的指向，而不需要移動(dòng)其它節(jié)點(diǎn)，相對(duì)數(shù)組元素的插入和刪除效率高。即：鏈表特別適合于對(duì)大線性表頻繁插入和刪除元素、或數(shù)據(jù)域成員數(shù)目不定的數(shù)據(jù)結(jié)構(gòu)。17鏈表類型--單向鏈表：包含兩個(gè)域，一個(gè)信息域和一個(gè)指針域。這個(gè)鏈接指向列表中的下一個(gè)節(jié)點(diǎn)，而最后一個(gè)節(jié)點(diǎn)則指向一個(gè)空值18鏈表類型--雙向鏈表：每個(gè)節(jié)點(diǎn)有兩個(gè)指針域：一個(gè)指向前一個(gè)節(jié)點(diǎn)；而另一個(gè)指向下一個(gè)節(jié)點(diǎn)19鏈表類型—循環(huán)鏈表：首節(jié)點(diǎn)和末節(jié)點(diǎn)被連接在一起用單鏈表實(shí)現(xiàn)雙向鏈表209.1.1鏈表的概念可以看出，鏈表是一種物理存儲(chǔ)非連續(xù)（非順序）的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針域?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(diǎn)組成，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成，因而鏈表可以動(dòng)態(tài)增長(zhǎng)或縮短。同時(shí)，結(jié)點(diǎn)是按指針域連接起來的，插入或刪除結(jié)點(diǎn)非常簡(jiǎn)便和迅速。通常，鏈表包含創(chuàng)建、遍歷、插入、刪除等運(yùn)算。219.1.2單鏈表與雙鏈表1．單鏈表單鏈表每個(gè)結(jié)點(diǎn)包含一個(gè)指向直接后繼結(jié)點(diǎn)的指針域，其形式為：next指向直接后繼結(jié)點(diǎn)，由它構(gòu)成了一條鏈。typedefstructtagLNode{//單鏈表結(jié)點(diǎn)類型

ElemTypedata;//數(shù)據(jù)域

structtagLNode*next;//指針域：指向直接后繼結(jié)點(diǎn)}LNode,*LinkList;//LNode為單鏈表結(jié)構(gòu)體類型，LinkList為單鏈表指針類型229.1.2單鏈表與雙鏈表圖9.2單鏈表結(jié)構(gòu)指針L指向單鏈表頭結(jié)點(diǎn)，頭結(jié)點(diǎn)指向開始結(jié)點(diǎn)，開始結(jié)點(diǎn)又指向下一個(gè)結(jié)點(diǎn)，……，直到最后一個(gè)尾結(jié)點(diǎn)。尾結(jié)點(diǎn)的next為0，表示NULL指針，約定單鏈表的結(jié)點(diǎn)的next為0時(shí)表示尾結(jié)點(diǎn)。上述鏈表稱為帶頭結(jié)點(diǎn)的單鏈表，若開始結(jié)點(diǎn)為頭結(jié)點(diǎn)，則稱這樣的鏈表為不帶頭結(jié)點(diǎn)的單鏈表。239.1.2單鏈表與雙鏈表2．雙鏈表雙鏈表每個(gè)結(jié)點(diǎn)包含指向前驅(qū)結(jié)點(diǎn)和指向直接后繼結(jié)點(diǎn)的指針域，其形式為：typedefstructtagDNode{//雙鏈表結(jié)點(diǎn)類型

ElemTypedata;//數(shù)據(jù)域

structtagDNode*prev,*next;//指針域：分別指向前驅(qū)結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)}DNode,*DLinkList;//DNode為雙鏈表結(jié)構(gòu)體類型，DLinkList為雙鏈表指針類型249.1.2單鏈表與雙鏈表圖9.3雙鏈表結(jié)構(gòu)指針L指向雙鏈表頭結(jié)點(diǎn)，其每個(gè)結(jié)點(diǎn)分別有指向前一個(gè)結(jié)點(diǎn)和后一個(gè)結(jié)點(diǎn)的指針。沿著next指針，頭結(jié)點(diǎn)指向開始結(jié)點(diǎn)，開始結(jié)點(diǎn)又指向下一個(gè)結(jié)點(diǎn)，……，直到尾結(jié)點(diǎn)，尾結(jié)點(diǎn)的next為0。沿著prev指針，尾結(jié)點(diǎn)指向前一個(gè)結(jié)點(diǎn)，直到頭結(jié)點(diǎn)head，頭結(jié)點(diǎn)的prev為0。約定雙鏈表的結(jié)點(diǎn)的next為0時(shí)表示尾結(jié)點(diǎn)，prev為0時(shí)表示頭結(jié)點(diǎn)。雙鏈表也有帶頭結(jié)點(diǎn)和不帶頭結(jié)點(diǎn)之分。259.1.2單鏈表與雙鏈表與單鏈表相比，雙鏈表可以從前向鏈和后向鏈遍歷整個(gè)鏈表，這樣簡(jiǎn)化了鏈表排序方法及運(yùn)算。同時(shí)，當(dāng)一個(gè)鏈數(shù)據(jù)受損（如數(shù)據(jù)庫(kù)設(shè)備故障）時(shí)可以根據(jù)另一個(gè)鏈來恢復(fù)它。269.1.2單鏈表與雙鏈表3．循環(huán)鏈表若單鏈表尾結(jié)點(diǎn)指向頭結(jié)點(diǎn)而不是0，則該鏈表是循環(huán)單鏈表。同理，若雙鏈表尾結(jié)點(diǎn)next指向頭結(jié)點(diǎn)而不是0，頭結(jié)點(diǎn)prev指向尾結(jié)點(diǎn)而不是0，則該鏈表是循環(huán)雙鏈表。279.1.2單鏈表與雙鏈表圖9.4循環(huán)單鏈表和循環(huán)雙鏈表289.2鏈表的創(chuàng)建299.2.1創(chuàng)建單鏈表通過第7章介紹的內(nèi)存動(dòng)態(tài)分配技術(shù)可以產(chǎn)生新結(jié)點(diǎn)的內(nèi)存單元，例如：調(diào)用malloc、realloc內(nèi)存分配函數(shù)或free釋放函數(shù)時(shí)，在程序中需要文件包含命令：LinkListp;//鏈表指針p=(LinkList)malloc(sizeof(LNode));//分配LNode類型內(nèi)存單元且將地址保存到p中#include<stdlib.h>309.2.1創(chuàng)建單鏈表創(chuàng)建鏈表常用兩種方法：頭插法和尾插法。（1）頭插法建立鏈表CreateLinkF(&L,n,input())該方法先建立一個(gè)頭結(jié)點(diǎn)*L，然后產(chǎn)生新結(jié)點(diǎn)，設(shè)置新結(jié)點(diǎn)的數(shù)據(jù)域；再將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭，直至指定數(shù)目的元素都增加到鏈表中為止。其步驟為：①創(chuàng)建頭結(jié)點(diǎn)*L，設(shè)置*L的next為0。②動(dòng)態(tài)分配一個(gè)結(jié)點(diǎn)s，輸入s的數(shù)據(jù)域。③將s插入到開始結(jié)點(diǎn)之前，頭結(jié)點(diǎn)之后，即s->next=p->next，p->next=s。④重復(fù)②～④步驟加入更多結(jié)點(diǎn)。319.2.1創(chuàng)建單鏈表采用頭插法創(chuàng)建單鏈表的算法如下：1voidCreateLinkF(LinkList*L,intn,

void(*input)(ElemType*))2{//頭插法創(chuàng)建單鏈表，調(diào)用input輸入函數(shù)輸入數(shù)據(jù)

3LinkLists;4

*L=(LinkList)malloc(sizeof(LNode));5(*L)->next=NULL;//初始時(shí)為空表

6

for(;n>0;n--){//創(chuàng)建n個(gè)結(jié)點(diǎn)鏈表

7s=(LinkList)malloc(sizeof(LNode));8input(&s->data);9s->next=(*L)->next;10(*L)->next=s;//頭結(jié)點(diǎn)之后

11}12}指向頭節(jié)點(diǎn)的頭指針329.2.1創(chuàng)建單鏈表1voidCreateLinkF(LinkList*L,intn,

void(*input)(ElemType*))參數(shù)L表示將要?jiǎng)?chuàng)建出來的單鏈表指針，之所以是LinkList類型的指針類型（即指針的指針），其原因是需要將鏈表返回到調(diào)用函數(shù)中。n表示創(chuàng)建鏈表時(shí)需要輸入的元素?cái)?shù)目，由實(shí)際應(yīng)用中的具體要求確定。339.2.1創(chuàng)建單鏈表圖9.5頭插法建立的單鏈表L運(yùn)行時(shí)若輸入5個(gè)元素：1、2、3、4、5，則調(diào)用建立的單鏈表如圖所示。LinkListL;CreateLinkF(&L,5,input);//創(chuàng)建單鏈表L349.2.1創(chuàng)建單鏈表（2）尾插法建立鏈表CreateLinkR(&L,n,input())頭插法建立的鏈表中結(jié)點(diǎn)的次序與元素輸入的順序相反，若希望兩者次序一致，可采用尾插法建立鏈表。該方法是將新結(jié)點(diǎn)插到當(dāng)前鏈表的末尾上，359.2.1創(chuàng)建單鏈表采用尾插法創(chuàng)建單鏈表的算法如下：1voidCreateLinkR(LinkList*L,intn,

void(*input)(ElemType*))2{//尾插法創(chuàng)建單鏈表，調(diào)用input輸入函數(shù)輸入數(shù)據(jù)

3LinkListp,s;4p=*L=(LinkList)malloc(sizeof(LNode));5

for(;n>0;n--){//創(chuàng)建n個(gè)結(jié)點(diǎn)鏈表

6s=(LinkList)malloc(sizeof(LNode));7input(&s->data);8p->next=s,p=s;9}10p->next=NULL;//尾結(jié)點(diǎn)

11}369.2.1創(chuàng)建單鏈表圖9.6尾插法建立的單鏈表L運(yùn)行時(shí)若輸入5個(gè)元素：1、2、3、4、5，則調(diào)用CreateLinkR(&L,5,input)建立的單鏈表如圖所示。37鏈表的建立操作例題：建立一個(gè)學(xué)生管理系統(tǒng)管理學(xué)生各門課程信息，需要在程序運(yùn)行過程中動(dòng)態(tài)輸入多個(gè)學(xué)生的成績(jī)信息。2006-2007學(xué)年第二學(xué)期成績(jī)表學(xué)號(hào)姓名性別高等數(shù)學(xué)大學(xué)英語(yǔ)大學(xué)物理平均分總評(píng)1李亦錚女89969493.0優(yōu)秀2李凌飛男98878991.3優(yōu)秀3馬云燕女84938687.7優(yōu)秀4陳牧笛女84898686.3優(yōu)秀問題解決思路：利用單向鏈表解題，不斷循環(huán)，為每一個(gè)有效數(shù)據(jù)動(dòng)態(tài)開辟新節(jié)點(diǎn)，并保存數(shù)據(jù)，直到輸入學(xué)號(hào)數(shù)據(jù)為0時(shí)結(jié)束.核心問題：如何將新節(jié)點(diǎn)加入到整個(gè)鏈表結(jié)構(gòu)中

38鏈表的建立操作39首先設(shè)計(jì)一種稱為結(jié)點(diǎn)的數(shù)據(jù)類型：typedefstructtagNODE{//結(jié)點(diǎn)數(shù)據(jù)類型intno；//數(shù)據(jù)域floateng;//數(shù)據(jù)域structtagNODE*next;//指針域}LNODE，*LinkList;//LNode為單鏈表結(jié)構(gòu)體類型，LinkList為單鏈表指針類型數(shù)據(jù)域包含兩個(gè)個(gè)成員，代表學(xué)生信息結(jié)點(diǎn)中的學(xué)號(hào)、英語(yǔ)成績(jī)。next成員表示指針域，存放另一個(gè)結(jié)點(diǎn)的地址，是鏈表中的組織者。鏈表的建立操作40通過第7章介紹的內(nèi)存動(dòng)態(tài)分配技術(shù)可以產(chǎn)生新結(jié)點(diǎn)的內(nèi)存單元，例如：調(diào)用malloc、realloc內(nèi)存分配函數(shù)或free釋放函數(shù)時(shí)，在程序中需要文件包含命令：LinkListp;//鏈表指針p=(LinkList)malloc(sizeof(LNode));//分配LNode類型內(nèi)存單元且將地址保存到p中#include<stdlib.h>鏈表的建立操作41第一步：新節(jié)點(diǎn)加入鏈表過程核心問題：維護(hù)鏈表結(jié)構(gòu)，假定有一個(gè)LNODE類型的對(duì)象指針L，通過將一個(gè)新結(jié)點(diǎn)的地址賦給L的最后一個(gè)節(jié)點(diǎn)的link成員，則可以通過尾節(jié)點(diǎn)的link成員（next）“鏈接”到新結(jié)點(diǎn)上，重復(fù)這個(gè)過程可以得到完整鏈表結(jié)構(gòu)。鏈表的建立操作新產(chǎn)生一個(gè)節(jié)點(diǎn)新節(jié)點(diǎn)指針q尾指針p42第二步更新尾指針，使得始終指向當(dāng)前鏈表中最后一個(gè)節(jié)點(diǎn)鏈表的建立操作新產(chǎn)生一個(gè)節(jié)點(diǎn)新節(jié)點(diǎn)指針q尾指針p第三步如果未到鏈表末尾，重復(fù)第一步和第二步總結(jié)：建立過程中始終需要有一個(gè)節(jié)點(diǎn)指針指向當(dāng)前鏈表中最后一個(gè)節(jié)點(diǎn)的位置動(dòng)態(tài)單鏈表的建立完整過程1）定義與節(jié)點(diǎn)同類型的鏈表頭指針變量L并賦值0，表示鏈表在建立之前是空的；2)定義與節(jié)點(diǎn)同類型的工作指針變量p、q。鏈表的建立操作3)開辟第一個(gè)節(jié)點(diǎn)的存儲(chǔ)區(qū)域，輸入第一個(gè)節(jié)點(diǎn)數(shù)據(jù)；并使L、p、q指向第一個(gè)節(jié)點(diǎn)，210189.5Lpq實(shí)現(xiàn)代碼：Len=sizeof(LNODE);q=(LinkLlist)malloc(len);scanf("%ld,%f",&q->num,&q->eng);L=p=q;鏈表的建立操作4)開辟下一節(jié)點(diǎn)的存儲(chǔ)區(qū)域，使q指向新節(jié)點(diǎn)并輸入新節(jié)點(diǎn)數(shù)據(jù)，然后使上一節(jié)點(diǎn)的next成員指向新節(jié)點(diǎn)；210189.5Lqp2304901048實(shí)現(xiàn)代碼q=(LinkList)malloc(len);scanf("%ld,%f",&q->num,&q->eng);p->next=p;//更新尾指針

13701370pq鏈表的建立操作3)重復(fù)第4步，建立并鏈接多個(gè)節(jié)點(diǎn)直至所需長(zhǎng)度，將末尾節(jié)點(diǎn)的next成員賦值0。210189.51370Lp2230490291885pNULL10481370q10121012pq實(shí)現(xiàn)代碼q=(LinkList)malloc(len);scanf("%ld,%f",&q->num,&q->eng);p->next=q;p=p->next;//p2跟進(jìn)p->next=NULL;//末尾節(jié)點(diǎn)next賦值0鏈表的建立操作采用尾插法創(chuàng)建單鏈表的算法如下：

1voidCreateLinkR(LinkListL,intn)

2{//尾插法創(chuàng)建單鏈表

3LinkListp,q;4p=L=(LinkList)malloc(sizeof(LNode));5

for(;n>0;n--){//創(chuàng)建n個(gè)結(jié)點(diǎn)鏈表

6q=(LinkList)malloc(sizeof(LNode));7scanf(“%d,%f”,&q->num,&q->eng);8p->next=q,p=q;9}10p->next=NULL;//尾結(jié)點(diǎn)

11}生成新節(jié)點(diǎn)更新尾指針實(shí)現(xiàn)建立鏈表過程鏈表的建立操作489.2.1創(chuàng)建單鏈表（3）初始化鏈表InitList(&L)構(gòu)造一個(gè)空鏈表（即沒有數(shù)據(jù)結(jié)點(diǎn)）的算法如下：1voidInitList(LinkList*L)

//構(gòu)造一個(gè)空的單鏈表L2{3

*L=(LinkList)malloc(sizeof(LNode));4(*L)->next=NULL;//初始時(shí)為空表

5}499.2.1創(chuàng)建單鏈表（4）判斷鏈表是否為空表ListEmpty(L)檢測(cè)一個(gè)鏈表是否為空表的算法如下：1intListEmpty(LinkListL)//檢測(cè)L是否為空表

2{//若L為空表返回TRUE，否則返回FALSE3

returnL->next==NULL;4}509.2.2創(chuàng)建雙鏈表雙鏈表每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，next指向直接后繼結(jié)點(diǎn)，prev指向前驅(qū)結(jié)點(diǎn)。建立雙鏈表的過程與單鏈表相似，只是需要再處理prev指針，建立前向鏈即可。519.2.2創(chuàng)建雙鏈表采用頭插法創(chuàng)建雙鏈表的算法如下：1voidCreateLinkF(DLinkList*L,intn,

void(*input)(ElemType*))2{//頭插法創(chuàng)建雙鏈表，調(diào)用input輸入函數(shù)輸入數(shù)據(jù)

3DLinkLists;4

*L=(DLinkList)malloc(sizeof(DNode));5(*L)->prev=(*L)->next=NULL;6

for(;n>0;n--){//創(chuàng)建n個(gè)結(jié)點(diǎn)鏈表

7

s=(DLinkList)malloc(sizeof(DNode));8input(&s->data);9s->next=(*L)->next;10

if((*L)->next!=NULL)(*L)->next->prev=s;11(*L)->next=s,s->prev=*L;12}13}529.2.2創(chuàng)建雙鏈表采用尾插法創(chuàng)建雙鏈表的算法如下：1voidCreateLinkR(DLinkList*L,intn,

void(*input)(ElemType*))2{//尾插法創(chuàng)建雙鏈表，調(diào)用input輸入函數(shù)輸入數(shù)據(jù)

3DLinkListp,s;4p=*L=(DLinkList)malloc(sizeof(DNode));5(*L)->prev=(*L)->next=NULL;6

for(;n>0;n--){//創(chuàng)建n個(gè)結(jié)點(diǎn)鏈表

7

s=(DLinkList)malloc(sizeof(DNode));8input(&s->data);9s->next=NULL;//當(dāng)前結(jié)點(diǎn)是尾結(jié)點(diǎn)

10p->next=s,s->prev=p,p=s;11}12}539.2.2創(chuàng)建雙鏈表構(gòu)造一個(gè)空的雙鏈表（即沒有數(shù)據(jù)結(jié)點(diǎn)）的算法如下：1voidInitList(DLinkList*L)

//構(gòu)造一個(gè)空的單鏈表L2{3

*L=(DLinkList)malloc(sizeof(DNode));4(*L)->prev=(*L)->next=NULL;5}549.3鏈表的運(yùn)算雙鏈表與單鏈表的基本運(yùn)算大多數(shù)是相同的，本節(jié)僅討論單鏈表的情形。559.3.1鏈表的遍歷（1）鏈表遍歷ListTraverse(L,visit())與數(shù)組不同，鏈表不是用下標(biāo)而是用指針運(yùn)算查找數(shù)據(jù)元素的。通過鏈表的頭結(jié)點(diǎn)L可以訪問開始結(jié)點(diǎn)p=L->next，令p=p->next，即p指向直接后繼結(jié)點(diǎn)，如此循環(huán)可以訪問整個(gè)鏈表中的全部結(jié)點(diǎn)，這就是鏈表的遍歷（traverse）。鏈表的輸出、銷毀、查找和逆序等運(yùn)算都需要遍歷鏈表。鏈表遍歷算法的實(shí)現(xiàn)步驟為：①令指針p指向L的開始結(jié)點(diǎn)。②若p為0，表示已到鏈尾，遍歷結(jié)束。③令p指向直接后繼結(jié)點(diǎn)，即p=p->next。重復(fù)②～③步驟直至遍歷結(jié)束。【例】建立并輸出有3名學(xué)生數(shù)據(jù)的單鏈表。#include<stdio.h>//包含NULL定義#defineN3structtagSTU//全局結(jié)構(gòu)體類型定義{longnum;floatscore;structtagSTU*next;//自引用結(jié)構(gòu)體指針};intmain(){┇}intmain(){structtagSTU*head,*p1,*p2;inti,len;head=NULL;//head初始化

len=sizeof(structtagSTU);//求類型長(zhǎng)

for(i=1;i<=N;i++)//↙強(qiáng)制轉(zhuǎn)換為結(jié)構(gòu)體指針類型

{p1=(structtagSTU*)malloc(len);//申請(qǐng)

printf("Enternum,score:");//↓輸入數(shù)據(jù)

scanf("%ld,%f",&p1->num,&p1->score);if(i==1)head=p2=p1;//指向首節(jié)點(diǎn)

else{p2->next=p1;p2=p1;}//節(jié)點(diǎn)鏈接

if(i==N)p2->next=NULL;//標(biāo)記末尾節(jié)點(diǎn)

}

┇┇intmain(){┇for(i=1;i<=N;i++)//建立鏈表

{┇}for(i=1;i<=N;i++)//遍歷輸出N個(gè)節(jié)點(diǎn)鏈表

{if(i==1)p1=head;

//p1指向頭節(jié)點(diǎn)

elsep1=p1->next;//p1指向下一節(jié)點(diǎn)

printf("num=%ld,score=%5.2f\n",p1->num,p1->score);}return0;}//mainSX09-10更適用的鏈表輸出：┇p1=head;while(p1!=NULL)//適用于任意節(jié)點(diǎn)數(shù)鏈表{printf("num=%ld,score=%5.2f\n",p1->num,p1->score);p1=p1->next;}┇注：本形式的鏈表輸出具有通用性，可適應(yīng)由于刪除或插入節(jié)點(diǎn)引起的鏈表長(zhǎng)度的變化。609.4結(jié)點(diǎn)的插入與刪除鏈表中每個(gè)結(jié)點(diǎn)都有指針域指向其前后結(jié)點(diǎn)，在進(jìn)行結(jié)點(diǎn)插入和刪除時(shí)，不能僅僅只對(duì)該結(jié)點(diǎn)進(jìn)行操作，還要考慮其前后結(jié)點(diǎn)。619.4.1單鏈表插入結(jié)點(diǎn)插入結(jié)點(diǎn)操作是指將一個(gè)新結(jié)點(diǎn)插入到已知的鏈表中。插入位置可能在頭結(jié)點(diǎn)、尾結(jié)點(diǎn)或者鏈表中間，插入操作前需要定位插入元素的位置和動(dòng)態(tài)分配產(chǎn)生新結(jié)點(diǎn)。假設(shè)將新結(jié)點(diǎn)s插入到單鏈表的第i個(gè)結(jié)點(diǎn)位置上。方法是先在單鏈表中找到第i-1個(gè)結(jié)點(diǎn)p，在其后插入新結(jié)點(diǎn)s，如圖（a）所示。為了插入結(jié)點(diǎn)s，先讓結(jié)點(diǎn)s的指針域指向結(jié)點(diǎn)p的后一個(gè)結(jié)點(diǎn)（即p->next），如圖（b）所示；然后修改結(jié)點(diǎn)p的指針域，令其指向結(jié)點(diǎn)s，如圖（c）所示，從而實(shí)現(xiàn)3個(gè)結(jié)點(diǎn)指向關(guān)系的變化。629.4.1單鏈表插入結(jié)點(diǎn)圖9.8單鏈表插入結(jié)點(diǎn)示意639.4.1單鏈表插入結(jié)點(diǎn)圖9.8單鏈表插入結(jié)點(diǎn)示意649.4.1單鏈表插入結(jié)點(diǎn)圖9.8單鏈表插入結(jié)點(diǎn)示意659.4.1單鏈表插入結(jié)點(diǎn)圖9.8單鏈表插入結(jié)點(diǎn)示意總結(jié)：插入節(jié)點(diǎn)需要知道插入點(diǎn)之前的節(jié)點(diǎn)位置p。669.4.1單鏈表插入結(jié)點(diǎn)實(shí)現(xiàn)上述步驟的C語(yǔ)言語(yǔ)句如下：請(qǐng)注意，這兩個(gè)表達(dá)式的順序不能顛倒。因?yàn)槿粝刃薷慕Y(jié)點(diǎn)p的指針域指向結(jié)點(diǎn)s，結(jié)點(diǎn)p的后一個(gè)結(jié)點(diǎn)（p->next）就此從鏈表中斷開，再讓結(jié)點(diǎn)s的指針域指向結(jié)點(diǎn)p的后一個(gè)結(jié)點(diǎn)已成錯(cuò)誤的。在單鏈表中第i個(gè)位置上插入元素e的新結(jié)點(diǎn)s的算法如下：s->next=p->next,p->next=s;//結(jié)點(diǎn)插入算法節(jié)點(diǎn)的插入插入可分為隨意插入和按順序插入，隨意插入包括插入到頭部、尾部或中間指定位置；按順序插入是指按某關(guān)鍵字的順序插入，而在插入前鏈表必須已按該關(guān)鍵字進(jìn)行了排序。按順序插入的步驟：開辟待插入節(jié)點(diǎn)的存儲(chǔ)區(qū)域并輸入數(shù)據(jù)；2)查找插入位置：從鏈表首節(jié)點(diǎn)開始按關(guān)鍵字成員與待插入節(jié)點(diǎn)相同成員進(jìn)行比較，直到確定了插入位置；3)將插入位置前一節(jié)點(diǎn)的“鏈節(jié)”成員賦給待插入節(jié)點(diǎn)的“鏈節(jié)”成員；4)將待插入節(jié)點(diǎn)的指針賦給前一節(jié)點(diǎn)“鏈節(jié)”成員；若：插入點(diǎn)在鏈頭，先將頭指針賦給插入節(jié)點(diǎn)的指針域，再將待插入節(jié)點(diǎn)的指針賦給頭指針變量。210189.51370head10482304901012241478

104813701012101226802680291885NULL139491104820302030【例】在上例增加“按學(xué)號(hào)插入節(jié)點(diǎn)的函數(shù)”插入函數(shù)：structtagSTU*insert(structtagSTU*head){structtagSTU*p0,*p1,*p2;longn;intlen;len=sizeof(structtagSTU);p0=(structtagSTU*)malloc(len);//申請(qǐng)新節(jié)點(diǎn)

printf("Enternum,scoretoinsert:");scanf("%ld,%f",&p0->num,&p0->score);n=p0->num;//產(chǎn)生學(xué)號(hào)副本np1=head;//從首節(jié)點(diǎn)開始查找

┇

┇

p1=head;//↓插入在頭部

if(n<p1->num){p0->next=head;head=p0;}else{do//查找插入位置

{p2=p1; p1=p1->next;}while(p1!=NULL&&n>p1->num);p0->next=p2->next;//插入點(diǎn)在p1之前位置

p2->next=p0;}return(head);}//insertSX09-12719.4.2單鏈表刪除結(jié)點(diǎn)結(jié)點(diǎn)刪除操作是指將鏈表中的某個(gè)結(jié)點(diǎn)從鏈表中刪除。刪除位置可能在頭結(jié)點(diǎn)、尾結(jié)點(diǎn)或者鏈表中間，刪除操作后需要釋放刪除結(jié)點(diǎn)的內(nèi)存空間。將鏈表中第i個(gè)結(jié)點(diǎn)刪去的方法是先在單鏈表中找到第i-1個(gè)結(jié)點(diǎn)p，再刪除其后的結(jié)點(diǎn)，如圖（a）所示。若要?jiǎng)h除結(jié)點(diǎn)p的后一個(gè)結(jié)點(diǎn)（即p->next），只需要將p的指針域指向p->next的后一個(gè)結(jié)點(diǎn)（即p->next->next），如圖（b）所示。729.4.2單鏈表刪除結(jié)點(diǎn)圖9.9單鏈表刪除結(jié)點(diǎn)示意739.4.2單鏈表刪除結(jié)點(diǎn)圖9.9單鏈表刪除結(jié)點(diǎn)示意第一步：將予刪除節(jié)點(diǎn)后一個(gè)節(jié)點(diǎn)連到d前一個(gè)節(jié)點(diǎn)749.4.2單鏈表刪除結(jié)點(diǎn)圖9.9單鏈表刪除結(jié)點(diǎn)示意第二步：將予刪除節(jié)點(diǎn)的內(nèi)存空間釋放free(d);//釋放結(jié)點(diǎn)實(shí)現(xiàn)分析：需要保存訪問節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的位置，指針p。759.4.2單鏈表刪除結(jié)點(diǎn)實(shí)現(xiàn)上述步驟的C語(yǔ)言語(yǔ)句如下：p->next=p->next->next;//結(jié)點(diǎn)刪除算法769.4.2單鏈表刪除結(jié)點(diǎn)1intListDelete(LinkList*L,ElemType*ep)2{//刪除第i個(gè)結(jié)點(diǎn),并由*ep返回其值

3LinkListp=NULL,q=*L;//q指向頭結(jié)點(diǎn)

4

while(q!=NULL&&i>=1){//直到第i個(gè)結(jié)點(diǎn)

5p=q;//p是q的前驅(qū)

6q=q->next;//q指向直接后繼結(jié)點(diǎn)

7i--;8}9

if(p==NULL||q==NULL)return0;10p->next=q->next;//結(jié)點(diǎn)刪除算法

11

if(ep!=NULL)*ep=q->data;12free(q);//釋放結(jié)點(diǎn)

13

return1;//操作成功返回真（1）

14}77約瑟夫問題，又稱為約瑟夫環(huán)。據(jù)說著名猶太歷史學(xué)家Josephus有過以下的故事：在羅馬人占領(lǐng)喬塔帕特后，39個(gè)猶太人與Josephus及他的朋友躲到一個(gè)洞中，39個(gè)猶太人決定寧愿死也不要被敵人抓到，于是決定了一個(gè)自殺方式，41個(gè)人排成一個(gè)圓圈，由第1個(gè)人開始報(bào)數(shù)，每報(bào)數(shù)到第3人該人就必須自殺，然后再由下一個(gè)重新報(bào)數(shù)，直到所有人都自殺身亡為止。問題：站在哪個(gè)位置上可以成為最后剩下的那個(gè)人？鏈表的刪除操作例題：有N個(gè)人圍坐一圈，從第一個(gè)開始報(bào)數(shù)，凡是報(bào)到3就退出圈子，請(qǐng)找出最后一個(gè)留在圈子里的序號(hào)？數(shù)組的聲明和引用問題解決思路：利用循環(huán)鏈表解題，不斷循環(huán)，刪除逢3的節(jié)點(diǎn)，直到最后剩一個(gè)節(jié)點(diǎn)核心問題：刪除節(jié)點(diǎn)

78分析：結(jié)點(diǎn)刪除操作是指將鏈表中的某個(gè)結(jié)點(diǎn)從鏈表中刪除。刪除操作后需要釋放刪除結(jié)點(diǎn)的內(nèi)存空間。799.1.1鏈表的概念首先設(shè)計(jì)一種稱為結(jié)點(diǎn)（node）的數(shù)據(jù)類型：這個(gè)結(jié)構(gòu)體類型中，data成員表示數(shù)據(jù)域，代表結(jié)點(diǎn)的數(shù)據(jù)信息。typedefstructtagNODE{//結(jié)點(diǎn)數(shù)據(jù)類型

intdata;//數(shù)據(jù)域

structtagNODE*next;//指針域}NODE;next成員表示指針域，存放另一個(gè)結(jié)點(diǎn)的地址，是鏈表中的組織者。80PNum=1Num=2Num=3刪除81剩余數(shù)為1？刪除當(dāng)前節(jié)點(diǎn)計(jì)數(shù)等于3計(jì)數(shù)加1更新剩余數(shù)否輸出剩余節(jié)點(diǎn)序號(hào)是是否單鏈表刪除結(jié)點(diǎn)問題解決流程圖表示829.4.2單鏈表刪除結(jié)點(diǎn)1voidsearch(LinkList*L，intN)2{//約瑟夫環(huán)

3LinkListp=*L;intsum=N;intNum=1//p指向首結(jié)點(diǎn)

4

while(sum!=1){//直到剩余1個(gè)結(jié)點(diǎn)

5Num++;//計(jì)數(shù)加一

6if(Num==3){q=p->next;p=p->next->next;free(q);Num=1;sum--;//釋放計(jì)數(shù)為3的節(jié)點(diǎn)}

7}

8*L=p;9}【例】創(chuàng)建一個(gè)鏈表,當(dāng)輸入數(shù)據(jù)小于等于0時(shí)創(chuàng)建結(jié)束，先輸出原始鏈表，然后將這個(gè)鏈表按反轉(zhuǎn)重新排列，即將鏈頭當(dāng)鏈尾，鏈尾當(dāng)鏈頭，輸出反轉(zhuǎn)后的鏈表。輸入格式:123497620輸出格式:

原始表:12->34->9->7->6->2

反轉(zhuǎn)表:2->6->7->9->34->12注意:

輸入以0表示數(shù)據(jù)結(jié)束,建立鏈表要具有通用第一個(gè)輸出為12,第二個(gè)為->34,因此需做計(jì)數(shù)#include<stdi