数据结构实践课程报告

算法设计实践课程报告学院：计算机学院班级：学号：姓名：一、课程目的本课程设计为培养学生综合实践的能力，理论知识和实际有机的结合起来，锻炼学生实际分析问题和解决问题的能力，提高学生适应实际、实践编程的能力，使对C++系统编程有一个深入的了解。二、题目3.校园导游程序——最短路径应用问题描述：用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。基本要求：实现一简单的功能查询界面：（1）查询各景点的相关信息；（2）选定某一景点作为起始点，可查询从该景点出发到其余各景点的最佳游览路径。三、算法分析与设计首先，此算法建立了类mgraph，通过邻接矩阵存储校园景点图，并通过构造函数初始化图，手动给校园图附上相关信息（包括景点编号、名称、简介、路径及路径长度等）。然后，手动绘制了部分模拟校园图。该函数包括深度优先遍历图和迪杰斯特拉最短路径算法，主要功能是实现校园七个景点（0.图书馆，1.三山楼，2.三江楼，3.教工浴室，4.西山操场，5.西山美食城，6.京江操场）的简介和最短路径的算法，最后用主函数输出结果，用switch语句分别输出，最后求出两点之间的最短路径。四、运行结果及分析输出结果：五、总结这个程序在调试时，我发现一次只能查找一个景点的相关介绍，之后的最短路径的计算生成时是成功的，但在调试时却不是很好，输出结果有误。通过这次算法设计实践，我对数据结构的运用有了更深的体会，对无向图和创建无向图的理解更加深刻，理解了迪杰斯特拉算法的原理，不再是盲目地照搬书上的程序。之后，我还发现了我的不足之处，对程序的设计还不过灵活。附录：源程序清单#includeiostream#includestringusingnamespacestd;constintmaxsize=100;classmgraph{public:mgraph(stringa[],intn,inte);//构造函数，建立n个顶点，e条边的图~mgraph(){}//析构函数voiddfstraverse(intv);//深度优先遍历voidshortpath(mgraphg,intv,intr);//求v到其余各个顶点的最短路径private:stringvertex[maxsize];//存放图中顶点的数组intarc[maxsize][maxsize];//存放图中边的数组intvertexnum,arcnum;//图中的顶点数和边数};mgraph::mgraph(stringa[],intn,inte){inti,j,k;vertexnum=n;arcnum=e;for(i=0;ivertexnum;i++)vertex[i]=a[i];for(i=0;ivertexnum;i++)//初始化邻接矩阵for(j=0;jvertexnum;j++)arc[i][j]=0;for(k=0;karcnum;k++)//依次输入每一条边{cout请输入两个景点的编号：endl;cinij;//依次输入边依附的两个顶点的编号和距离if(i7&&j7)arc[i][j]=arc[j][i]=1;//置有边标志elsecout没有该景点！！！endl;}}voidmgraph::shortpath(mgraphg,intv,intr){for(inti=0;ivertexnum;i++)for(intj=0;jvertexnum;j++){arc[i][j]=1000000;//初始化路径长度}arc[0][1]=arc[1][0]=10;arc[1][2]=arc[2][1]=5;arc[2][3]=arc[3][2]=8;arc[0][4]=arc[4][0]=15;arc[1][4]=arc[4][1]=9;arc[2][4]=arc[4][2]=10;arc[3][4]=arc[4][3]=11;arc[4][5]=arc[5][4]=12;arc[0][5]=arc[5][0]=10;arc[0][6]=arc[6][0]=14;arc[5][6]=arc[6][5]=9;intdist[maxsize]={0},s[maxsize];stringpath[maxsize];intk,i;for(i=0;ig.vertexnum;i++){dist[i]=g.arc[v][i];//初始化数组dist[n],path[n]if(dist[i]10000)path[i]=g.vertex[v]+g.vertex[i];elsepath[i]=;}s[0]=v;//初始化集合sdist[v]=0;//标记顶点v为源点intnum=1;while(numg.vertexnum)//当顶点数num小于图的顶点数{for(k=0,i=0;ig.vertexnum;i++)//在dist中查找最小值元素if((dist[i]!=0)&&(dist[i]dist[k]))k=i;s[num++]=k;//将新生成的终点加入集合sfor(i=0;ig.vertexnum;i++)//修改数组dist和pathif(dist[i]dist[k]+g.arc[k][i]){dist[i]=dist[k]+g.arc[k][i];path[i]=path[k]+g.vertex[i];}}cout路径长度为：dist[k]路径为：path[k];}intmain(){intaa,x,y;cout欢迎进入江苏大学校园导游系统！！endl;cout0.图书馆，1.三山楼，2.三江楼，3.教工浴室，4.西山操场，5.西山美食城，6.京江操场endl;stringa[7]={0,1,2,3,4,5,6};stringb[7]={图书馆,三山楼,三江楼,教工浴室,西山操场,西山美食城,京江操场};stringc[7]={图书馆：本建筑共有5层，有大量图书可供学生查阅，还可在其中自习,三山楼：2号教学楼，共8层，平时上课地点,三江楼：1号教学楼，共18层，平时上课地点,教工浴室：周二至周日开放，开放时间：14:00至20:00,西山操场：早操地点，平时自由锻炼的地方，每晚有大量人跑步,西山美食城：有大量美食可供选择，物美价廉,京江操场：位于六食堂附近，规模比西山操场略小};mgraphtu(a,7,1);cout主要景点平面图：endl;cout京江操场*******六食堂endl;cout**endl;cout**endl;cout**endl;cout**endl;cout**endl;cout****西山美食城****endl;cout****endl;cout****endl;cout****endl;cout***西山操场**老一区*endl;cout*****endl;cout***************教工浴室endl;cout*****endl;cout*****endl;cout*****东山操场***endl;cout****endl;cout****图书馆***************endl;cout***endl;cout**************三山楼****三江楼endl;cout请输入您想要了解的景点编号：;cinaa;switch(aa){case0:cout此景点为：b[0]\n简介：c[0]endl;break;case1:cout此景点为：b[1]\n简介：c[1]endl;break;case2:cout此景点为：b[2]\n简介：c[2]endl;break;case3:cout此景点为：b[3]\n简介：c[3]endl;break;case4:cout此景点为：b[4]\n简介：c[4]endl;break;case5:cout此景点为：b[5]\n简介：c[5]endl;break;case6:cout此景点为：b[6]\n简介：c[6]endl;break;default:cout您好，请输入编号为0-6的数字endl;}cout请输入当前所在景点的编号：;cinx;cout请输入您要前往的景点编号：endl;ciny;cout最短路径为：endl;tu.shortpath(tu,y,x);cout祝大家旅途愉快！！！endl;return0;}