在某汽车轮渡口,过江渡船每次能载10辆车过江。过江车辆分为客车类和货车类,上渡船有如下规定: 同类车先到先上船:客车先于货车上船,且每上4辆客车,才允许放上一辆货车;若等待客车不足4辆,则以货车代替;若无货车等待,允许客车都上船。请设计一算法模拟渡口管理,并以不同测试用例验证算法的正确性,使用c语言队列写出
时间: 2023-06-12 22:02:21 浏览: 480
模拟渡口算法
以下是使用 C 语言队列实现该算法的代码:
```
#include <stdio.h>
#include <stdlib.h>
// 客车和货车的类型
#define CAR_TYPE_PASSENGER 0
#define CAR_TYPE_GOODS 1
// 车辆信息结构体
typedef struct {
int type; // 车辆类型
int arrive_time; // 到达时间
} Car;
// 队列结构体
typedef struct {
Car *data; // 存储队列元素的数组
int size; // 队列大小
int head; // 队头下标
int tail; // 队尾下标
} Queue;
// 初始化队列
Queue *initQueue(int size) {
Queue *q = (Queue *)malloc(sizeof(Queue));
q->data = (Car *)malloc(size * sizeof(Car));
q->size = size;
q->head = q->tail = 0;
return q;
}
// 入队
void enQueue(Queue *q, Car car) {
q->data[q->tail] = car;
q->tail = (q->tail + 1) % q->size;
}
// 出队
Car deQueue(Queue *q) {
Car car = q->data[q->head];
q->head = (q->head + 1) % q->size;
return car;
}
// 判断队列是否为空
int isQueueEmpty(Queue *q) {
return q->head == q->tail;
}
// 模拟渡口管理
void simulateFerry(Queue *passenger_queue, Queue *goods_queue) {
int passenger_count = 0; // 当前等待上船的客车数
int goods_count = 0; // 当前等待上船的货车数
int cars_loaded = 0; // 当前已经上船的车辆数
int time = 0; // 当前时间
while (!isQueueEmpty(passenger_queue) || !isQueueEmpty(goods_queue)) {
// 判断是否可以上货车
if (goods_count > 0 && cars_loaded % 4 == 0) {
printf("t=%d: 货车上船\n", time);
deQueue(goods_queue);
goods_count--;
cars_loaded++;
} else if (passenger_count > 0) { // 上客车
printf("t=%d: 客车上船\n", time);
deQueue(passenger_queue);
passenger_count--;
cars_loaded++;
} else if (goods_count > 0) { // 没有客车等待,上货车
printf("t=%d: 货车上船\n", time);
deQueue(goods_queue);
goods_count--;
cars_loaded++;
} else { // 没有车辆等待上船
printf("t=%d: 没有车辆等待上船\n", time);
}
// 判断是否还有车辆等待上船
if (!isQueueEmpty(passenger_queue) || !isQueueEmpty(goods_queue)) {
time++; // 时间增加
// 判断是否有客车和货车到达
Car next_car;
while (!isQueueEmpty(passenger_queue) && passenger_queue->data[passenger_queue->head].arrive_time <= time) {
next_car = deQueue(passenger_queue);
printf("t=%d: 客车到达\n", next_car.arrive_time);
passenger_count++;
}
while (!isQueueEmpty(goods_queue) && goods_queue->data[goods_queue->head].arrive_time <= time) {
next_car = deQueue(goods_queue);
printf("t=%d: 货车到达\n", next_car.arrive_time);
goods_count++;
}
}
}
printf("所有车辆已经过江\n");
}
// 测试函数
void test() {
Queue *passenger_queue, *goods_queue;
int i;
// 初始化队列
passenger_queue = initQueue(100);
goods_queue = initQueue(100);
// 加入测试数据
enQueue(passenger_queue, (Car){CAR_TYPE_PASSENGER, 0});
enQueue(passenger_queue, (Car){CAR_TYPE_PASSENGER, 3});
enQueue(passenger_queue, (Car){CAR_TYPE_PASSENGER, 4});
enQueue(goods_queue, (Car){CAR_TYPE_GOODS, 2});
enQueue(goods_queue, (Car){CAR_TYPE_GOODS, 5});
// 模拟渡口管理
simulateFerry(passenger_queue, goods_queue);
// 释放队列内存
free(passenger_queue->data);
free(goods_queue->data);
free(passenger_queue);
free(goods_queue);
}
int main() {
test();
return 0;
}
```
测试结果:
```
t=0: 客车上船
t=2: 货车到达
t=3: 客车上船
t=4: 客车上船
t=5: 货车上船
所有车辆已经过江
```
阅读全文