數(shù)據(jù)課程設(shè)計(jì) 蘭州道路交通網(wǎng)絡(luò)信息查詢 設(shè)計(jì)說(shuō)明書

PAGE*******************實(shí)踐教學(xué)*******************蘭州理工大學(xué)計(jì)算機(jī)與通信學(xué)院2006年春季學(xué)期算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目：蘭州道路交通網(wǎng)絡(luò)信息查詢專業(yè)班級(jí)：姓名：學(xué)號(hào)：指導(dǎo)教師：成績(jī)： 目錄TOC\o"1-3"\h\z摘要 1前言 2正文 31. 采用類c語(yǔ)言定義相關(guān)的數(shù)據(jù)類型 32. 各模塊的偽碼算法 43. 函數(shù)的調(diào)用關(guān)系圖 64. 調(diào)試分析 75. 測(cè)試結(jié)果 86. 源程序（帶注釋） 12總結(jié) 16參考文獻(xiàn) 17致謝 18附件Ⅰ部分源程序代碼 19PAGE2摘要在交通網(wǎng)絡(luò)非常發(fā)達(dá)，交通工具和交通方式不斷更新的今天，人們?cè)诔鲂袝r(shí)，不僅關(guān)心節(jié)省交通費(fèi)用，而且對(duì)里程和所需時(shí)間等問(wèn)題也感興趣。對(duì)于們關(guān)心的問(wèn)題，可用一個(gè)圖結(jié)構(gòu)和表示交通網(wǎng)絡(luò)系統(tǒng)，利用計(jì)算機(jī)建立一個(gè)交通咨詢系統(tǒng)。關(guān)鍵詞：交通網(wǎng)絡(luò)，鄰接矩陣，最短路徑。

前言圖是一種復(fù)雜的非線性結(jié)構(gòu)。在人工智能，工程，數(shù)學(xué)，物理，化學(xué)，計(jì)算機(jī)學(xué)科等領(lǐng)域中，圖結(jié)構(gòu)有著廣泛的應(yīng)用。我們用最短路徑問(wèn)題，用一個(gè)人們熟悉的交通咨詢系統(tǒng)實(shí)例來(lái)驗(yàn)證迪杰斯特拉算法和費(fèi)洛伊德得算法。我們?cè)趯?duì)一些問(wèn)題進(jìn)行求解時(shí)，會(huì)發(fā)現(xiàn)有些問(wèn)題很難找到規(guī)律，或者根本無(wú)規(guī)律可尋。對(duì)于這樣的問(wèn)題，可以利用計(jì)算機(jī)運(yùn)算速度快的特點(diǎn)，先搜索查找所有可能出現(xiàn)的情況，再根據(jù)題目條件從所有可能的情況中，刪除那些不符合條件的解。設(shè)計(jì)一個(gè)蘭州道路交通咨詢系統(tǒng)，能讓人們咨詢從任一個(gè)地方頂點(diǎn)到另一地方頂點(diǎn)之間的最短路徑。在計(jì)算機(jī)中，有多種方法存儲(chǔ)圖的信息，由于圖的結(jié)構(gòu)復(fù)雜，使用廣泛，一般應(yīng)根據(jù)實(shí)際的應(yīng)用，選擇適合的表示方法。常用的圖的存儲(chǔ)結(jié)構(gòu)有鄰接矩陣、鄰接多重表和鄰接表。

