课程设计故宫导游咨询设计(最短路径).doc

《课程设计故宫导游咨询设计(最短路径).doc》由会员分享，可在线阅读，更多相关《课程设计故宫导游咨询设计(最短路径).doc（37页珍藏版）》请在三一办公上搜索。

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、能模块- 2 -3详细设计- 3 -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修改模块-

3、 22 -6.4插入模块- 23 -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 shortpa

7、th1();/查询到某景点的最短路径。void shortpath2();/查询到所有景点的最短路径。Void main();/主函数。2.2程序模块结构 图2 程序模块结构2.2.1 结构体定义景点的结构体定义如下：struct ding string dingdian; string xinxi;2.3各功能模块录入模块:void Creat()录入景点和路径的信息，并储存。查询景点模块:void select()查找某景点的信息。修改模块:void xiugai()修改某景点的信息。插入模块:void insert()插入新的景点和路径信息。删除模块:void delet()删除景点和路

8、径信息。查询到某景点最佳路径:void shortpath1()：查询到某景点的最短路径。查询到查询到所有景点的最短路径:void shortpath2()查询到所有景点的最短路径3详细设计3.1结构体定义景点的结构体定义如下：struct ding string 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)Ed

9、geij=0;elseEdgeij=MAXweight;numE=0;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+n

10、umE; numV=y+numV;3.4、录入信息void Graph:Creat() int 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(Vert

11、icesi.dingdian=a) coutc;Verticesi.xinxi=c;b+;cout修改成功!endl;if(b=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+) co

12、utv; 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-; else cout不存在该路线!endl; 3.8求到某一景点的路径void Graph:shortpath1() int v,v1; string b,c; coutb; co

13、utc; for(int i=0;inumV;i+)if(Verticesi.dingdian=b)v=i; for( i=0;inumV;i+)if(Verticesi.dingdian=c)v1=i; for( i=0;inumV;i+) disti=Edgevi;si=0;if(i!=v&distiMAXweight)pathi=v;elsepathi=-1; sv=1; distv=0; for(i=0;inumV;i+) float min=MAXweight;int u=v;for(int j=0;jnumV;j+)if(!sj&distjmin)u=j;min=distj;su=

14、1;for(int w=0;wnumV;w+) if(!sw&EdgeuwMAXweight&distu+Edgeuwdistw)distw=distu+Edgeuw;pathw=u; for( i=0;inumV;i+) if(i!=v&i=v1&disti!=MAXweight) string c10; int j=0; int k=i; cout从b到Verticesi.dingdian的; cout最佳路径长度为:; coutdisti米 ; cout大约需要走disti/100分钟 ; cout=1;n-) coutcn; if(n!=1) cout; coutendl; 3.9求到

15、所有景点的路径void Graph:shortpath2() int v; string b; coutb; for(int i=0;inumV;i+)if(Verticesi.dingdian=b)v=i; for( i=0;inumV;i+) disti=Edgevi;si=0;if(i!=v&distiMAXweight)pathi=v;elsepathi=-1; sv=1; distv=0; for(i=0;inumV;i+) float min=MAXweight;int u=v;for(int j=0;jnumV;j+)if(!sj&distjmin)u=j;min=distj;s

16、u=1;for(int w=0;wnumV;w+) if(!sw&EdgeuwMAXweight&distu+Edgeuwdistw)distw=distu+Edgeuw;pathw=u; for( i=0;inumV;i+) if(i!=v&disti!=MAXweight) string c10; int j=0; int k=i; cout从b到Verticesi.dingdian的; cout最佳路径长度为:; coutdisti米 ; cout大约需要走disti/100分钟 ; cout=1;n-) coutcn; if(n!=1) cout; coutendl; 3.10求到所有

17、景点的路径void Graph:shortpath2() int v; string b; coutb; for(int i=0;inumV;i+) if(Verticesi.dingdian=b) v=i; for( i=0;inumV;i+) disti=Edgevi; si=0; if(i!=v&distiMAXweight) pathi=v; elsepathi=-1; sv=1; distv=0; for(i=0;inumV;i+) float min=MAXweight;int u=v;for(int j=0;jnumV;j+)if(!sj&distjmin)u=j;min=dis

18、tj;su=1;for(int w=0;wnumV;w+)if(!sw&EdgeuwMAXweight&distu+Edgeuwdistw)distw=distu+Edgeuw;pathw=u; for( i=0;inumV;i+) if(i!=v&disti!=MAXweight) string c10; int j=0; int k=i; cout从b到Verticesi.dingdian的; cout最佳路径长度为:; coutdisti米 ; cout大约需要走disti/100分钟 ; cout=1;n-) coutcn; if(n!=1) cout; coutendl; 3.11主

19、函数void main() Graph a; for(;) char c; system(cls); cout*endl; cout* 登录! *endl; cout*endl; cout* A、管理员 *endl; cout* B、游客 *endl; cout* C、退出 *endl; cout* 请选择(A、B、C)*endl; cout*c; if(c=A) int d;char b;coutd;if(d=123)for(;)system(cls);cout*endl;cout* 欢迎登陆故宫管理系统 *endl;cout*endl;cout* A、录入景点和路径信息 *endl;cou

