停车场管理问题

一．问题描述

1.实验题目：

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

2.基本要求：

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

3.测试数据：

设n=2,输入数据为：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3， 20），（‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，4，40），（‘E’，0，0）。每一组输入数据包括三个数据项：汽车 “到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，‘A’表示到达；‘D’表示离去，‘E’表示输入结束。其中：（‘A’，1，5）表示1号牌照车在5这个时刻到达，而（‘D’，1，15）表示1号牌照车在15这个时刻离去。

二．需求分析

1.程序所能达到的基本可能：

程序以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入数据的序列进行模拟管理。栈以顺序结构实现，队列以链表结构实现。同时另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车。输入数据按到达或离去的时刻有序。当输入数据包括数据项为汽车的“到达”（‘A’表示）信息，汽车标识（牌照号）以及到达时刻时，应输出汽车在停车场内或者便道上的停车位置；当输入数据包括数据项为汽车的“离去”（‘D’表示）信息，汽车标识（牌照号）以及离去时刻时，应输出汽车在停车场停留的时间和应缴纳的费用（便道上停留的时间不收费）；当输入数据项为（‘P’，0，0）时，应输出停车场的车数；当输入数据项为（‘W’, 0, 0）时，应输出候车场车数；当输入数据项为（‘E’, 0, 0），退出程序；

2.输入输出形式及输入值范围：

程序运行后进入循环，显示提示信息：“请输入停车场最大容量n=:”，提示用户输入停车场最大容量，输入后显示提示信息：请输入车辆信息，提示用户输入车辆信息（“到达”

或者“离开”，车牌编号，到达或者离开的时间）。若车辆信息为“到达A”，车辆信息开始进栈(模拟停车场），当栈满，车辆会进队列（模拟停车场旁便道），若车辆信息为“离开D”，会显示该车进入停车场的时间以及相应的停车费用，若该车较部分车早进停车场，这部分车需先退出停车场，暂时进入一个新栈为其让道，当待离开车离开停车场后，这部分车会重新进入停车场，同时便道上的第一辆车进入停车场；若输入（‘P’，0，0），会显示停车场的车数；若输入（‘W’，0，0），会显示便道上的车数；若输入（‘E’，0，0），程序会跳出循环，同时程序结束。用户每输入一组数据，程序就会根据相应输入给出输出。输入值第一个必须为字母，后两个为数字，中间用逗号隔开

3.测试数据要求：

设n=2,输入数据为：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3， 20），（‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，4，40），（‘E’，0，0）。

三．概要设计

1. 所用到得数据结构及其ADT

为了实现上述功能，该程序以顺序栈模拟停车场以及临时停放为给要离去的汽车让路而从停车场退出来的汽车的场地，以链表队列模拟车场外的便道，因此需要栈和队列这两个抽象数据类型。

顺序栈数据类型定义

typedef struct Stack

{

struct Node data[MaxSize];

int top;

int num;

}SqStack;

基本操作：

SqStack *Init_SeqStack() //置空栈

int ISEmpty_SeqStack(SqStack *s) //判断栈是否为空，栈为空返回1

int ISFULL_SeqStack(SqStack *s,int n) //判断栈是否已满，若栈满返回1

void Push_SeqStack(SqStack *p,struct Node s) //入栈

int POP_SeqStack(SqStack *s,struct Node car)//出栈

2.链表队列数据类型定义

QNODE //队列节点

{

struct Node data;

QNODE *next;

};

typedef struct linkqueue //队列结构体定义

{

QNODE *front,*rear;

int num;

}LinkQueue;

基本操作：

LinkQueue *Init_LQueue() //创建空队列

int ISEmpty_LQueue(LinkQueue *q) //判断队列是否为空，队列为空返回1

void IN_Lqueue( LinkQueue *q,struct Node s) //入队

struct Node Out_LQueue(LinkQueue *q) //出队

2. 主程序流程及其模块调用关系

1)主程序模块

