课程论文（设计）2011-2012学年第2学期课程名称：数据结构课程设计课程性质：实践课专业班级：考核方式：考查学生姓名：学号：学时：1周教师姓名：..目录1. 作业内容 (1)2. 基本思路 (1)2.1 本校10个景点 (1)2.2 图的初始化 (2)2.3 图的遍历 (2)2.4 求最短路径 (3)3.系统流程 (4)3.1 系统的简单说明 (4)3.2 系统流程图 (5)4. 系统运行效果图 (5)4.1 校园导游界面 (5)4.2 华农校园地图 (6)4.3 景点的相关信息查询 (6)4.4 任意两个景点间的最短路径 (7)4.5 退出校园导游系统 (8)5.总结 (9)6.参考文献 (10)1. 作业内容设计一个校园导游程序，为来访客人提供各种信息查询任务。
基本要求：（1）设计你所在学校的校园平面图，所含景点不少于10个。
以图中顶点表示校内各景点，存放景点名称、代号、简介信息，以边表示路权，存放路径长度等相关信息。
（2）为来访客人提供图中任意景点相关信息的查询（3）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。
2. 基本思路要完成对整个导游图系统的功能实现，需要对的每一项功能都有清楚的设想和认识，了解并明确每一项功能的实现需要解决的问题，选择正确并且高效的算法把问题逐个解决，最终实现程序的正确调试运行。
有以下设计思路：（1）.结合本校的实际情况，选出10个景点；（2）.人为手工为选出的10个景点赋上相关信息（名称、代号、简介信息、以及路权等等）；（3）.根据选出来的10个景点用邻接矩阵存储校园图。
（4）.依照景点的相关信息创建校园图。
（5）.把纸质上的内容，利用C++编程语言编写查找景点相关信息的程序。
（6).根据人为赋值的路权，迪杰斯特拉算法计算任意两点之间的最短路径。
（7）.综上所诉，用一个主函数把这些板块合成，生产一个菜单界面呈现在用户面前。
为此，可把系统分为以下几个核心：图的初始化、图的遍历、求最佳路线。
2.1 选出本校10个景点结合华南农业大学实际情况，我选出以下10个景点，从1到10编号：2.2 图的初始化由于邻接矩阵特殊的存储方式，它非常便于快速的查找两个顶点之间的边上的权值。
所以，图采用带权的邻接矩阵存储。
决定了图的存储方式后，以华南农业大学10个景点的游览地图作为蓝本，把校园地图抽象化成顶点与边构成的图形式，如图2.2所示，途中数字代表线的权值。
2.3 图的遍历图的遍历是图中最基本的操作。
图的遍历是指从图中某一顶点出发，对图中所有顶点访问一次且仅访问一次。
导游图需要把每条路径的信息都向游客展示，就需要读取每两个顶点间的路径信息。
由于采用了带权的邻接矩阵存储结构进行存储，所以需要针对这一存储结构对路线进行遍历操作。
其遍历算法如图2.3所示。
2.4 求最短路径基于本程序中图的存储是邻接矩阵结构存储的图结构，因而采用适合该存储结构的迪杰斯特拉算法用于解决求最短路径的问题。
迪杰斯特拉提出了一个按路径长度递增的持续产生最短路径的算法，其基本思想是：设置一个集合S 存放已经找到最短路径的顶点，S 的初始状态只包含源点v ，对于v i ∈V-S ，假设从源点v 到v i 的有向边为最短路径。
以后每求得一条最短路径v ，…，v k ，就将v k 加入集合S 中，并将路径v ，…，v k ，v i ，与原来的假设相比较，取路径长度较小者为最短路径。
重复上述过程，直到集合V 中全部顶点加入到集合S 中。
如图2.4所示。
图2.3 遍历算法示意图图2.4 图的遍历算法执行效果示意图辅助数组dist[n]：元素dist[i]表示当前找到的从源点到终点vi的最短路径的长度。
初态为:若从v到vi有弧，则dist[i]为弧上的权值；否则置dist[i]为∞。
若当前求得的终点为vk,则根据下式进行迭代：dist[i]=min{dist[i],dist[k]+arc[k][i]} 1≦i≦n辅助数组path[n]:元素path[i]是一个串，表示当前所找到的从源点到终点v i 的最短路径。
初态为：若从v到vi有弧，则path[i]为“vvk”，否则置path[i]为空串。
数组s[n]：存放源点和已经生成的终点（即集合S），初态为只有一个源点v。
算法的伪代码描述是：1.初始化数组dist、path和s；2.while（s中的元素个数<n）2.1 在dist[n]中求最小值，其下标为k（则vk为正在生成的终点）；2.2 输出dist[j]和path[j]；2.3 修改数组dist和path;2.4 将顶点vk添加到数组s中；3.系统流程3.1 系统的简单说明1.创建校园图：（1）先手工画好华农的10个景点的草图，再用C++语言输出抽象化的校园地图。
（2）再用C++语言定义节点个数N，编写函数name( )为景点赋值各类信息项，函数information( )，输入各个景点的简介。
（3）读入道路的起始点，为邻接矩阵的边赋相应的值。
2．利用函数travgraph 来查找景点信息。
3．创建一个校园图creat(Matrix_Graph *G)，然后为相应的边赋上现实意义上的权值。
4．用path( )函数来求任意两景点之间的最短路径。
5.如果不查询则调用exit( )函数退出。
5．用main 函数来输出导游界面。
3.2 系统流程图4.系统运行效果图4.1 校园导游界面程序运行，后台对图结构进行初始化，运行结果如图4.1。
开始Main 函数界面菜单输出华农地图调用查询景点函数travgraph( )是否再次查询？调用查询最短距离函数path( )YESNO是否再次查询？ YES NO输入1输入2输入3 调用函数exit( ) 输入4 结束返 回 界面 菜单图4.1 校园导游节目图4.2 华农校园地图校园地图的查看是通过抽象化10个景点来用printf( )函数输出地图，在输入选择1之后弹出的界面，运行结果如图4.2。
图4.2 抽象化的华南农业大学校园导游地图4.3 景点的相关信息查询景点的相关信息查询是通过information( )函数来调用输出的，在主菜单那输入2之后，拿第2个景点红满堂和第7个景点竹园来当例子，第运行结果如图4.3.1和图4.3.2。
图4.3.1 景点2红满堂信息查询图4.3.2 景点7竹园信息查询4.4 任意两个景点间的最短路径根据用户的需求，在用户输入了起点和终点后计算出最短路径是哪一条路径。
以下举两个例子。
第一个例子的起点是5东区运动场，终点是1校史馆。
第二个例子的起点是2红满堂，终点是10黑山运动场。
运行结果如图4.4.1和图4.4.2所示。
图4.4.1 从东区运动场到校史馆的最短路径图4.4.2 从红满堂到黑山运动场的最短路径根据截图可知，在现实生活中的最短路径也是如此。
证明了程序的正确性。
4.5 退出校园导游系统用户满足了需求之后，只要在界面菜单处输入4便可退出此次校园导游系统。
运行结果如图4.5。
图4.5 退出校园导游系统5.总结由于设计者水平有限，本导游图系统的功能还比较简单，还有一些好的设想没有实现：比如添加管理模式，使得公园管理人员能够同样方便的更改导游图，因此更改这一导游图还必须在程序员的帮助下进行。
另外，本导游图系统还有一定的局限性，如果存在只有一条通路的景点，导游图将无法求得最佳旅游路径。
公园的导游图系统的这些不足请老师多多谅解。
通过这次的课程设计左右，让我对数据结构中定义无向图和创建无向图的理解更加深刻，不断提升认识，提高编程技巧，借以不断地提高程序设计水平，了解数据结构在编写比较复杂的程序的重要作用；理解了迪杰斯特拉算法的原理，但对于其算法的程序编写还是不太明白；学会了在编写几百行程序时如何查找错误，如何改错误等等。
总而言之，这次的课程设计很好地锻炼自己实际操作能力！参考文献[1]严蔚敏，吴伟民.数据结构（C语言版）.清华大学出版社.1997.[2]李春葆，尹为民，李蓉蓉.数据结构教程（第3版）上机实验指导.清华大学出版社.2009.[3]滕国文.数据结构课程设计.清华大学出版社.2010.218-223.[4]蒋盛益.数据结构学习指导与训练.中国水利水电出版社.2003.//程序名称：校园导游系统//程序员：//编写时间：2012年6月#define N 10#define MAX 25#define MAXedg 30#include <stdio.h>#include <string.h>#include <stdlib.h>#include <conio.h>void clrscr(){system("cls");}typedef int AdjMatrix[MAX][MAX];typedef struct{int vexs[MAX];AdjMatrix arcs;}Matrix_Graph;typedef struct{char name[10];char information[100];struct edgenode *link; }vexnode;typedef struct edgenode{int adjvex;int length;char info[10];char info2[100];struct edgenode *next;}edgenode, *Node ;typedef struct Edge{int lengh;int ivex, jvex;struct Edge *next;} EdgeType;typedef struct{int num;char name[10];} vertex;typedef struct{vertex vexs[MAX];int edges[MAX][MAX];}adjmax;void Name(int i){switch(i){case 1:printf("1:校史馆\n\n");break;case 2:printf("2:红满堂 \n\n");break;case 3:printf("3:行政楼\n\n");break;case 4:printf("4:西园\n\n");break;case 5:printf("5:东区运动场\n\n");break;case 6:printf("6:树木园\n\n");break;case 7:printf("7:竹园\n\n");break;case 8:printf("8:新校门\n\n");break;case 9:printf("9:老校门\n\n");break;case 10:printf("10:黑山运动场\n\n");break;default:printf("景点编号输入错误！请输入1-10的数字编号！\n\n"); break;}void Information(int i)/*景点介绍*/{switch(i){case 1:printf("校史馆:华农校史档案保存的地方。