數(shù)據(jù)結(jié)構(gòu)期末復(fù)習提要

數(shù)據(jù)結(jié)構(gòu)期末復(fù)習提要

中央電大理工部計算機教研室

數(shù)據(jù)結(jié)構(gòu)是中央電大計算機應(yīng)用專業(yè)?門統(tǒng)設(shè)必修課和專業(yè)基礎(chǔ)課，它主

要研究數(shù)據(jù)的各種邏輯結(jié)構(gòu)，在計算機中的存儲結(jié)構(gòu)，對數(shù)據(jù)進行的插入、查

找、刪除、排序、遍歷等運算，這些運算在存儲結(jié)構(gòu)上具體實現(xiàn)的算法。學習

好該課程將為學好整個計算機專業(yè)打下堅實的基礎(chǔ)。

第一部分各章復(fù)習要求

下面按照主教材中各章次序給出每章的具體復(fù)習要求，以便指導(dǎo)同學們更

好地進行期末復(fù)習。

第一章緒論

重點掌握的內(nèi)容：

1.數(shù)據(jù)結(jié)構(gòu)的二元組表示，對應(yīng)的圖形表示，序偶利邊之間的對應(yīng)關(guān)系。

2.集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹結(jié)構(gòu)和圖結(jié)構(gòu)的特點。

3.抽象數(shù)據(jù)類型的定義和表示方法。

4.一維和二維數(shù)組中元素的按下標和按地址的訪問方式以及相互轉(zhuǎn)換，元

素地址和數(shù)組地址的計算，元素占用存儲空間大小和數(shù)組占用存儲空間大小的

計算。

5.普通函數(shù)重裁和操作符函數(shù)重載的含義，定義格式和調(diào)用格式。

6.函數(shù)定義中值參數(shù)和引用參數(shù)的說明格式及作用，函數(shù)被調(diào)用執(zhí)行時對

傳送來的實際參數(shù)的影響。

7.算法的時間復(fù)雜度和空間復(fù)雜度的概念，計算方法，數(shù)量級表示。

8.一個簡單算法的最好、最差和平均這三種情況的時間復(fù)雜度的計算。

對于本章的其余內(nèi)容均作一般掌握。

第二章線性表

重點掌握的內(nèi)容：

1.線性表的定義和抽象數(shù)據(jù)類型的描述，線性表中每一種操作的功能，對

應(yīng)的函數(shù)名、返回值類型和參數(shù)表中每個參數(shù)的作用。

2.線性表的順序存儲結(jié)構(gòu)的類型定義，即List類型的定義和每個域的定

義及作用。

3.線性表的每一種運算在順序存儲結(jié)構(gòu)上實現(xiàn)的算法，及相應(yīng)的時間復(fù)雜

度。

4.鏈接存儲的概念，線性表的單鏈接和雙鏈接存儲的結(jié)構(gòu)，向單鏈表中一

個結(jié)點之后插入新結(jié)點或從單鏈表中刪除一個結(jié)點的后繼結(jié)點的指針鏈接過

程。

5.單鏈表中結(jié)點的結(jié)構(gòu)，每個域的定義及作用，即LNodc類型的定義及結(jié)

構(gòu)。

6.帶表頭附加結(jié)點的鏈表、循環(huán)鏈表、雙向鏈表的結(jié)構(gòu)特點。

7.線性表的每一種運算在單鏈表上實現(xiàn)的算法及相應(yīng)的時間復(fù)雜度。

8.在順序存儲或鏈接存儲的線性表上實現(xiàn)指定功能的算法的分析和設(shè)計。

對于本章的其余內(nèi)容均作一般掌握。

第三章稀疏矩陣和廣義表

重點掌握的內(nèi)容：

1.稀疏矩陣的定義和三元組線性表表示。

2.稀疏矩陣的順序存儲、帶行指針向量的鏈接存儲、卜字鏈接存儲的類型

定義，在每一種存儲中非零元素結(jié)點的結(jié)構(gòu)。

3.廣義表的定義和表示，廣義表長度和深度的計算。

4.廣義表的鏈接存儲結(jié)構(gòu)中結(jié)點類型的定義，分別求廣義表長度和深度的

遞歸算法，它們對應(yīng)的時間復(fù)雜度。

一般掌握的內(nèi)容：

L稀疏矩陣的轉(zhuǎn)置運算和算法描述。

2.兩個稀疏矩陣的做加法的過程和算法描述。

對于本章的其余內(nèi)容均作一般了解。

