C程序設計第九章ppt西工大

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

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

778123334

56419

778123334

5619

7

34123378

5619

7

331234

78

56條件i<j不滿足了，一趟排序結束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);

/*排好序的結果*/

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

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

}7第9章鏈表9.1鏈表概述9.2鏈表的創(chuàng)建9.3鏈表的運算9.4結點的插入與刪除8本知識點在本課程知識體系中地位鏈表是一種常見的重要的數(shù)據(jù)結構，它是動態(tài)的進行內(nèi)存存儲分配的一種結構，存儲空間能動態(tài)進行增長或縮小的數(shù)據(jù)結構。鏈表主要用于兩個目的：一是建立不定長度的數(shù)組。二是鏈表可以在不重新安排整個存儲結構的情況下，方便且迅速地插入和刪除數(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ù)，如果采用事先確定長度的存儲結構，將會帶來存儲空間的浪費必須用動態(tài)存儲結構存放數(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ù)，非順序的存儲結構11鏈表：是一種物理存儲單元上非連續(xù)、非順序的存儲結構，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。節(jié)點節(jié)點：數(shù)據(jù)+指針數(shù)據(jù):存放數(shù)據(jù)存儲單元指針：指示后繼元素存儲位置129.1.1鏈表的概念一種稱為結點（node）的數(shù)據(jù)類型：這個結構體類型中，data成員表示數(shù)據(jù)域，代表結點的數(shù)據(jù)信息。typedefstructtagNODE{//結點數(shù)據(jù)類型

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

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

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

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

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

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

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

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

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

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())頭插法建立的鏈表中結點的次序與元素輸入的順序相反，若希望兩者次序一致，可采用尾插法建立鏈表。該方法是將新結點插到當前鏈表的末尾上，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個結點鏈表

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

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é)點加入到整個鏈表結構中

