Linux环境下的C语言编程（四十一）

一、队列时间复杂度分析

1.链队列时间复杂度

// 链队列节点 typedef struct QueueNode { int data; struct QueueNode* next; // 额外指针开销 } QueueNode; // 链队列结构 typedef struct { QueueNode* front; // 队头指针 QueueNode* rear; // 队尾指针 } LinkedQueue;

入队操作 O(1)- 为什么是常数时间？（通过ai解决）

int enqueueLinked(LinkedQueue* q, int value) { // 1. 创建新节点 O(1) QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode)); // 2. 设置数据 O(1) newNode->data = value; newNode->next = NULL; if (isEmptyLinkedQueue(q)) { // 3. 直接设置 front 和 rear O(1) q->front = q->rear = newNode; } else { // 4. 直接插入到队尾 O(1) q->rear->next = newNode; // 通过 rear 直接访问尾部 q->rear = newNode; // 更新 rear } return 1; // 总共：4个O(1)操作 = O(1) }

关键点：

通过rear 指针，所以不需要遍历就能直接找到尾部

出队操作 O(1)- 单链表需要从头遍历吗？

int dequeueLinked(LinkedQueue* q, int* value) { // 1. 检查空队列 O(1) if (isEmptyLinkedQueue(q)) return 0; // 2. 直接从 front 获取数据 O(1) QueueNode* temp = q->front; *value = temp->data; // 3. 移动 front 指针 O(1) q->front = q->front->next; // 4. 特殊情况处理 O(1) if (q->front == NULL) { q->rear = NULL; } // 5. 释放内存 O(1) free(temp); return 1; // 总共：5个O(1)操作 = O(1) }

不需要！有front 指针直接指向头部，删除就是移动这个指针。

2.循环队列时间复杂度

#define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; // 连续内存空间 int front; // 队头索引 int rear; // 队尾索引 } CircularQueue;

所有操作 O(1)- 数组随机访问特性

// 入队 O(1) int enqueueCircular(CircularQueue* q, int value) { if (isFullCircularQueue(q)) return 0; // O(1) - 简单比较 // 数组的随机访问是 O(1) q->data[q->rear] = value; // O(1) - 直接下标访问 q->rear = (q->rear + 1) % MAX_SIZE; // O(1) - 简单计算 return 1; // 总：3个O(1)操作 = O(1) } // 出队 O(1) int dequeueCircular(CircularQueue* q, int* value) { if (isEmptyCircularQueue(q)) return 0; // O(1) *value = q->data[q->front]; // O(1) - 直接下标访问 q->front = (q->front + 1) % MAX_SIZE; // O(1) - 简单计算 return 1; // 总：3个O(1)操作 = O(1) }

关键点：

数组通过下标访问任意位置都是 O(1)，这是由内存的物理特性决定的：

• 地址 = 基地址 + 下标 × 元素大小

• 一次计算就能定位，不需要遍历

二、空间复杂度分析

1.链队列的空间复杂度

// 每个节点需要： struct QueueNode { int data; // 4字节（假设int是4字节） struct QueueNode* next; // 8字节（64位系统） // malloc 还有额外的头部开销（通常8-16字节） }; // 空间计算： // 有效数据：4字节 // 指针开销：8字节 // 内存对齐和malloc开销：约12字节 // 总共：约24字节存储一个int // 如果有n个元素： // 空间复杂度 = O(n) // 但实际上空间利用率 ≈ 4/24 ≈ 16.7%

2.循环队列的空间复杂度

// 固定分配： #define MAX_SIZE 100 // 预分配100个int的位置 int data[MAX_SIZE]; // 400字节（4×100） // 空间计算： // 有效数据：4×n字节 // 额外空间：两个int指针（8字节） // 总共：400 + 8 = 408字节 // 空间复杂度 = O(n) 但n是固定的 // 空间利用率最高可达 (MAX_SIZE-1)/MAX_SIZE ≈ 99% // （注意：循环队列通常牺牲一个空间区分空和满） // 实际内存布局： // [front][rear][data[0]][data[1]]...[data[99]]

三、复杂度对比表格