0909120615--钱晓雪 完结版

《0909120615--钱晓雪 完结版》由会员分享，可在线阅读，更多相关《0909120615--钱晓雪 完结版（27页珍藏版）》请在装配图网上搜索。

1、数据结构课程设计报告+物联网1201班+钱晓雪+0909120615CENTRAL SOUTH UNIVERSITY 数据结构课程设计报告学生姓名钱晓雪学 号0909120615专业班级物联网工程1201班指导老师盛羽老师学 院信息科学与工程学院完成时间2014年9月 目 录实验一 一、 课程设计的题目和要求1二、 设计与实现1（1） 基本思路（2） 主要数据结构（3） 程序的算法和主要流程 (4)程序实现过程中的主要难点和解决方法三、 实验结果及分析1（1） 实验的准备 (2)实验结果及分析四、 总结 1实验二 一课程设计的题目和要求1二设计与实现1 (1)基本思路 (2)主要数据结构 (3

2、)程序的算法和主要流程 (4)程序实现过程中的主要难点和解决方法三实验结果及分析1 (1)实验的准备 (2)实验结果及分析四总结 1实验一一、 课程设计的题目和要求： 题目：校园导游咨询（为来访的客人提供各种信息服务）1、 基本要求：1) 设计中南大学校园平面图，有三个校区和三所附属医院，在这些校区和医院内选10个以上的建筑物、办公室、宿舍等地名。以图中顶点表示校园内各地名，存放地名名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。2) 为来访客人提供图中任意地名相关信息的查询。3) 为来访客人提供任意地名的问路查询，即查询任意两个地名之间的一条最短路径。2、 实现提示一般情况下，

3、校园的道路是双向通行的，可设计校园平面图是一个无向网。顶点和边均含有相关信息。二、 设计与实现： (1)基本思路从中南大学校园平面图中选取10个有代表性的景点，抽象成一个无向带权图，以图中顶点表示景点，边上的权表示两地的之间的距离。本程序的目的是为用户提供路径查询。根据用户指定的始点和终点输出相应路径，或者根据用户指定的景点输出景点的信息。用邻接表建立图，图的每一个顶点代表相应的景点。然后再用深度优先遍历进行搜索，查找所需的路径。然后再用弗洛伊德算法求出要查询的出发点到目的地的最短路径。 (2)主要数据结构typedef struct Edge /对边的定义int adj; /路径长度Edge

4、,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef struct /图中顶点表示主要景点，存放景点的编号、名称、简介等信息，char name30;int num;char introduction100;/简介infotype; /数据域typedef structinfotype vexsMAX_VERTEX_NUM; /顶点的数据域AdjMatrix edge; /邻接矩阵int vexnum,edgenum; /图的当前顶点数和边数MGraph; (3)程序的算法和主要流程Floyd算法算法思想：从vi到vj的所有存在的路径中，选出一条长度最

5、短的路径，即每一对顶点之间的最短路径。void Floyd(MGraph *G)/用Floyd算法求图中各对顶点v和w之间的最短路径Pvw及其/带权长度Dvw。若Pvwu为1，则u是从v到w当前求得最短/路径上的顶点。 int v,u,i,w,k,j,flag=1,p101010,D1010; for(v=0;vvexnum;v+) /各对结点之间初始已知路径及距离 for(w=0;wvexnum;w+) Dvw=G-edgevw.adj; for(u=0;uvexnum;u+) pvwu=0; if(DvwINFINITY) pvwv=1;pvww=1; for(u=0;uvexnum;u+

6、) for(v=0;vvexnum;v+) for(w=0;wvexnum;w+) if(Dvu+DuwDvw) /从v经u到w的一条路径更短 Dvw=Dvu+Duw; /修改权值 for(i=0;ivexnum;i+) pvwi=pvui|puwi; while(flag) printf(请输入出发点和目的地的编号:); scanf(%d%d,&k,&j); if(kG-vexnum|jG-vexnum) printf(景点编号不存在!请重新输入出发点和目的地的编号:); scanf(%d%d,&k,&j); if(k=0&kvexnum&j=0&jvexnum) flag=0; print

