面试题：C语言链式队列优化

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

// 定义数据项结构体
typedef struct DataItem {
    int data;
    struct DataItem *next;
} DataItem;

// 定义队列节点结构体
typedef struct QueueNode {
    DataItem *dataHead;
    struct QueueNode *next;
} QueueNode;

// 定义链式队列结构体
typedef struct {
    QueueNode *front;
    QueueNode *rear;
} LinkedQueue;

// 创建新的数据项
DataItem* createDataItem(int value) {
    DataItem *newItem = (DataItem*)malloc(sizeof(DataItem));
    newItem->data = value;
    newItem->next = NULL;
    return newItem;
}

// 创建新的队列节点
QueueNode* createQueueNode() {
    QueueNode *newNode = (QueueNode*)malloc(sizeof(QueueNode));
    newNode->dataHead = NULL;
    newNode->next = NULL;
    return newNode;
}

// 初始化链式队列
void initQueue(LinkedQueue *queue) {
    queue->front = NULL;
    queue->rear = NULL;
}

// 判断队列是否为空
int isQueueEmpty(LinkedQueue *queue) {
    return queue->front == NULL;
}

// 入队操作
void enqueue(LinkedQueue *queue, int value) {
    if (isQueueEmpty(queue)) {
        queue->front = createQueueNode();
        queue->rear = queue->front;
    } else if (queue->rear->dataHead == NULL) {
        queue->rear->dataHead = createDataItem(value);
    } else {
        DataItem *current = queue->rear->dataHead;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = createDataItem(value);
    }

    // 检查是否需要创建新的队列节点
    if (queue->rear->dataHead != NULL && queue->rear->dataHead->next != NULL) {
        queue->rear->next = createQueueNode();
        queue->rear = queue->rear->next;
    }
}

// 出队操作
int dequeue(LinkedQueue *queue) {
    if (isQueueEmpty(queue)) {
        printf("Queue is empty.\n");
        return -1; // 返回一个特殊值表示错误
    }
    int value = queue->front->dataHead->data;
    DataItem *toDelete = queue->front->dataHead;
    queue->front->dataHead = queue->front->dataHead->next;
    free(toDelete);

    // 检查是否需要删除当前队列节点
    if (queue->front->dataHead == NULL) {
        QueueNode *toDeleteNode = queue->front;
        queue->front = queue->front->next;
        free(toDeleteNode);
    }

    return value;
}

// 合并两个有序链式队列
LinkedQueue* mergeQueues(LinkedQueue *queue1, LinkedQueue *queue2) {
    LinkedQueue *mergedQueue = (LinkedQueue*)malloc(sizeof(LinkedQueue));
    initQueue(mergedQueue);

    QueueNode *current1 = queue1->front;
    QueueNode *current2 = queue2->front;

    while (current1 != NULL && current2 != NULL) {
        DataItem *data1 = current1->dataHead;
        DataItem *data2 = current2->dataHead;

        while (data1 != NULL && data2 != NULL) {
            if (data1->data <= data2->data) {
                enqueue(mergedQueue, data1->data);
                data1 = data1->next;
            } else {
                enqueue(mergedQueue, data2->data);
                data2 = data2->next;
            }
        }

        while (data1 != NULL) {
            enqueue(mergedQueue, data1->data);
            data1 = data1->next;
        }

        while (data2 != NULL) {
            enqueue(mergedQueue, data2->data);
            data2 = data2->next;
        }

        current1 = current1->next;
        current2 = current2->next;
    }

    while (current1 != NULL) {
        DataItem *data = current1->dataHead;
        while (data != NULL) {
            enqueue(mergedQueue, data->data);
            data = data->next;
        }
        current1 = current1->next;
    }

    while (current2 != NULL) {
        DataItem *data = current2->dataHead;
        while (data != NULL) {
            enqueue(mergedQueue, data->data);
            data = data->next;
        }
        current2 = current2->next;
    }

    return mergedQueue;
}

// 打印队列
void printQueue(LinkedQueue *queue) {
    if (isQueueEmpty(queue)) {
        printf("Queue is empty.\n");
        return;
    }
    QueueNode *current = queue->front;
    while (current != NULL) {
        DataItem *data = current->dataHead;
        while (data != NULL) {
            printf("%d ", data->data);
            data = data->next;
        }
        current = current->next;
    }
    printf("\n");
}

// 释放队列内存
void freeQueue(LinkedQueue *queue) {
    QueueNode *current = queue->front;
    QueueNode *nextNode;
    while (current != NULL) {
        DataItem *data = current->dataHead;
        DataItem *nextData;
        while (data != NULL) {
            nextData = data->next;
            free(data);
            data = nextData;
        }
        nextNode = current->next;
        free(current);
        current = nextNode;
    }
}

int main() {
    LinkedQueue queue1, queue2;
    initQueue(&queue1);
    initQueue(&queue2);

    enqueue(&queue1, 1);
    enqueue(&queue1, 3);
    enqueue(&queue1, 5);

    enqueue(&queue2, 2);
    enqueue(&queue2, 4);
    enqueue(&queue2, 6);

    printf("Queue 1: ");
    printQueue(&queue1);
    printf("Queue 2: ");
    printQueue(&queue2);

    LinkedQueue *mergedQueue = mergeQueues(&queue1, &queue2);
    printf("Merged Queue: ");
    printQueue(mergedQueue);

    freeQueue(&queue1);
    freeQueue(&queue2);
    freeQueue(mergedQueue);
    free(mergedQueue);

    return 0;
}

合并操作时间复杂度分析

分析过程：
- 合并两个有序链式队列时，我们需要遍历两个队列的所有节点和数据项。假设队列1的节点数为m，每个节点平均存储的数据项数为a，队列2的节点数为n，每个节点平均存储的数据项数为b。
- 外层循环遍历两个队列的节点，最多执行m + n次。
- 在内层循环中，对于每个节点内的数据项，最多执行a + b次比较和入队操作。
- 因此，总的操作次数与两个队列中的节点数和每个节点的数据项数之和成正比。
时间复杂度：
- 时间复杂度为 $O((m + n) \times (a + b))$。如果我们假设两个队列的长度分别为$L_1$和$L_2$（这里的长度指所有节点中数据项的总数），则时间复杂度为$O(L_1 + L_2)$，这是因为$L_1 = m\times a$，$L_2 = n\times b$。这是一个线性时间复杂度的操作，因为合并操作所需的时间与输入队列的总长度成正比。

星途面试题库

面试题：C语言链式队列优化

知识考点

面试题答案

合并操作时间复杂度分析