数据结构——停车场管理问题

1、问题描述

1、题目
设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若停车场已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在其之后开入的车辆必须先退出停车场让路，待该辆车开出大门外，其他车辆再按原次序进入停车场，每辆停放在停车场的车在其离开停车场时必须按其停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。
2、设计要求
以栈模拟停车场，以队列模拟停车场外的便道，按照从终端读入的输入数据的方式进行模拟管理。输入1，表示车辆到达；输入2，表示车辆离开；输入3，表示显示出停车场内及便道上的停车情况；输入4，表示退出系统。车辆到达操作，需输入汽车牌照号码及到达时间；车辆离开操作，需输入汽车在停车场的位置及离开时刻，且应输出汽车在停车场内停留的时间和应缴纳的费用（在便道上停留的时间不收费）。

2、逐步分析

1）涉及操作

①基础操作

1. 初始化
2. 判断栈/队列为空
3. 判断栈/队列为满
4. 计算栈/队列长度
5. 入栈/队列
6. 出栈/队列
7. 栈/队列打印

②要求操作

1. 车辆到达
2. 车辆离开

2）代码实现

1、结构体定义
①车辆信息

typedef struct Car
{int CarNo;//车牌号int CarTime;//车进入时间
}Car;

②顺序栈

typedef struct SqStack
{Car* data;//车辆信息int top;//栈顶int size;//长度
}SqStack;

③循环队列

typedef struct SqQueue
{Car* data;//车辆信息int top;//队头int tail;//队尾int size;//长度                                                                                                                       
}SqQueue;

2、基础操作
①初始化
栈：

SqStack* InitStack()
{SqStack* s = (SqStack*)malloc(sizeof(SqStack));s->data = (Car*)malloc(sizeof(Car) * MAXSIZE_St);if (s->data == NULL || s->data == NULL){return NULL;}s->size = 0;s->top = 0;//表示栈为空return s;
}

队列：

SqQueue* InitQueue()
{SqQueue* q = malloc(sizeof(SqQueue));q->data = (Car*)malloc(sizeof(Car) * MAXSIZE_Qu);if (!q || !(q->data)){return NULL;}//初始头指针和尾指针指向0索引q->top = q->tail = 0;return q;
}

②为空判断
栈：

int StackEmpty(SqStack* s)
{if (s->top == 0)return 1;//为空elsereturn 0;//不为空
}

队列：

