淮 海 工 学 院 计算机工程学院
课程设计报告
设计名称: 数据结构课程设计
选题名称: 连云港市景点导游咨询
姓 名: 顾浩然 学 号: 110912109 专业班级: 网络工程 网络091 系 (院): 计算机工程学院 设计时间: 2010.12.20~2010.12.31 设计地点: 软件工程实验室、教室
指导教师评语: 成绩: 签名: 年 月 日 数据结构课程设计报告 第 1 页,共 页
1.课程设计目的 1、训练学生灵活应用所学数据结构知识,完成问题分析,结合数据结构理论知识,编写程序求解指定问题。 2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能; 3.提高综合运用所学的理论知识和方法分析和解决问题的能力; 4.训练用系统的观点和软件开发一般规范进行软件开发,巩固、深化学生的理论知识,提高编程水平,并在此过程中培养他们严谨的科学态度和良好的工作作风。 2.课程设计任务与要求: 任务:用无向网表示连云港市旅游景点平面图,图中顶点表示主要景点,存放景点编号、名称、简介等信息,图中边表示景点间的道路,存放路径长度信息。 要求:(1)查询各景点的相关信息; (2)查询图中任意两个景点间的最短路径 (3)查询图中任意两个景点间的所有路径 (4)可动态添加景点,加后可查询该景点到其它景点的最短路径 数据结构课程设计报告 第 2 页,共 页
3.课程设计说明书 一 需求分析: 连云港作为一个著名的旅游城市,每年都有大量的国内外游客来港城旅游,大多数外地游客对连云港的旅游景点的相关信息不是非常了解,所以我们可以为他们设计一个方便在连云港外出旅游的咨询程序,即连云港市景点导游咨询程序。 连云港市导游咨询程序需要把连云港市的主要景点(争取十个左右,虽然我只认识几个而已)都包括在一个平面图内。 (1) 以图中各顶点存放连云港的各景点名称,代号,简介等相关信息 (2)程序中,以各个旅游景点名称为图的顶点,各个顶点的信息是景点的简要描述,权值就是任意两个景点间的路径长度 (3) 以边存放路径及路径长度等相关信息,游客可根据图所提供的景点来查询各个景点的相关信息及各景点的路径查询 (4) 提供两个景点间的所有路径并提示最短路径,为游客的旅游带来方便,游客可根据实际情况选择最佳的游览路线。 二 概要设计 1、基本操作: CreateGraph(G):创建图G。 LocateVertex(G,v):确定顶点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的弧。 TraverseGraph(G):按照某种次序,对图G的每个结点访问一次且仅访问一次。 2、系统中子程序及功能要求: ①path(MGraph g,int i,int j,int k):确定路径上第k+1个顶点的序号,k初始值为0 ②apath(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):采用迪杰斯特拉算法求从顶点v0到顶点p的最短路径 ⑥chaname(MGraph g):查询景点的信息 ⑦chapath1(MGraph g):查询两个景点间的所有路径 ⑧chapath2(MGraph g):查询两个景点间的最短路径 数据结构课程设计报告 第 3 页,共 页
3、各程序模块之间的调用关系: 函数的调用关系图 main chaname ⑥ chapath1⑦ chapath2⑧ apath ④ Dijkstra⑤ path ① bpath④ path ① cpath ③ cpath③ 主函数可调用子程序⑥⑦⑧ 子程序⑦可调用子程序④ 子程序⑧可调用子程序⑤ 子程序④可调用子程序① 子程序①可调用子程序① 子程序④可调用子程序③ 子程序③可调用子程序③ 子程序②可调用子程序① 子程序⑤可调用子程序④ 三 详细设计 ⑴顶点、边和图的类型: typedef struct { int num;/*顶点编号*/ char name[MAXSIZE];/*顶点名称*/ char discription[MAXLEN];/*顶点信息描述*/ }VertexType; typedef struct { int edges[MAXV][MAXV]; int vexnum,arcnum; VertexType vexs[MAXV]; }MGraph; int visited[MAXV]; int p[MAXV]; ⑵创建连云港市景点地图: 数据结构课程设计报告 第 4 页,共 页
int i,j; int b[11]={1,2,3,4,5,6,7,8,9,10,11}; char *c[11]={/*各个景点名称*/}; char *d[11]={/*字符串指针数组,用来给每个顶点的简介信息进行赋值*/}; MGraph g;/*创建一个无向网*/ int A[11][11]={/*景点的相关简介进行赋值*/ }; g.vexnum=顶点个数; g.arcnum=顶点边数; /*建立无向网的邻接矩阵*/ for(i=0;i<图的顶点个数;i++) { /*给每个顶点一个编号*/ /*通过字符串复制函数给每个顶点一个名称*/ /*通过字符串复制函数给每个顶点加上信息,即作为景点的简介信息*/ } ⑶查询景点的信息: int i; char s; while(1) /*可提供循环查询,当输入为'N'或'n'时,结束循环*/ { printf(\"\\\ 请输入你要查询的景点:\"); scanf(\"%d\ for(int j=0;j<图的顶点个数;j++) { /*输出信息*/ } printf(\"继续查询?(y或n):\"); scanf(\"%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\数据结构课程设计报告 第 5 页,共 页
if(s=='N'||s=='n') break; } } ⑸查询两个景点间的最短路径: int i,j; char s; while(1) /*可提供循环查询,当输入为'N'或'n'时,结束循环*/ { /*输入起点与终点*/ Dijkstra(g,i,j);/*调用Dijkstra函数,用来输出两个景点间的最短路径*/ printf(\"继续查询?(y或n):\"); scanf(\"%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(select!=4);/*当select的值不为4时,继续循环*/ } 四 设计与调试分析 1、在执行查询景点间的游览路径时,我之前考虑到深度优先遍历,我可以以指定的为起点开始遍历,在到达指定的终点时,让他停止并输出路径,不过这之间要定义一个s,来存放访问过的并且可走通的顶点编号,以便可以方便输出,可是,如一个顶点有多个邻接点,它是选取其中一条的,有可能在这个顶点可以经过数据结构课程设计报告 第 6 页,共 页
这些邻接点照样可以走到我们指定的终点,在这里就出现了问题,怎样让它在访问一个邻接点之后还可以在访问它的另外一个邻接点。之后想到了递归调用,以及邻接矩阵并通过visited[]来解决这个问题; 2、在执行导游程序时,需要根据用户的临时输入求最短路径。虽然迪杰斯特拉算法的时间复杂度比弗洛伊德算法低,但每次在求一条最短路径时都必须重新搜索一遍,如果用户频繁查询会导致查询效率降低,所以,在选用算法时不能单纯的只考虑算法的渐近时间复杂度,有时还必须综合考虑各种因素。 五 用户手册 尊敬的用户您好,本程序提供完全人性化操作界面,您完全可以根据程序的详细操作提示得到您所要的相关信息及帮助服务,以下为本程序的主界面,感谢您的支持与使用。 六 测试成果 数据结构课程设计报告 第 7 页,共 页
数据结构课程设计报告 第 8 页,共 页
数据结构课程设计报告 第 9 页,共 页
数据结构课程设计报告 第 10 页,共 页
七 附录(源程序清单) #include int edges[MAXV][MAXV]; int vexnum,arcnum; VertexType vexs[MAXV]; }MGraph; int visited[MAXV]; int p[MAXV]; void path(MGraph g,int i,int j,int k)/*确定路径上第k+1个顶点的序号,k初始值为0*/ { int s; if(p[k]==j) { } s=0; while(s } void apath(MGraph g,int i,int j)/*初始化访问标志与路径条数,并调用path()函数*/ { int k; } s++; p[0]=i; for(k=0;k printf(\"%s->\ cpath(g,path1,i,v0); printf(\"%s \ printf(\"路径长度:%d公里\\n\ } void Dijkstra(MGraph g,int v0,int p)/*采用迪杰斯特拉算法求从顶点v0到顶点p的最短路径*/ { int dist[MAXV],path1[MAXV]; int s[MAXV]; int mindis,i,j,u,n=g.vexnum; for(i=0;i printf(\"\\\ 选择您的目地景点:\"); fflush(stdin); } void chapath2(MGraph g)/*查询连云港各景点间的最短游览路径*/ { printf(\"您可以选择以下任一景点:\\n\"); printf(\"--------------------------------------------------------------------------------\\n\"); printf(\"\\1:孔望山\\n\\2:连岛\\n\"); printf(\"\\3:连岛海底世界\\n\\4:孔雀沟风景区\\n\\5:秦山岛旅游度假区\\n\\6:船山\\n\\7:花 } scanf(\"%d\for(int k=0;k \"票价:25元 孔雀沟景区位于江苏省连云港市云台山南麓,是全国著名的国家级风景名胜区花果山风景区的重要组成部分。孔雀沟景区西连花果山景区,东邻渔湾景区、连云港港口、连岛海滨浴场,东距港口 15 公里,西距市中心新浦 12 公里。\ \"票价:50元 秦山岛位于赣榆县东部海边。相传秦始皇曾到这里登山祭海,感动了海神,派龙女向他敬献宝珠,至今尚有授珠台遗址。每年春夏之交,海雾迷蒙,不论是在山脚下,还是登上山岛,常常可以看见海市蜃楼的圣景,还有那些流传的关于此地的神话故事,更加增添了这里的神奇美丽,令人向往。 \ \"票价:30元 船山位于行城东侧,古为舟船避风之处,因而此名。暴雨过后来到船山,老远就听到瀑布冲击山谷发出的轰轰巨响。登上半山腰红柱金瓦的观瀑亭,举目眺望,瀑布全景尽收眼底。飞瀑沿山谷奔流,半山的云烟随涧水浮沉,三级瀑布在涧谷中时隐时现。\ \"票价:100元 花果山位于连云港市区东南,为云台山脉的一部分。原名苍梧山,亦称青峰顶,因吴承恩创作神话小说《西游记》取材于此,故名花果山。山中林木茂盛,青竹滴翠,云海起伏,古有东海第一胜境之誉。\ \"票价:30元 桃花涧景区因东方天书将军崖岩画、缤纷的桃花和青山秀水著称。 桃花涧源自锦屏山马耳峰。千回百转汇集成滔滔涧水流下南坡。这里峰峦峻秀,春来遍开桃花,因以为名,现已开辟为新的旅游景点。山上既有挺拔的林木,又有裸露的石骨,颇具中国画的风味。景区的下面,即著名的锦屏磷矿矿区。1979年冬,桃花涧发现了四五万年前古人类活动的遗址,出土的舟伏、漏斗状石器,与日本九州出土的这类石器形制大体相同。据专家考证,那时期海平面普遍下降,日本与连云港之间形成一条陆桥,两岸的古人类曾不断互相往来和交流。\ \"票价:288元 位于东海县西北部,因临近羽山,又称羽山温泉。它是连云港市新近开发的旅游温泉。 温泉发现于唐代,早见于史籍记载。这说明人们早在一千多年前就对它开发、利用。那时的温泉只是两个小水洼,灼热的地下水,不断涌出地面,漫野而流,人们称为“汤泉”。1972年,在这儿打出了一眼自流井,井深500多米,水温高达82 oC,每天喷流900余吨。 目前,东海温泉已开发成疗养胜地。国内外游客在饱览连云港海光山色、名胜古迹之后,驱车前往,洗尘肴濯足,是一件惬意美事。 据有关单位化验,羽山温泉属于钠钙型水,富含钠、钙、镁、锌等元素,特别是放射性气体氡的含量,在一升水中超过5.6马歇单位,有着重要的医疗价值,对关节炎、高血压和多种皮肤病有明显疗效。羽山泉水透明清澈、滑润爽肌,没有一般温泉那股难闻的硫磺味,洗浴时也无需用肥皂。水质可与西安华清池、南京汤山温泉相媲美。浴后再喝上一杯略带咸味的温泉水,不仅增进食欲,而且可以治疗肠胃疾病\数据结构课程设计报告 第 20 页,共 页 \"票价:10元 枫树湾位于云台山隧道南出口西侧不远处,那里密布着原生的枫树,夏季绿荫蔽日,秋来红叶满山,此处即为枫树湾。湾中有两株300年的金桂树,盛花时香飘十里。树旁还有好几棵老木瓜树,枝干光滑,硕果累累,是难得的观赏佳境。 \ \"票价:本处景点暂不售票,如要前往,需持有关部门相关证明或有效证件 前三岛位于江苏省连云港市黄海中部海州湾靠近的三座小岛屿,鼎足而立,孤悬海上。其中车牛山岛最高,海拔67.2米,面积为6公顷,达埝山岛面积为11.5公顷,平山岛面积为14公顷。车牛山岛离最近,直线距离为39.8公里。 岛上植被简单,均以草本植物为主。乔木多为人工栽种的柳、槐、马尾松、法国梧桐、海桐及悬铃木等,草本以艾蒿、灰蓠为主,还有芦苇、野菊花、鬼针草和苦荬菜等。三岛地形相似,均为低山地类型。山坡上缓下陡,断崖及暴露的岩石较多。土壤贫瘠,覆盖层薄。岩石间多缝隙。居民点附近有人工栽培的树木和种植的蔬菜地.前三岛是扁嘴海雀等海鸟的繁殖地和候鸟迁徙的重要驿站。黑叉尾海燕、白额鹱、海鸬鹚、黑尾鸥、扁嘴海雀等海鸟在岛上的悬崖峭壁上繁殖,还有大量的白腰雨燕在岛上繁殖。其他珍贵、濒危鸟类还有国家I级保护动物黑鹳、国家II级保护动物海鸬鹚、黄嘴白鹭、苍鹰、赤腹鹰、雀鹰、松雀鹰、普通鵟、白尾鹞、燕隼、灰背隼、红隼、小杓鹬、红角鴞、纵纹腹小鴞、长耳鴞等。 去前三岛观鸟首先要与连云港市环保局等有关部门取得联系,才能获准上岛观鸟。最好不要选择有台风或多风的季节前往,如果遇到意外天气,可能无法上岛或无法按时返回,所以要有克服困难的思想准备。此外,在岛上要遵守驻岛的各项规定,多方面沟通,以便得到他们的大力帮助。春、夏、秋三季比较适合观鸟。夏季有多种海鸟在岛上繁殖,春秋季节则有迁徙的候鸟停歇。如果只有1—2天时间,可以仅到车牛山岛。如果时间充裕,又有方便的船只,就可以到另外两个岛上去观鸟了。前三岛仅有驻扎,吃、住可以联系驻岛予以协助解决,但条件比较艰苦,可以自备一些食物和日用品。上岛船只一般7—10天一次,如果遇到台风或其他风浪较大的天气,则会延迟到15—30天才能有船只上岛. \" }; MGraph g; int A[11][11]={ {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,INF,10,INF,INF,INF,INF,INF,INF}, {INF,INF,INF,10,INF,10,8,INF,INF,INF,INF}, 数据结构课程设计报告 第 21 页,共 页 {INF,17,INF,INF,10,INF,INF,12,INF,INF,INF}, {INF,INF,INF,INF,8,INF,INF,18,INF,INF,INF}, {INF,INF,INF,INF,INF,12,18,INF,10,17,INF}, {INF,12,INF,INF,INF,INF,INF,10,INF,INF,INF}, {INF,INF,INF,INF,INF,INF,INF,17,INF,INF,20}, {3,INF,3,INF,INF,INF,INF,INF,INF,20,INF}}; g.vexnum=11; g.arcnum=17; for(i=0;i printf(\" 3、查询连云港各景点间的最短游览路径 \\n\"); printf(\" 4、输入您要添加的景点 \\n\"); printf(\" 5、退出本程序 \\n\"); printf(\" \\n\"); printf(\" ############################################\\n\"); printf(\"--------------------------------------------------------------------------------\\n\"); printf(\" 请输入您的选择:\"); scanf(\"%d\ switch(select) { case 1: chaname(g);/*查询连云港各景点的相关信息*/ break; case 2: chapath1(g);/*查询连云港各景点间的游览路径*/ break; case 3: chapath2(g);/*查询连云港各景点间的最短游览路径*/ break; case 4: chapath3(g);/*查询动态添加的景点到各景点间的游览路径*/ break; case 5:/*退出本程序*/ break; } }while(select!=5); } 数据结构课程设计报告 第 23 页,共 页 4.课程设计心得 因篇幅问题不能全部显示,请点此查看更多更全内容
Copyright © 2019- huatuo0.com 版权所有 湘ICP备2023021991号-1
违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com
本站由北京市万商天勤律师事务所王兴未律师提供法律服务