文档介绍：南京航空航天大学
《数据结构》课程设计报告
校园导游系统
目录
需求分析…………………………2
程序的主要功能…………………2
程序运行平台……………………2
数据结构…………………………2
算法设计思想及时间复杂度……2
测试用例及结果…………………5
存在的不足与对策及编程体会…6
程序源代码………………………6
一、需求分析
南航学生家长及入学新生很需要一个导游程序,来引领他们参观和了解南航。
二、程序的主要功能
1、查询各景点的相关信息
2、查询任意两景点间的所有路径
3、查询任意两景点间的最短路径 1、增加景点
4、推荐参观路线 2、删除景点
5、更新导游信息(操作需管理员密码) 3、更新道路信息
6、对景点联通性的浏览(2阶矩阵表示) 4、更新景点信息
7、学校全景一览 5、修改管理员密码
三、程序运行平台
Microsoft Visual C++
四、数据结构
图的邻接矩阵存储表示,栈的顺序存储表示
五、算法设计思想及时间复杂度
主要函数介绍:
1、求两点间的所有路径:
a)相关函数:
void dfs(MGraph G,SqStack path,int *used,int u,int w);//深度优先遍历
b)主要算法思想:栈的相关操作+深度优先搜索
创建一个空栈保存路径,一个空数组保存已标记节点,首先让起点进栈,并标记为已访问,然后调用深度优先搜索,如果该顶点的相邻顶点(即与其有直接通路的顶点)未被访问过就标记为已访问,进栈,然后对它调用深度优先搜索,依次类推,直到获得所有到指定终点的路径。
c)时间复杂度:O(VE),其中V为图的顶点数目,E为图中边的数目。
2、求两点间的最短路径:
a)相关函数:
void ShortestPath(MGraph G,int v0,int P[][Nmax],int *D);//查询任意两景点间的最短路径
void PrintShortest(MGraph G,int v1,int v2,int P[][Nmax],int *D); //输出最短路径
b)主要算法思想:迪杰斯特拉算法
假设起点为v0,S为已找到的从v0出发的最短路径的终点的集合,其初始状态为空集。而vj为当前求得的从v0出发的最短路径的终点,则将j加到集合S中去,然后修改从v0出发到集合S的补集上任一顶点vk可达的最短路径的长度。重复上两步共n-1次即可。
c)时间复杂度:O(V*V*V),V表示图中的顶点数目。
3、推荐参观路径:
a)相关函数:
void mentPath(MGraph G);//推荐参观路线
void NextValue(int k,int n);//生成下一个顶点
void Hamiltonian(int k,int n);//搜索所有的回路
b)主要算法思想:回溯法求哈密顿回路。
c)时间复杂度:O(E),其中E为图中边的数目。
4、更改导游信息
a)相关函数:
void MakeChange(MGraph &G,char *pass);//更新导游信息(操作需管理员密码)
void ChangeText(MGraph G,char *pass);//更新文本内容
b)主要算法思想:
第一个函数操作需要有管理员权限,初始密码为:1234,不然信息的安全性无法保证。修改后的信息会通过上面第二个函数写入文件,保证下次运行是修改后了的信息。
特色函数介绍:
1、验证密码正确性及修改密码函数
int ConfirmPassword(char *pass);//验证密码是否正确
void ChangePassword(char *pass);//修改管理员密码
用户输入密码时,程序会自动输出“*”符号,以保证密码不被其他人看到。修改密码时,程序提示用户输入两遍,以验证密码的正确性。
所以只有拥有密码的管理员才能够更新导游信息和修改密码。初始密码为:1234.
2、验证输入有效性的函数
int ConfirmChoice(int low,int high);//验证输入是否合法,是,则返回用户的选择
如果输入不合法,则程序输出出错信息,并提示用户重新输入选择。
六、测试用例及结果
以下是程序部分功能运行结果的截图:
七、存在的不足与对策及编程体会
存在的不足:
1、我的程序中有一个功能是为用户推荐游览路径,我的主要思想就