数据结构实践课程报告(共8页).doc

《数据结构实践课程报告(共8页).doc》由会员分享，可在线阅读，更多相关《数据结构实践课程报告(共8页).doc（8页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上算法设计实践课程报告 学院：计算机学院 班级： 学号： 姓名： 一、 课程目的本课程设计为培养学生综合实践的能力，理论知识和实际有机的结合起来，锻炼学生实际分析问题和解决问题的能力，提高学生适应实际、实践编程的能力，使对C+系统编程有一个深入的了解。二、题目3. 校园导游程序最短路径应用问题描述：用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。基本要求：实现一简单的功能查询界面：（1） 查询各景点的相关信息；（2） 选定某一景点作为起

2、始点，可查询从该景点出发到其余各景点的最佳游览路径。三、 算法分析与设计首先，此算法建立了类mgraph，通过邻接矩阵存储校园景点图，并通过构造函数初始化图，手动给校园图附上相关信息（包括景点编号、名称、简介、路径及路径长度等）。然后，手动绘制了部分模拟校园图。该函数包括深度优先遍历图和迪杰斯特拉最短路径算法，主要功能是实现校园七个景点（0.图书馆，1.三山楼，2.三江楼，3.教工浴室，4.西山操场，5.西山美食城，6.京江操场）的简介和最短路径的算法，最后用主函数输出结果，用switch语句分别输出，最后求出两点之间的最短路径。四、 运行结果及分析输出结果：五、 总结 这个程序在调试时，我发

3、现一次只能查找一个景点的相关介绍，之后的最短路径的计算生成时是成功的，但在调试时却不是很好，输出结果有误。 通过这次算法设计实践，我对数据结构的运用有了更深的体会，对无向图和创建无向图的理解更加深刻，理解了迪杰斯特拉算法的原理，不再是盲目地照搬书上的程序。之后，我还发现了我的不足之处，对程序的设计还不过灵活。附录：源程序清单#include#includeusing namespace std;const int maxsize=100;class mgraphpublic:mgraph(string a,int n,int e);/构造函数，建立n个顶点，e条边的图mgraph() /析构函

4、数void dfstraverse(int v);/深度优先遍历void shortpath(mgraph g,int v,int r);/求v到其余各个顶点的最短路径private:string vertexmaxsize;/存放图中顶点的数组int arcmaxsizemaxsize;/存放图中边的数组int vertexnum,arcnum;/图中的顶点数和边数;mgraph:mgraph(string a,int n,int e)int i,j,k;vertexnum=n;arcnum=e;for( i=0;ivertexnum;i+)vertexi=ai;for(i=0;iverte

5、xnum;i+) /初始化邻接矩阵for(j=0;jvertexnum;j+)arcij=0;for(k=0;karcnum;k+)/依次输入每一条边cout请输入两个景点的编号：ij;/依次输入边依附的两个顶点的编号和距离if(i7&j7)arcij=arcji=1;/置有边标志else cout没有该景点！endl;void mgraph:shortpath(mgraph g,int v,int r)for (int i = 0; i vertexnum; i+)for (int j = 0; j vertexnum; j+)arcij = ;/初始化路径长度arc01=arc10=10;

6、arc12=arc21=5;arc23=arc32=8;arc04=arc40=15;arc14=arc41=9;arc24=arc42=10;arc34=arc43=11;arc45=arc54=12;arc05=arc50=10;arc06=arc60=14;arc56=arc65=9;int distmaxsize=0,smaxsize;string pathmaxsize;int k,i;for( i=0;ig.vertexnum;i+)disti=g.arcvi; /初始化数组distn,pathnif(disti10000)pathi=g.vertexv+g.vertexi;els

7、e pathi=;s0=v;/初始化集合sdistv=0;/标记顶点v为源点int num=1;while(numg.vertexnum)/当顶点数num小于图的顶点数for( k=0,i=0;ig.vertexnum;i+)/在dist中查找最小值元素if(disti!=0)&(distidistk)k=i;snum+=k;/将新生成的终点加入集合sfor(i=0;idistk+g.arcki)disti=distk+g.arcki;pathi=pathk+g.vertexi;cout路径长度为：distk路径为：pathk;int main()int aa,x,y;cout欢迎进入江苏大学

8、校园导游系统！endl;cout0.图书馆，1.三山楼，2.三江楼，3.教工浴室，4.西山操场，5.西山美食城，6.京江操场endl;string a7=0,1,2,3,4,5,6;string b7=图书馆,三山楼,三江楼,教工浴室,西山操场,西山美食城,京江操场;string c7=图书馆：本建筑共有5层，有大量图书可供学生查阅，还可在其中自习,三山楼：2号教学楼，共8层，平时上课地点,三江楼：1号教学楼，共18层，平时上课地点,教工浴室：周二至周日开放，开放时间：14:00至20:00,西山操场：早操地点，平时自由锻炼的地方，每晚有大量人跑步,西山美食城：有大量美食可供选择，物美价廉,京

9、江操场：位于六食堂附近，规模比西山操场略小;mgraph tu(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 * * *

10、 * * * * * * * * * * * *教工浴室endl;cout * * * * * endl;cout * * * * * endl; cout* * * * *东山操场* * * endl;cout* * * * endl;cout* * * * 图书馆* * * * * * * * * * * * * * * endl;cout * * * endl;cout * * * * * * * * * * * * * *三山楼 * * * *三江楼 endl;coutaa;switch(aa)case 0:cout此景点为：b0n简介：c0endl;break;case 1:cout

11、此景点为：b1n简介：c1endl;break;case 2:cout此景点为：b2n简介：c2endl;break;case 3:cout此景点为：b3n简介：c3endl;break;case 4:cout此景点为：b4n简介：c4endl;break;case 5:cout此景点为：b5n简介：c5endl;break;case 6:cout此景点为：b6n简介：c6endl;break;default:cout您好，请输入编号为0-6的数字endl;coutx;cout请输入您要前往的景点编号：y;cout最短路径为：endl;tu.shortpath(tu,y,x);cout祝大家旅途愉快！endl;return 0;专心-专注-专业