算法與數據結構課程設計《蘭州道路交通網絡信息查詢設計說明書》

頁摘要在交通網絡非常發(fā)達，交通工具和交通方式不斷更新的今天，人們在出行時，不僅關心節(jié)省交通費用，而且對里程和所需時間等問題也感興趣。對于們關心的問題，可用一個圖結構和表示交通網絡系統，利用計算機建立一個交通咨詢系統。關鍵詞：交通網絡，鄰接矩陣，最短路徑。

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

正文采用類c語言定義相關的數據類型采用鄰接矩陣定義圖typedefstruct{VertexTypevexs[MVNum];//頂點數組，類型假定為char型Adjmatrixarcs[MVNum][MVNum];//鄰接矩陣，假定為int型}MGraph;建立圖的存儲結構#include<stdio.h>#include<stdlib.h>#defineMVNum100//最大頂點數#defineMaxint32767enumboolean{FALSE,TRUE};typedefcharVertexType;typedefintAdjmatrix;typedefstruct{VertexTypevexs[MVNum];//頂點數組，類型假定為char型Adjmatrixarcs[MVNum][MVNum];//鄰接矩陣，假定為int型}MGraph;

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

3.函數的調用關系圖主函數主函數main調用費洛伊德算法voidFloyd調用費洛伊德算法voidFloyd創(chuàng)建圖VoidMGraph調用迪杰斯特拉算法voidDijkstra調用迪杰斯特拉算法voidDijkstra打印圖的鄰接矩陣VoidMGraph

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

5.測試結果abgcabgcfed蘭州道路交通網圖91020181581053012一個有向圖因為在算法中，為了操作方便，對于圖的頂點都是用序號來表示的，所以頂點的字母就用其對應的序號來操作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）求兩個頂點之間的最短路徑和求兩個頂點之間是否有路徑存在：

6.源程序（帶注釋）#include<stdio.h>#include<stdlib.h>#defineMVNum100//最大頂點數#defineMaxint32767enumboolean{FALSE,TRUE};typedefcharVertexType;typedefintAdjmatrix;typedefstruct{VertexTypevexs[MVNum];//頂點數組，類型假定為char型Adjmatrixarcs[MVNum][MVNum];//鄰接矩陣，假定為int型}MGraph;voidCreateMGraph(MGraph*G,intn,inte){//采用鄰接矩陣表示法構造有向圖G，n，e表示圖的當前頂點數和邊數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頂點到其他頂點v的最短路徑P[v]及其權D[v]//設G是有向圖的鄰接矩陣，若邊〈i，j〉不存在，則G[i][j]=Maxint//S[v]為真當且僅當v∈S，即已求得從v1到v的最短路徑intD2[MVNum],P2[MVNum];intv,i,w,min;enumbooleanS[MVNum];for(v=1;v<=n;v++){//初始化S和DS[v]=FALSE;//置空最短路徑終點集D2[v]=G->arcs[v1][v];//置初始的最短路徑值if(D2[v]<Maxint)P2[v]=v1;//v1是v的前趨（雙親）elseP2[v]=0;//v無前趨}D2[v1]=0;S[v1]=TRUE;//S集初始時只有源點，源點到源點的距離為0//開始循環(huán)，每次求得v1到某個v頂點的最短路徑，并加v到s集中for(i=2;i<n;i++){//其余n-1個頂點min=Maxint;for(w=1;w<=n;w++)if(!S[w]&&D2[w]<min){v=w;min=D2[w];}//w頂點離v1頂點更近S[v]=TRUE;for(w=1;w<=n;w++)//更新當前最短路徑及距離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++)//設置路徑長度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次迭代，每次均試圖將頂點k擴充到當前求得的從i到j的最短路徑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];//修改長度 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);//建立圖的存儲結構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);//調用費洛伊德算法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);//輸出后繼頂點k=P[k][w];//繼續(xù)找下一個后繼頂點}printf("->%d",w);//輸出終點wprintf("lujingchangdu:%d\n",D[v][w]);}}elseif(xz==1){printf("qiudanyuanlujing,shuruqidianv:");scanf("%d",&v);Dijkstra(G,v,n);//調用迪杰斯特拉算法}}printf("jieshuqiuzuiduanlujing,byebye!\n");}

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

參考文獻嚴蔚敏，陳文博編