《數(shù)據(jù)結(jié)構(gòu)》實驗指導(dǎo)

實驗一抽象數(shù)據(jù)類型

-實驗任務(wù)

抽象數(shù)據(jù)類型Triplet的表示和實現(xiàn)。

二實驗?zāi)康?/p>

1)理解和掌握抽象數(shù)據(jù)類型的概念。

2)熟悉數(shù)據(jù)結(jié)構(gòu)的定義及基本操作。

3)實踐系統(tǒng)程序開發(fā)的規(guī)范步驟。

三實驗原理

1.抽象數(shù)據(jù)類型的定義

抽象數(shù)據(jù)類型(ADT,AbstractDataType)由具有一定關(guān)系的一組數(shù)據(jù)和定

義在該組數(shù)據(jù)上的操作組成。抽象數(shù)據(jù)類型為我們提供了一個描述數(shù)據(jù)結(jié)構(gòu)的架

構(gòu)。

抽象數(shù)據(jù)類型的定義一般包括數(shù)據(jù)定義和操作定義兩個部分。一個含抽象數(shù)

據(jù)類型的模塊通常包含定義、表示和實現(xiàn)3個部分。

抽象數(shù)據(jù)類型的形式表示為如下三元組：

(D,S,0)

其中：D是數(shù)據(jù)對象，S是D上的關(guān)系集合，。是D上的基本操作集合。

我們習(xí)慣上把抽象數(shù)據(jù)類型表示成如下格式：

ADT抽象數(shù)據(jù)類型名

{

數(shù)據(jù)對象：(數(shù)據(jù)對象的定義〉

數(shù)據(jù)關(guān)系：(數(shù)據(jù)關(guān)系的定義〉

基本操作：(基本操作的定義〉

}ADT抽象數(shù)據(jù)類型名

例如，抽象數(shù)據(jù)類型Triplet的三元組定義：

ADTTriplet{

數(shù)場對象:D={el,e2,e3|el,e2,e3IElemSet}

數(shù)據(jù)關(guān)系：Rl={<E1,e2>,<E2,e3>}

基本操作：

InitTriplet(&T,vl,v2,v3)

操作結(jié)果：構(gòu)造了三元組T,元素el,e2和e3分別被賦以參數(shù)vl,v2

和v3的值

DestroyTriplet(&T)

操作結(jié)果：三元組T被銷毀。

Get(T,i,&e)

初始條件：三元組T已存在，l￡i￡3o

操作結(jié)果：用e返回T的第i元的值。

Put(&T,i,e)

初始條件：三元組T已經(jīng)存在，l￡i￡3。

操作結(jié)果：改變T的第i元的值為e。

IsAscending(T)

初始條件：三元組T已存在。

操作結(jié)果：如果T的三個元素按升序排列，則返回1,否則返回0。

IsDescending(T)

初始條件：三元組T已存在。

操作結(jié)果：如果T的三個元素按降序排列，則返回1,否則返回0。

Max(T,&e)

初始條件：三元組T已存在。

操作結(jié)果：用e返回T中三個元素的最大值。

Min(T,&e)

初始條件：三元組T已存在。

操作結(jié)果：用e返回T中三個元素的最小值。

}ADTTriplet

2.抽象數(shù)據(jù)類型的表示與實現(xiàn)

我們可以通過固有數(shù)據(jù)類型來表示和實現(xiàn)抽象數(shù)據(jù)類型，即利用處理器中已

存在的數(shù)據(jù)類型來說明新的結(jié)構(gòu)，用已經(jīng)實現(xiàn)的操作來組合新的操作。我們約定

以C語言作為數(shù)據(jù)結(jié)果的描述工具。

例如，抽象數(shù)據(jù)類型Triplet的表示和實現(xiàn)如下：

typedefElemType*Triplet;

//------基本操作的實現(xiàn)-------

StatusInitTriplet(Triplet&T,ElemTypevl,ElemTypev2,

ElemTypev3)<

〃構(gòu)造三元組T,依次設(shè)置T的三個元素的初值為vl,v2和v3。

T=(ElemType*)malloc(3*sizeof(ElemType));

if(!T)exit(OVERFLOW);

T[0]=vl;T[1]=v2;T[2]=v3;

returnOK!

}

StatusDestroyTriplet(Triplet&T)<

free(T);T=NULL;

returnOK!

}

StatusGet(TripletTzinti,ElemType&e){

if(i<111i>3)returnERROR;

e=T[i-l];

returnOK!

}

StatusPut(Triplet&T,inti,ElemTypee){

if(i<111i>3)returnERROR;

T[i-1]=e;

returnOK!

}

）

四實驗設(shè)備、儀器、工具及資料

微機(jī)、VC

五實驗內(nèi)容

通過C語言實現(xiàn)一個可無誤運(yùn)行的完整程序，完成抽象數(shù)據(jù)類型Triplet的

表示和實現(xiàn)。要求：程序運(yùn)行時顯示基本操作的菜單，由用戶選擇執(zhí)行相應(yīng)操作

（如：可利用switch語句等），以此整合Triplet的各基本操作，實現(xiàn)程序設(shè)計。

六實驗步驟

（1）實驗預(yù)習(xí)

1）預(yù)習(xí)本實驗原理中關(guān)于抽象數(shù)據(jù)類型Triplet的定義、表示及實現(xiàn)。

2）熟悉程序運(yùn)行環(huán)境VC的使用。

（2）實驗步驟

1）問題分析與系統(tǒng)的結(jié)構(gòu)設(shè)計。充分地分析和理解此實驗項目，弄清要求

作什么，限制條件是什么。按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊。最后寫出每

個子程序（過程或函數(shù)）的規(guī)格說明，列出它們之間的調(diào)用關(guān)系，可以使用調(diào)用

關(guān)系圖表示則更加清晰，這樣便完成了系統(tǒng)結(jié)構(gòu)設(shè)計。

2）詳細(xì)設(shè)計和編碼。詳細(xì)設(shè)計的目的是對子程序（過程或函數(shù)）的進(jìn)一步

求精。用IF、WHILE和賦值語句等，以及自然語言寫出算法的框架。利用自然

語言的目的是避免陷入細(xì)節(jié)。在編碼時，可以對詳細(xì)設(shè)計的結(jié)果進(jìn)一步求精，用

高級語言表示出來。

3）在VC環(huán)境下調(diào)試程序。

七實驗報告要求

實驗報告包含程序開發(fā)過程所形成的所有文檔資料，包括如下內(nèi)容：

1）需求分析及規(guī)格說明：問題描述，求解的問題是什么。

2）概要設(shè)計：本程序所用的數(shù)據(jù)類型定義；主程序流程；程序模塊及相互

關(guān)系。

3）詳細(xì)設(shè)計：采用C語言定義的數(shù)據(jù)結(jié)構(gòu)；各模塊的偽碼算法；各函數(shù)調(diào)

用關(guān)系。

4）調(diào)試報告。

5）本實驗項目的程序清單及運(yùn)行結(jié)果。

八思考題

為什么用抽象數(shù)據(jù)類型描述數(shù)據(jù)結(jié)構(gòu)？

實驗二線性表

一實驗任務(wù)

1）線性表的順序表示和實現(xiàn)

2）線性表的鏈?zhǔn)浇Y(jié)構(gòu)表示和實現(xiàn)

