數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告四

1、甘肅政法學(xué)院本科生實(shí)驗(yàn)報(bào)告（）姓名:學(xué)院:專(zhuān)業(yè):班級(jí):13級(jí)實(shí)驗(yàn)課程名稱(chēng):數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)日期:2014年5月30日指導(dǎo)教師及職稱(chēng):實(shí)驗(yàn)成績(jī):開(kāi)課時(shí)間： 2013-2014學(xué)年 第二學(xué)期甘肅政法學(xué)院實(shí)驗(yàn)管理中心印制實(shí)驗(yàn)題目樹(shù)形結(jié)構(gòu)小組合作否姓名班級(jí)學(xué) 號(hào)一、實(shí)驗(yàn)?zāi)康?.1實(shí)現(xiàn)圖的鄰接矩陣和鄰接表儲(chǔ)存8.2實(shí)現(xiàn)圖的遍歷算法8.3求所有深度優(yōu)先遍歷序列8.4用圖搜索方法求解迷宮問(wèn)題8.5求有向圖的簡(jiǎn)單路徑8.6求無(wú)向圖的深度優(yōu)先生成樹(shù)和廣度優(yōu)先生成樹(shù)8.7用普利姆算法求最小生成樹(shù)8.8采用克魯斯卡爾算法求最小生成樹(shù)8.9采用狄克斯特拉算法求有向帶權(quán)圖的最短路徑8.10采用弗洛伊德算法求有向帶權(quán)圖的最短

2、路徑二實(shí)驗(yàn)環(huán)境安裝了Windows7操作系統(tǒng)，并且安裝了Microsoft Visual C+ 6.0。三、實(shí)驗(yàn)內(nèi)容與步驟1、安裝Microsoft Visual C+ 6.0。2打開(kāi)Microsoft Visual C+ 6.0四實(shí)驗(yàn)過(guò)程：8.1實(shí)現(xiàn)圖的鄰接矩陣和鄰接表儲(chǔ)存編寫(xiě)一個(gè)程序algo8-1，實(shí)現(xiàn)不帶權(quán)圖和帶權(quán)圖的鄰接矩陣與鄰接表的相互轉(zhuǎn)化算法、輸出鄰接矩陣與鄰接表的運(yùn)算并在此基礎(chǔ)上設(shè)計(jì)一個(gè)主程序完成如下功能：（1） 建立如圖所示的有向G鄰接矩陣，并輸出之；（2） 由有向圖G的鄰接矩陣產(chǎn)生鄰接表，并輸出之；（3） 再由（2）的鄰接表產(chǎn)生相應(yīng)的鄰接矩陣，并輸出之新建工程選擇“Hello

3、，world！程序”選擇Fileview復(fù)制algo8-1和Graph到工程文件中。把主文件大開(kāi)，用exp8-1的內(nèi)容覆蓋到主文件由于main（）函數(shù)被重復(fù)定義所以需要備注，把a(bǔ)lgo8-1中主函數(shù)備注掉，并且手動(dòng)引入#include“algo8-1.cpp”。運(yùn)行程序，如下圖：輸入代碼如下：8.2實(shí)現(xiàn)圖的遍歷算法編寫(xiě)一個(gè)程序algo8-2，實(shí)現(xiàn)實(shí)現(xiàn)圖的遍歷算法并在此基礎(chǔ)上設(shè)計(jì)一個(gè)exp8-2.cpp程序完成如下功能：（1） 輸出有向圖G從丁丁點(diǎn)0開(kāi)始的深度優(yōu)先遍歷序列(遞歸算法)（2） 輸出有向圖G從丁丁點(diǎn)0開(kāi)始的深度優(yōu)先遍歷序列(非遞歸算法)（3） 輸出有向圖G從丁丁點(diǎn)0開(kāi)始的廣度優(yōu)先遍歷

4、序列（4） 新建工程選擇“Hello，world！程序”選擇Fileview復(fù)制algo8-1和algo8-2和Graph到工程文件中。把主文件大開(kāi)，用exp8-2的內(nèi)容覆蓋到主文件由于main（）函數(shù)被重復(fù)定義所以需要備注，把a(bǔ)lgo8-1中主函數(shù)備注掉，并且手動(dòng)引入#include“algo8-1.cpp” 和#include“algo8-2.cpp”。運(yùn)行程序，如下圖：輸入代碼如下：8.3求所有深度優(yōu)先遍歷序列編寫(xiě)一個(gè)程序algo8-3，采用鄰接表存儲(chǔ)圖。新建工程選擇“Hello，world！程序”選擇Fileview復(fù)制algo8-1和Graph到工程文件中。把主文件大開(kāi)，用exp8-

5、3的內(nèi)容覆蓋到主文件由于main（）函數(shù)被重復(fù)定義所以需要備注，把a(bǔ)lgo8-1中主函數(shù)備注掉，并且手動(dòng)引入#include“algo8-1.cpp” 。運(yùn)行程序，如下圖：輸入程序如下：8.4用圖搜索方法求解迷宮問(wèn)題設(shè)計(jì)一個(gè)程序，實(shí)現(xiàn)如下功能：（1）建立教程所示迷宮對(duì)應(yīng)的鄰接表表示。（2）采用深度優(yōu)先遍歷輸出所有迷宮的路徑。 新建工程選擇“Hello，world！程序”選擇Fileview復(fù)制algo8-1和Graph到工程文件中。把主文件大開(kāi)，用exp8-4的內(nèi)容覆蓋到主文件由于main（）函數(shù)被重復(fù)定義所以需要備注，把a(bǔ)lgo8-1中主函數(shù)備注掉，并且手動(dòng)引入#include“algo8-

