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

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

解：算法思路：依次檢查線性表B中的每個元素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中找到了，將其刪除

}}線性表的基本運算算法2.1線性表的基本概念9/133

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

算法思路：先初始化線性表C，然后依次檢查線性表A中的每個元素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順序表的定義順序表是線性表采用順序存儲結(jié)構(gòu)在計算機(jī)內(nèi)存中的存儲方式，它由多個連續(xù)的存儲單元構(gòu)成，每個存儲單元存放線性表的一個元素。順序表邏輯上相鄰的數(shù)據(jù)元素在內(nèi)存的存儲結(jié)構(gòu)中也是相鄰的，不需要額外的內(nèi)存空間來存放元素之間的邏輯關(guān)系。2.2順序表12/133假定線性表的數(shù)據(jù)元素的類型為ElemType，在C/C++語言中，順序表類型聲明如下：#defineMaxSize100typedefintElemType;

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

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

intlength; //順序表的實際長度}SqList; //順序表類型2.2順序表13/133順序表的示意圖如下：

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

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

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

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

returnL.length;}2.2順序表17/133（4）求線性表中第i個元素運算算法

在邏輯序號i無效時返回特殊值0（假），有效時返回1（真），并用引用型形參e返回第i個元素的值。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）按值查找運算算法

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

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

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

elsereturn(i+1);

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

i-1

…

n-1均后移一個位置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é)點及之后的結(jié)點后移L.data[j]=L.data[j-1];L.data[i-1]=x; //在位置i處放入x

L.length++; //線性表長度增1

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

刪除順序表L中邏輯序號為i的元素。在i無效時返回0（表示刪除失敗）。有效時將L.data[i..length-1]前移一個位置，順序表長度減1，并返回1（表示刪除成功。2.2順序表26/133均前移一個位置元素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é)點之后的結(jié)點前移L.data[j-1]=L.data[j];

L.length--; //線性表長度減1

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

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

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

printf("\n");}2.2順序表32/133將順序表類型聲明及其基本運算函數(shù)存放在SqList.cpp文件中#include"SqList.cpp" //包括前面的順序表基本運算函數(shù)intmain(){inti;ElemTypee;SqListL; //定義一個順序表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("長度:%d\n",GetLength(L));i=3;GetElem(L,i,e);printf("第%d個元素:%d\n",i,e);e=1;printf("元素%d是第%d個元素\n",e,Locate(L,e));i=4;printf("刪除第%d個元素\n",i);

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

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

【例2.3】假設(shè)有一個順序表L，其中元素為整數(shù)且所有元素值均不相同。設(shè)計一個算法將最大值元素與最小值元素交換。用maxi和mini記錄順序表L中最大值元素和最小值元素的下標(biāo)，初始時maxi=mini=0。i從1開始掃描所有元素：當(dāng)L.data[i]>L.data[maxi]時置maxi=i；否則若L.data[i]<L.data[mini]時置mini=i。掃描完畢時，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è)計一個算法，從線性表中刪除自第i個元素開始的k個元素，其中線性表用順序表L存儲。將線性表中ai～ai+k-1元素（對應(yīng)L.data[i-1..i+k-2]的元素）刪除，即將ai+k～an（對應(yīng)L.data[i+k-1..n-1]）的所有元素依次前移k個位置。2.2順序表39/133均前移k個位置元素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個位置L.data[j-k]=L.data[j];

L.length-=k;

//L的長度減kreturn1;}2.2順序表41/133

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

設(shè)計思路：置i=0，j=n-1，在順序表L中從左向右找到偶數(shù)L.data[i]，從右向左找到奇數(shù)L.data[j]，將兩者交換；循環(huán)這個過程直到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è)計這類算法設(shè)計中需要根據(jù)條件產(chǎn)生新的結(jié)果順序表。2.2順序表44/133

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

由于刪除所有x元素后得到的結(jié)果順序表可以與原L共享存儲空間，求解問題轉(zhuǎn)化為新建結(jié)果順序表。采用整體創(chuàng)建順序表的算法思路，將插入元素的條件設(shè)置為“不等于x”，即僅僅將不等于x的元素插入到L中。用k記錄結(jié)果順序表中元素個數(shù)（初始值為0）.掃描L，將L中所有不為x的元素重新插入到L中，每插入一個元素k增加1.最后置L的長度為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的長度}算法的時間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)，屬于高效的算法。2.2順序表46/133

【例2.7】