int QueueEmpty(SqQueue* q)
{if (q->top == q->tail){return 1;//为空}return 0;//不为空
}

③为满判断
栈：

int StackFull(SqStack* s)
{if (s->size != MAXSIZE_St)return 0;//未满elsereturn 1;//已满
}

队列：

int QueueFull(SqQueue* q)
{return ((q->tail + 1) % MAXSIZE_Qu == q->top) ? 1 : 0;
}

④长度计算
栈：

int StackLength(SqStack* s)
{return s->size;
}

队列：

int QueueLength(SqQueue* q)
{return (q->tail - q->top + MAXSIZE_Qu) % MAXSIZE_Qu;
}

⑤入栈/队列
栈：

void Push(SqStack* s, int n, int t1)
{s->data[s->top].CarNo = n;s->data[s->top].CarTime = t1;s->top++;s->size++;
}

队列：

void EnQueue(SqQueue* q, int n, int t1)
{if (QueueFull(q)){return;}q->data[q->tail].CarNo = n;q->data[q->tail].CarTime = t1;//入队成功后,尾指针指向下一个位置q->tail = (q->tail + 1) % MAXSIZE_Qu;
}

⑥出栈/队列
栈：

void Pop(SqStack* s)
{if (StackEmpty(s)){printf("停车场为空\n");return;}s->top--;s->size--;
}

队列：

void DeQueue(SqQueue* q)
{if (QueueEmpty(q)){return;//队列为空}//出队成功后,头指针指向下一个位置q->top = (q->top + 1) % MAXSIZE_Qu;
}

⑦打印
栈：

void DispStack(SqStack* s)
{//对栈是否为空进行判断if (StackEmpty(s)){printf("停车场中没有车辆\n");return;}//循环打印停车场中的元素int i = 0;printf("停车场中共%d辆车，还有%d个空位\n", StackLength(s), MAXSIZE_St -StackLength(s));printf("车牌号\t进场时间\n");//size-1是因为在入栈时size最后会自增指向空位置for (i = s->size - 1; i >= 0; i--){printf("%-4d\t%-2d\n", s->data[i].CarNo, s->data[i].CarTime);}
}

队列：

void DispQueue(SqQueue* q)
{if (QueueEmpty(q)){printf("便道上没有车辆\n");return;//队列为空}//循环打印便道(队列Q)中的元素int i = 0;printf("便道中共%d辆车\n", StackLength(q));printf("便道中的车辆: \n");for (i = 0; i < QueueLength(q); i++){//出队后头指针会向后走,所以头指针决定了元素的索引printf("车牌号   %d\n", q->data[i + q->top].CarNo);}
}

3、要求操作
①车辆到达

void Parking_Arrive(SqStack* s1, SqQueue* q)
{int n = 0;	//车号int t1 = 0;	//车的到达时间if (!StackFull(s1)){//停车场S1未满时printf("车号  到达时间: ");scanf("%d %d", &n, &t1);Push(s1, n, t1);printf("所在停车场位置: %d\n", s1->size);}else{//停车场S1已满时printf("车号  到达时间: ");scanf("%d %d", &n, &t1);EnQueue(q, n, t1);printf("所在便道位置: %d\n", (q->tail));}return;
}

②车辆离开

void Parking_Leave(SqStack* s1, SqStack* s2, SqQueue* q)
{int i = 0;int n = 0;	//车号int t2 = 0; //车的离开时间int index = -1;	//对应车号的索引int count = 0;	//出栈入栈次数printf("车号  离开时间: ");scanf("%d %d", &n, &t2);//找到要离开的车,记录其索引for (i = s1->size - 1; i >= 0; i--){if (n == s1->data[i].CarNo){index = i;break;}}if (index == -1){printf("无对应车号的车辆!\n");return;}//说明离开的车所花停车费用int price = (t2 - s1->data[index].CarTime) * Parking_price;printf("该汽车的停车费用为: %d.\n", price);//将需要离开的车其后面的车移动到栈S2中for (i = s1->size - 1; i > index; i--){//将对应元素入栈到S2中后,再从S1中出栈Push(s2, s1->data[i].CarNo, s1->data[i].CarTime);Pop(s1);//每有一辆车进入S2则count加一count++;}//将离开的车(目前处于栈顶)出栈Pop(s1);//先将暂存S2中的车入栈到栈S1中(S2有车的情况下)for (i = count - 1; i >= 0; i--){//S2中的车入栈到S1中,再在S2中进行出栈Push(s1, s2->data[i].CarNo, s2->data[i].CarTime);Pop(s2);}//如果栈S1未满,则将便道Q的车入栈到S1中if (!StackFull(s1) && !QueueEmpty(q)){for (i = 0; i < MAXSIZE_St - s1->size; i++){//队列Q中的车入栈到S1中,再在Q中进行出队Push(s1, q->data[i + q->top].CarNo, q->data[i + q->top].CarTime);DeQueue(q);}}return;
}

4、主函数

int main()
{//初始化两个停车场栈（S1和S2）和一个便道队列（Q）SqStack* S1 = InitStack();SqStack* S2 = InitStack();SqQueue* Q = InitQueue();int select = 0;	do {printf("请输入指令(1:车辆到达 2:车辆离开 3:停车场、便道信息 0:退出系统): ");scanf("%d", &select);switch (select){case 1:Parking_Arrive(S1, Q);break;case 2:Parking_Leave(S1, S2, Q);break;case 3:DispStack(S1);DispQueue(Q);break;case 0:printf("已退出系统!\n");break;default:printf("请重新输入\n");getchar();}} while (select);return 0;
}

3、代码整合

#define _CRT_SECURE_NO_WARNINGS
#include<stdlib.h>
#include<stdio.h>#define MAXSIZE_St 3//栈最大容量
#define MAXSIZE_Qu 100//队列最大容量
#define Parking_price 5	//停车费5/h//车辆信息
typedef struct Car
{int CarNo;//车牌号int CarTime;//车进入时间
}Car;//顺序栈(停车场和车辆离开时暂时需要进入的区域)
typedef struct SqStack
{Car* data;//车辆信息int top;//栈顶int size;//长度
}SqStack;//循环队列(便道)
typedef struct SqQueue
{Car* data;//车辆信息int top;//队头int tail;//队尾int size;//长度                                                                                                                       
}SqQueue;//初始化栈
SqStack* InitStack()
{SqStack* s = (SqStack*)malloc(sizeof(SqStack));s->data = (Car*)malloc(sizeof(Car) * MAXSIZE_St);if (s->data == NULL || s->data == NULL){return NULL;}s->size = 0;s->top = 0;//表示栈为空return s;
}//检查栈是否为空，即停车场是否无车。
int StackEmpty(SqStack* s)
{if (s->top == 0)return 1;//为空elsereturn 0;//不为空
}//检查栈是否已满，即停车场是否已满。
int StackFull(SqStack* s)
{if (s->size != MAXSIZE_St)return 0;//未满elsereturn 1;//已满
}//计算栈的长度，即停车场内车辆数量。
int StackLength(SqStack* s)
{return s->size;
}//将新车辆加入到栈（停车场）中。
void Push(SqStack* s, int n, int t1)
{s->data[s->top].CarNo = n;s->data[s->top].CarTime = t1;s->top++;s->size++;
}//从栈中移除车辆。
void Pop(SqStack* s)
{if (StackEmpty(s)){printf("停车场为空\n");return;}s->top--;s->size--;
}//显示栈中的所有车辆信息。
void DispStack(SqStack* s)
{//对栈是否为空进行判断if (StackEmpty(s)){printf("停车场中没有车辆\n");return;}//循环打印停车场中的元素int i = 0;printf("停车场中共%d辆车，还有%d个空位\n", StackLength(s), MAXSIZE_St -StackLength(s));printf("车牌号\t进场时间\n");//size-1是因为在入栈时size最后会自增指向空位置for (i = s->size - 1; i >= 0; i--){printf("%-4d\t%-2d\n", s->data[i].CarNo, s->data[i].CarTime);}
}//初始化队列
SqQueue* InitQueue()
{SqQueue* q = malloc(sizeof(SqQueue));q->data = (Car*)malloc(sizeof(Car) * MAXSIZE_Qu);if (!q || !(q->data)){return NULL;}//初始头指针和尾指针指向0索引q->top = q->tail = 0;return q;
}//检查队列是否为空，即便道是否无车。
int QueueEmpty(SqQueue* q)
{if (q->top == q->tail){return 1;//为空}return 0;//不为空
}//检查队列是否已满，即便道是否已满。
int QueueFull(SqQueue* q)
{return ((q->tail + 1) % MAXSIZE_Qu == q->top) ? 1 : 0;
}int QueueLength(SqQueue* q)
{return (q->tail - q->top + MAXSIZE_Qu) % MAXSIZE_Qu;
}//将新车辆加入到队列中。
void EnQueue(SqQueue* q, int n, int t1)
{if (QueueFull(q)){return;}q->data[q->tail].CarNo = n;q->data[q->tail].CarTime = t1;//入队成功后,尾指针指向下一个位置q->tail = (q->tail + 1) % MAXSIZE_Qu;
}//从队列中移除车辆。
void DeQueue(SqQueue* q)
{if (QueueEmpty(q)){return;//队列为空}//出队成功后,头指针指向下一个位置q->top = (q->top + 1) % MAXSIZE_Qu;
}//显示队列中的所有车辆信息。
void DispQueue(SqQueue* q)
{if (QueueEmpty(q)){printf("便道上没有车辆\n");return;//队列为空}//循环打印便道(队列Q)中的元素int i = 0;printf("便道中共%d辆车\n", StackLength(q));printf("便道中的车辆: \n");for (i = 0; i < QueueLength(q); i++){//出队后头指针会向后走,所以头指针决定了元素的索引printf("车牌号   %d\n", q->data[i + q->top].CarNo);}
}void Parking_Arrive(SqStack* s1, SqQueue* q)
{int n = 0;	//车号int t1 = 0;	//车的到达时间if (!StackFull(s1)){//停车场S1未满时printf("车号  到达时间: ");scanf("%d %d", &n, &t1);Push(s1, n, t1);printf("所在停车场位置: %d\n", s1->size);}else{//停车场S1已满时printf("车号  到达时间: ");scanf("%d %d", &n, &t1);EnQueue(q, n, t1);printf("所在便道位置: %d\n", (q->tail));}return;
}void Parking_Leave(SqStack* s1, SqStack* s2, SqQueue* q)
{int i = 0;int n = 0;	//车号int t2 = 0; //车的离开时间int index = -1;	//对应车号的索引int count = 0;	//出栈入栈次数printf("车号  离开时间: ");scanf("%d %d", &n, &t2);//找到要离开的车,记录其索引for (i = s1->size - 1; i >= 0; i--){if (n == s1->data[i].CarNo){index = i;break;}}if (index == -1){printf("无对应车号的车辆!\n");return;}//说明离开的车所花停车费用int price = (t2 - s1->data[index].CarTime) * Parking_price;printf("该汽车的停车费用为: %d.\n", price);//将需要离开的车其后面的车移动到栈S2中for (i = s1->size - 1; i > index; i--){//将对应元素入栈到S2中后,再从S1中出栈Push(s2, s1->data[i].CarNo, s1->data[i].CarTime);Pop(s1);//每有一辆车进入S2则count加一count++;}//将离开的车(目前处于栈顶)出栈Pop(s1);//先将暂存S2中的车入栈到栈S1中(S2有车的情况下)for (i = count - 1; i >= 0; i--){//S2中的车入栈到S1中,再在S2中进行出栈Push(s1, s2->data[i].CarNo, s2->data[i].CarTime);Pop(s2);}//如果栈S1未满,则将便道Q的车入栈到S1中if (!StackFull(s1) && !QueueEmpty(q)){for (i = 0; i < MAXSIZE_St - s1->size; i++){//队列Q中的车入栈到S1中,再在Q中进行出队Push(s1, q->data[i + q->top].CarNo, q->data[i + q->top].CarTime);DeQueue(q);}}return;
}int main()
{//初始化两个停车场栈（S1和S2）和一个便道队列（Q）SqStack* S1 = InitStack();SqStack* S2 = InitStack();SqQueue* Q = InitQueue();int select = 0;	do {printf("请输入指令(1:车辆到达 2:车辆离开 3:停车场、便道信息 0:退出系统): ");scanf("%d", &select);switch (select){case 1:Parking_Arrive(S1, Q);break;case 2:Parking_Leave(S1, S2, Q);break;case 3:DispStack(S1);DispQueue(Q);break;case 0:printf("已退出系统!\n");break;default:printf("请重新输入\n");getchar();}} while (select);return 0;
}