校园导航实验报告

计算机工程学院课程设计报告课程名称：数据结构课程设计设计题目：校园导航问题院系：计算机工程学院专业：计算机科学与技术组别：学生姓名：学号:起止日期: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软硬件运行环境开发工具12概要设计错误!未定义书签。2.1本课题设计所用数据结构错误！未定义书签。\o"CurrentDocument"2.2本课题主要设计思想2\o"CurrentDocument"3代码设计2\o"CurrentDocument"4调试与操作说明85总结86致谢8\o"CurrentDocument"7参考文献88指导老师评语91需求分析1.1课程设计（实践周）题目设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同。找出从任意场所到达另一场所的最佳路径（最短路径）。本课题实现校园多个场所（至少10个）的最短路径的求解。1.2课程设计（实践周）任务及要求设计要求：主要的功能有：1）景点显示（显示景点的编号、名称以及简介）2）最短路径求解（求一点到所有点之间的路径及长短，求始终两点之间的路径及长短）。3）景点查找（有选择的查找你所想了解的景点）1.3课程设计（实践周）思想按照题目要求，将代码分为三个结构体和三个主要函数1.4运行环境以及开发工具Windows2000以上操作系统VisualC++6.0以上编译环境2概要设计2.1本课题设计所用数据结构本课题主要用到的是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<<"请输入出发点和目的地的编号(用空格隔开):";cin>>k>>j;if(k<0||k>G->vexnum){cout<<"景点编号不存在!请重新输入出发点和目的地的编号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调试与操作说明调试过程中不存在问题。操作包括如下几个步骤：程序刚运行时跳出的功能主菜单；输入选项1后，会跳出所有景点的序列号，名称以及简介并循环主菜单功能图输入选项2后，会跳出查询所有路线功能的起始界面，会让你输入你所在的起点所能到达的所有地方输入选项3后，会跳出让你选择起始点和出发点的功能的起始界面，让你输入起始点和出发点输入选项4后，会跳出景点的名称与序号对应列表，并让你输入你所想了解的景点信息总结这次课程设计的成功，不单单是解决的课程设计这问题，更多的是掌握了许多宝贵的实践经验，这才是学习最重要的一部分。致谢谢谢所有在这