實驗報告開課學院及實驗室：年月日學院年級、專業(yè)、班姓名學號實驗課程名稱數(shù)據(jù)構(gòu)造成績實驗工程名稱實驗5圖的應(yīng)用指導教師一實驗?zāi)康?、掌握圖的根本概念和根本存儲方法；2、掌握有關(guān)圖的操作算法，并用高級語言實現(xiàn)；3、熟悉圖的各種存儲構(gòu)造及其構(gòu)造算法，理解實際問題的求解效率與采用何種存儲構(gòu)造及算法有著親密聯(lián)絡(luò)；4、熟悉如何用圖構(gòu)造解決實際應(yīng)用問題；5、培養(yǎng)數(shù)據(jù)抽象的設(shè)計才能和實際動手的綜合才能，并進一步掌握完好應(yīng)用系統(tǒng)的設(shè)計過程和方法。二實驗原理圖形構(gòu)造是一種應(yīng)用非常廣泛的數(shù)據(jù)構(gòu)造，它的應(yīng)用已經(jīng)浸透到語言學、邏輯學、物理、化學、電子、通信、數(shù)學、計算機科學等諸多學科領(lǐng)域。最短途徑是指途徑長度〔即路勁上邊的權(quán)值之和〕最小的途徑，一般討論帶權(quán)有向圖，在實際應(yīng)用中經(jīng)常用于解決城市節(jié)點間運輸代價最少或運輸時間最短等問題。三實驗內(nèi)容請為珠江三角洲城市間設(shè)計與實現(xiàn)一個簡單的交通咨詢系統(tǒng)。根本要求：〔1〕設(shè)計簡單的珠江三角洲城市間道路通行平面圖，所含城市不少于10個。以圖中頂點表示城市節(jié)點，存放城市名稱、代號、簡介等信息；以邊表示通行道路，存放道路的途徑長度?！?〕提供圖中任意城市的相關(guān)信息查詢?！?〕提供圖中任意城市間的最短途徑查詢。四實驗步驟1將珠江三角洲城市間的交通圖抽象為無向帶權(quán)圖?！惨蠼o出一個設(shè)計方案〕2設(shè)計求圖中任意結(jié)點間最短途徑的算法。3編程實現(xiàn)。五實驗方法1對問題進展需求分析，選取詳細城市結(jié)點，通過調(diào)研獲取城市間的交通網(wǎng)絡(luò)，選取主要的通行道路抽象為圖的無向帶權(quán)邊。2進展概要設(shè)計和詳細設(shè)計，形成模塊間的調(diào)用構(gòu)造圖和模塊的算法。3編寫程序，設(shè)計測試用例進展測試。4完成開發(fā)文檔。六實驗結(jié)果1需求分析：在中國城市，電子地圖的認知度和使用率正在飛快遞增，隨著用戶量不斷增加，紙質(zhì)地圖逐漸被電子地圖取而代之。在大中型城市，電子地圖已經(jīng)成為絕大多數(shù)用戶出行前首選的參照工具和查詢途徑。電子地圖強調(diào)準確性、簡單易用以及查詢速度。電子地圖的另外一個特點是使用方便，無論是通過互聯(lián)網(wǎng)還是手機都可以方便接觸到并使用。出行前用電腦通過互聯(lián)網(wǎng)地圖規(guī)劃道路、查找目的地，路上那么可以用手機連接無線網(wǎng)絡(luò)，通過手機地圖隨時修正道路和辨識方向。2概要設(shè)計：3詳細設(shè)計：4編程遇到的問題和調(diào)試分析：5用戶手冊：概述：簡單的交通咨詢系統(tǒng)功能： 1.珠三角地區(qū)交通查詢； 2.珠三角地區(qū)各城市信息查詢。使用說明： 1.翻開方法：翻開命令行窗口，進入map.exe文件所在目錄〔如：cde:/map〕，輸入map，進入程序。 2.構(gòu)造地圖信息，按提示輸入map.txt. 3.交通查詢功能的使用：輸入1進入查詢，按要求輸入起點城市編號和終點城市編號，回車即可。 4.城市信息查詢功能的使用：輸入2進入查詢，按要求輸入城市編號，回車即可。6測試結(jié)果：7附錄〔源程序清單〕#defineMAX_NAME9//頂點字符串的最大長度#defineMAX_INFO20//相關(guān)信息字符串的最大長度#defineMAX_MES300//頂點城市信息的最大長度typedefintVRType;structVertexType{charname[MAX_NAME];//城市名字charmes[MAX_MES];//城市信息};typedefcharInfoType;//c1.h(程序名)#include<string.h>#include<malloc.h>//malloc()等#include<limits.h>//INT_MAX等#include<stdio.h>//EOF(=^Z或F6),NULL#include<io.h>//eof()//函數(shù)結(jié)果狀態(tài)代碼#defineTRUE1#defineFALSE0typedefintStatus;//Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等typedefintBoolean;//Boolean是布爾類型,其值是TRUE或FALSE#defineINFINITYINT_MAX//用整型最大值代替∞#defineMAX_VERTEX_NUM26//最大頂點個數(shù)enumGraphKind{DG,DN,UDG,UDN};//{有向圖,有向網(wǎng),無向圖,無向網(wǎng)}typedefstruct{VRTypeadj;//頂點關(guān)系類型。對無權(quán)圖，//用1(是)或0(否)表示相鄰否；//對帶權(quán)圖，那么為權(quán)值InfoType*info;//該弧相關(guān)信息的指針(可無)}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//二維數(shù)組structMGraph{VertexTypevexs[MAX_VERTEX_NUM];//頂點向量,原程序放城市名字,如今加上城市信息AdjMatrixarcs;//鄰接矩陣intvexnum,arcnum;//圖的當前頂點數(shù)和弧數(shù)GraphKindkind;//圖的種類標志};//鄰接矩陣存儲構(gòu)造的根本操作intLocateVex(MGraphG,charu[MAX_NAME]){//初始條件：圖G存在，u和G中頂點有一樣特征//操作結(jié)果：假設(shè)G中存在頂點u，那么返回該頂點在圖中位置；否那么返回-1inti;for(i=0;i<G.vexnum;++i)if(strcmp(u,G.vexs[i].name)==0)returni;return-1;}//初始化無向圖voidCreateFUDN(MGraph&G){//采用數(shù)組(鄰接矩陣)表示法，由文件構(gòu)造沒有相關(guān)信息的無向網(wǎng)Ginti,j,k,w;charfilename[13];charva[MAX_NAME],vb[MAX_NAME];FILE*graphlist;printf("請輸入數(shù)據(jù)文件名：");scanf("%s",filename);graphlist=fopen(filename,"r");//翻開數(shù)據(jù)文件，并以graphlist表示fscanf(graphlist,"%d",&G.vexnum);fscanf(graphlist,"%d",&G.arcnum);for(i=0;i<G.vexnum;++i)//構(gòu)造頂點向量fscanf(graphlist,"%s",G.vexs[i].name);for(i=0;i<G.vexnum;++i)//初始化鄰接矩陣for(j=0;j<G.vexnum;++j){G.arcs[i][j].adj=INFINITY;//網(wǎng)G.arcs[i][j].info=NULL;//沒有相關(guān)信息}for(k=0;k<G.arcnum;++k){fscanf(graphlist,"%s%s%d",va,vb,&w);i=LocateVex(G,va);j=LocateVex(G,vb);G.arcs[i][j].adj=G.arcs[j][i].adj=w;//無向網(wǎng)}//讀取城市信息數(shù)據(jù)for(i=0;i<G.vexnum;++i)//構(gòu)造城市信息fscanf(graphlist,"%s",G.vexs[i].mes);fclose(graphlist);//關(guān)閉數(shù)據(jù)文件G.kind=UDN;}typedefintPathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM];//3維數(shù)組typedefintDistancMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//2維數(shù)組//求有向網(wǎng)中各對頂點之間最短間隔的Floyd算法voidShortestPath_FLOYD(MGraphG,PathMatrixP,DistancMatrixD){//用Floyd算法求有向網(wǎng)G中各對頂點v和w之間的最短途徑P[v][w]及其帶權(quán)長度D[v][w]。intu,v,w,i;for(v=0;v<G.vexnum;v++)//各對結(jié)點之間初始途徑及間隔for(w=0;w<G.vexnum;w++){D[v][w]=G.arcs[v][w].adj;//頂點v到頂點w的直接間隔for(u=0;u<G.vexnum;u++)P[v][w][u]=FALSE;//途徑矩陣初值if(D[v][w]<INFINITY)//從v到w有直接途徑P[v][w][v]=P[v][w][w]=TRUE;//由v到w的途徑經(jīng)過v和w兩點}for(u=0;u<G.vexnum;u++)for(v=0;v<G.vexnum;v++)for(w=0;w<G.vexnum;w++)if(D[v][u]<INFINITY&&D[u][w]<INFINITY&&D[v][u]+D[u][w]<D[v][w]){//從v經(jīng)u到w的一條途徑更短D[v][w]=D[v][u]+D[u][w];//更新最短間隔for(i=0;i<G.vexnum;i++)P[v][w][i]=P[v][u][i]||P[u][w][i];//從v到w的途徑經(jīng)過從v到u和從u到w的所有途徑}}//path()函數(shù)voidpath(MGraphG,PathMatrixP,inti,intj){//求由序號為i的起點城市到序號為j的終點城市最短途徑沿途所經(jīng)過的城市intk;intm=i;//起點城市序號賦給mprintf("依次經(jīng)過的城市：\n");while(m!=j)//沒到終點城市{G.arcs[m][m].adj=INFINITY;//對角元素賦值無窮大for(k=0;k<G.vexnum;k++)for(k=0;k<G.vexnum;k++)if(G.arcs[m][k].adj<INFINITY&&P[m][j][k])//m到k有直接通路，且k在m到j(luò)的最短途徑上{printf("%s",G.vexs[m].name);G.arcs[m][k].adj=G.arcs[k][m].adj=INFINITY;//將直接通路設(shè)為不通m=k;//經(jīng)過的城市序號賦給m，繼續(xù)查找break;}}printf("%s\n",G.vexs[j].name);//輸出終點城市}//主函數(shù)voidmain(){MGraphg;inti,j,q=1;intm;//查詢城市信息有關(guān)PathMatrixp;//3維數(shù)組DistancMatrixd;//2維數(shù)組printf("數(shù)據(jù)文件名為map.txt\n");CreateFUDN(g);//通過文件構(gòu)造無向網(wǎng)gfor(i=0;i<g.vexnum;i++)g.arcs[i][i].adj=0;//ShortestPath_FLOYD()要求對角元素值為0，因為兩點一樣，其間隔為0while(q){printf("請選擇：1道路查詢2城市信息查詢0完畢\n");scanf("%d",&q);if(q){for(i=0;i<g.vexnum;i++){printf("%2d%-9s",i+1,g.vexs[i].name);if(i%6==5)//printf("\n");}if(q==2){printf("\n請輸入你想要查詢的城市：\n");scanf("%d",&m);printf("%s\n\n",g.vexs[m-1].mes);}else{printf("\n請輸入要查詢的起點城市代碼終點城市代碼:");scanf("%d%d",&i,&j);if(d[i-1][j-1]<INFINITY)//有通路{printf("%s到%s的最短間隔為%d\n",g.vexs[i-1].name,g.vexs[j-1].name,d[i-1][j-1]);path(g,p,i-1,j-1);//求最短途徑上由起點城市到終點城市沿途所經(jīng)過的城市}elseprintf("%s到%s沒有途徑可通\n",g.vexs[i-1].name,g.vexs[j-1].name);printf("\n");}}}}1122廣州深圳佛山東莞中山珠海惠州江門肇慶香港澳門廣州佛山34廣州惠州141廣州東莞72廣州中山87廣州深圳141廣州澳門140深圳東莞74深圳惠州100深圳香港48深圳珠海158深圳中山126佛山肇慶86佛山江門78佛山中山79東莞惠州96東莞深圳74東莞中山97中山江門53中山珠海50中山香港169珠海江門91珠海澳門12廣州，簡稱穗，別稱羊城、花城，是廣東省會、副省級市，中國國家中心城市，世界著名的港口城市，國家重要的經(jīng)濟、金融、貿(mào)易、交通、會展和航運中心。深圳，別稱鵬城，廣東省省轄市、副省級市、方案單列市、經(jīng)濟特區(qū)，中國四大一線城市之一，中國國家區(qū)域中心城市〔華南〕，國際重要的空海樞紐和外貿(mào)口岸，中國南方重要的高新技術(shù)研發(fā)和制造基地，中國重要的經(jīng)濟和金融中心，2021年經(jīng)濟總量居中國大陸第四位。佛山，簡稱佛，是廣東省省轄市、特大城市，廣東第三大城市，中國先進制造業(yè)基地、珠三角重要的制造業(yè)城市、廣東重要的制造業(yè)中心，是珠三角核心地區(qū)輻射粵西沿海、西江流域的商務(wù)、物流中心和交通樞紐，是珠江三角洲經(jīng)濟圈中西部的重要城市，在廣東省經(jīng)濟開展中處于領(lǐng)先地位。東莞是廣東省省轄市，是“廣東四小虎〞之一，號稱“世界工廠〞，是全國4個不設(shè)市轄區(qū)的地級市之一。位于珠江口東岸，東接惠州、南抵深圳、西挨廣州、北達博羅縣，四周共與廣州、深圳和惠州的10個縣級行政區(qū)接壤。中