第四章棧和隊列

重點掌握的內(nèi)容：

1.棧的定義和抽象數(shù)據(jù)類型的描述，棧中每?種操作的功能，對應(yīng)的函數(shù)

名、返回值類型和參數(shù)表中每個參數(shù)的作用。

2.棧的順序存儲結(jié)構(gòu)的類型定義，即Stack類型的定義和每個域的定義及

作用。

3.棧的每一種運算在順序存儲結(jié)構(gòu).上實現(xiàn)的算法，及相應(yīng)的時間復(fù)雜度。

4.棧的每一種運算在鏈接存儲結(jié)構(gòu)上實現(xiàn)的算法及相應(yīng)的時間復(fù)雜度。

5.算術(shù)表達式的中綴表示和后綴表示，以及相互轉(zhuǎn)換的規(guī)則，后綴表達式

求值的方法。

6.隊列的定義和抽象數(shù)據(jù)類型的描述，隊列中每一種操作的功能，對應(yīng)的

函數(shù)名、返回值類型和參數(shù)表中每個參數(shù)的作用。

7.隊列的順序存儲結(jié)構(gòu)的類型定義，即Queue類型的定義和每個域的定義

及作用。

8.隊列的每一種運算在順序存儲結(jié)構(gòu)上實現(xiàn)的算法及相應(yīng)的時間復(fù)雜度。

9.利用棧和隊列解決簡單問題的算法分析和設(shè)計。

一般掌握的內(nèi)容：

1.后綴表達式求值的算法，把中綴表達式轉(zhuǎn)換為后綴表達式的算法。

2.求解階乘問題和迷宮問題的方法和算法。

3.隊列的鏈接存儲結(jié)構(gòu)，以及實現(xiàn)每一種隊列運算的算法和相應(yīng)的時間復(fù)

雜度。

第五章樹和二叉樹

重點掌握的內(nèi)容：

1.樹和二叉樹的定義，對于一棵具體樹和二叉樹的二元組表示及廣義表表

2.樹和二叉樹的概念，如結(jié)點的度、樹的度、樹的層數(shù)、樹的深度等。

3.樹和二叉樹的性質(zhì)，如己知樹或二叉樹的深度h可求出相應(yīng)的最多結(jié)點

數(shù)，已知結(jié)點數(shù)n可求出對應(yīng)樹或二叉樹的最大和最小高度。

4.二叉樹中結(jié)點的編號規(guī)則和對應(yīng)的順序存儲結(jié)構(gòu)。

5.二叉樹的鏈接存儲結(jié)構(gòu)及存儲結(jié)點的類型定義，即BTreeNode類型的定

義和每個域的定義及作用。

6.二叉樹的先序、中序、后序遍歷的遞歸過程和遞歸算法，中序遍歷的非

遞歸算法，按層遍歷的過程和算法，每種算法的時間復(fù)雜度。

7.普通樹的鏈接存儲結(jié)構(gòu),GTreeNode類型的定義和每個域的定義及作用。

8.普通樹的先根、后根和按層遍歷的過程及算法。

9.在鏈接存儲的二叉樹上實現(xiàn)指定功能的算法分析和設(shè)計。

對于本章的其余內(nèi)容均作一般掌握。

第六章二叉樹的應(yīng)用

重點掌握的內(nèi)容：

1.二叉搜索樹的定義和性質(zhì)。

2.二叉搜索樹查找的遞歸算法和非遞歸算法，相應(yīng)的時間復(fù)雜度，查找一

個元素的查找長度，即從樹根結(jié)點到該結(jié)點的路徑上的結(jié)點數(shù)。

3.二叉搜索樹插入的遞歸算法和非遞歸算法，相應(yīng)的時間復(fù)雜度，根據(jù)-

組數(shù)據(jù)生成一棵二叉搜索樹的過程。

4.堆的定義和順序存儲結(jié)構(gòu)，小根堆和大根堆的異同。

5.向堆中插入元素的過程、算法描述及時間復(fù)雜度。

6.從堆中刪除元素的過程、算法描述及時間復(fù)雜度。

7.哈夫曼樹的定義，樹的帶權(quán)路徑長度的計算，根據(jù)若干個葉子結(jié)點的權(quán)

構(gòu)造哈夫曼樹的過程。

對本章的其余內(nèi)容均作一般了解。

第七章圖

重點掌握的內(nèi)容：

1.圖的頂點集和邊集的表示。

2.圖的一些概念的含義，如頂點、邊、度、完全圖、子圖、路徑、路徑長

