校园导游图数据结构课程设计最终版.doc

南京航空航天大学
《数据结构》课程设计报告
校园导游系统

班级:0809103 班
学号:080910315
姓名: 施
评定成绩:
目录
一、需求分析 3
二、程序的主要功能 3
三、程序运行平台 4
四、系统总框架图 4
五、数据结构.......................................4
六、测试用例.......................................5
七、存在的不足与对策及编程体会13
八、程序源代码.................................14
需求分析
校园导游程序
[问题描述]用无向网表示你所在学校的校园景点平面图,图中顶点表示主要景点,存放景点的编号、名称、简介等信息,图中的边表示景点间的道路,存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。
[基本要求]
(1) 查询各景点的相关信息;
(2) 查询图中任意两个景点间的最短路径。
(3) 查询图中任意两个景点间的所有路径。
(4) 增加、删除、更新有关景点和道路的信息。
二、程序的主要功能
该校园导游程序共有7个主要功能:
功能一:查询景点的信息;
功能二:查询任意两景点之间的最短路径及路径长度;
功能三:查询任意两景点之间的所有路线;
功能四:在已有的校园导游图中添加新的景点及该景点到其他景点的路径长度;
功能五:在已有的校园导游图中删除已有的景点及以该景点为端点的路径;
功能六:修改已有校园导游图中的任意一个景点的名称和景点信息或任意一条路径的长度;
功能七:重新创建一个新的学校的导游图。
三、程序运行平台
virtual C++
四、系统总框架图
校园导游图
查询景点信息
查询最短路
查询所有路径
添加景点和路径
删除景点和路径
修改景点和路径
创建新导游图
程序结束

五、数据结构
该程序运用数据结构中的图的邻接表的存储方式,用顶点来存储景点的名称和景点信息等,用边来存储路径的长度等信息。之后,以有向图的邻接矩阵的方式用Dijkstra算法来求图的最短路径问题,以及图的遍历来求两点间的所有路径问题。最后,用图的添加、删除、修改等基本操作完成对校园导游图的修改和重新创建。
六、测试用例
运行程序:

输入“1”:
输入“1”:
输入编号“3”:
按任意键返回上一菜单,再选择“2、按照景点名称查询”:
输入“东区”:
按任意键返回后,再输入“e”,返回主菜单,选择“2.、查询两景点间最短路径”,再输入起点和终点景点的序号:
按任意键返回主菜单,选择“3.、查询两景点间所有路线”,再输入出发和目的景点:
按任意键返回主菜单,选择“4”添加新的景点和路径,输入新的景点名称、景点信息以及该景点到其他各景点的距离:
选择“5”删除景点和路径,之后可以按照景点编号或景点名称查询景点,将其删除:
按任意键返回后,6号景点四号楼已经被删除,其余景点依次重新排列:
选择“6”修改已有景点和路径,会出现修改景点或修改道路的选择:
我们输入“1”,然后出现输入选择要修改景点的编号,修改景点名称和修改景点描述的选择,我们输入