數(shù)據(jù)結(jié)構(gòu)實驗報告圖與景區(qū)

1、WORD格式學(xué)生學(xué)號實驗課成績學(xué)生實驗報告書實驗課程名稱數(shù)據(jù)構(gòu)造與算法綜合實驗開課學(xué)院計算機科學(xué)與技術(shù)學(xué)院指導(dǎo)教師*學(xué)生*學(xué)生專業(yè)班級2021-2021學(xué)年第2學(xué)期專業(yè)資料整理WORD格式1專業(yè)資料整理WORD格式實驗課程名稱：數(shù)據(jù)構(gòu)造與算法綜合實驗實驗工程名稱圖與景區(qū)信息管理系統(tǒng)實踐報告成績實驗者專業(yè)班級組別同組者完成日期2021年 5月 23 日第一局部：實驗分析與設(shè)計可加頁一、實驗?zāi)康暮鸵?. 目的掌握圖的定義和圖的存儲構(gòu)造。掌握圖的創(chuàng)立方法和圖的應(yīng)用使用 C+語言，定義圖的數(shù)據(jù)構(gòu)造， 結(jié)合迭代開發(fā)思路實現(xiàn)“景區(qū)信息管理系統(tǒng) 。掌握圖的兩種遍歷方法和應(yīng)用。使用 C+語言和深度優(yōu)先算法實

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

3、拉算法、普里姆算法，實現(xiàn)搜索最短路徑和電路鋪設(shè)，開發(fā)景區(qū)信息管理系統(tǒng)。專業(yè)資料整理WORD格式1專業(yè)資料整理WORD格式1. 數(shù)據(jù)構(gòu)造的設(shè)計記錄頂點信息的構(gòu)造體structVexintnum; / 景點編號char name20;/ 景點名字char desc1024;/ 景點介紹;記錄邊的信息的構(gòu)造體structEdgeintvex1; / 邊的第一個頂點intvex2; / 邊的第二個頂點intweight;/ 權(quán)值;用來保存路徑的鏈表的構(gòu)造體typedefstructPathintvexs20;/ 保存一條路徑Path *next;*PathList;CGraph類用來實現(xiàn)相應(yīng)功能的方法

4、classCGraphprivate:intm_aAdjMatrix2020;/ 鄰接矩陣Vex m_aVexs20;/ 頂點信息數(shù)組intm_nVexNum;/ 當前圖的頂點個數(shù)public:voidInit( void );bool InsertVex(Vex sVex);bool InsertEdge(Edge sEdge);Vex GetVex( int nVex);intGetVexnum( void );intFindEdge(intnVex,Edge aEdge);voidDFS(intnVex, boolaVisited,int &nIndex,PathList &pList)

