数据结构报告-停车场问题

数据结构报告-停车场问题⒈问题描述：停车场管理问题[问题描述]设有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里面向大门口处停放(最先到达的第一辆车放在停车场的最里面)。如果停车场已放满n辆车，则后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场就要离去，允许其离去，不收停车费，并且仍然保持在便道上等待的车辆的次序。编制一程序模拟该停车场的管理。[实现要求]要求程序输出每辆车到达后的停车位置(停车场或便道上)，以及某辆车离开停车场时应交纳的费用和它在停车场内停留的时间。[实现提示]汽车的模拟输入信息格式可以是：(到达／离去，汽车牌照号码，到达／离去的时刻)。例如，(‘A’，，1，5)表示1号牌照车在5这个时刻到达，而(‘D’，，5，20)表示5号牌照车在20这个时刻离去。整个程序可以在输入信息为(‘E’，0，0)时结束。本题可用栈和队列来实现。⒉设计：⑴数据结构设计和核心算法设计描述；停车场管理系统是充分利用数据结构中栈和队列的思想实现的，栈是一种只能在叫做栈的一段进行进栈或者出栈操作的线性数据结构。栈的主要特点是”后进先出”，即后进栈的元素先处理。停车场的容量即为栈的存储空间，停车场的车辆的停靠是无秩序的，因此采用链式存储的方式更适合，也方便车辆的调度。队列是限定仅能在表的一端进行插入，在表的另一端进行删除的线性表。队列中可以插入的一端称为队尾，可以删除的一端称为队首。把一个元素插入队列中的操作为进队，队列中删除一个元素的操作为出队。队列存取操作符合：先进先出。停车场的车辆到达停车和车辆的离开的管理方式就是采用队列的“先进先出”的移动的思想。停车场的入口就是队列的队首，停车场的出口就是队列的队尾。⑵主控及功能模块层次结构；数据结构报告-停车场问题全文共12页，当前为第1页。2.1设定栈的抽象数据类型定义为：

ADTstack{

数据对象：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的栈顶插入新的栈顶元素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()。

}ADTstack

2.2设定队列的抽象数据类型定义为：

ADTQueue{

数据对象：D={ai|ai∈ElemSet,i=1,2,……,n,n≥0}

数据关系：R1={|ai-1,ai∈D,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)

数据结构报告-停车场问题全文共12页，当前为第2页。初始条件：队列Q已存在。

操作结果：插入元素e为Q的新的队尾元素。

DeQueue(&Q,&e)

初始条件：Q为非空队列。

操作结果：删除Q的队头元素，并用e返回其值。

QueueTraverse(Q,visit())

初始条件：Q已存在且非空。

操作结果：从队头到队尾，依次对Q的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。

数据结构报告-停车场问题全文共12页，当前为第1页。数据结构报告-停车场问题全文共12页，当前为第2页。2.3详细设计车辆信息类型

typedefstructnode{

intpassport;//存储车辆牌照信息

inttime;//存储进场时间信息

}node;

2．栈类型（停车场）

typedefstructstack{//定义停车场栈类型 node*base; node*top; intstacksize;}stack;voidinitstack(stack&S,intn){//构造空栈 S.base=(node*)malloc(n*sizeof(node)); S.top=S.base; S.stacksize=n;}

voidpush(stack&S,nodee){//入栈函数 if((S.top-S.base)>=S.stacksize){EnQueue(Q,e);}//如果栈满则调用入队函数 else{ S.top->passport=e.passport; S.top->time=e.time; S.top++; }}voidwait(stack&S){ if((S.top-S.base)==(S.stacksize-1)&&count!=0){ nodetemp; DeQueue(Q,temp); temp.time=times; push(S,temp); }}数据结构报告-停车场问题全文共12页，当前为第3页。数据结构报告-停车场问题全文共12页，当前为第3页。 if(S.top==S.base)returnERROR;//如果栈空则返回ERROR --S.top; e.passport=S.top->passport; e.time=S.top->time; returnOK;}3．队列类型（便道）

typedefstructQnode{//定义便道队列类型 nodeQdata; structQnode*next;}Qnode;typedefstruct{ Qnode*front; Qnode*rear;}LinkQueue;voidEnQueue(LinkQueue&Q,nodee){//入队函数 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;}voidDeQueue(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．全局变量及编译预处理语句

#defineERROR0

#defineOK1

#defineNULL0

intcount=0;//队列是否为空的标志inttimes;stacks,temp;//初始化栈数据结构报告-停车场问题全文共12页，当前为第4页。数据结构报告-停车场问题全文共12页，当前为第4页。5．主函数及其他函数的算法

voidmain(){ intn,exit; floatmoney; charinfo; intpass; 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;} elseif(info=='1'){ inti,j; nodea; 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;数据结构报告-停车场问题全文共12页，当前为第5页。 数据结构报告-停车场问题全文共12页，当前为第5页。 } printf("停车位置(便道):%d\n",j); } } elseif(info=='2'){ noded; inttp,counter=0; do{ counter++; tp=pop(s,d); while(tp!=ERROR){ if(d.passport==pass){ floatm; 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,d); } wait(s); d.passport=9999; tp=ERROR; } else{ push(temp,d); d.passport=0; tp=ERROR; } } }while(d.passport==0||counter>n); } elseif(info!='1'&&info!='2'&&info!='3'){} }}数据结构报告数据结构报告-停车场问题全文共12页，当前为第6页。⑶主要功能模块的输入、处理(算法框架描述)和输出；⑷功能模块之间的调用与被调用关系等。（1）输入车辆数据：1为到达，2为离去，3为结束程序。（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