二實驗?zāi)康?/p>

1）掌握線性表的類型定義和結(jié)構(gòu)特點。

2）掌握線性表的順序存儲表示、鏈?zhǔn)酱鎯Ρ硎炯捌銫語言實現(xiàn)。

3）掌握順序表的各種基本操作的實現(xiàn)。

4）掌握線性表在鏈?zhǔn)酱鎯Y(jié)構(gòu)上的各種操作。

三實驗原理

1.線性表的邏輯結(jié)構(gòu)及特性

所謂線性表(Linear_List),就是水(120)個數(shù)據(jù)元素的集合{ai,32,an},

這些數(shù)據(jù)元素之間有邏輯上的線性關(guān)系。

線性表的抽象數(shù)據(jù)類型定義如下：

ADTList

數(shù)據(jù)對象：D={aj|ajGEIemSet,i=l,2,n>0}

數(shù)據(jù)關(guān)系：Rl={<aj-i,aj>|aj-1,ajGD,i=2,...,n)

基本操作：

CreatList(&L)

操作結(jié)果：生成一個空的線性表L。

ListLength(L)

初始條件：線性表L已存在。

操作結(jié)果：返回L中數(shù)據(jù)元素個數(shù)。

ListInsert(&L,i,e)

初始條件：線性表L已存在，lSiWListLength(L)+l。

操作結(jié)果:在L中第i個位置之前插入新的數(shù)據(jù)元素e,L的長度加lo

ListDelete(&L,i,&e)

初始條件：線性表L已存在且非空，l<i<ListLength(L)o

操作結(jié)果：刪除L的第i個數(shù)據(jù)元素，并用e返回其值，L的長度減

lo

Get日em(L,i,&e)

初始條件：線性表L已存在，ISiSListLength(L)。

操作結(jié)果：用e返回L中第i個數(shù)據(jù)元素的值。

LocateElem(L,e,compare())

初始條件：線性表L已存在，compare()是數(shù)據(jù)元素判定函數(shù)。

操作結(jié)果：返回L中第1個與e滿足關(guān)系compare()的數(shù)據(jù)元素的位

序。若這樣的數(shù)據(jù)元素不存在，則返回值為0。

ListEmpty(L)

初始條件：線性表L已存在。

操作結(jié)果：若L為空表，則返回TRUE,否則返回FALSE。

ClearList(&L)

初始條件：線性表L已存在。

操作結(jié)果：將L重置為空表。

DestroyList(&L)

初始條件：線性表L已存在。

操作結(jié)果：銷毀線性表L。

}ADTList

2.線性表的順序表示

線性表的順序表示就是利用一組地址連續(xù)的內(nèi)存空間依次存儲線性表的各

個數(shù)據(jù)元素，即以元素在計算機(jī)內(nèi)''物理位置相鄰”來表示線性表中數(shù)據(jù)元素之間

的邏輯關(guān)系。

由于順序存儲結(jié)構(gòu)是一種隨機(jī)存取的存儲結(jié)構(gòu)，所以通常利用C語言中動態(tài)

分配的一組連續(xù)的存儲單元作為順序存儲結(jié)構(gòu)所需要的存儲空間。

可通過定義結(jié)構(gòu)體類型來實現(xiàn)線性表的動態(tài)分配順序存儲結(jié)構(gòu)。具體數(shù)據(jù)類

型描述如下：

#defineMAXLEN100

#defineLISTJNCREASE10〃線性表存儲空間的動態(tài)分配增量

typedefstruct

{

ElemType*list;〃線性表的存儲空間的基地址

intlength;〃線性表的當(dāng)前長度

intmaxsize;〃線性表當(dāng)前分配的存儲容量

}List_Sq;

3.磨性表的鏈?zhǔn)浇Y(jié)構(gòu)

鏈?zhǔn)酱鎯Y(jié)構(gòu)具有以下特點：不要求邏輯上相鄰的元素在物理結(jié)構(gòu)上也相鄰;

允許迅速簡單地插入或刪除結(jié)點，而不必移動大量元素；但只能順序存取而不能

隨機(jī)存取線性表中任一元素。

線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)可通過單鏈表來實現(xiàn)。此時，線性表中的每個元素對

應(yīng)單鏈表中的一個結(jié)點，每個結(jié)點的數(shù)據(jù)域存儲線性表的數(shù)據(jù)元素，每個結(jié)點的

指針域存儲其后繼元素所在結(jié)點的地址，可以通過每個結(jié)點的指針域訪問到其后

繼結(jié)點，如圖2.1所示。

頭指針第一，結(jié)藥

——aJ-%—?機(jī)—?a.A

圖2.1線性鏈表示例

因此，單鏈表中每個結(jié)點都是由包含這個數(shù)據(jù)元素的信息和一個指示其直接

后繼的指針組成的一個結(jié)構(gòu)體類型，具體描述如下：

typedefstructLNode

{

ElemTypedata;

structLNode*next;

}LNode,*List_Link;

每個單鏈表的反指針L是List_Link型的變量，指向鏈表中第一個結(jié)點。由表

頭指針出發(fā)可以依次訪問到每個結(jié)點，存取相應(yīng)的數(shù)據(jù)元素值。線性表中數(shù)據(jù)元

素間的線性關(guān)系都可以通過單鏈表中結(jié)點指針域的鏈接關(guān)系反映出來。當(dāng)

L=NULL時，意味著所表示的線性表為''空"表，其長度n為''零"。

四實驗設(shè)備、儀器、工具及資料

微機(jī)、VC

五實驗內(nèi)容

（1）實驗任務(wù)1：順序表的表示與實現(xiàn)

請編制C程序，利用順序存儲方式來實現(xiàn)下列功能：

1）建立主程序菜單，使之具有建立線性表、插入元素、刪除元素、查找元

素、銷毀線性表、結(jié)束程序運(yùn)行等菜單項。

2）根據(jù)鍵盤輸入數(shù)據(jù)生成一個線性表，并輸出該原始線性表。

3）根據(jù)屏幕菜單的提示選擇，進(jìn)行數(shù)據(jù)插入、刪除、查找等操作。

