第2章線性表2.1線性表的基本概念2.2順序表2.3單鏈表和循環單鏈表2.4雙鏈表和循環雙鏈表2.5線性表的應用第2章線性表1/1332.1線性表的基本概念2.1.1線性表的定義線性表是由n（n≥0）個相同類型的數據元素組成的有限序列。當n=0時為空表，記為()或Φ.當n>0時，線性表的邏輯表示為（al,a2,…,ai,…,an），也可以用下圖所示的邏輯結構圖表示。2.1線性表的基本概念a1a2aian……2/133a1a2aian……開始元素尾元素邏輯序號或位置為i邏輯特征：若至少含有一個元素，則只有唯一的開始元素和終端元素除了起始元素外其他元素有且僅有一個前驅元素除了終端結點外其他元素有且僅有一個后繼元素2.1線性表的基本概念3/133線性表中的每個元素有唯一的序號（邏輯序號），同一個線性表中可以存在值相同的多個元素，但它們的序號是不同的。如一個整數線性表：（1，3，2，4，2，1，5）序號為1序號為62.1線性表的基本概念4/1332.1.2線性表的基本運算初始化InitList(L)。其作用是建立一個空表L（即建立線性表的構架，但不含任何數據元素）。銷毀線性表DestroyList(L)。其作用是釋放線性表L的內存空間。求線性表的長度GetLength(L)。其作用是返回線性表L的長度。求線性表中第i個元素GetElem(L,i,e)。其作用是返回線性表L的第i個數據元素。通常線性表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線性表抽象數據類型List=線性表中元素的邏輯結構+基本運算定義2.1線性表的基本概念7/133

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

解：算法思路：依次檢查線性表B中的每個元素x，看它是否在線性表A中。若x在線性表A中，則將其從A中刪除。2.1線性表的基本概念8/133voidDelete(List&A,ListB) //A為引用型參數{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的基本運算，設計一個由線性表A和B中的公共元素產生線性表C的算法。

算法思路：先初始化線性表C，然后依次檢查線性表A中的每個元素x，看它是否在線性表B中；若x在線性表B中，則將其插入到線性表C中。2.1線性表的基本概念10/133voidCommelem(ListA,ListB,List&C) //C為引用型參數{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順序表的定義順序表是線性表采用順序存儲結構在計算機內存中的存儲方式，它由多個連續的存儲單元構成，每個存儲單元存放線性表的一個元素。順序表邏輯上相鄰的數據元素在內存的存儲結構中也是相鄰的，不需要額外的內存空間來存放元素之間的邏輯關系。2.2順序表12/133假定線性表的數據元素的類型為ElemType，在C/C++語言中，順序表類型聲明如下：#defineMaxSize100typedefintElemType;

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

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

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

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

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

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

這里順序表L的內存空間是由系統自動分配的，在不再需要時由系統自動釋放其空間。所以對應的函數不含任何語句。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個元素）。當i無效時返回0（表示插入失敗）。有效時將L.data[i-1..L.length-1]后移一個位置，在L.data[i-1]處插入x，順序表長度增1，并返回1（表示插入成功。2.2順序表20/133元素a1…an…下標0…

i-1

…

n-1均后移一個位置ai…元素a1…an…下標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; //無效的參數ifor(j=L.length;j>=i;j--)//將位置為i的結點及之后的結點后移L.data[j]=L.data[j-1];L.data[i-1]=x; //在位置i處放入x

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

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

刪除順序表L中邏輯序號為i的元素。在i無效時返回0（表示刪除失敗）。有效時將L.data[i..length-1]前移一個位置，順序表長度減1，并返回1（表示刪除成功。2.2順序表26/133均前移一個位置元素a1…an…下標0…

i-1i

…

n-1ai+1…ai元素a1…an…下標0…

i-1…

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

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

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

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

