《(完整word版)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告圖與景區(qū)(word文檔良心出品).doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《(完整word版)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告圖與景區(qū)(word文檔良心出品).doc（11頁珍藏版）》請(qǐng)?jiān)趨R文網(wǎng)上搜索。

1、學(xué)生學(xué)號(hào) 實(shí)驗(yàn)課成績學(xué) 生 實(shí) 驗(yàn) 報(bào) 告 書實(shí)驗(yàn)課程名稱數(shù)據(jù)結(jié)構(gòu)與算法綜合實(shí)驗(yàn)開課學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院指導(dǎo)教師姓名學(xué)生姓名學(xué)生專業(yè)班級(jí)2017-2018學(xué)年第2學(xué)期10實(shí)驗(yàn)課程名稱： 數(shù)據(jù)結(jié)構(gòu)與算法綜合實(shí)驗(yàn) 實(shí)驗(yàn)項(xiàng)目名稱圖與景區(qū)信息管理系統(tǒng)實(shí)踐報(bào)告成績實(shí)驗(yàn)者專業(yè)班級(jí)組別同組者 完成日期2018年5月23日第一部分：實(shí)驗(yàn)分析與設(shè)計(jì)（可加頁）一、 實(shí)驗(yàn)?zāi)康暮鸵?. 目的=掌握?qǐng)D的定義和圖的存儲(chǔ)結(jié)構(gòu)。=掌握?qǐng)D的創(chuàng)建方法和圖的應(yīng)用=使用C+語言，定義圖的數(shù)據(jù)結(jié)構(gòu)，結(jié)合迭代開發(fā)思路實(shí)現(xiàn)“景區(qū)信息管理系統(tǒng)”。=掌握?qǐng)D的兩種遍歷方法和應(yīng)用。=使用C+語言和深度優(yōu)先算法實(shí)現(xiàn)“旅游景點(diǎn)導(dǎo)航”功能開發(fā)。=

2、掌握迪杰斯特拉算法和應(yīng)用。=使用C+語言和迪杰斯特拉算法實(shí)現(xiàn)“搜索最短路徑”功能開發(fā)。=理解最小生成樹的概念，掌握普里姆算法和應(yīng)用。=使用C+語言和最小生成樹算法實(shí)現(xiàn)“鋪設(shè)電路規(guī)劃”功能開發(fā)。2.要求=開發(fā)景區(qū)信息管理系統(tǒng)，對(duì)景區(qū)的信息進(jìn)行管理。=使用圖的數(shù)據(jù)結(jié)構(gòu)來保存景區(qū)景點(diǎn)信息，為用戶提供創(chuàng)建圖、查詢景點(diǎn)信息、旅 游景點(diǎn)導(dǎo)航、搜索最短路徑、鋪設(shè)電路規(guī)劃等功能。二、 分析與設(shè)計(jì)(1) 創(chuàng)建工程讀取文件信息，創(chuàng)建圖，輸出周邊景點(diǎn)信息讀取景區(qū)信息文件，采用圖的存儲(chǔ)結(jié)構(gòu)，創(chuàng)建景區(qū)景點(diǎn)圖，查詢景點(diǎn)信息。(2)迭代開發(fā)，進(jìn)行深度優(yōu)先搜索，實(shí)現(xiàn)旅游景點(diǎn)導(dǎo)航。(3)繼續(xù)迭代，采用迪杰斯特拉算法、普里姆算法

3、，實(shí)現(xiàn)搜索最短路徑和電路鋪 設(shè)，開發(fā)景區(qū)信息管理系統(tǒng)。1. 數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)=記錄頂點(diǎn)信息的結(jié)構(gòu)體struct Vexint num;/景點(diǎn)編號(hào)char name20;/景點(diǎn)名字char desc1024;/景點(diǎn)介紹;=記錄邊的信息的結(jié)構(gòu)體struct Edgeint vex1;/邊的第一個(gè)頂點(diǎn)int vex2;/邊的第二個(gè)頂點(diǎn)int weight;/權(quán)值;=用來保存路徑的鏈表的結(jié)構(gòu)體typedef struct Pathint vexs20;/保存一條路徑Path *next;*PathList;=CGraph類用來實(shí)現(xiàn)相應(yīng)功能的方法class CGraphprivate:int m_aAdj