E，0，0数据结构报告数据结构报告-停车场问题全文共12页，当前为第7页。运行结果（1）进入停车场离开停车场等待停车数据结构报告-停车场问题全文共12页，当前为第8页。数据结构报告-停车场问题全文共12页，当前为第8页。程序源代码#include<stdio.h>#include<stdlib.h>#defineERROR0#defineOK1#defineNULL0typedefstructnode{//定义车辆信息数据结构 intpassport;//存储车辆牌照信息 inttime;//存储进场时间信息}node;typedefstructstack{//定义停车场栈类型 node*base; node*top; intstacksize;}stack;typedefstructQnode{//定义便道队列类型 nodeQdata; structQnode*next;}Qnode;typedefstruct{ Qnode*front; Qnode*rear;}LinkQueue;intcount=0;//队列是否为空的标志inttimes;stacks,temp;//初始化栈LinkQueueQ;//初始化队列voidinitstack(stack&S,intn){//构造空栈 S.base=(node*)malloc(n*sizeof(node)); S.top=S.base; S.stacksize=n;}voidEnQueue(LinkQueue&Q,nodee);//入队函数voidDeQueue(LinkQueue&Q,node&e);//出队函数voidpush(stack&S,nodee){//入栈函数 if((S.top-S.base)>=S.stacksize){EnQueue(Q,e);}//如果栈满则调用入队函数 else{ S.top->passport=e.passport;数据结构报告-停车场问题全文共12页，当前为第9页。 数据结构报告-停车场问题全文共12页，当前为第9页。 S.top++; }}intpop(stack&S,node&e){//出栈函数 if(S.top==S.base)returnERROR;//如果栈空则返回ERROR --S.top; e.passport=S.top->passport; e.time=S.top->time; returnOK;}voidwait(stack&S){ if((S.top-S.base)==(S.stacksize-1)&&count!=0){ nodetemp; DeQueue(Q,temp); temp.time=times; push(S,temp); }}voidEnQueue(LinkQueue&Q,nodee){//入队函数 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;}voidDeQueue(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;} }}voidmain(){ intn,exit; floatmoney; charinfo; intpass; Q.front=NULL;数据结构报告-停车场问题全文共12页，当前为第10页。 数据结构报告-停车场问题全文共12页，当前为第10页。 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结束:"); scanf("%c",&info); printf("请输入车辆牌照:"); scanf("%d",&pass); if(info=='1'||info=='3')printf("请输入进场时间:"); if(info=='2')printf("请输入离场时间:"); scanf("%d",×); if(info=='3'){exit=OK;} elseif(info=='1'){ inti,j; nodea; 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); } } elseif(