數(shù)據(jù)結(jié)構(gòu)-實(shí)驗(yàn)5-圖的應(yīng)用

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