C程序設(shè)計第九章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從后向前掃描，找到第一個比關(guān)鍵數(shù)據(jù)小的數(shù)，交換1956781233734ij2）利用i從前向后掃描，找到第一個比關(guān)鍵數(shù)據(jù)大的數(shù)，交換19

34781233756ij3）重復（1）即利用j從后向前掃描，找到第一個比關(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鏈表的運算9.4結(jié)點的插入與刪除8本知識點在本課程知識體系中地位鏈表是一種常見的重要的數(shù)據(jù)結(jié)構(gòu)，它是動態(tài)的進行內(nèi)存存儲分配的一種結(jié)構(gòu)，存儲空間能動態(tài)進行增長或縮小的數(shù)據(jù)結(jié)構(gòu)。鏈表主要用于兩個目的：一是建立不定長度的數(shù)組。二是鏈表可以在不重新安排整個存儲結(jié)構(gòu)的情況下，方便且迅速地插入和刪除數(shù)據(jù)元素。9例如：建立一個學生管理程序，要求實現(xiàn)學生的數(shù)據(jù)動態(tài)錄入、查詢和刪除鏈表概述2006-2007學年第二學期成績表序號姓名性別高等數(shù)學大學英語大學物理平均分總評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ù)刪除問題特點：事先不確定學生人數(shù)，如果采用事先確定長度的存儲結(jié)構(gòu)，將會帶來存儲空間的浪費必須用動態(tài)存儲結(jié)構(gòu)存放數(shù)據(jù)10程序中存放大量數(shù)據(jù)：鏈表和數(shù)組數(shù)組存放數(shù)據(jù)：必須事先定義固定的長度（即元素個數(shù)數(shù)組存放數(shù)據(jù)：物理存儲單元要求在內(nèi)存中分配連續(xù)存儲空間鏈表存放數(shù)據(jù)：可以根據(jù)需要，動態(tài)開辟內(nèi)存單元。鏈表存放數(shù)據(jù)：物理存儲單元非連續(xù)，非順序的存儲結(jié)構(gòu)11鏈表：是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。節(jié)點節(jié)點：數(shù)據(jù)+指針數(shù)據(jù):存放數(shù)據(jù)存儲單元指針：指示后繼元素存儲位置129.1.1鏈表的概念一種稱為結(jié)點（node）的數(shù)據(jù)類型：這個結(jié)構(gòu)體類型中，data成員表示數(shù)據(jù)域，代表結(jié)點的數(shù)據(jù)信息。typedefstructtagNODE{//結(jié)點數(shù)據(jù)類型

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

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

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

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

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

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

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

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

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

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

6

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

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

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

void(*input)(ElemType*))參數(shù)L表示將要創(chuàng)建出來的單鏈表指針，之所以是LinkList類型的指針類型（即指針的指針），其原因是需要將鏈表返回到調(diào)用函數(shù)中。n表示創(chuàng)建鏈表時需要輸入的元素數(shù)目，由實際應用中的具體要求確定。339.2.1創(chuàng)建單鏈表圖9.5頭插法建立的單鏈表L運行時若輸入5個元素：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é)點的次序與元素輸入的順序相反，若希望兩者次序一致，可采用尾插法建立鏈表。該方法是將新結(jié)點插到當前鏈表的末尾上，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個結(jié)點鏈表

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

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

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

13701370pq鏈表的建立操作3)重復第4步，建立并鏈接多個節(jié)點直至所需長度，將末尾節(jié)點的next成員賦值0。210189.51370Lp2230490291885pNULL10481370q10121012pq實現(xiàn)代碼q=(LinkList)malloc(len);scanf("%ld,%f",&q->num,&q->eng);p->next=q;p=p->next;//p2跟進p->next=NULL;//末尾節(jié)點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個結(jié)點鏈表

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

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

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

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

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

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

returnL->next==NULL;4}509.2.2創(chuàng)建雙鏈表雙鏈表每個結(jié)點有兩個指針域，next指向直接后繼結(jié)點，prev指向前驅(qū)結(jié)點。建立雙鏈表的過程與單鏈表相似，只是需要再處理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個結(jié)點鏈表

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個結(jié)點鏈表

7

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

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

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

*L=(DLinkList)malloc(sizeof(DNode));4(*L)->prev=(*L)->next=NULL;5}549.3鏈表的運算雙鏈表與單鏈表的基本運算大多數(shù)是相同的，本節(jié)僅討論單鏈表的情形。559.3.1鏈表的遍歷（1）鏈表遍歷ListTraverse(L,visit())與數(shù)組不同，鏈表不是用下標而是用指針運算查找數(shù)據(jù)元素的。通過鏈表的頭結(jié)點L可以訪問開始結(jié)點p=L->next，令p=p->next，即p指向直接后繼結(jié)點，如此循環(huán)可以訪問整個鏈表中的全部結(jié)點，這就是鏈表的遍歷（traverse）。鏈表的輸出、銷毀、查找和逆序等運算都需要遍歷鏈表。鏈表遍歷算法的實現(xiàn)步驟為：①令指針p指向L的開始結(jié)點。②若p為0，表示已到鏈尾，遍歷結(jié)束。③令p指向直接后繼結(jié)點，即p=p->next。重復②～③步驟直至遍歷結(jié)束。【例】建立并輸出有3名學生數(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);//求類型長

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

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

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

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

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

if(i==N)p2->next=NULL;//標記末尾節(jié)點

}

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

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

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

//p1指向頭節(jié)點

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

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

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

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

┇

┇

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;//插入點在p1之前位置

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

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

4

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

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

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

7i--;8}9

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

11

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

13

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

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

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

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

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

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

4

while(sum!=1){//直到剩余1個結(jié)點

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

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

7}

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

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

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

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