校园导游系统课程设计报告

《校园导游系统课程设计报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、南京航空航天大学　　　　　　　　　《数据结构》课程设计报告　　　　　　校园导游系统　　　　　　　　　　　　　　　目录　　　一、需求分析…………………………2　　　　　　二、程序的主要功能…………………2　　三、程序运行平台……………………2　　　　　四、数据结构…………………………2　　　　　五、算法设计思想及时间复杂度……2　　六、测试用例及结果…………………5　　　　七、存在的不足与对策及编程体会…6　　　　八、程序源代码………………………6　　　　　　　　一、需求分析　　南航学生家长及入学新生很需要一

2、个导游程序，来引领他们参观和了解南航。　　　二、程序的主要功能　　1、查询各景点的相关信息　2、查询任意两景点间的所有路径　3、查询任意两景点间的最短路径1、增加景点　4、推荐参观路线2、删除景点　　　5、更新导游信息（操作需管理员密码）3、更新道路信息　　6、对景点联通性的浏览（2阶矩阵表示）4、更新景点信息　　　7、学校全景一览5、修改管理员密码　　　　　三、程序运行平台　　MicrosoftVisualC++6.0　　　四、数据结构　　图的邻接矩阵存储表示，栈的顺序存储表示　　五、算法设计思想及时间复

3、杂度　　　主要函数介绍：　　1、求两点间的所有路径：　　　a)相关函数：　　voiddfs(MGraphG,SqStackpath,int*used,intu,intw);//深度优先遍历　b)主要算法思想：栈的相关操作+深度优先搜索　　　创建一个空栈保存路径，一个空数组保存已标记节点，首先让起点进栈，并标记为已访问，然后调用深度优先搜索，如果该顶点的相邻顶点（即与其有直接通路的顶点）未被访问过就标记为已访问，进栈，然后对它调用深度优先搜索，依次类推，直到获得所有到指定终点的路径。　　c)时间复杂度：O（V

4、E），其中V为图的顶点数目，E为图中边的数目。　2、求两点间的最短路径：　a)相关函数：　voidShortestPath(MGraphG,intv0,intP[][Nmax],int*D);//查询任意两景点间的最短路径　　　voidPrintShortest(MGraphG,intv1,intv2,intP[][Nmax],int*D);//输出最短路径　　b)主要算法思想：迪杰斯特拉算法　　　假设起点为v0，S为已找到的从v0出发的最短路径的终点的集合，其初始状态为空集。而vj为当前求得的从v0出发的

5、最短路径的终点，则将j加到集合S中去，然后修改从v0出发到集合S的补集上任一顶点vk可达的最短路径的长度。重复上两步共n-1次即可。　　　c)时间复杂度：O(V*V*V)，V表示图中的顶点数目。　3、推荐参观路径：　a)相关函数：　　voidRecommentPath(MGraphG);//推荐参观路线　voidNextValue(intk,intn);//生成下一个顶点　　　voidHamiltonian(intk,intn);//搜索所有的回路　　　b)主要算法思想：回溯法求哈密顿回路。　　c)时间复杂

6、度：O（E），其中E为图中边的数目。　4、更改导游信息　　　a)相关函数：　voidMakeChange(MGraph&G,char*pass);//更新导游信息（操作需管理员密码）　voidChangeText(MGraphG,char*pass);//更新文本内容　b)主要算法思想：　　　第一个函数操作需要有管理员权限，初始密码为：1234，不然信息的安全性无法保证。修改后的信息会通过上面第二个函数写入文件，保证下次运行是修改后了的信息。　　特色函数介绍：　1、验证密码正确性及修改密码函数　　　intC

7、onfirmPassword(char*pass);//验证密码是否正确　voidChangePassword(char*pass);//修改管理员密码　　用户输入密码时，程序会自动输出“*”符号，以保证密码不被其他人看到。修改密码时，程序提示用户输入两遍，以验证密码的正确性。　　　所以只有拥有密码的管理员才能够更新导游信息和修改密码。初始密码为：1234.　2、验证输入有效性的函数　　intConfirmChoice(intlow,inthigh);//验证输入是否合法，是,则返回用户的选择　　如果输入不

8、合法，则程序输出出错信息，并提示用户重新输入选择。　六、测试用例及结果　　　　　以下是程序部分功能运行结果的截图：　　　　　　　　　　　　　七、存在的不足与对策及编程体会　　存在的不足：　　1、我的程序中有一个功能是为用户推荐游览路径，我的主要思想就是用回溯法在图中搜索哈密顿回路。即只要沿着该条简单回路，能不重复地游遍全校的景点，就把它当做推荐路线。　2、程序功能还不够强大，比如可以增加一个功能是：允许游客输入大