4）最后，輸出修改之后的線性表并結(jié)束程序的運(yùn)行。

（2）實驗任務(wù)2：線性表的鏈?zhǔn)酱鎯Ρ硎九c實現(xiàn)

請編制C程序，利用鏈?zhǔn)酱鎯Ψ绞絹韺崿F(xiàn)下列功能：

1）建立主程序菜單，使之具有建立線性表、插入元素、刪除元素、查找元

素、銷毀線性表、結(jié)束程序運(yùn)行等菜單項。

2）根據(jù)鍵盤輸入數(shù)據(jù)生成一個單鏈表，并輸出該原始單鏈表。

3）根據(jù)屏幕菜單的提示選擇，進(jìn)行數(shù)據(jù)插入、刪除、查找等操作。

4）最后，輸出修改之后的單鏈表并結(jié)束程序的運(yùn)行。

（3）實驗任務(wù)3：線性表的合并（選做）

編制C程序?qū)崿F(xiàn)下列功能：

1）建立兩個線性表（順序存儲表示或鏈?zhǔn)酱鎯Ρ硎荆?/p>

2）對已建立的兩個線性表進(jìn)行升序排序。

3）合并這兩個有序表。

六實驗步驟

（1）實驗預(yù)習(xí)

1）預(yù)習(xí)本實驗原理中關(guān)于線性表的定義、順序存儲表示和鏈?zhǔn)酱鎯Y(jié)構(gòu)。

2）分析掌握教材21~23頁中的算法2-1~2-5,為完成實驗任務(wù)1做好準(zhǔn)備。

3）分析掌握教材27~30頁中的算法2-9~2-13,為完成實驗任務(wù)2做好準(zhǔn)

備。

4）分析掌握教材25頁中的算法2-7~2-8或教材31~32頁中的算法

2-15-2-16,為完成實驗任務(wù)3做好準(zhǔn)備。

（2）實驗步驟

1）問題分析。充分地分析和理解此實驗任務(wù)，弄清要求作什么，限制條件

是什么。

2）系統(tǒng)的結(jié)構(gòu)設(shè)計。按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊。最后寫出每

個子程序（過程或函數(shù)）的規(guī)格說明，列出它們之間的調(diào)用關(guān)系，可以使用調(diào)用

關(guān)系圖表示則更加清晰，這樣便完成了系統(tǒng)結(jié)構(gòu)設(shè)計。

3）詳細(xì)設(shè)計。詳細(xì)設(shè)計的目的是對子程序（過程或函數(shù)）的進(jìn)一步求精。

用IF、WHILE和賦值語句等，以及自然語言寫出算法的框架。利用自然語言的

目的是避免陷入細(xì)節(jié)。

4）編碼。在詳細(xì)設(shè)計的基礎(chǔ)上，對詳細(xì)設(shè)計的結(jié)果進(jìn)一步求精，用C語言

表示出來。

5）在VC環(huán)境下調(diào)試程序。

七實驗報告要求

實驗報告包含程序開發(fā)過程所形成的所有文檔資料，包括如下內(nèi)容：

1）需求分析及規(guī)格說明：問題描述，求解的問題是什么。

2）概要設(shè)計：本程序所用的數(shù)據(jù)類型定義；主程序流程；程序模塊及相互

關(guān)系。

3）詳細(xì)設(shè)計：采用C語言定義的數(shù)據(jù)結(jié)構(gòu)；各模塊的偽碼算法；各函數(shù)調(diào)

用關(guān)系。

4）調(diào)試報告。

5）本實驗任務(wù)1、2的程序清單及運(yùn)行結(jié)果。

八思考題

1)通過實驗任務(wù)1、2的實現(xiàn)比較線性表的兩種存儲結(jié)構(gòu)的優(yōu)缺點。

2)實現(xiàn)任務(wù)3種采用哪種存儲表示更容易些？

實驗三棧與隊列

-實驗任務(wù)

1)棧的應(yīng)用

2)隊列的表示與實現(xiàn)

二實驗?zāi)康?/p>

1)了解棧與隊列的特性

2)掌握棧的順序、鏈?zhǔn)酱鎯Ρ硎炯皩崿F(xiàn)

3)掌握隊列的順序、鏈?zhǔn)酱鎯Ρ硎炯皩崿F(xiàn)

4)掌握棧與隊列在實際問題中的應(yīng)用

三實驗原理

1.棧的特性

棧(Stack)又稱堆棧，是一種特殊的線性表，可定義為插入、刪除和訪問

只能在某一端進(jìn)行的線性數(shù)據(jù)結(jié)構(gòu)。堆棧允許插入、刪除和訪問的一端稱為棧頂

(Top),另一端稱為棧底(Bottom)o棧頂?shù)牡谝粋€元素被稱為棧頂元素。

堆棧的性質(zhì)決定它的數(shù)據(jù)是按''先進(jìn)后出”的順序被訪問，即最先存儲的元素

最后被訪問、刪除，最后存儲的元素最先被訪問、刪除，所以棧也稱為"LIFO"

(Last_In,First_Out)。

棧而抽象數(shù)例類型定義如下：

ADTStack{

數(shù)據(jù)對象：D={ai|aiGElemSet,i=1,2,n>0}

數(shù)據(jù)關(guān)系:R={<ai-i,ai>|aH,aieD,i=2,...,n)

約定an端為棧頂，ai端為棧底。

基本操作：

InitStack(&S)

操作結(jié)果：構(gòu)造一個空棧S。

Push(&S,e)

初始條件：棧S已存在。

操作結(jié)果：插入元素e為新的棧頂元素。

Pop(&S,&e)

初始條件：棧S已存在且非空。

操作結(jié)果：刪除S的棧頂元素，并用e返回其值。

GetTbp(S,&e)

初始條件：棧S已存在且非空。

操作結(jié)果：用e返回S的棧頂元素。

StackEmpty(S)

初始條件：棧S已存在。

操作結(jié)果：若S為空棧，則返回TRUE,否則返回FALSE。

StackLength(S)

初始條件：棧S已存在。

操作結(jié)果：返回S的元素個數(shù)，即棧的長度。

StackTraverse(S,visit())

初始條件：棧S已存在且非空。

操作結(jié)果：從棧底到棧頂依次對S的每個數(shù)據(jù)元素調(diào)用函數(shù)visit

()o-Bvisit()失敗，則操作失敗。

ClearStack(&S)

初始條件：棧S已存在。

操作結(jié)果：將S清為空棧。

DestroyStack(&S)

初始條件：棧S已存在。

操作結(jié)果：棧S被銷毀。

}ADTStack

2.棧的順序表示

