校園導航實驗報告

計算機工程學院課程設計報告課程名稱：數(shù)據(jù)結構課程設計設計題目：校園導航問題院系：計算機工程學院專業(yè)：計算機科學與技術組別：學生姓名：學號:起止日期:2011年12月26日~2012年1月3日指導教師:目錄TOC\o"1-5"\h\z\o"CurrentDocument"1需求分析02.1課程設計（實踐周）題目錯誤！未定義書簽。2.2課程設計（實踐周）任務及要求錯誤！未定義書簽。\o"CurrentDocument"2.3課程設計（實踐周）思想12.4軟硬件運行環(huán)境開發(fā)工具12概要設計錯誤!未定義書簽。2.1本課題設計所用數(shù)據(jù)結構錯誤！未定義書簽。\o"CurrentDocument"2.2本課題主要設計思想2\o"CurrentDocument"3代碼設計2\o"CurrentDocument"4調(diào)試與操作說明85總結86致謝8\o"CurrentDocument"7參考文獻88指導老師評語91需求分析1.1課程設計（實踐周）題目設計你的學校的平面圖，至少包括10個以上的場所，每兩個場所間可以有不同的路，且路長也可能不同。找出從任意場所到達另一場所的最佳路徑（最短路徑）。本課題實現(xiàn)校園多個場所（至少10個）的最短路徑的求解。1.2課程設計（實踐周）任務及要求設計要求：主要的功能有：1）景點顯示（顯示景點的編號、名稱以及簡介）2）最短路徑求解（求一點到所有點之間的路徑及長短，求始終兩點之間的路徑及長短）。3）景點查找（有選擇的查找你所想了解的景點）1.3課程設計（實踐周）思想按照題目要求，將代碼分為三個結構體和三個主要函數(shù)1.4運行環(huán)境以及開發(fā)工具Windows2000以上操作系統(tǒng)VisualC++6.0以上編譯環(huán)境2概要設計2.1本課題設計所用數(shù)據(jù)結構本課題主要用到的是struct類以及圖論里面的迪杰斯特拉算法和弗洛伊德算法2.2本課題主要設計思想1）淮陰工學院景點省略圖2）結構圖3代碼設計迪杰斯特拉算法:voidShortestPath_DIJ(MGraph*G){intv,w,i,min,t=0,x,flag=1,v0;intfinal[40],D[40],p[40][40];cout<<"I111"<<endl;cout<<"I編號I景點名稱|簡介I"<<endl;for(v=0;v<10;v++){cout<<"I"<<G->view[v].num<<setw(5)<<"I"<<G->view[v].name<<setw(11)<<"I"<<G->view[v].instruction<<setw(5)<<"I"<<endl;}for(v=10;v<G->vexnum;v++){cout<<"I"<<G->view[v].num<<setw(4)<<"I"<<G->view[v].name<<setw(11)<<"I"<<G->view[v].instruction<<setw(6)<<"I"<<endl;}cout<<"1111"<<endl;while(flag==1){cout<<"請輸入一個起始景點編號:"；cin>>v0;if(v0<0||v0>G->vexnum){cout<<"景點編號不存在!請重新輸入景點編號:"；cin>>v0;}if(v0>=0&&v0<G->vexnum){flag=0;for(v=0;v<G->vexnum;v++)final[v]=0;D[v]=G->l[vO][v],d;for(w=0;w<G->vexnum;w++)(p[v][w]=O;}if(D[v]<INFINITY)(p[v][vO]=l;p[v][v]=l;}}D[vO]=O;final[vO]=l;for(i=l;i<G->vexnum;i++)(min=INFINITY;for(w=0;w<G->vexnum;w++)(if(!final[w])(if(D[w]<min)v=w;min=D[w];final[v]=l;}for(w=0;w<G->vexnum;w++)if(final[w]!=0&&(min+G->l[v][w].d<D[w])){D[w]=min+G->l[v][w].d;for(x=0;x<G->vexnum;x++)p[w][x]=p[v][x];p[w][w]=1;}}for(v=0;v<G->vexnum;v++){if(v0!=v){cout<<G->view[v0].name;}for(w=0;w<G->vexnum;w++){if(p[v][w]==1&&w!=v0){cout<<"-->"<<G->view[w].name;}t++;}if(t>G->vexnum-1&&v0!=v){cout<<"總路線長"<<D[v]<<endl;}}}弗洛伊德算法：voidFloyd(MGraph*G){intv,u,i,w,k,j,flag=1,p[40][40][40],D[40][40];cout<<I111"<<endl;cout<<"|編號|景點名稱|簡介I"<<endl;for(v=0;v<10;v++)TOC\o"1-5"\h\zcout<<"|"<<G->view[v].num<<setw(5)<<"|"<<G->view[v].name<<setw(11)<<"|"<<G->view[v].instruction<<setw(5)<<"|"<<endl;for(v=10;v<G->vexnum;v++)cout<<"|"<<G->view[v].num<<setw(4)<<"|"<<G->view[v].name<<setw(11)<<"|"<<G->view[v].instruction<<setw(6)<<”|"<<endl;cout<<"1111"<<endl;for(v=0;v<G->vexnum;v++){for(w=0;w<G->vexnum;w++){D[v][w]=G->l[v][w].d;for(u=0;u<G->vexnum;u++){p[v][w][u]=0;}if(D[v][w]<INFINITY){p[v][w][v]=1;p[v][w][w]=1;}}}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]+D[u][w]<D[v][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];}}}}}while(flag==1){cout<<"請輸入出發(fā)點和目的地的編號(用空格隔開):";cin>>k>>j;if(k<0||k>G->vexnum){cout<<"景點編號不存在!請重新輸入出發(fā)點和目的地的編號cin>>k>>j;}if(k>=0&&k<G->vexnum)flag=0;}cout<<G->view[k].name;for(u=0;u<G->vexnum;u++){if(p[k][j][u]&&k!=u&&j!=u){cout<<"-->"<<G->view[u].name;}cout<<"-->"<<G->view[j].name;cout<<"總路線長"<<D[k][j]<<endl;}4調(diào)試與操作說明調(diào)試過程中不存在問題。操作包括如下幾個步驟：程序剛運行時跳出的功能主菜單；輸入選項1后，會跳出所有景點的序列號，名稱以及簡介并循環(huán)主菜單功能圖輸入選項2后，會跳出查詢所有路線功能的起始界面，會讓你輸入你所在的起點所能到達的所有地方輸入選項3后，會跳出讓你選擇起始點和出發(fā)點的功能的起始界面，讓你輸入起始點和出發(fā)點輸入選項4后，會跳出景點的名稱與序號對應列表，并讓你輸入你所想了解的景點信息總結這次課程設計的成功，不單單是解決的課程設計這問題，更多的是掌握了許多寶貴的實踐經(jīng)驗，這才是學習最重要的一部分。致謝謝謝所有在這