数据结构课程设计报告

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 设计地点： 软件工程实验室、教室成绩：指导教师评语： 签名： 年 月 日20 / 231课程设计目的1、训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。 2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4.训练用系统的观点和软件开发一般规进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在

3、此过程中培养他们严谨的科学态度和良好的工作作风。2课程设计任务与要求：任务：用无向网表示市旅游景点平面图，图中顶点表示主要景点，存放景点编号、名称、简介等信息，图中边表示景点间的道路，存放路径长度信息。 要求：（1）查询各景点的相关信息； （2）查询图中任意两个景点间的最短路径 （3）查询图中任意两个景点间的所有路径 （4）可动态添加景点，加后可查询该景点到其它景点的最短路径 3课程设计说明书一 需求分析：作为一个著名的旅游城市，每年都有大量的国外游客来港城旅游，大多数外地游客对的旅游景点的相关信息不是非常了解，所以我们可以为他们设计一个方便在外出旅游的咨询程序，即市景点导游咨询程序。市导游咨

4、询程序需要把市的主要景点（争取十个左右，虽然我只认识几个而已）都包括在一个平面图。(1) 以图中各顶点存放的各景点名称，代号，简介等相关信息 （2）程序中，以各个旅游景点名称为图的顶点，各个顶点的信息是景点的简要描述，权值就是任意两个景点间的路径长度(3) 以边存放路径与路径长度等相关信息，游客可根据图所提供的景点来查询各个景点的相关信息与各景点的路径查询(4) 提供两个景点间的所有路径并提示最短路径，为游客的旅游带来方便，游客可根据实际情况选择最佳的游览路线。二 概要设计1、基本操作：CreateGraph(G):创建图G。 LocateVertex(G,v):确定顶点v在图g中的位置，若图

5、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的弧。TraverseGraph（G）：按照某种次序，对图G的每

6、个结点访问一次且仅访问一次。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,int v0,int p)：采用迪杰斯特拉算法求

7、从顶点v0到顶点p的最短路径chaname(MGraph g)：查询景点的信息chapath1(MGraph g)：查询两个景点间的所有路径chapath2(MGraph g)：查询两个景点间的最短路径3、各程序模块之间的调用关系：函数的调用关系图mainchaname chapath1 chapath2apathDijkstrapath bpathpath cpathcpath主函数可调用子程序子程序可调用子程序子程序可调用子程序子程序可调用子程序子程序可调用子程序子程序可调用子程序子程序可调用子程序子程序可调用子程序子程序可调用子程序三 详细设计顶点、边和图的类型：typedef stru

8、ctint 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 *d11=/*字符串指针数组,用来给每个顶点的简介信息进行赋值

9、*/;MGraph g;/*创建一个无向网*/int A1111=/*景点的相关简介进行赋值*/ ; g.vexnum=顶点个数;g.arcnum=顶点边数;/*建立无向网的邻接矩阵*/for(i=0;i<图的顶点个数;i+) /*给每个顶点一个编号*/ /*通过字符串复制函数给每个顶点一个名称*/ /*通过字符串复制函数给每个顶点加上信息，即作为景点的简介信息*/ 查询景点的信息：int i;char s; while(1)/*可提供循环查询,当输入为'N'或'n'时,结束循环*/printf("ttt 请输入你要查询的景点：");

