数据结构课程设计故宫导游(最短路径)(34页).doc
-数学与计算机学院课程设计说明书课 程 名 称: 数据结构与算法课程设计 课 程 代 码: 6014389 题 目: 故宫导游咨询 年级/专业/班: 学 生 姓 名: 学 号: 开 始 时 间: 2011 年 12 月 9 日完 成 时 间: 2011 年 12 月 23 日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5） 说明书（计算书、图纸、分析报告）撰写质量（45）总 分（100）指导教师签名： 年 月 日-第 - 30 - 页-目录引 言- 4 -1、需求分析- 4 -1.1任务与分析- 4 -2 概要设计- 1 -2.1 ADT描述- 1 -2.2程序模块结构- 2 -2.3各功能模块- 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修改模块- 22 -6.4插入模块- 23 -6.5删除模块- 24 -6.6查询到某景点最佳路径- 25 -6.7查询到所有景点的最短路径。- 26 -结 论- 28 -致 谢- 29 -参考文献- 30 -摘 要随着计算机的普及，涉及计算机相关的科目也越来越普遍，其中数据结构是计算机专业重要的专业基础课程与核心课程之一，为适应我国计算机科学技术的发展和应用，学好数据结构非常必要，然而要掌握数据结构的知识非常难，所以对“数据结构”的课程设计比不可少。本说明书是对“故宫导游咨询”课程设计的说明。首先是对需求分析的简要阐述，说明系统要完成的任务和相应的分析，并给出测试数据。其次是概要设计，说明所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次关系，以及ADT描述。然后是详细设计，描述实现概要设计中定义的基本功操作和所有数据类型，以及函数的功能及代码实现。再次是对系统的调试分析说明，以及遇到的问题和解决问题的方法。然后是用户使用说明书的阐述，然后是测试的数据和结果的分析，最后是对本次课程设计的结论。关键词：计算机、课程设计、数据结构 引 言 数据结构是计算机专业重要的专业基础课程与核心课程之一，在计算机领域应用广泛，计算机离不开数据结构。数据结构课程设计为了能使我们掌握所学习的知识并有应用到实际的设计中的能力，对于掌握这门课程的学习方法有极大的意义。本课程设计的题目为“故宫导游咨询”，完成相应的录入信息、查找、修改、删除、计算功能等等。本课程设计采用的编程环境为Microsoft Visual Stdio 6.0。1、需求分析 游客游览某一景点时，对景点都不熟悉。特别是对于象故宫这样的大型景点，如果随便参观的话，可能会错过一些景点，也可能走许多冤枉路。为了方便游客，需要一套软件系统，能够为游客提供：查询景点信息，给出到某个景点的最佳路线，给出到所有景点的最佳路线。为系统管理员提供以下功能：添加和撤销景点，添加和撤销旅游线路，修改景点信息。 1.1任务与分析 此系统要完成对故宫景点信息的储存、修改、删除、添加和查询最短路线，因为涉及到最短路线问题，所以数据结构优先考虑采用图的邻接矩阵储存结构，景点和旅游线路可以构成图状结构，景点作为图的顶点，旅游线路作为图的边，边上的权值作为景点间的距离。此结构便于完成任务的各种操作。1.2测试数据 图1 测试数据2 概要设计 2.1 ADT描述 ADT Graph数据对象：D故宫景点和路径数据关系：RVRVR=<v,w>|v,wV，<v,w>表示顶点v和顶点w之间的边；基本操作： void Creat();/录入景点和路径的信息。void select();/查找某景点的信息。void xiugai();/修改某景点的信息。void insert();/插入新的景点和路径信息。void delet();/删除景点和路径信息。void shortpath1();/查询到某景点的最短路径。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()删除景点和路径信息。查询到某景点最佳路径:void shortpath1()：查询到某景点的最短路径。查询到查询到所有景点的最短路径:void shortpath2()查询到所有景点的最短路径3详细设计3.1结构体定义景点的结构体定义如下：struct ding string dingdian; string xinxi;3.2 初始化构造函数初始化变量：Graph:Graph() for(int i=0;i<MAXVertices;i+) Verticesi.dingdian="0" for(i=0;i<MAXVertices;i+) for(int j=0;j<MAXVertices;j+)if(i=j)Edgeij=0;elseEdgeij=MAXweight;numE=0;numV=0;3.3 插入操作插入路径和景点信息： void Graph:insert() int i,vi,vj,w,x,y; cout<<"输入添加路径的条数和景点数：" cin>>x>>y; cout<<"输入添加景点名称:"<<endl; for(i=0;i<y;i+) cout<<numV+i+1<<":"cin>>VerticesnumV+i.dingdian;cout<<" "<<"景点信息:"cin>>VerticesnumV+i.xinxi;cout<<"添加成功!"<<endl; for(i=0;i<x;i+) cout<<"输入添加景点到景点的路径的长度(vi,vj,length):" cin>>vi>>vj>>w; Edgevi-1vj-1=w; Edgevj-1vi-1=w; cout<<"添加成功!"<<endl; numE=x+numE; numV=y+numV;3.4、录入信息void Graph:Creat() int i,vi,vj,w; cout<<"输入路径的条数数和景点数：" cin>>numE>>numV; cout<<"输入景点名称:"<<endl; for(i=0;i<numV;i+) cout<<i+1<<":"cin>>Verticesi.dingdian;cout<<"景点信息:"cin>>Verticesi.xinxi; for(i=0;i<numE;i+) cout<<"输入景点到景点的路径的长度(vi,vj,length):" cin>>vi>>vj>>w; Edgevi-1vj-1=w; Edgevj-1vi-1=w; 3.5修改操作void Graph:xiugai() string a,c; int b=0; cout<<"请输入要修改的景点:" cin>>a; for(int i=0;i<numV;i+) if(Verticesi.dingdian=a) cout<<"请重新输入景点信息:"cin>>c;Verticesi.xinxi=c;b+;cout<<"修改成功!"<<endl;if(b=0)cout<<"不存在该景点！"<<endl;3.6查询操作void Graph:select() string a; int b=0; cout<<"请输入要查询的景点:" cin>>a; for(int i=0;i<numV;i+)if(Verticesi.dingdian=a)cout<<Verticesi.xinxi<<endl;b+;if(b=0)cout<<"不存在该景点！"<<endl;3.7删除操作void Graph:delet() int x,y,z,k,v; cout<<"请你输入要撤销景点数和路线条数:" cin>>k>>z; for(int j=0;j<k;j+) cout<<"请输入要撤销的景点编号:" cin>>v; for(int i=0;i<numV;i+) if(i!=v-1) Edgev-1i=MAXweight;Edgeiv-1=MAXweight; cout<<"撤销成功!"<<endl; for(int i=0;i<z;i+) cout<<"请输入要撤销的旅游路线的景点编号(vi,vj):" cin>>x>>y; 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; cout<<"输入你所在的景点:" cin>>b; cout<<"输入你所要去的景点:" cin>>c; for(int i=0;i<numV;i+)if(Verticesi.dingdian=b)v=i; for( i=0;i<numV;i+)if(Verticesi.dingdian=c)v1=i; for( i=0;i<numV;i+) disti=Edgevi;si=0;if(i!=v&&disti<MAXweight)pathi=v;elsepathi=-1; sv=1; distv=0; for(i=0;i<numV;i+) float min=MAXweight;int u=v;for(int j=0;j<numV;j+)if(!sj&&distj<min)u=j;min=distj;su=1;for(int w=0;w<numV;w+) if(!sw&&Edgeuw<MAXweight&&distu+Edgeuw<distw)distw=distu+Edgeuw;pathw=u; for( i=0;i<numV;i+) if(i!=v&&i=v1&&disti!=MAXweight) string c10; int j=0; int k=i; cout<<"从"<<b<<"到"<<Verticesi.dingdian<<"的" cout<<"最佳路径长度为:" cout<<disti<<"米"<<" " cout<<"大约需要走"<<disti/100<<"分钟"<<" " cout<<"路径为:" doj+; cj=Verticesk.dingdian; k=pathk; while(k!=v); j+; cj=Verticesk.dingdian; for(int n=j;n>=1;n-) cout<<cn; if(n!=1) cout<<"->" cout<<endl; 3.9求到所有景点的路径void Graph:shortpath2() int v; string b; cout<<"输入你所在的景点:" cin>>b; for(int i=0;i<numV;i+)if(Verticesi.dingdian=b)v=i; for( i=0;i<numV;i+) disti=Edgevi;si=0;if(i!=v&&disti<MAXweight)pathi=v;elsepathi=-1; sv=1; distv=0; for(i=0;i<numV;i+) float min=MAXweight;int u=v;for(int j=0;j<numV;j+)if(!sj&&distj<min)u=j;min=distj;su=1;for(int w=0;w<numV;w+) if(!sw&&Edgeuw<MAXweight&&distu+Edgeuw<distw)distw=distu+Edgeuw;pathw=u; for( i=0;i<numV;i+) if(i!=v&&disti!=MAXweight) string c10; int j=0; int k=i; cout<<"从"<<b<<"到"<<Verticesi.dingdian<<"的" cout<<"最佳路径长度为:" cout<<disti<<"米"<<" " cout<<"大约需要走"<<disti/100<<"分钟"<<" " cout<<"路径为:" doj+; cj=Verticesk.dingdian; k=pathk; while(k!=v); j+; cj=Verticesk.dingdian; for(int n=j;n>=1;n-) cout<<cn; if(n!=1) cout<<"->" cout<<endl; 3.10求到所有景点的路径void Graph:shortpath2() int v; string b; cout<<"输入你所在的景点:" cin>>b; for(int i=0;i<numV;i+) if(Verticesi.dingdian=b) v=i; for( i=0;i<numV;i+) disti=Edgevi; si=0; if(i!=v&&disti<MAXweight) pathi=v; elsepathi=-1; sv=1; distv=0; for(i=0;i<numV;i+) float min=MAXweight;int u=v;for(int j=0;j<numV;j+)if(!sj&&distj<min)u=j;min=distj;su=1;for(int w=0;w<numV;w+)if(!sw&&Edgeuw<MAXweight&&distu+Edgeuw<distw)distw=distu+Edgeuw;pathw=u; for( i=0;i<numV;i+) if(i!=v&&disti!=MAXweight) string c10; int j=0; int k=i; cout<<"从"<<b<<"到"<<Verticesi.dingdian<<"的" cout<<"最佳路径长度为:" cout<<disti<<"米"<<" " cout<<"大约需要走"<<disti/100<<"分钟"<<" " cout<<"路径为:" doj+; cj=Verticesk.dingdian; k=pathk; while(k!=v); j+; cj=Verticesk.dingdian; for(int n=j;n>=1;n-) cout<<cn; if(n!=1) cout<<"->" cout<<endl; 3.11主函数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<<"*"<<endl; cin>>c; if(c='A') int d;char b;cout<<"请输入密码:"cin>>d;if(d=123)for(;)system("cls");cout<<"*"<<endl;cout<<"* 欢迎登陆故宫管理系统 *"<<endl;cout<<"*"<<endl;cout<<"* A、录入景点和路径信息 *"<<endl;cout<<"* B、修改景点信息 *"<<endl;cout<<"* C、插入景点和路径 *"<<endl;cout<<"* D、删除景点和路径 *"<<endl; cout<<"* E、退出 *"<<endl;cout<<"* 请选择(A、B、C、D、E) *"<<endl;cout<<"*"<<endl;cin>>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='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<<"*"<<endl;cin>>b;if(b='A') a.select(); system("pause"); if(b='B')a.shortpath1();system("pause");if(b='C')a.shortpath2();system("pause");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);查询到某景点最佳路径；此算法为迪杰斯特拉算法时间复杂度为O(n*n);查询到所有景点的最短路径: 此算法为迪杰斯特拉算法时间复杂度为O(n*n);4.4经验和体会在本次课程设计中主要是对图的数据结构操作，所有刚开始对知识不是很熟悉操作起来有一定难度，容易在程序的关键地方但经过翻阅教材能较好的解决问题。5用户使用说明本系统是关于故宫的管理系统分为两类用户，管理员和游客，由于管理员可以对数据进行修改，为了保护数据，所以管理员登陆需要密码而游客不需要密码，管理员有添加景点和路径、删除景点和路径、修改景点信息权限，游客能查询景点信息、查找到某一景点的最佳路径和到所有景点的最佳路径。6测试结果6.1录入信息 图3 录入信息界面 图4 录入信息界面6.2查询景点模块 图5 查询景点信息界面6.3修改模块 图6 修改景点信息界面6.4插入模块 图7 添加景点信息界面6.5删除模块 图8 删除景点信息界面6.6查询到某景点最佳路径 图9 查询到某景点最佳路径界面6.7查询到所有景点的最短路径。 图10 查询到所有景点最佳路径界面结 论 本次课程设计“故宫导游咨询”按照任务书相应的要求成功的完成了任务，由于本课程设计涉及景点和路径，采用图的储存结构和算法比较方便处理数据的储存、查询、删除等操作。但图的操作比较难，比如求某景点到所有景点的最佳路径问题，需要使用到迪杰斯特拉算法实现。 致 谢 在本次课程设计过程中，首先感谢辅导老师周立章，在数据结构课堂上为课程设计需要的前期知识打下了基础，在课程设计过程中抽出休息时间来做相应的课程设计指导。同时在这次课程设计中，也要感谢许多乐意同学对我不懂的地方的指导和耐心讲解。参考文献 1 严蔚敏，吴伟民.数据结构.清华大学出版社出版。 2 严蔚敏，吴伟民. 数据结构题集(C语言版) .清华大学出版社.2003年5月。3 杨秀金，数据结构(C+版) .高等教育出版社.2009年4月。4 朱战立.数据结构(C+语言描述)（第二版本）.高等出版社出版.2004年4月。5 胡学钢.数据结构(C语言版) .高等教育出版社.2004年8月。6 杨金秀.数据结构（C语言版）.西安电子科技大学出版社，2004年8月。
