数据结构 连云港景点导游咨询 课程设计.doc

淮 海 工 学 院 计算机工程学院课程设计报告设计名称： 数据结构课程设计 选题名称： 连云港景点导游咨询 姓 名： 刘胜昔 学 号： 专业班级： 计算机科学与技术 计算机111 系 （院）： 计算机工程学院 设计时间： 2012.12.242013.1.4 设计地点： 计算机楼104机房 成绩：指导教师评语： 签名： 年 月 日数据结构课程设计报告 第 23 页，共 页1课程设计目的1、训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。 2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4.训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。2课程设计任务与要求：任务根据教材数据结构-C语言描述（耿国华主编）和参考书数据结构题集（C语言版）（严蔚敏、吴伟民主编）选择课程设计题目，要求通过设计，在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。设计题目从任务书所列选题表中选取，每班每题不得超过2人。学生自选课题学生原则上可以结合个人爱好自选课题，要求课题有一定的深度与难度，有一定的算法复杂性，能够巩固数据结构课程所学的知识。学生自选课题需在18周前报课程设计指导教师批准方可生效。要求：1、在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。前期准备工作完备与否直接影响到后序上机调试工作的效率。在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率。 2、.设计的题目要求达到一定工作量（300行以上代码），并具有一定的深度和难度。3、程序设计语言推荐使用C/C+，程序书写规范，源程序需加必要的注释;4、每位同学需提交可独立运行的程序；5 、每位同学需独立提交设计报告书（每人一份），要求编排格式统一、规范、内容充实，不少于10页（代码不算）；6、课程设计实践作为培养学生动手能力的一种手段，单独考核。 3课程设计说明书一 需求分析代码需要实现以下4种功能：（1）输入任一个景点，能够为游客输出该景点的相关信息，包括（编号，名称，票价，简介）；（2）输入起点以及下一个要到达的景点，为游客输出两个景点间的最短路径；（3）输入任意两个景点，为游客输出两个景点间的所有路径；（4）可动态添加景点，加后可查询该景点到其它景点的最短路径；二 概要设计 V1 连岛 V0花果山33.433.756.117.8 7566.639.7 V3石棚山 V2孔望山49.312.6 V4桃花涧1定义数据类型：（1）包含景点序号（num）、名称（name）、门票价格（money）、简介（introduce）等;（2）定义无向网，实际情况每两个不相同的景点间均有权值；2主要操作函数：（1）Insjd();初始化景点数据记录，输入各景点主要信息；（2）CreateUDG(); 创建无向网储存景点名称及权值；（3）Search();主要用于查找并向游客展示该景点所有信息；（4） CountMinway()； 找出所有路径；（5）Minway()； 找出最短路径，并输出；（6）AllPath();查找全部路径； （7）AddInt（）；动态添加景点；（8）Menu();输出菜单；（9）Main(); 主函数；3系统子程序：（10）Locate();定位元素；（11）Allway(）； 寻找所有路径；4各模块调用关系（9）调用（1）（2）（3）（4）（5）（6）（7）（8）；（4）调用（10）（11）；（6）调用（10）；三 详细设计(1)./图的邻接矩阵表示法定义#define MAX_VERTEX_NUM 景点最大个数#define INFINITY 初始权值#define AdjType 权值（景点间距离）typedef 景点名格式（string） VertexData;typedef struct ArcNodeAdjType adj;ArcNode;typedef structVertexData vexsMAX_VERTEX_NUM;ArcNode arcsMAX_VERTEX_NUMMAX_VERTEX_NUM（记录景点间距离）;int vexnum（景点数）,arcnum（路径条数）;AdjMatrix;(2)./景点结构体typedef struct jdNodeint num;/序号string name;/名称string ticket;/门票string introduce;/简介jdNode;typedef structjdNode elemMAX_VERTEX_NUM;int length;/景点数jd;(3) .void Insjd(jd *JD（景点指针） , AdjMatrix *G（图指针）)/初始化景点资料(4) .int Locate(AdjMatrix *g（图指针） , string a（景点名称）)/定位景点的位置(5) .void CreateUDG(AdjMatrix *G（图指针）)/创建无向图(6) .void Menu()/菜单界面(7) .void Search(jd JD（景点结构体） , string Name（景点名称）)/查询景点信息(8) （9）（10）整体求出最短路径。 （8）.void Allway(AdjMatrix G（图结构）,bool *visited（返回判断景点有无访问）,string vexs（景点名）,double Long（路径长度）,string vb（终点名称）,string path（路径）)/递归求取所有顶点va到顶点vb的路径 （9）.void CountMinway(AdjMatrix G（图结构）)/求输入两景点的所有路径（10）.void Minway()/输出最短路径（11）.void AllPath(AdjMatrix *G（图指针） , int v（访问景点的位置） , int s（终点位置）)/查询全部路径（12）.void AddInt(AdjMatrix *G（图指针） , jd *JD（景点指针）)/添加动态景点（13）.void main()/主函数具体操作：（3）.void Insjd(jd *JD , AdjMatrix *G)JD-elem0.num=1;JD-=G-vexs0=花果山;JD-elem0.ticket=100元/人;JD-roduce=花果山风景区是国家级重点风景名胜区。花果山以古连云港花果山风景区典名著西游记所描述的“孙大圣老家”而著称于世，名闻海内外。;按上述方式依次初始化每一个景点的序号、名称、门票和简介JD-length=上面初始化的景点数;（4）.int Locate(AdjMatrix *g , string a)寻找图中与输入景点名称相同的景点，然后该景点的位置（5）.void CreateUDG(AdjMatrix *G)int i,j;G-arcnum=10;G-vexnum=5;for(i=0 ; ivexnum ; i+)for(j=0 ; jvexnum ; j+)初始化每条路径的长度为INFINITY;G-arcs01.adj=G-arcs10.adj=33.4;按上面的方法给每条路径赋值（6）.void Menu()输出包含“景点查询、最短路径查询、所有路径查询、动态添加景点”四个选项的菜单，并输出让用户选择的提示（7）.void Search(jd JD , string Name)int i=0 ;while(1)if(待查询景点名称与第i个景点名相同)输出该景点所有信息i=i+1;vector allPath;/向量，用来存放所有的顶点va到顶点vb的路径vector all;/向量，用来存放对应路径的长度（8）.void Allway(AdjMatrix G,bool *visited,string vexs,double Long,string vb,string path) If（访问的景点名与终点名称相同） 将路径放入向量allPath中将路径长放入向量all中else 访问景点，递归Allway自身（9）.void CountMinway(AdjMatrix G)string va,vb;string path; /存放路径coutva;coutendl; coutvb;coutendl;if(输入景点不在录入景点中) 返回错误else 清除上一次查询的结果 递归调用Allway（10）.void Minway()比较求出的所有路径长度，得到权值最小的路径cout最短路径: 最短路径 长度:最短路径长度endl;coutendl; int visitedMAX_VERTEX_NUM; int xMAX_VERTEX_NUM;（11）.void AllPath(AdjMatrix *G , int v , int s)if(xv-1的值等于终点s)输出每条路径else for(int i=0 ; ivexnum ; i+)if(G-arcsxv-1i.adj!=INFINITY & visitedi=0)visitedi=1;/将第i个结点标记为已访问xv=i;AllPath(G,v+1,s);/从下一结点开始递归调用visitedi=0;返回时将已访问的结点重新置为未访问（12）.void AddInt(AdjMatrix *G , jd *JD)依次输入新增景点的名称、门票和简介信息将景点数加1结点数加1路径增加以前的路径数for(int j=0 ; jlength-1 ; j+)输入该景点道每个景点的距离（13）.void main()jd JD;AdjMatrix G;Insjd(&JD,&G);/初始化景点CreateUDG(&G);/创建无向图string Name;string Start , Stop;int m;bool flag=1;while(flag)Menu();char choose;cinchoose;switch(choose)case A:/景点查询for(m=0 ; mJD.length ; m+)输出已录入的每个景点名称；输入要查询的景点名Name；定位景点，如果有该景点，运行Search(JD, Name)查找，否则提示错误并结束； break;case B:/最短路径查询CountMinway(G);/找出所有路径Minway();/输出最短路径break;case C:/所有路经查询for(m=0 ; m输入一个系统尚未录入的景点，如渔湾 输出提示的错误信息 结果正确 2.2输入一个系统已录入的景点，如桃花涧 输出该景点所有信息，如名称：桃花涧门票：30元/人简介：桃花涧位于锦屏山桃花涧南麓，桃花涧距连云港市区9公里。这里山青水碧，谷幽涧深，而且每年的4月桃花遍开，桃花涧与山涧相互掩映，风景如画般美丽，桃花涧引来游人如织，因此名曰“桃花涧”。结果正确3.查询最短路径3.1输入一个系统尚未录入的起点或终点，如桃花涧和渔湾 输出提示的错误信息 结果正确3.2输入一个系统已录入的起点和终点，如花果山和连岛输出：花果山到连岛的最短路线为：花果山 -连岛长度为：33.4公里。结果正确4.查询所有路径4.1输入一个系统尚未录入的起点或终点，如桃花涧和渔湾 输出提示的错误信息 结果正确4.2输入一个系统已录入的起点和终点，如花果山和连岛 输出：花果山连岛花果山孔望山连岛花果山孔望山石棚山连岛花果山孔望山石棚山桃花涧连岛花果山孔望山桃花涧连岛花果山孔望山桃花涧石棚山连岛花果山石棚山连岛花果山石棚山孔望山连岛花果山石棚山孔望山桃花涧连岛花果山石棚山桃花涧连岛花果山石棚山桃花涧孔望山连岛花果山桃花涧连岛花果山桃花涧孔望山连岛花果山桃花涧孔望山石棚山连岛花果山桃花涧石棚山连岛花果山桃花涧石棚山孔望山连岛 结果正确5.动态添加景点输出渔湾输出50输出渔湾以瀑布著称，上山的路上一路都与水相伴，是旅游的好去处。输出30输出10输出22输出32输出35输出添加完毕！结果正确五 用户手册1.运行程序，首先出现主菜单。主菜单包括4个选项： 景点信息查询【A】景点间最短路径查询【B】景点间所有路径查询【C】动态添加景点【D】2.选择A景点查询时，提示输入要查询的景点，若系统已录入该景点，则会输出该景点多有信息，否则会提示输入错误，并结束查询；3.选择B查询最短路径时，提示输入起点和终点，如果起点和终点均已被系统录入，则会输出两点间最短路径，否则将提示输入错误，并结束查询；3.选择C查询所有路径时，提示输入起点和终点，如果起点和终点均已被系统录入，则会输出两点间所有路径，否则将提示输入错误，并结束查询；3.选择D添加景点信息时，将会提示输入景点名称、门票、简介，以及该景点与已有景点间的实际距离，输入完成后，提示添加完毕，并结束添加；4.结束上述操作后，系统将询问是否继续操作，如果您要继续操作，输入YES，系统将清屏并输出菜单供您继续才做，如果您不需要继续操作，则输入NO，系统将结束程序，如果您输入错误，既非YES亦非NO，系统将提示出错，并重新操作。六 测试成果1. 菜单界面2. 景点信息查询3. 景点间最短路径查询4. 景点间所有路径查询5. 动态添加景点6. 添加后景点信息查询7. 添加后景点间最短路径查询8. 添加后景点间所有路径查询七 附录（源程序清单）#include #include #include#include using namespace std;#define MAX_VERTEX_NUM 10#define INFINITY 32768#define AdjType doublevector allPath; /向量，用来存放所有的顶点va到顶点vb的路径vector all; /向量，用来存放对应路径的长度typedef string VertexData;typedef struct ArcNodeAdjType adj;ArcNode;typedef structVertexData vexsMAX_VERTEX_NUM;ArcNode arcsMAX_VERTEX_NUMMAX_VERTEX_NUM;int vexnum,arcnum;AdjMatrix;/景点结构体typedef struct jdNodeint num;string name;string ticket;string introduce;jdNode;/景点较多，通过jd结构体可以表示多个结构体类型typedef structjdNode elemMAX_VERTEX_NUM;int length;jd;/初始化景点资料void Insjd(jd *JD , AdjMatrix *G)JD-elem0.num=1;JD-=G-vexs0=花果山;JD-elem0.ticket=100元/人;JD-roduce=花果山风景区是国家级重点风景名胜区。景区面积12.8平方公里，规划面积110平方公里，层峦叠嶂136峰，其中花果山玉女峰是江苏省最高峰，海拔624.4 米。花果山以古连云港花果山风景区典名著西游记所描述的“孙大圣老家”而著称于世，名闻海内外。;JD-elem1.num=2;JD-=G-vexs1=连岛;JD-elem1.ticket=50元/人;JD-roduce=连岛古称鹰游山，面积7.6平方公里，是江苏省最大的海岛，与连云港港隔海相望，通过6.7公里的中国最长的拦海大堤与连云港市东部城区相连。集青山、碧海、茂林、海蚀奇石、天然沙滩、海岛渔村人文景观于一体，是江苏唯一的AAAA级海滨旅游景区，还以盛产海鲜著称。得天独厚的资源已使连岛成为夏季避暑纳凉、踏浪休闲娱乐、享受海鲜美味的旅游胜地。;JD-elem2.num=3;JD-=G-vexs2=孔望山;JD-elem2.ticket=40元/人;JD-roduce=国家4A级景区孔望山正因为孔子登山望海，而成为中国文化史册上的千年奇山。孔望山-位于江苏连云港市海州古城城东，锦屏山东北麓，东西长800米，南北宽300米，海拔高度129米，传说孔子曾登此山而望东海，故名孔望山。唐时此山称龙兴山，南宋防金，又称巡望山。以丰富的人文景观而著称，是国家级风景名胜区、全国重点文物保护单位。;JD-elem3.num=4;JD-=G-vexs3=石棚山;JD-elem3.ticket=25元/人;JD-roduce=石棚山景区，为国家3A级风景名胜区，是宋代文学家石曼卿、苏东坡的宦游之地，自古闻名遐迩。石棚山的得名是因为山上有一处天然石棚，据清嘉庆海州直隶州志记载：“山有巨石，复压岩上如棚因名，一名万花岩，又名锦岩山。”山上满布奇石，佛手岩、天蟾独跃、犀牛斗象等，形态逼真，栩栩如生。景区内除汉糜竺墓、宋石曼卿读书处、明张公去思碑、清锦岩碑林等原有的名胜古迹之外，近年又投资数百万元新建了虹桥、交华亭、花径、石棚山庄诸景。该景区地处城郊，资源丰富，是海州“三山一涧一古城”中的一颗灿烂的明珠。;JD-elem4.num=5;JD-=G-vexs4=桃花涧;JD-elem4.ticket=30元/人;JD-roduce=桃花涧位于锦屏山桃花涧南麓，桃花涧距连云港市区9公里。这里山青水碧，谷幽涧深，而且每年的4月桃花遍开，桃花涧与山涧相互掩映，风景如画般美丽，桃花涧引来游人如织，因此名曰“桃花涧”。;JD-length=5;/创建无向图int Locate(AdjMatrix *g , string a)for(int i=0 ; ivexnum ; i+)if(a=g-vexsi)return i;return -1;void CreateUDG(AdjMatrix *G)int i,j;VertexData v1,v2;G-arcnum=10;G-vexnum=5;for(i=0 ; ivexnum ; i+)for(j=0 ; jvexnum ; j+)G-arcsij.adj=INFINITY;G-arcs01.adj=G-arcs10.adj=33.4;G-arcs02.adj=G-arcs20.adj=17.8;G-arcs03.adj=G-arcs30.adj=33.7;G-arcs04.adj=G-arcs40.adj=39.7;G-arcs12.adj=G-arcs21.adj=56.1;G-arcs13.adj=G-arcs31.adj=75;G-arcs14.adj=G-arcs41.adj=66.6;G-arcs23.adj=G-arcs32.adj=4;G-arcs24.adj=G-arcs42.adj=9.3;G-arcs34.adj=G-arcs43.adj=12.6;/菜单void Menu()coutendl;cout * endl;cout 连云港景点导游咨询 endl;cout * endl;cout 景点信息查询【A】 endl;cout 景点间最短路径查询【B】 endl;cout 景点间所有路径查询【C】 endl;cout 动态添加景点【D】 endl;cout * endl;cout * endl;coutendl;cout $ $ $ $ $ $ $ $ $ $ $ $ $ $ endl;cout 请您选择: ;/查询景点信息void Search(jd JD , string Name)int i=0 ;while(1)if(Name=JD.)coutName简介如下：endl;cout-endl;cout景点编号：JD.elemi.numendl;cout景点名称：JD.endl;cout景点门票：JD.elemi.ticketendl;cout景点简介：endl JD.roduceendl;cout-endl+vexs;allPath.push_back(path); /将路径放入向量中all.push_back(Long); /将路径长放入对应向量中elsepath=path+-+vexs;int i=Locate(&G,vexs);visitedi=true;for(int j=0;jG.vexnum;j+)if(!visitedj)&(G.arcsij.adj!=0)Allway(G,visited,G.vexsj,Long+G.arcsij.adj,vb,path); /递归调用自身visitedi=false; /退出递归前清除访问记录void CountMinway(AdjMatrix G) /该函数调用递归部分实现递归string va,vb;string path; /存放路径coutva;coutendl; coutvb;coutendl;if(Locate(&G , va)=-1 | Locate(&G , vb)=-1)coutendl -OH NO ! ! ! 输入错误 ! ! ! YOU ARE WRONG ! ! !-endlendl;else allPath.clear();all.clear();int i=Locate(&G,va);bool visited100;for(int j=0;jG.vexnum;j+)visitedj=false; /初始化访问记录，全都未访问过visitedi=true; /起点顶点设为访问过double Long=0;path+=va;for( j=0;jG.vexnum;j+)if(G.arcsij.adj!=0)Long=G.arcsij.adj;Allway(G,visited,G.vexsj,Long,vb,path); /调用递归部分coutendl;void Minway()/输出最短路径double min=10000;for(int i=0;iallPath.size();i+)if(allimin)min=alli;for(int j=0;jallPath.size();j+)if(allj=min)cout最短路径: allPathj 长度:alljendl;coutendl;/查询全部路径int visitedMAX_VERTEX_NUM;int xMAX_VERTEX_NUM;void AllPath(AdjMatrix *G , int v , int s)if(xv-1=s)coutsetw(7)setiosflags(ios:left)vexsx0;for(int i=1;iv;i+)cout ;coutsetw(7)setiosflags(ios:left)vexsxi;coutendlendl;else for(int i=0 ; ivexnum ; i+)if(G-arcsxv-1i.adj!=INFINITY & visitedi=0)visitedi=1;xv=i;AllPath(G,v+1,s);visitedi=0;/动态添加景点void AddInt(AdjMatrix *G , jd *JD)int i=JD-length;JD-elemi.num=i+1;cout请输入景点信息：endl;cout-endl;coutJD-;G-vexsi=JD-;couta;JD-elemi.ticket=a+元/人;coutJD-roduce;JD-length=i+1;G-vexnum=G-vexnum+1;G-arcnum=G-arcnum+1;G-arcsii.adj=INFINITY;for(int j=0 ; jlength-1 ; j+)cout到vexsjG-arcsji.adj;G-arcsij.adj=G-arcsji.adj;coutendl;cout-endlendl;cout添加完毕！endlchoose;cout $ $ $ $ $ $ $ $ $ $ $ $ $ $ endlendl;switch(choose)case A:/景点查询cout系统已录入景点如下：endl;cout-endl;for(m=0 ; mJD.length ; m+)coutJD. ;coutendl-endlendl;cout请输入您要查找的景点：endl;cout-Name;cout-endlendl;if(Locate(&G , Name)=-1)coutendl -OH NO ! ! ! 输入错误 ! ! ! YOU ARE WRONG ! ! !-endlendl;break;elseSearch(JD, Name);break;case B:/最短路径查询CountMinway(G); /找出所有路径Minway(); /输出最短路径break;case C:/所有路经查询for(m=0 ; mJD.length ; m+)visitedm=0;coutStart;coutendl;coutStop;if(Locate(&G , Start)=-1 | Locate(&G , Stop)=-1)coutendl -OH NO ! ! ! 输入错误 ! ! ! YOU ARE WRONG ! ! !-endlendl;break;elsex0=Locate(&G , Start);visitedLocate(&G , Start)=1;coutendl;cout所有路径为：endl;coutendl;AllPath(&G , 1 , Locate(&G , Stop);cout-endlendl;break;case D:/动态添加景点AddInt(&G,&JD);break;default:cout- % % % % % % % 输入错误 ! % % % % % % % -endlendl;break;cout - 您还需要继续操作吗？如果需要，请输入“