C语言写一份电梯调度算法

以下是一份简单的电梯调度算法的实现，对于多电梯的情况，可以扩展该算法来实现：

#include <stdio.h>
#include <stdlib.h>

#define MAX_FLOORS 20
#define MAX_CUSTOMERS 10

typedef struct {
    int start_floor;
    int target_floor;
    int direction; // 1: Up, -1: Down
} Customer;

typedef struct {
    int queue[MAX_CUSTOMERS];
    int head;
    int tail;
    int count;
} Queue;

// Initialize the queue
void init(Queue *q) {
    q->head = 0;
    q->tail = -1;
    q->count = 0;
}

// Add a new customer to the queue
void enqueue(Queue *q, int customer) {
    if (q->count == MAX_CUSTOMERS) {
        printf("The queue is already full.\n");
        return;
    }
    q->tail = (q->tail + 1) % MAX_CUSTOMERS;
    q->queue[q->tail] = customer;
    q->count++;
}

// Remove the first customer from the queue
void dequeue(Queue *q) {
    if (q->count == 0) {
        printf("The queue is already empty.\n");
        return;
    }
    q->head = (q->head + 1) % MAX_CUSTOMERS;
    q->count--;
}

// Return the first customer in the queue
int front(Queue *q) {
    if (q->count == 0) {
        printf("The queue is empty.\n");
        return -1;
    }
    return q->queue[q->head];
}

// Return the empty slots in the queue
int slots(Queue *q) {
    return MAX_CUSTOMERS - q->count;
}

// Return the number of customers in the queue
int size(Queue *q) {
    return q->count;
}

// Check whether the direction of the elevator is compatible with the direction of the customer
int is_direction_compatible(int elevator_direction, int customer_direction) {
    return ((elevator_direction == 1 && customer_direction == 1) || (elevator_direction == -1 && customer_direction == -1));
}

// Check whether the elevator should stop on the current floor
int should_stop_here(int current_floor, int elevator_direction, Queue *up_queue, Queue *down_queue) {
    int stop = 0;
    if (elevator_direction == 1 && size(up_queue) > 0) {
        if (front(up_queue) == current_floor) {
            stop = 1;
        } else if (is_direction_compatible(elevator_direction, 1) && front(up_queue) > current_floor) {
            stop = 1;
        }
    } else if (elevator_direction == -1 && size(down_queue) > 0) {
        if (front(down_queue) == current_floor) {
            stop = 1;
        } else if (is_direction_compatible(elevator_direction, -1) && front(down_queue) < current_floor) {
            stop = 1;
        }
    }
    return stop;
}

// Pick up the customers that want to go up from the current floor
int pick_up_up(Queue *up_queue, int current_floor, int max_floors, Queue *elevator_queue) {
    int picked_up = 0;
    int i, customer;
    for (i = current_floor; i <= max_floors; i++) {
        if (size(up_queue) == 0) {
            break;
        }
        customer = front(up_queue);
        if (customer == i) {
            enqueue(elevator_queue, customer);
            dequeue(up_queue);
            picked_up++;
        }
    }
    return picked_up;
}

// Pick up the customers that want to go down from the current floor
int pick_up_down(Queue *down_queue, int current_floor, int min_floors, Queue *elevator_queue) {
    int picked_up = 0;
    int i, customer;
    for (i = current_floor; i >= min_floors; i--) {
        if (size(down_queue) == 0) {
            break;
        }
        customer = front(down_queue);
        if (customer == i) {
            enqueue(elevator_queue, customer);
            dequeue(down_queue);
            picked_up++;
        }
    }
    return picked_up;
}

// Drop off the customers that have reached their target floor
int drop_off(Queue *elevator_queue, int current_floor) {
    int dropped_off = 0;
    int i, customer;
    for (i = 0; i < size(elevator_queue); i++) {
        customer = elevator_queue->queue[(elevator_queue->head + i) % MAX_CUSTOMERS];
        if (customer == current_floor) {
            dequeue(elevator_queue);
            dropped_off++;
        }
    }
    return dropped_off;
}

// Print the state of the elevator and the queues
void print_state(int current_floor, int elevator_direction, Queue *up_queue, Queue *down_queue, Queue *elevator_queue) {
    int i;
    printf("Current floor: %d\n", current_floor);
    printf("Elevator direction: %d\n", elevator_direction);
    printf("Up queue: ");
    for (i = 0; i < size(up_queue); i++) {
        printf("%d ", up_queue->queue[(up_queue->head + i) % MAX_CUSTOMERS]);
    }
    printf("\n");
    printf("Down queue: ");
    for (i = 0; i < size(down_queue); i++) {
        printf("%d ", down_queue->queue[(down_queue->head + i) % MAX_CUSTOMERS]);
    }
    printf("\n");
    printf("Elevator queue: ");
    for (i = 0; i < size(elevator_queue); i++) {
        printf("%d ", elevator_queue->queue[(elevator_queue->head + i) % MAX_CUSTOMERS]);
    }
    printf("\n");
}

// Simulate the elevator behavior
void simulate_elevator(Queue *up_queue, Queue *down_queue) {
    Queue elevator_queue;
    init(&elevator_queue);

    int current_floor = 1;
    int elevator_direction = 1; // 1: Up, -1: Down
    int waiting_time = 0;
    int max_floors = MAX_FLOORS;
    int min_floors = 1;

    while (1) {
        int should_stop = should_stop_here(current_floor, elevator_direction, up_queue, down_queue);
        if (should_stop) {
            int picked_up = 0, dropped_off = 0;
            if (elevator_direction == 1) {
                picked_up = pick_up_up(up_queue, current_floor, max_floors, &elevator_queue);
            } else if (elevator_direction == -1) {
                picked_up = pick_up_down(down_queue, current_floor, min_floors, &elevator_queue);
            }
            dropped_off = drop_off(&elevator_queue, current_floor);
            if (picked_up > 0 || dropped_off > 0) {
                printf("Waiting time: %d\n", waiting_time);
                print_state(current_floor, elevator_direction, up_queue, down_queue, &elevator_queue);
                printf("Picked up: %d\n", picked_up);
                printf("Dropped off: %d\n", dropped_off);
                waiting_time = 0;
            }
        }

        current_floor += elevator_direction;
        waiting_time++;

        if (current_floor == max_floors) {
            elevator_direction = -1;
        } else if (current_floor == min_floors) {
            elevator_direction = 1;
        }

        if (size(up_queue) == 0 && size(down_queue) == 0 && size(&elevator_queue) == 0) {
            printf("End of the simulation.\n");
            break;
        }
    }
}

int main() {
    Queue up_queue, down_queue;
    init(&up_queue);
    init(&down_queue);

    // Add some customers to the queues
    Customer customers[MAX_CUSTOMERS] = {
        { 1, 11, 1 }, { 2, 5, 1 }, { 3, 7, 1 }, { 4, 14, 1 },
        { 8, 2, -1 }, { 12, 1, -1 }, { 15, 3, -1 }
    };
    int i;
    for (i = 0; i < MAX_CUSTOMERS; i++) {
        if (customers[i].direction == 1) {
            enqueue(&up_queue, i);
        } else if (customers[i].direction == -1) {
            enqueue(&down_queue, i);
        }
    }

    simulate_elevator(&up_queue, &down_queue);

    return 0;
}

该算法模拟了一个单电梯的情况，包括了上下行队列和电梯队列，并且处理了电梯停在楼层和乘客上下车的逻辑。在模拟过程中，会输出当前状态和等待时间，并且在电梯有人上下车时输出相关信息。