38鏈表的建立操作39首先設計一種稱為結點的數(shù)據(jù)類型：typedefstructtagNODE{//結點數(shù)據(jù)類型intno；//數(shù)據(jù)域floateng;//數(shù)據(jù)域structtagNODE*next;//指針域}LNODE，*LinkList;//LNode為單鏈表結構體類型，LinkList為單鏈表指針類型數(shù)據(jù)域包含兩個個成員，代表學生信息結點中的學號、英語成績。next成員表示指針域，存放另一個結點的地址，是鏈表中的組織者。鏈表的建立操作40通過第7章介紹的內(nèi)存動態(tài)分配技術可以產(chǎn)生新結點的內(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é)點加入鏈表過程核心問題：維護鏈表結構，假定有一個LNODE類型的對象指針L，通過將一個新結點的地址賦給L的最后一個節(jié)點的link成員，則可以通過尾節(jié)點的link成員（next）“鏈接”到新結點上，重復這個過程可以得到完整鏈表結構。鏈表的建立操作新產(chǎn)生一個節(jié)點新節(jié)點指針q尾指針p42第二步更新尾指針，使得始終指向當前鏈表中最后一個節(jié)點鏈表的建立操作新產(chǎn)生一個節(jié)點新節(jié)點指針q尾指針p第三步如果未到鏈表末尾，重復第一步和第二步總結：建立過程中始終需要有一個節(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個結點鏈表

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

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

//構造一個空的單鏈表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)建雙鏈表雙鏈表每個結點有兩個指針域，next指向直接后繼結點，prev指向前驅(qū)結點。建立雙鏈表的過程與單鏈表相似，只是需要再處理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個結點鏈表

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個結點鏈表

7

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

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

//構造一個空的單鏈表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ù)元素的。通過鏈表的頭結點L可以訪問開始結點p=L->next，令p=p->next，即p指向直接后繼結點，如此循環(huán)可以訪問整個鏈表中的全部結點，這就是鏈表的遍歷（traverse）。鏈表的輸出、銷毀、查找和逆序等運算都需要遍歷鏈表。鏈表遍歷算法的實現(xiàn)步驟為：①令指針p指向L的開始結點。②若p為0，表示已到鏈尾，遍歷結束。③令p指向直接后繼結點，即p=p->next。重復②～③步驟直至遍歷結束?！纠拷⒉⑤敵鲇?名學生數(shù)據(jù)的單鏈表。#include<stdio.h>//包含NULL定義#defineN3structtagSTU//全局結構體類型定義{longnum;floatscore;structtagSTU*next;//自引用結構體指針};intmain(){┇}intmain(){structtagSTU*head,*p1,*p2;inti,len;head=NULL;//head初始化

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

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

{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結點的插入與刪除鏈表中每個結點都有指針域指向其前后結點，在進行結點插入和刪除時，不能僅僅只對該結點進行操作，還要考慮其前后結點。619.4.1單鏈表插入結點插入結點操作是指將一個新結點插入到已知的鏈表中。插入位置可能在頭結點、尾結點或者鏈表中間，插入操作前需要定位插入元素的位置和動態(tài)分配產(chǎn)生新結點。假設將新結點s插入到單鏈表的第i個結點位置上。方法是先在單鏈表中找到第i-1個結點p，在其后插入新結點s，如圖（a）所示。為了插入結點s，先讓結點s的指針域指向結點p的后一個結點（即p->next），如圖（b）所示；然后修改結點p的指針域，令其指向結點s，如圖（c）所示，從而實現(xiàn)3個結點指向關系的變化。629.4.1單鏈表插入結點圖9.8單鏈表插入結點示意639.4.1單鏈表插入結點圖9.8單鏈表插入結點示意649.4.1單鏈表插入結點圖9.8單鏈表插入結點示意659.4.1單鏈表插入結點圖9.8單鏈表插入結點示意總結：插入節(jié)點需要知道插入點之前的節(jié)點位置p。669.4.1單鏈表插入結點實現(xiàn)上述步驟的C語言語句如下：請注意，這兩個表達式的順序不能顛倒。因為若先修改結點p的指針域指向結點s，結點p的后一個結點（p->next）就此從鏈表中斷開，再讓結點s的指針域指向結點p的后一個結點已成錯誤的。在單鏈表中第i個位置上插入元素e的新結點s的算法如下：s->next=p->next,p->next=s;//結點插入算法節(jié)點的插入插入可分為隨意插入和按順序插入，隨意插入包括插入到頭部、尾部或中間指定位置；按順序插入是指按某關鍵字的順序插入，而在插入前鏈表必須已按該關鍵字進行了排序。按順序插入的步驟：開辟待插入節(jié)點的存儲區(qū)域并輸入數(shù)據(jù)；2)查找插入位置：從鏈表首節(jié)點開始按關鍵字成員與待插入節(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單鏈表刪除結點結點刪除操作是指將鏈表中的某個結點從鏈表中刪除。刪除位置可能在頭結點、尾結點或者鏈表中間，刪除操作后需要釋放刪除結點的內(nèi)存空間。將鏈表中第i個結點刪去的方法是先在單鏈表中找到第i-1個結點p，再刪除其后的結點，如圖（a）所示。若要刪除結點p的后一個結點（即p->next），只需要將p的指針域指向p->next的后一個結點（即p->next->next），如圖（b）所示。729.4.2單鏈表刪除結點圖9.9單鏈表刪除結點示意739.4.2單鏈表刪除結點圖9.9單鏈表刪除結點示意第一步：將予刪除節(jié)點后一個節(jié)點連到d前一個節(jié)點749.4.2單鏈表刪除結點圖9.9單鏈表刪除結點示意第二步：將予刪除節(jié)點的內(nèi)存空間釋放free(d);//釋放結點實現(xiàn)分析：需要保存訪問節(jié)點的前一個節(jié)點的位置，指針p。759.4.2單鏈表刪除結點實現(xiàn)上述步驟的C語言語句如下：p->next=p->next->next;//結點刪除算法769.4.2單鏈表刪除結點1intListDelete(LinkList*L,ElemType*ep)2{//刪除第i個結點,并由*ep返回其值

3LinkListp=NULL,q=*L;//q指向頭結點

4

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

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

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

7i--;8}9

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

11

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

13

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

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

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

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

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

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

4

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

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)建結束，先輸出原始鏈表，然后將這個鏈表按反轉(zhuǎn)重新排列，即將鏈頭當鏈尾，鏈尾當鏈頭，輸出反轉(zhuǎn)后的鏈表。輸入格式:123497620輸出格式:

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

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

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