棧的順序存儲結(jié)構(gòu)，即順序棧，是利用一組連續(xù)的存儲單元依次存放自棧底

到棧頂?shù)臄?shù)據(jù)元素，同時通過指針top指示棧頂元素在順序棧中的位置。由于很

難估計棧在使用過程中所需要的最大空間的大小，所以通常利用C語言中動態(tài)分

配的一組連續(xù)的存儲單元作為順序棧所需要的存儲空間。

順序棧所需要的具體數(shù)據(jù)類型描述如下：

#defineMAXLEN100

#defineSTACKJNCREASE10〃順序棧存儲空間的動態(tài)分配增量

typedefstruct{

ElemType*base;〃棧的存儲空間的基地址，即棧底指針

ElemType*top;〃棧頂指針

intmaxsize;〃棧當(dāng)前分配的存儲容量

}SqStack;

其中，maxsize指示棧當(dāng)前可使用的最大容量；base為棧底指針，在順序棧

中，它始終指向棧底的位置，若base=NULL,則表明棧結(jié)構(gòu)不存在；top為棧頂

指針，起初值為棧底指針值，即top=base,這也可作為?？盏臉?biāo)記。棧插入新

元素時，將新元素插入到棧頂指針?biāo)赶虻奈恢?，同時指針top增1,刪除棧頂

元素時，指針top減1。

3.棧的鏈?zhǔn)酱鎯Ρ硎?/p>

棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)，即鏈棧，與線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)類似，是通過由結(jié)點

構(gòu)成的單鏈表實現(xiàn)的，但每個結(jié)點的指針指向其前驅(qū)結(jié)點(在其之前進(jìn)棧的結(jié)點)。

此時，表頭指針稱為棧頂指針，其指向的結(jié)點即為棧頂結(jié)點。所需要的具體數(shù)據(jù)

類型描述如下：

typedefstructSNode{

ElemTypedata;

structSNode*prior;〃prior將指向其前一次入棧的元素

}SNode,*SLink;

4.隊列的特性

隊列(Queue)簡稱隊，也是一種特殊的線性表，可定義為只允許在表的一

端進(jìn)行插入，而在表的另一端進(jìn)行刪除的線性結(jié)構(gòu)。隊列允許插入的一端稱為隊

尾(Rear),允許刪除的一端稱為隊首(Front)?

由于隊列的插入和刪除分別在不同的兩端進(jìn)行，因而先插入者自然先從另一

端刪除，所以隊列具有''先進(jìn)先出"的特點，簡稱為FIFO(First-In,First-Out)。

隊列的抽象數(shù)據(jù)類型定義如下：

ADTQueue{

數(shù)據(jù)對象：D={ai|aieElemSet,i=n>0}

數(shù)據(jù)關(guān)系：Rl={<ai.i,a,>|ai-i,aiGD,i=2,...,n}

約定其中ai端為隊首，an端為隊尾。

基本操作：

InitQueue(&Q)

操作結(jié)果：構(gòu)造一個空隊列Q。

QueueEmpty(Q)

初始條件：隊列Q已存在。

操作結(jié)果：若Q為空隊列，則返回TRUE,否則FALSE。

QueueLength(Q)

'初始條件：隊列Q已存在。

操作結(jié)果：返回Q的元素個數(shù)，即隊列的長度。

EnQueue(&Q,e)

初始條件：隊列Q已存在。

操作結(jié)果：插入元素e為Q的新的隊尾元素。

DeQueue(&Q,&e)

初始條件：Q為非空隊列。

操作結(jié)果：刪除Q的隊首元素，并用e返回其值。

GetHead(Q,&e)

初始條件：Q為非空隊列。

操作結(jié)果：用e返回Q的隊首元素。

QueueTraverse(Q,visit())

初始條件：Q已存在且非空。

操作結(jié)果：從隊首到隊尾，依次對Q的每個數(shù)據(jù)元素調(diào)用函數(shù)

visit()0一旦visit。失敗，則操作失敗。

ClearQueue(&Q)

初始條件：隊列Q已存在。

操作結(jié)果：將Q清為空隊列。

DestroyQueue(&Q)

初始條件：隊列Q已存在。

操作結(jié)果：隊列Q被銷毀，不再存在。

}ADTQueue

5.隊列的順序表示

隊列的順序存儲結(jié)構(gòu)，用一組地址連續(xù)的存儲單元依次存放從隊首到隊尾的

元素，同時附設(shè)兩個指針-front和rear分別指示隊首元素及隊尾元素的位置。

循環(huán)隊列所需要的具體數(shù)據(jù)類型描述如下：

#defineMAXQSIZE100〃最大隊列長度

typedefstruct{

ElemType*base;〃初始化的動態(tài)分配存儲空間

intfront;〃頭指針，若隊列不空，指向隊首元素

intrear;〃尾指針，若隊列不空，指向隊尾元素的下一個位置

}SqQueue;

6.隊列的鏈?zhǔn)酱鎯Ρ硎?/p>

隊列的鏈接存儲結(jié)構(gòu)，簡稱鏈隊列。鏈隊列所需要的具體數(shù)據(jù)類型描述如下:

typedefstructQNode{

ElemTypedata;〃值域

structQNode*next;〃鏈接指針域

}QNode,*QueuePtr;

typedefstruct{

QueuePtrfront;〃頭指針

QueuePtrrear;〃尾指針

}LinkQueue;

四實驗設(shè)備、儀器、工具與材料

微機(jī)、VC

五實驗內(nèi)容

（1）實驗任務(wù)1：棧的應(yīng)用一迷宮求解

編制C程序完成迷宮問題。程序基本要求：用戶輸入迷宮數(shù)據(jù)初始化迷宮；

利用棧的順序表示以及入棧、出棧等基本操作，實現(xiàn)迷宮路徑的求解；輸出求解

得到的完整路徑（或提示迷宮無通路）。

（2）實驗任務(wù)2：隊列的表示與實現(xiàn)

編寫一個C程序?qū)崿F(xiàn)順序隊列的各種基本操作，并在此基礎(chǔ)上設(shè)計一個主程

序，完成如下功能：

1）建立循環(huán)隊列

2）入隊列

3）出隊列

4）判斷隊列是否為空

5）遍歷隊列

6）取隊首元素

六實驗步驟

（1）實驗預(yù)習(xí)

1）預(yù)習(xí)本實驗原理中關(guān)于棧與隊列的定義、順序存儲表示。

2）分析掌握教材48~50頁中的算法3-1-3-4,為完成實驗任務(wù)1做好準(zhǔn)備。

3）分析掌握教材57~60頁中迷宮問題及求解算法3-13,為完成實驗任務(wù)1

做好準(zhǔn)備。

