清华大学_严蔚敏版_数据结构课程设计-停车场.doc

停车场管理系统专 业： 班 级：姓 名：学 号：指导教师： 完成日期：2008年6月25日 数据结构课程设计任务书一、开设数据结构课程设计的目的 数据结构是一门实践性较强的软件基础课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能，特开设此课程设计。二、数据结构课程设计的具体内容停车场管理系统问题描述 车辆的信息包括：车牌号、汽车到达/离去标志、到达/离去时刻等。利用栈结构模拟停车场，用队列结构模拟等待的便道。基本要求l 收费：根据车辆到达和离开停车场的时间计时收费。l 查询：通过车牌号能查到该车辆在停车场或便道中的位置l 调度：当有车辆从停车场离开时，等待的车辆按顺序进入停车场停放。三、课程设计要求1、独立思考，按要求认真完成本次课程设计。 2、按照课程设计的具体要求完成几个内容。 a) 需求分析：叙述课题的功能要求；b ) 概要设计：详细说明每个部分的算法设计及过程，可以辅助流程图；， c）详细设计：算法实现的源程序（设计的具体语言不限制）；d）调试分析：测试数据，时间复杂度分析，和每个模块设计和调试时存在问题的思考。3、报告书提交（报告书的书写格式参照以下条目）l 认真完成报告书，使用B5纸张，正文用小四字体, 打印。首页为封面，要求写清楚标题、班级、姓名、指导教师、完成日期。第二页为本任务书。第三页为教师评语。第四页为目录。从第五页开始，为报告书正文。l 报告书正文具体内容包括：算法的简介、说明及分析；整个程序的功能设计与分析；程序测试与分析，附程序清单。四、完成期限二八年六月二十三日 二七年六月二十七日 指导教师：黎娅 机电信息工程系 二八年六月二十日教师评语：目 录任务书 2教师评语 3目录 4一、 数据结构内容简介 5二、 需求分析 5三、 算法设计 61.概要设计 72.详细设计 9四、 程序功能分析 13 1.算法分析与探讨 132.调试分析 13 3.程序测试 14 4.测试结果 145.源程序代码 15五、 总结 20 六、 参考文献 21 一、 数据结构内容简介数据结构指的是数据的逻辑结构和存储结构，算法就是对数据运算的描述。程序设计的实质就是对实际问题选取一种优秀的数据结构，加之设计一个优秀的算法，而且优秀的算法很大程度上取决于描述实际问题的数据结构。栈是限定仅在表尾进行插入和删除的线性表。对栈来说，允许进行插入和删除的一端，称为栈顶(top)；不允许插入和删除的另一端则称为栈底(bottom)。栈的运算有：(1)初始化CREAT(S):建立一个空栈；(2)入栈PUSH(S,x):在栈中加入一个新元素x；(3)出栈POP(S):删除栈S的栈顶元素；(4)取栈顶GETTOP(S):读取S中的栈顶元素；(5)判空EMPTY(S)：测试栈S是否为空。队列和栈一样，均属于限定性的数据结构，也属于线性表的一种。和栈相反，队列是一种先进先出的线性表，它只允许在表达的一端进行插入，二在另一端进行删除元素，在队列中，允许插入的一端称为队尾(Rear)，允许删除的一端称为队头(Front)。队列的基本操作有：(1)构造空队列InitQueue(Q);(2)队列销毁DestroyQueue；(3)队列清空ClearQueue(Q)；(4)取头元素GetHead(Q,e)；(5)队列插入Enqueue(Q,e)；(6)队头删除Dequeue(Q,e)；二、需求分析本次数据结构课程设计的具体内容是停车场管理系统，该系统用栈结构模拟停车场，限定停车场的容量为n，用队列结构模拟等待的便道，空间不限制。车辆的信息包括：车牌号、汽车到达/离去标志、到达/离去时刻等。按照从终端读入的数据序列进行模拟管理。每辆车需要三个数据，其中车辆数据为：A表示到达，D表示离去，E表示程序结束。车辆牌照为整型数据。进场或离场时间同样为整型数据。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。停车场管理系统主要实现以下几个功能： (1)根据车辆到达停车场到车辆离开停车场时所停留的时间进行计时收费。 (2)该程序设计能够通过车牌号能查到该车辆在停车场或便道中的位置。(3)当有车辆从停车场离开时，等待的车辆按顺序进入停车场停放。实现停车场的调度功能。该程序设计可以完整的模拟停车场的管理过程。三、算法设计停车场管理系统是充分利用数据结构中栈和队列的思想实现的，栈是一种只能在叫做栈的一段进行进栈或者出栈操作的线性数据结构。栈的主要特点是”后进先出”，即后进栈的元素先处理。停车场的容量即为栈的存储空间，停车场的车辆的停靠是无秩序的，因此采用链式存储的方式更适合，也方便车辆的调度。队列是限定仅能在表的一端进行插入，在表的另一端进行删除的线性表。队列中可以插入的一端称为队尾，可以删除的一端称为队首。把一个元素插入队列中的操作为进队，队列中删除一个元素的操作为出队。队列存取操作符合：先进先出。停车场的车辆到达停车和车辆的离开的管理方式就是采用队列的“先进先出”的移动的思想。停车场的入口就是队列的队首，停车场的出口就是队列的队尾。停车场管理系统流程图如图1所示。关闸开闸出口 入口 车辆过闸开闸缴费车辆过闸计时关闸调度等待准备离场停车图1 停车场管理系统流程图1、概要设计1.1设定栈的抽象数据类型定义为：ADT stack数据对象：D=ai|aicharset, i=1,2,n,n0数据关系：R1=|ai-1,aiD,i=2,n基本操作：initstack(&S, n)操作结果：构造一个空栈S,该栈可存放n个元素。push(&S, e)初始条件：栈S已存在。操作结果：在栈S的栈顶插入新的栈顶元素e。pop(&S, &e)初始条件：栈S已存在。操作结果：删除S的栈顶元素，并以e返回其值。DestroyStack(&S)初始条件：栈S已存在。操作结果：销毁栈S。ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。StackLength(&S)初始条件：栈S已存在。操作结果：返回栈S的长度。StackEmpty(&S)初始条件：栈S已存在。操作结果：若S为空栈，则返回TRUE，否则返回FALSE。GetTop(S, &e)初始条件：栈S已存在。操作结果：若栈S不空，则以e返回栈顶元素。StackTraverse(S, visit()初始条件：栈S已存在。操作结果：从栈底到栈顶依次对S中的每个元素调用函数visit()。ADT stack1.2 设定队列的抽象数据类型定义为：ADT Queue数据对象：D=ai|aiElemSet, i=1,2,n,n0数据关系：R1=|ai-1,aiD,i=2,n基本操作：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返回Q的队头元素。EnQueue(&Q, e)初始条件：队列Q已存在。操作结果：插入元素e为Q的新的队尾元素。DeQueue(&Q, &e)初始条件：Q为非空队列。操作结果：删除Q的队头元素，并用e返回其值。QueueTraverse(Q, visit()初始条件：Q已存在且非空。操作结果：从队头到队尾，依次对Q的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。ADT Queue2.详细设计1 车辆信息类型typedef struct nodeint passport; /存储车辆牌照信息int time; /存储进场时间信息node;2栈类型（停车场）typedef struct stacknode *base;node *top;int stacksize;stack;void initstack(stack &S,int n) /构造空栈S.base=(node *)malloc(n*sizeof(node);S.top=S.base;S.stacksize=n;void push(stack &S,node e) /入栈函数if(S.top-S.base)=S.stacksize)EnQueue(Q,e); /如果栈满，调用入队函数else S.top-passport=e.passport;S.top-time=e.time;S.top+;int pop(stack &S,node &e) /出栈函数if(S.top=S.base)return ERROR; /如果栈空，返回ERROR-S.top;e.passport=S.top-passport;e.time=S.top-time;return OK;3队列类型（便道）typedef struct Qnodenode Qdata;struct Qnode *next;Qnode;typedef struct Qnode *front;Qnode *rear;LinkQueue;void EnQueue(LinkQueue &Q,node e) /入队函数Qnode *q;q=(Qnode *)malloc(sizeof(Qnode);q-Qdata.passport=e.passport;q-Qdata.time=e.time;q-next=NULL;if(count=0)Q.front=q;count+; /若创建节点前队空，头指针指向节点Q.rear-next=q;Q.rear=q;void DeQueue(LinkQueue &Q,node &e) /出队函数if(Q.rear=NULL)else e.passport=Q.front-Qdata.passport;e.time=Q.front-Qdata.time;Q.front=Q.front-next;if(Q.front=NULL)Q.rear=Q.front;count=0;4全局变量及编译预处理语句#define ERROR 0#define OK 1#define NULL 0int count=0; /队列是否为空的标志int times;stack s,temp; /初始化栈LinkQueue Q; /初始化队列5主函数及其他函数的C+算法void main()int n,exit;float money;char info;int pass;Q.front=NULL;Q.rear=(Qnode *)malloc(sizeof(Qnode);Q.rear-next=Q.rear;printf(停车场容量:);cinn;initstack(s,n);initstack(temp,n);printf(停车场费率:);cinmoney;while(exit!=OK)printf(n请输入车辆数据nA到达 D离去 E结束:);cininfo;printf(请输入车辆牌照:);cinpass;if(info=A|info=E)printf(请输入进场时间:);if(info=D)printf(请输入离场时间:);cintimes;if(info=E)exit=OK;else if(info=A)int i,j;node a;a.passport=pass;a.time=times;push(s,a);for(i=1;inext;j+;printf(停车位置(便道):%dn,j);else if(info=D)node d;int tp,counter=0;docounter+;tp=pop(s,d);while(tp!=ERROR)if(d.passport=pass)float m;m=(times-d.time)*money;printf(停留时间:%d 需交费:%fn,times-d.time,m);while(temp.base!=temp.top)pop(temp,d);push(s,d);wait(s);d.passport=9999;tp=ERROR;elsepush(temp,d);d.passport=0;tp=ERROR;while(d.passport=0|countern);else if(info!=A&info!=D&info!=E)void wait(stack &S)if(S.top-S.base)=(S.stacksize-1)&count!=0)node temp;DeQueue(Q,temp);temp.time=times;push(S,temp);三、程序功能分析1、算法分析与探讨 该停车场管理系统首先初始化栈模拟停车场的容量，车辆到达时实现入栈操作，在栈中加入一个新元素，然后为新元素设置变量保存车辆的信息。车辆的信息包括：车牌号、汽车到达/离去标志、到达/离去时刻等。用队列模拟便道，实现能够通过车牌号等信息就可以查到车辆在便道中的位置。按照从终端读入的数据序列进行模拟管理。每辆车需要三个数据，其中车辆数据为：A表示到达，D表示离去，E表示程序结束。车辆牌照为整型数据。进场或离场时间同样为整型数据。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。如果停车场满了即栈满了就调用队列函数，等其他车辆离开后新的车辆在进入便道。2、调试分析（1）一开始在调试程序时遇到了内存错误，经过DEBUG，找到了引起内存错误的原因：即在建立队头指针与队尾指针时没有对指针进行初始化(没有为指针动态分配空间)。问题得到解决。 （2）在Wait函数中的If语句处，一开始的算法有些问题，导致实现的功能与设想的有出入，无法得到正确的结果。原条件为: S.top-S.base=S.stacksize后改为： (S.top-S.base)=(S.stacksize-1)&count!=0 该函数的功能得以正确实现。（3）在EnQueue函数中，一开始用的是建立实体结点，用队头队尾指针指向该实体的方法来创建队列。在调试过程中发现，忽略了生存期，导致队列并没有被创建。改为创建指针，并为指针分配空间，再给头指针和尾指针赋值的方式解决问题。虽然指针也有生存期，但为它分配的空间却并没有被收回，于是队列创建成功，问题解决。 （4）本程序中：车辆到达,离去时的时间复杂度均为：O(n)。本程序空间复杂度为：O(n)。 （5）经验体会：借助DEBUG和Watch，可以更快的找到程序中的非语法错误。在声明一个指针后，要对指针进行初始化，并且0可以作为地址使用。注意生存期对程序的影响。3、程序测试（1）输入车辆数据：A为到达，D为离去，E为结束程序。（2）接着输入车辆的牌照信息（3）若为到达的车辆，输入进场信息，若为离去的车辆，输入离场信息。（4）若车辆到达，可得到车辆的停放位置信息，若车辆离去，可得到车辆的停放时间（在便道上的停放时间除外），以及应该交纳的费用。（5）本程序不断循环要求输入车辆信息，直到输入的车辆数据为E时，程序结束。4、测试结果测试数据：设n=2输入数据：2输出：停车场容量:2停车场费率:6A，1，5 停车位置(停车场内):1A，2，10 停车位置(停车场内):2D，1，15 停留时间:10 需交费:60.00A，3，20 停车位置(停车场内):2A，4，25 停车位置(便道):1A，5，30 停车位置(便道):2D，2，35 停留时间:25 需交费:150.00D，4，40 停留时间:5 需交费:30.00E，0，05、源程序代码#include #include #include #define ERROR 0#define OK 1#define NULL 0typedef struct nodeint passport;int time;node;typedef struct stacknode *base;node *top;int stacksize;stack;typedef struct Qnodenode Qdata;struct Qnode *next;Qnode;typedef struct Qnode *front;Qnode *rear;LinkQueue;int count=0;int times;stack s,temp;LinkQueue Q;void initstack(stack &S,int n)S.base=(node *)malloc(n*sizeof(node);S.top=S.base;S.stacksize=n;void EnQueue(LinkQueue &Q,node e);void DeQueue(LinkQueue &Q,node &e);void push(stack &S,node e)if(S.top-S.base)=S.stacksize)EnQueue(Q,e);else S.top-passport=e.passport;S.top-time=e.time;S.top+;int pop(stack &S,node &e)if(S.top=S.base)return ERROR;-S.top;e.passport=S.top-passport;e.time=S.top-time;return OK;void wait(stack &S)if(S.top-S.base)=(S.stacksize-1)&count!=0)node temp;DeQueue(Q,temp);temp.time=times;push(S,temp);void EnQueue(LinkQueue &Q,node e)Qnode *q;q=(Qnode *)malloc(sizeof(Qnode);q-Qdata.passport=e.passport;q-Qdata.time=e.time;q-next=NULL;if(count=0)Q.front=q;count+;Q.rear-next=q;Q.rear=q;void DeQueue(LinkQueue &Q,node &e)if(Q.rear=NULL)else e.passport=Q.front-Qdata.passport;e.time=Q.front-Qdata.time;Q.front=Q.front-next;if(Q.front=NULL)Q.rear=Q.front;count=0;void main()int n,exit;float money;char info;int pass;Q.front=NULL;Q.rear=(Qnode *)malloc(sizeof(Qnode);Q.rear-next=Q.rear;printf(停车场容量:);cinn;initstack(s,n);initstack(temp,n);printf(停车场费率:);cinmoney;while(exit!=OK)printf(n请输入车辆数据nA到达 D离去 E结束:);cininfo;printf(请输入车辆牌照:);cinpass;if(info=A|info=E)printf(请输入进场时间:);if(info=D)printf(请输入离场时间:);cintimes;if(info=E)exit=OK;else if(info=A)int i,j;node a;a.