度、連通圖、權(quán)、網(wǎng)等。

3.圖的鄰接矩陣、鄰接表和邊集數(shù)組三種存儲結(jié)構(gòu)及相應(yīng)的空間復(fù)雜度。

4.存儲圖使用的vexlist,adjmatrix,adjlist,edgenode,edgeset,

edge等類型的定義及用途。

5.圖的深度優(yōu)先和廣度優(yōu)先搜索遍歷的過程。

6.對分別用鄰接矩陣和用鄰接表表示的圖進行深度優(yōu)先搜索遍歷的過程、

算法描述以及相應(yīng)的時間復(fù)雜度。

7.對分別用鄰接矩陣和用鄰接表表示的圖進行廣度優(yōu)先搜索遍歷的過程、

算法描述以及相應(yīng)的時間復(fù)雜度。

8.圖的生成樹、生成樹的權(quán)、最小生成樹等的定義。

9.根據(jù)普里姆算法求圖的最小生成樹的過程和算法描述。

10.根據(jù)克魯斯卡爾算法求圖的最小生成樹的過程和算法描述。

11.圖的拓撲序列和拓撲排序的概念，求圖的拓撲序列的方法，對用鄰接

表表示的圖進行拓撲排序的過程和算法。

對本章的其余內(nèi)容均作一般掌握。它包括建立圖的鄰接矩陣、鄰接表、邊

集數(shù)組算法，建立圖的逆鄰接表和卜字鄰接表等內(nèi)容。

第八章查找

重點掌握的內(nèi)容：

1.在一維數(shù)組上進行順序查找的過程、算法、平均查找長度和時間復(fù)雜度。

2.在一維數(shù)組上進行二分查找的過程、遞歸和非遞歸算法、平均查找長度

和時間復(fù)雜度，二分查找一個給定值元素的查找長度（即查找路徑上的元素數(shù)）,

二分查找對應(yīng)的判定樹的性質(zhì)。

3.索引存儲的概念，索引表的存儲結(jié)構(gòu)和索引項的存儲結(jié)構(gòu)，索引查找一

個元素的過程、平均查找長度和時間復(fù)雜度。

4.散列存儲的概念，散列函數(shù)、散列表、沖突、同義詞、裝填因子等術(shù)語

的含義。

5.利用除留余數(shù)法建立散列函數(shù)求元素散列地址的方法。

6.利用開放定址法中的線性探查法處理沖突進行散列存儲和查找的過程,

利用鏈接法處理沖突進行散列存儲和查找的過程。

7.根據(jù)除留余數(shù)法構(gòu)造散列函數(shù)，采用線性探查法或鏈接法處理沖突，把

一組數(shù)據(jù)散列存儲到散列表中，計算出?個給定值元素的查找長度和查找所有

元素的平均查找長度。

8.B—樹中每個結(jié)點的結(jié)構(gòu)，樹根結(jié)點或非樹根結(jié)點中關(guān)鍵字的個數(shù)范圍和

子樹的個數(shù)范圍，B-的結(jié)構(gòu)特性，從B_樹上查找一個給定值元素的過程。

一般掌握的內(nèi)容：

1.索引查找和分塊查找算法。

2.B樹查找算法。

3.向B樹中插入元素的過程。

對本章的其余內(nèi)容均作一般了解。

第九章排序

重點掌握的內(nèi)容：

1.直接插入、直接選擇和冒泡排序的方法，排序過程及時間復(fù)雜度。

2.在堆排序中建立初始堆的過程和利用堆排序的過程，對一個分支結(jié)點進

行篩運算的過程、算法及時間復(fù)雜度，整個堆排序的算法描述及時間復(fù)雜度。

3.快速排序的方法，對一組數(shù)據(jù)的排序過程，對應(yīng)的二叉搜索樹，快速排

序過程中劃分的層數(shù)和遞歸排序區(qū)間的個數(shù)。

4.快速排序的遞歸算法，它在平均情況下的時間和空間復(fù)雜度，在最壞情

況F的時間和空間復(fù)雜度。

5.二路歸并排序的方法和對數(shù)據(jù)的排序過程，每趟排序前、后的有序表長

度，二路歸并排序的趟數(shù)、時間復(fù)雜度和空間復(fù)雜度。

一般掌握的內(nèi)容：

1.每一種排序方法的穩(wěn)定性。

2.直接插入排序和直接選擇排序的算法。

一般了解的內(nèi)容：