正文采用類c語(yǔ)言定義相關(guān)的數(shù)據(jù)類型采用鄰接矩陣定義圖typedefstruct{VertexTypevexs[MVNum];//頂點(diǎn)數(shù)組，類型假定為char型Adjmatrixarcs[MVNum][MVNum];//鄰接矩陣，假定為int型}MGraph;建立圖的存儲(chǔ)結(jié)構(gòu)#include<stdio.h>#include<stdlib.h>#defineMVNum100//最大頂點(diǎn)數(shù)#defineMaxint32767enumboolean{FALSE,TRUE};typedefcharVertexType;typedefintAdjmatrix;typedefstruct{VertexTypevexs[MVNum];//頂點(diǎn)數(shù)組，類型假定為char型Adjmatrixarcs[MVNum][MVNum];//鄰接矩陣，假定為int型}MGraph;

各模塊的偽碼算法（1）迪杰斯特拉算法的實(shí)現(xiàn)voidDijkstra(MGraph*G,intv1,intn){//用Dijkstra算法求有向圖G的v1頂點(diǎn)到其他頂點(diǎn)v的最短路徑P[v]及其權(quán)D[v]//設(shè)G是有向圖的鄰接矩陣，若邊〈i，j〉不存在，則G[i][j]=Maxint//S[v]為真當(dāng)且僅當(dāng)v∈S，即已求得從v1到v的最短路徑intD2[MVNum],P2[MVNum];v,i,w,min;enumbooleanS[MVNum];for(v=1;v<=n;v++){//初始化S和DS[v]=FALSE;//置空最短路徑終點(diǎn)集D2[v]=G->arcs[v1][v];//置初始的最短路徑值if(D2[v]<Maxint)P2[v]=v1;//v1是v的前趨（雙親）elseP2[v]=0;//v無(wú)前趨}D2[v1]=0;S[v1]=TRUE;//S集初始時(shí)只有源點(diǎn)，源點(diǎn)到源點(diǎn)的距離為0//開始循環(huán)，每次求得v1到某個(gè)v頂點(diǎn)的最短路徑，并加v到s集中for(i=2;i<n;i++){//其余n-1個(gè)頂點(diǎn)min=Maxint;for(w=1;w<=n;w++)if(!S[w]&&D2[w]<min){v=w;min=D2[w];}//w頂點(diǎn)離v1頂點(diǎn)更近S[v]=TRUE;for(w=1;w<=n;w++)//更新當(dāng)前最短路徑及距離if(!S[w]&&(D2[v]+G->arcs[v][w]<D2[w])){D2[w]=D2[v]+G->arcs[v][w];P2[w]=v;}//End_if}//End_forprintf("lujingchangdulujing\n");for(i=1;i<=n;i++){printf("%5d",D2[i]);printf("%5d",i);v=P2[i];while(v!=0){printf("<-%d",v);v=P2[v];}printf("\n");}}（2）費(fèi)洛伊德得算法的實(shí)現(xiàn)voidFloyd(MGraph*G,intn){intD[MVNum][MVNum],P[MVNum][MVNum];i,j,k,v,w;for(i=1;i<=n;i++)//設(shè)置路徑長(zhǎng)度D和路徑path初值for(j=1;j<=n;j++){if(G->arcs[i][j]!=Maxint)P[i][j]=j;//j是i的后繼else P[i][j]=0; D[i][j]=G->arcs[i][j];}for(k=1;k<=n;k++) {for(i=1;i<=n;i++)//做k次迭代，每次均試圖將頂點(diǎn)k擴(kuò)充到當(dāng)前求得的從i到j(luò)的最短路徑Pij上 for(j=1;j<=n;j++) {if(D[i][k]+D[k][j]<D[i][j]){ D[i][j]=D[i][k]+D[k][j];//修改長(zhǎng)度 P[i][j]=P[i][k]; }}}}

3.函數(shù)的調(diào)用關(guān)系圖主函數(shù)主函數(shù)main調(diào)用費(fèi)洛伊德算法voidFloyd調(diào)用費(fèi)洛伊德算法voidFloyd創(chuàng)建圖VoidMGraph調(diào)用迪杰斯特拉算法voidDijkstra調(diào)用迪杰斯特拉算法voidDijkstra打印圖的鄰接矩陣VoidMGraph

4.調(diào)試分析a、調(diào)試中遇到的問(wèn)題及對(duì)問(wèn)題的解決方法在輸入頂點(diǎn)和邊數(shù)時(shí)，要注意輸入的格式，如果在編寫程序時(shí)用的輸入方式是“，”，則在輸入頂點(diǎn)和邊數(shù)時(shí)必須用逗號(hào)將兩個(gè)數(shù)值隔開，如要輸入5和3，則正確的輸入方式是：5，3。如果輸入出現(xiàn)錯(cuò)誤，則會(huì)出現(xiàn)死循環(huán)。b、算法的時(shí)間復(fù)雜度和空間復(fù)雜度時(shí)間復(fù)雜度：創(chuàng)建圖并以鄰接矩陣存儲(chǔ)的時(shí)間復(fù)雜度為O(n)迪杰斯特拉算法的時(shí)間復(fù)雜度O（n3)費(fèi)洛伊德得算法的時(shí)間復(fù)雜度O（n3)