已知一個整數(shù)線性表采用順序表L存儲。設(shè)計一個盡可能高效的算法刪除其中所有值為負(fù)整數(shù)的元素（假設(shè)L中值為負(fù)整數(shù)的元素可能有多個）。采用整體創(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的長度}2.2順序表48/1333.有序順序表的二路歸并算法有序表是指按元素值遞增或者遞減排列的線性表。有序順序表是有序表的順序存儲結(jié)構(gòu)。也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。對于有序表可以利用其元素的有序性提高相關(guān)算法的效率。二路歸并就是有序表的一種經(jīng)典算法。2.2順序表49/133

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

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

A：135

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

//k記錄順序表C中的元素個數(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的實際長度}本算法的空間復(fù)雜度為O(1)，時間復(fù)雜度為O(m+n)，其中m和n分別為順序表A和B的長度。2.2順序表53/133

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

采用二路歸并的思路，用i、j分別遍歷有序順序表A、B，跳過不相等的元素，將兩者相等的元素（即公共元素）放置到順序表C中。2.2順序表54/133voidCommelem(SqListA,SqListB,SqList&C){inti=0,j=0,k=0; //k記錄順序表C中的元素個數(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的實際長度}本算法的空間復(fù)雜度為O(1)，時間復(fù)雜度為O(m+n)。2.2順序表55/133

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

設(shè)計一個盡可能高效的算法求這m+n個元素中第k小的元素。如果參數(shù)k錯誤，算法返回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ù)錯誤返回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ù)錯誤返回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單鏈表的定義

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

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

structnode*next;

//指針域}SLinkNode;

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

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

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

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

L->next=NULL;}2.3單鏈表和循環(huán)單鏈表66/133（2）銷毀線性表運算算法一個單鏈表中的所有結(jié)點空間都是通過malloc函數(shù)分配的，在不再需要時需通過free函數(shù)釋放所有結(jié)點的空間。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）求線性表的長度運算算法設(shè)置一個整型變量i作為計數(shù)器，i初值為0，p初始時指向第一個數(shù)據(jù)結(jié)點。然后沿next域逐個往后查找，每移動一次，i值增1。當(dāng)p所指結(jié)點為空時，結(jié)束這個過程，i之值即為表長。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個元素運算算法用p從頭開始遍歷單鏈表L中的結(jié)點，用計數(shù)器j累計遍歷過的結(jié)點，其初值為0。在遍歷時j等于i時，若p不為空，則p所指結(jié)點即為要找的結(jié)點，查找成功，算法返回1。否則算法返回0表示未找到這樣的結(jié)點。2.3單鏈表和循環(huán)單鏈表70/133intGetElem(SLinkNode*L,inti,ElemType&e){intj=0;

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

if(i<=0)return0; //參數(shù)i錯誤返回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）按值查找運算算法在單鏈表L中從第一個數(shù)據(jù)結(jié)點開始查找第一個值域與e相等的結(jié)點，若存在這樣的結(jié)點，則返回其邏輯序號；否則返回0。2.3單鏈表和循環(huán)單鏈表72/133intLocate(SLinkNode*L,ElemTypee) {SLinkNode*p=L->next;

intj=1; //p指向第一個數(shù)據(jù)結(jié)點，j置為其序號1

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

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

}

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

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

注意：插入操作的①和②執(zhí)行順序不能顛倒。①結(jié)點s的next域指向p的下一個結(jié)點（s->next=p->next）。②將結(jié)點p的next域改為指向新結(jié)點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錯誤返回0

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

//查找第i-1個結(jié)點p

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

}

if(p==NULL)return0;

//未找到第i-1個結(jié)點時返回0

else

//找到第i-1個結(jié)點p

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

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

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

p->next=s; return1; //插入運算成功,返回1

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

刪除操作：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錯誤返回0

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

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

}

if(p==NULL)return0;

//未找到第i-1個結(jié)點時返回0

else

//找到第i-1個結(jié)點p