4、Matrix2020;/鄰接矩陣Vex m_aVexs20;/頂點(diǎn)信息數(shù)組int m_nVexNum;/當(dāng)前圖的頂點(diǎn)個(gè)數(shù)public:void Init(void);bool InsertVex(Vex sVex);bool InsertEdge(Edge sEdge);Vex GetVex(int nVex);int GetVexnum(void);int FindEdge(int nVex,Edge aEdge);void DFS(int nVex,bool aVisited,int &nIndex,PathList &pList);void DFSTraverse(int nVex,Pa

5、thList &pList);int FindShortPath(int nVexStart,int nVexEnd,Edge aPath);void FindMinTree(Edge aPath);2.核心算法設(shè)計(jì)（1）輸出周邊景點(diǎn)信息Input:操作表號(hào)與景點(diǎn)編號(hào)Output:輸入景點(diǎn)的周邊景點(diǎn)信息Process:int CGraph:FindEdge(int nVex,Edge aEdge)int k=0;for(int i=0;ivexsnIndex+=nVex;/訪問頂點(diǎn)/判斷是否所有節(jié)點(diǎn)都已訪問過int nVexNum=0;for(int i=0;inext=(PathList)m

6、alloc(sizeof(Path);for(int i=0;inext-vexsi=pList-vexsi;pList=pList-next;pList-next=NULL;else/按頂點(diǎn)的存儲(chǔ)順序，查找當(dāng)前頂點(diǎn)相連的的頂點(diǎn)for(int i=0;i0)/以該頂點(diǎn)為起點(diǎn)遍歷剩下的頂點(diǎn)DFS(i,aVisited,nIndex,pList);aVisitedi=false;/訪問狀態(tài)置空nIndex-;/回溯void CGraph:DFSTraverse(int nVex,PathList &pList)int nIndex=0;bool aVisitedMAX_VERTEX_NUM=fal

7、se;DFS(nVex,aVisited,nIndex,pList);（3） Dijkstra算法搜索最短路徑Input: 操作表號(hào)與起始景點(diǎn)編號(hào)Output: 從起始頂點(diǎn)到終點(diǎn)的最短路徑Process:int CGraph:FindShortPath(int nVexStart,int nVexEnd,Edge aPath)int nShortPathMAX_VERTEX_NUMMAX_VERTEX_NUM;/保存最短路徑int nShortDistanceMAX_VERTEX_NUM;/保存最短距離bool aVisitedMAX_VERTEX_NUM;/判斷某頂點(diǎn)是否已經(jīng)加入到最短路徑/

8、初始化int v;for(v=0;vm_nVexNum;v+)aVisitedv=false;if(m_aAdjMatrixnVexStartv!=0)/初始化該頂點(diǎn)到其他頂點(diǎn)的最短距離，默認(rèn)為兩點(diǎn)間的距離nShortDistancev=m_aAdjMatrixnVexStartv;else/如果頂點(diǎn)i和nVexStart不相連，則最短距離設(shè)為最大值 nShortDistancev=0x7FFFFFFF;nShortPathv0=nVexStart;/起始點(diǎn)為nVexStartfor(int j=1;jm_nVexNum;j+)nShortPathvj=-1;/初始化最短路徑/初始化，nVex

9、Start頂點(diǎn)加入到集合中aVisitednVexStart=true;int min;for(int i=1;im_nVexNum;i+)min=0x7FFFFFFF;bool bAdd=false;/判斷是否還有頂點(diǎn)可以加入到集合中for(int j=0;jm_nVexNum;j+)if(aVisitedj=false)if(nShortDistancejmin)v=j;/j頂點(diǎn)離nVexStart頂點(diǎn)最近min=nShortDistancej;/j到nVexStart的最短距離為minbAdd=true;/如果沒有頂點(diǎn)可以加入到集合，則跳出循環(huán)if(bAdd=false)break;aV

10、isitedv=true;/將頂點(diǎn)j加入到集合nShortPathvi=v;/將頂點(diǎn)j保存到nVexStart到j(luò)的最短路徑里for(int w=0;wm_nVexNum;w+)/將w作為過度頂點(diǎn)計(jì)算nVexStart通過w到每個(gè)頂點(diǎn)的距離if(aVisitedw=false&(min+m_aAdjMatrixvwnShortDistancew)&m_aAdjMatrixvw!=0)/更新當(dāng)前最短路徑及距離nShortDistancew=min+m_aAdjMatrixvw;for(int i=0;im_nVexNum;i+)/如果通過w到達(dá)頂點(diǎn)i的距離比較短，則將w的最短路徑復(fù)制給inSho

11、rtPathwi=nShortPathvi;int nIndex=0; int nVex1=nVexStart;/將最短路徑保存為邊的結(jié)構(gòu)體數(shù)組for(int i=1;im_nVexNum;i+)if(nShortPathnVexEndi!=-1)aPathnIndex.vex1=nVex1;aPathnIndex.vex2=nShortPathnVexEndi;aPathnIndex.weight=m_aAdjMatrixaPathnIndex.vex1aPathnIndex.vex2;nVex1=nShortPathnVexEndi;nIndex+;return nIndex;（4）普里姆

12、算法構(gòu)建最小生成樹Input:輸入操作編號(hào)Output:得到最小生成樹的路徑Process:void CGraph:FindMinTree(Edge aPath)bool aVisitedMAX_VERTEX_NUM;/判斷某頂點(diǎn)是否在最小生成樹頂點(diǎn)集合里for(int i=0;iMAX_VERTEX_NUM;i+)aVisitedi=false;aVisited0=true;/0頂點(diǎn)加入到集合中int min;int nVex1,nVex2;for(int k=0;km_nVexNum-1;k+)min=0x7FFFFFFF;for(int i=0;im_nVexNum;i+) if(aVi

13、sitedi)/從集合中取一個(gè)頂點(diǎn) for(int j=0;jm_nVexNum;j+) if(!aVisitedj)/從不在集合的頂點(diǎn)中取出一個(gè)頂點(diǎn) if(m_aAdjMatrixijmin)&(m_aAdjMatrixij!=0) nVex1=i; nVex2=j; min=m_aAdjMatrixij;/找出最短的邊 /保存最短邊的兩個(gè)頂點(diǎn)aPathk.vex1=nVex1;aPathk.vex2=nVex2;aPathk.weight=m_aAdjMatrixnVex1nVex2;/將兩個(gè)頂點(diǎn)加入到集合aVisitednVex1=true;aVisitednVex2=true;3.測試

14、用例設(shè)計(jì)=使用實(shí)驗(yàn)所要求的圖創(chuàng)建兩個(gè)文本文件，對(duì)文件進(jìn)行讀取，觀察其相關(guān)功能的實(shí)現(xiàn)。三、主要儀器設(shè)備及耗材1.安裝了Windows 10或其它版本的Windows操作系統(tǒng)的PC機(jī)1臺(tái)2.PC機(jī)系統(tǒng)上安裝了Microsoft Visual Studio 2010開發(fā)環(huán)境第二部分：實(shí)驗(yàn)過程和結(jié)果（可加頁）一、 實(shí)現(xiàn)說明使用Mircosoft Visual Studio 2010開發(fā)工具，創(chuàng)建一個(gè)空的控制臺(tái)工程。利用圖的存儲(chǔ)結(jié)構(gòu)來保存景區(qū)景點(diǎn)圖，使用C+語言開發(fā)景區(qū)信息管理系統(tǒng)，工程名為GraphCPro。（1） 添加Graph.h文件，用來定義圖的數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)圖的相關(guān)操作。（2） 添加Touri

15、sm.h文件，用來實(shí)現(xiàn)景區(qū)信息管理系統(tǒng)的相關(guān)功能。Tourism.h存放與Tourism.cpp相關(guān)函數(shù)的數(shù)據(jù)類型的定義，函數(shù)原型的聲明等。（3） 添加Main.cpp文件，在文件中創(chuàng)建程序入口函數(shù)int main（void）。調(diào)用Tourism.h中的相關(guān)函數(shù)實(shí)現(xiàn)相應(yīng)功能。二、 調(diào)試說明（調(diào)試手段、過程及結(jié)果分析）調(diào)試的主要內(nèi)容為編寫程序的語法正確性與否，程序邏輯的正確性與否。調(diào)試手段主要采用了Mircosoft Visual Studio 2010集成開發(fā)環(huán)境中的“開始執(zhí)行（Ctrl+F5）”運(yùn)行并測試，和F11“逐語句調(diào)試”、F12“逐過程調(diào)試”、F9“切換斷點(diǎn)”、ctrl+B“新建斷點(diǎn)

16、”等。三、 軟件測試（測試效果.界面、綜合分析和結(jié)論）1 測試效果界面2綜合分析和結(jié)論由于上一次的哈夫曼樹沒有寫很好所以我回去以后有好好學(xué)習(xí)了一下數(shù)據(jù)結(jié)構(gòu)，本次實(shí)驗(yàn)也比第一次有了經(jīng)驗(yàn)了，通過和視頻的學(xué)習(xí)我本次把實(shí)驗(yàn)全都做出來了。但在實(shí)現(xiàn)的過程中對(duì)算法的理解還不夠透徹，有待提高。第三部分：實(shí)驗(yàn)小結(jié)、收獲與體會(huì)通過本次試驗(yàn)，我進(jìn)一步掌握了有關(guān)圖的相關(guān)算法，也對(duì)數(shù)據(jù)結(jié)構(gòu)在實(shí)際編程的應(yīng)用中有了進(jìn)一步的了解，也對(duì)深度優(yōu)先搜索、迪杰斯特拉、普里姆算法有了進(jìn)一步的了解。同時(shí)，我也發(fā)現(xiàn)自己對(duì)于圖的有關(guān)知識(shí)掌握的還遠(yuǎn)遠(yuǎn)不夠，對(duì)于一些算法還不能熟練應(yīng)用于編程中，所以，在以后的學(xué)習(xí)中，要多編程，以提高自己的動(dòng)手編程能力。