20、t* B、修改景点信息 *endl;cout* C、插入景点和路径 *endl;cout* D、删除景点和路径 *endl; cout* E、退出 *endl;cout* 请选择(A、B、C、D、E) *endl;cout*b; if(b=A) a.Creat(); system(pause); if(b=B) a.xiugai(); system(pause);if(b=C)a.insert(); system(pause);if(b=D)a.delet(); system(pause); if(b=E)break;elsecout密码错误!endl;system(pause); if(c=

21、B) char b; for(;) system(cls);cout*endl; cout* 欢迎登陆故宫导游系统 *endl;cout*endl;cout* A、查询信息 *endl;cout* B、查询到景点的最佳路径 *endl;cout* C、查询到所有景点的最佳路径 *endl; cout* D、退出 *endl;cout* 请选择(A、B、C、D) *endl;cout*b;if(b=A) a.select(); system(pause); if(b=B)a.shortpath1();system(pause);if(b=C)a.shortpath2();system(pause

22、);if(b=D)break; if(c=C) break; 4 调试分析4.1测试数据测试数据见图1.4.2调试问题 在调试过程中遇到输出路径算法有错误，当删除一条路径时时不能正确输出相应路径，然后对输出路径的条件进行改进，增加了条件，测试成功。 4.3算法时间复杂度录入：时间复杂度为O(n);查询景点信息: 时间复杂度为O(n);修改景点信息: 时间复杂度为O(n);插入景点和路径: 当插入的景点和路径为x，y时，若x=y时间复杂度为O(x)反之为O(y);删除景点和路径: 当删除的景点和路径为x，y时，若x=y时间复杂度为O(x)反之为O(y);查询到某景点最佳路径；此算法为迪杰斯特拉算

23、法时间复杂度为O(n*n);查询到所有景点的最短路径: 此算法为迪杰斯特拉算法时间复杂度为O(n*n);4.4经验和体会在本次课程设计中主要是对图的数据结构操作，所有刚开始对知识不是很熟悉操作起来有一定难度，容易在程序的关键地方但经过翻阅教材能较好的解决问题。5用户使用说明本系统是关于故宫的管理系统分为两类用户，管理员和游客，由于管理员可以对数据进行修改，为了保护数据，所以管理员登陆需要密码而游客不需要密码，管理员有添加景点和路径、删除景点和路径、修改景点信息权限，游客能查询景点信息、查找到某一景点的最佳路径和到所有景点的最佳路径。6测试结果6.1录入信息 图3 录入信息界面 图4 录入信息界

24、面6.2查询景点模块 图5 查询景点信息界面6.3修改模块 图6 修改景点信息界面6.4插入模块 图7 添加景点信息界面6.5删除模块 图8 删除景点信息界面6.6查询到某景点最佳路径 图9 查询到某景点最佳路径界面6.7查询到所有景点的最短路径。 图10 查询到所有景点最佳路径界面结 论 本次课程设计“故宫导游咨询”按照任务书相应的要求成功的完成了任务，由于本课程设计涉及景点和路径，采用图的储存结构和算法比较方便处理数据的储存、查询、删除等操作。但图的操作比较难，比如求某景点到所有景点的最佳路径问题，需要使用到迪杰斯特拉算法实现。 致 谢 在本次课程设计过程中，首先感谢辅导老师周立章，在数据

25、结构课堂上为课程设计需要的前期知识打下了基础，在课程设计过程中抽出休息时间来做相应的课程设计指导。同时在这次课程设计中，也要感谢许多乐意同学对我不懂的地方的指导和耐心讲解。参考文献 1 严蔚敏，吴伟民.数据结构.清华大学出版社出版。 2 严蔚敏，吴伟民. 数据结构题集(C语言版) .清华大学出版社.2003年5月。3 杨秀金，数据结构(C+版) .高等教育出版社.2009年4月。4 朱战立.数据结构(C+语言描述)（第二版本）.高等出版社出版.2004年4月。5 胡学钢.数据结构(C语言版) .高等教育出版社.2004年8月。6 杨金秀.数据结构（C语言版）.西安电子科技大学出版社，2004年

26、8月。 Employment tribunals sort out disagreements between employers and employees.You may need to make a claim to an employment tribunal if: you dont agree with the disciplinary action your employer has taken against you your employer dismisses you and you think that you have been dismissed unfairly.F

27、or more information about dismissal and unfair dismissal, seeDismissal.You can make a claim to an employment tribunal, even if you haventappealedagainst the disciplinary action your employer has taken against you. However, if you win your case, the tribunal may reduce any compensation awarded to you

28、 as a result of your failure to appeal.Remember that in most cases you must make an application to an employment tribunal within three months of the date when the event you are complaining about happened. If your application is received after this time limit, the tribunal will not usually accept it.

29、If you are worried about how the time limits apply to you, take advice from one of the organisations listed underFurther help.Employment tribunals are less formal than some other courts, but it is still a legal process and you will need to give evidence under an oath or affirmation.Most people find

30、making a claim to an employment tribunal challenging. If you are thinking about making a claim to an employment tribunal, you should get help straight away from one of the organisations listed underFurther help.If you are being represented by a solicitor at the tribunal, they may ask you to sign an

31、agreement where you pay their fee out of your compensation if you win the case. This is known as adamages-based agreement. In England and Wales, your solicitor cant charge you more than 35% of your compensation if you win the case.If you are thinking about signing up for a damages-based agreement, yo