开始初始界面显示输入停车场最大容量n输入车辆信息NNcar.AL=='A'Ycar.AL=='D'Y出栈，输出车辆停留时间N队列为空car.AL='P'，car.NO=0，car.time=0 Ncar.AL='W'，car.NO=0，car.time=0Ncar.AL!='E'Y显示停车场的车数Y显示候车场的车数Y栈满入栈，输出车辆在停车场的位置进入队列输出车辆在便道的位置进栈，车辆从便道进入停车场输入结束结束输入车辆信息 2)出栈

开始找到车牌号为P.NO的车，驶出停车场计算停留时间输出3）判断栈是否为空4）判断栈是否已满Y候车场为空N候车场驶入停车场结束开始Ns->top ==-1Y栈空返回1栈不为空返回0结束

开始Ns->top =n-1Y栈满返回1栈不满返回0结束 5）判断队列是否为空

开始q->front==q->rearNY队列空返回1队列不为空返回0结束 6）出队

开始p=q->front->next;q->front->next=p->next;q->num --;q->front->next==NULLNYq->rear=q->front;结束

函数调用：

main()函数中调用：

ISFULL_SeqStack(parkstack,n)，

IN_Lqueue(parkqueue,car);

Push_SeqStack(parkstack,car);

t=POP_SeqStack(parkstack,car);

ISEmpty_LQueue(parkqueue)==0；

Push_SeqStack(parkstack,Out_LQueue(parkqueue) );

POP_SeqStack(SqStack *s,struct Node car)出栈函数中调用：

Init_SeqStack();

Push_SeqStack(p,s->data[s->top]);

ISEmpty_SeqStack(p)==0

函数调用关系图

ISFULL_SeqStack()IN_Lqueue()Push_SeqStack()main()函数POP_SeqStack()Init_SeqStack();ISEmpty_LQueue()Push_SeqStack( ) 四、 详细设计

1. 实现每个操作的伪码，重点语句加注释

1）主程序模块

int main()