1.二路歸并排序過程中涉及的每個算法。

2.冒泡排序算法。

第二部分期末復(fù)習題示例

一、單選題(每小題2分，共8分)

1.在個單鏈表HL中，若要向表頭插入一個由指針p指向的結(jié)點，則執(zhí)

行。

AHL=p;p->next=HL;Bp->next=HL;HL=p;

Cp->next=HL;p=HL;Dp->next=HL->next;HL->next=p;

2.在一個順序隊列中，隊首指針指向隊首元素的位置。

A前一個B后一個C當前

3.從二叉搜索樹中查找一個元素時，其時間復(fù)雜度大致為o

2

A0(n)B0(1)CO(log2n)D0(n)

4.由權(quán)值分別為3,8,6,2,5的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑

長度為。

A24B48C72D53

二、填空題(每空1分，共32分)

1.一個算法的時間復(fù)雜度為(3//+2〃log2加4k7)/(5〃)，其數(shù)量級表示為

O

2.在以HL為表頭指針的帶表頭附加結(jié)點的單鏈表和循環(huán)單鏈表中，鏈衣

為空的條件分別為一一和。

3.?個廣義表中的元素分為―—元素和―—元素兩類。

4.從一個鏈棧中刪除一個結(jié)點時，需要把棧頂結(jié)點的域的值賦

________________o

5.在進行函數(shù)調(diào)用時，需要把每個實參的值和調(diào)用后的傳送給被

調(diào)用的函數(shù)中。

6.對于一棵具有n個結(jié)點的二叉樹，若一個結(jié)點的編號為i(l<iWn),

則它的左孩子結(jié)點的編號為，右孩子結(jié)點的編號為，雙親結(jié)

點的編號為o

7.在一棵高度為5的理想平衡樹中，最少含有___個結(jié)點，最多含有

個結(jié)點。

8.在一個堆的順序存儲中，若一個元素的下標為i(OWiWn-l),則它的

左孩子元素的下標為,右孩子元素的下標為o

9.在一個具有n個頂點的無向完全圖中，包含有條邊，在一個具

有n個頂點的有向完全圖中，包含有條邊。

10.對于一個具有n個頂點和e條邊的有向圖和無向圖，若采用邊集數(shù)組

表示，則存于數(shù)組中的邊數(shù)分別為一和條。

11.以二分查找方法從長度為12的有序表中查找一個元素時，平均查找長

度為。

12.假定一個線性表為(12,23,74,55,63,40,82,36),若按Key%3條件進

行劃分，使得同一余數(shù)的元素成為一個子表，則得到的三個子表分別為

、和。

13.在線性表的散列存儲中，裝填因子a又稱為裝填系數(shù)，若用m表示散

列表的長度，n表示待散列存儲的元素的個數(shù)，貝皈等于。

14.在一棵m階也樹上，每個非樹根結(jié)點的關(guān)鍵字數(shù)目最少為一個,

最多為個，其子樹數(shù)目最少為，最多為。

15.在堆排序的過程中，對任一分支結(jié)點進行篩運算的時間復(fù)雜度為

整個堆排序過程的時間復(fù)雜度為。

16.快速排序在平均情況下的時間復(fù)雜度為，在最壞情況下的時

間復(fù)雜度為。

三、運算題(每小題6分，共24分)

1.假定一棵二叉樹廣義表表示為a(b(c),d(e,f)),分別寫出對它進行先

序、中序、后序、按層遍歷的結(jié)果。

先序：

中序：

后序：

按層：

2.已知一個圖的頂點集V和邊集G分別為：

V={0,1,2,3,4,5,6,7);

E={(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3,6)10,

(4,6)4,(5,7)20};

按照普里姆算法從頂點0出發(fā)得到最小生成樹，試寫出在最小生成樹中依

次得到的各條邊。

3.已知一個圖的頂點集V和邊集G分別為：

V={0,1,2,3,4,5,6,7,8);

E={<0,2>,<1,3>,<1,4>,<2,4>,<2,5>,<3,6>,<3,7>,<4,7>,<4,8>,

<5,7>,<6,7>,<7,8>};

若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結(jié)點都是按照終點序號

從小到大的次序鏈接的，則按主教材中介紹的進行拓撲排序的算法，寫出得到

的拓撲序列(提示：先畫出對應(yīng)的圖形，然后再運算)。

拓撲序列：

4.假定一組記錄的排序碼為(46,79,56,38,40,80,25,34),則對其進行快

速排序的第一次劃分的結(jié)果為o

四、閱讀算法，回答問題(每小題8分，共16分)

1.voidAE(StackftS)

(

InitStack(S);

Push(S,30);

Push(S,40):

Push(S,50);

intx=Pop(S)+2*Pop(S);

Push(S,x);

inti,a[4]={5,8,12,15);

for(i=0;i<4;i++)Push⑸a[i]);

while(JStackEmpty(S))cout<<Pop(S)<<，

該算法被調(diào)用后得到的輸出結(jié)果為：

2.voidAJ(adjlistGL,inti,intn)

(

QueueQ;

InitQueue(Q);

cout?i?，';

visited[i]=true;

QInsert(Q,i);

while(!QueueEmpty(Q)){

intk=QDelete(Q);

edgenode*p=GL[k];

while(p!=NULL)

(

intj=p->adjvex;

if(!visited[j]){

cout?j?,J;

visited[j]=true;

QInsert(Q,j);

}

p=p->next;

)

)

)

該算法的功能為：

五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容(10分)。

向以BST為樹根指針的二叉搜索樹上插入值為item的結(jié)點的遞歸算法。

voidInsert(BTreeNode*&BST,constElemTypeftitem)

if(BST二二NULL)

{BTreeNode*p=newBTreeNode;

p->data=item;

BST=p;

)

elseif(item<BST->data);

else;

)

