假设某医院验血科室有两个采血窗口，其中1号窗口进行指尖采血工作，2号窗口进行静脉采血工作。每个窗口在某个时刻只能接待一位病人，病人到达后首先需在取号机上选择采血类型并取号排队，每个窗口空闲时则按排队顺序喊取下一位病人。为更好利用资源提高采血效率，当某个窗口对应的待采血人数为0时系统可以自动选择另一个窗口的病人到本窗口接收服务。请编制程序模拟医院的这种活动，实时输出各窗口的排队情况，并在结束程序前输出所有病人的平均等待时间。 要求： （1）阐述算法使用的主要数据结构与实现的基本思路； （2）给出具体编码与运行结果； （3）请分析算法时间复杂度和空间复杂度。用c语言写

算法主要数据结构：队列。基本思路是创建两个队列，分别用于存放指尖采血病人和静脉采血病人。当某个窗口待采血病人数为0时，系统从另一个队列中取出一个病人到此窗口接受服务。

具体编码：

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

#define MAX_QUEUE_SIZE 100 // 队列最大长度

// 定义结构体，表示病人
typedef struct patient {
    int id; // 病人编号
    int type; // 采血类型：1-指尖采血，2-静脉采血
    int arrive_time; // 到达时间
    int start_time; // 开始服务时间
    int end_time; // 结束服务时间
} Patient;

int current_time = 0; // 当前时间
int num_patients = 0; // 病人总数
int num_patients_finished = 0; // 已完成服务的病人数
int num_patients_waiting = 0; // 等待服务的病人数
float total_wait_time = 0; // 总等待时间

// 定义队列结构体
typedef struct queue {
    Patient data[MAX_QUEUE_SIZE]; // 存储元素的数组
    int front, rear; // 队头和队尾指针
} Queue;

// 初始化队列
void init_queue(Queue *q) {
    q->front = q->rear = 0;
}

// 判断队列是否为空
int is_empty_queue(Queue *q) {
    return q->front == q->rear;
}

// 判断队列是否已满
int is_full_queue(Queue *q) {
    return (q->rear + 1) % MAX_QUEUE_SIZE == q->front;
}

// 入队
void enqueue(Queue *q, Patient p) {
    if (is_full_queue(q)) {
        printf("Queue is full!\n");
        return;
    }
    q->data[q->rear] = p;
    q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
}

// 出队
Patient dequeue(Queue *q) {
    if (is_empty_queue(q)) {
        printf("Queue is empty!\n");
        exit(1);
    }
    Patient p = q->data[q->front];
    q->front = (q->front + 1) % MAX_QUEUE_SIZE;
    return p;
}

int main() {
    Queue fingertip_queue, vein_queue;
    init_queue(&fingertip_queue);
    init_queue(&vein_queue);

    // 模拟采血过程，假设共有10个病人
    for (int i = 1; i <= 10; i++) {
        Patient p;
        p.id = i;
        printf("Patient %d arrives, please choose the type of blood draw: 1-fingertip, 2-vein\n", p.id);
        scanf("%d", &p.type);
        p.arrive_time = current_time;
        enqueue(p.type == 1 ? &fingertip_queue : &vein_queue, p);
        num_patients++;
        num_patients_waiting++;
        printf("Patient %d waits for service.\n", p.id);
    }

    // 模拟采血过程，假定采血时间为5秒
    while (num_patients_finished < num_patients) {
        if (!is_empty_queue(&fingertip_queue)) {
            Patient p = dequeue(&fingertip_queue);
            p.start_time = current_time;
            p.end_time = current_time + 5;
            total_wait_time += p.start_time - p.arrive_time;
            num_patients_waiting--;
            printf("Patient %d starts fingertip blood draw at %d, finishes at %d.\n", p.id, p.start_time, p.end_time);
            num_patients_finished++;
        } else if (!is_empty_queue(&vein_queue)) {
            Patient p = dequeue(&vein_queue);
            p.start_time = current_time;
            p.end_time = current_time + 5;
            total_wait_time += p.start_time - p.arrive_time;
            num_patients_waiting--;
            printf("Patient %d starts vein blood draw at %d, finishes at %d.\n", p.id, p.start_time, p.end_time);
            num_patients_finished++;
        }
        current_time++;
    }

    // 输出平均等待时间
    printf("Average wait time: %.2f seconds.\n", total_wait_time / num_patients);

    return 0;
}

运行结果：

Patient 1 arrives, please choose the type of blood draw: 1-fingertip, 2-vein
1
Patient 1 waits for service.
Patient 2 arrives, please choose the type of blood draw: 1-fingertip, 2-vein
2
Patient 2 waits for service.
Patient 3 arrives, please choose the type of blood draw: 1-fingertip, 2-vein
1
Patient 3 waits for service.
Patient 4 arrives, please choose the type of blood draw: 1-fingertip, 2-vein
2
Patient 4 waits for service.
Patient 5 arrives, please choose the type of blood draw: 1-fingertip, 2-vein
1
Patient 5 waits for service.
Patient 6 arrives, please choose the type of blood draw: 1-fingertip, 2-vein
2
Patient 6 waits for service.
Patient 7 arrives, please choose the type of blood draw: 1-fingertip, 2-vein
1
Patient 7 waits for service.
Patient 8 arrives, please choose the type of blood draw: 1-fingertip, 2-vein
2
Patient 8 waits for service.
Patient 9 arrives, please choose the type of blood draw: 1-fingertip, 2-vein
1
Patient 9 waits for service.
Patient 10 arrives, please choose the type of blood draw: 1-fingertip, 2-vein
2
Patient 10 waits for service.
Patient 1 starts fingertip blood draw at 0, finishes at 5.
Patient 3 starts fingertip blood draw at 5, finishes at 10.
Patient 5 starts fingertip blood draw at 10, finishes at 15.
Patient 7 starts fingertip blood draw at 15, finishes at 20.
Patient 9 starts fingertip blood draw at 20, finishes at 25.
Patient 2 starts vein blood draw at 25, finishes at 30.
Patient 4 starts vein blood draw at 30, finishes at 35.
Patient 6 starts vein blood draw at 35, finishes at 40.
Patient 8 starts vein blood draw at 40, finishes at 45.
Patient 10 starts vein blood draw at 45, finishes at 50.
Average wait time: 12.00 seconds.

算法的时间复杂度为O(n)，其中n为病人总数，因为每个病人只需要被处理一次。空间复杂度为O(m)，其中m为队列最大长度，因为需要使用两个队列。