《数据结构课程设计汇本故宫导游最短路径》由会员分享，可在线阅读，更多相关《数据结构课程设计汇本故宫导游最短路径（34页珍藏版）》请在金锄头文库上搜索。
1、 数学与计算机学院课程设计说明书课 程 名 称:数据结构与算法课程设计 课 程 代 码: 6014389 题 目:故宫导游咨询年级/专业/班:学 生 姓 名:学 号:开 始 时 间:2011 年12月 9日完 成 时 间:2011年12月23日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5） 说明书（计算书、图纸、分析报告）撰写质量（45）总 分（100）指导教师签名：年月日 / 目录引言- 4 -1、需求分析- 4 -1.1任务与分析- 4 -2 概要设计- 1 -2.1 ADT描述- 1 -2.2程序模块结构- 2 -2.3各功能模块- 2 -3详细设计- 3
2、-3.1结构体定义- 3 -3.2 初始化- 3 -3.3 插入操作- 4 -3.4、录入信息- 4 -3.5修改操作- 5 -3.6查询操作- 6 -3.7删除操作- 6 -3.8求到某一景点的路径- 8 -3.9求到所有景点的路径- 10 -3.10求到所有景点的路径- 12 -3.11主函数- 15 -4 调试分析- 18 -4.1测试数据- 19 -4.2调试问题- 19 -4.3算法时间复杂度- 19 -4.4经验和体会- 19 -5用户使用说明- 19 -6测试结果- 19 -6.1录入信息- 19 -6.2查询景点模块- 21 -6.3修改模块- 22 -6.4插入模块- 23
3、-6.5删除模块- 24 -6.6查询到某景点最佳路径- 25 -6.7查询到所有景点的最短路径。- 26 -结论- 28 -致谢- 29 -参考文献- 30 -摘 要随着计算机的普及，涉及计算机相关的科目也越来越普遍，其中数据结构是计算机专业重要的专业基础课程与核心课程之一，为适应我国计算机科学技术的发展和应用，学好数据结构非常必要，然而要掌握数据结构的知识非常难，所以对“数据结构”的课程设计比不可少。本说明书是对“故宫导游咨询”课程设计的说明。首先是对需求分析的简要阐述，说明系统要完成的任务和相应的分析，并给出测试数据。其次是概要设计，说明所有抽象数据类型的定义、主程序的流程以及各程序模块
4、之间的层次关系，以及ADT描述。然后是详细设计，描述实现概要设计中定义的基本功操作和所有数据类型，以及函数的功能及代码实现。再次是对系统的调试分析说明，以及遇到的问题和解决问题的方法。然后是用户使用说明书的阐述，然后是测试的数据和结果的分析，最后是对本次课程设计的结论。关键词：计算机、课程设计、数据结构引 言数据结构是计算机专业重要的专业基础课程与核心课程之一，在计算机领域应用广泛，计算机离不开数据结构。数据结构课程设计为了能使我们掌握所学习的知识并有应用到实际的设计中的能力，对于掌握这门课程的学习方法有极大的意义。本课程设计的题目为“故宫导游咨询”，完成相应的录入信息、查找、修改、删除、计算
5、功能等等。本课程设计采用的编程环境为Microsoft Visual Stdio 6.0。1、需求分析游客游览某一景点时，对景点都不熟悉。特别是对于象故宫这样的大型景点，如果随便参观的话，可能会错过一些景点，也可能走许多冤枉路。为了方便游客，需要一套软件系统，能够为游客提供：查询景点信息，给出到某个景点的最佳路线，给出到所有景点的最佳路线。为系统管理员提供以下功能：添加和撤销景点，添加和撤销旅游线路，修改景点信息。1.1任务与分析此系统要完成对故宫景点信息的储存、修改、删除、添加和查询最短路线，因为涉及到最短路线问题，所以数据结构优先考虑采用图的邻接矩阵储存结构，景点和旅游线路可以构成图状结构
6、，景点作为图的顶点，旅游线路作为图的边，边上的权值作为景点间的距离。此结构便于完成任务的各种操作。1.2测试数据 图1 测试数据2 概要设计2.1 ADT描述 ADT Graph数据对象：D故宫景点和路径数据关系：RVRVR=|v,wV，表示顶点v和顶点w之间的边；基本操作：void Creat();/录入景点和路径的信息。void select();/查找某景点的信息。void xiugai();/修改某景点的信息。void insert();/插入新的景点和路径信息。void delet();/删除景点和路径信息。void shortpath1();/查询到某景点的最短路径。void sh
7、ortpath2();/查询到所有景点的最短路径。Void main();/主函数。2.2程序模块结构 图2 程序模块结构2.2.1 结构体定义景点的结构体定义如下：struct dingstring dingdian;string xinxi;2.3各功能模块录入模块:void Creat()录入景点和路径的信息，并储存。查询景点模块:void select()查找某景点的信息。修改模块:void xiugai()修改某景点的信息。插入模块:void insert()插入新的景点和路径信息。删除模块:void delet()删除景点和路径信息。查询到某景点最佳路径:void shortpat
8、h1()：查询到某景点的最短路径。查询到查询到所有景点的最短路径:void shortpath2()查询到所有景点的最短路径3详细设计3.1结构体定义景点的结构体定义如下：struct dingstring dingdian;string xinxi;3.2 初始化构造函数初始化变量：Graph:Graph()for(int i=0;iMAXVertices;i+)Verticesi.dingdian=0;for(i=0;iMAXVertices;i+)for(int j=0;jMAXVertices;j+)if(i=j)Edgeij=0;elseEdgeij=MAXweight;numE=0
9、;numV=0;3.3 插入操作插入路径和景点信息：void Graph:insert()int i,vi,vj,w,x,y;coutxy;cout输入添加景点名称:endl;for(i=0;iy;i+)coutnumV+i+1VerticesnumV+i.dingdian;cout VerticesnumV+i.xinxi;cout添加成功!endl;for(i=0;ix;i+)coutvivjw;Edgevi-1vj-1=w;Edgevj-1vi-1=w;cout添加成功!endl;numE=x+numE;numV=y+numV;3.4、录入信息void Graph:Creat()int
10、i,vi,vj,w;coutnumEnumV;cout输入景点名称:endl;for(i=0;inumV;i+)couti+1Verticesi.dingdian;coutVerticesi.xinxi;for(i=0;inumE;i+)coutvivjw;Edgevi-1vj-1=w;Edgevj-1vi-1=w;3.5修改操作void Graph:xiugai()string a,c;int b=0;couta;for(int i=0;inumV;i+)if(Verticesi.dingdian=a)coutc;Verticesi.xinxi=c;b+;cout修改成功!endl;if(b
11、=0)cout不存在该景点！endl;3.6查询操作void Graph:select()string a;int b=0;couta;for(int i=0;inumV;i+)if(Verticesi.dingdian=a)coutVerticesi.xinxiendl;b+;if(b=0)cout不存在该景点！endl;3.7删除操作void Graph:delet()int x,y,z,k,v;coutkz;for(int j=0;jk;j+)coutv; for(int i=0;inumV;i+) if(i!=v-1) Edgev-1i=MAXweight;Edgeiv-1=MAXweight; cout撤销成功!endl;for(int i=0;iz;i+)coutxy;if(Edgex-1y-1!=MAXweight)Edgex-1y-1=MAXweight;Edgey-1x-1=MAXweight;cout撤销成功!endl;numE-;elsecout不存在该路线!endl;3.8求到某一景点的路径void Graph:shortpath1()int v,v1;string b,c;coutb;coutc;for(int i=0;inumV;i+)if(Verticesi.dingdian=b)v=i;for( i=0;inumV;i+)if(Vertices
