停车场问题

实验内容

1.问题描述：

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

2.基本要求：

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

(2)菜单操作

测试数据

设n=2，输入数据为(“A”,1,5),(“A”,2,10),(“D”,1,15),(“A” ,3,20),(“D”,2,35),("E”,0,0),(“A”,1,5),其中 :“A”表示达到(Arrival);“D”表示离去(Departure);“E”表示输入结束(End)。

1. 实现提示:

需另设一个栈，临时停放为要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包括两个数据项:汽车的牌照号码和进入停车场的时刻。

实验原理

1.车辆停入停车场的流程：

首先判断停车场的车位是否停满。两种情况：(1)停满时此时后来的车辆只能停在走道上(2)未停满时后来的车辆继续入栈。

2.车辆出站的思想。两种情况：(1)车辆在栈顶时，此时直接出栈而用不到辅助栈(2)车辆不在车顶时排在前面的车辆必须让位，此时它才能出栈，算法思想是首先根据输入的车牌号进行在栈中搜索，返还一个角标，根据角标来，找到出栈的车辆，这时前面的车辆入辅助栈，当循环的目标车辆时，这时不需要入辅助栈，直接出栈即可.

#include <stdio.h>
#include <stdlib.h> //用malloc时要声明，引入stdlib.h以使用malloc和realloc
#include <string.h> //字符串处理库，例如字符串的复制、连接、比较等 #define MAX_CARS 2 // 停车场最大容量
#define MAX_PLATE_LEN 10 // 汽车牌照最大长度// 定义汽车结构体
typedef struct {char plate[MAX_PLATE_LEN]; // 牌照号码int arrival_time; // 到达时间
} Car;// 顺序栈实现
typedef struct {Car cars[MAX_CARS]; // 停车场存放的汽车数组int top; // 栈顶指针
} Stack;// 链表节点
typedef struct Node {Car car; // 汽车struct Node* next; // 指向下一个节点
} Node;// 链表队列实现
typedef struct {Node* front; // 队首指针Node* rear; // 队尾指针
} Queue;// 初始化栈
void initStack(Stack* stack) {stack->top = -1; // 栈顶指针初始化为-1，表示栈为空
}// 判断栈是否满
int isStackFull(Stack* stack) {return stack->top == MAX_CARS - 1; // 栈满的条件
}// 判断栈是否空
int isStackEmpty(Stack* stack) {return stack->top == -1; // 栈空的条件
}// 入栈操作
void push(Stack* stack, Car car) {if (!isStackFull(stack)) { // 先检查栈是否满stack->cars[++stack->top] = car; // 将汽车入栈并更新栈顶指针}
}// 出栈操作
Car pop(Stack* stack) {if (!isStackEmpty(stack)) { // 先检查栈是否空return stack->cars[stack->top--]; // 返回栈顶汽车并更新栈顶指针}Car emptyCar = {"", 0}; // 返回一个空的汽车结构体，表示出栈失败return emptyCar;
}// 初始化队列
void initQueue(Queue* queue) {queue->front = queue->rear = NULL; // 队列前后指针初始化为NULL，表示队列为空
}// 判断队列是否空
int isQueueEmpty(Queue* queue) {return queue->front == NULL; // 队列为空的条件
}// 入队操作
void enqueue(Queue* queue, Car car) {Node* newNode = (Node*)malloc(sizeof(Node)); // 创建新节点newNode->car = car; // 设置节点中的汽车信息newNode->next = NULL; // 新节点的next指针初始化为NULLif (isQueueEmpty(queue)) { // 如果队列为空queue->front = queue->rear = newNode; // 新节点既是队首又是队尾} else {queue->rear->next = newNode; // 将新节点添加到队尾queue->rear = newNode; // 更新队尾指针}
}// 出队操作
Car dequeue(Queue* queue) {if (!isQueueEmpty(queue)) { // 先检查队列是否空Node* temp = queue->front; // 暂存队首节点Car car = temp->car; // 获取队首的汽车信息queue->front = queue->front->next; // 更新队首指针free(temp); // 释放旧的队首节点if (queue->front == NULL) { // 如果队列变为空queue->rear = NULL; // 更新队尾指针}return car; // 返回出队的汽车信息}Car emptyCar = {"", 0}; // 返回一个空的汽车结构体，表示出队失败return emptyCar;
}// 查找并返回车辆在栈中的索引
int findCarInStack(Stack* stack, char* plate) {for (int i = stack->top; i >= 0; i--) { // 从栈顶向下查找if (strcmp(stack->cars[i].plate, plate) == 0) { // 找到匹配的车牌return i; // 返回车辆的索引}}return -1; // 未找到，返回-1
}// 主程序
int main() {Stack parking_lot; // 定义停车场栈Queue waiting_area; // 定义便道队列initStack(&parking_lot); // 初始化停车场initQueue(&waiting_area); // 初始化便道char command; // 命令变量Car car; // 当前处理的汽车int current_time; // 当前时间printf("请输入命令（A/D/E）：\n");while (1) {scanf(" %c", &command); // 读取命令if (command == 'E') { // 如果命令是结束break; // 退出循环}scanf("%s %d", car.plate, &current_time); // 读取车牌和时间if (command == 'A') { // 如果是到达命令if (!isStackFull(&parking_lot)) { // 检查停车场是否已满car.arrival_time = current_time; // 记录到达时间push(&parking_lot, car); // 入栈printf("车辆 %s 停在停车场位置 %d\n", car.plate, parking_lot.top + 1);} else { // 停车场已满car.arrival_time = current_time; // 记录到达时间enqueue(&waiting_area, car); // 入队printf("车辆 %s 停在便道\n", car.plate);}} else if (command == 'D') { // 如果是离去命令int index = findCarInStack(&parking_lot, car.plate); // 查找车辆在栈中的位置if (index != -1) { // 如果找到// 将需要让路的车辆放入临时栈Stack temp_stack; // 辅助栈initStack(&temp_stack); // 初始化辅助栈for (int i = parking_lot.top; i > index; i--) { // 将需要让路的车辆入辅助栈push(&temp_stack, pop(&parking_lot)); // 从停车场出栈并入辅助栈}// 出栈目标车辆Car departed_car = pop(&parking_lot); // 目标车辆出栈int duration = current_time - departed_car.arrival_time; // 计算停留时间printf("车辆 %s 停留时间 %d，需支付费用 %d\n", departed_car.plate, duration, duration);// 将临时栈中的车辆恢复到停车场while (!isStackEmpty(&temp_stack)) {push(&parking_lot, pop(&temp_stack)); // 将辅助栈的车辆放回停车场}// 检查便道是否有车辆可以进入if (!isQueueEmpty(&waiting_area)) {Car next_car = dequeue(&waiting_area); // 从便道出队next_car.arrival_time = current_time; // 更新到达时间push(&parking_lot, next_car); // 入栈停车场printf("车辆 %s 从便道进入停车场，停在位置 %d\n", next_car.plate, parking_lot.top + 1);}} else {printf("车辆 %s 不在停车场内\n", car.plate); // 未找到车辆}}}return 0; // 程序结束
}