基于栈和队列的停车场管理系统设计与实现课程设计-学位论文.doc

长春建筑学院数据结构课程设计（论文）基于栈和队列的停车场管理系统设计与实现Stack and queue-based parking management system design and Implementation年 级: 学 号: 姓 名: 专 业 : 指导老师: 二零一三年十二月- 1 -长春建筑学院数据结构课程设计（论文）摘 要计算机科学技术的发展，不仅极大地促进了整个科学技术的发展，而且明显地加快了经济信息化和社会信息化的进程。因此，计算机教育在全国备受重视，计算机知识与能力已成为21世纪人才素质的基本要素之一。如今，高等教育的计算机教育发展十分迅速。十多年前，只有部分理工科专业开设计算机课程。今天，几乎所有高校的所有专业都开设了程度不同的计算机课程。人们已经认识到，计算机知识已成为当代知识分子知识结构中不可缺少的重要组成部分。而除了掌握计算机的基础知识和操作的基本能力外，掌握一门高级编程语言，并可以熟练运用它，已成为当代大学生综合能力必要组成。 计算机技术发展如此迅猛，计算机应用如此广泛，需要学习的东西愈来愈多，而我们的总学时是有限的。一般来说，计算机课程学习可以分为两部分：一部分是理论课程学习，一部分是上机应用实习。根据我们专业的性质和要求，则应侧重于上机操作运用。关键字：计算机 上机应用实习- 1 -长春建筑学院数据结构课程设计（论文）AbstractDevelopment of computer science and technology, not only greatly promoted the development of the science and technology, but also significantly accelerate the economic and social informatization process of information. Therefore, the country has attracted increasing attention in computer education, computer knowledge and ability has become one of the basic elements of the 21st century, the quality of talent.Today, the computer is very fast development of higher education. Ten years ago, only a part of the creation of computer science and engineering courses. Today, almost all professional colleges and universities have set up all the different levels of computer courses. It has been recognized, computer knowledge has become the contemporary intellectuals important part of the knowledge structure indispensable. And in addition to master the basics of computer operation and basic ability to master a high-level programming language, and can skillfully use it, has become an essential component of contemporary college students' comprehensive ability.Computer technology is growing so fast, computer application so extensive, more and more things to learn, and our total hours are limited. Generally, computer learning courses can be divided into two parts: one is the theoretical courses, practical application part of the machine. According to the nature and requirements of our professional, you should focus on the use of machine operation.Keywords：comptuer Computer application practice长春建筑学院数据结构课程设计（论文）目 录摘 要IABSTRACTII第1章 绪 论- 1 -1.1 设计目的- 1 -1.2 设计内容- 1 -1.3 设计要求- 2 -1.4 设计思想- 2 -第2章 概要设计- 3 -21抽象数据类型定义- 3 -22模块划分- 5 -第3章 详细设计- 7 -31数据类型的定义- 7 -32主要模块的算法描述- 8 -第4章 系统测试- 12 -第4章 系统测试- 13 -4.1 调试分析- 13 -第5章 测试结果- 14 -5.1 测试数据及结果- 14 -5.2 结果分析- 17 -第6章 课程设计总结- 18 -长春建筑学院数据结构课程设计（论文） 第1章 绪 论引言：课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。数据结构是一门重要的专业基础课，是计算机理论和应用的核心基础课程。数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。1.1 设计目的1、掌握栈和队列的建立。 2、掌握栈和队列的基本操作。 3、深入了解栈和队列的特性,以便在解决实际问题中灵活运用它们。 4、加深对栈和队列的理解和认识。 1.2 设计内容停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。停车场内已停了n辆汽车，后来的汽车只能在门外的便道上等候，一旦有车开走，排在通道上的第一辆车即可开入；当停车场内每辆车要离开时，在它之后进入的车辆必须先退出停车场为其让路，待该辆车开出大门，其他车辆再按原次序进入停车场。为停车场编写按上述要求进行管理的模拟程序。1.3 设计要求（1）根据车辆到达停车场到车辆离开停车场时所停留的时间进行计时收费。（2）当有车辆从停车场离开时，等待的车辆按顺序进入停车场停放。实现停车场的调度功能。（3）用顺序栈来表示停车场，链队表示停车场外的便道。（4）显示停车场信息和便道信息。（5）程序执行的命令为：车辆进入停车场 车辆离开停车场 显示停车场的信息。1.4 设计思想1.当车辆要进入停车场时，检查停车场是否已满，如果未满则车辆进入停车场；如果停车场已满，则车辆进入便道等候。2.当车辆要求出栈时，先让在它之后进入停车场的车辆退出停车场为它让路，再让该车退出停车场，让路的所有车辆再按其原来进入停车场的次序进入停车场。之后，再检查在便道上是否有车等候，有车则让最先等待的那辆车进入停车场。3.用顺序结构实现栈，用链表实现队列。第2章 概要设计21抽象数据类型定义（1）栈的抽象数据类型定义AST Stack数据对象：D=ai|aiElemSet,i=1,2,.,n, n0数据关系：R1=<ai-1,ai>|ai-1,aiD，i=2,.,n约定an端为栈顶，a1端为栈底。基本操作： InitStack(&S) 操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：栈S被销毁。ClearStack(&S)初始条件：栈S已存在。操作结果：将栈S清为空栈。StackEmpty(S)初始条件：栈S已存在。操作结果：若栈S为空栈，则返回TRUE，否则FALSE。StackLength(s)初始条件:栈S已存在。操作结果：返回S的元素个数，既栈的长度。GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。StackTraverse(S,visit()初始条件：栈S已存在且非空。 操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit()。一旦visit()失败，则操作失效。ADT Stack（2）队列的抽象数据类型定义ADT Queue数据对象：D=ai|aiElemSet,i=1,2,.,n,n0数据关系：R1=<ai-1,ai>|ai-1,aiD,i=2,.,n约定其中a1端为队列头，an为队列尾。基本操作：InitQueue(&Q)操作结果：构造一个空队列Q。DestroyQueue(&Q)初始条件：队列Q已存在。操作结果：队列Q被销毁，不再存在。ClearQueue(&Q)初始条件：队列Q已存在。操作结果：将Q清为空队列。QueueEmpty(Q)初始条件：队列Q已存在。操作结果：若Q为空队列，则返回TRUE，否则FALSE。QueueLength(Q)初始条件：队列Q已存在。操作结果：返回Q的元素个数，即队列的长度。GetHead(Q,&e)初始条件：Q为非空队列。操作结果：用e返回的队头元素。EnQueue(&Q,e)初始条件：队列Q已存在。操作结果：插入元素e为Q的新的队尾元素。DeQueue(&Q,&e)初始条件：Q为非空队列。操作结果：删除Q的队头元素，并用e返回其值。QueueTraverse(Q,visit()初始条件：Q已存在且非空。操作结果：从队头到队尾，依次对Q的每个数据元素调用函数visit()。一旦visit() 失败，则操作失败。ADT Queue 22模块划分本程序包括六个模块：（1）主程序模块void main()初始化停车站；初始化让路的临时栈；初始化通道；输出主菜单：车辆到达、车辆离开与计费、查看停车场信息；（2）入场模块int arrive(SqStack *In,LinkQueue *W)车辆进入停车场；计算停车费用（3）出场模块void leave(SqStack *In,SqStack *Out,LinkQueue *W)车辆离开停车场；（4）输出模块void info(SqStack S,LinkQueue W) 输出停车场信息； （5）栈模块实现栈的抽象数据类型（6）队列模块实现队列的抽象数据类型第3章 详细设计31数据类型的定义int MAX; /*定义一个全局变量用来存储车库最大容量*/ float price;/* 定义一个全局变量用来存储每车每小时的费用*/ typedef struct time int hour; int min; Time; /*时间结点*/ typedef struct node char num10; Time reach; Time leave; Car; /*车辆信息结点*/ typedef struct NODE Car *stack100; int top; SqStack; /*停车站*/ typedef struct car Car *data; struct car *next; QNode; typedef struct Node QNode *head; QNode *rear; LinkQueue; /*通道*/ 32主要模块的算法描述本程序主要分为四部分：（1）主函数及程序框架、（2）车辆到达模块、（3）车辆离开模块、（4）显示车辆信息模块，由梁伟明、段庆龙、丁磊和我合作编写，我主要负责leave（车辆离开）函数部分。（1）主函数void main() SqStack In,Out; LinkQueue Wait; int ch; InitStack(&In); /*初始化停车站*/ InitStack(&Out); /*初始化让路的临时栈*/ InitQueue(&Wait); /*初始化通道*/ while(1) printf("-欢迎使用停车场管理系统-n");printf("t本系统由5011工作室开发，作者:邓春国、段庆龙、梁伟明、丁磊。nn");printf("请输入停车场的容量:");scanf("%d",&MAX);printf("请输入停车场的收费标准(元/小时):");scanf("%f",&price);printf("您输入的停车场容量为%d位，费用为%2.1f元/小时。n",MAX,price);printf("n(1)车辆到达n(2)车辆离开n(3)停车场信息n(4)退出系统n请选择n");while(1) ch=getch();switch(ch) case 49:arrive(&In,&Wait);break; /*车辆到达*/ case 50:leave(&In,&Out,&Wait);break; /*车辆离开*/ case 51:info(In,Wait);break; /*输出车站信息*/case 52:printf("谢谢使用！");exit(0); /*退出主程序*/ default:printf("n按键无效，请重新按键选择！");/*49-52分别表示“1”-“4”这四个按键的键值*/system("CLS");printf("-欢迎使用停车场管理系统-n");printf("t本系统由CG工作室开发，作者:邓春国、段庆龙、梁伟明、丁磊。nnn");printf("您输入的停车场容量为%d位，费用为%2.1f元/小时。n",MAX,price);printf("n(1)车辆到达n(2)车辆离开n(3)停车场信息n(4)退出系统n请选择n"); （2）车辆离开模块算法分析void leave(SqStack *In,SqStack *Out,LinkQueue *W) /*车辆离开*/ int room;Car *p,*t;QNode *q;/*开始定义一个整型变量room，用来记录要离开的车辆在停车场的位置，定义车辆结点指针p和t和队列结点指针q。*/ if(In->top>0) /*有车*/ while(1) printf("n请输入车在停车场的位置(1-%d)：",In->top); scanf("%d",&room); if(room>=1&&room<=In->top) break; /*判断停车场内是否有车，如果有车，就输入要离开的车辆在停车场的位置，否则就提示停车场没车。这里用了while循环语句，如果输入的车辆位置超出范围，就要重新输入。*/while(In->top>room) /*车辆离开*/Out->top+;Out->stackOut->top=In->stackIn->top;In->stackIn->top=NULL;In->top-;/*如果栈顶位置In->top大于要离开的车位置room（即要离开的车不在停车场的门口）的话，在要离开的车辆前面的车就要先离开，开到临时停车场，即临时栈中，因此Out所表示的临时栈的栈顶top加1，用来表示临时停车场增加1辆车；接着把该车的信息拷贝到栈Out中，然后删除栈In的栈顶（即这辆车开走）。*/p=In->stackIn->top; In->stackIn->top=NULL;In->top-;while(Out->top>=1) In->top+;In->stackIn->top=Out->stackOut->top; Out->stackOut->top=NULL; Out->top-; /*直到要离开的车辆前面的车都开到临时停车场之后，该车才离开，离开之后，该车的信息结点In->stackIn->top置空，然后栈顶In->top减1。之后就判断临时停车场是否有车，有车就一辆一辆的开回停车场里面，因此停车场的栈顶In->top 加1，然后就把临时停车场的车结点的信息拷贝到停车场的车结点上，接着删除临时停车场车的结点 (即Out->stackOut->top=NULL;Out->top-;)。*/PRINT(p,room); if(W->head!=W->rear)&&In->top<MAX) q=W->head->next;t=q->data;In->top+; printf("n便道的%s号车进入车场第%d号停车位。",t->num,In->top); printf("n请输入现在的时间(格式“*:*”):"); scanf("%d:%d",&(t->reach.hour),&(t->reach.min); W->head->next=q->next;if(q=W->rear) W->rear=W->head; In->stackIn->top=t; free(q);/*判断(W->head!=W->rear)&&In->top<MAX（即通道上是否有车及停车场是否已满），如果便道有车且停车场未满，通道的车便可进入停车场，此时指针q指向便道的头，即队头，然后停车场的栈顶In->top 加1以便增加新的车辆，接着输入队头的车辆信息，即要进去停车场的车的信息，然后便道队列的头结点指向q（即刚进入停车场的车的结点）的后继结点，即原队列中第二辆车的结点，接着判断刚离开的车是否是最后一辆车，如果是，就把队列置空，即队头等于队尾；之后就把结点t（即要进入停车场的车）的信息拷贝到停车场栈顶的车中，最后释放p的空间，即原队头结点。*/ else printf("n停车场里没有车n"); /*没车*/printf("请按任意键返回");getch(); leave函数流程图如图3.1所示：结束开始判断停车场是否有车图3.1 leave函数流程图否是是是车临时停车场的车回到停车场便道的车先进入停车场否判断便道否有车否判断前面是否有其他车且停车场未满输入离开车辆的信息车辆离开前面的车先进入临时停车场输出停车场里没有车定义必要的变量第4章 系统测试4.1 调试分析 调试过程中的主要问题由于此停车场管理系统是分模块设计的，而且在程序的实现过程中又使用了清屏函数，所以，运行时用户选择任务并且执行完任务后，又会回到供用户选择功能的主界面，因此整个程序从整体上来讲结构清晰，使用方便。本程序的调试运行，总体上情况良好，但中间也出现了一些小问题。其中比较有代表性的主要问题有：（1）当停车场已经达到最大容量，但仍有车辆进入停车场的时候，运行界面上没有出现或者说出现了但又跳掉了“车站已满!车辆已经入通道!”的提示信息。在查阅了多种资料后，在那一个printf语句后加了一个getch()，此时，程序运行结果就符合要求了，看起来也比较清晰了。（2）使用getch（）语句必须使用头文件#include<conio.h>刚开始因为没有使用这个头文件，所以会出现getch（）这个无法辨别图5.1错误报告1（3）在对字符型的数据进行赋值的时候，要用strcpy，而不能直接用pcar.num=pnum这样的赋值形式，这样子会产生如下的错误：图5.2错误报告2正确的形式应该是这样的：strcpy(pcar.num,pnum);第5章 测试结果5.1 测试数据及结果输入停车场的容量4，收费5元/小时，接着查看停车场的信息，如图5.1所示：图5.1 停车场系统初始化示意图接着输入4辆车的信息，然后查看停车场信息，如图5.2所示：图5.2 车辆进入停车场示意图再输入1辆车的信息，然后查看停车场信息，如图5.3(a)和图5.3(b)所示：图5.3(a) 车辆进入便道示意图图5.3(b) 车辆进入便道示意图最后选择车辆离开，输入第2辆车离开，再查看停车场信息，如图5.4(a)和图5.4(b)所示：图5.4(a) 车辆离开示意图图5.4(b) 车辆离开示意图5.2 结果分析 通过这次数据结构课程设计，我认识到从课本上学到的知识是远远不够的。本次设计使我深入的了解了栈与队列的建立、插入、删除和在实际问题下灵活运用它们，另一方面使我对栈和队列的抽象数据类型有了进一步的认识。虽然经过努力终于把该系统完成，可是该系统还是不完善，程序中的一些算法还不是很清楚，只不过把简单的功能实现了出来，这些缺憾归根结底都是因为我的C+语言和数据结构的水平还不是很高 ，还需要经过不懈的努力才能做出比较完善的系统。这次课程设计让我明白要真正的掌握一门编程语言需要的不仅仅是课本上的东西，还要在实际的编程过程中慢慢的掌握其中的奥妙。同时我明白了，要成为一名优秀的编程人员所要具备的各种条件（坚实的编程语言基础、熟练的调试程序的技能、重要的是要有耐心、同时细心也是不可缺少的）。所以为了自己的梦想，在以后的学习过程中，我要不断的充实自己，努力的学习。通过这次课程设计，对数据结构的特点以及存储表示方式的认识有了明显的提高，同时还对在具体应用中选择合适的数据结构和存储结构的能力有了进一步的提升。熟悉了软件开发的基本过程；初步掌握了软件开发过程的问题分析、系统设计、程序编码、测试等阶段的基本任务和技能方法；培养了我的算法设计和算法分析的能力；提高了综合运用所学的理论知识和方法以及独立分析和解决问题的能力。通过课程设计，我明白，数据结构就是要培养我们的数据抽象能力，它用规范的数学语言来描述数据结构的定义，以突出这门课程的特性。总之，数据结构是计算机专业的一门不可缺少的专业课。虽然课程设计的过程是艰辛的，但是当看着自己的程序能够运行的瞬间，无限的满足感会让自己感到从未有过的兴奋。第6章 课程设计总结通过这次课程设计使我充分的理解了用栈和队列实现模拟停车场的基本原理，知道了栈的顺序存储结构和队列的链式存储结构的定义和算法描述，同时也学会了编写停车场问题的程序。虽然此次的程序不是很完备，没有加入一些更完善的功能，但是总体还是一个比较能体现数据结构知识点能力的程序了，当然只是相对于我这个初学者来说。在刚开始编程的时候，我感到有点无从下手，但经过对题目的详细分析和思考之后，我就知道具体应该做什么，怎么做了。经过几天和同组同学的一起研究，我们分工完成了这个程序，完成这个程序，我学到了很多东西，这是在课堂上无法做到的。在此我非常要感谢的是我的指导老师成娅辉老师，感谢老师的细心认真的辅导，让我对数据结构这门课程掌握得更好，懂得更多，她教我怎么分析问题，应该要注意些什么，最后还指出我存在的问题。致 谢：通过本次课程设计，使我对数据结构这门课的认识更进一步，数据结构作为计算机专业的一门必修课，对如何编写好的算法进行了比较深入的阐述，为我们写出正确的，强壮的代码奠定了基础。在做课程设计的过程中，从查阅的相关资料和问题的解决中学到了不少的知识，因此对课本上的知识也有了更深入的了解。     参考文献唐国民，王国军. 数据结构（C语言版）.清华大学出版社，2009.李春葆，曾慧，张植民. 数据结构程序设计题典. 清华大学出版社，2002.秦锋，袁志祥. 数据结构例题详解与课程设计指导. 中国科学技术大学出版社2007.- 19 -