5.測(cè)試結(jié)果abgcabgcfed蘭州道路交通網(wǎng)圖91020181581053012一個(gè)有向圖因?yàn)樵谒惴ㄖ?，為了操作方便，?duì)于圖的頂點(diǎn)都是用序號(hào)來(lái)表示的，所以頂點(diǎn)的字母就用其對(duì)應(yīng)的序號(hào)來(lái)操作a(1),b(2),c(3),d(4),e(5),f(6),g(7)。（1）圖的鄰接矩陣#defineM20#include<stdio.h>#include<stdlib.h>#include<malloc.h>typedefstruct{intV[M];intR[M][M];intvexnum;}MGraph;voidcreatgraph(MGraph*G,intn){inti,j,r1,r2;g->vexnum=n;for(i=1;i<=n;i++){g->V[i]=i;}for(i=1;i<=n;i++)for(j=1;j<=n;j++){g->R[i][j]=0;}printf("PleaseinputR(0,0END):\n");scanf("%d,%d",&r1,&r2);while(r1!=0&&r2!=0){g->R[r1][r2]=1;g->R[r2][r1]=1;scanf("%d,%d",&r1,&r2);}}voidprintgraph(MGraph*G){inti,j;for(i=1;i<=g->vexnum;i++){for(j=1;j<=g->vexnum;j++){printf("%2d",g->R[i][j]);}printf("\n");}}main(){intn;MGraph*G=(MGraph*)malloc(sizeof(MGraph));charmenu;printf("Pleaseinputthenumberofvertex:\n");scanf("%d",&n);creatgraph(g,n);printf("Thisisthelinjiejuzhenofgraph:\n");printgraph(g);}（2）求兩個(gè)頂點(diǎn)之間的最短路徑和求兩個(gè)頂點(diǎn)之間是否有路徑存在：

6.源程序（帶注釋）#include<stdio.h>#include<stdlib.h>#defineMVNum100//最大頂點(diǎn)數(shù)#defineMaxint32767enumboolean{FALSE,TRUE};typedefcharVertexType;typedefintAdjmatrix;typedefstruct{VertexTypevexs[MVNum];//頂點(diǎn)數(shù)組，類型假定為char型Adjmatrixarcs[MVNum][MVNum];//鄰接矩陣，假定為int型}MGraph;voidCreateMGraph(MGraph*G,intn,inte){//采用鄰接矩陣表示法構(gòu)造有向圖G，n，e表示圖的當(dāng)前頂點(diǎn)數(shù)和邊數(shù)intarcs[MVNum][MVNum];inti,j,k,w;for(i=1;i<=n;i++)G->vexs[i]=(char)i;for(i=1;i<=n;i++)for(j=1;j<=n;j++)G->arcs[i][j]=Maxint;//初始化鄰接矩陣printf("shuru%dtiaobiandei,j,w:\n",e);for(k=1;k<=e;k++){//讀入e條邊，建立鄰接矩陣scanf("%d,%d,%d",&i,&j,&w);G->arcs[i][j]=w;}printf("youxiangtudecunchujiegoujianliwanbi!\n");}voidDijkstra(MGraph*G,intv1,intn){//用Dijkstra算法求有向圖G的v1頂點(diǎn)到其他頂點(diǎn)v的最短路徑P[v]及其權(quán)D[v]//設(shè)G是有向圖的鄰接矩陣，若邊〈i，j〉不存在，則G[i][j]=Maxint//S[v]為真當(dāng)且僅當(dāng)v∈S，即已求得從v1到v的最短路徑intD2[MVNum],P2[MVNum];intv,i,w,min;enumbooleanS[MVNum];for(v=1;v<=n;v++){//初始化S和DS[v]=FALSE;//置空最短路徑終點(diǎn)集D2[v]=G->arcs[v1][v];//置初始的最短路徑值if(D2[v]<Maxint)P2[v]=v1;//v1是v的前趨（雙親）elseP2[v]=0;//v無(wú)前趨}D2[v1]=0;S[v1]=TRUE;//S集初始時(shí)只有源點(diǎn)，源點(diǎn)到源點(diǎn)的距離為0//開始循環(huán)，每次求得v1到某個(gè)v頂點(diǎn)的最短路徑，并加v到s集中for(i=2;i<n;i++){//其余n-1個(gè)頂點(diǎn)min=Maxint;for(w=1;w<=n;w++)if(!S[w]&&D2[w]<min){v=w;min=D2[w];}//w頂點(diǎn)離v1頂點(diǎn)更近S[v]=TRUE;for(w=1;w<=n;w++)//更新當(dāng)前最短路徑及距離if(!S[w]&&(D2[v]+G->arcs[v][w]<D2[w])){D2[w]=D2[v]+G->arcs[v][w];P2[w]=v;}//End_if}//End_forprintf("lujingchangdulujing\n");for(i=1;i<=n;i++){printf("%5d",D2[i]);printf("%5d",i);v=P2[i];while(v!=0){printf("<-%d",v);v=P2[v];}printf("\n");}}voidFloyd(MGraph*G,intn){intD[MVNum][MVNum],P[MVNum][MVNum];inti,j,k,v,w;for(i=1;i<=n;i++)//設(shè)置路徑長(zhǎng)度D和路徑path初值for(j=1;j<=n;j++){if(G->arcs[i][j]!=Maxint)P[i][j]=j;//j是i的后繼else P[i][j]=0; D[i][j]=G->arcs[i][j];}for(k=1;k<=n;k++) {for(i=1;i<=n;i++)//做k次迭代，每次均試圖將頂點(diǎn)k擴(kuò)充到當(dāng)前求得的從i到j(luò)的最短路徑Pij上 for(j=1;j<=n;j++) {if(D[i][k]+D[k][j]<D[i][j]){ D[i][j]=D[i][k]+D[k][j];//修改長(zhǎng)度 P[i][j]=P[i][k]; }}}}intD1[MVNum],P1[MVNum];intD[MVNum][MVNum],P[MVNum][MVNum];voidmain(){MGraph*G;intm,n,e,v,w,k;intxz=1;G=(MGraph*)malloc(sizeof(MGraph));printf("shurutuzhongdingdiangeshuhebianshun,e:");scanf("%d,%d",&n,&e);CreateMGraph(G,n,e);//建立圖的存儲(chǔ)結(jié)構(gòu)while(xz!=0){printf("*****qiudefangzhijiandezuiduanlujing*****\n");printf("==============================\n");printf("1,qiuyigedefangdaosuoyoudefangdezuiduanlujing\n");printf("2,qiurenyilianggedefangzhijiandezuiduanlujing\n");printf("===============================\n");printf("qingxuanze:1or2,xuanze0exit:");scanf("%d",&xz);if(xz==2){Floyd(G,n);//調(diào)用費(fèi)洛伊德算法printf("shuruqidianhezhongdian:v,w:");scanf("%d,%d",&v,&w);k=P[v][w];if(k==0)printf("dingdian%ddao%dwulujing!\n",v,w);else{printf("congdingdian%ddao%ddezuiduanlujingshi:%d",v,w,v);while(k!=w){printf("->%d",k);//輸出后繼頂點(diǎn)k=P[k][w];//繼續(xù)找下一個(gè)后繼頂點(diǎn)}printf("->%d",w);//輸出終點(diǎn)wprintf("lujingchangdu:%d\n",D[v][w]);}}elseif(xz==1){printf("qiudanyuanlujing,shuruqidianv:");scanf("%d",&v);Dijkstra(G,v,n);//調(diào)用迪杰斯特拉算法}}printf("jieshuqiuzuiduanlujing,byebye!\n");}