return1;}2.2順序表28/133算法分析當i=n時（刪除尾元素），移動次數為0，呈現最好的情況。當i=1時（刪除第一個元素），移動次數為n-1，呈現最壞的情況。2.2順序表29/133平均情況分析a1a2aian……n種刪除情況刪除位置i的元素ai，需要將ai+1～an的元素均前移一次，移動次數為n-(i+1)+1=n-i。假設在等概率下pi（pi=1/n），移動元素的平均次數為：2.2順序表30/133刪除算法的主要時間花費在元素移動上，所以算法DelElem()的平均時間復雜度為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將順序表類型聲明及其基本運算函數存放在SqList.cpp文件中#include"SqList.cpp" //包括前面的順序表基本運算函數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.整體創建順序表的算法假設給定一個含有n個元素的數組a，由它來創建順序表。voidCreateList(SqList&L,ElemTypea[],intn){inti,k=0; //k累計順序表L中的元素個數for(i=0;i<n;i++){L.data[k]=a[i]; //向L中添加一個元素k++; //L中元素個數增1}L.length=k; //設置L的長度}2.2順序表35/1332.2.3順序表的算法設計示例1.基于順序表基本操作的算法設計這類算法設計中包括順序表元素的查找、插入和刪除等。2.2順序表36/133

【例2.3】假設有一個順序表L，其中元素為整數且所有元素值均不相同。設計一個算法將最大值元素與最小值元素交換。用maxi和mini記錄順序表L中最大值元素和最小值元素的下標，初始時maxi=mini=0。i從1開始掃描所有元素：當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】設計一個算法，從線性表中刪除自第i個元素開始的k個元素，其中線性表用順序表L存儲。將線性表中ai～ai+k-1元素（對應L.data[i-1..i+k-2]的元素）刪除，即將ai+k～an（對應L.data[i+k-1..n-1]）的所有元素依次前移k個位置。2.2順序表39/133均前移k個位置元素a1…an下標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存儲，且每個元素都是互不相等的整數。設計一個將所有奇數移到所有的偶數前邊的算法（要求時間最少，輔助空間最少）。

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

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

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

if(i<j)

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

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

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

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

【例2.7】

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

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

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

A：135

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

//k記錄順序表C中的元素個數

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中剩余的元素復制到C中

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

}

while(j<B.length)

//將B中剩余的元素復制到C中

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

j++;k++;

}

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

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

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

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的實際長度}本算法的空間復雜度為O(1)，時間復雜度為O(m+n)。2.2順序表55/133

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

設計一個盡可能高效的算法求這m+n個元素中第k小的元素。如果參數k錯誤，算法返回0；否則算法返回1，并且用參數e表示求出的第k小的元素。2.2順序表56/133intTopk1(SqListA,SqListB,intk,ElemType&e){inti=0,j=0;if(k<1||k>A.length+B.length)return0; //參數錯誤返回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改進#defineINF32767intTopk2(SqListA,SqListB,intk,ElemType&e){inti=0,j=0;if(k<1||k>A.length+B.length)return0; //參數錯誤返回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單鏈表和循環單鏈表2.3.1單鏈表的定義

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

//數據域

structnode*next;

//指針域}SLinkNode;

//單鏈表結點類型2.3單鏈表和循環單鏈表63/133

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

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

//創建頭結點L

L->next=NULL;}2.3單鏈表和循環單鏈表66/133（2）銷毀線性表運算算法一個單鏈表中的所有結點空間都是通過malloc函數分配的，在不再需要時需通過free函數釋放所有結點的空間。a1a2an∧…Lprep2.3單鏈表和循環單鏈表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單鏈表和循環單鏈表68/133（3）求線性表的長度運算算法設置一個整型變量i作為計數器，i初值為0，p初始時指向第一個數據結點。然后沿next域逐個往后查找，每移動一次，i值增1。當p所指結點為空時，結束這個過程，i之值即為表長。intGetLength(SLinkNode*L){

inti=0;

SLinkNode*p=L->next;

while(p!=NULL)

{i++;

p=p->next;

}

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

SLinkNode*p=L; //p指向頭結點，計數器j置為0

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

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

{j++;

p=p->next;

}

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

else

{e=p->data;

return1; //找到后返回1

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

intj=1; //p指向第一個數據結點，j置為其序號1

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

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

}

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

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

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

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

//參數i錯誤返回0

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

//查找第i-1個結點p

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

}

if(p==NULL)return0;

//未找到第i-1個結點時返回0

else

//找到第i-1個結點p

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

//創建存放元素x的新結點s s->next=p->next;

//將s結點插入到p結點之后

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

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

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

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

