欢迎来到天天文库
浏览记录
ID:60836670
大小:48.50 KB
页数:8页
时间:2020-12-21
《数据结构实践课程报告.doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、算法设计实践课程报告学院:计算机学院班级:学号:姓名:一、课程目的本课程设计为培养学生综合实践的能力,理论知识和实际有机的结合起来,锻炼学生实际分析问题和解决问题的能力,提高学生适应实际、实践编程的能力,使对C++系统编程有一个深入的了解。二、题目3.校园导游程序——最短路径应用问题描述: 用无向网表示你所在学校的校园景点平面图,图中顶点表示主要景点,存放景点的编号、名称、简介等信息,图中的边表示景点间的道路,存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。基本要求: 实现一简单的功能查询
2、界面:(1)查询各景点的相关信息;(2)选定某一景点作为起始点,可查询从该景点出发到其余各景点的最佳游览路径。三、算法分析与设计首先,此算法建立了类mgraph,通过邻接矩阵存储校园景点图,并通过构造函数初始化图,手动给校园图附上相关信息(包括景点编号、名称、简介、路径及路径长度等)。然后,手动绘制了部分模拟校园图。该函数包括深度优先遍历图和迪杰斯特拉最短路径算法,主要功能是实现校园七个景点(0.图书馆,1.三山楼,2.三江楼,3.教工浴室,4.西山操场,5.西山美食城,6.京江操场)的简介和最短路径的算法
3、,最后用主函数输出结果,用switch语句分别输出,最后求出两点之间的最短路径。四、运行结果及分析输出结果:五、总结这个程序在调试时,我发现一次只能查找一个景点的相关介绍,之后的最短路径的计算生成时是成功的,但在调试时却不是很好,输出结果有误。通过这次算法设计实践,我对数据结构的运用有了更深的体会,对无向图和创建无向图的理解更加深刻,理解了迪杰斯特拉算法的原理,不再是盲目地照搬书上的程序。之后,我还发现了我的不足之处,对程序的设计还不过灵活。附录:源程序清单#include#includ
4、eusingnamespacestd;constintmaxsize=100;classmgraph{public:mgraph(stringa[],intn,inte);//构造函数,建立n个顶点,e条边的图~mgraph(){}//析构函数voiddfstraverse(intv);//深度优先遍历voidshortpath(mgraphg,intv,intr);//求v到其余各个顶点的最短路径private:stringvertex[maxsize];//存放图中顶点的数组intarc
5、[maxsize][maxsize];//存放图中边的数组intvertexnum,arcnum;//图中的顶点数和边数};mgraph::mgraph(stringa[],intn,inte){inti,j,k;vertexnum=n;arcnum=e;for(i=0;i6、)//依次输入每一条边{cout<<"请输入两个景点的编号:"<>i>>j;//依次输入边依附的两个顶点的编号和距离if(i<7&&j<7)arc[i][j]=arc[j][i]=1;//置有边标志elsecout<<"没有该景点!!!"<7、rc[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[8、maxsize]={0},s[maxsize];stringpath[maxsize];intk,i;for(i=0;i
6、)//依次输入每一条边{cout<<"请输入两个景点的编号:"<>i>>j;//依次输入边依附的两个顶点的编号和距离if(i<7&&j<7)arc[i][j]=arc[j][i]=1;//置有边标志elsecout<<"没有该景点!!!"<7、rc[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[8、maxsize]={0},s[maxsize];stringpath[maxsize];intk,i;for(i=0;i
7、rc[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[
8、maxsize]={0},s[maxsize];stringpath[maxsize];intk,i;for(i=0;i
此文档下载收益归作者所有