數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)明教程（第3版）課件 第2章 線性表(上)（下）

第2章線性表2.1線性表的基本概念2.2順序表2.3單鏈表和循環(huán)單鏈表2.4雙鏈表和循環(huán)雙鏈表2.5線性表的應(yīng)用第2章線性表1/1332.1線性表的基本概念2.1.1線性表的定義線性表是由n（n≥0）個(gè)相同類型的數(shù)據(jù)元素組成的有限序列。當(dāng)n=0時(shí)為空表，記為()或Φ.當(dāng)n>0時(shí)，線性表的邏輯表示為（al,a2,…,ai,…,an），也可以用下圖所示的邏輯結(jié)構(gòu)圖表示。2.1線性表的基本概念a1a2aian……2/133a1a2aian……開始元素尾元素邏輯序號(hào)或位置為i邏輯特征：若至少含有一個(gè)元素，則只有唯一的開始元素和終端元素除了起始元素外其他元素有且僅有一個(gè)前驅(qū)元素除了終端結(jié)點(diǎn)外其他元素有且僅有一個(gè)后繼元素2.1線性表的基本概念3/133線性表中的每個(gè)元素有唯一的序號(hào)（邏輯序號(hào)），同一個(gè)線性表中可以存在值相同的多個(gè)元素，但它們的序號(hào)是不同的。如一個(gè)整數(shù)線性表：（1，3，2，4，2，1，5）序號(hào)為1序號(hào)為62.1線性表的基本概念4/1332.1.2線性表的基本運(yùn)算初始化InitList(L)。其作用是建立一個(gè)空表L（即建立線性表的構(gòu)架，但不含任何數(shù)據(jù)元素）。銷毀線性表DestroyList(L)。其作用是釋放線性表L的內(nèi)存空間。求線性表的長(zhǎng)度GetLength(L)。其作用是返回線性表L的長(zhǎng)度。求線性表中第i個(gè)元素GetElem(L,i,e)。其作用是返回線性表L的第i個(gè)數(shù)據(jù)元素。通常線性表List的基本運(yùn)算如下：2.1線性表的基本概念5/133按值查找Locate(L,x)。若L中存在一個(gè)或多個(gè)值與x相等的元素，則其作用是返回第一個(gè)值為x的元素的邏輯序號(hào)。插入元素InsElem(L,x,i)。其作用是在線性表L的第i個(gè)位置上增加一個(gè)以x為值的新元素，刪除元素DelElem(L,i)。其作用是刪除線性表L的第i個(gè)元素ai。輸出元素值DispList(L)。其作用是按前后次序輸出線性表L的所有元素值。2.1線性表的基本概念6/133線性表抽象數(shù)據(jù)類型List=線性表中元素的邏輯結(jié)構(gòu)+基本運(yùn)算定義2.1線性表的基本概念7/133

【例2.1】利用線性表List的基本運(yùn)算，設(shè)計(jì)一個(gè)在線性表A中刪除線性表B中出現(xiàn)的元素的算法。

解：算法思路：依次檢查線性表B中的每個(gè)元素x，看它是否在線性表A中。若x在線性表A中，則將其從A中刪除。2.1線性表的基本概念8/133voidDelete(List&A,ListB) //A為引用型參數(shù){inti,k;ElemTypex;for(i=1;i<=GetLength(B);i++){x=GetElem(B,i);//依次獲取線性表B中的元素，存放在x中

k=Locate(A,x);

//在線性表A中查找x

if(k>0)DelElem(A,k); //若在線性表A中找到了，將其刪除

}}線性表的基本運(yùn)算算法2.1線性表的基本概念9/133

【例2.2】利用線性表List的基本運(yùn)算，設(shè)計(jì)一個(gè)由線性表A和B中的公共元素產(chǎn)生線性表C的算法。

算法思路：先初始化線性表C，然后依次檢查線性表A中的每個(gè)元素x，看它是否在線性表B中；若x在線性表B中，則將其插入到線性表C中。2.1線性表的基本概念10/133voidCommelem(ListA,ListB,List&C) //C為引用型參數(shù){inti,k,j=1;ElemTypex;

InitList(C);

for(i=1;i<=GetLength(A);i++)

{x=GetElem(A,i); //依次獲取線性表A中的元素，存放在x中k=Locate(B,x); //在線性表B中查找x

if(k>0)

{InsElem(C,x,j);

j++; //若在線性表B中找到了，將其插入到C中

}

}}2.1線性表的基本概念11/1332.2順序表2.2.1順序表的定義順序表是線性表采用順序存儲(chǔ)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的存儲(chǔ)方式，它由多個(gè)連續(xù)的存儲(chǔ)單元構(gòu)成，每個(gè)存儲(chǔ)單元存放線性表的一個(gè)元素。順序表邏輯上相鄰的數(shù)據(jù)元素在內(nèi)存的存儲(chǔ)結(jié)構(gòu)中也是相鄰的，不需要額外的內(nèi)存空間來存放元素之間的邏輯關(guān)系。2.2順序表12/133假定線性表的數(shù)據(jù)元素的類型為ElemType，在C/C++語(yǔ)言中，順序表類型聲明如下：#defineMaxSize100typedefintElemType;

//假設(shè)順序表中所有元素為int類型typedefstruct{

ElemTypedata[MaxSize]; //存放順序表的元素

intlength; //順序表的實(shí)際長(zhǎng)度}SqList; //順序表類型2.2順序表13/133順序表的示意圖如下：

由于順序表采用數(shù)組存放元素，而數(shù)組具有隨機(jī)存取特性，所以順序表具有隨機(jī)存取特性。元素a1a2…an…下標(biāo)01n-1MaxSize-1空閑2.2順序表14/1332.2.2線性表基本運(yùn)算在順序表上的實(shí)現(xiàn)1.順序表的基本運(yùn)算算法（1）初始化線性表運(yùn)算算法將順序表L的length域置為0。voidInitList(SqList&L)

//由于L要回傳給實(shí)參，所以用引用類型{

L.length=0;}2.2順序表15/133（2）銷毀線性表運(yùn)算算法

這里順序表L的內(nèi)存空間是由系統(tǒng)自動(dòng)分配的，在不再需要時(shí)由系統(tǒng)自動(dòng)釋放其空間。所以對(duì)應(yīng)的函數(shù)不含任何語(yǔ)句。voidDestroyList(SqListL){}2.2順序表16/133（3）求線性表長(zhǎng)度運(yùn)算算法返回順序表L的length域值。intGetLength(SqListL){

returnL.length;}2.2順序表17/133（4）求線性表中第i個(gè)元素運(yùn)算算法

在邏輯序號(hào)i無效時(shí)返回特殊值0（假），有效時(shí)返回1（真），并用引用型形參e返回第i個(gè)元素的值。intGetElem(SqListL,inti,ElemType&e){if(i<1||i>L.length) //無效的i值返回0

return0;

else

{e=L.data[i-1]; //取元素值并返回1

return1;}}2.2順序表18/133（5）按值查找運(yùn)算算法