{

SqStack *parkstack; //parkstack为表示停车场的栈

LinkQueue *parkqueue; //parkqueue为表示便道的队列

struct Node car;

int n,a=0,t; //n为停车场栈的最大容量

time_t rawtime;

struct tm * timeinfo;

time (&rawtime);

timeinfo = localtime (&rawtime);

parkstack=Init_SeqStack();

parkqueue=Init_LQueue();

printf(\"/*************************************/\\n\"); //初始界面

printf(\" 学号：031350102\\n\");

printf(\" 姓名：王亚文\\n\");

printf(\" 停车场管理问题\\n\");

printf(\"/*************************************/\\n\");

printf(\"请输入停车场最大容量n=\\n\");

scanf(\"%d\

printf(\"请输入车辆信息\\n\");

scanf(\"%c,%d,%d\

while(car.AL!='E')

{

if(car.AL=='A' )

{ // 汽车到达的情况

if(ISFULL_SeqStack(parkstack,n)==1) //栈满的情况

{

IN_Lqueue(parkqueue,car); //进入队列等待

printf(\"这辆车在门外便道上第%d个位置\\n\

printf(\"\\n\");

printf(\"请输入车辆信息\\n\");

}

else

{

Push_SeqStack(parkstack,car); //入栈

printf(\"这辆车在停车场内第%d个位置\\n\

printf(\"\\n\");

printf(\"请输入车辆信息\\n\");

}

}

if(car.AL=='D' ) //汽车离开的情况

{

t=POP_SeqStack(parkstack,car);//出栈

printf(\"这辆车停留时间为%d\\n\

printf(\"\\n\");

printf(\"请输入车辆信息\\n\");

if(ISEmpty_LQueue(parkqueue)==0) //队列不为空需要进栈

Push_SeqStack(parkstack,Out_LQueue(parkqueue) );

}

if(car.AL=='P'&&car.NO==0&&car.time==0 )//显示停车场的车数

{

printf(\"停车场的车数为%d\\n\

printf(\"\\n\");

printf(\"请输入车辆信息\\n\");

}

if(car.AL=='W'&&car.NO==0&&car.time==0 )//显示候车场的车数

{

printf(\"候车场的车数为%d\\n\

printf(\"\\n\");

printf(\"请输入车辆信息\\n\");

}

scanf(\"%c,%d,%d\

}

printf(\"输入结束\\n\");

return 1;

}

2）置空栈模块

SqStack *Init_SeqStack() //置空栈

{

SqStack *s;

s=(SqStack*)malloc(sizeof(SqStack));

s->top=-1;

s->num=0;

return s;

}

3）创建空队列模块

LinkQueue *Init_LQueue() //创建空队列

{

LinkQueue *q;

QNODE *p;

q=(LinkQueue*)malloc(sizeof(LinkQueue));

p=(QNODE*)malloc(sizeof(QNODE));

p->next=NULL;

q->front=q->rear=p;

q->num=0;

return q;

}

4）判断栈是否为空模块

int ISEmpty_SeqStack(SqStack *s) //判断栈是否为空，栈为空返回1

{

if(s->top ==-1)

return 1;

else

return 0;

}

5）判断栈是否已满模块

int ISFULL_SeqStack(SqStack *s,int n) //判断栈是否已满，若栈满返回1

{

if(s->top==n-1)

return 1;

else

return 0;

}

6）判断队列是否为空模块

int ISEmpty_LQueue(LinkQueue *q) //判断队列是否为空，队列为空返回1

{

if(q->front==q->rear)

return 1;

else

return 0;

}

7）入队模块

void IN_Lqueue( LinkQueue *q,struct Node s) //入队

{

QNODE *p;

p=(QNODE*)malloc(sizeof(QNODE));

p->data=s;

q->num++;

p->next=NULL;

q->rear->next =p;

q->rear =p;

}

8）入栈模块

void Push_SeqStack(SqStack *p,struct Node s) {

p->top ++;

p->data[p->top]=s;

//入栈

p->num++;

}

9）出栈模块

int POP_SeqStack(SqStack *s,struct Node car)//出栈

{

SqStack *p;

int t;

p=Init_SeqStack();

while(s->data[s->top].NO !=car.NO)//找到车牌号为P.NO的车，

{

Push_SeqStack(p,s->data[s->top]);

s->top--;

s->num--;

}

t=car.time-s->data[s->top].time;

s->top--;

s->num--;

while(ISEmpty_SeqStack(p)==0)

{

Push_SeqStack(s,p->data[p->top]);

p->top--;

p->num--;

}

return t;

}

10）出队模块

struct Node Out_LQueue(LinkQueue *q) //出队

{

QNODE *p;

p=q->front->next;

q->front->next=p->next;

q->num --;

if( q->front->next==NULL)

q->rear=q->front;

return p->data;

free(p);

}

五、 调试分析

1. 设计与调试过程中遇到的问题分析、体会

1）编写代码时，由于对栈和队列不熟悉，经常会一些问题，该程序定义了车辆信息，停车场的顺序栈，便道上的链表队列，所以在函数代值时会出现代值的问题，例如在出栈的程序

POP_SeqStack(SqStack

*s,struct

Node

car)中一开始在

s->data[s->top].NO !=car.NO这句话中我编的代码是s->data.NO !=car.NO'程序报错.NO' : left operand points to 'struct', use '->'，这就是因为定义的太多了，忘记了当初定义的停车场栈是：struct Node s->data[s->top].time

data[MaxSize];

就

是

像

程

序

中

这样的定义因为太长了经常会搞混，再次像

IN_Lqueue(parkqueue,car);， Push_SeqStack(parkstack,car); 这种涉及函数调用的尤其要注意代的应该是什么。

2）这个程序设计时还有一个问题就是有关结构体的输入问题，一开始我的程序是printf(\"请输入车辆状态信息\\n\");scanf(\"%c\请输入车辆车牌号\\n\");scanf(“%d\请输入车辆时间n\"); scanf(\"%d\）；程序没有报错，但在输入时就有问题了

后

来

将

程

序

改

为

printf(\"

请

输

入

车

辆

信

息

\\n\");

scanf(\"%c,%d,%d\之后程序可以正常运行了

3）再次本程序由于多次涉及到程序调用。一开始我比较喜欢把所有的语句全写在主程

序中，在简单的程序这种方法是可行的，但是这个程序由于有些函数像Push_SeqStack(p,s->data[s->top]);ISEmpty_SeqStack(p)==0会多次用到，所以考虑写子程序，这样减少了程序的复杂性，主函数也更加简单明了。

2. 主要算法的时间复杂度分析

主函数中 对每次输入的车辆信息只选择其中一个执行，时间复杂度O（1）；空间复杂度O（1）；入栈入队列函数根据判断条件将数据入栈或入队列，时间复杂度O（1）；空间复杂度O（1）；出栈数据不在最顶端需将n个数据先出该栈，再入新栈，再回旧栈，时间复杂度O（n）；空间复杂度O（1）；

六、 使用说明

程序运行后进入循环，显示提示信息：“请输入停车场最大容量n=:”，提示用户输入停车场最大容量，输入后显示提示信息：请输入车辆信息，提示用户输入车辆信息（“到达”或者“离开”，车牌编号，到达或者离开的时间）。若车辆信息为“到达A”，车辆信息开始进栈(模拟停车场），当栈满，车辆会进队列（模拟停车场旁便道），若车辆信息为“离开D”，会显示该车进入停车场的时间以及相应的停车费用，若该车较部分车早进停车场，这部分车需先退出停车场，暂时进入一个新栈为其让道，当待离开车离开停车场后，这部分车会重新进入停车场，同时便道上的第一辆车进入停车场；若输入（‘P’，0，0），会显示停车场的车数；若输入（‘W’，0，0），会显示便道上的车数；若输入（‘E’，0，0），程序会跳出循环，同时程序结束。用户每输入一组数据，程序就会根据相应输入给出输出。输入值第一个必须为字母，后两个为数字，中间用逗号隔开

七、 测试结果

八、 附录

#include

#include

#include

#include

typedef int ElemType;

#define MaxSize 100

#define QNODE struct QNode

typedef struct Node //车辆信息

{

char AL;

int NO;

int time;

}Node;

typedef struct Stack //栈定义

{

struct Node data[MaxSize];

int top;

int num;

}SqStack;

QNODE //队列节点

{

struct Node data;

QNODE *next;

};

typedef struct linkqueue //队列结构体定义

{

QNODE *front,*rear;

int num;

}LinkQueue;

SqStack *Init_SeqStack() //置空栈

{

SqStack *s;

s=(SqStack*)malloc(sizeof(SqStack));

s->top=-1;

s->num=0;

return s;

}

LinkQueue *Init_LQueue() //创建空队列

{

LinkQueue *q;

QNODE *p;

q=(LinkQueue*)malloc(sizeof(LinkQueue));

p=(QNODE*)malloc(sizeof(QNODE));

p->next=NULL;

q->front=q->rear=p;

q->num=0;

return q;

}

int ISEmpty_SeqStack(SqStack *s) {

if(s->top ==-1)

return 1;

else

return 0;

//判断栈是否为空，栈为空返回1

}

int ISFULL_SeqStack(SqStack *s,int n) //判断栈是否已满，若栈满返回1

{

if(s->top==n-1)

return 1;

else

return 0;

}

int ISEmpty_LQueue(LinkQueue *q) {

if(q->front==q->rear)

return 1;

else

//判断队列是否为空，队列为空返回1

return 0;

}

void IN_Lqueue( LinkQueue *q,struct Node s) //入队

{

QNODE *p;

p=(QNODE*)malloc(sizeof(QNODE));

p->data=s;

q->num++;

p->next=NULL;

q->rear->next =p;

q->rear =p;

}

void Push_SeqStack(SqStack *p,struct Node s) //入栈

{

p->top ++;

p->data[p->top]=s;

p->num++;

}

int POP_SeqStack(SqStack *s,struct Node car)//出栈

{

SqStack *p;

int t;

p=Init_SeqStack();

while(s->data[s->top].NO !=car.NO)//找到车牌号为P.NO的车，

{

Push_SeqStack(p,s->data[s->top]);

s->top--;

s->num--;

}

t=car.time-s->data[s->top].time;

s->top--;

s->num--;

while(ISEmpty_SeqStack(p)==0)

{

Push_SeqStack(s,p->data[p->top]);

p->top--;

p->num--;

}

return t;

}

struct Node Out_LQueue(LinkQueue *q) //出队

{

QNODE *p;

p=q->front->next;

q->front->next=p->next;

q->num --;

if( q->front->next==NULL)

q->rear=q->front;

return p->data;

free(p);

}

int main()

{

SqStack *parkstack; //parkstack为表示停车场的栈

LinkQueue *parkqueue; //parkqueue为表示便道的队列

struct Node car;

int n,a=0,t; //n为停车场栈的最大容量

time_t rawtime;

struct tm * timeinfo;

time (&rawtime);

timeinfo = localtime (&rawtime);

parkstack=Init_SeqStack();

parkqueue=Init_LQueue(); //初始界面

printf(\" 实验名称：实验二 停车场管理问题求解\\n\");

printf(\" 学号：031350102\\n\");

printf(\" 姓名：王亚文\\n\");

printf(\"=============================================\\n\");

printf(\"程序运行开始，\");

printf(\"Current local time and date:%s\

printf(\"请输入停车场最大容量n=\\n\");

scanf(\"%d\

printf(\"请输入车辆信息\\n\");

scanf(\"%c,%d,%d\

while(car.AL!='E')

{

if(car.AL=='A' )

{ // 汽车到达的情况

if(ISFULL_SeqStack(parkstack,n)==1) //栈满的情况

{

IN_Lqueue(parkqueue,car); //进入队列等待

printf(\"这辆车在门外便道上第%d个位置\\n\

printf(\"\\n\");

printf(\"请输入车辆信息\\n\");

}

else

{

Push_SeqStack(parkstack,car); //入栈

printf(\"这辆车在停车场内第%d个位置\\n\

printf(\"\\n\");

printf(\"请输入车辆信息\\n\");

}

}

if(car.AL=='D' ) //汽车离开的情况

{

t=POP_SeqStack(parkstack,car);//出栈

printf(\"这辆车停留时间为%d\\n\

printf(\"\\n\");

printf(\"请输入车辆信息\\n\");

if(ISEmpty_LQueue(parkqueue)==0) //队列不为空需要进栈

Push_SeqStack(parkstack,Out_LQueue(parkqueue) );

}

if(car.AL=='P'&&car.NO==0&&car.time==0 )//显示停车场的车数

{

printf(\"停车场的车数为%d\\n\

printf(\"\\n\");

printf(\"请输入车辆信息\\n\");

}

if(car.AL=='W'&&car.NO==0&&car.time==0 )//显示候车场的车数

{

printf(\"候车场的车数为%d\\n\

printf(\"\\n\");

printf(\"请输入车辆信息\\n\");

}

scanf(\"%c,%d,%d\

}

printf(\"输入结束\\n\");

printf(\"Current local time and date:%s\

return 1;

}

九、 实验收获和感想

通过这个实验模拟了简单的停车场管理系统，这个程序设计需要栈和队列的相关操作，所以在程序设计过程中逐渐熟悉了栈和队列的相关操作，由于像栈，队列这样，有判断栈空，栈满，入栈，出栈这样的操作，在编写程序时将相关操作写成子程序，然后直接在主程序中调用既方便又简洁，再次这个停车管理系统的逻辑性也比较强，直接编写程序很容易疏忽，所以先画出流程图，根据流程图判断需要的函数，根据流程图编写程序，如在车辆进入停车场时就需要先判断栈是否已满，这个时候编写判断栈满的子程序，栈满时车辆进入候车场，这个时候需要编写入队程序，若栈未满，这个时候编写入栈程序，根据流程图写一个大致的框架，之后可以再考虑其他问题，如显示停车场数量以及候车场数量的时候我就是最后写的，定义队列和栈时增加一个num，然后在每次入队时num++;这样将一个大问题化简成许多小问题，使程序的编写大大简化，在第一个实验的基础上做了一些改进确实时间节省了。在这个程序中还有一个问题，就是定义的结构体数组有些多，容易混乱，所以我选择每定义一个结构体都将其画出一个图，这样编写的时候就不至于太混乱。这个停车管理系统的设计过程，还是慢慢在适应模块化程序的编写，但有的程序还是喜欢写在一起，使得一个子程序会很长，这个问题希望在之后的问题再继续慢慢改进。