數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告圖與景區(qū)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告圖與景區(qū)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告圖與景區(qū)學(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é)期數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告圖與景區(qū)全文共11頁，當(dāng)前為第1頁。數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告圖與景區(qū)全文共11頁，當(dāng)前為第1頁。數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告圖與景區(qū)全文共11頁，當(dāng)前為第2頁。實(shí)驗(yàn)課程名稱:數(shù)據(jù)結(jié)構(gòu)與算法綜合實(shí)驗(yàn)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告圖與景區(qū)全文共11頁，當(dāng)前為第2頁。實(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)康呐c要求目的=掌握圖的定義與圖的存儲(chǔ)結(jié)構(gòu)。=掌握圖的創(chuàng)建方法與圖的應(yīng)用=使用C++語言,定義圖的數(shù)據(jù)結(jié)構(gòu),結(jié)合迭代開發(fā)思路實(shí)現(xiàn)“景區(qū)信息管理系統(tǒng)”。=掌握圖的兩種遍歷方法與應(yīng)用。=使用C++語言與深度優(yōu)先算法實(shí)現(xiàn)“旅游景點(diǎn)導(dǎo)航”功能開發(fā)。=掌握迪杰斯特拉算法與應(yīng)用。=使用C++語言與迪杰斯特拉算法實(shí)現(xiàn)“搜索最短路徑”功能開發(fā)。=理解最小生成樹的概念,掌握普里姆算法與應(yīng)用。=使用C++語言與最小生成樹算法實(shí)現(xiàn)“鋪設(shè)電路規(guī)劃”功能開發(fā)。2、要求=開發(fā)景區(qū)信息管理系統(tǒng),對景區(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ù)迭代,采用迪杰斯特拉算法、普里姆算法,實(shí)現(xiàn)搜索最短路徑與電路鋪設(shè),開發(fā)景區(qū)信息管理系統(tǒng)。數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)=記錄頂點(diǎn)信息的結(jié)構(gòu)體structVex{ intnum;//景點(diǎn)編號(hào) charname[20];//景點(diǎn)名字 chardesc[1024];//景點(diǎn)介紹};=記錄邊的信息的結(jié)構(gòu)體structEdge{ intvex1;//邊的第一個(gè)頂點(diǎn) intvex2;//邊的第二個(gè)頂點(diǎn) intweight;//權(quán)值};=用來保存路徑的鏈表的結(jié)構(gòu)體typedefstructPath{ intvexs[20];//保存一條路徑 Path*next;}*PathList;=CGraph類用來實(shí)現(xiàn)相應(yīng)功能的方法classCGraph{private: intm_aAdjMatrix[20][20];//鄰接矩陣 Vexm_aVexs[20];//頂點(diǎn)信息數(shù)組 intm_nVexNum;//當(dāng)前圖的頂點(diǎn)個(gè)數(shù)public: voidInit(void); boolInsertVex(VexsVex); boolInsertEdge(EdgesEdge); VexGetVex(intnVex); intGetVexnum(void); intFindEdge(intnVex,EdgeaEdge[]); voidDFS(intnVex,boolaVisited[],int&nIndex,PathList&pList); voidDFSTraverse(intnVex,PathList&pList); intFindShortPath(intnVexStart,intnVexEnd,EdgeaPath[]); voidFindMinTree(EdgeaPath[]);};數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告圖與景區(qū)全文共11頁，當(dāng)前為第3頁。2、核心算法設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告圖與景區(qū)全文共11頁，當(dāng)前為第3頁。(1)輸出周邊景點(diǎn)信息Input:操作表號(hào)與景點(diǎn)編號(hào)Output:輸入景點(diǎn)的周邊景點(diǎn)信息Process:intCGraph::FindEdge(intnVex,EdgeaEdge[]){ intk=0; for(inti=0;i<m_nVexNum;i++) { if(m_aAdjMatrix[nVex][i]!=0) { aEdge[k]、vex1=nVex; aEdge[k]、vex2=i; aEdge[k]、weight=m_aAdjMatrix[nVex][i]; k++; } } returnk;//返回邊的條數(shù)}(2)深度優(yōu)先搜索算法實(shí)現(xiàn)旅游景點(diǎn)導(dǎo)航Input:操作表號(hào)與景點(diǎn)編號(hào)Output:從輸入景點(diǎn)出發(fā)走遍整個(gè)景區(qū)的各種路線方案Process:voidCGraph::DFS(intnVex,boolaVisited[],int&nIndex,PathList&pList){ aVisited[nVex]=true;//改為已訪問 pList->vexs[nIndex++]=nVex;//訪問頂點(diǎn) //判斷就是否所有節(jié)點(diǎn)都已訪問過 intnVexNum=0; for(inti=0;i<m_nVexNum;i++) { if(aVisited[i])nVexNum++; } //所有頂點(diǎn)都被訪問過 if(nVexNum==m_nVexNum) { //新增鏈表節(jié)點(diǎn),保存本次遍歷的路徑 pList->next=(PathList)malloc(sizeof(Path)); for(inti=0;i<m_nVexNum;i++) { pList->next->vexs[i]=pList->vexs[i]; } pList=pList->next;數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告圖與景區(qū)全文共11頁，當(dāng)前為第4頁。 pList->next=NULL;數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告圖與景區(qū)全文共11頁，當(dāng)前為第4頁。 } else { //按頂點(diǎn)的存儲(chǔ)順序,查找當(dāng)前頂點(diǎn)相連的的頂點(diǎn) for(inti=0;i<m_nVexNum;i++) { //既沒有遍歷過,又與當(dāng)前頂點(diǎn)相連的頂點(diǎn) if(!aVisited[i]&&(m_aAdjMatrix[nVex][i]>0)) { //以該頂點(diǎn)為起點(diǎn)遍歷剩下的頂點(diǎn) DFS(i,aVisited,nIndex,pList); aVisited[i]=false;//訪問狀態(tài)置空 nIndex--;//回溯 } } }}voidCGraph::DFSTraverse(intnVex,PathList&pList){ intnIndex=0; boolaVisited[MAX_VERTEX_NUM]={false}; DFS(nVex,aVisited,nIndex,pList);} Dijkstra算法搜索最短路徑Input:操作表號(hào)與起始景點(diǎn)編號(hào)Output:從起始頂點(diǎn)到終點(diǎn)的最短路徑Process:intCGraph::FindShortPath(intnVexStart,intnVexEnd,EdgeaPath[]){ intnShortPath[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//保存最短路徑 intnShortDistance[MAX_VERTEX_NUM];//保存最短距離 boolaVisited[MAX_VERTEX_NUM];//判斷某頂點(diǎn)就是否已經(jīng)加入到最短路徑 //初始化 intv; for(v=0;v<m_nVexNum;v++) { aVisited[v]=false; if(m_aAdjMatrix[nVexStart][v]!=0) //初始化該頂點(diǎn)到其她頂點(diǎn)的最短距離,默認(rèn)為兩點(diǎn)間的距離 nShortDistance[v]=m_aAdjMatrix[nVexStart][v]; else //如果頂點(diǎn)i與nVexStart不相連,則最短距離設(shè)為最大值nShortDistance[v]=0x7FFFFFFF;數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告圖與景區(qū)全文共11頁，當(dāng)前為第5頁。 nShortPath[v][0]=nVexStart;//起始點(diǎn)為nVexStart數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告圖與景區(qū)全文共11頁，當(dāng)前為第5頁。 for(intj=1;j<m_nVexNum;j++) { nShortPath[v][j]=-1;//初始化最短路徑 } } //初始化,nVexStart頂點(diǎn)加入到集合中 aVisited[nVexStart]=true; intmin; for(inti=1;i<m_nVexNum;i++) { min=0x7FFFFFFF; boolbAdd=false;//判斷就是否還有頂點(diǎn)可以加入到集合中 for(intj=0;j<m_nVexNum;j++) { if(aVisited[j]==false) { if(nShortDistance[j]<min) { v=j;//j頂點(diǎn)離nVexStart頂點(diǎn)最近 min=nShortDistance[j];//j到nVexStart的最短距離為min bAdd=true; } } }//如果沒有頂點(diǎn)可以加入到集合,則跳出循環(huán) if(bAdd==false) { break; } aVisited[v]=true;//將頂點(diǎn)j加入到集合 nShortPath[v][i]=v;//將頂點(diǎn)j保存到nVexStart到j(luò)的最短路徑里 for(intw=0;w<m_nVexNum;w++) { //將w作為過度頂點(diǎn)計(jì)算nVexStart通過w到每個(gè)頂點(diǎn)的距離 if(aVisited[w]==false&&(min+m_aAdjMatrix[v][w]<nShortDistance[w])&&m_aAdjMatrix[v][w]!=0) { //更新當(dāng)前最短路徑及距離 nShortDistance[w]=min+m_aAdjMatrix[v][w]; for(inti=0;i<m_nVexNum;i++) { //如果通過w到達(dá)頂點(diǎn)i的距離比較短,則將w的最短路徑復(fù)制給i nShortPath[w][i]=nShortPath[v][i]; }數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告圖與景區(qū)全文共11頁，當(dāng)前為第6頁。 }數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告圖與景區(qū)全文共11頁，當(dāng)前為第6頁。 } } intnIndex=0; intnVex1=nVexStart; //將最短路徑保存為邊的結(jié)構(gòu)體數(shù)組 for(inti=1;i<m_nVexNum;i++) { if(nShortPath[nVexEnd][i]!=-1) { aPath[nIndex]、vex1=nVex1; aPath[nIndex]、vex2=nShortPath[nVexEnd][i]; aPath[nIndex]、weight=m_aAdjMatrix[aPath[nIndex]、vex1][aPath[nIndex]、vex2]; nVex1=nShortPath[nVexEnd][i]; nIndex++; } } returnnIndex;}(4)普里姆算法構(gòu)建最小生成樹Input:輸入操作編號(hào)Output:得到最小生成樹的路徑Process:voidCGraph::FindMinTree(EdgeaPath[]){ boolaVisited[MAX_VERTEX_NUM];//判斷某頂點(diǎn)就是否在最小生成樹頂點(diǎn)集合里 for(inti=0;i<MAX_VERTEX_NUM;i++) { aVisited[i]=false; } aVisited[0]=true;//0頂點(diǎn)加入到集合中 intmin; intnVex1,nVex2; for(intk=0;k<m_nVexNum-1;k++) { min=0x7FFFFFFF; for(inti=0;i<m_nVexNum;i++) { if(aVisited[i])//從集合中取一個(gè)頂點(diǎn) { for(intj=0;j<m_nVexNum;j++) { if(!aVisited[j])//從不在集合的頂點(diǎn)中取出一個(gè)頂點(diǎn) {數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告圖與景區(qū)全文共11頁，當(dāng)前為第7頁。 if((m_aAdjMatrix[i][j]<min)&&(m_aAdjMatrix[i][j]!=0))數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告圖與景區(qū)全文共11頁，當(dāng)前為第7頁。 { nVex1=i; nVex2=j; min=m_aAdjMatrix[i][j];//找出最短的邊 } } } } } //保存最短邊的兩個(gè)頂點(diǎn) aPath[k]、vex1=nVex1; aPath[k]、vex2=nVex2; aPath[k]、weight=m_aAdjMatrix[nVex1][nVex2]; //將兩個(gè)頂點(diǎn)加入到集合 aVisited[nVex1]=true; aVisited[nVex2]=true; }}3、測試用例設(shè)計(jì)=使用實(shí)驗(yàn)所要求的圖創(chuàng)建兩個(gè)文本文件,對文件進(jìn)行讀取,觀察其相關(guān)功能的實(shí)現(xiàn)。三、主要儀器設(shè)備及耗材1、安裝了Windows10或其它版本的Windows操作系統(tǒng)的PC機(jī)1臺(tái)2、PC機(jī)系統(tǒng)上安裝了MicrosoftVisualStudio2010開發(fā)環(huán)境第二部分:實(shí)驗(yàn)過程與結(jié)果(可加頁)實(shí)現(xiàn)說明數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告圖與景區(qū)全文共11頁，當(dāng)前為第8頁。使用MircosoftVisualStudio2010開發(fā)工具,創(chuàng)建一個(gè)空的控制臺(tái)工程。利用圖的存儲(chǔ)結(jié)構(gòu)來保存景區(qū)景點(diǎn)圖,使用C++語言開發(fā)景區(qū)信息管理系統(tǒng),工程名為GraphCPro。數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告圖與景區(qū)全文共11頁，當(dāng)前為第8頁。添加Graph、h文件,用來定義圖的數(shù)據(jù)結(jié)構(gòu),實(shí)現(xiàn)圖的相關(guān)操作。添加Tourism、h文件,用來實(shí)現(xiàn)景區(qū)信息管理系統(tǒng)的相關(guān)功能。Tourism、h存放與Tourism、cpp相關(guān)函數(shù)的數(shù)據(jù)類型的定義,函數(shù)原型的聲明等。添加Main、cpp文