六、編寫算法(10分)

編寫向類型為List的線性表L中第i個元素位置插入一個元素的算法，假

定不需要對i的值進行有效性檢查，同時不需要檢查存儲空間是否用完。

voidInsert(List&L,inti,ElemTypex)

第三部分期末復(fù)習題示例解答及評分標準

一、單選題(每小題2分，共8分)

評分標準：選對者得2分，否則不得分。

1.B2.A3.C4.D

二、填空題(每空1分，共32分)

評分標準：每空得2分，否則不得分。

1.O(n)

2.HL->next==NULLHL->next==HL

3.單表

4.指針棧頂指針

5.返回地址

6.2i2i+li/2(或Li/2」)

7.1631

8.2i+l2i+2

9.n(n-l)/2n(n'l)

10.ee

11.37/12

12.(12,63,36)(55,40,82)(23,74)

13.n/m

14.「m/21Tm-l「m/2~|m

15.O(log2n)O(nlog2n)

2

16.O(nlog2n)O(n)

三、運算題(每小題6分，共24分)

1.先序：a,b,c,d,e,f2分

中序：c,b,a,e,d,f2分

后序：c,b,e,f,d,a1分

按層：a,b,d,c,e,f1分

2.(0,3)2,(0,2)5,(0,1)8,(1,5)6,(3,6)10,(6,4)4,(5,7)20

3.拓撲序列：1,3,6,0,2,5,4,7,8

4.[40342538]46[805679]

評分標準：每小題若有任何錯誤則應(yīng)得分全扣。

四、閱讀算法，回答問題(每小題8分，共16分)

1/p>

評分標準：有一處錯扣4分，兩處及以上錯8分全扣。

2.從初始點火出發(fā)廣度優(yōu)先搜索由鄰接表GL所表示的圖。

評分標準：請根據(jù)敘述情況酌情給分。

五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容(10分)。

p->left=p->right=NULL

Insert(BST->left,item)

Insert(BST->right,item)

評分標準：每空對給3分，全對給10分。

六、編寫算法(10分)

評分標準：請根據(jù)編程情況酌情給分。

voidInsert(List&L,inti,ElemTypex)

(

for(intj=L.sizeT;j>=i-l;j-)

L.list[j+l]=L.;

L.list[i-l]=x;

L.size++;

}

第四部分教材第二章部分習題參考解答

一、單選題

1.B2.A3.C4.B5.D6.C

二、填空題

1.值指針

2.(38,56,25,60,42,74)

3.0(n)0(1)

4.0(1)0(n)

5.i-1i+1

6.p->nexta[p].next

7.表頭

8.前驅(qū)后繼

9.表尾表頭

10.HL->next==NULLHL->next==HL

11.a[i],next=a[l].next;a[l].next=i;

12.i=a[l],next;a[l].next=a[i],next;

13.p=a[i],next;a[i],next=a[p],next;i=p;

14.a[j].next=a[i],next;a[i],next=j;

三、普通題

第1小題

1.(79,62,34,57,26,48)

2.(26,34,48,57,62,79)

3.(48,56,57,62,79,34)

4.(56,57,79,34)

5.(26,34,39,48,57,62)

第2小題

分析：為了排版方便,假定采用以下輸出格式表示單鏈表示意圖：每個括

號內(nèi)的數(shù)據(jù)表示一個元素結(jié)點，其中第一個數(shù)據(jù)為元素值，第二個數(shù)據(jù)為后繼

結(jié)點的指針，第一個元素結(jié)點前的數(shù)值為表頭指針。

1.(7(79,6),(62,5),(34,4),(57,3),(26,2),(48,0))

2.(3(26,5),(34,2),(48,4),(57,6),(62,7),(79,0))

3.(2(48,8),(56,4),(57,6),(62,7),(79,5),(34,0))

4.(8(56,4),(57,7),(79,5),(34,0))

第3小題

1.ElemTypeDMValue(List&L)

〃從線性表中刪除具有最小值的元素并山函數(shù)返回，空出的位置

〃由最后個元素填補，若線性表為空則顯示出錯信息并退出運

行。

(

if(ListEmpty(L)){

cerr?z，ListisEmpty!z/<<endl;

exit(1);

ElemTypex;

x=L.list[0];

intk=0;

for(inti=l;i<L.size;i++){

ElemTypey=L.list[i];

if(y<x){x=y;k=i;}

)

L.list[k]=L.list[L.size-1];

L.size―;

returnx;

)

2.intDeletel(List&L,inti)

〃從線性表中刪除第i個元素并由函數(shù)返回。

(

if(i<l||i>L.size){

cerr<<，，Indexisoutrange!/z?endl;

exit(1);

)

ElemTypex;

x=L.list[i-1];

for(intj=i-l;j<L.size-1;j++)

L.list[j]=L.list[j+l];

L.size一；

returnx;

3.voidInsertl(List&L,inti,ElemTypex)

〃向線性表中第i個元素位置插入一個元素。

(

if(i<l||i>L.size+1){

cerr<<^Indexisoutrange!z/<<end1;

exit(1);

)

if(L.size二二MaxSize)

{

cerr?，，Listoverflow!〃<<endl;

exit(1);

for(intj=L.size-1;j>=i-l;j一)

L.list[j+l]=L.list[j];

L.list[i-l]=x;

L.size++;

)

4.voidDelete2(List&L,ElemTypex)

〃從線性表中刪除具有給定值x的所有元素。

(

inti=0;

while(i<L.size)

if(L.list[i]=x){

for(intj=i+l；j<L.size;j++)

L.list[j-l]=L.list[j];

L.size一；

)

else

i++；

)

5.voidDelete3(List&L,ElemTypes,ElemTypet)

〃從線性表中刪除其值在給定值s和t之間的所有元素。

(

inti=0;

while(i<L.size)

if((L.list[i]>=s)&&(L.list[i]<=t)){

for(intj=i+l;j<L.size;j++)

L.list[j-l]=L.list[j];

L.size一；

)

else

i++；

)

6.voidDelete4(List&L,ElemTypes,ElemTypet)

〃從有序表中刪除其值在給定值s和t之間的所有元素。

inti=0;

while(i<L.size)//從有序表L中查找出大于等于s的第一個元

素。

if(L.list[i]<s)i++;

elsebreak;

if(i<L.size)(

intj=l;

while((i+j<L.size)&&(L.list[i+j]<=t))

j++；〃求出s和t之間元素的個數(shù)。

for(intk=i+j;k<L,size;k++)

L.list[k-j]=L.list[k];

L.size-=j;

7.voidMerge(List&LI,ListftL2,List&L)

〃將兩個有序表合并成一個新的有序表并由變量返回。

(

if(LI.size+L2.size>MaxSize){

cerr?//Listoverflow!z/<<endl;

exit(1);

)

inti=0,j=0,k=0;

while((i<Ll.size)&&(j<L2.size)){

if(LI.list[i]<=L2.list[j])

{〃將口中的元素賦給L。

L.list[k]=Ll.list[i];

i++；

)

else{〃將L2中的元素賦給L。

L.list[k]=L2.list[j];

j++；

)

k++;

)

while(i<Ll.size){〃將LI中剩余的元素賦給L。

L.list[k]=Ll.list[i];

i++;k++;

while(j<L2.size){〃將L2中剩余的元素賦給L。

L.list[k]=L2.list[j];

j++；k++;

)

L.size=k;

)

8.voidDelete5(List&L)

〃從線性表中刪除所有其值重復(fù)的元素，使所有元素的值均不同。

|

inti=0;

while(i<L.size){

intj=i+l;

while(j<L.size)

{〃刪除重復(fù)值為LJist[i]的所有元素

if(L.list[j]=L.list[i]){

for(intk=j+l;k<Lsize;k++)

L.list[k-l]=L.list[k];

L.size一;

)

else

j++；

)

i++;

)

)

第4小題

1.voidContrary(LNode*&HL)

〃將一個單鏈表按逆序鏈接。

{

LNode*p=IIL;//p指向待逆序的第一個結(jié)點，初始指向原表頭

結(jié)點。

HL=NULL;〃也仍為逆序后的表頭指針，初始值為空。

while(p!=NULL)

{〃把原單鏈表中的結(jié)點依次進行逆序鏈接。

LNode*q=p;〃q指向待處理的結(jié)點。

p=p->next;//p指向下一個待逆序的結(jié)點。

〃將q結(jié)點插入到已逆序單鏈表的表頭。

q->next=HL;

HL=q;

2.voidDelete1(LNode*&HL,inti)

〃刪除單鏈表中的第i個結(jié)點。

(

if(i<l||HL==NULL){

cerr?，，Indexisoutrange!，，<<endl;

exit(1);

)

LNode*ap,*cp;

ap=NULL;cp=HL;〃cp指向當前結(jié)點，ap指向其前驅(qū)結(jié)點。

intj=l;

while(cp!=NULL)

if(j==i)

break;//cp結(jié)點即為第i個結(jié)點。

else(〃繼續(xù)向后尋找。

ap=cp;

cp=cp->next;

j++；

)

if(cp=NULL){

cerr<<z，Indexisoutrange!/z<<end1;

exit(1);

)

if(ap==NULL)

HL=HL->next;

else

ap->next=cp->next;

deletecp;

}

3.ElemTypeMaxValue(LNode*HL)

〃從單鏈表中查找出所有元素的最大值，該值由函數(shù)返回。

if(HL=NULL){

cerr<<，zLinkedlistisempty!，z?endl;

exit(1);

)

ElemTypemax=HL->data;

LNode*p=HL->next;

while(p!=NULL){

if(max<p->data)max=p->data;

p=p->next;

)

returnmax;

)

4.intCount(LNode*HL,ElemTypex)

〃統(tǒng)計出單鏈表中結(jié)點的值等于給定值x的結(jié)點數(shù)。

(

intn=0;

while(HL!=NULL){

if(HL->data==x)n++;

HL=HL->next;

)

returnn;

}

5.voidCreate(LNode*&HL,ElemTypea[],intn)

〃根據(jù)一維數(shù)組a[n]建立一個單鏈表

(

InitList(HL);

for(inti=nT;i>=0;i-)

InsertFront(HL,a[i]);

)

6.voidOrderList(LNode*&HL)

〃將一個單鏈表重新鏈接成有序單鏈表。

LNode*p=HL;//p指向待處理的第一個結(jié)點，初始指向原表頭

結(jié)點。

HL二NULL;//HL仍為待建立的有序表的表頭指針，初始值為空。

while(p!=NULL)

{〃把原單鏈表中的結(jié)點依次進行有序鏈接。

LNode*q二p;〃q指向待處理的結(jié)點。

p=p->next;//p指向下一個待處理的結(jié)點。

LNode*ap=NULL,*cp=HL;

〃cp指向有序表中待比較的結(jié)點，ap指向其前驅(qū)結(jié)點。

while(cp!=NULL)

{〃為插入q結(jié)點尋找插入位置。

if(q->data<cp->data)

break;

else{

ap=cp;

cp=cp->next;

)

)

〃將q結(jié)點插入到ap和cp結(jié)點之間。

q->next=cp;

if(ap==NULL)

HL=q;

else

ap->nextz=q;

)

7.LNode*Merge1(LNode*&pl,LNode*&p2)

//將兩個有序單鏈表合并成一個有序單鏈表。

(

LNodea;//a結(jié)點作為結(jié)果有序單鏈表的表頭附加結(jié)點，這樣

〃便于處理，處理結(jié)束后返回a結(jié)點的指針域的值。

LNode*p二&a;〃p指向結(jié)果有序單鏈表的表尾結(jié)點，

p->next=NULL;〃初始指向表頭附加結(jié)點。

while((pl!=NULL)&&(P2!=NULL))

{〃處理兩個表非空時的情況。

if(pl->data<p2->data){

p->next=pl;pl=pl->next;

)

else{

p->next=p2;p2=p2->next;

)

p=p->next;

)

if(pl!=NULL)p->next=pl;

if(p2!=NULL)p->next=p2;

pl=p2=NULL;

returna.next;

)

8.LNode*Merge2(LNode*pl,LNode*p2)

〃根據(jù)兩個有序單鏈表生成一個新的有序單鏈表。

(

LNodea;〃用a作為新的有序單鏈表的表頭附加結(jié)點。

LNode*p=&a;〃p指向結(jié)果有序單鏈表的表尾結(jié)點，

p->next=NULL;〃初始指向表頭附加結(jié)點。

while((pl!=NULL)&&(p2!=NULL))

{〃處理兩個表非空時的情況。

LNode*newptr=newLNode;

if(pl->data<p2->data)

〃由pl->data建立新結(jié)點，然后pl指針后移。

newptr->data=p1->data;

pl=pl->next;

)

else

〃由p2->data建立新結(jié)點，然后p2指針后移。

newptr->data=p2->data;

p2=p2->next;

)

〃將newptr結(jié)點插入到結(jié)果有序表的表尾。

p->next=newptr;

p二newptr;

}

while(pl!=NULL)

{〃繼續(xù)處理pl單鏈表中剩余的結(jié)點。

LNode*newptr二newLNode;

newptr->data=pl->data;

pl=pl->next;

p->next=newptr;

p=newptr;

)

while(p2!=NULL)

{〃繼續(xù)處理p2單鏈表中剩余的結(jié)點。

LNode*newptr=newLNode;

newptr->data=p2->data;

p2=p2->next;

p->next=newptr;

p=newptr;

)

p->next=NULL;

returna.next;

}

9.voidSeparate(LNode*HL,LNode*&pl,LNode*&p2)

〃根據(jù)一個單鏈表HL按條件拆分生成為兩個單鏈表pl和p2?

(

LNo加a,b;//a和b結(jié)點分別作為pl和p2單鏈表的表頭附加

結(jié)點。

LNode*tl=&a,*t2=&b;//tl和t2分別作為指向pl和p2單鏈

表

〃的表尾結(jié)點，初始指向表頭附加結(jié)點。

LNode*p=HL;

while(p!=NULL)

(〃每循環(huán)一次產(chǎn)生一個新結(jié)點，并把它加入到

〃pl或p2單鏈表的末尾。

LNode*newptr=newLNode;

if(p->data%2==l){

newptr->data=p->data;

tl->next=newptr;

tl=newptr;

)

else{

newptr->data=p->data;

t2->next=newptr;

t2=newptr;

)

p=p->next;

}

tl->next=t2->next=NULL;

pl=a.next;p2=b.next;〃把指向兩個單鏈表的表頭結(jié)點的

//指針分別賦給pl和p2返回。

第6小題

參考算法如下：

voidJosephus(intn,intm,ints)

〃使用帶表頭附加結(jié)點的循環(huán)單鏈表解決約瑟夫問題。

{

〃生成表頭附加結(jié)點，此時循環(huán)單鏈表為空。

LNode*HL二newLNode;

HL->next=HL;

inti;

〃生成含有n個結(jié)點的、結(jié)點值依次為1,2,...,n的帶表頭附加結(jié)

點

〃的循環(huán)單鏈表。

for(i=n;i>=l;i一){

〃生成新結(jié)點。

LNode*newptr=newLNode;

newptr->data=i;

〃把新結(jié)點插入到表頭。

newptr->next=HL->next;

HL->next=newptr;

)

〃從表頭開始順序查找出第S個結(jié)點，對應(yīng)第一個開始報數(shù)的人。

LNode*ap=HL,*cp=HL->next;

for(i=l;i<s;i++){

//ap和cp指針后移一個位置。

ap=cp;

cp=cp->next;

〃若cp指向了表頭附加結(jié)點，則仍需后移ap和cp指針，

//使之指向表頭結(jié)點。

if(cp==HL){ap=HL;cp=HL->next;}

〃依次使n-1個人出列。

for(i=l;i<n;i++){

〃順序查找出待出列的人，即為循環(huán)結(jié)束后cp所指向的結(jié)點。

for(intj=l;j<m;j++){

ap=cp;

cp=cp->next;

if(cp==HL){ap=HL;cp=HL->next;}

)

〃輸出cp結(jié)點的值，即出列的人。

cout<<cp->data?z，〃；

〃從單鏈表中刪除cp結(jié)點。

ap->next=cp