数据结构报告 停车场问题.doc

⒈ 问题描述：停车场管理问题[问题描述] 设有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出车辆按到达停车场时间的早晚依次从停车场最里面向大门口处停放(最先到达的第一辆车放在停车场的最里面)如果停车场已放满n辆车，则后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场停车场内如有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费如果停留在便道上的车未进停车场就要离去，允许其离去，不收停车费，并且仍然保持在便道上等待的车辆的次序编制一程序模拟该停车场的管理[实现要求] 要求程序输出每辆车到达后的停车位置(停车场或便道上)，以及某辆车离开停车场时应交纳的费用和它在停车场内停留的时间[实现提示] 汽车的模拟输入信息格式可以是：(到达／离去，汽车牌照号码，到达／离去的时刻)例如，(‘A’，，1，5)表示1号牌照车在5这个时刻到达，而(‘D’，，5，20)表示5号牌照车在20这个时刻离去整个程序可以在输入信息为(‘E’，0，0)时结束。

本题可用栈和队列来实现⒉ 设计：⑴ 数据结构设计和核心算法设计描述；停车场管理系统是充分利用数据结构中栈和队列的思想实现的，栈是一种只能在叫做栈的一段进行进栈或者出栈操作的线性数据结构栈的主要特点是”后进先出”，即后进栈的元素先处理停车场的容量即为栈的存储空间，停车场的车辆的停靠是无秩序的，因此采用链式存储的方式更适合，也方便车辆的调度队列是限定仅能在表的一端进行插入，在表的另一端进行删除的线性表队列中可以插入的一端称为队尾，可以删除的一端称为队首把一个元素插入队列中的操作为进队，队列中删除一个元素的操作为出队队列存取操作符合：先进先出停车场的车辆到达停车和车辆的离开的管理方式就是采用队列的“先进先出”的移动的思想停车场的入口就是队列的队首，停车场的出口就是队列的队尾⑵ 主控及功能模块层次结构；2.1设定栈的抽象数据类型定义为：ADT stack{数据对象：D={ai|ai∈charset, i=1,2,……,n,n≥0}数据关系：R1={|ai-1,ai∈D,i=2……,n}基本操作：initstack(&S, n)操作结果：构造一个空栈S,该栈可存放n个元素push(&S, e)初始条件：栈S已存在。

操作结果：在栈S的栈顶插入新的栈顶元素epop(&S, &e)初始条件：栈S已存在操作结果：删除S的栈顶元素，并以e返回其值DestroyStack(&S)初始条件：栈S已存在操作结果：销毁栈SClearStack(&S)初始条件：栈S已存在操作结果：将S清为空栈StackLength(&S)初始条件：栈S已存在操作结果：返回栈S的长度StackEmpty(&S)初始条件：栈S已存在操作结果：若S为空栈，则返回TRUE，否则返回FALSEGetTop(S, &e)初始条件：栈S已存在操作结果：若栈S不空，则以e返回栈顶元素StackTraverse(S, visit())初始条件：栈S已存在操作结果：从栈底到栈顶依次对S中的每个元素调用函数visit()}ADT stack2.2 设定队列的抽象数据类型定义为：ADT Queue{数据对象：D={ai|ai∈ElemSet, i=1,2,……,n,n≥0}数据关系：R1={|ai-1,ai∈D,i=2……,n}基本操作：InitQueue(&Q)操作结果：构造一个空队列QDestroyQueue(&Q)初始条件：队列Q已存在操作结果：队列Q被销毁，不再存在。

ClearQueue(&Q)初始条件：队列Q已存在操作结果：将Q清为空队列QueueEmpty(&Q)初始条件：队列Q已存在操作结果：若Q为空队列，则返回TRUE，否则返回FALSEQueueLength(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.3详细设计车辆信息类型typedef struct node{int passport; //存储车辆牌照信息int time; //存储进场时间信息}node;2．栈类型（停车场）typedef struct stack{ //定义停车场栈类型 node *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++; }}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); }}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 Qnode{ //定义便道队列类型 node 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．主函数及其他函数的算法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("停车场容量:"); scanf("%d",&n); initstack(s,n); initstack(temp,n); printf("停车场费率(元/小时):"); scanf("%f",&money); while(exit!=OK){ printf("\n请选择车辆状态\n1到达 2离去 3结束:"); getchar(); scanf("%c",&info); printf("请输入车辆牌照:"); scanf("%d",&pass); if(info=='1'||info=='3')printf("请输入进场时间:"); if(info=='2')printf("请输入离场时间:"); scanf("%d",×); if(info=='3'){exit=OK;} else if(info=='1'){ int i,j; node a; a.passport=pass; a.time=times; push(s,a); for(i=1;i<=n;i++){ if(s.base[i-1].passport==a.passport){ printf("停车位置(停车场内):%d\n",i); } } Qnode *tp; tp=Q.front; if(tp==NULL){} else{ j=1; while(tp!=Q.rear){ tp=tp->next; j++; } printf("停车位置(便道):%d\n",j); } } else if(info=='2'){ node d; int tp,counter=0; do{ counter++; tp=pop(s,d); while(tp!=ERROR){ if(d.passport==pass){ float m; m=-(times-d.time)*money; printf("停留时间:%d 需交费:%f\n",-(times-d.time)*(-1),m*(-1)); while(temp.base!=temp.top){ pop(temp,d); push(s,。