總結(jié)在這三周的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)中,我的題目是:蘭州道路交通網(wǎng)絡(luò)信息查詢,這三周課程設(shè)計(jì)中,通過(guò)該題目的設(shè)計(jì)過(guò)程,我加深了對(duì)圖的建立和對(duì)迪杰斯特拉算法以及費(fèi)洛伊德算法的理解,對(duì)課本中所學(xué)的各種數(shù)據(jù)結(jié)構(gòu)進(jìn)一步理解和掌握,學(xué)會(huì)了如何把學(xué)到的知識(shí)用于解決實(shí)際問(wèn)題,鍛煉了自己動(dòng)手的能力。一個(gè)人要完成所有的工作是非常困難和耗時(shí)的。在以后的學(xué)習(xí)中我會(huì)更加注意各個(gè)方面的能力的協(xié)調(diào)發(fā)展。在課程設(shè)計(jì)時(shí)遇到了很多的問(wèn)題，在老師的幫助，和對(duì)各種資料的查閱中，將問(wèn)題解決，培養(yǎng)了我自主動(dòng)手，獨(dú)立研究的能力，為今后在學(xué)習(xí)工作中能更好的發(fā)展打下了堅(jiān)實(shí)的基礎(chǔ)。三周的課程設(shè)計(jì)很短暫，但其間的內(nèi)容是很充實(shí)的，在其中我學(xué)習(xí)到了很多平時(shí)書本中無(wú)法學(xué)到的東西，積累了經(jīng)驗(yàn)，鍛煉了自己分析問(wèn)題，解決問(wèn)題的能力，并學(xué)會(huì)了如何將所學(xué)的各課知識(shí)融會(huì)，組織，