数据结构 停车场管理

数据结构 停车场管理数据结构停车场管理2008-12-26 17：16需求分析本次数据结构课程设计的具体内容是停车场管理系统，该系统用栈结构模拟停车场，限定停车场的容量为n，用队列结构模拟等待的便道，空间不限制。车辆的信息包括：车牌号、汽车到达/离去标志、到达/离去时刻等。按照从终端读入的数据序列进行模拟管理。每辆车需要三个数据，其中车辆数据为：A表示到达，D表示离去，E表示程序结束。车辆牌照为整型数据。进场或离场时间同样为整型数据。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用(在便道上停留的时间不收费)。停车场管理系统主要实现以下几个功能：(1)根据车辆到达停车场到车辆离开停车场时所停留的时间进行计时收费。(2)该程序设计能够通过车牌号能查到该车辆在停车场或便道中的位置。(3)当有车辆从停车场离开时，等待的车辆按顺序进入停车场停放。实现停车场的调度功能。该程序设计可以完整的模拟停车场的管理过程。概要设计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 stack 1.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 Queue 2)本程序图示结构(保密)详细设计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)；/如果栈满，调用入队函数elseS.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 structQnode*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)elsee.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(停车场容量：)；cin n；initstack(s,n)；initstack(temp,n)；printf(停车场费率：)；cin money；while(exit！=OK)printf(n请输入车辆数据nA到达D离去E结束：)；cin info；printf(请输入车辆牌照：)；cin pass；if(info=A|info=E)printf(请输入进场时间：)；if(info=D)printf(请输入离场时间：)；cin times；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；i=n；i+)if(s.basei-1.passport=a.passport)printf(停车位置(停车场内)：%dn,i)；Qnode*tp；tp=Q.front；if(tp=NULL)elsej=1；while(tp！=Q.rear)tp=tp-next；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|counter n)；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)一开始在调试程序时遇到了内存错误，经过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可以作为地址使用。注意生存期对程序的影响。用户使用说明(1)输入车辆数据：A为到达，D为离去，E为结束程序。(2)接着输入车辆的牌照信息(3)若为到达的车辆，输入进场信息，若为离去的车辆，输入离场信息。(4)若车辆到达，可得到车辆的停放位置信息，若车辆离去，可得到车辆的停放时间(在便道上的停放时间除外)，以及应该交纳的费用。(5)本程序不断循环要求输入车辆信息，直到输入的车辆数据为E时，程序结束。测试结果测试数据：设n=2输入数据：2输出：停车场容量：2停车场费率：6 A，1，5停车位置(停车场内)：1 A，2，10停车位置(停车场内)：2 D，1，15停留时间：10需交费：60.00 A，3，20停车位置(停车场内)：2 A，4，25停车位置(便道)：1 A，5，30停车位置(便道)：2 D，2，35停留时间：25需交费：150.00 D，4，40停留时间：5需交费：30.00