5、;voidDFSTraverse(int nVex,PathList &pList);intFindShortPath(intnVexStart, intnVexEnd,Edge aPath);voidFindMinTree(Edge aPath);專業(yè)資料整理WORD格式2專業(yè)資料整理WORD格式2. 核心算法設(shè)計（ 1輸出周邊景點信息 Input: 操作表號與景點編號 Output: 輸入景點的周邊景點信息Process:intCGraph:FindEdge(intnVex,Edge aEdge)intk=0;for ( inti=0;ivexsnIndex+=nVex;/ 訪問頂點/ 判

6、斷是否所有節(jié)點都已訪問過intnVexNum=0;for ( inti=0;inext=(PathList)malloc(sizeof (Path);for ( inti=0;inext-vexsi=pList-vexsi;專業(yè)資料整理WORD格式3專業(yè)資料整理WORD格式pList=pList-next;pList-next=NULL;else/ 按頂點的存儲順序，查找當前頂點相連的的頂點for ( inti=0;i0)/ 以該頂點為起點遍歷剩下的頂點DFS(i,aVisited,nIndex,pList);aVisitedi=false ; / 訪問狀態(tài)置空nIndex-;/ 回溯void

7、 CGraph:DFSTraverse(intnVex,PathList &pList)intnIndex=0;bool aVisitedMAX_VERTEX_NUM=false ;DFS(nVex,aVisited,nIndex,pList);（ 3 Dijkstra 算法搜索最短路徑Input: 操作表號與起始景點編號Output: 從起始頂點到終點的最短路徑Process:intCGraph:FindShortPath(intnVexStart,intnVexEnd,Edge aPath)int nShortPathMAX_VERTEX_NUMMAX_VERTEX_NUM;/ 保存最短路

8、徑 int nShortDistanceMAX_VERTEX_NUM;/ 保存最短距離bool aVisitedMAX_VERTEX_NUM;/ 判斷某頂點是否已經(jīng)參加到最短路徑/ 初始化intv;for (v=0;vm_nVexNum;v+)aVisitedv=false ;if (m_aAdjMatrixnVexStartv!=0)/ 初始化該頂點到其他頂點的最短距離，默認為兩點間的距離nShortDistancev=m_aAdjMatrixnVexStartv;專業(yè)資料整理WORD格式4專業(yè)資料整理WORD格式else/ 如果頂點 i 和 nVexStart 不相連，那么最短距離設(shè)為最大

9、值nShortDistancev=0x7FFFFFFF;nShortPathv0=nVexStart;/ 起始點為 nVexStartfor ( intj=1;jm_nVexNum;j+)nShortPathvj=-1;/ 初始化最短路徑/ 初始化， nVexStart 頂點參加到集合中aVisitednVexStart=true ;intmin;for ( inti=1;im_nVexNum;i+)min=0x7FFFFFFF;bool bAdd=false ; / 判斷是否還有頂點可以參加到集合中for ( intj=0;jm_nVexNum;j+)if (aVisitedj=false

10、)if (nShortDistancejmin)v=j; /j頂點離 nVexStart 頂點最近min=nShortDistancej;/j到 nVexStart 的最短距離為 minbAdd=true ; / 如果沒有頂點可以參加到集合，那么跳出循環(huán)if (bAdd=false )break ;aVisitedv=true ; / 將頂點 j 參加到集合nShortPathvi=v;/ 將頂點 j 保存到 nVexStart 到j(luò) 的最短路徑里for ( intw=0;wm_nVexNum;w+)/ 將w作為過度頂點計算 nVexStart 通過 w到每個頂點的距離if (aVisited

11、w=false &(min+m_aAdjMatrixvwnShortDistancew)&m_aAdjMatrixvw!=0)/ 更新當前最短路徑及距離nShortDistancew=min+m_aAdjMatrixvw;for ( inti=0;im_nVexNum;i+)專業(yè)資料整理WORD格式5專業(yè)資料整理WORD格式/ 如果通過 w到達頂點 i 的距離比較短，那么將 w的最短路徑復(fù)制給 i nShortPathwi=nShortPathvi;intnIndex=0;intnVex1=nVexStart;/ 將最短路徑保存為邊的構(gòu)造體數(shù)組for ( inti=1;im_nVexNum;i

12、+)if (nShortPathnVexEndi!=-1)aPathnIndex.vex1=nVex1;aPathnIndex.vex2=nShortPathnVexEndi;aPathnIndex.weight=m_aAdjMatrixaPathnIndex.vex1aPathnIndex.vex2; nVex1=nShortPathnVexEndi;nIndex+;returnnIndex;（ 4普里姆算法構(gòu)建最小生成樹Input: 輸入操作編號Output: 得到最小生成樹的路徑Process:void CGraph:FindMinTree(Edge aPath)bool aVisite

13、dMAX_VERTEX_NUM;/ 判斷某頂點是否在最小生成樹頂點集合里 for ( int i=0;iMAX_VERTEX_NUM;i+)aVisitedi=false ;aVisited0=true ; /0 頂點參加到集合中intmin;intnVex1,nVex2;for ( intk=0;km_nVexNum-1;k+)min=0x7FFFFFFF;for ( inti=0;im_nVexNum;i+)if (aVisitedi)/ 從集合中取一個頂點專業(yè)資料整理WORD格式6專業(yè)資料整理WORD格式for ( intj=0;jm_nVexNum;j+)if (!aVisitedj)

14、/ 從不在集合的頂點中取出一個頂點if (m_aAdjMatrixijmin)&(m_aAdjMatrixij!=0)nVex1=i;nVex2=j;min=m_aAdjMatrixij;/ 找出最短的邊/ 保存最短邊的兩個頂點aPathk.vex1=nVex1;aPathk.vex2=nVex2;aPathk.weight=m_aAdjMatrixnVex1nVex2;/ 將兩個頂點參加到集合aVisitednVex1=true ;aVisitednVex2=true ;3. 測試用例設(shè)計使用實驗所要求的圖創(chuàng)立兩個文本文件，對文件進展讀取，觀察其相關(guān)功能的實現(xiàn)。三、主要儀器設(shè)備及耗材1. 安

15、裝了 Windows 10 或其它版本的Windows操作系統(tǒng)的 PC機 1 臺2.PC 機系統(tǒng)上安裝了 Microsoft Visual Studio 2021開發(fā)環(huán)境專業(yè)資料整理WORD格式7專業(yè)資料整理WORD格式第二局部：實驗過程和結(jié)果可加頁一、實現(xiàn)說明使用 Mircosoft Visual Studio 2021開發(fā)工具，創(chuàng)立一個空的控制臺工程。利用圖的存儲構(gòu)造來保存景區(qū)景點圖，使用C+語言開發(fā)景區(qū)信息管理系統(tǒng)，工程名為 GraphCPro。1添加 Graph.h 文件，用來定義圖的數(shù)據(jù)構(gòu)造，實現(xiàn)圖的相關(guān)操作。2添加 Tourism.h 文件，用來實現(xiàn)景區(qū)信息管理系統(tǒng)的相關(guān)功能。 T

16、ourism.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ù)實現(xiàn)相應(yīng)功能。二、調(diào)試說明調(diào)試手段、過程及結(jié)果分析調(diào)試的主要內(nèi)容為編寫程序的語法正確性與否，程序邏輯的正確性與否。調(diào)試手段主要采用了 Mircosoft Visual Studio 2021集成開發(fā)環(huán)境中的“開場執(zhí)行 Ctrl+F5 運行并測試，和 F11“逐語句調(diào)試、 F12“逐過程調(diào)試、F9“切換斷點、 ctrl+B “新建斷點等。三、軟件測試測試效果 . 界面、綜合分析和結(jié)論1測試效果界面專業(yè)資料整理WORD格式8專業(yè)資料整理WORD格式9專業(yè)資料整理WORD格式2綜合分析和結(jié)論由于上一次的哈夫曼樹沒有寫很好所以我回去以后有好