北理珠校园导游咨询与最短路径数据结构完整报告

1、1 北 京 理 工 大 学 珠 海 学 院课 程 设 计 说 明 书20122013 学年第一学期题目: 北理珠校园导游咨询与最短路径学院：计算机学院专业班级：软件工程5 班学号：110202051007 学生姓名：卜博指导教师：邵珂成绩：时间：2012 年 10 月 26 日2 选题五：北理珠校园导游咨询与最短路径【任务描述】1) 从北京理工大学珠海学院的平面图中选取有代表性景点（10-15 个） ，抽象成一个无向带权图。以图中顶点表示景点，边上的权值表示两地之间距离。2) 本程序的目的是为用户提供路径咨询。根据用户指定的始点和终点输出相应路径，或者根据用户指定的景点输出景点的信息。知识点：

2、图，最短路径算法难度级： 【任务要求】1) 从北京理工大学珠海学院的平面图中选取有代表性景点（10-15 个） ，抽象成一个无向带权图。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等信息。2) 为来访客人提供图中任意景点相关信息的查询。3) 为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。4) 区分汽车线路与步行线路。【测试数据】北理珠校园导游图（距离可估计）。【实验提示】一般情况下校园的道路是双向通行的可设校园平面图是一个无向网。顶点和边均含有相关信息。【实现功能】3 这个系统给用户提供查询景点，浏览路径，寻找最佳的方

3、案到达目的地，还提供了最佳路径。【概要设计】 ：用的图的算法进行构造，用邻接表建立图，图的每一个顶点代表相应的景点。然后再用深度优先遍历进行搜索，查找所需的路径。 再用迪杰特斯拉算法求出一个景点到其他景点之间的最佳路径。 然后再用弗洛伊德算法求出要查询的出发点到目的地的最短路径。【关键词】北理珠校园导游咨询与最短路径【源代码】/*包含头文件 */ #include #include /*定义符号常量 */ #define int_max 10000 #define n 10 /*定义全局变量 */ 4 int costnn;/* 边的值 */ int shortestnn;/* 两点间的最短距

4、离 */ int pathnn;/* 经过的景点 */ /*自定义函数原型说明 */ void introduce(); int shortestdistance(); void algorithm(); void display(int i,int j); void main() /*主函数 */ int i,j; char k; for(i=0;i=n;i+) for(j=0;j10 的数字编号！ nn); break; /*introduce*/ int shortestdistance() /*要查找的两景点的最短距离*/ int i,j; printf( 请输入要查询的两个景点的编号

5、(1-10 的数字编号并用 ,间隔):); scanf(%d,%d,&i,&j); if(in|in|j10的数字编号并用,间隔):n); scanf(%d,%d,&i,&j); 10 else algorithm(); display(i,j); return 1; /*shortestdistance*/ void algorithm () /*用 algorithm 算法求两个景点的最短路径*/ int i,j,k; for(i=1;i=n;i+) for(j=1;j=n;j+) shortestij=costij; pathij=0; for(k=1;k

6、=n;k+) for(i=1;i=n;i+) for(j=1;j(shortestik+shortestkj) 11 /*用 path 记录从 i 到 j 的最短路径上点j 的前驱景点的序号 */ shortestij=shortestik+shortestkj; pathij=k; pathji=k; /* algorithm */ void display(int i,int j) /* 打印两个景点的路径及最短距离*/ int a,b; a=i; b=j; printf( 您要查询的两景点间最短路径是:nn); if(shortestij!=int_max) if(ij) printf(

7、%d,b); while(pathij!=0) /* 把 i 到 j 的路径上所有经过的景点按逆序打印出来*/ printf(-%d,pathij); if(ij) 12 j=pathij; else i=pathji; printf(%d) 最短距离是 :%d 米nn,a,b,shortestab); else printf(%d,a); while(pathij!=0) /* 把 i 到 j 的路径上所有经过的景点按顺序打印出来*/ printf(-%d,pathij); if(i%d,b); printf(nn); printf(%d-%d) 最短距离是 :%5d 米nn,a,b,sho

8、rtestab); 13 else printf( 输入错误！不存在此路！nn); printf(n); /*display*/ 【测试和运行】进入系统14 景点信息查询，选择服务景点最短路径查询，选择服务15 退出系统，选择服务【心得体会】经过两周的课程设计收获很多，在做课程设计之前，我觉得这是一项浩大的工程，总觉得自己会做不到。现在当我真的完成这个课程设计时，心里有一种成就感。这次课程设计，我学到了很多东西： 学会了在编写几百行程序时如何查找错误，如何改错误；了解数据结构在编写比较复杂的程序的重要作用；对数据结构中定义无向图和创建无向图的理解更加深刻；最重要的是让我基本上明白了迪杰斯特拉算

9、法和弗洛伊德算法。巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。培养了16 我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。够按要求编写课程设计报告书，能正确阐述设计和实验结果，正确绘制系统和程序框图。通过课程设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。同时，通过这次课程设计我发现，我的数据结构基础不够扎实，有很多地方还需要继续努力。课程设计是把我们所学的理论知识进行系统的总结并应用于实践的良好机会，有利于加强我们用知识理论来分析实际问题的能力，进而加强了我们对知识认识的实践度，巩固了我们的理论知识，深化了对知识的认识，并为走向社会打下一个良好的基础。在这次课程设计中我遇到许多问题和麻烦，得到了同学的帮助和指导，才能够使得这次课程设计顺利的进行下去，这也让我明白， 要多于别人交流才能更好的完善自己。【参考文献】1严蔚敏，数据结构（c 语言版），清华大学出版社，2008 年；2杨晓光，数据结构实例教程，清华大学出版社，2008 年；3陈媛，数据结构学习指导实验指导课程设计， 机械工业出版社， 2008 年；4李春葆，数据结构教程（第2 版） ，