//參數i錯誤返回0

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

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

}

if(p==NULL)return0;

//未找到第i-1個結點時返回0

else

//找到第i-1個結點p

{ q=p->next;

//q指向被刪結點

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

{p->next=q->next;

//從單鏈表中刪除q結點

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

return1; }

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

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

}

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

L=(SLinkNode*)malloc(sizeof(SLinkNode));//創建頭結點L->next=NULL; //頭結點的next域置空，表示一個空單鏈表

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

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

L->next=s;

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

L=(SLinkNode*)malloc(sizeof(SLinkNode));//創建頭結點

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

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

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

tc=s;

}

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

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

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

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

maxp=p; //當p指向更大的結點時，將其賦給maxp

p=p->next; //p沿next域下移一個結點

}

returnmaxp;}2.3單鏈表和循環單鏈表90/133

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

p=p->next;

}

maxpre->next=maxp->next; //刪除maxp結點

free(maxp); //釋放maxp結點}2.3單鏈表和循環單鏈表92/1332.基于整體建表的算法設計這類算法設計中需要根據條件產生新的結果單鏈表。而創建結果單鏈表的方法有頭插法和尾插法。2.3單鏈表和循環單鏈表93/133

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

L->next=NULL;

while(p!=NULL) //遍歷所有數據結點

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

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

L->next=p; p=q;

}}2.3單鏈表和循環單鏈表95/1333.有序單鏈表的二路歸并算法有序單鏈表是有序表的單鏈表存儲結構，同樣可以利用有序表元素的有序性提高相關算法的效率。當數據采用單鏈表存儲時，對應的二路歸并就是單鏈表二路歸并算法。2.3單鏈表和循環單鏈表96/133

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

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

hc=ha;tc=hc;

//將ha的頭結點用作hc的頭結點

free(hb);

//釋放hb的頭結點

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單鏈表還有結點時

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

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

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

intscore; //成績域

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

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

//創建頭結點

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

printf("學生人數:");

scanf("%d",&n);

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

{ s=(StudList*)malloc(sizeof(StudList));//創建新結點

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

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

tc=s;

}

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

while(p!=NULL)

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

}

free(pre);}2.3單鏈表和循環單鏈表105/133輸出學生單鏈表的算法如下：voidDispList(StudList*L) //輸出學生單鏈表{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單鏈表和循環單鏈表106/133學生單鏈表按成績遞減排序的算法設計：LMary∧∧75John90Smith85Harry95p斷開成兩個部分將p結點有序插入到L中：在L中從前向后查找第一個score小于等于p->score的結點的前驅結點pre。將p結點插入在pre結點之后。直到p=NULL。2.3單鏈表和循環單鏈表107/133學生單鏈表按成績遞減排序的算法如下：voidSortList(StudList*&L) //將學生單鏈表按成績遞減排序{StudList*p,*pre,*q;

p=L->next->next; //p指向L的第2個數據結點

L->next->next=NULL; //構造只含一個數據結點的有序表while(p!=NULL)

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

pre=L;

//從有序表開頭進行比較,pre指向插入p的前驅結點

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

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

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

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

CreateStudent(st);

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

SortList(st);

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

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

第1個學生姓名和成績:Mary75↙

第2個學生姓名和成績:John90↙

第3個學生姓名和成績:Smith85↙

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

姓名成績

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

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

L->next=L;}循環單鏈表的基本運算算法設計。2.3單鏈表和循環單鏈表112/133（2）銷毀線性表運算算法一個循環單鏈表中的所有結點空間都是通過malloc函數分配的，在不再需要時需通過free函數釋放所有結點的空間。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單鏈表和循環單鏈表113/133（3）求線性表的長度運算算法設置一個整型變量i作為計數器，i初值為0，p初始時指向第一個結點。然后沿next域逐個往下移動，每移動一次，i值增1。當p所指結點為頭結點時這一過程結束，i之值即為表長。intGetLength(SLinkNode*L){inti=0;

SLinkNode*p=L->next;

while(p!=L)

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

}

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

SLinkNode*p=L->next; //p指向首結點，計數器j置為1

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

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

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

}

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

else

{ e=p->data; return1;

//找到后返回1

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

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

inti=1;

SLinkNod