数据结构与算法

算法是完成一项任务或解决一个问题的明确、有限的步骤和流程。

数据结构是算法高效运行的前提。
它是特意设计的数据存储和组织方式。

• 数据结构 = 字典排版（拼音排序、索引）

• 算法 = 查字典方法（二分查找）

• 数据结构：设计稳固的地基。

• 算法：规划最优的动线。

构建（数据结构）

线性表、栈、队列、树、图

数组

数组是一块连续的内存空间，用于存放一组相同类型的数据。

• 连续存储：像一排紧挨着的房间。
• 固定步长：每个房间大小完全一致。
• 下表访问：通过门牌号（Index）快速定位。

C++示例：

int main(){
    // 声明并初始化数组 
    int a[] = {3, 1, 4, 1, 5};

    // 计算元素个数 
    int n = sizeof(a) / sizeof(a[0]);

    // 遍历打印  
    for(int i = 0 ; i < n; i ++){
        printf("a[%d] = %d\n", i, a[i]);
    }
}

python示例：

# 声明并初始化数组 
a = [3, 1, 4, 1, 5]

# 计算元素个数 
n = len(a)

# 遍历打印  
for i in range(n):
    print(f"a[{i}] = {a[i]}")

逻辑视角

随机访问（Random Access）：指可以直接访问任意位置的数据，而不需要从头遍历。
寻址公式：addr(i) = base + i * size。
CPU只需要进行一次乘法和一次加法，就能算出任意元素的内存地址。

数组显然符合随机访问逻辑🤓

物理视角

数组在物理内存中的连续性，完美契合了现代CPU的缓存机制。

空间局部性原理：程序倾向于访问相邻的内存位置。

预取优势（Prefetching）：CPU读取a[0]时， 会顺便把a[1]...a[k]一起加载到高速缓存（Cache🚀）中。

数组的增删改查

数组在读写方面是天才，但在增删方面略显笨拙。

操作	时间复杂度	说明
读取 (Access)	O(1)	随机访问，秒级定位
修改 (Update)	O(1)	直接覆盖内存
插入 (Insert)	O(n)	最坏需移动 n 个元素
删除 (Delete)	O(n)	最坏需移动 n 个元素

• 原则：如果你的场景是“读多写少”（如配置表、缓存索引），数组是首选。

动态数组

动态数组（Dynamic Array）

动态数组解决了静态数组“大小固定”的痛点（如Java ArrayList，C++ Vector，Python List）

自动扩容机制

初始化：申请小空间（Capacity = 10）
存满时：触发扩容（Grow）
搬家：

• 申请更大的新空间（x2）
• 将就数据复制过去
• 释放就空间

代码实现：

定义结构体：

typedef struct{
    int *data;       // 连续内存指针
    size_t size;     // 实际元素个数
    size_t capacity; // 总容量
} DynamicArray;

• data：指向底层真正的静态数组。

• size：住了多少人（Len）。

• capacity：房子有多大（Cap）。

• 时刻保持： size $\le$ capacity

追加元素（Push Back）：

void push_back(DynamicArray *da, int val){
    // 1. 检查容量   
    if(da->size == da->capacity){
        grow(da); // 扩容
    }

    // 2. 放入新元素
    da->data[da->size] = val;

    // 3. 更新计数 
    da->size ++;
}

• 大多数情况：容量够用，直接放，O(1)。
• 极少数情况：容量满了，触发扩容，O(n)。

扩容（grow）：

void grow(DynamicArray *da){
    // 1. 计算新容量（通常翻倍）  
    int new_cap = da->capacity * 2;
    int *new_data = malloc(new_cap * sizeof(int)); // 申请新空间

    // 2. 搬家（复制数据）  
    for (int i = 0; i < da->size; ++ i){
        new_data[i] = da->data[i];
    }

    // 3. 销毁旧房子，启用新房子
    free(da->data);
    da->data = new_data;
    da->capacity = new_cap;
}

• 申请内存：需要操作系统分配。
• 数据复制：O(n)的操作，元素越多越慢。

链表

数组的困境：数组要求大家“整齐排队”（连续内存），但如果内存里没有足够大的连续空地怎么办。

链表（Linked List）化身为一张藏宝图：
数据分散在各个角落，每个节点即有奖励（Data），又有指向下一站的线索（Pointer）。

链表是一组零散的内存块（节点），通过指针串联在一起的数据结构。

