2. 停车场管理(栈和队列) [题目描述] 设停车场是一个可以停放n辆汽车的狭长通道,且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序,依次由北向南排列(大门在最南端,最先到达的第一辆车停放在车场的最北端),若车场内已停满n辆车,那么后来的车只能在门外的便道上等候,一旦停车场内有车开走,则排在便道上的第一辆车即可开入;当停车场内某辆车要离开时,在它之后进入的车辆必须先退出车场为它让路,待该辆车开出大门外,其他车辆再按原次序进入车场。试为停车场编制按上述要求进行管理的模拟程序。 以栈模拟停车场,以队列模拟车场外的便道。每一组输入数据包括三个数据项:汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为:若是车辆到达,则输出汽车在停车场内或便道上的停车位置;当车辆将要离去时,若车在停车场内,模拟输出汽车出入情况并输出汽车在停车场内停留的时间,若车在便道上,直接输出汽车在停车场内停留的时间:0。栈以顺序存储结构实现,队列以链表结构实现。 用c语言写
时间: 2024-04-04 13:31:34 浏览: 89
停车场管理--栈、队列和递归算法设计
以下是停车场管理的C语言实现代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 100
// 汽车信息结构体
typedef struct {
char id[10]; // 车牌号码
int arrive_time; // 到达时间
int park_time; // 停留时间
} Car;
// 栈结构体
typedef struct {
Car data[MAXSIZE]; // 栈中存储的汽车信息
int top; // 栈顶指针
} Stack;
// 队列结构体
typedef struct Node {
Car data; // 队列中存储的汽车信息
struct Node *next; // 指向下一个节点的指针
} Node, *QueuePtr;
typedef struct {
QueuePtr front; // 队头指针
QueuePtr rear; // 队尾指针
} Queue;
// 初始化栈
void InitStack(Stack *s) {
s->top = -1;
}
// 判断栈是否为空
int IsStackEmpty(Stack s) {
return s.top == -1;
}
// 判断栈是否已满
int IsStackFull(Stack s) {
return s.top == MAXSIZE - 1;
}
// 入栈
int PushStack(Stack *s, Car c) {
if (IsStackFull(*s)) {
return 0; // 栈已满,入栈失败
}
s->data[++s->top] = c;
return 1; // 入栈成功
}
// 出栈
int PopStack(Stack *s, Car *c) {
if (IsStackEmpty(*s)) {
return 0; // 栈已空,出栈失败
}
*c = s->data[s->top--];
return 1; // 出栈成功
}
// 获取栈顶元素
int GetTopStack(Stack s, Car *c) {
if (IsStackEmpty(s)) {
return 0; // 栈已空,获取栈顶元素失败
}
*c = s.data[s.top];
return 1; // 获取栈顶元素成功
}
// 初始化队列
void InitQueue(Queue *q) {
q->front = q->rear = (QueuePtr)malloc(sizeof(Node));
if (!q->front) {
exit(1); // 内存分配失败,退出程序
}
q->front->next = NULL;
}
// 判断队列是否为空
int IsQueueEmpty(Queue q) {
return q.front == q.rear;
}
// 入队
void EnQueue(Queue *q, Car c) {
QueuePtr p = (QueuePtr)malloc(sizeof(Node));
if (!p) {
exit(1); // 内存分配失败,退出程序
}
p->data = c;
p->next = NULL;
q->rear->next = p;
q->rear = p;
}
// 出队
int DeQueue(Queue *q, Car *c) {
if (IsQueueEmpty(*q)) {
return 0; // 队列已空,出队失败
}
QueuePtr p = q->front->next;
*c = p->data;
q->front->next = p->next;
if (q->rear == p) {
q->rear = q->front;
}
free(p);
return 1; // 出队成功
}
// 查找栈中指定车牌号码的汽车位置(从栈顶开始查找)
int SearchStack(Stack s, char *id) {
int i;
for (i = s.top; i >= 0; i--) {
if (strcmp(s.data[i].id, id) == 0) {
return s.top - i + 1; // 返回车辆在停车场内的位置
}
}
return -1; // 没有找到指定车牌号码的汽车
}
int main() {
Stack s; // 停车场
Queue q; // 便道
InitStack(&s);
InitQueue(&q);
int n; // 停车场可停放的汽车数量
printf("请输入停车场可停放的汽车数量:");
scanf("%d", &n);
while (1) {
int op, time;
Car c;
printf("请输入操作类型(1表示到达,2表示离去,0表示退出):");
scanf("%d", &op);
if (op == 0) {
break; // 退出程序
}
printf("请输入车牌号码和时间:");
scanf("%s %d", c.id, &time);
if (op == 1) { // 车辆到达
if (IsStackFull(s)) { // 停车场已满,加入便道等待
printf("停车场已满,加入便道等待\n");
c.arrive_time = time;
EnQueue(&q, c);
} else { // 停车场未满,直接停入停车场
printf("停车场未满,停入第%d个位置\n", PushStack(&s, c) + 1);
}
} else { // 车辆离去
int pos = SearchStack(s, c.id); // 查找车辆在停车场内的位置
if (pos != -1) { // 车辆在停车场内
while (s.top >= s.top - pos + 1) { // 将车辆之后的汽车全部出栈并进入便道
Car t;
PopStack(&s, &t);
t.park_time = time - t.arrive_time;
printf("车牌号码为%s的汽车离开停车场,停留时间为%d分钟\n", t.id, t.park_time);
if (!IsQueueEmpty(q)) { // 便道上有汽车等待,将其入栈
DeQueue(&q, &t);
t.arrive_time = time;
printf("便道上的车牌号码为%s的汽车进入停车场,停入第%d个位置\n", t.id, PushStack(&s, t) + 1);
}
}
} else { // 车辆在便道上
Queue tmp; // 临时队列,用于存储便道上的汽车
InitQueue(&tmp);
while (!IsQueueEmpty(q)) { // 将便道上的汽车全部出队并入临时队列
Car t;
DeQueue(&q, &t);
if (strcmp(t.id, c.id) == 0) { // 找到指定车牌号码的汽车
t.park_time = time - t.arrive_time;
printf("车牌号码为%s的汽车离开停车场,停留时间为%d分钟\n", t.id, t.park_time);
} else {
EnQueue(&tmp, t);
}
}
while (!IsQueueEmpty(tmp)) { // 将临时队列中的汽车重新加入便道
Car t;
DeQueue(&tmp, &t);
EnQueue(&q, t);
}
}
}
}
return 0;
}
```
注意,上述代码中使用了栈和队列两种数据结构来模拟停车场管理。其中,栈用于存储停在停车场内的汽车,队列用于存储在便道上等待进入停车场的汽车。在程序运行过程中,根据用户输入的操作类型,程序会进行相应的操作。如果是车辆到达,程序会根据停车场是否已满来决定是否将车辆停在停车场内或放在便道上等待;如果是车辆离去,程序会先在停车场中查找目标车辆,如果找到则将目标车辆之后的所有车辆全部出栈,并将其放入便道上等待;如果在停车场中没有找到目标车辆,则程序会在便道上查找目标车辆,将其出队并统计停留时间。无论是车辆到达还是离去,程序都会输出相应的信息。
阅读全文