10、scanf("%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);/*调用d

11、isppath函数,用来输出两个景点间的所有路径*/ printf("继续查询?(y或n):");scanf("%s",&s);if(s='N'|s='n')break;查询两个景点间的最短路径：int i,j; char s; while(1)/*可提供循环查询,当输入为'N'或'n'时,结束循环*/*输入起点与终点*/Dijkstra(g,i,j);/*调用Dijkstra函数,用来输出两个景点间的最短路径*/printf("继续查询?(y或n):");sca

12、nf("%s",&s);if(s='N'|s='n')break;主函数：int select;/*定义一个整型变量,用来输入不同的选择*/ do/*可提供循环输入选择,当输入的选择为4时,退出循环*/ switch(select)/*判断select的值，根据其值跳转到相应的子模块继续执行*/ case 1: /*查询景点的信息*/ break; case 2: ;/*查询景点间的游览路径*/ break; case 3: /*查询景点间的最短游览路径*/ break; case 4:/*退出程序*/ break; while(se

13、lect!=4);/*当select的值不为4时，继续循环*/四 设计与调试分析1、在执行查询景点间的游览路径时，我之前考虑到深度优先遍历，我可以以指定的为起点开始遍历，在到达指定的终点时，让他停止并输出路径，不过这之间要定义一个s，来存放访问过的并且可走通的顶点编号，以便可以方便输出，可是，如一个顶点有多个邻接点，它是选取其中一条的，有可能在这个顶点可以经过这些邻接点照样可以走到我们指定的终点，在这里就出现了问题，怎样让它在访问一个邻接点之后还可以在访问它的另外一个邻接点。之后想到了递归调用,以与邻接矩阵并通过visited来解决这个问题；2、在执行导游程序时，需要根据用户的临时输入求最短路

14、径。虽然迪杰斯特拉算法的时间复杂度比弗洛伊德算法低，但每次在求一条最短路径时都必须重新搜索一遍，如果用户频繁查询会导致查询效率降低，所以，在选用算法时不能单纯的只考虑算法的渐近时间复杂度，有时还必须综合考虑各种因素。五 用户手册尊敬的用户您好，本程序提供完全人性化操作界面，您完全可以根据程序的详细操作提示得到您所要的相关信息与帮助服务，以下为本程序的主界面，感您的支持与使用。六 测试成果七 附录（源程序清单）#include<stdio.h>#include<string.h>#include <stdlib.h>#define MAXV 11#define

15、 MAXSIZE 30#define MAXLEN 3000#define INF 32767int a=0;typedef struct int num; char nameMAXSIZE; char xinxiMAXLEN;VertexType; typedef structint edgesMAXVMAXV; int vexnum,arcnum; VertexType vexsMAXV;MGraph;int visitedMAXV;int pMAXV;void path(MGraph g,int i,int j,int k)/*确定路径上第k+1个顶点的序号,k初始值为0*/int s;

16、if(pk=j)a+;printf("第%d条:",a);for(s=0;s<=k-1;s+)printf("%s->",);printf("%sn",);s=0;while(s<g.vexnum)if(s!=i)if(g.edgespks!=INF&&visiteds=0)visiteds=1;pk+1=s;path(g,i,j,k+1);visiteds=0;s+;void apath(MGraph g,int i,int j)/*初始化访问标志

17、与路径条数，并调用path（）函数*/int k; p0=i; for(k=0;k<g.vexnum;k+)visitedi=0;a=0;path(g,i,j,0);void cpath(MGraph g,int path1,int i,int v0)/*输出最短路径*/int k;k=path1i; if(k=v0)return;cpath(g,path1,k,v0);printf("%s->",);void bpath(MGraph g,int dist,int path1,int s,int n,int v0,int i)/*由pa

18、th1计算从v0到i的最短路径*/if(si=1&&i!=v0)printf("从%s到%s的最短游览路径是:n",,);printf("%s->",); cpath(g,path1,i,v0); printf("%s ",); printf("路径长度：%d公里n",disti);void Dijkstra(MGraph g,int v0,int p)/*采用迪杰斯特拉算法求从顶点v0到顶点p

19、的最短路径*/int distMAXV,path1MAXV;int sMAXV; int mindis,i,j,u,n=g.vexnum;for(i=0;i<n;i+)disti=g.edgesv0i;si=0;if(g.edgesv0i<INF)path1i=v0;else path1i=-1;sv0=1;path1v0=0;for(i=0;i<n;i+)mindis=INF;u=-1;for(j=0;j<n;j+)if(sj=0&&distj<mindis) u=j;mindis=distj;su=1;for(j=0;j<n;j+)if(

20、sj=0)if(g.edgesuj<INF&&distu+g.edgesuj<distj)distj=distu+g.edgesuj;path1j=u; bpath(g,dist,path1,s,n,v0,p);void chaname(MGraph g)/*查询各景点的相关信息*/printf("您可以选择以下任一景点:n"); printf("-n");printf("tt1:孔望山ntt2:连岛n");printf("tt3:连岛海底世界ntt4:孔雀沟风景区ntt5:山岛旅游度假区ntt6

21、:船山ntt7:花果山n");printf("tt8:桃花涧ntt9:东海温泉ntt10:枫树湾ntt11:前三岛n"); printf("-n"); int i; char s; while(1)printf("ttt 请输入您要查询的景点："); scanf("%d",&i);for(int j=0;j<g.vexnum;j+)if(i=g.vexsj.num)printf("%s该景点的相关简介：n",); printf("-n&q

22、uot;);printf("%s",g.vexsj.xinxi);printf("n"); printf("-n");printf("您是否要继续查询?(按任意键继续或按n退出):");scanf("%s",&s);if(s='N'|s='n')break;void chapath1(MGraph g)/*查询各景点间的游览路径 */ printf("您可以选择以下任一景点:n"); printf("-n");pri

23、ntf("tt1:孔望山ntt2:连岛n");printf("tt3:连岛海底世界ntt4:孔雀沟风景区ntt5:山岛旅游度假区ntt6:船山ntt7:花果山n");printf("tt8:桃花涧ntt9:东海温泉ntt10:枫树湾ntt11:前三岛n"); printf("-n"); int i,j; char s; while(1)printf("ttt 选择您的出发景点："); fflush(stdin); scanf("%d",&i);printf("

24、;ttt 选择您的目地景点："); fflush(stdin);scanf("%d",&j);for(int k=0;k<g.vexnum;k+)if(i=g.vexsk.num) i=k;for(int l=0;l<g.vexnum;l+)if(j=g.vexsl.num) j=l;printf("从%s到%s的所有游览路径有:n",,);apath(g,i,j);printf("-n");printf("您是否要继续查询?(按任意键继续或按n退

25、出):");scanf("%s",&s);if(s='N'|s='n')break;void chapath2(MGraph g)/*查询各景点间的最短游览路径*/ printf("您可以选择以下任一景点:n"); printf("-n");printf("tt1:孔望山ntt2:连岛n");printf("tt3:连岛海底世界ntt4:孔雀沟风景区ntt5:山岛旅游度假区ntt6:船山ntt7:花果山n");printf("tt8:桃

26、花涧ntt9:东海温泉ntt10:枫树湾ntt11:前三岛n"); printf("-n"); int i,j; char s; while(1)printf("ttt 选择您的出发景点：");fflush(stdin);scanf("%d",&i);printf("ttt 选择您的目地景点：");fflush(stdin); scanf("%d",&j); for(int k=0;k<g.vexnum;k+)if(i=g.vexsk.num) i=k; for(

27、int l=0;l<g.vexnum;l+)if(j=g.vexsl.num) j=l; Dijkstra(g,i,j);printf("-n");printf("您是否要继续查询?(按任意键继续或按n退出):");scanf("%s",&s);if(s='N'|s='n')break;void chapath3(MGraph g)/*动态添加景点*/printf("您可以添加任何您想查询的景点：n");printf("-n");printf(&qu

28、ot;尊敬的用户，本程序暂还未能实现本功能，为此给您带来的不便我表示抱歉，感您的使用，再见n"); printf("-n"); printf("请您重新运行本程序");int i,j; char s; while(1) scanf("ttt 请输入您要添加的景点：");scanf("-n"); scanf("尊敬的用户，本程序暂还未能实现本功能，为此给您带来的不便我表示抱歉，感您的使用，再见n"); scanf("-n"); scanf("-n"

29、);printf("您是否要继续查询?(按任意键继续或按n退出):");scanf("%s",&s);if(s='N'|s='n');void main()int i,j;int b11=1,2,3,4,5,6,7,8,9,10,11;char *c11="孔望山","连岛","连岛海底世界","孔雀沟风景区","山岛旅游度假区","船山","花果山","桃花涧&qu

30、ot;,"东海温泉","枫树湾","前三岛" char *d11= "票价：30元 孔望山风景区是市四大风景区之一，怪石峥嵘，草本葱郁；堪称原始艺术精华的孔望山摩崖石刻以与历代名人墨客的铭刻留言更使风景区古趣怡然，驰名中外。 ", "票价：50元 连岛美在海中央，她云腾雾绕，似海上仙山浮座于万顷波涛之上，7.57平方公里的面积，位居海滨之首。它距市区30公里，距港口5公里。这里青山批翠，碧海泛波，独特的海滨风光秀丽迷人，成为黄海之滨一颗璀璨的明珠。", "票价：25元 连岛海洋馆作为连

31、岛旅游度假区近年来引进的最大的旅游项目之一，是省沿海唯一的海洋馆，省科普教育基地，也是国展示活体珊瑚品种数量最多的海洋馆。在这里，你可以探索海洋的奥秘，认识各种各样的海洋生物，有五颜六色的珊瑚，小巧玲珑的“水母”，多姿多彩的贝类，还有许许多多美丽的珊瑚鱼. ", "票价：25元 孔雀沟景区位于省市云台山南麓，是全国著名的国家级风景名胜区花果山风景区的重要组成部分。孔雀沟景区西连花果山景区，东邻渔湾景区、港口、连岛海滨浴场，东距港口 15 公里，西距市中心新浦 12 公里。", "票价：50元 山岛位于赣榆县东部海边。相传始皇曾到这里登山祭海，感动了海神，

32、派龙女向他敬献宝珠，至今尚有授珠台遗址。每年春夏之交，海雾迷蒙，不论是在山脚下，还是登上山岛，常常可以看见海市蜃楼的圣景，还有那些流传的关于此地的神话故事，更加增添了这里的神奇美丽，令人向往。 ", "票价：30元 船山位于行城东侧，古为舟船避风之处，因而此名。暴雨过后来到船山，老远就听到瀑布冲击山谷发出的轰轰巨响。登上半山腰红柱金瓦的观瀑亭，举目眺望，瀑布全景尽收眼底。飞瀑沿山谷奔流，半山的云烟随涧水浮沉，三级瀑布在涧谷中时隐时现。", "票价：100元 花果山位于市区东南，为云台山脉的一部分。原名苍梧山，亦称青峰顶，因吴承恩创作神话小说西游记取材于此

33、，故名花果山。山中林木茂盛，青竹滴翠，云海起伏，古有东海第一胜境之誉。","票价：30元 桃花涧景区因天书将军崖岩画、缤纷的桃花和青山秀水著称。 桃花涧源自锦屏山马耳峰。千回百转汇集成滔滔涧水流下南坡。这里峰峦峻秀,春来遍开桃花,因以为名,现已开辟为新的旅游景点。山上既有挺拔的林木,又有裸露的石骨,颇具中国画的风味。景区的下面,即著名的锦屏磷矿矿区。1979年冬,桃花涧发现了四五万年前古人类活动的遗址,出土的舟伏、漏斗状石器,与日本九州出土的这类石器形制大体一样。据专家考证,那时期海平面普遍下降,日本与之间形成一条陆桥,两岸的古人类曾不断互相往来和交流。", &q

34、uot;票价：288元 位于东海县西北部，因临近羽山，又称羽山温泉。它是市新近开发的旅游温泉。 温泉发现于唐代，早见于史籍记载。这说明人们早在一千多年前就对它开发、利用。那时的温泉只是两个小水洼，灼热的地下水，不断涌出地面，漫野而流，人们称为“汤泉”。1972年，在这儿打出了一眼自流井，井深500多米，水温高达82 oC，每天喷流900余吨。目前，东海温泉已开发成疗养胜地。国外游客在饱览海光山色、名胜古迹之后，驱车前往，洗尘肴濯足，是一件惬意美事。 据有关单位化验，羽山温泉属于钠钙型水，富含钠、钙、镁、锌等元素，特别是放射性气体氡的含量，在一升水中超过56马歇单位，有着重要的医疗价值，对关节炎

35、、高血压和多种皮肤病有明显疗效。羽山泉水透明清澈、滑润爽肌，没有一般温泉那股难闻的硫磺味，洗浴时也无需用肥皂。水质可与华清池、汤山温泉相媲美。浴后再喝上一杯略带咸味的温泉水，不仅增进食欲，而且可以治疗肠胃疾病", "票价：10元 枫树湾位于云台山隧道南出口西侧不远处，那里密布着原生的枫树，夏季绿荫蔽日，秋来红叶满山，此处即为枫树湾。湾中有两株300年的金桂树，盛花时香飘十里。树旁还有好几棵老木瓜树，枝干光滑，硕果累累，是难得的观赏佳境。 ","票价：本处景点暂不售票，如要前往，需持有关部门相关证明或有效证件 前三岛位于省市黄海中部海州湾靠近大陆的三座小岛

36、屿，鼎足而立，孤悬海上。其中车牛山岛最高，海拔67.2米，面积为6公顷，达埝山岛面积为11.5公顷，平山岛面积为14公顷。车牛山岛离大陆最近，直线距离为39.8公里。 岛上植被简单，均以草本植物为主。乔木多为人工栽种的柳、槐、马尾松、法国梧桐、海桐与悬铃木等，草本以艾蒿、灰蓠为主，还有芦苇、野菊花、鬼针草和苦荬菜等。三岛地形相似，均为低山地类型。山坡上缓下陡，断崖与暴露的岩石较多。土壤贫瘠，覆盖层薄。岩石间多缝隙。居民点附近有人工栽培的树木和种植的蔬菜地.前三岛是扁嘴海雀等海鸟的繁殖地和候鸟迁徙的重要驿站。黑叉尾海燕、白额鹱、海鸬鹚、黑尾鸥、扁嘴海雀等海鸟在岛上的悬崖峭壁上繁殖，还有大量的白腰

37、雨燕在岛上繁殖。其他珍贵、濒危鸟类还有国家I级保护动物黑鹳、国家II级保护动物海鸬鹚、黄嘴白鹭、苍鹰、赤腹鹰、雀鹰、松雀鹰、普通鵟、白尾鹞、燕隼、灰背隼、红隼、小杓鹬、红角鴞、纵纹腹小鴞、长耳鴞等。 去前三岛观鸟首先要与市环保局等有关部门取得联系，才能获准上岛观鸟。最好不要选择有台风或多风的季节前往，如果遇到意外天气，可能无法上岛或无法按时返回，所以要有克服困难的思想准备。此外，在岛上要遵守解放军驻岛部队的各项规定，多方面沟通，以便得到他们的大力帮助。春、夏、秋三季比较适合观鸟。夏季有多种海鸟在岛上繁殖，春秋季节则有迁徙的候鸟停歇。如果只有12天时间，可以仅到车牛山岛。如果时间充裕，又有方便的船只，就可以到另外两个岛上去观鸟了。前三岛仅有解放军部队驻扎，吃、住可以联系驻岛部队予以协助解决，但条件比较艰苦，可以自备一些食物和日用品。上岛船只一般710天一次，如果遇到台风或其他风浪较大的天气，则会延迟到1530天才能有船只上岛. " ;MGraph g; int A1111= INF,14,INF,INF,INF,INF,INF,INF,INF,INF,17, 14,INF,3,INF,INF,17,INF,INF,12,INF,INF, INF,3,INF,17,INF,INF,INF,INF,INF,INF,3, INF,INF,17,I