• 节点（Node）：既存数据，也存线索。
• 离散存储：无需连续内存，走到哪住到哪。
• 逻辑连续：通过指针“手拉手”形成链条。

定义节点与创建链表

代码实现：

1.定义节点：

typedef struct Node{
    int data;          // 数据域
    struct Node* next; // 指针域 
} Node;

// 创建新节点  

Node* createNode(int value){
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

2.创建链表：

C++创建链表代码示例：

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

typedef struct Node
{
    int data;
    struct Node* next;
}Node;

Node* createNode(int val)
{
    Node* newNode = new Node;
    newNode->data = val;
    newNode->next = nullptr;
    return newNode;
}

int main()
{
    // 创建3个节点
    Node* a = createNode(10);
    Node* b = createNode(20);
    Node* c = createNode(30);
    
    // 将三个节点连接
    a->next = b; b->next = c;
    
    // 打印该链表
    int j = 1;
    for(Node* i = a; i != nullptr; i = i->next)
    {
        printf("节点%d的地址为0x%x, 节点%d的值为%d, 节点%d的next为0x%x\n", j, i, j, i->data, j, i->next);
        j++;
    }
    
    delete a; delete b; delete c;
    
    return 0;
}

/*
结果：
节点1的地址为0x10, 节点1的值为10, 节点1的next为0x2A
节点2的地址为0x2A, 节点2的值为20, 节点2的next为0x5F
节点3的地址为0x5F, 节点3的值为30, 节点3的next为0x0
*/

在C中创建链表，开辟空间和释放空间方式有所不同：

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

typedef struct Node
{
    int data;
    struct Node* next;
}Node;

Node* createNode(int val)
{
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = val;
    newNode->next = NULL;
    return newNode;
}

int main()
{
    // 创建3个节点
    Node* a = createNode(10);
    Node* b = createNode(20);
    Node* c = createNode(30);
    
    // 将三个节点连接
    a->next = b; b->next = c;
    
    // 打印该链表
    int j = 1;
    for(Node* i = a; i != NULL; i = i->next)
    {
        printf("节点%d的地址为0x%x, 节点%d的值为%d, 节点%d的next为0x%x\n", j, i, j, i->data, j, i->next);
        j++;
    }
    
    free(a); free(b); free(c);
    
    return 0;
}

链表插入

相比数组的“搬家式”插入，链表只需要“修改指针”即可完成。

• 关键两步：1. New指向C 2. B指向New

代码实现：
A -> New -> B

void insert(Node* A, Node* New){
    // 1. 先连后方（New -> B）  
    New->next = A->next;

    // 2. 再断前缘（A -> New）
    A->next = New;
}

链表删除

删除节点同样只需“修改指针”，让前驱直接指向后继。

• 关键一步：A绕过B，直接指向C

删除Current的后继节点

• 定位：标记要删的节点（toDelete）
• 旁路：让当前节点指向下下个节点
• 释放：归还内存（free）

代码实现：

void deleteNextNode(Node* currentNode){
    if(currentNode->next != NULL){
        // 1. 找到要删除的节点 
        Node* toDelete = currentNode->next;

        // 2. 旁路：当前指向下下个
        currentNode->next = toDelete->next;

        // 3. 释放内存
        free(toDelete);
    }
}

链表读取

只知道头节点，要想找到下标为5的节点。 因为内存不连续，无法通过公式计算地址，必须从头节点开始，顺着next指针跳5次。
走法：从head出发，沿next连跳5次。

代码实现：

Node* get(Node* head, int k){
    int i = 0; 
    while(head && i < k){
        head = head->next;
        i ++;
    }
    return head;
}

链表与数组

特性	数组 (Array)	链表 (Linked List)
内存结构	连续，利用 CPU 缓存	离散，指针连接
随机访问	✅ O(1) 秒级定位	❌ O(n) 只能遍历
插入/删除	❌ O(n) 需要搬移数据	✅ O(1) 仅改指针
空间效率	固定大小 (或需扩容)	动态申请 (但有指针开销)

链表总结

链表巧妙牺牲随机访问，换取动态性与插入/删除的极致效率

链表与数组互补：数组追求“快读”，链表擅长“快插快删”。

栈

栈是一种受限的线性表，只允许再同一端（栈顶）进行插入和删除操作。

• LIFO（Last In First Out）：后进者先出，如同洗盘子。
• 栈顶（Top）：允许操作的一端。
• 栈底（Bottom）：封死的一端，最早进来的元素在最底下。

• Push（入栈）
• Pop（出栈）

栈的核心操作

无论底层用数组还是链表实现，栈对外暴露的接口是统一的，时间复杂度均为O(1)。

• push(x) 压栈：把元素x放到栈顶。
• pop() 弹栈：移除并返回栈顶元素。
• peek() 查看：只看一眼栈顶（不删除）。
• isEmpty() 判空：检查栈里有没有元素。
• size() 计数：返回当前元素个数。

约定：

• top指向当前栈顶元素。
• 栈空时top = -1

代码实现：

typedef struct Stack{
    int data[MAX];
    int top;
} Stack;

void initStack(Stack *s){
    s->top = -1;
}

bool push(Stack *s, int val){
    if(s->top == MAX - 1) return false;
    s->data[++ s->top] = val; // 栈顶上移并存值
    return true;
}

bool pop(Stack *s, int *val){
    if(isEmpty(s)) return false;
    *val = s->data[s->top --]; // 弹栈并返回
    return true;
}

bool peek(Stack *s, int *val){
    if(isEmpty(s)) return false;
    *val = s->data[s->top]; // 只读不移
    return true;
}

bool isEmpty(Stack *s){
    return s->top == -1;
}

int size(Stack *s){
    return s->top + 1;
}

括号匹配

代码实现：

// 判断左右括号是否匹配
bool isMatchingPair(char left, char right){
    return (left == '(' && right == ')') ||
           (left == '[' && right == ']') ||
           (left == '{' && right == '}');
}

// 是否是合法括号
bool isValidBrackets(const char *str){
    Stack s;
    initStack(&s);

    // 读取str
    for(int i = 0; str[i] != '\0'; i ++){
        char ch = str[i];

        // 遇到左括号，入栈  
        if(ch == '(' || ch == '[' || ch == '{'){
            push(&s, ch);
        }
        //遇到右括号，尝试匹配  
        else if(ch == ')' || ch == ']' || ch == '}'){
            int topVal;
            if(isEmpty(&s)) return false; // 右括号多余

            pop(&s, &topVal);
            if(!isMatchingPair((char)topVal, ch)){
                return false; // 类型不匹配
            }
        }
    }

    // 最后栈必须为空
    return isEmpty(&s);
}

int main(){
    const char *str = "abc(d[e]f)[g{h}i]{jkl}";
    bool calid = isValidBrackets(str);
    printf("%-20s -> %s\n", str, valid ? "匹配成功" : "匹配失败");

    return 0;
}

后缀求值

代码实现：

int applyOperator(int a, int b, char op){
    switch(op){
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': return a / b;
    }
    return 0;
}

int evaluatePostfix(const char *expr){
    Stack s;
    initStack(&s);

    for(int i = 0; expr[i] != '\0'; i ++){
        char c = expr[i];

        if(c == ' ') continue;

        // 如果是数字
        if(isdigit(c)){
            push(&s, c - '0');
        }
        // 如果是运算符
        else if(isOperator(c)){
            int a, b;
            pop(&s, &b); // 先出栈的是右操作数
            pop(&s, &a); // 后出栈的是左操作数
            int result = applyOperator(a, b, c);
            push(&s, result);
        }
    }

    int finalResult;
    pop(&s, &finalResult);
    return finalResult; 
}

中缀转后缀

代码实现：

// 辅助：获取优先级（*/ > +-）
int getPriority(char op){
    if(op == '*' || op == '/') return 2;
    if(op == '+' || op == '-') return 1;
    return 0; // '('优先级最低
}

void infixToPostfix(const char* infix, char* postfix){
    Stack s; 
    initStack(&s);
    int j = 0; // postfix写入位置

    for(int i = 0; infix[i] != '\0'; i ++){
        char c = infix[i];
        if(c == ' ') continue;

        // 1. 数字：直接输出
        if(isdigit(c)){
            postfix[j ++] = c;
        }
        // 2. 左括号：入栈待命
        else if(c == '('){
            push(&s, c);
        }
        // 3. 右括号：弹栈直到'('
        else if(c == ')'){
            int topVal;
            pop(&s, &topVal);
            while(!isEmpty(&s) && topVal != '('){
                pop(&s, &topVal);
                postfix[j ++] = (char)topVal;
                peek(&s, &topVal);
            }
            pop(&s, &topVal); // 丢弃'('
        }
        // 4.运算符：维护优先级单调性  
        else{
            int topVal;
            while(!isEmpty(&s)){
                peek(&s, &topVal);
                // 栈顶 < 当前：直接入栈
                if(topVal =='(' || getPriority(topVal) < getPriority(c))
                    break;

                // 栈顶 >= 当前：弹出栈顶
                pop(&s, &topVal);
                postfix[j ++] = (char)topVal;
            }
            push(&s, c);
        }
    }
    // 5. 收尾：弹出剩余符号
    while(!isEmpty(&s)){
        int topVal;
        pop(&s, &topVal);
        postfix[j ++] = (char)topVal;
    }
    postfix[j] = '\0';
}

栈的应用

凡是符合“最后做的事要先被撤回/先被处理”或“先走到底，再一层层往回退”的问题，本质上都适合用栈来解决。

算法应用：

• 深度优先搜索（DFS）：利用栈“先走到最深，再按相反顺序回退”，逐层展开并回溯。
• 回溯算法：保存决策路径，失败时快速撤销最近一次选择。
• 递归显式实现：手动保存函数状态，模拟系统调用栈。

系统与工程应用：

• OS函数调用栈：保证函数按”后调用、先返回“顺序执行。
• 游览器前进/后退：通过栈记录访问历史，实现逆序回退。
• 撤销操作（Undo）：按相反顺序回访，优先撤销最近修改。

队列

• 入队（Enqueue）：新来的只能排在队尾（Rear）。
• 出队（Dequeue）：离开的永远是队头（Front）。
• 双端操作：一端只进，另一端只出。

• 先进先出（FIFO，First In First Out）

队列的核心操作

队列对外暴露的接口是统一的，时间复杂度均为O(1)。

• enqueue(x)：将元素x加入队尾
• dequeue(): 移除并返回队头元素
• peek() 查看队头元素（不删除）。
• isEmpty() 判空：检查队列里有没有元素。
• size() 计数：获取队列当前元素个数。

循环队列的实现

循环数组本质上是基于固定长度数组实现的。
通过取模运算，在逻辑上将数组的末尾与开头相连，形成一个环形结构，从而服用数组空间。

核心变量状态：

• Front（头指针）：指向队列第一个有效元素的位置。
• Rear（尾指针）：指向下一个即将插入数据的空位。
• Capacity（容量）：数组的总长度。

循环队列的实现：

#define MAX_SIZE 128

typedef struct Queue{
    int data[MAX_SIZE];
    int front;
    int rear;
} Queue;

bool enqueue(Queue, *q, int val){
    // 1. 判满（留空法） 
    if((q->rear + 1) % MAX_SIZE == q->front){
        return false;
    }
    // 2. 存数据
    q->data[q->rear] = val;
    // 3. 移动指针（回绕）
    q->rear = (q->rear + 1) % MAX_SIZE;
    return true;
}

• 不需要size变量也能维护状态。
• Rear指向的是空位，所以先存数据，再移指针。
• 容量上限固定，适合内存敏感或负载可以预测的场景。

bool dequeue(Queue *q, int *val){
    // 1. 判空
    if(q->front == q->rear){
        return false;
    }
    // 2. 取数据
    *val = q->data[front];
    // 3. 移动头指针（回绕）
    q->front = (q->front + 1) % MAX_SIZE;
    return true;
}

链表队列的实现

链表实现队列
如果无法预估计数据量，或者需要频繁扩容，链表（Linked List）是更好的选择。

• 无限容量：仅受内存限制，无isFull。
• 头尾指针：
  • front指向链表头节点（出队）。
  • rear指向链表尾节点（入队）。

• 入队：队列为空front和rear指向新节点，否则只更新rear。
• 出队：当队列中只剩下一个元素时，手动将rear也设为NULL。

typedef struct Node{
    int data;
    struct Node *next;
}Node;

typedef struct LinkedQueue{
    Node *front;
    Node *rear;
}LinkedQueue;

void enqueue(LinkQueue *q, int val){
    Node *n = malloc(sizeof(Node));
    n->data = val; n->next = NULL;

    // 特判空队列
    if(q->rear == NULL){
        q->front = q->rear = n;
    }
    else{
        q->rear->next = n;
        q->rear = n;
    }
}

bool dequeue(LinkedQueue *q, int *val){
    if(!q->front) return false;

    Node *t = q->front;
    *val = t->data;
    q->front = q->front->next;

    // 特判队空，重置rear
    if(!q->front) q->rear = NULL;

    free(t);
    return true;
}

链表队列的使用场景：

尽管基于循环数组的队列在追求极致吞吐量和缓存亲和性的场景下表现优异，但在并发变成、操作系统内核以及容量波动较大的复杂场景中，链表实现的队列依然拥有不可替代的地位。

1.消除扩容抖动
数组扩容会有笋尖的性能尖峰（Stop-the-World）。链表入队永远是稳定的O(1)，适合实时系统。

2.兵法锁粒度更小
数组队列通常需要锁住整个结构。链表队列天然头尾分离，入队和出队互不干扰，可实现细粒度锁或无锁队列（Lock-free）。

3.避免内存浪费
不需要像数组那样与分配一大块连续内存，对内存碎片容忍度高。

4.大对象传递
如果队列存的是很重的对象（如PCB），链表传递指针比数组拷贝整个数据块要快得多。

队列场景

广度优先搜索（BFS）：
层序遍历的基础。比如地图导航找最近路线、社交网络找三度好友。

消息队列（MQ）：
Kafka/RabbitMQ。用于削峰填谷和系统解耦。生产者发消息入队，消费者按能力出队处理。

操作系统调度：
CPU就绪队列。所有进程排队等待CPU时间片（Time Slice）。

栈vs队列

特性	栈 (Stack)	队列 (Queue)
逻辑结构	LIFO (后进先出)	FIFO (先进先出)
入口	栈顶 (Top)	队尾 (Rear)
出口	栈顶 (Top)	队头 (Front)
核心思想	回溯、撤销、深度优先	缓冲、公平、广度优先

哈希表

一种用键（Key）快速定位值（Value）的数据结构。

• Key：查找的标识（如学号）。
• Bucket：存储数据的容器（数组）。
• Hash Function：转换器（Key->整数）。
• 策略：用空间（数组）换时间（计算）。

哈希函数

将任意长度的输入，转换为固定长度的输出（下标）。
Index = Hash(Key) % Capacity

// 简单的字符串哈希
unsigned int simpleHash(char *key, int cap){
    unsigned int hash = 0; 
    while(*key){
        hash = 31 * hash + *key; // 31是质数
        key ++;
    }
    return hash % cap;
}

• 转整数：把字符串变成数字。
• 取模：%capacity确保落在数组范围内。
• 定位：拿到合法的数组下标。

哈希冲突

鸽巢原理：如果鸽子比巢穴多，肯定有两只鸽子挤在一起。

拉链法

拉链法（Separate Chaining）

桶内不直接存数据，而是存一个链表头指针。

• 插入：计算下标 -> 找到链表头 -> 头插法/尾插法放入。
• 查找：计算下标 -> 遍历该位置的链表 -> 比对Key。

哈希表实现

定义结构体：

typedef struct Entry{
    char *key;
    int value;
    struct Entry *next; // 链表指针
}Entry;

typedef struct HashTable{
    // 指针数组：每个元素是链表头
    Entry *buckets[TABLE_SIZE];
}HashTable;

• Entry（节点）：存储Key，Value和Next指针。
• HashTable：一个数组，数组存的是Entry*。
• 初始化时，要把所有buckets置为NULL。

put()函数：

void put(HashTable *table, char *key, int val){
    int idx = hash(key) % TABLE_SIZE;

    // 1. 遍历链表，检查Key是否已存在。  
    Entry *cur = table->buckets[idx];
    while(cur){
        if(strcmp(cur->key, key) == 0){
            cur->value = val; // 更新
            return ;
        }
        cur = cur->next;
    }
    
    // 2. 不存在，头插法插入新节点
    Entry *new_node = malloc(sizeof(Entry));
    new_node->key = strdup(key);
    new_node->value = val;
    new_node->next = table->buckets[idx]; //接旧头
    table->buckets[idx] = new_node; //换新头
}

• 计算hash(key)得到数组下标i。
• 找到table[i]对应的链表。
• 遍历链表：
  • 如果发现Key已经存在，更新Value。
  • 如果遍历完没找到，将新节点添加到链表中

治理（排序算法）

让无序变有序，为高效铺路

检索（查找算法）

在特定结构中，精准定位目标