4）分析掌握教材70~73頁中的算法3-15~3-20,為完成實驗任務(wù)2做好準(zhǔn)

備。

（2）實驗步驟

1）問題分析。充分地分析和理解此實驗任務(wù)，弄清要求作什么，限制條件

是什么。

2）系統(tǒng)的結(jié)構(gòu)設(shè)計。按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊。最后寫出每

個子程序（過程或函數(shù)）的規(guī)格說明，列出它們之間的調(diào)用關(guān)系，可以使用調(diào)用

關(guān)系圖表示則更加清晰，這樣便完成了系統(tǒng)結(jié)構(gòu)設(shè)計。

3）詳細(xì)設(shè)計。詳細(xì)設(shè)計的目的是對子程序（過程或函數(shù)）的進(jìn)一步求精。

用IF、WHILE和賦值語句等，以及自然語言寫出算法的框架。利用自然語言的

目的是避免陷入細(xì)節(jié)。

4）編碼。在詳細(xì)設(shè)計的基礎(chǔ)上，對詳細(xì)設(shè)計的結(jié)果進(jìn)一步求精，用C語言

表示出來。

5）在VC環(huán)境下調(diào)試程序。

七實驗報告要求

實驗報告包含程序開發(fā)過程所形成的所有文檔資料，包括如下內(nèi)容：

1）需求分析及規(guī)格說明：問題描述，求解的問題是什么。

2）概要設(shè)計：本程序所用的數(shù)據(jù)類型定義；主程序流程；程序模塊及相互

關(guān)系。

3）詳細(xì)設(shè)計：采用C語言定義的數(shù)據(jù)結(jié)構(gòu)；各模塊的偽碼算法；各函數(shù)調(diào)

用關(guān)系。

4）調(diào)試報告。

5）本實驗任務(wù)1、2的程序清單及運(yùn)行結(jié)果。

八思考題

如果一個程序中用到兩個棧，為了不發(fā)生溢出錯誤，就必須給每個棧預(yù)先一

個較大的存儲空間。若每個棧都預(yù)先分配過大的存儲空間，勢必造成系統(tǒng)空間緊

張，如何解決這個問題？

實驗四樹和二叉樹

-實驗任務(wù)

1）二叉樹的表示與實現(xiàn)

2）Huffman編碼

—實驗?zāi)康?/p>

1）掌握二叉樹的類型定義和結(jié)構(gòu)特點。

2）掌握二叉樹的鏈?zhǔn)酱鎯Ρ硎竞蛯崿F(xiàn)。

3）掌握赫夫曼樹及其應(yīng)用

三實驗原理

1.二叉樹的定義

所謂二叉樹，是指結(jié)點的一個有限集合，它或為空集，或為滿足下列性質(zhì)的

非空集合：有且只有一個根結(jié)點，其余結(jié)點分成左右兩個互不相交的集合TL、

TR,且TL、TR均為二叉樹。

二叉樹的抽象數(shù)據(jù)類型定義如下：

ADTBinaryTree{

數(shù)據(jù)對或D：D=Qi|aiGEIemSet,i=l,2,n>0}

數(shù)據(jù)關(guān)系R：若D為空集，則稱為空二叉樹。

若D僅含一個數(shù)據(jù)元素，則R為空集，否則R={H},H滿足關(guān)系：

<!-[if!supportLists]->（l）<!-[endif]-->T中存在唯一的一個結(jié)點，

它沒有前驅(qū)，稱為樹的根，用root表示，在集合D中用ai表示；

<!-[if!supportLists]->（2）<!--[endif]-->若D中元素個數(shù)大于1,對

于任意的數(shù)據(jù)元素aj￡D且心2,存在唯一的數(shù)據(jù)元素aiGD,有<A,

aj>eH；

<!--[if!supportLists]-->（3）<!--[endif]-，若D中元素個數(shù)大于1,對

于任意的數(shù)據(jù)元素ai￡D,僅存在不多于2個數(shù)據(jù)元素aj,ak￡D且j,

k>i,有<a.aj>,<a.ak>WH,其中，若j<K<span>,則稱可

為ai的左孩子節(jié)點，ak為ai的右孩子節(jié)點。

基本操作P：

InitBiTree（&T）;

操作結(jié)果：構(gòu)造空二叉樹T。

CreateBiTree(&T,tree);

初始條件：tree給出二叉樹T的表示形式。

操作結(jié)果：按tree構(gòu)造二叉樹T。

BiTreeEmpty(T);

初始條件：二叉樹T存在。

操作結(jié)果：若T為空樹，則返回TRUE否則返回FALSE。

BiTreeDepth(T);

初始條件：二叉樹T存在。

操作結(jié)果：返回T的深度。

Root(T);

初始條件：二叉樹T存在。

操作結(jié)果：返回T的根。

Value(T,e);

初始條件：二叉樹T存在，e是需尋找的結(jié)點的值。

操作結(jié)果：若找到該結(jié)點，則函數(shù)返回TRUE,否則返回FALSE。

Assign(T,e,value);

初始條件：二叉樹T存在，e是需尋找的結(jié)點的值。

操作結(jié)果：若找到該結(jié)點，結(jié)點e賦值為value,則函數(shù)返回TRUE

否則返回FALSEo

Parent(T,e,P);

初始條件：二叉樹T存在，e是需尋找的結(jié)點的值。

操作結(jié)果：若樹中存在值為e的結(jié)點，則函數(shù)返回TRUE,否則返回

FALSE；若存在該結(jié)點，用P返回雙親結(jié)點的位置，若結(jié)

點為根結(jié)點，則P返回空。

LeftChild(T,e,P);

初始條件：二叉樹T存在，e是需尋找的結(jié)點的值。

操作結(jié)果：若樹中存在值為e的結(jié)點，則函數(shù)返回TRUE,否則返回

FALSE；若存在該結(jié)點，用P返回左孩子結(jié)點的位置，若

結(jié)點無左孩子結(jié)點，則P返回空。

RightChild(T,e,P);

初始條件：二叉樹T存在，e是需尋找的結(jié)點的值。

操作結(jié)果：若樹中存在值為e的結(jié)點，則函數(shù)返回TRUE否則返回

FALSE；若存在該結(jié)點，用P返回右孩子結(jié)點的位置，若

結(jié)點無右孩子結(jié)點，則P返回空。

DelBiTreeNode(&T,P);

初始條件：二叉樹T存在，P指向該二叉樹中的一個結(jié)點。

操作結(jié)果：刪除P所指向的結(jié)點及其子樹。

TraverseBiTree(T,visit());

初始條件：二叉樹T存在，visit是對結(jié)點操作的應(yīng)用函數(shù)。

