校园导游咨询为来访的客人提供各种信息服务完结版

CENTRALSOUTHUNIVERSITY数据结构课程设计报告学生姓名学号专业班级指导老师学院完成时间目录实验一课程设计的题目和要求·························1设计与实现···································1基本思路主要数据结构程序的算法和主要流程(4)程序实现过程中的主要难点和解决方法实验结果及分析·······························1实验的准备(2)实验结果及分析总结·····································1实验二一．课程设计的题目和要求·························1二．设计与实现···································1(1)基本思路(2)主要数据结构(3)程序的算法和主要流程(4)程序实现过程中的主要难点和解决方法三．实验结果及分析·······························1(1)实验的准备(2)实验结果及分析四．总结·····································1第第页实验一课程设计的题目和要求：题目：校园导游咨询（为来访的客人提供各种信息服务）基本要求：设计中南大学校园平面图，有三个校区和三所附属医院，在这些校区和医院内选10个以上的建筑物、办公室、宿舍等地名。以图中顶点表示校园内各地名，存放地名名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。为来访客人提供图中任意地名相关信息的查询。为来访客人提供任意地名的问路查询，即查询任意两个地名之间的一条最短路径。实现提示一般情况下，校园的道路是双向通行的，可设计校园平面图是一个无向网。顶点和边均含有相关信息。设计与实现：(1)基本思路=1\*GB3①从中南大学校园平面图中选取10个有代表性的景点，抽象成一个无向带权图，以图中顶点表示景点，边上的权表示两地的之间的距离。=2\*GB3②本程序的目的是为用户提供路径查询。根据用户指定的始点和终点输出相应路径，或者根据用户指定的景点输出景点的信息。=3\*GB3③用邻接表建立图，图的每一个顶点代表相应的景点。然后再用深度优先遍历进行搜索，查找所需的路径。然后再用弗洛伊德算法求出要查询的出发点到目的地的最短路径。(2)主要数据结构typedefstructEdge//对边的定义{intadj;//路径长度}Edge,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct//图中顶点表示主要景点，存放景点的编号、名称、简介等信息，{charname[30];intnum;charintroduction[100];//简介}infotype;//数据域typedefstruct{infotypevexs[MAX_VERTEX_NUM];//顶点的数据域AdjMatrixedge;//邻接矩阵intvexnum,edgenum;//图的当前顶点数和边数}MGraph;(3)程序的算法和主要流程<1>Floyd算法算法思想：从vi到vj的所有存在的路径中，选出一条长度最短的路径，即每一对顶点之间的最短路径。voidFloyd(MGraph*G)//用Floyd算法求图中各对顶点v和w之间的最短路径P[v][w]及其//带权长度D[v][w]。若P[v][w][u]为1，则u是从v到w当前求得最短//路径上的顶点。{intv,u,i,w,k,j,flag=1,p[10][10][10],D[10][10];for(v=0;v<G->vexnum;v++)//各对结点之间初始已知路径及距离for(w=0;w<G->vexnum;w++){D[v][w]=G->edge[v][w].adj;for(u=0;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=0;u<G->vexnum;u++)for(v=0;v<G->vexnum;v++)for(w=0;w<G->vexnum;w++)if(D[v][u]+D[u][w]<D[v][w])//从v经u到w的一条路径更短{D[v][w]=D[v][u]+D[u][w];//修改权值for(i=0;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>=0&&k<G->vexnum&&j>=0&&j<G->vexnum)flag=0;}printf("%s",G->vexs[k].name);for(u=0;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<2>主函数主函数调用函数调用函数<3>结束查看各景点游览路线结束查看各景点游览路线开始开始定义变量VVoidMenu()进入菜单Switch()选择功能退出系统浏览校园全景显示此图的邻接矩阵查看景点信息选择出发点和目的地退出系统浏览校园全景显示此图的邻接矩阵查看景点信息选择出发点和目的地（4）程序实现过程中的主要难点和解决方法<1>这个程序的关键代码就利用Floyd算法求最短路径并将路径存放起来。Floyd算法的算法思想：设矩阵用来存放带权无向图G的权值，即矩阵元素D[i][j]中存放着序号为i的结点到序号为j的结点之间的权值，可以通过递推构造一个矩阵序列A0，A1，A2，…，AN来求每对结点之间的最短路径。其中，Ak[i][j]表示从结点Vi到结点Vj的路径上所经过的结点序号不大于k的最短路径长度。初始时有A0[i][j]=cost[i][j]。当已经求出Ak，要递推求解Ak+1时，可分为两种情况来考虑：一种清楚是该结点序号为k+1的结点，此时该路径长度与从结点Vi到结点Vj的路径上所经过的结点序号不大于k的最短路径长度相同；另一种情况是该路径经过结点序号k+1的结点，此时该路径可分为两段，一段是从结点Vi到结点Vk+1的最短路径，另一段是从结点Vk+1到结点Vj的最短路径，此时的最短路径长度等于这两段最短路径长度之和。这两种情况的路径长度较小者，就是要求的从结点Vi到结点Vj的路径上所经过的结点序号不大于k+1的最短路径长度。Floyd具体算法设计voidfloyed(){inti,j,k;for(i=1;i<=n;i++)for(j=1;j<=n;j++){shortest[i][j]=cost[i][j];path[i][j]=0;}for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(shortest[i][j]>(shortest[i][k]+shortest[k][j])){ shortest[i][j]=shortest[i][k]+shortest[k][j];path[i][j]=k;path[j][i]=k;}}<2>由于导游程序在实际执行时，需要根据用户的临时输入求最短路径。因此。虽然迪杰斯特拉算法的时间复杂度比佛洛依德算法低，但每求一条最短路径都必须重新搜索一遍，在频繁查询时会导致查询效率降低，而佛洛依德算法只要计算一次，即可求得每一对顶点间的最短路径，虽然时间复杂度为o(n^3)，但以后每次查询都只查表即可，极大地提高了查询效率，而且，佛洛依德算法还支持带负权的图的最短路径的计算。由此可见，在选用算法时，不能单纯的只考虑算法的渐近时间复杂度，有时还必须综合考虑各种因素。实验结果与分析：实验的准备用邻接表建立图，图的每一个顶点代表相应的景点。然后再用深度优先遍历进行搜索，查找所需的路径。然后再用弗洛伊德算法求出要查询的出发点到目的地的最短路径。（1）主菜单（Menu）：存放着所有的选择供用户查询。用户可通过输入编号来查询自己想要获得的信息。（2）浏览校园全景（Browser）：采用深度遍历遍历图进行所有景点浏览，将遍历景点信息输出。（3）选择出发点和目的地(Floyd)：用户输入一个出发点和一个目的地编号，采用弗洛伊德算法求出发点到目的地的最短路径。（4）查看景点信息(Search)：直接输入编号进行单个景点查询。（5）显示图的邻接矩阵(print)（6）退出系统(exit)(2)实验结果及分析<1>开始界面实现了底为湖蓝色，字体为白色的整体要求，以及选项明确，直观易懂。<2>浏览校园全景，中南大学10个景点的名称以及简介。<3>选择出发点和目的地，输入两地编号，输出用弗洛伊德算法计算出的两点之间的最短距离以及最短线路。<4>查看景点信息，输入景点编号，输出景点名称和简介<5>显示此图的邻接矩阵四．总结：为期一周的课程设计快结束了，通过这次数据结构课程设计，我感受最深的就是对于循环链表的使用，可以说对循环链表有了比以前更进一步的认识，以前只是一知半解的，如果只给个题目自己根本不能把程序完整地编写出来，所以这次课程设计最大的收获就在于对循环链表有了一定的理解，包括其中的一系列操作，如建立一个循环链表，删除链表中的一个结点，增加一个结点等。在这次课程设计过程中需要我们一边设计一边探索，这这个过程当中我发现自己在数据结构方面知识掌握不够深入，对一些基本概念不能很好的理解，对一些数据结构不能够熟练的进行上机实现，这是自己比较薄弱的。学好基础知识是理论付诸实践的前提，这样理论和实践才能充分地结合起来。在以后的学习中，我还要努力改正，充分利用上机实验的机会提高自己。在程序的输入的时候，因为自己对键盘的不熟练，代码又很多很繁琐，常常会产生放弃的念头，从中我也感受到只有坚持到底，胜利才会出现。本次程序设计是对全学期数据结构课程学习的一次实践，通过亲自编写编译调试程序，逐步掌握了编程方法。也说明了一个深刻道理，知识只有在实践中才能充分理解并运用。从传统的被动接受变为主动探索，起初不是很适应，什么也不懂，茫然无措。渐渐地开始自己编写时候，发现了其中之乐趣。我相信，这样的学习坚持到底，必将有所成就。数据结构课程设计有别于大学考试的类型，要求我们创新自己的新程序，从已有的教材模板中推陈出新，总结教材上的例题和基本结构，发散思维来设计命题程序，对我们提出了很高的要求，是我们不仅要把课本读透，还要求我们有所创造，这是一个很大的挑战。当毫无头绪时，一个人的力量是微薄的，所以这就要求我们和同学一起讨论，一起研究，在激烈的争论中有所收获，也提高了我们思维的缜密度和拓展了思想的深度及广度。扬长避短，通过讨论和对书本的进一步深究理解，以及上网查询有关注意事项并上机调试，是我们加深了对程序设计的理解与探寻，使我们在设计的过程中加强了编程逻辑，深喑耐心细致十分重要，更懂得了编程不能求快，急于求成，只能稳扎稳打，步步推进。而我们从中所收获的，不仅如此，更为以后我们的编程学习和工作获得了一些初级经验，我明天积累下重要财富。虽然通过自己的努力，解决了很多从前没有遇到的问题，但依旧有无数的难题摆在我面前，重重叠叠的大山阻碍着我前进的道路。山高人为峰，我一定不会惧怕摆在前面的困难，不断努力奋斗，争取看到更多的阳光。目前的程序漏洞确实还是很多，但编成之后的成就感还是会油然而生，成为我向程序设计之路成功迈出的第一步，同时，对于我的VC++的应用水平也有很大的提高，用起来会更加娴熟、得心应手。从易到难这是一个准则，总之，数据结构的研究会对增长程序阅读能力、程序编写能力等起到了意想不到的作用。在以后漫漫的研究学习道路上，我还有很远的路要走，迎接我的是又一个严峻的挑战!实验二课程设计的题目和要求：题目：停车场管理问题问题描述设有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里面向大门口处停放(最先到达的第一辆车放在停车场的最里面)。如果停车场已放满n辆车，则后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场就要离去，允许其离去，不收停车费，并且仍然保持在便道上等待的车辆的次序。编制一程序模拟该停车场的管理。实现要求要求程序输出每辆车到达后的停车位置(停车场或便道上)，以及某辆车离开停车场时应交纳的费用和它在停车场内停留的时间。实现提示汽车的模拟输入信息格式可以是：(到达／离去，汽车牌照号码，到达／离去的时刻)。例如，(‘A’，，1，5)表示1号牌照车在5这个时刻到达，而(‘D’，，5，20)表示5号牌照车在20这个时刻离去。整个程序可以在输入信息为(‘E’，0，0)时结束。本题可用栈和队列来实现。二．设计与实现：(1)基本思路此停车场管理系统是在一个狭长的通道上的，而且只有一个大门可以供车辆进出，并且要实现停车场内某辆车要离开时，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场的功能，就可以设计两个堆栈，其中一个堆栈用来模拟停车场，另一个堆栈用来模拟临时停车场，该临时停车场用来存放当有车辆离开时，原来停车场内为其让路的车辆。至于当停车场已满时，需要停放车辆的通道可以用一个链队列来实现。当停车场内开走一辆车时，通道上便有一辆车进入停车场，此时只需要改变通道上车辆结点的连接方式就可以了，使通道上第一辆车进入停车场这个堆栈，并且使通道上原来的第二辆车成为通道上的第一辆车，此时只需将模拟通道的链队列的头结点连到原来的第二辆车上就可以了。对于此停车场管理系统的实现，就是用两个堆栈来分别模拟停车场以及停车场内车辆为其它车辆让路时退出停车的临时停放地点。至于通道上车辆的停放则用一个链队列来实现，此时，通道上车辆的离开或者进入停车场只需改变此链队列上的结点而已。对于要对停车场内的车辆根据其停放时间收取相应的停车费用，可以记录下车辆进入以及离开停车场的时间，再用时间差乘以相应的单价并且打印出最后的费用就可以实现了。主要数据结构typedefstructnode{intnum;intreachtime;intleavetime;}CarNode;/*车辆信息结点*/typedefstructNODE{CarNode*stack[MAX+1];inttop;}SeqStackCar;/*模拟车站*/typedefstructcar{CarNode*data;structcar*next;}QueueNode;typedefstructNode{QueueNode*head;QueueNode*rear;}LinkQueueCar;/*链队列模拟通道*/程序的算法和主要流程intArrival(SeqStackCar*Enter,LinkQueueCar*W)/*车辆到达*/{CarNode*p;QueueNode*t;p=(CarNode*)malloc(sizeof(CarNode));printf("\t\t\t请输入到达车辆车牌号:");scanf("%d",&(p->num));if(Enter->top<MAX)/*车场未满，车进车场*/{Enter->top++;printf("\n\t\t\t该车辆在停车场的位置是:%d\n",Enter->top);printf("\n\t\t\t请输入该车辆到达的时间:");scanf("%d",&(p->reachtime));Enter->stack[Enter->top]=p;return(1);}else/*车场已满，车进便道*/{printf("\n\t\t\t停车场已满该车辆需在便道上等待！");t=(QueueNode*)malloc(sizeof(QueueNode));t->data=p;t->next=NULL;W->rear->next=t;W->rear=t;return(1);}}voidLeave(SeqStackCar*Enter,SeqStackCar*Temp,LinkQueueCar*W)/*车辆离开*/{introom;CarNode*p,*t;QueueNode*q;/*判断车场内是否有车*/if(Enter->top>0)/*有车*/{while(1)/*输入离开车辆的信息*/{printf("\t\t\t停车场里停放的车辆总数:%d",Enter->top);printf("\n\n\t\t\t请输入要离开车辆的位置:");scanf("%d",&room);if(room>=1&&room<=Enter->top)break;}while(Enter->top>room)/*车辆离开*/{Temp->top++;Temp->stack[Temp->top]=Enter->stack[Enter->top];Enter->stack[Enter->top]=NULL;Enter->top--;}p=Enter->stack[Enter->top];Enter->stack[Enter->top]=NULL;Enter->top--;while(Temp->top>=1){Enter->top++;Enter->stack[Enter->top]=Temp->stack[Temp->top];Temp->stack[Temp->top]=NULL;Temp->top--;}PRINT(p);/*判断通道上是否有车及车站是否已满*/if((W->head!=W->rear)&&Enter->top<MAX)/*便道的车辆进入车场*/{q=W->head->next;t=q->data;Enter->top++;printf("\n\n\t\t\t便道的%d号车进入车场第%d位置.",t->num,Enter->top);printf("\n\n\t\t\t请输入现在的时间:");scanf("%d",&(t->reachtime));W->head->next=q->next;if(q==W->rear)W->rear=W->head;Enter->stack[Enter->top]=t;free(q);}elseprintf("\n\n\t\t\t便道里没有车.\n");}elseprintf("\n\n\t\t\t车场里没有车.");/*没车*/}程序实现过程中的主要难点和解决方法<1>在刚开始进行停车场管理系统分析时，我始终没有解决如何在一辆车要离开停车场时，它后面的车要为它让路这件事，如果是堆栈的增加减少，整个程序显得过于麻烦，所以经过查找资料，我发现建立一个临时停车场来存放一辆车在离开时它后面的车是最简单的解决方法，编入程序也简洁明了，瞬间降低了程序的复杂度，我觉得很开心。<2>在刚开始程序执行程序时，选择执行一个任务后就会跳转到一个全新的界面，之前的选项不复存在，所以只能进行单一的选择，不能连贯执行形成一个动态存取过程，因此我想到由于此停车场管理系统是分模块设计的，而且在程序的实现过程中又使用了清屏函数，那么，运行时用户选择任务并且执行完任务后，又会回到供用户选择功能的主界面，因此整个程序从整体上来讲结构清晰，使用方便。三．实验结果与分析：（1）实验的准备首先定义用来模拟停车场的堆栈以及用来模拟通道的链队列为全局变量，然后编写主函数，在此主函数中实现对其它各个模块的调用。在主函数中首先调用option()函数，出现欢迎用户使用的主界面，然后提示用户进入此停车场管理系统后，再出现一个供用户选择的界面，在用户的选择过程中，程序又分别调用车辆的到达、车辆的离开、停车场内停放车辆的信息以及退出程序这四个函数模块。其中，在车辆的离开那个模块函数中又调用了打印离开车辆信息的函数，在停车场内停放车辆信息的那个模块函数中，又分别调用了显示停车场上车辆信息的函数以及显示便道上车辆信息的函数。最后，从调用的这四个函数中回到主函数结束整个程序的运行。(2)实验结果及分析<1>开始界面，界面清晰简洁，一目了然<2>车辆到达，输入到达车辆的车牌号，该车辆在停车场存放的位置以及车辆到达的时间，则这些信息就会存储在存车信息中。<3>我暂时将整个停车场的最大容车辆定在了两辆，就是为了检测一下通道是否正常运行。第二辆车可以正常存放在停车场的二号位置，但是第三辆车进入就会显示停车场已满，该车辆需要停在便道上等待，程序运行符合预期要求。<4>查看存车信息。依次显示车场，便道的车辆信息，显示车辆的位置，到达时间以及车牌