校園導(dǎo)航實(shí)驗(yàn)報(bào)告

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