操作結(jié)果：按某種次序?qū)的每個結(jié)點調(diào)用函數(shù)visit()一次且至多

一次。一旦visit。失敗，則操作失敗。

ClearBiTree(&T);

初始條件：二叉樹T存在。

操作結(jié)果：將二叉樹T清空。

}ADTBinaryTree

2.二叉樹的鏈?zhǔn)酱鎯Ρ硎?/p>

二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)通常采用二叉鏈表形式，即在每個結(jié)點中設(shè)置三個域,

分別為數(shù)據(jù)域data、左指針域left和右指針域right。其中，數(shù)據(jù)域用于存儲對

應(yīng)的數(shù)據(jù)元素，left和right用來分別存儲左孩子和右孩子結(jié)點的存儲位置。

二叉鏈表的結(jié)點類型可定義為：

typedefstructBiTreeNode{

ElemTypedata;

structBiTreeNode*left;

structBiTreeNode*right;

}BiTreeNode,*BiTreePtr;

3.二叉樹的遍歷

二叉樹的遍歷是二叉樹中最重要的運(yùn)算，也是各種操作的基礎(chǔ)。二叉樹的遍

歷是指按照某個搜索路徑尋訪樹中的每個結(jié)點，使得每個結(jié)點均被訪問一次，而

且僅被訪問一次。在遍歷的過程中，可以對結(jié)點進(jìn)行各種操作。

根據(jù)二叉樹的遞歸定義，一棵非空二叉樹由根結(jié)點、左子樹和右子樹組成，

因此，遍歷一棵二叉樹可以分解為三個問題：訪問根結(jié)點、遍歷左子樹、遍歷右

子樹。若分別用D、L、R表示上述三個子問題，則可能有DLR、LDR、LRD、DRL、

RDL、RLD幾種情況。若限定先左后右，則只有前3種情況：

(1)DLR,此時訪問根結(jié)點的操作在遍歷左、右子樹之前，故稱之為先序遍

歷或先根遍歷；

(2)LDR,此時訪問根結(jié)點的操作在遍歷左子樹之后、右子樹之前，故稱之

為中序遍歷或中根遍歷；

(3)LRD,此時訪問根結(jié)點的操作在遍歷左、右子樹之后，故稱之為后序

遍歷或后根遍歷。

4赫夫曼樹

n個帶權(quán)葉子結(jié)點構(gòu)成的所有二叉樹中，帶權(quán)路徑長度WPL最小的二叉樹稱

作赫夫曼樹。權(quán)值越大的結(jié)點離根越近的二叉樹才是最優(yōu)二叉樹。

赫夫曼樹構(gòu)造算法，具體敘述如下：

(1)給定n個權(quán)值{Wi,W2,…，Wn},對應(yīng)n個結(jié)點，構(gòu)成具有n棵二叉樹的

森林F={TI,T2,…,Tn},其中每棵二叉樹Ti(l<i<n)都只有一個權(quán)值為少的根

結(jié)點，其左右子樹均為空。

(2)在森林F中選出兩棵根結(jié)點的權(quán)值最小的樹作為一棵新樹的左、右子樹，

且置新樹的根結(jié)點的權(quán)值為其左、右子樹上根結(jié)點的權(quán)值之和。

(3)從F中刪除構(gòu)成新樹的那兩棵樹，同時把新樹加入F中。

(4)重復(fù)(2)和(3),直到F中只含有一棵樹為止，此樹就是赫夫曼樹。

5.赫夫曼編碼

若要設(shè)計長短不等的編碼，則要求字符集中任一個字符的編碼都不是另一個

字符的編碼的前綴，這種編碼稱做前綴編碼。

為了使不等長編碼為前綴編碼，可用該字符集中的每個字符作為葉子結(jié)點生

成一棵編碼二叉樹，將每個字符出現(xiàn)的次數(shù)作為字符結(jié)點的權(quán)值賦予該結(jié)點上，

求出此樹的最小帶權(quán)路徑長度，也就是傳送電文的最短長度。因此，求傳送電文

的最短長度問題就轉(zhuǎn)化為求由字符集中的所有字符作為葉子結(jié)點且由字符的出

現(xiàn)頻率作為其權(quán)值所產(chǎn)生的赫夫曼樹的問題。

四實驗設(shè)備、儀器、工具與資料

微機(jī)、VC

五實驗內(nèi)容

（1）實驗任務(wù)1:二叉樹建立和遍歷

編制C程序?qū)崿F(xiàn)下列功能：

1）建立二叉樹。

2）按先序、中序、后序方式遍歷二叉樹。

程序的基本要求：采用二叉鏈表存儲結(jié)構(gòu)表示二叉樹；通過二叉樹廣義表輸

入所有結(jié)點建立二叉樹；通過遞歸算法實現(xiàn)二叉樹的遍歷并輸出結(jié)點數(shù)據(jù)信息。

（2）實驗任務(wù)2：赫夫曼編碼

從鍵盤上輸入n個字符及其權(quán)值，編制C程序建立赫夫曼樹，并編碼輸出。

六實驗步驟

（1）實驗預(yù)習(xí)

1）預(yù)習(xí)本實驗原理中關(guān)于二叉樹的定義、二叉鏈表存儲表示。

2）分析掌握教材93~99頁中的算法4-1~4-4、算法4-7~4-7,為完成實驗

任務(wù)1做好準(zhǔn)備。

3）預(yù)習(xí)本實驗原理中關(guān)于赫夫曼樹、赫夫曼編碼的含義及赫夫曼樹的構(gòu)造

方法。

4）分析掌握教材頁中的算法4-14~4-15,為完成實驗任務(wù)2做好

準(zhǔn)備。

（2）實驗步驟

1）問題分析。充分地分析和理解此實驗任務(wù)，弄清要求作什么，限制條件

是什么。

2）系統(tǒng)的結(jié)構(gòu)設(shè)計。按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊。最后寫出每

個子程序（過程或函數(shù)）的規(guī)格說明，列出它們之間的調(diào)用關(guān)系，可以使用調(diào)用

關(guān)系圖表示則更加清晰，這樣便完成了系統(tǒng)結(jié)構(gòu)設(shè)計。

3）詳細(xì)設(shè)計。詳細(xì)設(shè)計的目的是對子程序（過程或函數(shù)）的進(jìn)一步求精。

用IF、WHILE和賦值語句等，以及自然語言寫出算法的框架。利用自然語言的

目的是避免陷入細(xì)節(jié)。

4）編碼。在詳細(xì)設(shè)計的基礎(chǔ)上，對詳細(xì)設(shè)計的結(jié)果進(jìn)一步求精，用C語言

表示出來。

5）在VC環(huán)境下調(diào)試程序。

