数据结构（一）：基础数据结构

数据结构是计算机存储、组织数据的方式。选择合适的数据结构可以显著提升算法的效率。

---

一、数组（Array）

定义

数组是连续内存空间中存储的相同类型元素的集合，支持 O(1) 随机访问。

// 声明和初始化
int arr[5] = {1, 2, 3, 4, 5};
int arr2[] = {1, 2, 3, 4, 5};  // 自动推断大小
int arr3[5] = {0};              // 全部初始化为 0

// 访问元素
printf("%d\n", arr[2]);  // 3（O(1) 访问）

// 遍历
for (int i = 0; i < 5; i++) {
    printf("%d ", arr[i]);
}

操作时间复杂度

操作	最好	平均	最坏
访问	O(1)	O(1)	O(1)
查找	O(1)	O(n)	O(n)
插入（尾部）	O(1)	O(1)	O(1)
插入（头部/中间）	O(n)	O(n)	O(n)
删除（尾部）	O(1)	O(1)	O(1)
删除（头部/中间）	O(n)	O(n)	O(n)

动态数组

#include <stdlib.h>

int* dynamic_array = (int*)malloc(10 * sizeof(int));
if (dynamic_array == NULL) {
    // 内存分配失败处理
}

// 使用完释放
free(dynamic_array);

优缺点

• 优点：随机访问快，缓存友好（空间局部性好）
• 缺点：插入/删除慢（需要移动元素），大小固定（静态数组）

适用场景

• 需要频繁随机访问
• 元素数量相对固定
• 对内存空间要求严格

---

二、链表（Linked List）

定义

链表由节点（Node） 通过指针连接而成，每个节点包含数据域和指针域，存储不连续。

单向链表

// 节点定义
struct Node {
    int data;
    struct Node* next;
};

// 创建节点
struct Node* create_node(int data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}

// 插入到头部
struct Node* insert_head(struct Node* head, int data) {
    struct Node* new_node = create_node(data);
    new_node->next = head;
    return new_node;
}

// 遍历打印
void print_list(struct Node* head) {
    struct Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

// 查找元素
struct Node* search(struct Node* head, int target) {
    struct Node* current = head;
    while (current != NULL) {
        if (current->data == target)
            return current;
        current = current->next;
    }
    return NULL;
}

// 删除节点
struct Node* delete_node(struct Node* head, int target) {
    if (head == NULL) return NULL;
    if (head->data == target) {
        struct Node* temp = head->next;
        free(head);
        return temp;
    }
    struct Node* current = head;
    while (current->next != NULL && current->next->data != target) {
        current = current->next;
    }
    if (current->next != NULL) {
        struct Node* temp = current->next;
        current->next = temp->next;
        free(temp);
    }
    return head;
}

双向链表

struct DoublyNode {
    int data;
    struct DoublyNode* prev;
    struct DoublyNode* next;
};

操作时间复杂度

操作	单向链表	双向链表
访问头部	O(1)	O(1)
访问尾部	O(n)	O(1)（有尾指针）
访问中间	O(n)	O(n)
插入头部	O(1)	O(1)
插入尾部	O(n)	O(1)（有尾指针）
删除头部	O(1)	O(1)
删除已知节点	O(1)（有前驱）	O(1)

优缺点

• 优点：插入/删除快（O(1)），大小可动态变化
• 缺点：不支持随机访问（O(n)），需要额外指针空间

适用场景

• 频繁插入和删除操作
• 元素数量不确定，需要动态增长
• 不需要随机访问

---

三、栈（Stack）

定义

栈是一种后进先出（LIFO, Last In First Out） 的线性数据结构，限制只在栈顶进行插入和删除操作。

数组实现

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int top;  // 栈顶指针，-1 表示空栈
} Stack;

// 初始化
void init(Stack* s) {
    s->top = -1;
}

// 判断栈空
int is_empty(Stack* s) {
    return s->top == -1;
}

// 判断栈满
int is_full(Stack* s) {
    return s->top == MAX_SIZE - 1;
}

