数据结构课程设计-校园导游咨询

数据结构课程设计--校园导游咨询数据结构课程设计--校园导游咨询数据结构课程设计--校园导游咨询数据结构课程设计--校园导游咨询编制仅供参考审核批准生效日期地址：电话：传真:邮编:琼州学院电子信息工程学院课程设计报告课程名称：《数据结构》课程设计设计题目：校园导游咨询专业：软件工程班级：2010软件工程学生姓名：学号：起止日期：指导教师：指导教师评语：最终成绩：指导教师签名：年月日成绩评定项目权重成绩1、设计过程中的学习态度0.22、课程设计的质量及答辩0.53、设计报告书规范程度0.34、总成绩注意事项一、设计目的《数据结构》是一门实践性较强的软件基础课，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。二、设计要求1．通过这次课程设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。2．学生必须仔细研读《数据结构》课程设计要求，以学生自学为主、指导教师指导为辅，独立完成课程设计的任务，有问题及时主动与指导教师沟通。3．本次课程设计按照教学要求需要在本学期15周前完成，学生要发挥自主学习的能力，充分利用时间，安排好课程设计的时间计划，并在课程设计过程中不断检测自己的计划完成情况，及时向指导教师汇报。4．编程语言：C语言。三、课程设计说明书的格式要求设计文档的撰写必须提前进行，以保证使文档与程序同步提交。1．设计题目2．运行环境（软、硬件环境）3．算法的需求分析4．算法概要设计5．算法详细设计6．算法的测试7．运行结果分析8．收获及体会四、问题分析、设计和测试过程要规范化1．需求分析：将题目中要求的功能进行叙述分析。2．概要设计：算法的设计说明，描述解决此问题的数据存储结构，（有些题目已经指定了数据存储的，按照指定的设计），描述算法建议使用流程图，进行算法分析指明关键语句的时间复杂度。3．详细设计：即各个算法的具体实现步骤，每个题目要有相应的源程序，其中每个功能模块采用不同的函数实现。源程序要规范编写：结构要清晰，注释要清楚。重点函数的重点变量和重点功能部分要加上清楚的程序注释。4．调试和测试：给出实现功能的一组或多组测试数据，程序调试后，将按照此测试数据进行测试的结果列出来。在调试过程中遇到的问题和解决方法也要记录下来。程序要能够正常运行，还要有基本的容错功能。尽量避免出现操作错误时出现死循环。5．改进措施：