七實驗報告要求

實驗報告包含程序開發(fā)過程所形成的所有文檔資料，包括如下內(nèi)容：

1）需求分析及規(guī)格說明：問題描述，求解的問題是什么。

2）概要設(shè)計：本程序所用的數(shù)據(jù)類型定義；主程序流程；程序模塊及相互

關(guān)系。

3）詳細(xì)設(shè)計：采用C語言定義的數(shù)據(jù)結(jié)構(gòu)；各模塊的偽碼算法；各函數(shù)調(diào)

用關(guān)系。

4）調(diào)試報告。

5）本實驗任務(wù)1、2的程序清單及運(yùn)行結(jié)果。

八思考題

1)如何以廣義表的形式輸出二叉樹？

2)如何用非遞歸算法實現(xiàn)二叉樹的中序遍歷？

3)如何利用已建好的赫夫曼編碼對輸入的正文進(jìn)行譯碼?

實驗五圖

一實驗任務(wù)

1)圖的鄰接表存儲與遍歷

2)圖的最短路徑求解

二實驗?zāi)康?/p>

1)圖的基本存儲方法。

2)掌握圖的兩種搜索路徑的遍歷方法。

3)掌握圖的有關(guān)應(yīng)用(最短路徑)。

三實驗原理

1.圖

圖G由兩個集合組成：頂點(結(jié)點)集合V和連接頂點的邊的集合E,集合

E由集合V中的不同的頂點對組成，通常記為6=(V,E)o圖是一種較線性表

和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在圖形結(jié)構(gòu)中，結(jié)點之間的關(guān)系可以是任意的，圖中

任意兩個數(shù)據(jù)元素之間都可能有關(guān)。

圖的抽象數(shù)據(jù)類型定義如下：

ADTGraph/Digraph{

數(shù)據(jù)對象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點集。

數(shù)據(jù)關(guān)系R：R={VR}

對于有向圖VR={<V<span>,w>|v,wiv且P(v,w),<V<span>,

w>表示從V到w的弧，

謂詞P(v,w)定義了弧<V<span>，w>的意義或

信息}

對于無向圖VR={(v,w)|v,wiv且P(v,w),(v,w)表示從v到w

的邊，謂詞P(v,w)定義了邊(v,w)

的意義或信息}

基本操作P：

CreateGraph(&G,V,VR)

返回結(jié)果：V是圖的頂點集，VR是圖中邊或弧集合。按V和VR的定

義構(gòu)造圖G。

DestoryGraph(&G)

初始條件：G是已經(jīng)存在的一個圖。

操作結(jié)果：銷毀圖G。

Exist(G,v,w)

初始條件：G是已經(jīng)存在的一個圖，v、w是兩個頂點。

操作結(jié)果：如果存在邊(v,w)或弧<V<span>，w>,則返回TRUE,

否則返回

FALSEo

Edges(G)

初始條件：G是已經(jīng)存在的一個圖。

操作結(jié)果：返回圖中邊的數(shù)目。

Vertices(G)

初始條件：G是已經(jīng)存在的一個圖。

操作結(jié)果：返回圖中頂點的數(shù)目。

Add(&G,v,w)

初始條件：圖G已存在，V,w是兩個頂點。

操作結(jié)果：如果G是有向圖，則在G中添加一條弧<V<span〉，w>；

如果G是無向圖，則在G中添加一條邊(v,w)o

Delete(&G,v,w)

初始條件：圖G已存在，v,w是兩個頂點。

操作結(jié)果：如果G是有向圖，則在G中刪除一條弧<V<span>,w>；

如果G是無向圖，則在G中刪除一條邊(v,w)o

Degree(G,v)

初始條件：圖G及頂點v已存在。

操作結(jié)果：返回圖G中頂點v的度。

Indegree(G,v)

初始條件：圖G及頂點v已存在。

操作結(jié)果：如果G是有向圖，則返回頂點v的入度；如果G是無向圖，

則返回圖G中頂點v的度。

Outdegree(G,v)

初始條件：圖G及頂點v已存在。

操作結(jié)果：如果G是有向圖，則返回頂點v的出度；如果G是無向圖，

則返回圖G中頂點v的度。

DFSTraverse(G,v,visit())

初始條件：圖G已存在，v是G中的某個頂點，visit是頂點的應(yīng)用函

數(shù)。

操作結(jié)果：從頂點v起深度優(yōu)先遍歷圖G,并對頂點調(diào)用函數(shù)visit一

次且僅一次。一旦visit失敗，則操作失敗。

BFSTraverse(G,v,visit())

初始條件：圖G已存在，v是G中的某個頂點，visit是頂點的應(yīng)用函

數(shù)。

操作結(jié)果：從頂點v起廣度優(yōu)先遍歷圖G并對頂點調(diào)用函數(shù)visit-

次且僅一次。一旦visit失敗，則操作失敗。

}ADTGQph/Digqph

2.圖的存儲結(jié)構(gòu)

(1)鄰接矩陣

一個n個頂點的圖G=(V,E)的鄰接矩陣(AdjacencyMatrix)是一個nxn

矩陣AdjMatrix,AdjMatrix中的每個元素是0或1。假設(shè)圖G中頂點集合:V={L

2,...?n},那么AdjMatrix中的元素定義如下：

AdjMatrix[i]U]=<i-[jf!vml]-->C<!-[endif]-->

<!-[if!vml]-->

<!-[endif]-->

圖的鄰接矩陣存儲結(jié)構(gòu)的C語言描述形式如下:

#defineINFINITYINTMAX

#defineMAX_VERTEX_NUM20

typedefenum{DG=1,AG,DN,AN}GraphKind；〃{有向圖、無向圖；

有向網(wǎng)、無向

網(wǎng)}

typedefstructnode{

VertexTypevextex；〃頂點信息

}Node；

typedefstructarcs{

intadj；//頂點鄰接關(guān)系

...〃該邊或弧的相關(guān)信息指針

}Arcs;

typedefstruct{

Nodenodes[MAX_VERTEX_NUM]；〃頂點集合

Arcsarcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]；〃鄰接矩陣

intvexnum,arcnum；〃頂點數(shù)和弧數(shù)

GraphKindkind;

〃kind取值1、2、3、4分別表示有向圖、無向圖、有向網(wǎng)、無向

網(wǎng)

}Graph;

（2）鄰接表

鄰接表（AdjacencyList）是一種順序存儲與鏈?zhǔn)酱鎯ο嘟Y(jié)合的存儲結(jié)構(gòu)，

順序存儲部分用來保存圖中頂點信息，鏈?zhǔn)酱鎯Σ糠直４鎴D中邊或弧的信息。具

