算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計《蘭州道路交通網(wǎng)絡(luò)信息查詢設(shè)計說明書》

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

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

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

各模塊的偽碼算法（1）迪杰斯特拉算法的實現(xiàn)voidDijkstra(MGraph*G,intv1,intn){//用Dijkstra算法求有向圖G的v1頂點到其他頂點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;//置空最短路徑終點集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++)//更新當(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）費洛伊德得算法的實現(xiàn)voidFloyd(MGraph*G,intn){intD[MVNum][MVNum],P[MVNum][MVNum];i,j,k,v,w;for(i=1;i<=n;i++)//設(shè)置路徑長度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擴充到當(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];//修改長度 P[i][j]=P[i][k]; }}}}

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

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

5.測試結(jié)果abgcabgcfed蘭州道路交通網(wǎng)圖91020181581053012一個有向圖因為在算法中，為了操作方便，對于圖的頂點都是用序號來表示的，所以頂點的字母就用其對應(yīng)的序號來操作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//最大頂點數(shù)#defineMaxint32767enumboolean{FALSE,TRUE};typedefcharVertexType;typedefintAdjmatrix;typedefstruct{VertexTypevexs[MVNum];//頂點數(shù)組，類型假定為char型Adjmatrixarcs[MVNum][MVNum];//鄰接矩陣，假定為int型}MGraph;voidCreateMGraph(MGraph*G,intn,inte){//采用鄰接矩陣表示法構(gòu)造有向圖G，n，e表示圖的當(dāng)前頂點數(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頂點到其他頂點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;//置空最短路徑終點集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++)//更新當(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è)置路徑長度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擴充到當(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];//修改長度 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);//建立圖的存儲結(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)用費洛伊德算法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);//調(diào)用迪杰斯特拉算法}}printf("jieshuqiuzuiduanlujing,byebye!\n");}

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

參考文獻(xiàn)嚴(yán)蔚敏，陳文博編