数据结构课程设计-故宫导游咨询(最短路径)

数学与计算机学院课程设计说明书课程名称数据结构与算法课程设计课程代码6014389题目故宫导游咨询年级/专业/班学生姓名学号开始时间2011年12月9日完成时间2011年12月23日课程设计成绩学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书（计算书、图纸、分析报告）撰写质量（45）总分（100）指导教师签名年月日目录引言41、需求分析411任务与分析42概要设计121ADT描述122程序模块结构223各功能模块23详细设计331结构体定义332初始化333插入操作434、录入信息435修改操作536查询操作637删除操作638求到某一景点的路径839求到所有景点的路径10310求到所有景点的路径12311主函数154调试分析1841测试数据1942调试问题1943算法时间复杂度1944经验和体会195用户使用说明196测试结果1961录入信息1962查询景点模块2163修改模块2264插入模块2365删除模块2466查询到某景点最佳路径2567查询到所有景点的最短路径。26结论28致谢29参考文献30摘要随着计算机的普及，涉及计算机相关的科目也越来越普遍，其中数据结构是计算机专业重要的专业基础课程与核心课程之一，为适应我国计算机科学技术的发展和应用，学好数据结构非常必要，然而要掌握数据结构的知识非常难，所以对“数据结构”的课程设计比不可少。本说明书是对“故宫导游咨询”课程设计的说明。首先是对需求分析的简要阐述，说明系统要完成的任务和相应的分析，并给出测试数据。其次是概要设计，说明所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次关系，以及ADT描述。然后是详细设计，描述实现概要设计中定义的基本功操作和所有数据类型，以及函数的功能及代码实现。再次是对系统的调试分析说明，以及遇到的问题和解决问题的方法。然后是用户使用说明书的阐述，然后是测试的数据和结果的分析，最后是对本次课程设计的结论。关键词计算机、课程设计、数据结构引言数据结构是计算机专业重要的专业基础课程与核心课程之一，在计算机领域应用广泛，计算机离不开数据结构。数据结构课程设计为了能使我们掌握所学习的知识并有应用到实际的设计中的能力，对于掌握这门课程的学习方法有极大的意义。本课程设计的题目为“故宫导游咨询”，完成相应的录入信息、查找、修改、删除、计算功能等等。本课程设计采用的编程环境为MICROSOFTVISUALSTDIO60。1、需求分析游客游览某一景点时，对景点都不熟悉。特别是对于象故宫这样的大型景点，如果随便参观的话，可能会错过一些景点，也可能走许多冤枉路。为了方便游客，需要一套软件系统，能够为游客提供查询景点信息，给出到某个景点的最佳路线，给出到所有景点的最佳路线。为系统管理员提供以下功能添加和撤销景点，添加和撤销旅游线路，修改景点信息。11任务与分析此系统要完成对故宫景点信息的储存、修改、删除、添加和查询最短路线，因为涉及到最短路线问题，所以数据结构优先考虑采用图的邻接矩阵储存结构，景点和旅游线路可以构成图状结构，景点作为图的顶点，旅游线路作为图的边，边上的权值作为景点间的距离。此结构便于完成任务的各种操作。12测试数据图1测试数据2概要设计21ADT描述ADTGRAPH数据对象D故宫景点和路径数据关系RVRVR|V,WV，表示顶点V和顶点W之间的边；基本操作VOIDCREAT/录入景点和路径的信息。VOIDSELECT/查找某景点的信息。VOIDXIUGAI/修改某景点的信息。VOIDINSERT/插入新的景点和路径信息。VOIDDELET/删除景点和路径信息。VOIDSHORTPATH1/查询到某景点的最短路径。VOIDSHORTPATH2/查询到所有景点的最短路径。VOIDMAIN/主函数。22程序模块结构登陆判断输入密码游客管理员修改景点信息删除景点和路径信息添加景点和路径信息退出查询到所有景点的最佳路径查询到某景点最佳路径查询景点信息录入信息正确错误退出退出图2程序模块结构221结构体定义景点的结构体定义如下STRUCTDINGSTRINGDINGDIANSTRINGXINXI23各功能模块录入模块VOIDCREAT录入景点和路径的信息，并储存。查询景点模块VOIDSELECT查找某景点的信息。修改模块VOIDXIUGAI修改某景点的信息。插入模块VOIDINSERT插入新的景点和路径信息。删除模块VOIDDELET删除景点和路径信息。查询到某景点最佳路径VOIDSHORTPATH1查询到某景点的最短路径。查询到查询到所有景点的最短路径VOIDSHORTPATH2查询到所有景点的最短路径3详细设计31结构体定义景点的结构体定义如下STRUCTDINGSTRINGDINGDIANSTRINGXINXI32初始化构造函数初始化变量GRAPHGRAPHFORINTI0IXYCOUTVERTICESNUMVIDINGDIANCOUTVERTICESNUMVIXINXICOUTVIVJWEDGEVI1VJ1WEDGEVJ1VI1WCOUTNUMENUMVCOUTVERTICESIDINGDIANCOUTVERTICESIXINXIFORI0IVIVJWEDGEVI1VJ1WEDGEVJ1VI1W35修改操作VOIDGRAPHXIUGAISTRINGA,CINTB0COUTAFORINTI0ICVERTICESIXINXICBCOUTAFORINTI0IKZFORINTJ0JVFORINTI0IXYIFEDGEX1Y1MAXWEIGHTEDGEX1Y1MAXWEIGHTEDGEY1X1MAXWEIGHTCOUTBCOUTCFORINTI0I1NCOUT“COUTBFORINTI0I1NCOUT“COUTBFORINTI0I1NCOUT“COUTCIFCAINTDCHARBCOUTDIFD123FORSYSTEM“CLS“COUTBIFBAACREATSYSTEM“PAUSE“IFBBAXIUGAISYSTEM“PAUSE“IFBCAINSERTSYSTEM“PAUSE“IFBDADELETSYSTEM“PAUSE“IFBEBREAKELSECOUTBIFBAASELECTSYSTEM“PAUSE“IFBBASHORTPATH1SYSTEM“PAUSE“IFBCASHORTPATH2SYSTEM“PAUSE“IFBDBREAKIFCCBREAK4调试分析41测试数据测试数据见图142调试问题在调试过程中遇到输出路径算法有错误，当删除一条路径时时不能正确输出相应路径，然后对输出路径的条件进行改进，增加了条件，测试成功。43算法时间复杂度录入时间复杂度为ON查询景点信息时间复杂度为ON修改景点信息时间复杂度为ON插入景点和路径当插入的景点和路径为X，Y时，若XY时间复杂度为OX反之为OY删除景点和路径当删除的景点和路径为X，Y时，若XY时间复杂度为OX反之为OY查询到某景点最佳路径；此算法为迪杰斯特拉算法时间复杂度为ONN查询到所有景点的最短路径此算法为迪杰斯特拉算法时间复杂度为ONN44经验和体会在本次课程设计中主要是对图的数据结构操作，所有刚开始对知识不是很熟悉操作起来有一定难度，容易在程序的关键地方但经过翻阅教材能较好的解决问题。5用户使用说明本系统是关于故宫的管理系统分为两类用户，管理员和游客，由于管理员可以对数据进行修改，为了保护数据，所以管理员登陆需要密码而游客不需要密码，管理员有添加景点和路径、删除景点和路径、修改景点信息权限，游客能查询景点信息、查找到某一景点的最佳路径和到所有景点的最佳路径。6测试结果61录入信息图3录入信息界面图4录入信息界面62查询景点模块图5查询景点信息界面63修改模块图6修改景点信息界面64插入模块图7添加景点信息界面65删除模块图8删除景点信息界面66查询到某景点最佳路径图9查询到某景点最佳路径界面67查询到所有景点的最短路径。图10查询到所有景点最佳路径界面结论本次课程设计“故宫导游咨询”按照任务书相应的要求成功的完成了任务，由于本课程设计涉及景点和路径，采用图的储存结构和算法比较方便处理数据的储存、查询、删除等操作。但图的操作比较难，比如求某景点到所有景点的最佳路径问题，需要使用到迪杰斯特拉算法实现。致谢在本次课程设计过程中，首先感谢辅导老师周立章，在数据结构课堂上为课程设计需要的前期知识打下了基础，在课程设计过程中抽出休息时间来做相应的课程设计指导。同时在这次课程设计中，也要感谢许多乐意同学对我不懂的地方的指导