《数据结构课程设计报告》由会员分享,可在线阅读,更多相关《数据结构课程设计报告(23页珍藏版)》请在金锄头文库上搜索。
1、n更多企业学院: 中小企业管理全能版183套讲座+89700份资料总经理、高层管理49套讲座+16388份资料中层管理学院46套讲座+6020份资料国学智慧、易经46套讲座人力资源学院56套讲座+27123份资料各阶段员工培训学院77套讲座+ 324份资料员工管理企业学院67套讲座+ 8720份资料工厂生产管理学院52套讲座+ 13920份资料财务管理学院53套讲座+ 17945份资料销售经理学院56套讲座+ 14350份资料销售人员培训学院72套讲座+ 4879份资料 淮 海 工 学 院 计算机工程学院课程设计报告设计名称: 数据结构课程设计 选题名称: 连云港市景点导游咨询 姓 名: 顾浩
2、然 学 号: 110912109 专业班级: 网络工程 网络091 系 (院): 计算机工程学院 设计时间: 2010.12.202010.12.31 设计地点: 软件工程实验室、教室 成绩:指导教师评语: 签名: 年 月 日1课程设计目的1、训练学生灵活应用所学数据结构知识,独立完成问题分析,结合数据结构理论知识,编写程序求解指定问题。 2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能;3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力;4.训练用系统的观点和软件开发一般规范进行软件开发,巩固、深化学生的理论知识,提高编程水平,并在此过程中培养他们严谨的
3、科学态度和良好的工作作风。2课程设计任务与要求:任务:用无向网表示连云港市旅游景点平面图,图中顶点表示主要景点,存放景点编号、名称、简介等信息,图中边表示景点间的道路,存放路径长度信息。 要求:(1)查询各景点的相关信息; (2)查询图中任意两个景点间的最短路径 (3)查询图中任意两个景点间的所有路径 (4)可动态添加景点,加后可查询该景点到其它景点的最短路径 3课程设计说明书一 需求分析:连云港作为一个著名的旅游城市,每年都有大量的国内外游客来港城旅游,大多数外地游客对连云港的旅游景点的相关信息不是非常了解,所以我们可以为他们设计一个方便在连云港外出旅游的咨询程序,即连云港市景点导游咨询程序
4、。连云港市导游咨询程序需要把连云港市的主要景点(争取十个左右,虽然我只认识几个而已)都包括在一个平面图内。(1) 以图中各顶点存放连云港的各景点名称,代号,简介等相关信息 (2)程序中,以各个旅游景点名称为图的顶点,各个顶点的信息是景点的简要描述,权值就是任意两个景点间的路径长度(3) 以边存放路径及路径长度等相关信息,游客可根据图所提供的景点来查询各个景点的相关信息及各景点的路径查询(4) 提供两个景点间的所有路径并提示最短路径,为游客的旅游带来方便,游客可根据实际情况选择最佳的游览路线。二 概要设计1、基本操作: CreateGraph(G):创建图G。 LocateVertex(G,v)
5、:确定顶点v在图g中的位置,若图g中没有顶点v,则函数值为“空”。 GetVertex(G,i):取出图g中的第i个顶点的值,若i大于图g中顶点数,则函数值为“空”。 FirstAdjVertex(G,v):求图G顶点v的第一个邻接点,若v无邻接点或图G中无顶点v,则函数值为“空”。 NextAdjVertex(G,v,w):已知w是图G中顶点v的某个邻接点,求顶点v的下一个邻接点(紧跟在w后面),若w是v的最后一个邻接点,则函数值为“空”。 InsertVertex(G,u):在图G中增加一个顶点u。 InsertArc(G,v,w):在图G中增加一条从顶点v到顶点w的弧。 Traverse
6、Graph(G):按照某种次序,对图G的每个结点访问一次且仅访问一次。 2、系统中子程序及功能要求:path(MGraph g,int i,int j,int k):确定路径上第k+1个顶点的序号,k初始值为0apath(MGraph g,int i,int j):初始化访问标志与路径条数,并调用path()函数cpath(MGraph g,int path1,int i,int v0):输出最短路径bpath(MGraph g,int dist,int path1,int s,int n,int v0,int i):由path1计算从v0到i的最短路径Dijkstra(MGraph g,in
7、t v0,int p):采用迪杰斯特拉算法求从顶点v0到顶点p的最短路径chaname(MGraph g):查询景点的信息chapath1(MGraph g):查询两个景点间的所有路径chapath2(MGraph g):查询两个景点间的最短路径3、各程序模块之间的调用关系:函数的调用关系图mainchaname chapath1 chapath2apath Dijkstrapath bpathpath cpath cpath主函数可调用子程序 子程序可调用子程序子程序可调用子程序子程序可调用子程序子程序可调用子程序子程序可调用子程序子程序可调用子程序子程序可调用子程序子程序可调用子程序三 详
8、细设计顶点、边和图的类型:typedef structint num;/*顶点编号*/ char nameMAXSIZE;/*顶点名称*/ char discriptionMAXLEN;/*顶点信息描述*/VertexType; typedef structint edgesMAXVMAXV; int vexnum,arcnum;VertexType vexsMAXV; MGraph;int visitedMAXV;int pMAXV;创建连云港市景点地图:int i,j;int b11=1,2,3,4,5,6,7,8,9,10,11;char *c11=/*各个景点名称*/;char *d1
9、1=/*字符串指针数组,用来给每个顶点的简介信息进行赋值*/;MGraph g;/*创建一个无向网*/ int A1111=/*景点的相关简介进行赋值*/ ; g.vexnum=顶点个数;g.arcnum=顶点边数;/*建立无向网的邻接矩阵*/for(i=0;i图的顶点个数;i+) /*给每个顶点一个编号*/ /*通过字符串复制函数给每个顶点一个名称*/ /*通过字符串复制函数给每个顶点加上信息,即作为景点的简介信息*/ 查询景点的信息:int i;char s; while(1)/*可提供循环查询,当输入为N或n时,结束循环*/printf(ttt 请输入你要查询的景点:); scanf(%
10、d,&i);for(int j=0;j图的顶点个数;j+) /*输出信息*/ printf(继续查询?(y或n):);scanf(%s,&s);if(s=N|s=n)break;查询景点间的游览路径:void chapath1(MGraph g) int i,j; char s; while(1)/*可提供循环查询,当输入为N或n时,结束循环*/*输入起点与终点*/; disppath(g,i,j);/*调用disppath函数,用来输出两个景点间的所有路径*/ printf(继续查询?(y或n):);scanf(%s,&s);if(s=N|s=n)break;查询两个景点间的最短路径:int
11、 i,j; char s; while(1)/*可提供循环查询,当输入为N或n时,结束循环*/*输入起点与终点*/Dijkstra(g,i,j);/*调用Dijkstra函数,用来输出两个景点间的最短路径*/printf(继续查询?(y或n):);scanf(%s,&s);if(s=N|s=n)break;主函数:int select;/*定义一个整型变量,用来输入不同的选择*/ do/*可提供循环输入选择,当输入的选择为4时,退出循环*/ switch(select)/*判断select的值,根据其值跳转到相应的子模块继续执行*/ case 1: /*查询景点的信息*/ break; cas
12、e 2: ;/*查询景点间的游览路径*/ break; case 3: /*查询景点间的最短游览路径*/ break; case 4:/*退出程序*/ break; while(select!=4);/*当select的值不为4时,继续循环*/四 设计与调试分析1、在执行查询景点间的游览路径时,我之前考虑到深度优先遍历,我可以以指定的为起点开始遍历,在到达指定的终点时,让他停止并输出路径,不过这之间要定义一个s,来存放访问过的并且可走通的顶点编号,以便可以方便输出,可是,如一个顶点有多个邻接点,它是选取其中一条的,有可能在这个顶点可以经过这些邻接点照样可以走到我们指定的终点,在这里就出现了问题,怎样让它在访问一个邻接点之后还可以在访问它的另外一个邻接点。之后想到了递归调用,以及邻接矩阵并通过visited来解决这个问题;2、在执行导游程序时,需要根据用户的临时输入求最短路径。虽然迪杰斯特拉算法的时间复杂度比弗洛伊德算法低,但每次在求一条最短路径时都必须重新搜索一遍,如果用户频繁查询会导致查