在順序表L找第一個(gè)值為x的元素，找到后返回其邏輯序號(hào)，否則返回0（由于線性表的邏輯序號(hào)從1開始，這里用0表示沒有找到值為x的元素）。intLocate(SqListL,ElemTypex) {inti=0;

while(i<L.length&&L.data[i]!=x)i++; //查找值為x的第1個(gè)元素,查找范圍為0～L.length-1

if(i>=L.length)return(0);//未找到返回0

elsereturn(i+1);

//找到后返回其邏輯序號(hào)}2.2順序表19/133（6）插入元素運(yùn)算算法將新元素x插入到順序表L中邏輯序號(hào)為i的位置（如果插入成功，元素x成為線性表的第i個(gè)元素）。當(dāng)i無效時(shí)返回0（表示插入失?。?。有效時(shí)將L.data[i-1..L.length-1]后移一個(gè)位置，在L.data[i-1]處插入x，順序表長(zhǎng)度增1，并返回1（表示插入成功。2.2順序表20/133元素a1…an…下標(biāo)0…

i-1

…

n-1均后移一個(gè)位置ai…元素a1…an…下標(biāo)0…

i-1

i

…

nai…x插入元素x2.2順序表21/133intInsElem(SqList&L,ElemTypex,inti){intj;

if(i<1||i>L.length+1||L.length==MaxSize)return0; //無效的參數(shù)ifor(j=L.length;j>=i;j--)//將位置為i的結(jié)點(diǎn)及之后的結(jié)點(diǎn)后移L.data[j]=L.data[j-1];L.data[i-1]=x; //在位置i處放入x

L.length++; //線性表長(zhǎng)度增1

return1;}2.2順序表22/133算法分析當(dāng)i=n+1時(shí)（插入尾元素），移動(dòng)次數(shù)為0，呈現(xiàn)最好的情況。當(dāng)i=1時(shí)（插入第一個(gè)元素），移動(dòng)次數(shù)為n，呈現(xiàn)最壞的情況。2.2順序表23/133平均情況分析a1a2aian……n+1種插入情況在位置i插入新元素x，需要將ai～an的元素均后移一次，移動(dòng)次數(shù)為n-i+1。假設(shè)在等概率下pi（pi=1/(n+1)），移動(dòng)元素的平均次數(shù)為：2.2順序表24/133插入算法的主要時(shí)間花費(fèi)在元素移動(dòng)上，所以算法InsElem()的平均時(shí)間復(fù)雜度為O(n)。2.2順序表25/133（7）刪除元素運(yùn)算算法

刪除順序表L中邏輯序號(hào)為i的元素。在i無效時(shí)返回0（表示刪除失?。?。有效時(shí)將L.data[i..length-1]前移一個(gè)位置，順序表長(zhǎng)度減1，并返回1（表示刪除成功。2.2順序表26/133均前移一個(gè)位置元素a1…an…下標(biāo)0…

i-1i

…

n-1ai+1…ai元素a1…an…下標(biāo)0…

i-1…

n-2ai+1…刪除元素ai2.2順序表27/133intDelElem(SqList&L,inti){intj;

if(i<1||i>L.length) //無效的參數(shù)ireturn0;

for(j=i;j<L.length;j++) //將位置為i的結(jié)點(diǎn)之后的結(jié)點(diǎn)前移L.data[j-1]=L.data[j];

L.length--; //線性表長(zhǎng)度減1

return1;}2.2順序表28/133算法分析當(dāng)i=n時(shí)（刪除尾元素），移動(dòng)次數(shù)為0，呈現(xiàn)最好的情況。當(dāng)i=1時(shí)（刪除第一個(gè)元素），移動(dòng)次數(shù)為n-1，呈現(xiàn)最壞的情況。2.2順序表29/133平均情況分析a1a2aian……n種刪除情況刪除位置i的元素ai，需要將ai+1～an的元素均前移一次，移動(dòng)次數(shù)為n-(i+1)+1=n-i。假設(shè)在等概率下pi（pi=1/n），移動(dòng)元素的平均次數(shù)為：2.2順序表30/133刪除算法的主要時(shí)間花費(fèi)在元素移動(dòng)上，所以算法DelElem()的平均時(shí)間復(fù)雜度為O(n)。2.2順序表31/133（8）輸出元素值運(yùn)算算法

從頭到尾遍歷順序表L，輸出各元素值。voidDispList(SqListL){inti;

for(i=0;i<L.length;i++) printf("%d",L.data[i]);

printf("\n");}2.2順序表32/133將順序表類型聲明及其基本運(yùn)算函數(shù)存放在SqList.cpp文件中#include"SqList.cpp" //包括前面的順序表基本運(yùn)算函數(shù)intmain(){inti;ElemTypee;SqListL; //定義一個(gè)順序表L

InitList(L); //初始化順序表L

InsElem(L,1,1); //插入元素1

InsElem(L,3,2); //插入元素3

InsElem(L,1,3); //插入元素1

InsElem(L,5,4); //插入元素5

InsElem(L,4,5); //插入元素4

InsElem(L,2,6); //插入元素22.2順序表33/133printf("線性表:");DispList(L);printf("長(zhǎng)度:%d\n",GetLength(L));i=3;GetElem(L,i,e);printf("第%d個(gè)元素:%d\n",i,e);e=1;printf("元素%d是第%d個(gè)元素\n",e,Locate(L,e));i=4;printf("刪除第%d個(gè)元素\n",i);

DelElem(L,i);printf("線性表:");DispList(L);

DestroyList(L);}線性表:131542長(zhǎng)度:6第3個(gè)元素:1元素1是第1個(gè)元素刪除第4個(gè)元素線性表:131422.2順序表34/1332.整體創(chuàng)建順序表的算法假設(shè)給定一個(gè)含有n個(gè)元素的數(shù)組a，由它來創(chuàng)建順序表。voidCreateList(SqList&L,ElemTypea[],intn){inti,k=0; //k累計(jì)順序表L中的元素個(gè)數(shù)for(i=0;i<n;i++){L.data[k]=a[i]; //向L中添加一個(gè)元素k++; //L中元素個(gè)數(shù)增1}L.length=k; //設(shè)置L的長(zhǎng)度}2.2順序表35/1332.2.3順序表的算法設(shè)計(jì)示例1.基于順序表基本操作的算法設(shè)計(jì)這類算法設(shè)計(jì)中包括順序表元素的查找、插入和刪除等。2.2順序表36/133

【例2.3】假設(shè)有一個(gè)順序表L，其中元素為整數(shù)且所有元素值均不相同。設(shè)計(jì)一個(gè)算法將最大值元素與最小值元素交換。用maxi和mini記錄順序表L中最大值元素和最小值元素的下標(biāo)，初始時(shí)maxi=mini=0。i從1開始掃描所有元素：當(dāng)L.data[i]>L.data[maxi]時(shí)置maxi=i；否則若L.data[i]<L.data[mini]時(shí)置mini=i。掃描完畢時(shí)，L.data[maxi]為最大值元素，L.data[mini]為最小值元素，將它們交換。算法思路2.2順序表37/133voidswap(ElemType&x,ElemType&y) //交換x和y{ElemTypetmp=x;x=y;y=tmp;}voidSwapmaxmin(SqList&L) //交換L中最大值元素與最小值元素{inti,maxi,mini;maxi=mini=0;for(i=1;i<L.length;i++){if(L.data[i]>L.data[maxi])maxi=i;elseif(L.data[i]<L.data[mini])mini=i;}swap(L.data[maxi],L.data[mini]);}2.2順序表38/133

【例2.4】設(shè)計(jì)一個(gè)算法，從線性表中刪除自第i個(gè)元素開始的k個(gè)元素，其中線性表用順序表L存儲(chǔ)。將線性表中ai～ai+k-1元素（對(duì)應(yīng)L.data[i-1..i+k-2]的元素）刪除，即將ai+k～an（對(duì)應(yīng)L.data[i+k-1..n-1]）的所有元素依次前移k個(gè)位置。2.2順序表39/133均前移k個(gè)位置元素a1…an下標(biāo)0…

i-1…

i+k-2i+k-1…

n-1ai+k…ai…ai+k-12.2順序表40/133intDeletek(SqList&L,inti,intk){intj;

if(i<1||k<1||i+k-1>L.length)return0;

//判斷i和k是否合法

for(j=i+k-1;j<L.length;j++) //將元素前移k個(gè)位置L.data[j-k]=L.data[j];

L.length-=k;

//L的長(zhǎng)度減kreturn1;}2.2順序表41/133

【例2.5】已知線性表(a1,a2,…,an)采用順序表L存儲(chǔ)，且每個(gè)元素都是互不相等的整數(shù)。設(shè)計(jì)一個(gè)將所有奇數(shù)移到所有的偶數(shù)前邊的算法（要求時(shí)間最少，輔助空間最少）。

設(shè)計(jì)思路：置i=0，j=n-1，在順序表L中從左向右找到偶數(shù)L.data[i]，從右向左找到奇數(shù)L.data[j]，將兩者交換；循環(huán)這個(gè)過程直到i等于j為止。2.2順序表42/133voidMove(SqList&L){inti=0,j=L.length-1;while(i<j)

{while(L.data[i]%2==1)i++; //從前向后找偶數(shù)

while(L.data[j]%2==0)j--; //從后向前找奇數(shù)

if(i<j)

swap(L.data[i],L.data[j]);

//交換這兩元素}}a1a2a3a4a5a6a7指向偶數(shù)：ij：指向奇數(shù)交換2.2順序表43/1332.基于整體建表的算法設(shè)計(jì)這類算法設(shè)計(jì)中需要根據(jù)條件產(chǎn)生新的結(jié)果順序表。2.2順序表44/133

【例2.6】已知一個(gè)整數(shù)線性表采用順序表L存儲(chǔ)。設(shè)計(jì)一個(gè)盡可能高效的算法刪除其中所有值為x的元素（假設(shè)L中值為x的元素可能有多個(gè)）。

由于刪除所有x元素后得到的結(jié)果順序表可以與原L共享存儲(chǔ)空間，求解問題轉(zhuǎn)化為新建結(jié)果順序表。采用整體創(chuàng)建順序表的算法思路，將插入元素的條件設(shè)置為“不等于x”，即僅僅將不等于x的元素插入到L中。用k記錄結(jié)果順序表中元素個(gè)數(shù)（初始值為0）.掃描L，將L中所有不為x的元素重新插入到L中，每插入一個(gè)元素k增加1.最后置L的長(zhǎng)度為k。2.2順序表45/133voidDeletex(SqList&L,ElemTypex){inti,k=0;for(i=0;i<L.length;i++){if(L.data[i]!=x) //將不為x的元素插入到L中{L.data[k]=L.data[i];k++;}}L.length=k; //重置L的長(zhǎng)度}算法的時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)，屬于高效的算法。2.2順序表46/133

【例2.7】

已知一個(gè)整數(shù)線性表采用順序表L存儲(chǔ)。設(shè)計(jì)一個(gè)盡可能高效的算法刪除其中所有值為負(fù)整數(shù)的元素（假設(shè)L中值為負(fù)整數(shù)的元素可能有多個(gè)）。采用整體創(chuàng)建順序表的算法思路,僅僅將插入元素的條件設(shè)置為“元素值≥0”即可。2.2順序表47/133voidDeleteminus(SqList&L){inti,k=0;for(i=0;i<L.length;i++){if(L.data[i]>=0) //將不為負(fù)數(shù)的元素插入到L中{L.data[k]=L.data[i];k++;}}L.length=k; //重置L的長(zhǎng)度}2.2順序表48/1333.有序順序表的二路歸并算法有序表是指按元素值遞增或者遞減排列的線性表。有序順序表是有序表的順序存儲(chǔ)結(jié)構(gòu)。也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。對(duì)于有序表可以利用其元素的有序性提高相關(guān)算法的效率。二路歸并就是有序表的一種經(jīng)典算法。2.2順序表49/133

【例2.8】已知有兩個(gè)按元素值遞增有序的順序表A和B（這樣的順序表稱遞增有序順序表）。設(shè)計(jì)一個(gè)算法將順序表A和B的全部元素歸并到一個(gè)按元素遞增有序的順序表C中。并分析算法的空間復(fù)雜度和時(shí)間復(fù)雜度。

設(shè)計(jì)思路：用i遍歷順序表A，用j遍歷順序表B。當(dāng)A和B都未遍歷完時(shí)，比較兩者的當(dāng)前元素，則將較小者復(fù)制到C中，若兩者的當(dāng)前元素相等，則將這兩個(gè)元素都復(fù)制到C中。最后將尚未遍歷完的順序表的余下元素均復(fù)制到順序表C中。這一過程稱為二路歸并。2.2順序表50/133例如，A=（1，3，5），B＝（2，4，6，8）其二路歸并過程如下：

A：135

B：2468ij較小者復(fù)制到CC：1234568二路歸并過程兩個(gè)有序表合并成一個(gè)有序表的高效算法2.2順序表51/133voidMerge(SqListA,SqListB,SqList&C) //C為引用型參數(shù){inti=0,j=0,k=0;

//k記錄順序表C中的元素個(gè)數(shù)

while(i<A.length&&j<B.length)

{if(A.data[i]<B.data[j])

{C.data[k]=A.data[i];

i++;k++;

}

else //A.data[i]>B.data[j]

{C.data[k]=B.data[j];

j++;k++;

}

}2.2順序表52/133

while(i<A.length)

//將A中剩余的元素復(fù)制到C中

{ C.data[k]=A.data[i]; i++;k++;

}

while(j<B.length)

//將B中剩余的元素復(fù)制到C中

{ C.data[k]=B.data[j];

j++;k++;

}

C.length=k; //指定順序表C的實(shí)際長(zhǎng)度}本算法的空間復(fù)雜度為O(1)，時(shí)間復(fù)雜度為O(m+n)，其中m和n分別為順序表A和B的長(zhǎng)度。2.2順序表53/133

【例2.9】已知有兩個(gè)遞增有序順序表A和B，設(shè)計(jì)一個(gè)算法由順序表A和B的所有公共元素產(chǎn)生一個(gè)順序表C。并分析該算法的空間復(fù)雜度和時(shí)間復(fù)雜度。

采用二路歸并的思路，用i、j分別遍歷有序順序表A、B，跳過不相等的元素，將兩者相等的元素（即公共元素）放置到順序表C中。2.2順序表54/133voidCommelem(SqListA,SqListB,SqList&C){inti=0,j=0,k=0; //k記錄順序表C中的元素個(gè)數(shù)

while(i<A.length&&j<B.length)

{if(A.data[i]<B.data[j])

i++;

elseif(A.data[i]>B.data[j])

j++;

else

//A.data[i]=B.data[j]

{C.data[k]=A.data[i];

i++;j++;k++;

}

}

C.length=k; //指定順序表C的實(shí)際長(zhǎng)度}本算法的空間復(fù)雜度為O(1)，時(shí)間復(fù)雜度為O(m+n)。2.2順序表55/133

【例2.10】有兩個(gè)遞增有序順序表A和B，分別含有m和n個(gè)整數(shù)元素（最大的元素不超過32767），假設(shè)這m+n個(gè)元素均不相同。

設(shè)計(jì)一個(gè)盡可能高效的算法求這m+n個(gè)元素中第k小的元素。如果參數(shù)k錯(cuò)誤，算法返回0；否則算法返回1，并且用參數(shù)e表示求出的第k小的元素。2.2順序表56/133intTopk1(SqListA,SqListB,intk,ElemType&e){inti=0,j=0;if(k<1||k>A.length+B.length)return0; //參數(shù)錯(cuò)誤返回0while(i<A.length&&j<B.length){k--;if(A.data[i]<B.data[j]){if(k==0){e=A.data[i];return1;}i++;}2.2順序表采用二路歸并的思路，僅僅找第k次歸并的較小元素。57/133else{if(k==0){e=B.data[j];return1;}j++;}} //endwhileif(i<A.length) //A沒有掃描完畢e=A.data[i+k-1];elseif(j<B.length) //B沒有掃描完畢e=B.data[j+k-1];return1;}2.2順序表58/133改進(jìn)#defineINF32767intTopk2(SqListA,SqListB,intk,ElemType&e){inti=0,j=0;if(k<1||k>A.length+B.length)return0; //參數(shù)錯(cuò)誤返回02.2順序表59/133while(true){k--;intx=(i<A.length?A.data[i]:INF);inty=(j<B.length?B.data[j]:INF);if(x<y){if(k==0){e=x;return1;}i++;}else{if(k==0){e=y;return1;}j++;}}}2.2順序表60/1332.3單鏈表和循環(huán)單鏈表2.3.1單鏈表的定義

線性表的單鏈表存儲(chǔ)方法：用一個(gè)指針表示結(jié)點(diǎn)間的邏輯關(guān)系。因此單鏈表的一個(gè)存儲(chǔ)結(jié)點(diǎn)包含兩個(gè)部分，結(jié)點(diǎn)的形式如下：datanextdata：為數(shù)據(jù)域，用于存儲(chǔ)線性表的一個(gè)數(shù)據(jù)元素，也就是說在單鏈表中一個(gè)結(jié)點(diǎn)存放一個(gè)數(shù)據(jù)元素。next：為指針域或鏈域，用于存放一個(gè)指針，該指針指向后繼元素對(duì)應(yīng)的結(jié)點(diǎn)，也就是說單鏈表中結(jié)點(diǎn)的指針用于表示后繼關(guān)系。2.3單鏈表和循環(huán)單鏈表61/133單鏈表分為帶頭結(jié)點(diǎn)和不帶頭結(jié)點(diǎn)兩種類型。在許多情況下，帶頭結(jié)點(diǎn)的單鏈表能夠簡(jiǎn)化運(yùn)算的實(shí)現(xiàn)過程。因此這里討論的單鏈表除特別指出外均指帶頭結(jié)點(diǎn)的單鏈表。2.3單鏈表和循環(huán)單鏈表62/133仍假設(shè)數(shù)據(jù)元素的類型為ElemType。單鏈表的結(jié)點(diǎn)類型聲明如下：typedefstructnode{ElemTypedata;

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

structnode*next;

//指針域}SLinkNode;

//單鏈表結(jié)點(diǎn)類型2.3單鏈表和循環(huán)單鏈表63/133

在單鏈表中尾結(jié)點(diǎn)之后不再有任何結(jié)點(diǎn)，那么它的next域設(shè)置為什么值呢？有兩種方式：將尾結(jié)點(diǎn)的next域用一個(gè)特殊值NULL（空指針，不指向任何結(jié)點(diǎn)，只起標(biāo)志作用）表示，這樣的單鏈表為非循環(huán)單鏈表，通常所說的單鏈表都是指這種類型的單鏈表。將尾結(jié)點(diǎn)的next域指向頭結(jié)點(diǎn)，這樣可以通過尾結(jié)點(diǎn)移動(dòng)到頭結(jié)點(diǎn)，從而構(gòu)成一個(gè)查找環(huán)，將這樣的單鏈表為循環(huán)單鏈表。2.3單鏈表和循環(huán)單鏈表64/1332.3.2線性表基本運(yùn)算在單鏈表上的實(shí)現(xiàn)帶頭結(jié)點(diǎn)的單鏈表：a1a2an∧…Ldatanext不含實(shí)際值頭結(jié)點(diǎn)尾結(jié)點(diǎn)2.3單鏈表和循環(huán)單鏈表65/1331.單鏈表的基本運(yùn)算算法（1）初始化線性表運(yùn)算算法創(chuàng)建一個(gè)空的單鏈表，它只有一個(gè)頭結(jié)點(diǎn)，由L指向它。該結(jié)點(diǎn)的next域?yàn)榭?，data域未設(shè)定任何值。對(duì)應(yīng)的算法如下：voidInitList(SLinkNode*&L)

//L為引用型參數(shù){L=(SLinkNode*)malloc(sizeof(SLinkNode));

//創(chuàng)建頭結(jié)點(diǎn)L

L->next=NULL;}2.3單鏈表和循環(huán)單鏈表66/133（2）銷毀線性表運(yùn)算算法一個(gè)單鏈表中的所有結(jié)點(diǎn)空間都是通過malloc函數(shù)分配的，在不再需要時(shí)需通過free函數(shù)釋放所有結(jié)點(diǎn)的空間。a1a2an∧…Lprep2.3單鏈表和循環(huán)單鏈表67/133voidDestroyList(SLinkNode*&L){SLinkNode*pre=L,*p=pre->next;

while(p!=NULL)

{free(pre);

pre=p;p=p->next; //pre、p同步后移

}

free(pre);}2.3單鏈表和循環(huán)單鏈表68/133（3）求線性表的長(zhǎng)度運(yùn)算算法設(shè)置一個(gè)整型變量i作為計(jì)數(shù)器，i初值為0，p初始時(shí)指向第一個(gè)數(shù)據(jù)結(jié)點(diǎn)。然后沿next域逐個(gè)往后查找，每移動(dòng)一次，i值增1。當(dāng)p所指結(jié)點(diǎn)為空時(shí)，結(jié)束這個(gè)過程，i之值即為表長(zhǎng)。intGetLength(SLinkNode*L){

inti=0;

SLinkNode*p=L->next;

while(p!=NULL)

{i++;

p=p->next;

}

returni;}2.3單鏈表和循環(huán)單鏈表69/133（4）求線性表中第i個(gè)元素運(yùn)算算法用p從頭開始遍歷單鏈表L中的結(jié)點(diǎn)，用計(jì)數(shù)器j累計(jì)遍歷過的結(jié)點(diǎn)，其初值為0。在遍歷時(shí)j等于i時(shí)，若p不為空，則p所指結(jié)點(diǎn)即為要找的結(jié)點(diǎn)，查找成功，算法返回1。否則算法返回0表示未找到這樣的結(jié)點(diǎn)。2.3單鏈表和循環(huán)單鏈表70/133intGetElem(SLinkNode*L,inti,ElemType&e){intj=0;

SLinkNode*p=L; //p指向頭結(jié)點(diǎn)，計(jì)數(shù)器j置為0

if(i<=0)return0; //參數(shù)i錯(cuò)誤返回0

while(p!=NULL&&j<i)

{j++;

p=p->next;

}

if(p==NULL)return0; //未找到返回0

else

{e=p->data;

return1; //找到后返回1

}}2.3單鏈表和循環(huán)單鏈表71/133（5）按值查找運(yùn)算算法在單鏈表L中從第一個(gè)數(shù)據(jù)結(jié)點(diǎn)開始查找第一個(gè)值域與e相等的結(jié)點(diǎn)，若存在這樣的結(jié)點(diǎn)，則返回其邏輯序號(hào)；否則返回0。2.3單鏈表和循環(huán)單鏈表72/133intLocate(SLinkNode*L,ElemTypee) {SLinkNode*p=L->next;

intj=1; //p指向第一個(gè)數(shù)據(jù)結(jié)點(diǎn)，j置為其序號(hào)1

while(p!=NULL&&p->data!=e)

{ p=p->next; j++;

}

if(p==NULL)return(0); //未找到返回0

elsereturn(j); //找到后返回其序號(hào)}2.3單鏈表和循環(huán)單鏈表73/133（6）插入元素運(yùn)算算法在單鏈表L中插入第i個(gè)值為x的結(jié)點(diǎn)。先在單鏈表L中查找第i-1個(gè)結(jié)點(diǎn)，若未找到返回0；找到后由p指向該結(jié)點(diǎn)，創(chuàng)建一個(gè)以x為值的新結(jié)點(diǎn)s，將其插入到p指結(jié)點(diǎn)之后。2.3單鏈表和循環(huán)單鏈表74/133插入操作：在p結(jié)點(diǎn)之后插入s結(jié)點(diǎn)的操作如下：

注意：插入操作的①和②執(zhí)行順序不能顛倒。①結(jié)點(diǎn)s的next域指向p的下一個(gè)結(jié)點(diǎn)（s->next=p->next）。②將結(jié)點(diǎn)p的next域改為指向新結(jié)點(diǎn)s（p->next=s）。*p*sx①②2.3單鏈表和循環(huán)單鏈表75/133intInsElem(SLinkNode*&L,ElemTypex,inti) {intj=0;

SLinkNode*p=L,*s;if(i<=0)return0;

//參數(shù)i錯(cuò)誤返回0

while(p!=NULL&&j<i-1)

//查找第i-1個(gè)結(jié)點(diǎn)p

{ j++; p=p->next;

}

if(p==NULL)return0;

//未找到第i-1個(gè)結(jié)點(diǎn)時(shí)返回0

else

//找到第i-1個(gè)結(jié)點(diǎn)p

{ s=(SLinkNode*)malloc(sizeof(SLinkNode)); s->data=x;

//創(chuàng)建存放元素x的新結(jié)點(diǎn)s s->next=p->next;

//將s結(jié)點(diǎn)插入到p結(jié)點(diǎn)之后

p->next=s; return1; //插入運(yùn)算成功,返回1

}}2.3單鏈表和循環(huán)單鏈表76/133（7）刪除元素運(yùn)算算法先在單鏈表L中查找第i-1個(gè)結(jié)點(diǎn)，若未找到返回0。找到后由p指向該結(jié)點(diǎn)，然后讓q指向后繼結(jié)點(diǎn)（即要?jiǎng)h除的結(jié)點(diǎn)）。若q所指結(jié)點(diǎn)為空則返回0，否則刪除q結(jié)點(diǎn)并釋放其占用的空間。在單鏈表L中刪除第i個(gè)結(jié)點(diǎn)。2.3單鏈表和循環(huán)單鏈表77/133刪除p指結(jié)點(diǎn)的后繼結(jié)點(diǎn)的過程：

刪除操作：p->next=q->next;free(q);*p**q2.3單鏈表和循環(huán)單鏈表78/133intDelElem(SLinkNode*&L,inti){intj=0;

SLinkNode*p=L,*q;if(i<=0)return0;

//參數(shù)i錯(cuò)誤返回0

while(p!=NULL&&j<i-1) //查找第i-1個(gè)結(jié)點(diǎn)

{ j++; p=p->next;

}

if(p==NULL)return0;

//未找到第i-1個(gè)結(jié)點(diǎn)時(shí)返回0

else

//找到第i-1個(gè)結(jié)點(diǎn)p

{ q=p->next;

//q指向被刪結(jié)點(diǎn)

if(q==NULL)return0;//沒有第i個(gè)結(jié)點(diǎn)時(shí)返回0 else

{p->next=q->next;

//從單鏈表中刪除q結(jié)點(diǎn)

free(q); //釋放其空間

return1; }

}}2.3單鏈表和循環(huán)單鏈表79/133（8）輸出線性表運(yùn)算算法從第一個(gè)數(shù)據(jù)結(jié)點(diǎn)開始，沿next域逐個(gè)往下遍歷，輸出每個(gè)遍歷到結(jié)點(diǎn)的data域，直到尾結(jié)點(diǎn)為止。voidDispList(SLinkNode*L){SLinkNode*p=L->next;

while(p!=NULL){ printf("%d",p->data); p=p->next;

}

printf("\n");}2.3單鏈表和循環(huán)單鏈表80/133可以通過調(diào)用基本運(yùn)算算法來創(chuàng)建單鏈表，其過程是先初始化一個(gè)單鏈表，然后向其中一個(gè)一個(gè)地插入元素。這里介紹是快速創(chuàng)建整個(gè)單鏈表的算法，也稱為整體建表。假設(shè)給定一個(gè)含有n個(gè)元素的數(shù)組a，由它來創(chuàng)建單鏈表，這種建立單鏈表的常用方法有兩種。2.整體創(chuàng)建單鏈表的算法2.3單鏈表和循環(huán)單鏈表81/133（1）頭插法建表從一個(gè)空單鏈表（含有一個(gè)L指向的頭結(jié)點(diǎn)）開始。讀取數(shù)組a（含有n個(gè)元素）中的一個(gè)元素，生成一個(gè)新結(jié)點(diǎn)s，將讀取的數(shù)據(jù)元素存放到新結(jié)點(diǎn)的數(shù)據(jù)域中。將新結(jié)點(diǎn)s插入到當(dāng)前鏈表的表頭上。再讀取數(shù)組a的下一個(gè)元素，采用相同的操作建立新結(jié)點(diǎn)s并插入到單鏈表L中，直到數(shù)組a中所有元素讀完為止。2.3單鏈表和循環(huán)單鏈表82/133voidCreateListF(SLinkNode*&L,ElemTypea[],intn){SLinkNode*s;inti;

L=(SLinkNode*)malloc(sizeof(SLinkNode));//創(chuàng)建頭結(jié)點(diǎn)L->next=NULL; //頭結(jié)點(diǎn)的next域置空，表示一個(gè)空單鏈表

for(i=0;i<n;i++) //遍歷a數(shù)組所有元素

{ s=(SLinkNode*)malloc(sizeof(SLinkNode)); s->data=a[i]; //創(chuàng)建存放a[i]元素的新結(jié)點(diǎn)s s->next=L->next; //將s插在頭結(jié)點(diǎn)之后

L->next=s;

}}2.3單鏈表和循環(huán)單鏈表83/133若數(shù)組a包含元素1、2、3和4，則調(diào)用CreateListF(L,a,4)建立的單鏈表如下圖所示。從中看到，單鏈表L中數(shù)據(jù)結(jié)點(diǎn)的次序與數(shù)組a的元素次序正好相反。L4321∧2.3單鏈表和循環(huán)單鏈表84/133（2）尾插法建表從一個(gè)空單鏈表（含有一個(gè)L指向的頭結(jié)點(diǎn)）開始。讀取數(shù)組a（含有n個(gè)元素）中的一個(gè)元素，生成一個(gè)新結(jié)點(diǎn)s，將讀取的數(shù)據(jù)元素存放到新結(jié)點(diǎn)的數(shù)據(jù)域中。將新結(jié)點(diǎn)s插入到當(dāng)前鏈表的表尾上。再讀取數(shù)組a的下一個(gè)元素，采用相同的操作建立新結(jié)點(diǎn)s并插入到單鏈表L中，直到數(shù)組a中所有元素讀完為止。由于尾插法算法每次將新結(jié)點(diǎn)插到當(dāng)前鏈表的表尾上，為此增加一個(gè)尾指針tc，使其始終指向當(dāng)前鏈表的尾結(jié)點(diǎn)。2.3單鏈表和循環(huán)單鏈表85/133voidCreateListR(SLinkNode*&L,ElemTypea[],intn){SLinkNode*s,*tc;inti;

L=(SLinkNode*)malloc(sizeof(SLinkNode));//創(chuàng)建頭結(jié)點(diǎn)

tc=L; //tc始終指向尾結(jié)點(diǎn),初始時(shí)指向頭結(jié)點(diǎn)

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

{ s=(SLinkNode*)malloc(sizeof(SLinkNode)); s->data=a[i]; //創(chuàng)建存放a[i]元素的新結(jié)點(diǎn)s tc->next=s; //將s插入tc之后

tc=s;

}

tc->next=NULL; //尾結(jié)點(diǎn)next域置為NULL}2.3單鏈表和循環(huán)單鏈表86/133若數(shù)組a包含元素1、2、3和4，則調(diào)用CreateListR(L,a,4)建立的單鏈表如下圖所示.從中看到，單鏈表L中數(shù)據(jù)結(jié)點(diǎn)的次序與數(shù)組a的元素次序相同。L1234∧2.3單鏈表和循環(huán)單鏈表87/1332.3.3單鏈表的算法設(shè)計(jì)示例1.基于單鏈表基本操作的算法設(shè)計(jì)這類算法設(shè)計(jì)中包括單鏈表結(jié)點(diǎn)的查找、插入和刪除等。2.3單鏈表和循環(huán)單鏈表88/133

【例2.11】設(shè)計(jì)一個(gè)算法，通過一趟遍歷確定單鏈表L（至少含兩個(gè)數(shù)據(jù)結(jié)點(diǎn)）中第一個(gè)元素值最大的結(jié)點(diǎn)。用p遍歷單鏈表，在遍歷時(shí)用maxp指向data域值最大的結(jié)點(diǎn)（maxp的初值為p）。當(dāng)單鏈表遍歷完畢，最后返回maxp。2.3單鏈表和循環(huán)單鏈表89/133SLinkNode*Maxnode(SLinkNode*L){SLinkNode*p=L->next,*maxp=p;

while(p!=NULL) //遍歷所有的結(jié)點(diǎn)

{if(maxp->data<p->data)

maxp=p; //當(dāng)p指向更大的結(jié)點(diǎn)時(shí)，將其賦給maxp

p=p->next; //p沿next域下移一個(gè)結(jié)點(diǎn)

}

returnmaxp;}2.3單鏈表和循環(huán)單鏈表90/133

【例2.13】設(shè)計(jì)一個(gè)算法，刪除一個(gè)單鏈表L（至少含兩個(gè)數(shù)據(jù)結(jié)點(diǎn)）中第一個(gè)元素值最大的結(jié)點(diǎn)。在單鏈表中刪除一個(gè)結(jié)點(diǎn)先要找到它的前驅(qū)結(jié)點(diǎn)。以p遍歷單鏈表，pre指向p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。在遍歷時(shí)用maxp指向data域值最大的結(jié)點(diǎn)，maxpre指向maxp結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。當(dāng)單鏈表遍歷完畢，通過maxpre結(jié)點(diǎn)刪除其后的結(jié)點(diǎn)，即刪除了元素值最大的結(jié)點(diǎn)。2.3單鏈表和循環(huán)單鏈表91/133voidDelmaxnode(SLinkNode*&L){SLinkNode*p=L->next,*pre=L,*maxp=p,*maxpre=pre;

while(p!=NULL)

{if(maxp->data<p->data)

{maxp=p;

maxpre=pre;

}

pre=p; //pre、p同步后移，保證pre始終為p的前驅(qū)結(jié)點(diǎn)

p=p->next;

}

maxpre->next=maxp->next; //刪除maxp結(jié)點(diǎn)

free(maxp); //釋放maxp結(jié)點(diǎn)}2.3單鏈表和循環(huán)單鏈表92/1332.基于整體建表的算法設(shè)計(jì)這類算法設(shè)計(jì)中需要根據(jù)條件產(chǎn)生新的結(jié)果單鏈表。而創(chuàng)建結(jié)果單鏈表的方法有頭插法和尾插法。2.3單鏈表和循環(huán)單鏈表93/133

【例2.14】設(shè)計(jì)一個(gè)算法，將一個(gè)單鏈表L（至少含兩個(gè)數(shù)據(jù)結(jié)點(diǎn)）中所有結(jié)點(diǎn)逆置。并分析算法的時(shí)間復(fù)雜度。先將單鏈表L拆分成兩部分，一部分是只有頭結(jié)點(diǎn)L的空表，另一部分是由p指向第一個(gè)數(shù)據(jù)結(jié)點(diǎn)的單鏈表。然后遍歷p，將p所指結(jié)點(diǎn)逐一采用頭插法插入到L單鏈表中，由于頭插法的特點(diǎn)是建成的單鏈表結(jié)點(diǎn)次序與插入次序正好相反，從而達(dá)到結(jié)點(diǎn)逆置的目的。2.3單鏈表和循環(huán)單鏈表94/133voidReverse(SLinkNode*&L){SLinkNode*p=L->next,*q;

L->next=NULL;

while(p!=NULL) //遍歷所有數(shù)據(jù)結(jié)點(diǎn)

{ q=p->next; //q臨時(shí)保存p結(jié)點(diǎn)之后的結(jié)點(diǎn)

p->next=L->next; //將結(jié)點(diǎn)p插入到頭結(jié)點(diǎn)之后

L->next=p; p=q;

}}2.3單鏈表和循環(huán)單鏈表95/1333.有序單鏈表的二路歸并算法有序單鏈表是有序表的單鏈表存儲(chǔ)結(jié)構(gòu)，同樣可以利用有序表元素的有序性提高相關(guān)算法的效率。當(dāng)數(shù)據(jù)采用單鏈表存儲(chǔ)時(shí)，對(duì)應(yīng)的二路歸并就是單鏈表二路歸并算法。2.3單鏈表和循環(huán)單鏈表96/133

【例2.16】設(shè)ha和hb分別是兩個(gè)帶頭結(jié)點(diǎn)的遞增有序單鏈表。設(shè)計(jì)一個(gè)算法，將這兩個(gè)有序鏈表的所有數(shù)據(jù)結(jié)點(diǎn)合并成一個(gè)遞增有序的單鏈表hc，并分析算法的時(shí)間和空間復(fù)雜度。

要求hc單鏈表仍使用原來兩個(gè)鏈表的存儲(chǔ)空間，不另外占用其他的存儲(chǔ)空間，ha和hb兩個(gè)表中允許有重復(fù)的數(shù)據(jù)結(jié)點(diǎn)。2.3單鏈表和循環(huán)單鏈表97/133本例合并后ha、hb兩個(gè)單鏈表都不存在了。用二路歸并的思路。用pa遍歷ha的數(shù)據(jù)結(jié)點(diǎn)，pb遍歷hb的數(shù)據(jù)結(jié)點(diǎn)。將ha頭結(jié)點(diǎn)用作新單鏈表hc的頭結(jié)點(diǎn)，讓tc始終指向hc的尾結(jié)點(diǎn)（初始時(shí)指向hc）。當(dāng)pa和pb均不為空時(shí)循環(huán)：比較pa與pb之data域值，將較小者鏈到pc之后。如此重復(fù)直到ha或hb為空，再將余下的鏈表鏈接到tc之后。2.3單鏈表和循環(huán)單鏈表98/133voidMerge(SLinkNode*ha,SLinkNode*hb,SLinkNode*&hc){SLinkNode*pa=ha->next,*pb=hb->next,*tc;

hc=ha;tc=hc;

//將ha的頭結(jié)點(diǎn)用作hc的頭結(jié)點(diǎn)

free(hb);

//釋放hb的頭結(jié)點(diǎn)

while(pa!=NULL&&pb!=NULL)

{if(pa->data<pb->data)

{tc->next=pa;tc=pa;

//將pa鏈接到tc之后

pa=pa->next;

}

else //pa->data>pb->data

{tc->next=pb;tc=pb; //將pb鏈接到tc之后

pb=pb->next;

}

}

tc->next=NULL;

if(pa!=NULL)tc->next=pa;

//ha單鏈表還有結(jié)點(diǎn)時(shí)

if(pb!=NULL)tc->next=pb;

//hb單鏈表還有結(jié)點(diǎn)時(shí)}2.3單鏈表和循環(huán)單鏈表99/1334.單鏈表的排序在很多情況下，單鏈表中結(jié)點(diǎn)有序時(shí)可以提高相應(yīng)算法的效率。2.3單鏈表和循環(huán)單鏈表100/133

【例2.18】設(shè)計(jì)一個(gè)完整的程序，根據(jù)用戶輸入的學(xué)生人數(shù)n（n≥3）及每個(gè)學(xué)生姓名和成績(jī)建立一個(gè)單鏈表，并按學(xué)生成績(jī)遞減排序，然后按名次輸出所有學(xué)生的姓名和成績(jī)。解：依題意，聲明學(xué)生單鏈表結(jié)點(diǎn)類型為StudList：typedefstructnode{charname[10]; //姓名

intscore; //成績(jī)域

structnode*next; //指針域}StudList; //學(xué)生單鏈表結(jié)點(diǎn)類型2.3單鏈表和循環(huán)單鏈表101/133例如，有4個(gè)學(xué)生記錄，其姓名和成績(jī)分別為：（Mary，75），（John，90），（Smith，85），（Harry，95），其構(gòu)建的帶頭結(jié)點(diǎn)的單鏈表如下圖所示。LMary∧75John90Smith85Harry952.3單鏈表和循環(huán)單鏈表102/133設(shè)計(jì)基本運(yùn)算算法如下：voidCreateStudent(StudList*&sl)：采用交互式方式創(chuàng)建學(xué)生單鏈表。voidDestroyList(StudList*&L)：銷毀學(xué)生單鏈表。voidDispList(StudList*L)：輸出學(xué)生單鏈表。voidSortList(StudList*&L)：將學(xué)生單鏈表按成績(jī)遞減排序。2.3單鏈表和循環(huán)單鏈表103/133采用尾插法創(chuàng)建學(xué)生單鏈表的算法如下：voidCreateStudent(StudList*&sl) //采用尾插法創(chuàng)建學(xué)生單鏈表{intn,i; StudList*s,*tc;

sl=(StudList*)malloc(sizeof(StudList));

//創(chuàng)建頭結(jié)點(diǎn)

tc=sl; //tc始終指向尾結(jié)點(diǎn),開始時(shí)指向頭結(jié)點(diǎn)

printf("學(xué)生人數(shù):");

scanf("%d",&n);

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

{ s=(StudList*)malloc(sizeof(StudList));//創(chuàng)建新結(jié)點(diǎn)

printf("第%d個(gè)學(xué)生姓名和成績(jī):",i+1); scanf("%s",s->name); //輸入姓名和成績(jī)

scanf("%d",&s->score); tc->next=s; //將s插入tc之后

tc=s;

}

tc->next=NULL; //尾結(jié)點(diǎn)next域置為NULL}2.3單鏈表和循環(huán)單鏈表104/133銷毀學(xué)生單鏈表的算法如下：voidDestroyList(StudList*&L)//銷毀學(xué)生單鏈表{StudList*pre=L,*p=pre->next;

while(p!=NULL)

{ free(pre); pre=p;p=p->next; //pre、p同步后移

}

free(pre);}2.3單鏈表和循環(huán)單鏈表105/133輸出學(xué)生單鏈表的算法如下：voidDispList(StudList*L) //輸出學(xué)生單鏈表{StudList*p=L->next;

inti=1;

printf("名次姓名成績(jī)\n");

while(p!=NULL)

{ printf("%d\t\t",i++); printf("%s\t\t",p->name); printf("%d\n",p->score); p=p->next;

}}2.3單鏈表和循環(huán)單鏈表106/133學(xué)生單鏈表按成績(jī)遞減排序的算法設(shè)計(jì)：LMary∧∧75John90Smith85Harry95p斷開成兩個(gè)部分將p結(jié)點(diǎn)有序插入到L中：在L中從前向后查找第一個(gè)score小于等于p->score的結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)pre。將p結(jié)點(diǎn)插入在pre結(jié)點(diǎn)之后。直到p=NULL。2.3單鏈表和循環(huán)單鏈表107/133學(xué)生單鏈表按成績(jī)遞減排序的算法如下：voidSortList(StudList*&L) //將學(xué)生單鏈表按成績(jī)遞減排序{StudList*p,*pre,*q;

p=L->next->next; //p指向L的第2個(gè)數(shù)據(jù)結(jié)點(diǎn)

L->next->next=NULL; //構(gòu)造只含一個(gè)數(shù)據(jù)結(jié)點(diǎn)的有序表while(p!=NULL)

{ q=p->next; //q保存p結(jié)點(diǎn)后繼結(jié)點(diǎn)的指針

pre=L;

//從有序表開頭進(jìn)行比較,pre指向插入p的前驅(qū)結(jié)點(diǎn)

while(pre->next!=NULL&&pre->next->score>p->score)

pre=pre->next; //在有序表中找插入p的前驅(qū)結(jié)點(diǎn)pre p->next=pre->next; //將pre之后插入p pre->next=p; p=q; //掃描原單鏈表余下的結(jié)點(diǎn)

}}2.3單鏈表和循環(huán)單鏈表108/133最后設(shè)計(jì)如下主函數(shù)：intmain(){StudList*st;

printf("(1)建立學(xué)生單鏈表\n");

CreateStudent(st);

printf("(2)按成績(jī)遞減排序\n");

SortList(st);

printf("(3)排序后的結(jié)果\n");DispList(st);

printf("(4)銷毀學(xué)生單鏈表\n");DestroyList(st);}2.3單鏈表和循環(huán)單鏈表109/133本程序的一次執(zhí)行結(jié)果如下（下劃線部分表示用戶輸入，↙表示回車鍵）：(1)建立學(xué)生單鏈表學(xué)生人數(shù):4↙

第1個(gè)學(xué)生姓名和成績(jī):Mary75↙

第2個(gè)學(xué)生姓名和成績(jī):John90↙

第3個(gè)學(xué)生姓名和成績(jī):Smith85↙

第4個(gè)學(xué)生姓名和成績(jī):Harry95↙(2)按成績(jī)遞減排序(3)排序后的結(jié)果名次

姓名成績(jī)

1Harry952John903Smith854Mary75(4)銷毀學(xué)生單鏈表2.3單鏈表和循環(huán)單鏈表110/1332.3.4循環(huán)單鏈表循環(huán)單鏈表的特點(diǎn)是表中尾結(jié)點(diǎn)的next域指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)。在循環(huán)鏈表中，從任一結(jié)點(diǎn)出發(fā)都可以找到表中其他結(jié)點(diǎn)。循環(huán)單鏈表L中，p所指結(jié)點(diǎn)為尾結(jié)點(diǎn)的條件是：p->next==L。帶頭結(jié)點(diǎn)的循環(huán)單鏈表：a1a2an…Ldatanext頭結(jié)點(diǎn)尾結(jié)點(diǎn)2.3單鏈表和循環(huán)單鏈表111/133（1）初始化線性表運(yùn)算算法創(chuàng)建一個(gè)空的循環(huán)單鏈表，它只有頭結(jié)點(diǎn)，由L指向它。該結(jié)點(diǎn)的next域指向該頭結(jié)點(diǎn)，data域未設(shè)定任何值。voidInitList(SLinkNode*&L)

//L為引用型參數(shù){L=(SLinkNode*)malloc(sizeof(SLinkNode));

L->next=L;}循環(huán)單鏈表的基本運(yùn)算算法設(shè)計(jì)。2.3單鏈表和循環(huán)單鏈表112/133（2）銷毀線性表運(yùn)算算法一個(gè)循環(huán)單鏈表中的所有結(jié)點(diǎn)空間都是通過malloc函數(shù)分配的，在不再需要時(shí)需通過free函數(shù)釋放所有結(jié)點(diǎn)的空間。voidDestroyList(SLinkNode*&L){SLinkNode*pre=L,*p=pre->next;

while(p!=L)

{ free(pre); pre=p;p=p->next; //pre、p同步后移

}

free(pre);}2.3單鏈表和循環(huán)單鏈表113/133（3）求線性表的長(zhǎng)度運(yùn)算算法設(shè)置一個(gè)整型變量i作為計(jì)數(shù)器，i初值為0，p初始時(shí)指向第一個(gè)結(jié)點(diǎn)。然后沿next域逐個(gè)往下移動(dòng)，每移動(dòng)一次，i值增1。當(dāng)p所指結(jié)點(diǎn)為頭結(jié)點(diǎn)時(shí)這一過程結(jié)束，i之值即為表長(zhǎng)。intGetLength(SLinkNode*L){inti=0;

SLinkNode*p=L->next;

while(p!=L)

{ i++; p=p->next;

}

returni;}2.3單鏈表和循環(huán)單鏈表114/133（4）求線性表中第i個(gè)元素運(yùn)算算法用p從頭開始遍歷循環(huán)單鏈表L中的結(jié)點(diǎn)（初值指向第一個(gè)數(shù)據(jù)結(jié)點(diǎn)），用計(jì)數(shù)器j累計(jì)遍歷過的結(jié)點(diǎn)，其初值為1。當(dāng)p不為L(zhǎng)且j<i時(shí)循環(huán)，p后移一個(gè)結(jié)點(diǎn)，j增1。當(dāng)循環(huán)結(jié)束時(shí)，若p指向頭結(jié)點(diǎn)則表示查找失敗返回0，否則p所指結(jié)點(diǎn)即為要找的結(jié)點(diǎn)，查找成功，算法返回1。2.3單鏈表和循環(huán)單鏈表115/133intGetElem(SLinkNode*L,inti,ElemType&e){intj=1;

SLinkNode*p=L->next; //p指向首結(jié)點(diǎn)，計(jì)數(shù)器j置為1

if(i<=0)return0; //參數(shù)i錯(cuò)誤返回0

while(p!=L&&j<i) //找第i個(gè)結(jié)點(diǎn)p

{ j++; p=p->next;

}

if(p==L)return0; //未找到返回0

else

{ e=p->data; return1;

//找到后返回1

}}2.3單鏈表和循環(huán)單鏈表116/133（5）按值查找運(yùn)算算法

用i累計(jì)查找數(shù)據(jù)結(jié)點(diǎn)的個(gè)數(shù)，從第一個(gè)數(shù)據(jù)結(jié)點(diǎn)開始，由前往后依次比較單鏈表中各結(jié)點(diǎn)數(shù)據(jù)域的值。若某結(jié)點(diǎn)數(shù)據(jù)域的值等于給定值x，則返回i；否則繼續(xù)向后比較。若整個(gè)單鏈表中沒有這樣的結(jié)點(diǎn)，則返回0。2.3單鏈表和循環(huán)單鏈表117/133intLocate(SLinkNode*L,ElemTypex) {

inti=1;

SLinkNod