对有些题目提出算法改进方案，比较不同算法的优缺点。五、对指导教师的要求指导教师要关心学生的课程设计进展，认真答疑。对课程设计报告的撰写要给予充分的指导，报告中切忌出现大篇源代码，应严格要求学生将主要篇幅放在“原理实现”上，即如何用框图表达设计和实施思想。课程设计报告要用红笔批阅，最终成绩以优、良、中、及格与不及格分等计算。目录摘要 11设计内容和要求 -2-1.1设计内容 -2-1.1设计要求 -2-2概要设计 22.1程序的模块图 22.2主函数的概要设计 32.3查找介绍函数的概要设计 32.4查找最短路径函数的概要设计 32.5景点分布图的概要设计 32.6退出函数的概要设计 33详细设计 53.1程序的流程图 53.2主函数的详细设计 63.3查找介绍函数的详细设计 63.4查找最短路径函数的详细设计 73.5景点分布图的详细设计 83.6退出函数的详细设计 93.7数据结构的详细设计 94软件测试 104.1菜单的测试 104.2查找景点简介的测试 114.3查找两个景点之间的最短距离的测试 124.4查看景点分布图的测试 134.5退出的测试 145软件使用说明 156参考文献 167附录 177.1系统完整代码 17摘要现代快节奏的生活使得都市人越来越渴望亲近自然，因此外出旅游现在被越来越多的都市人所看中，所以如何快速方便的找到我们想要的旅游景点的信息和最短路径就成了一个很重要的问题。本设计基于图的结构，创建一个无向图，针对游客的实际需求，将琼州学院的景点编号、名称、介绍等信息放入到图的顶点当中并保存在景点文本文件当中，将两个景点的编号和它们之间的距离当作权值也保存到权值文本文件当中，利用迪杰斯特拉算法来求从一个景点到另一个景点的最短距离，利用Search();函数来查找景点，并显示出它的信息，从而解决了要查找景点信息和景点之间的最短路径的问题，最后按照显示屏上的提示进行相关的操作。关键词：分布图、查找信息、最短距离、校园导游咨询1设计内容和要求1.1设计内容 依据课程设计的要求，利用一个无向图的结构，将景点当作图的顶点，将景点之间的距离当作权值来储存，然后根据游客自己的需求，按照显示屏上的提示来进行查找景点介绍，查找两个景点之间的最短距离，退出程序等基本操作。1.1设计要求本软件为校园导游咨询系统，根据游客的实际需求而设计，首先创建一个无向图，然后从文件当中读取所有景点的编号、名称、介绍和两点之间的权值，并将它们写入到无向图当中。功能主要包括查找已知景点的信息，查找从一个景点到另一个景点的最短路径，退出等基本操作。软件的界面要求使用VC++6.0的运行环境。软件的数据库包括校园景点的编号、名称、介绍和两个景点之间的距离（权值），首先要定义顶点的数据类型结构体，里面包括景点的编号、名称、介绍，然后定义一个邻接矩阵结构体来储存边的信息，最后定义一个无向图类型的结构体来储存顶点的信息，边的信息，顶点的个数，边的条数。最后游客按照显示屏上的提示来进行相关的操作。2概要设计2.1程序的模块图本软件的算法依据无向图的操作通过查找函数查找景点的信息，通过费洛伊德函数来查找最短距离，开始时首先从文件当中读取景点的编号、名称、介绍和两个景点之间的距离即权值，然后将其加入到图当中，再调用查找函数查找景点的信息，调用费洛伊德函数来查找最短距离，调用退出函数实现退出功能，其模块图如图2.5所示：开始开始加入图加入图分布图退出最短距离查找信息分布图退出最短距离查找信息屏幕显示屏幕显示屏幕显示屏幕显示屏幕显示屏幕显示图2.5模块图2.2主函数的概要设计 基于程序的操作要求，对于主函数的设计首先是显示一个可视化的操作界面提醒游客进行相关的操作和提示游客其可供选择的景点的名称，便于其在后面的操作过程当中能够快速方便的找到其需要查找的景点的名称。而后就是一个switch（）；的选择函数，提供查找景点信息，查找两个景点之间的最短距离和退出的相关的选择操作而后进入到每一个操作界面当中，从而实现所需要的功能。2.3查找介绍函数的概要设计 当游客选择了要查找景点的信息的介绍这一项功能的时候，就会进入到查找的界面，对于查找景点信息就是利用Search();函数，当游客输入景点的名称的时候看其是否与文件当中的数据相匹配，如果有则输出它的介绍，如果没有则输出错误的提示提醒游客进行相关的操作来进入到正确的操作过程当中。2.4查找最短路径函数的概要设计 对于查找最短路径的这一项功能，可以利用迪杰斯特拉算法，但我是用的费洛伊德算法，相对来说步骤跟简单一点。后面有详细介绍。2.5景点分布图的概要设计先手稿绘制所有景点的分布，利用printf（）；函数打印分布图的框架构造。各景点之间用线条链接，通过分布图能全面的对校园各景点有个方位感。2.6退出函数的概要设计 关于退出函数，则是当游客执行完了他想要进行的操作过后选择退出的功能的时候就调用退出函数exit(0);跳入到退出界面实现退出的功能。3详细设计3.1程序的流程图 当我们想要更加实际的了解一个程序的算法过程的时候，我们就要依据程序的流程图来给我们一个比较实际的过程，从流程图当中能够更加清楚整个程序实现的过程是怎样的。其流程图如图3.1所示：startstart创建无向图写入无向图中Case3Case2Case1查找信息最短路径TTFFCase4分布图TendF图3.1流程图3.2主函数的详细设计 主函数是一个程序的主体，当我们要进行我们所需要的操作的时候我们就要根据主函数中的显示信息和它给我们的相关的提示信息来进行所需要的操作，因此在这次的程序实现的过程当中，调用 Browser();提示游客根据switch();的选择语句，选择来进入到相关的操作界面实现程序的基本功能。，3.3查找介绍函数的详细设计 当游客选择了要查找景点的信息的介绍这一项功能的时候，程序就会调用Search();函数进入到查找景点的介绍的界面，当游客输入了需要查找的景点的编号的时候，程序通过结构体，自动匹配相应的信息，查找是否有这个景点。voidSearch(MGraph*G){ intk,flag=1; while(flag){ printf("请输入要查询的景点编号:"); scanf("%d",&k); if(k<=0||k>G->vexnum){ printf("景点编号不存在!请重新输入景点编号:"); scanf("%d",&k); } if(k>0&&k<=G->vexnum)flag=0; } printf("\n┏━━┳━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n"); printf("┃编号┃景点名称┃简介┃\n"); printf("┃%-4d┃%-16s┃%-62s┃\n",G->vexs[k].num,G->vexs[k].name,G->vexs[k].introduction); printf("┗━━┻━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");}，找到将它的编号返回，并输出它的介绍，没有找到这输出错误提示，提醒游客进行相关的操作进入正确的操作过程当中。3.4查找最短路径函数的详细设计 当游客选择了要查找两个景点之间的最短距离这一项功能的时候，函数进入到查找两个景点之间的最短距离的操作界面当中，当游客输入了两个景点的名称过后，程序会判断是否有这两个景点，如果有则返回他们各自的编号，并调用Floyd();函数进入到查找最短路径问题的程序当中。voidFloyd(MGraph*G){ intv,u,i,w,k,j,flag=1,p[14][14][14],D[14][14]; for(v=1;v<=G->vexnum;v++) for(w=1;w<=G->vexnum;w++) { D[v][w]=G->arcs[v][w].adj; for(u=1;u<=G->vexnum;u++) p[v][w][u]=0; if(D[v][w]<INFINITY) { p[v][w][v]=1;p[v][w][w]=1; } } for(u=1;u<=G->vexnum;u++) for(v=1;v<=G->vexnum;v++) for(w=1;w<=G->vexnum;w++) if(D[v][u]+D[u][w]<D[v][w]) { D[v][w]=D[v][u]+D[u][w]; for(i=1;i<=G->vexnum;i++) p[v][w][i]=p[v][u][i]||p[u][w][i]; } while(flag) { printf("请输入出发点和目的地的编号:"); scanf("%d%d",&k,&j); if(k<=0||k>G->vexnum||j<=0||j>G->vexnum) { printf("景点编号不存在!请重新输入出发点和目的地的编号:"); scanf("%d%d",&k,&j); } if(k==j) { printf("出发点和目的地一样!请重新输入出发点和目的地的编号:"); scanf("%d%d",&k,&j); } if(k>0&&k<=G->vexnum&&j>0&&j<=G->vexnum) flag=0; } printf("\n最短游览路线：%s",G->vexs[k].name); if(k>j){ for(u=G->vexnum;u>0;u--) if(p[k][j][u]&&k!=u&&j!=u) printf("-->%s",G->vexs[u].name);} if(k<j){ for(u=1;u<=G->vexnum;u++) if(p[k][j][u]&&k!=u&&j!=u) printf("-->%s",G->vexs[u].name);} printf("-->%s",G->vexs[j].name); printf("总路线长%dm\n",D[k][j]);} 已知有n个顶点的有向图,佛洛伊德算法可以求解出每一对顶点之间的最短路径。假设使用邻接矩阵d(i,j)来对图进行存储,d(i,j)表示υi到υj之间的距离,但是该距离不一定是最短距离。佛洛伊德算法的基本思想是:为求顶点υi→υj之间的最短距离,需要进行n次试探。首先将υ0加入路径,考虑路径υi→υ0→υj是否存在,如果存在,则比较υi→υj和υi→υ0→υj的路径长度,取长度短的路径作为υi→υj的路径,记作(υi,υj)。接着在路径上再增加一个顶点υ1,比较υi→υ1→υj和(υi,υj)的路径长度,取长度短的路径作为(υi,υj)。不断将顶点υ2,υ3,.,υn-1加入进行试探,最后得到的(υi,υj)必定为υi→υj的最短路径。若使用数组dk(i,j)表示加入顶点k后,最短路径长度的变化情况,使用数组pk(i,j)表示加入顶点k后,最短路径上顶点的变化情况,这样就求得了最短路径和最短路径长度。3.5景点分布图的详细设计 这里不详细介绍，具体代码，查看附录browse_view_distribute()函数。3.6退出函数的详细设计 对于退出函数，当游客选择了退出这一个操作的时候，程序就会调用exit(0);函数实现退出主函数的功能。最后会提示游客，欢迎下次继续使用！3.7数据结构的详细设计 本软件的数据结构包括3个部分：邻接矩阵typedefintAdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];定义一个邻接矩阵，用邻接矩阵来定义和储存边的相关信息。2.顶点的结构体typedefstructVertex//定义图中顶点的数据类型{ intnum;//景点编号 charname[30];//景点名称 charintroduction[200];//景点介绍}Vertex;定义一个顶点的结构体，用来储存景点的编号、景点得名称和景点的介绍等关于景点的信息。3.无向图的结构体typedefstruct//定义图的数据类型{ Vertexvexs[MAX_VERTEX_NUM];//顶点的结构体 AdjMatrixarcs;//边的邻接矩阵 intvexnum,arcnum;//顶点的个数，边的个数}MGraph;定义一个图的结构体，用来储存顶点的信息、边的信息、顶点的个数和边的个数等相关的信息便于我们以后在用的时候能够方便快捷的调用。定义好这些结构体后，当我们以后需要调用的时候，我们就能够方便快捷的调用这些结构体，从而使得我们在运行程序的时候能够更加的快速能够提高我们的程序的运行效率，大大的节省了我们的时间还使得程序变得更加的简单。4软件测试4.1菜单的测试 对于菜单函数的测试，首先菜单是一个可示化的界面，它能够提示游客依据显示屏上出现的提示来进行相关的操作，查看所有的景点从而方便游客进行相关的操作，因而我们在运行程序的时候首先就会进入到菜单函数当中，经过测试其能够实现我们所要实现得基本功能，其效果图如图4.1所示：图4.1菜单4.2查找景点简介的测试 对于查找景点的介绍的测试，首先依据显示屏上的提示首先输入要进行的操作输入3进入查找景点信息的操作界面，然后输入需要查找的景点的名称即可显示出景点的介绍信息，经过测试可以得出其没有什么错误，程序能够按照我的要求实现它的功能，其效果图如图4.2所示：图4.2查找景点信息4.3查找两个景点之间的最短距离的测试 同查找景点的信息一样，对于查找景点之间的最短距离的测试，我们就要依据提示输入2进入到查询最短路径的界面，依次输入所需要查找的两个景点就会显示出怎样到达这两个景点并显示出它们之间的最短路径，经过测试可见程序能够按照我的要求来实现其所需要的功能，其效果图如图4.3所示：图4.3查找两个景点之间的最短距离4.4查看景点分布图的测试对于查看景点分布图的测试，我需要依据显示屏上的提示，需要输入1进入到分布图的界面，系统就会直接调用browse_view_distribute();函数，在屏幕上打印出景点的分布图。图4.4景点分布图界面4.5退出的测试 原理同上，对于退出函数的测试，我需要依据显示屏上的提示，需要输入4进入到退出的界面，系统就会直接调用退出的函数，显示出“欢迎下次继续使用！”的话，退出了系统，其效果图如图4.4所示：图4.5退出界面5软件使用说明 对于软件的使用，对于第一次使用软件的游客来说，要让他们在第一次用的时候就能够快速轻松的掌握软件的用法，因此在程序一开始运行的时候，我们要进行如下的操作：（1）首先我会给游客提供一个可视化的菜单操作界面，在显示屏上提示用户其可以进行的操作和他能够查询的景点的编号、名称。（2）用户输入了“1”后，屏幕上会显示出所有景点的位置关系平面图。能够大致了解景点的分布。（3）当用户输入了“2”后，进入到查询任意两景点间最短路径的界面，然后提示用户依次输入两个景点的编号，程序就会将这两个景点的最短路径给我们表示出来并显示出最短路径是多少。（4）用户输入了“3”后，进入到查询景点信息的界面，然后提示用户输入景点的编号（一次限一个），程序就会显示出这个景点的详细介绍。（5）当用户输入了“4”后，进入到退出界面，这时系统就会显示“欢迎下次继续使用!”的提示语，最后按下任意键退出系统。6参考文献数据结构(C语言版)严蔚敏吴伟民编著清华大学出版社2002C程序设计经典教程，[美]Deitel,H.M.，[美]Deitel,P.J.著，清华大学出版社2006Windows程序设计，[美]CharlesPetzold著，北京大学出版社2004DataStructures：APseudecode（ApproachwithC）[美]RichardF.Gilberg，[美]BehrouzA.Forouzan著7附录7.1系统完整代码#defineINFINITY10000/*无穷大*/#defineMAX_VERTEX_NUM40#defineMAX40#include<stdlib.h>#include<stdio.h>#include<conio.h>#include<string.h>#include"Exit.h"typedefstructArCell{ intadj;//路径长度}ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct//图中顶点表示主要景点，存放景点的编号、名称、简介等信息，{ charname[30]; intnum; charintroduction[200];//简介}infotype;typedefstruct{ infotypevexs[MAX_VERTEX_NUM];//景点 AdjMatrixarcs;//路径数组 intvexnum,arcnum;//景点数，路径长度记录}MGraph;MGraphb;//全局变量voidcmd(void);//在主函数中用来调用其他应用子函数的函数声明MGraphInitGraph(void);//用来构造学校地图的子函数返回MGraph类型voidMenu(void);//菜单函数；voidBrowser(MGraph*G);//调用MGraph类型的地址，进行voidShortestPath_DIJ(MGraph*G);//迪杰斯特拉算法求最短路径的子函数voidFloyd(MGraph*G);//佛洛伊德算法voidSearch(MGraph*G);//寻找要查询的景点，并输出该景点的信息voidbrowse_view_distribute();//查看景点分布图voidtou(MGraph*G);//景点列表voidpanduan();//voidExit();//退出intLocateVex(MGraph*G,char*v);//定点位置MGraph*CreatUDN(MGraph*G);////初始化图形，接受用户输入voidprint(MGraph*G);//打印输出子函数/******************************************************/voidmain(void){ system("color1f");//设置调试窗口背景和字体颜色 system("modecon:cols=140lines=130");//设置调试窗口的大小 cmd();//用该函数来调用其他需要用到的函数}/******************************************************/voidcmd(void)//用来调用其他需要用到的函数的子函数{ inti; b=InitGraph();//构造校园地图 Browser(&b);//Menu();//调用菜单函数 scanf("%d",&i); while(i!=4) { switch(i) { case1:system("cls");/*ShortestPath_DIJ(&b);*/browse_view_distribute();Browser(&b);break; case2:system("cls");tou(&b);Floyd(&b);Browser(&b);break; case3:system("cls");tou(&b);Search(&b);Browser(&b);break; case4:exit(0);break; default:break; } scanf("%d",&i); } printf("欢迎下次继续使用!\n\n");}//*******************************************************************MGraphInitGraph(void)//构造校园地图{ MGraphG; inti,j; G.vexnum=13;//景点数量 G.arcnum=21;//路径数量 for(i=1;i<=G.vexnum;i++) G.vexs[i].num=i;//对景点进行对应编号/*对对应的景点编号进行命名，输入简介*/ strcpy(G.vexs[3].name,"行政办公楼");strcpy(G.vexs[3].introduction,"学校的行政机构。"); strcpy(G.vexs[6].name,"图书馆"); strcpy(G.vexs[6].introduction,"体积庞大，是学校的标志性建筑，目前还在建设中。"); strcpy(G.vexs[2].name,"果园"); strcpy(G.vexs[2].introduction,"枝叶茂盛，各种新鲜水果。");strcpy(G.vexs[1].name,"校门"); strcpy(G.vexs[1].introduction,"学校的形象，气势宏伟。"); strcpy(G.vexs[4].name,"体育运动区"); strcpy(G.vexs[4].introduction,"包括有排球场、篮球场、网球场等。"); strcpy(G.vexs[5].name,"教学区"); strcpy(G.vexs[5].introduction,"包括左教学楼、小湖、右教学楼、实验楼和医务室等。"); strcpy(G.vexs[10].name,"男生宿舍"); strcpy(G.vexs[10].introduction,"分1、2、7、8栋，供男同学居住，女生勿进。"); strcpy(G.vexs[7].name,"琴房"); strcpy(G.vexs[7].introduction,"音乐学院学生练琴的地方。"); strcpy(G.vexs[8].name,"足球场"); strcpy(G.vexs[8].introduction,"踢球，跑步，运动比赛场地。"); strcpy(G.vexs[9].name,"省高速路"); strcpy(G.vexs[9].introduction,"上面是省高速路，下面是人行隧道。"); strcpy(G.vexs[11].name,"食堂"); strcpy(G.vexs[11].introduction,"分1、2、3、4楼，价格有所不同，根据自己爱好，随意点菜。"); strcpy(G.vexs[12].name,"女生宿舍"); strcpy(G.vexs[12].introduction,"楼下一“爱心”超市，价格绝对不便宜。楼上女同学居住，男生勿进。"); strcpy(G.vexs[13].name,"教师村"); strcpy(G.vexs[13].introduction,"老师们的居住地，10多楼高。");//对有路的各景点之间的路径长度进行设置,没路的设置为无穷大for(i=1;i<=G.vexnum;i++)for(j=1;j<=G.vexnum;j++) G.arcs[i][j].adj=INFINITY; G.arcs[1][3].adj=100; G.arcs[1][2].adj=100; G.arcs[1][5].adj=200; G.arcs[2][4].adj=100; G.arcs[2][3].adj=150; G.arcs[3][5].adj=200; G.arcs[3][8].adj=300; G.arcs[4][5].adj=100; G.arcs[4][7].adj=150; G.arcs[5][6].adj=100; G.arcs[6][7].adj=150; G.arcs[6][8].adj=100; G.arcs[7][9].adj=50; G.arcs[8][9].adj=200; G.arcs[8][13].adj=200; G.arcs[9][10].adj=200; G.arcs[9][11].adj=150; G.arcs[9][12].adj=200; G.arcs[10][11].adj=100; G.arcs[11][12].adj=150; G.arcs[12][13].adj=150;//无向图的路径是相互的for(i=1;i<=G.vexnum;i++) for(j=1;j<=G.vexnum;j++) G.arcs[j][i].adj=G.arcs[i][j].adj;returnG;}//InitGraphend//*******************************************************************/*//菜单函数，打印出导游项目菜单voidMenu(){ printf("\n琼州学院校园导游图\n"); printf("┏━━┳━━━━━━━━━━━━━━━━━━┓\n");printf("┃编号┃实现的功能┃\n"); printf("┣━━╋━━━━━━━━━━━━━━━━━━┫\n"); printf("┃1┃查看景点分布图┃\n"); printf("┣━━╋━━━━━━━━━━━━━━━━━━┫\n"); printf("┃2┃查找两景点间最短距离┃\n"); printf("┣━━╋━━━━━━━━━━━━━━━━━━┫\n");printf("┃3┃查看景点信息┃\n"); printf("┣━━╋━━━━━━━━━━━━━━━━━━┫\n");printf("┃4┃退出系统┃\n"); printf("┗━━┻━━━━━━━━━━━━━━━━━━┛\n"); printf("输入你的操作编号：");}*///*******************************************************************//输出所有景点信息voidBrowser(MGraph*G){ intv; printf("┏━━┳━━━━━━┓\n"); printf("┃编号┃景点名称┃\n"); for(v=1;v<=G->vexnum;v++){ printf("┃%-4d┃%-12s┃",G->vexs[v].num,G->vexs[v].name); switch(v+2){ case4:printf("琼州学院校园导游图\n");break; case5:printf("┏━━┳━━━━━━━━━━━━━━━━┓\n");break; case6:printf("┃编号┃实现的功能┃\n");break; case7:printf("┣━━╋━━━━━━━━━━━━━━━━┫\n");break; case8:printf("┃1┃查看景点分布图┃\n");break; case9:printf("┣━━╋━━━━━━━━━━━━━━━━┫\n");break; case10:printf("┃2┃查找两景点间最短距离┃\n");break; case11:printf("┣━━╋━━━━━━━━━━━━━━━━┫\n");break; case12:printf("┃3┃查看景点信息┃\n");break; case13:printf("┣━━╋━━━━━━━━━━━━━━━━┫\n");break; case14:printf("┃4┃退出系统┃\n");break; case15:printf("┗━━┻━━━━━━━━━━━━━━━━┛\n");break; default:printf("\n");break; }} printf("┗━━┻━━━━━━┛\n"); printf("输入你的操作编号：");}//*******************************************************************/*//迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径,v0为起点voidShortestPath_DIJ(MGraph*G){ intv,w,i,min,t=0,x,flag=1,v0;intfinal[20],D[20],p[20][20]; while(flag) { printf("请输入一个起始景点编号:"); scanf("%d",&v0); if(v0<=0||v0>G->vexnum) { printf("景点编号不存在!请重新输入景点编号:"); scanf("%d",&v0); printf("\n"); } if(v0>0&&v0<=G->vexnum) flag=0; } for(v=1;v<=G->vexnum;v++) { final[v]=0; D[v]=G->arcs[v0][v].adj; for(w=1;w<=G->vexnum;w++) p[v][w]=0; if(D[v]<INFINITY) { p[v][v0]=1;p[v][v]=1; } } D[v0]=0;final[v0]=1; for(i=1;i<=G->vexnum;i++) { min=INFINITY; for(w=1;w<=G->vexnum;w++) if(!final[w]) if(D[w]<min){v=w;min=D[w];} final[v]=1; for(w=1;w<=G->vexnum;w++) if(!final[w]&&(min+G->arcs[v][w].adj<D[w])) { D[w]=min+G->arcs[v][w].adj; for(x=1;x<=G->vexnum;x++) p[w][x]=p[v][x]; p[w][w]=1; } } for(v=1;v<=G->vexnum;v++) { if(v0!=v)printf("%s",G->vexs[v0].name); for(w=v0;w>0;w--) { p[v][v0-v]=0; if(p[v][w]&&w!=v0)printf("-->%s",G->vexs[w].name); t++; printf("yyyy"); } for(w=v0-1;w<=G->vexnum;w++) { if(p[v][w]&&w!=v0)printf("-->%s",G->vexs[w].name); t++; printf("xxxx"); } if(t>G->vexnum-1&&v0!=v)printf("总路线长%dm\n\n",D[v]); }}//ShortestPath_DIJend*///*******************************************************************voidFloyd(MGraph*G){ intv,u,i,w,k,j,flag=1,p[14][14][14],D[14][14]; for(v=1;v<=G->vexnum;v++) for(w=1;w<=G->vexnum;w++) { D[v][w]=G->arcs[v][w].adj; for(u=1;u<=G->vexnum;u++) p[v][w][u]=0; if(D[v][w]<INFINITY) { p[v][w][v]=1;p[v][w][w]=1; } } for(u=1;u<=G->vexnum;u++) for(v=1;v<=G->vexnum;v++) for(w=1;w<=G->vexnum;w++) if(D[v][u]+D[u][w]<D[v][w]) { D[v][w]=D[v][u]+D[u][w]; for(i=1;i<=G->vexnum;i++) p[v][w][i]=p[v][u][i]||p[u][w][i]; } while(flag) { printf("请输入出发点和目的地的编号:"); scanf("%d%d",&k,&j); if(k<=0||k>G->vexnum||j<=0||j>G->vexnum) { printf("景点编号不存在!请重新输入出发点和目的地的编号:"); scanf("%d%d",&k,&j); } if(k==j) { printf("出发点和目的地一样!请重新输入出发点和目的地的编号:"); scanf("%d%d",&k,&j); } if(k>0&&k<=G->vexnum&&j>0&&j<=G->vexnum) flag=0; } printf("\n最短游览路线：%s",G->vexs[k].name); if(k>j){ for(u=G->vexnum;u>0;u--) if(p[k][j][u]&&k!=u&&j!=u) printf("-->%s",G->vexs[u].name);} if(k<j){ for(u=1;u<=G->vexnum;u++) if(p[k][j][u]&&k!=u&&j!=u) printf("-->%s",G->vexs[u].name);} printf("-->%s",G->vexs[j].name); printf("总路线长%dm\n",D[k][j]);}//Floydend//****************************************************************//寻找要查询的景点，并输出该景点的信息voidSearch(MGraph*G){ intk,flag=1; while(flag) { printf("请输入要查询的景点编号:"); scanf("%d",&k); if(k<=0||k>G->vexnum) { printf("景点编号不存在!请重新输入景点编号:"); scanf("%d",&k); } if(k>0&&k<=G->vexnum) flag=0; } printf("\n┏━━┳━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n"); printf("┃编号┃景点名称┃简介┃\n"); printf("┃%-4d┃%-16s┃%-62s┃\n",G->vexs[k].num,G->vexs[k].name,G->vexs[k].introduction); printf("┗━━┻━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");}//Searchend//*******************************************************************intLocateVex(MGraph*G,char*v){ intc=-1,i; for(i=1;i<=G->vexnum;i++) if(strcmp(v,G->vexs[i].name)==0) {c=i;break;} returnc;}//******************************************************************MGraph*CreatUDN(MGraph*G)//初始化图形，接受用户输入{ inti,j,k,w; charv1[20],v2[20]; printf("请输入图的顶点数,弧数:"); scanf("%d%d",&G->vexnum,&G->arcnum); printf("请输入景点的编号:、名称、简介:\n"); for(i=1;i<=G->vexnum;i++) { printf("景点编号:"); scanf("%d",&G->vexs->num); printf("景点名称:"); scanf("%s",G->vexs[i].name); printf("景点简介:"); scanf("%s",G->vexs->introduction); } for(i=1;i<=G->vexnum;i++) for(j=1;j<=G->vexnum;j++) G->arcs[i][j].adj=INFINITY; printf("请输入路径长度:\n"); for(k=1;k<=G->arcnum;k++) { printf("第%d条边:\n",k+1); printf("景点对(x,y):"); scanf("%s",v1); scanf("%s",v2); printf("路径长度:"); scanf("%d",&w); i=LocateVex(G,v1); j=LocateVex(G,v2); if(i>0&&j>0) { G->arcs[i][j].adj=w; G->arcs[j][i]=G->arcs[i][j]; } }returnG;}//*******************************************************************voidbrowse_view_distribute(){//查看景点分布图，3 printf("§·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·∽·§\n"); printf("§§\n"); printf("§┏━━━━━┓┏━━━━━┓┏━━━━━┓┏━━━━━┓§\n"); printf("§┃┃┃┃┃┃┃┃§\n"); printf("§┃┃┃┃┃┃┃┃§\n"); printf("§┃⒑男生宿舍┣┅┫⒒食堂┣┅┅┫⒓女生宿舍┣┅┅┫⒔教师村┃§\n"); printf("§┃┃┃┃┃┃┃┃§\n"); printf("§┃┃┃┃┃┃┃┃§\n"); printf("§┗━━┳━━┛┗━━┳━━┛┗━━┳━━┛┗━━━┳━┛§\n"); printf("§┏━━┻━━━━━━━┻━━━━━━━━┻━━━━━━━━━┇━┓§\n");printf("§┃┇┃§\n"); printf("§┃-----------⒐省高速路-----------┇-┃§\n");printf("§┃┇┃§\n");printf("§┗━━┳━━━━━━━━━━━━━━━━━━━━━━┳━━━┇━┛§\n"); printf("§┏━━┻━━┓┏━━━━━━━━━━━━┓┏┻━━━┻━┓§\n"); printf("§┃┃┃┃┃┃§\n"); printf("§┃┃┃┃┃┃§\n"); printf("§┃⒎琴房┣┅┅┫⒍图书馆