6、1.cpp”運(yùn)行程序，如下圖：輸入程序如下：8.5求有向圖的簡(jiǎn)單路徑編寫(xiě)一個(gè)程序exp8-5，實(shí)現(xiàn)如下功能： （1）輸出所示的有線圖G從頂點(diǎn)5到頂點(diǎn)2的所有路徑： （2）輸出所示的有線圖G從頂點(diǎn)5到頂點(diǎn)2的所有長(zhǎng)度為3的路徑： （3）輸出所示的有線圖G從頂點(diǎn)5到頂點(diǎn)2的最短路徑： 新建工程選擇“Hello，world！程序”選擇Fileview復(fù)制algo8-1和Graph到工程文件中。把主文件大開(kāi)，用exp8-5的內(nèi)容覆蓋到主文件由于main（）函數(shù)被重復(fù)定義所以需要備注，把a(bǔ)lgo8-1中主函數(shù)備注掉，并且手動(dòng)引入#include“algo8-1.cpp” 運(yùn)行程序，如下圖：輸入代碼如下：

7、8.6求無(wú)向圖的深度優(yōu)先生成樹(shù)和廣度優(yōu)先生成樹(shù)編寫(xiě)一個(gè)程序algo8-2，輸出所示的有線圖G從頂點(diǎn)3出發(fā)深度優(yōu)先生成樹(shù)和廣度優(yōu)先生成樹(shù)。新建工程選擇“Hello，world！程序”選擇Fileview復(fù)制algo8-1和 Graph到工程文件中。把主文件大開(kāi)，用exp8-6的內(nèi)容覆蓋到主文件由于main（）函數(shù)被重復(fù)定義所以需要備注，把a(bǔ)lgo8-1中主函數(shù)備注掉，并且手動(dòng)引入#include“algo8-1.cpp” 程運(yùn)行序，如下圖：輸入程序如下：8.7用普利姆算法求最小生成樹(shù)編寫(xiě)一個(gè)程序設(shè)計(jì)一個(gè)算法對(duì)所示無(wú)限帶權(quán)圖G,采用普利姆算法輸出從頂點(diǎn)0出發(fā)的最小生成樹(shù)新建工程選擇“Hello，w

8、orld！程序”選擇Fileview復(fù)制algo8-1和Graph到工程文件中。把主文件大開(kāi)，用exp8-7的內(nèi)容覆蓋到主文件由于main（）函數(shù)被重復(fù)定義所以需要備注，把a(bǔ)lgo8-1中主函數(shù)備注掉，并且手動(dòng)引入#include“algo8-1.cpp” 。運(yùn)行程序，如下圖：輸入程序如下：8.8采用克魯斯卡爾算法求最小生成樹(shù)編寫(xiě)一個(gè)程序所示無(wú)限帶權(quán)圖G,采用克魯斯卡爾算法輸出從頂點(diǎn)0出發(fā)的最小生成樹(shù)新建工程選擇“Hello，world！程序”選擇Fileview復(fù)制algo8-1和Graph到工程文件中。把主文件大開(kāi)，用exp8-8的內(nèi)容覆蓋到主文件由于main（）函數(shù)被重復(fù)定義所以需要備注

9、，把a(bǔ)lgo8-1中主函數(shù)備注掉，并且手動(dòng)引入#include“algo8-1.cpp”運(yùn)行程序，如下圖：輸入程序如下：8.9采用狄克斯特拉算法求有向帶權(quán)圖的最短路徑編寫(xiě)一個(gè)程對(duì)所示無(wú)限帶權(quán)圖G,采用克魯斯卡爾算法輸出從頂點(diǎn)0的最短路徑的長(zhǎng)度和最短路徑。新建工程選擇“Hello，world！程序”選擇Fileview復(fù)制algo8-1和Graph到工程文件中。把主文件大開(kāi)，用exp8-9的內(nèi)容覆蓋到主文件由于main（）函數(shù)被重復(fù)定義所以需要備注，把a(bǔ)lgo8-1中主函數(shù)備注掉，并且手動(dòng)引入#include“algo8-1.cpp” 運(yùn)行程序，如下圖：輸入程序如下：8.10采用弗洛伊德算法求有向帶權(quán)圖的最短路徑編寫(xiě)一個(gè)程序?qū)λ緹o(wú)限帶權(quán)圖G,采用弗洛伊德算法輸出從頂點(diǎn)0的最短路徑的長(zhǎng)度和最短路徑。新建工程選擇“Hello，world！程序”選擇Fileview復(fù)制algo8-1和Graph到工程文件中。把主文件大開(kāi)，用exp8-10的內(nèi)容覆蓋到主文件。由于main（）函數(shù)被重復(fù)定義所以需要備注，把a(bǔ)lgo8-1中主函數(shù)備注掉，并且手動(dòng)引入#include“algo8-1.cpp” 運(yùn)行程序，如下圖：輸入程序如下：五、實(shí)驗(yàn)故障在實(shí)驗(yàn)一中就出現(xiàn)了問(wèn)題，始終調(diào)試不出來(lái)。顯示錯(cuò)誤為：后來(lái)經(jīng)過(guò)反反復(fù)復(fù)的調(diào)試才發(fā)現(xiàn)是我沒(méi)把graph添加到