{ q=p->next;

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

if(q==NULL)return0;//沒有第i個結(jié)點時返回0 else

{p->next=q->next;

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

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

return1; }

}}2.3單鏈表和循環(huán)單鏈表79/133（8）輸出線性表運算算法從第一個數(shù)據(jù)結(jié)點開始，沿next域逐個往下遍歷，輸出每個遍歷到結(jié)點的data域，直到尾結(jié)點為止。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)用基本運算算法來創(chuàng)建單鏈表，其過程是先初始化一個單鏈表，然后向其中一個一個地插入元素。這里介紹是快速創(chuàng)建整個單鏈表的算法，也稱為整體建表。假設(shè)給定一個含有n個元素的數(shù)組a，由它來創(chuàng)建單鏈表，這種建立單鏈表的常用方法有兩種。2.整體創(chuàng)建單鏈表的算法2.3單鏈表和循環(huán)單鏈表81/133（1）頭插法建表從一個空單鏈表（含有一個L指向的頭結(jié)點）開始。讀取數(shù)組a（含有n個元素）中的一個元素，生成一個新結(jié)點s，將讀取的數(shù)據(jù)元素存放到新結(jié)點的數(shù)據(jù)域中。將新結(jié)點s插入到當(dāng)前鏈表的表頭上。再讀取數(shù)組a的下一個元素，采用相同的操作建立新結(jié)點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é)點L->next=NULL; //頭結(jié)點的next域置空，表示一個空單鏈表

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

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

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

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

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

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

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

tc=s;

}

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

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

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

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

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

p=p->next; //p沿next域下移一個結(jié)點

}

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

【例2.13】設(shè)計一個算法，刪除一個單鏈表L（至少含兩個數(shù)據(jù)結(jié)點）中第一個元素值最大的結(jié)點。在單鏈表中刪除一個結(jié)點先要找到它的前驅(qū)結(jié)點。以p遍歷單鏈表，pre指向p結(jié)點的前驅(qū)結(jié)點。在遍歷時用maxp指向data域值最大的結(jié)點，maxpre指向maxp結(jié)點的前驅(qū)結(jié)點。當(dāng)單鏈表遍歷完畢，通過maxpre結(jié)點刪除其后的結(jié)點，即刪除了元素值最大的結(jié)點。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é)點

p=p->next;

}

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

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

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

L->next=NULL;

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

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

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

L->next=p; p=q;

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

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

要求hc單鏈表仍使用原來兩個鏈表的存儲空間，不另外占用其他的存儲空間，ha和hb兩個表中允許有重復(fù)的數(shù)據(jù)結(jié)點。2.3單鏈表和循環(huán)單鏈表97/133本例合并后ha、hb兩個單鏈表都不存在了。用二路歸并的思路。用pa遍歷ha的數(shù)據(jù)結(jié)點，pb遍歷hb的數(shù)據(jù)結(jié)點。將ha頭結(jié)點用作新單鏈表hc的頭結(jié)點，讓tc始終指向hc的尾結(jié)點（初始時指向hc）。當(dāng)pa和pb均不為空時循環(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é)點用作hc的頭結(jié)點

free(hb);

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

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é)點時

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

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

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

intscore; //成績域

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

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

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

scanf("%d",&n);

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

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

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

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

tc=s;

}

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

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

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

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

pre=L;

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

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

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

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

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

CreateStudent(st);

printf("(2)按成績遞減排序\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個學(xué)生姓名和成績:Mary75↙

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

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

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

姓名成績

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

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

L->next=L;}循環(huán)單鏈表的基本運算算法設(shè)計。2.3單鏈表和循環(huán)單鏈表112/133（2）銷毀線性表運算算法一個循環(huán)單鏈表中的所有結(jié)點空間都是通過malloc函數(shù)分配的，在不再需要時需通過free函數(shù)釋放所有結(jié)點的空間。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）求線性表的長度運算算法設(shè)置一個整型變量i作為計數(shù)器，i初值為0，p初始時指向第一個結(jié)點。然后沿next域逐個往下移動，每移動一次，i值增1。當(dāng)p所指結(jié)點為頭結(jié)點時這一過程結(jié)束，i之值即為表長。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個元素運算算法用p從頭開始遍歷循環(huán)單鏈表L中的結(jié)點（初值指向第一個數(shù)據(jù)結(jié)點），用計數(shù)器j累計遍歷過的結(jié)點，其初值為1。當(dāng)p不為L且j<i時循環(huán)，p后移一個結(jié)點，j增1。當(dāng)循環(huán)結(jié)束時，若p指向頭結(jié)點則表示查找失敗返回0，否則p所指結(jié)點即為要找的結(jié)點，查找成功，算法返回1。2.3單鏈表和循環(huán)單鏈表115/133intGetElem(SLinkNode*L,inti,ElemType&e){intj=1;

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

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

while(p!=L&&j<i) //找第i個結(jié)點p

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

}

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

else

{ e=p->data; return1;

//找到后返回1

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

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

inti=1;

SLinkNod