关于停车场问题的算法

停车场管理问题

1） 问题描述

设停车场是一个可停放 n 辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端）。若停车场内已经停满 n辆车，那么后来的车只能在门外的便道上等候。一旦有车开走，则排在便道上的第一辆车即可开入。当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场。每辆停放在车场的车在它离开停车场时必须按它停留的时间长短缴纳费用。试为停车场编制按上述要求进行管理的模拟程序。

2）基本要求

以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入数据的序列进行模拟管理。每一组输入数据包括三个数据项：汽车的“到达”（‘A’表示）或“离去”（‘D’表示）信息、汽车标识（牌照号）以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或者便道上的停车位置；若是车辆离去，则输出汽车在停车场停留的时间和应缴纳的费用（便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。 3）提示

需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。

4）输入输出:

输入数据：程序接受5个命令，分别是：到达（‘A’,车牌号,时间)；离去(‘D’,车牌号,时间)；停车场（‘P’, 0, 0）显示停车场的车数；候车场（‘W’, 0, 0）显示候车场的车数；退出（‘E’, 0, 0）退出程序。

输出数据：对于车辆到达，要输出汽车在停车场内或者便道上的停车位置；对于车辆离去，则输出汽车在停车场停留的时间和应缴纳的费用（便道上不收费）。

二、算法基本思想描述

根据要求由此很容易联想到数据结构中的堆栈模型，因此可首先设计一个堆栈，以堆栈来模拟停车场，我设计用顺序存储结构来存储停车场内的车辆信息，并给车辆按进栈顺序编号，当停车场内某辆车要离开时，在他之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入停车场。这是个一退一进的过程，而且让道的汽车必须保持原有的先后顺序，因此可再设计一个堆栈，以之来暂时存放为出站汽车暂时让道的汽车。当停车场满后，继续进来的汽车需要停放在停车场旁边的便道上等候，若停车场有汽车开走，则按排队的先后顺序依次进站，最先进入便道的汽车将会最先进入停车场，这完全是一个先进先出模型，因此可设计一个队列来模拟便道，队列中的数据元素设计成汽车的车牌号，并以链表的形式存储。另外，停车场根据汽车在停车场内停放的总时长来收费的，在便道上的时间不计费，因此必须记录车辆进入停车场时的时间和车辆离开停车场时的时间，然后计算、显示费用情况。

三、模块结构及流程图

以堆栈来模拟停车场和以堆栈里的数据元素我设计成汽车的车牌号 初始化车站, 初始化让路的临时栈, 初始化通道 车辆到达 车场已满，车进便道 车场未满，车进车场 判断车场是否已满 输入车子到达时间,车牌号

车子离开 此车后面的车辆退出并进入临时栈 输入离开车辆的离开时间,进行停车费用的计算 有 判断车场内是否有车 无未满 车进入车场 不做任何计算

四、详细设计

#include #include #include typedef struct{ int number;

int time; }car;

typedef struct{

car *base; car *top;

int stacksize; }sqstack;

void Initstack(sqstack *s){

s->base=(car *)malloc(sizeof(car)); if(!s->base) exit(-1); s->top=s->base;

s->stacksize=0; }

void push(sqstack *s,car e){ *s->top++=e; s->stacksize++; }

car pop(sqstack *s){ car e;

if(s->top==s->base){

printf(\停车场内没有该车辆!\\n\ exit(0) ; }

e=*--s->top; s->stacksize--; return e; }

typedef struct Qnode{ int number;

int time;

struct Qnode *next; }QNode,*QueuePtr; typedef struct{ QueuePtr front; QueuePtr rear; int length; }LinkQueue;

int InitQueue(LinkQueue *Q){

Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q->front)exit(-1); Q->front->next=NULL; Q->length=0; return 1; }

void EnQueue(LinkQueue *Q,car *a ){ QueuePtr p;

p=(QueuePtr)malloc(sizeof(QNode)); if(!p)exit(-1);

p->number=a->number; p->time=a->time; p->next=NULL; Q->rear->next=p; Q->rear=p; Q->length++; }

QueuePtr DeQueue(LinkQueue *Q){ QueuePtr p,e,s={0}; if(Q->front==Q->rear){ printf(\便道上没有车辆!\\n\ return s; }

p=Q->front->next; e=p;

Q->front->next=p->next; Q->length--;

if(Q->rear==p)Q->front=Q->rear;

本文来源：https://www.bwwdw.com/article/uwfh.html