校园导游咨询课程设计报告

淮 海 工 学 院 计算机工程学院课程设计报告设计名称： 数据结构课程设计 选题名称： 校园导游咨询 姓 名： 李晨 学 号： 2012122663 专业班级： 计算机科学与技术 网络 122 班 系 （ 院）： 计算机工程学院 设计时间： 2013.12.232013.1.3 设计地点： 软件工程实验室、教室 指导教师评语：签名： 成绩：年 月 日数据结构课程设计报告 第 1 页，共 25 页1课程设计目的1、训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。 2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4.训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。2课程设计任务与要求：任务根据教材数据结构-C 语言描述 （耿国华主编）和参考书数据结构题集（C 语言版） （严蔚敏、吴伟民主编）选择课程设计题目，要求通过设计，在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。设计题目从任务书所列选题表中选取，每班每题不得超过 2 人。学生自选课题学生原则上可以结合个人爱好自选课题，要求课题有一定的深度与难度，有一定的算法复杂性，能够巩固数据结构课程所学的知识。学生自选课题需在 18 周前报课程设计指导教师批准方可生效。要求：1、在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。前期准备工作完备与否直接影响到后序上机调试工作的效率。在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率。 2、.设计的题目要求达到一定工作量（300 行以上代码） ，并具有一定的深度和难度。3、程序设计语言推荐使用 C/C+，程序书写规范，源程序需加必要的注释;4、每位同学需提交可独立运行的程序；5 、每位同学需独立提交设计报告书（每人一份） ，要求编排格式统一、规范、内容充实，不少于 10 页（代码不算） ；6、课程设计实践作为培养学生动手能力的一种手段，单独考核。数据结构课程设计报告 第 2 页，共 25 页3课程设计说明书一 需求分析用无向网表示淮海工学院的校园景点平面图，图中顶点表示主要景点，存放景点编号、名称、简介等信息，图中边表示景点间的道路，存放路径长度信息。 基本要求 （1） 查询各景点的相关信息；（2） 查询图中任意两个景点间的最短路径（3） 查询图中任意两个景点间的所有路径1. 淮海工学院的平面图上选取 13 个具有代表性的景点,抽象成一个无向带权图.以图中顶点表示校内各景点，存放景点名称，代号，简介等信息；以边表示路径，存放路径长度等信息。2. 本程序的目的是为用户提供路径咨询.根据用户指定的景点输出景点信息。3. 根据用户指定的始点和终点输出相应的路径,即查询任意两个景点之间的一条最短的简单路径。4. 测试数据.二 概要设计1抽象数据类型图的定义如下：（书上 157 页）ADT Graph数据对象 V：V 是具有相同特性的数据元素的集合，称为顶点集。数据关系 R：R=VRVR=（v,w）v,wV,(v,w)表示 v 和 w 之间存在路径基本操作 P：CreateUND(V,VR)初始条件:v 是图的顶点集,a 是图中边的集合.操作结果:按 v 和 a 的定义构造图 G. output(V,W)初始条件：图 G 存在，V 和 W 中顶点。操作结果：若输入的 V 和 W 不重合且存在最短路径，则返回两顶点之间的最短路径；否则返回其他信息。Searchpath1(G) 初始条件：图 G 存在。操作结果：以 V 为起点遍历输出所有可以到达 W 点的路径。path(G，V,，W,K)初始条件：图 G 存在，V 和 W，K 是 G 中顶点,且 V 为起始点，W 为要查询的终点，K 是路径上的顶点序号。操作结果：确定路径上 K+1 个顶点序号。 disppath(G,V，W)初始条件：图 G 存在，V，W 是图中顶点。操作结果：通过调用 path 函数，找到从 V 到 W 的所有路径并输出ShortestPath(V)初始条件：图 G 存在，V 是 G 中一条边的顶点。操作结果：若存在路径，则返回以努 V 为入口点的一条最短路径，否则返回其他信息。数据结构课程设计报告 第 3 页，共 25 页ADT Graph2.主程序void main()初始化；do接受命令（输入景点信息或输出最短路径） ；处理命令；while（“命令”！=“退出” ） ；3.本程序只有两个模块，调用关系简单。主程序模块带权无向图模块三 详细设计（重点设计每一个功能模块的实现算法和数据库关系表的结构定义等）1图的基本操作：void CreateUDN(int v,int a);/ 造图函数 路径类型：typedef struct ArcCellint adj; / 相邻接的景点之间的路程 ArcCell; / 定义边的类型 typedef struct VertexTypeint number; / 景点编号 char *sight; / 景点名称 char *description; / 景点描述 VertexType; /定义顶点的类型 typedef structVertexType vexNUM; / 图中的顶点，即为景点 ArcCell arcsNUMNUM; / 图中的边，即为景点间的距离 int vexnum,arcnum; / 顶点数，边数 MGraph; / 定义图的类型 相关的基本操作有：void Searchpath1(MGraph G) /输出两个顶点之间的所有路径。void path(MGraph G,int i,int j,int k) /i 为要查询是起始点，j 为要查询的终点，相当于深度优先遍历/确定路径上第 k+1 个顶点的序号,k 初始值为 0void disppath(MGraph G,int i,int j)/找到从 vi 到 vj 的所有路径并输出其中部分操作的伪代码如下：void path(MGraph G,int i,int j,int k) /i 为要查询是起始点，j 为要查询的终点，相当于深度优先遍历/确定路径上第 k+1 个顶点的序号,k 初始值为 0数据结构课程设计报告 第 4 页，共 25 页int s;if(xk=j)/找到一条路径，初始 x0=ia+;/路径的条数值加 1printf(“第%d 条:“,a);for(s=0;s“,G.vexxs.sight);printf(“%sn“,G.vexxs.sight);s=0;while(si;printf(“选择目地景点：“);数据结构课程设计报告 第 5 页，共 25 页cinj;printf(“nt 从%s 到%s 的所有游览路径有:n“,G.vexi.sight,G.vexj.sight);/输出出发景点和目地景点的名称disppath(G,i,j);/调用 disppath 函数,用来输出两个景点间的所有路径printf(“继续查询?(y 或 n):“);scanf(“%s“,if(s=N|s=n)break;3主程序和其他伪代码void main() /主函数 do 主菜单；ShortestPath(v0); / 计算两个景点之间的最短路径 output(v0,v1); / 输出结果 search();Searchpath1(G);/查询景点间的游览路径 while(ck!=e);/mainchar Menu() / 主菜单char c;int flag;doflag=1;system(“cls“);narrate();显示指示图;printf(“tttt 请输入您的选择：“);scanf(“%c“,if(c=1|c=2|c=3|c=e)flag=0;while(flag);return c;void search() / 查询景点信息 int num;int i;数据结构课程设计报告 第 6 页，共 25 页char c;char name40;dosystem(“cls“);c=SearchMenu();switch (c)case 1: system(“cls“);narrate();printf(“nntt 请输入您要查找的景点编号：“);scanf(“%d“,for(i=0;iNUM;i+)if(num=G.vexi.number)printf(“nnttt 您要查找景点信息如下:“);printf(“nnttt%-25snn“,G.vexi.description);printf(“nttt 按任意键返回.“);getchar();getchar();break;if(i=NUM)printf(“nnttt 没有找到！“);printf(“nnttt 按任意键返回.“);getchar();getchar();break;case 2:system(“cls“);narrate();printf(“nntt 请输入您要查找的景点名称：“);scanf(“%s“,name);for(i=0;iNUM;i+)if(!strcmp(name,G.vexi.sight)/将 G.vexi.sight 赋值给 nameprintf(“nnttt 您要查找景点信息如下:“);printf(“nnttt%-25snn“,G.vexi.description);printf(“nttt 按任意键返回.“);getchar();数据结构课程设计报告 第 7 页，共 25 页getchar();break;if(i=NUM)printf(“nnttt 没有找到！“);printf(“nnttt 按任意键返回.“);getchar();getchar();break;while(c!=e);void narrate() / 说明函数 int i,k=0;printf(“nt*欢迎使用校园导游程序*n“);printf(“t*n“);printf(“t 景点名称t|t 景点描述n“);printf(“t*|*n“);for(i=0;iNUM;i+)printf(“t (%2d)%-10s:%-25sn“,i,G.vexi.sight,G.vexi.description); /* 输出景点列表 */k=k+1;printf(“t*|*n“);void ShortestPath(int num) / 迪杰斯特拉算法最短路径函数 num 为入口点的编号 int v,w,i,t; / i、w 和 v 为计数变量 int finalNUM; int min;for(v=0;vNUM;v+)finalv=0; / 假设从顶点 num 到顶点 v 没有最短路径 Dv=G.arcsnumv.adj;/ 将与之相关的权值放入 D 中存放 for(w=0;wNUM;w+) / 设置为空路径 Pvw=0;if(Dv20000) / 存在路径 Pvnum=1; / 存在标志置为一 Pvv=1; / 自身到自身 数据结构课程设计报告 第 8 页，共 25 页Dnum=0;finalnum=1; / 初始化 num 顶点属于 S 集合 / 开始主循环，每一次求得 num 到某个顶点的最短路径，并将其加入到 S 集合 for(i=0;iNUM;+i) / 其余 G.vexnum-1 个顶点 min=Max; / 当前所知离顶点 num 的最近距离 for(w=0;wNUM;+w)if(!finalw) / w 顶点在 v-s 中if(Dwmin) / w 顶点离 num 顶点更近 v=w;min=Dw; finalv=1; / 离 num 顶点更近的 v 加入到 s 集合 for(w=0;wNUM;+w) /更新当前最短路径极其距离 if(!finalwfor(t=0;tNUM;t+)Pwt=Pvt;Pww=1;void output(int sight1,int sight2) / 输出函数int a,b,c,d,q=0;a=sight2; / 将景点二赋值给 a if(a!=sight1) / 如果景点二不和景点一输入重合，则进行. printf(“nt 从%s 到%s 的最短路径是“,G.vexsight1.sight,G.vexsight2.sig