7、f(%s,G-vexsk.name); for(u=0;uvexnum;u+) if(pkju&k!=u&j!=u) printf(-%s,G-vexsu.name); printf(-%s,G-vexsj.name); printf( 总路线长%dmn,Dkj);/Floyd end主函数 调 用 函 数结束查看各景点游览路线开始定义变量Void Menu()进入菜单Switch()选择功能退出系统浏览校园全景显示此图的邻接矩阵查看景点信息选择出发点和目的地（4）程序实现过程中的主要难点和解决方法这个程序的关键代码就利用Floyd算法求最短路径并将路径存放起来。Floyd算法的算法思想：设矩

8、阵用来存放带权无向图G的权值，即矩阵元素Dij中存放着序号为i的结点到序号为j的结点之间的权值，可以通过递推构造一个矩阵序列A0，A1，A2，AN来求每对结点之间的最短路径。其中，Akij表示从结点Vi到结点Vj的路径上所经过的结点序号不大于k的最短路径长度。初始时有A0ij=costij。当已经求出Ak，要递推求解Ak+1时，可分为两种情况来考虑：一种清楚是该结点序号为k+1的结点，此时该路径长度与从结点Vi到结点Vj的路径上所经过的结点序号不大于k的最短路径长度相同；另一种情况是该路径经过结点序号k+1的结点，此时该路径可分为两段，一段是从结点Vi到结点Vk+1的最短路径，另一段是从结点V