// 入栈（push）
void push(Stack* s, int value) {
    if (is_full(s)) {
        printf("栈满\n");
        return;
    }
    s->data[++s->top] = value;
}

// 出栈（pop）
int pop(Stack* s) {
    if (is_empty(s)) {
        printf("栈空\n");
        return -1;
    }
    return s->data[s->top--];
}

// 获取栈顶元素
int peek(Stack* s) {
    if (is_empty(s)) return -1;
    return s->data[s->top];
}

链表实现

struct StackNode {
    int data;
    struct StackNode* next;
};

void push(struct StackNode** top, int value) {
    struct StackNode* new_node = (struct StackNode*)malloc(sizeof(struct StackNode));
    new_node->data = value;
    new_node->next = *top;
    *top = new_node;
}

int pop(struct StackNode** top) {
    if (*top == NULL) return -1;
    struct StackNode* temp = *top;
    int value = temp->data;
    *top = (*top)->next;
    free(temp);
    return value;
}

操作时间复杂度

所有操作（push、pop、peek、isEmpty）均为 O(1)。

常见应用

• 函数调用栈：保存函数调用的返回地址和局部变量
• 表达式求值：中缀表达式转后缀表达式
• 括号匹配：检查括号是否成对出现
• 撤销操作：编辑器的 Ctrl+Z
• 浏览器的后退：页面访问历史

括号匹配示例

int is_valid_brackets(char* s) {
    struct StackNode* stack = NULL;
    for (int i = 0; s[i] != '\0'; i++) {
        if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
            push(&stack, s[i]);
        } else {
            if (stack == NULL) return 0;
            char top = pop(&stack);
            if ((s[i] == ')' && top != '(') ||
                (s[i] == ']' && top != '[') ||
                (s[i] == '}' && top != '{')) {
                return 0;
            }
        }
    }
    return stack == NULL;
}

---

四、队列（Queue）

定义

队列是一种先进先出（FIFO, First In First Out） 的线性数据结构，队尾插入，队头删除。

数组实现（循环队列）

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int front;  // 队头指针
    int rear;   // 队尾指针
} Queue;

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

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

// 判断队列满
int is_full(Queue* q) {
    return (q->rear + 1) % MAX_SIZE == q->front;
}

// 入队
void enqueue(Queue* q, int value) {
    if (is_full(q)) {
        printf("队列满\n");
        return;
    }
    q->data[q->rear] = value;
    q->rear = (q->rear + 1) % MAX_SIZE;
}

// 出队
int dequeue(Queue* q) {
    if (is_empty(q)) {
        printf("队列空\n");
        return -1;
    }
    int value = q->data[q->front];
    q->front = (q->front + 1) % MAX_SIZE;
    return value;
}

操作时间复杂度

所有操作（enqueue、dequeue、isEmpty、isFull）均为 O(1)。

常见应用

• BFS（广度优先搜索）：图的层次遍历
• 任务调度：打印队列、CPU 任务队列
• 消息队列：生产者-消费者模型
• 缓冲区：IO 缓冲、网络数据包缓冲

---

各结构时间复杂度对比

操作	数组	链表	栈	队列
访问（头部）	O(1)	O(1)	O(1)	O(1)
访问（尾部）	O(1)	O(n)	O(1)	O(1)
访问（中间）	O(1)	O(n)	—	—
插入头部	O(n)	O(1)	—	—
插入尾部	O(1)	O(n)	O(1)	O(1)
删除头部	O(n)	O(1)	O(1)	O(1)
删除尾部	O(1)	O(n)	O(1)	—
搜索	O(n)	O(n)	O(n)	O(n)

---

选择建议

需求场景	推荐结构
需要快速随机访问	数组
频繁插入和删除	链表
后进先出（LIFO）	栈
先进先出（FIFO）	队列
需要快速访问首尾	双向链表或循环队列

---

练习

动手实践

1. 用数组实现一个栈，支持 push、pop、peek 操作
2. 用链表实现一个队列，支持 enqueue、dequeue 操作
3. 用栈实现括号匹配（包含 (), [], {}）
4. 实现一个 LRU 缓存淘汰算法（提示：使用双向链表 + 哈希表）