體做法是：圖G被表示為一個數(shù)組或向量v[l],v[2],v[n],每個元素對應(yīng)

圖中一個頂點。每個v[i]存儲頂點%的信息，以及一個指向包含所有依附于頂點

W的邊組成的單鏈表的指針，v[i]稱之為頭結(jié)點。頭結(jié)點結(jié)構(gòu)如下圖所示：

其中data存放與頂點相關(guān)的信息，firstarc是指針；鄰接單鏈表中每個結(jié)點表示

依附于該頂點的一條邊（對于有向圖則是以頂點Vi為尾的弧），稱為邊（?。┙Y(jié)

點，其結(jié)構(gòu)如下圖所示：

info*'

其中adjvex存放依附于該邊的另一個頂點在一維數(shù)組中的序號，對于有向

圖，存放的是該弧結(jié)點所表示的弧的弧頭頂點在一維數(shù)組中的序號；nextarc為

指向下一條邊（或?。┙Y(jié)點的指針；inf。存儲和邊或弧相關(guān)的信息，如權(quán)值等。

圖的鄰接表存儲結(jié)構(gòu)的C語言描述形式如下：

#defineMAXLEN10

typedefstructnode{/*邊結(jié)點結(jié)構(gòu)*/

intadjvex;/*存放與頭結(jié)點相鄰接的頂點在數(shù)組中的

序號*/

intinfo;/*權(quán)值等信息*/

structnode*nextarc;/*指向與頭結(jié)點相鄰接下一個頂點的

表結(jié)點*/

}EdgeNode;

typedefstruct{/*頭結(jié)點結(jié)構(gòu)*/

intid;/*頂點入度*/

/*頂點信息*/

chardata;海端頭結(jié)點對應(yīng)的單鏈表中的表結(jié)

EdgeNode*firstarc;

占*/

八、、/

}VexNode;

typedefstruct{/*鄰接表結(jié)構(gòu)*/

VexNodeadjs[MAXLEN];/*鄰接表的頭結(jié)點集合*/

intvexnum,arcnum;/*頂點數(shù)，邊數(shù)*/

intkind;/*圖的種類*/

}AdjList;

3.圖的遍歷

圖有兩種搜索路徑的遍歷方法：深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷。

圖的深度優(yōu)先搜索(Depth-FirstSearch,DFS)策略是從給定頂點v出發(fā)，

在回溯之前，沿著從v出發(fā)的一條路徑盡可能深入前進(jìn)。其遍歷規(guī)則為：從v出

發(fā)，訪問V的一個未被訪問的鄰接頂點wl,再從wl出發(fā)，訪問wl的一個未被

訪問的鄰接頂點w2,然后從w2出發(fā)，訪問w2的一個未被訪問的鄰接頂點w3,…,

如此下去，直到一個所有鄰接點都被訪問過的頂點為止。然后回溯到尚有鄰接點

未被訪問的頂點，重復(fù)上述過程，直到圖中所有與v有路徑相通的頂點都被訪問

過；此時，若圖中還存在未被訪問過的頂點，則從其中一個未被訪問過的頂點出

發(fā)，重復(fù)上述過程，直到圖中所有頂點都被訪問為止。

圖的廣度優(yōu)先搜索(Broad-FirstSearch,BFS)策略是在訪問給定頂點v之

后，先訪問與V鄰接的所有頂點Wl、W2、…、Wk，然后再依次從Wl、W2、...、

Wk出發(fā)，訪問它們的未被訪問過的鄰接頂點，重復(fù)上述操作，直到圖中所有被

訪問過的頂點的鄰接頂點都被訪問為止。若此時圖中還有未被訪問過的頂點，則

從一個未被訪問過的頂點出發(fā)，重復(fù)上述過程，直到圖中所有的頂點都被訪問過

為止。

4.最短路徑

圖的最短路徑問題有：一是求從一個頂點(源點)到其它各頂點的最短路徑；

二是求每對頂點之間的最短路徑。第一種情況采用迪杰斯特拉算法解決，這是一

個按路徑長度遞增的順序逐步產(chǎn)生最短路徑的算法。第二種情況采用Floyd算法

求解。

(1)Dijkstra算法的實現(xiàn)

設(shè)有向網(wǎng)G=(V,E),它采用鄰接矩陣作為存儲結(jié)構(gòu)。若鄰接矩陣為Cost,

并規(guī)定：

,“頂去點到頂點之間有直接邊，且權(quán)值為Wjj

Cost[i][j]=<0i=j,頂點i與頂點j是同一個頂點

8頂點i和頂點j之間沒有邊

設(shè)立兩個一維數(shù)組S和Distance,其中S存放已經(jīng)找到最短路徑的頂點，它的初

始狀態(tài)為：集合S中只含有起始頂點（源點）。并規(guī)定：

.=10未找到源點到頂點》的最短路徑

S0"11已經(jīng)找到源點到頂點V，的最短路徑

Distance的每個分量Distance。]表示當(dāng)前所找到的從起始頂點v到每個目的頂點

Vi的最短路徑長度。它的初始狀態(tài)為：若從v到Vi有弧，則Distance。]為弧上的

權(quán)值,否則置Distance。]為8,即Distance[i]=Cost[LocateVex（v）][i],LocateVex

用于確定頂點v在G中的位序。

利用Distance的各個分量的值，選取當(dāng)前具有的最短路徑的頂點垮，使得

Distance[j]=min{Distance[i]|ViGV-S}

然后將頂點埼加入集合S中，即令同時對于所有S[i]=0的頂點%,修

改源點到它們可達(dá)的最短路徑為

Distance[i]=min{Distance[i],Distance[j]+Cost[j][i]}

上述過程重復(fù)執(zhí)行n-1次，就可以得到源點到其它頂點的最短路徑值。

（2）Floyd算法的思想

假設(shè)求從頂點％到頂點Vj的最短路徑。如果從頂點Vi到頂點Vj有弧，則從頂

點%到頂點埼存在一條長度為Cost[i][j]的路徑，該路徑不一定是最短路徑，尚

需進(jìn)行n次試探。首先考慮路徑（%,vo,Vj）是否存在（即判斷?。╳,vo）和

（Vo,Vj）是否存在）。如果存在，則比較（Vi，Vo,Vj）和（Vi，Vj）的路徑長度，

然后取長度較短者為頂點%到頂點埼的中間頂點的序號不大于0的最短路徑。

假如在路徑上再增加一個頂點vl,也就是說，如果（％,…，Vi）和（V1，...?

vp分別是當(dāng)前找到的中間頂點的序號不大于0的最短路徑，那么（V,,...,vi,...,

Vj）就有可能是從坐到頂點Vj的中間頂點的序號不大于I的最短路徑。將它和已