9、k+1到结点Vj的最短路径，此时的最短路径长度等于这两段最短路径长度之和。这两种情况的路径长度较小者，就是要求的从结点Vi到结点Vj的路径上所经过的结点序号不大于k+1的最短路径长度。Floyd具体算法设计void floyed() int i,j,k; for(i=1;i=n;i+) for(j=1;j=n;j+) shortestij=costij; pathij=0; for(k=1;k=n;k+) for(i=1;i=n;i+) for(j=1;j(shortestik+shortestkj) shortestij=shortestik+shortestkj; pathij=k; pa

10、thji=k; 由于导游程序在实际执行时，需要根据用户的临时输入求最短路径。因此。虽然迪杰斯特拉算法的时间复杂度比佛洛依德算法低，但每求一条最短路径都必须重新搜索一遍，在频繁查询时会导致查询效率降低，而佛洛依德算法只要计算一次，即可求得每一对顶点间的最短路径，虽然时间复杂度为o(n3)，但以后每次查询都只查表即可，极大地提高了查询效率，而且，佛洛依德算法还支持带负权的图的最短路径的计算。由此可见，在选用算法时，不能单纯的只考虑算法的渐近时间复杂度，有时还必须综合考虑各种因素。 三、 实验结果与分析：（1） 实验的准备用邻接表建立图，图的每一个顶点代表相应的景点。然后再用深度优先遍历进行搜索，查

11、找所需的路径。然后再用弗洛伊德算法求出要查询的出发点到目的地的最短路径。（1）主菜单（Menu）：存放着所有的选择供用户查询。用户可通过输入编号来查询自己想要获得的信息。（2）浏览校园全景（Browser）：采用深度遍历遍历图进行所有景点浏览，将遍历景点信息输出。（3）选择出发点和目的地(Floyd)：用户输入一个出发点和一个目的地编号，采用弗洛伊德算法求出发点到目的地的最短路径。（4）查看景点信息(Search)：直接输入编号进行单个景点查询。（5）显示图的邻接矩阵(print)（6）退出系统(exit)(2)实验结果及分析开始界面 实现了底为湖蓝色，字体为白色的整体要求，以及选项明确，直观

12、易懂。浏览校园全景，中南大学10个景点的名称以及简介。选择出发点和目的地，输入两地编号，输出用弗洛伊德算法计算出的两点之间的最短距离以及最短线路。查看景点信息，输入景点编号，输出景点名称和简介显示此图的邻接矩阵四总结：为期一周的课程设计快结束了，通过这次数据结构课程设计，我感受最深的就是对于循环链表的使用，可以说对循环链表有了比以前更进一步的认识，以前只是一知半解的，如果只给个题目自己根本不能把程序完整地编写出来，所以这次课程设计最大的收获就在于对循环链表有了一定的理解，包括其中的一系列操作，如建立一个循环链表，删除链表中的一个结点，增加一个结点等。在这次课程设计过程中需要我们一边设计一边探索

13、，这这个过程当中我发现自己在数据结构方面知识掌握不够深入，对一些基本概念不能很好的理解，对一些数据结构不能够熟练的进行上机实现，这是自己比较薄弱的。学好基础知识是理论付诸实践的前提，这样理论和实践才能充分地结合起来。在以后的学习中，我还要努力改正，充分利用上机实验的机会提高自己。在程序的输入的时候，因为自己对键盘的不熟练，代码又很多很繁琐，常常会产生放弃的念头，从中我也感受到只有坚持到底，胜利才会出现。本次程序设计是对全学期数据结构课程学习的一次实践，通过亲自编写编译调试程序，逐步掌握了编程方法。也说明了一个深刻道理，知识只有在实践中才能充分理解并运用。从传统的被动接受变为主动探索，起初不是很

14、适应，什么也不懂，茫然无措。渐渐地开始自己编写时候，发现了其中之乐趣。我相信，这样的学习坚持到底，必将有所成就。数据结构课程设计有别于大学考试的类型，要求我们创新自己的新程序，从已有的教材模板中推陈出新，总结教材上的例题和基本结构，发散思维来设计命题程序，对我们提出了很高的要求，是我们不仅要把课本读透，还要求我们有所创造，这是一个很大的挑战。当毫无头绪时，一个人的力量是微薄的，所以这就要求我们和同学一起讨论，一起研究，在激烈的争论中有所收获，也提高了我们思维的缜密度和拓展了思想的深度及广度。扬长避短，通过讨论和对书本的进一步深究理解，以及上网查询有关注意事项并上机调试，是我们加深了对程序设计的

15、理解与探寻，使我们在设计的过程中加强了编程逻辑，深喑耐心细致十分重要，更懂得了编程不能求快，急于求成，只能稳扎稳打，步步推进。而我们从中所收获的，不仅如此，更为以后我们的编程学习和工作获得了一些初级经验，我明天积累下重要财富。虽然通过自己的努力，解决了很多从前没有遇到的问题，但依旧有无数的难题摆在我面前，重重叠叠的大山阻碍着我前进的道路。山高人为峰，我一定不会惧怕摆在前面的困难，不断努力奋斗，争取看到更多的阳光。目前的程序漏洞确实还是很多，但编成之后的成就感还是会油然而生，成为我向程序设计之路成功迈出的第一步，同时，对于我的VC+的应用水平也有很大的提高，用起来会更加娴熟、得心应手。从易到难这

16、是一个准则，总之，数据结构的研究会对增长程序阅读能力、程序编写能力等起到了意想不到的作用。在以后漫漫的研究学习道路上，我还有很远的路要走，迎接我的是又一个严峻的挑战!实验二一 课程设计的题目和要求： 题目：停车场管理问题1、 问题描述设有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里面向大门口处停放(最先到达的第一辆车放在停车场的最里面)。如果停车场已放满n辆车，则后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让

17、路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场就要离去，允许其离去，不收停车费，并且仍然保持在便道上等待的车辆的次序。编制一程序模拟该停车场的管理。2、 实现要求 要求程序输出每辆车到达后的停车位置(停车场或便道上)，以及某辆车离开停车场时应交纳的费用和它在停车场内停留的时间。3、 实现提示 汽车的模拟输入信息格式可以是：(到达离去，汽车牌照号码，到达离去的时刻)。例如，(A，1，5)表示1号牌照车在5这个时刻到达，而(D，5，20)表示5号牌照车在20这个时刻离去。整个程序可以在输入信息为(E，0

18、，0)时结束。本题可用栈和队列来实现。二设计与实现： (1)基本思路此停车场管理系统是在一个狭长的通道上的，而且只有一个大门可以供车辆进出，并且要实现停车场内某辆车要离开时，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场的功能，就可以设计两个堆栈，其中一个堆栈用来模拟停车场，另一个堆栈用来模拟临时停车场，该临时停车场用来存放当有车辆离开时，原来停车场内为其让路的车辆。至于当停车场已满时，需要停放车辆的通道可以用一个链队列来实现。当停车场内开走一辆车时，通道上便有一辆车进入停车场，此时只需要改变通道上车辆结点的连接方式就可以了，使通道上第一辆车进入

19、停车场这个堆栈，并且使通道上原来的第二辆车成为通道上的第一辆车，此时只需将模拟通道的链队列的头结点连到原来的第二辆车上就可以了。对于此停车场管理系统的实现，就是用两个堆栈来分别模拟停车场以及停车场内车辆为其它车辆让路时退出停车的临时停放地点。至于通道上车辆的停放则用一个链队列来实现，此时，通道上车辆的离开或者进入停车场只需改变此链队列上的结点而已。对于要对停车场内的车辆根据其停放时间收取相应的停车费用，可以记录下车辆进入以及离开停车场的时间，再用时间差乘以相应的单价并且打印出最后的费用就可以实现了。（2） 主要数据结构typedef struct node int num; int reach

20、time; int leavetime; CarNode; /*车辆信息结点*/ typedef struct NODE CarNode *stackMAX+1; int top; SeqStackCar; /*模拟车站*/typedef struct car CarNode *data; struct car *next; QueueNode; typedef struct Node QueueNode *head; QueueNode *rear; LinkQueueCar; /*链队列模拟通道*/（3） 程序的算法和主要流程int Arrival(SeqStackCar *Enter,L

21、inkQueueCar *W) /*车辆到达*/ CarNode *p; QueueNode *t; p=(CarNode *)malloc(sizeof(CarNode); printf(ttt请输入到达车辆车牌号: ); scanf(%d,&(p-num); if(Enter-toptop+; printf(nttt该车辆在停车场的位置是: %dn,Enter-top); printf(nttt请输入该车辆到达的时间: ); scanf(%d,&(p-reachtime); Enter-stackEnter-top=p; return(1); else /*车场已满，车进便道*/ prin

22、tf(nttt停车场已满 该车辆需在便道上等待！); t=(QueueNode *)malloc(sizeof(QueueNode); t-data=p; t-next=NULL; W-rear-next=t; W-rear=t; return(1); void Leave(SeqStackCar *Enter,SeqStackCar *Temp,LinkQueueCar *W) /*车辆离开*/ int room; CarNode *p,*t; QueueNode *q; /*判断车场内是否有车*/ if(Enter-top0) /*有车*/ while(1) /*输入离开车辆的信息*/ p

23、rintf(ttt停车场里停放的车辆总数: %d,Enter-top); printf(nnttt请输入要离开车辆的位置: ); scanf(%d,&room); if(room=1&roomtop) break; while(Enter-toproom) /*车辆离开*/ Temp-top+; Temp-stackTemp-top=Enter-stackEnter-top; Enter-stackEnter-top=NULL; Enter-top-; p=Enter-stackEnter-top; Enter-stackEnter-top=NULL; Enter-top-; while(Te

24、mp-top=1) Enter-top+; Enter-stackEnter-top=Temp-stackTemp-top; Temp-stackTemp-top=NULL; Temp-top-; PRINT(p);/*判断通道上是否有车及车站是否已满*/ if(W-head!=W-rear)&Enter-tophead-next; t=q-data; Enter-top+; printf(nnttt便道的%d号车进入车场第%d位置.,t-num,Enter-top); printf(nnttt请输入现在的时间:); scanf(%d,&(t-reachtime); W-head-next=q

25、-next; if(q=W-rear) W-rear=W-head; Enter-stackEnter-top=t; free(q); else printf(nnttt便道里没有车.n); else printf(nnttt车场里没有车.); /*没车*/ （4） 程序实现过程中的主要难点和解决方法在刚开始进行停车场管理系统分析时，我始终没有解决如何在一辆车要离开停车场时，它后面的车要为它让路这件事，如果是堆栈的增加减少，整个程序显得过于麻烦，所以经过查找资料，我发现建立一个临时停车场来存放一辆车在离开时它后面的车是最简单的解决方法，编入程序也简洁明了，瞬间降低了程序的复杂度，我觉得很开心。

26、在刚开始程序执行程序时，选择执行一个任务后就会跳转到一个全新的界面，之前的选项不复存在，所以只能进行单一的选择，不能连贯执行形成一个动态存取过程，因此我想到由于此停车场管理系统是分模块设计的，而且在程序的实现过程中又使用了清屏函数，那么，运行时用户选择任务并且执行完任务后，又会回到供用户选择功能的主界面，因此整个程序从整体上来讲结构清晰，使用方便。三实验结果与分析：（1）实验的准备首先定义用来模拟停车场的堆栈以及用来模拟通道的链队列为全局变量，然后编写主函数，在此主函数中实现对其它各个模块的调用。在主函数中首先调用option()函数，出现欢迎用户使用的主界面，然后提示用户进入此停车场管理系统

27、后，再出现一个供用户选择的界面，在用户的选择过程中，程序又分别调用车辆的到达、车辆的离开、停车场内停放车辆的信息以及退出程序这四个函数模块。其中，在车辆的离开那个模块函数中又调用了打印离开车辆信息的函数，在停车场内停放车辆信息的那个模块函数中，又分别调用了显示停车场上车辆信息的函数以及显示便道上车辆信息的函数。最后，从调用的这四个函数中回到主函数结束整个程序的运行。 (2)实验结果及分析开始界面，界面清晰简洁，一目了然车辆到达，输入到达车辆的车牌号，该车辆在停车场存放的位置以及车辆到达的时间，则这些信息就会存储在存车信息中。我暂时将整个停车场的最大容车辆定在了两辆，就是为了检测一下通道是否正常

28、运行。第二辆车可以正常存放在停车场的二号位置，但是第三辆车进入就会显示停车场已满，该车辆需要停在便道上等待，程序运行符合预期要求。查看存车信息。依次显示车场，便道的车辆信息，显示车辆的位置，到达时间以及车牌号。车辆离开停车场，输入要离开车辆的位置，离开的时间以及离开车辆的车牌号，则会自动显示该车辆到达时间，离开时间以及停车场管理费用，并且等候在通道区的第三辆车就会进入停车场中。此时车场内开走一辆车，便道内的车开进车场，便道内没有车辆四总结：通过这几天的数据结构课程设计，对于堆栈以及链队列有了更深的理解。刚开始遇到这个题目是觉得无从下手，觉得停车管理系统很庞大，一个个的修改车场内以及便道内车辆的

29、头结点以及尾结点很麻烦，看着一些列的问题使自己变得很烦躁。待到心情平静下来认真的一点一点推敲的时候发现只要定义额外的一个堆栈，用来存放临时的停车场，这样设计下来只需要修改便道内车辆的结点就可以了，整个的思路立马变得清晰起来，又重新充满斗志起来。模拟实现这样一个比较复杂的算法，感觉对自己的能力提高还是很有帮助的。在编写代码的同时，不断的体会到面向对象思想的精妙之处，学会将一个大问题不断分解为容易实现的小问题，学会了用不同的函数处理不同的消息。总之，受益匪浅！ 鉴于自己对数据结构知识掌握的现状，以后还要认真复习数据结构这本书，根据需要加强网络编程语言的学习。虽然我开发的停车场管理系统，基本上可以完

30、成每一项功能。汽车进入停车场的信息、离开停车场的信息以及通道上的信息都可以在程序上一一实现。但是，该程序也有不足的地方。主要表现在车辆的车牌号上，现实中的车牌号是一串字符，可是，在这个程序中，为了简便起见，我们就车牌号定义为了整型，这个与现实是有些不符的。还有一个可以改进的地方就是记录车辆进入停车场以及离开停车场的时间，应该精确到小时以及分钟的，可是在程序中，为了简便起见，我们只是设置成了一个时刻，所以，在这方面还是有待改进的。改进的程序中，还应该增加时间的判断功能，即停车场内有可能有车辆停放的时间超过一天。还有一个很重要的问题，对于停车场内可以停放的最多车辆数，为了测试数据的方便，我在程序中

31、，定为了2，在实际使用中，可以改变程度开头的宏定义以增加停车场的容量。网络真的很强大，用在学习上将是一个非常高效的助手。几乎所有的资料都能够在网上找到。当然网上的东西很乱很杂，自己要能够学会筛选。不能决定对或错的，有个很简单的方法就是去尝试。多找个几个参照资料，相互比较，慢慢研究，最后才能事半功倍。同学间的讨论，这是很重要的。老师毕竟比较忙。对于课程设计最大的讨论伴侣应该是同学了。能和学长学姐讨论当然再好不过了，没有这个机会的话，和自己班上同学讨论也是能够受益匪浅的。大家都在研究同样的问题，讨论起来，更能够把思路理清楚，相互帮助，可以大大提高效率。敢于攻坚，越是难的问题，越是要有挑战的心理。这样就能够达到废寝忘食的境界。第 27 页 共 27 页