数据结构是存储和组织数据的方式，通过提高存取效率、节省内存和支持复杂操作来提高算法性能和程序性能。常见的数据结构包括数组、链表、栈、队列、哈希表、二叉树等。

操作速度按步数计算，即时间复杂度（衡量操作步数随输入规模的变化）。核心操作：读取、查找、插入、删除。
算法运行时所需的额外内存，即空间复杂度（衡量所需的额外内存空间随输入规模变化）。

大 O 记法

O ( 1 )	常数时间，不随数据规模变化。
O ( N )	线性时间，每增加一个元素，多一步。
O ( log N )	对数时间，数据翻倍，步数 +1。
O ( N² )	常见于嵌套循环（冒泡、选择、插入排序）。 - 大 O 只保留最高阶项，忽略常数。

大 O 默认 最坏情况。
平均情况：更贴近实际。
- 插入排序：适合基本有序的数据。
- 选择排序：适合逆序数据。
有序数组：插入需要查找位置；查找可更快。
二分查找 vs 线性查找
- 100 个元素：线性查找需 100 步，二分查找需 7 步。
规律：数组长度 ×2，二分查找最多步数 +1。

各数据结构对比

数据结构	查找	插入	删除	是否保持顺序	典型应用
数组	O(1)（按索引）/ O(N)（按值）	O(N)	O(N)	✅	顺序存储、随机访问
有序数组	O(log N)（二分）	O(N)	O(N)	✅	需要快速查找、少插入
链表	O(N)	O(1)（表头）/ O(N)（一般）	O(1)（头/尾）/ O(N)（一般）	✅	动态数据、频繁增删
双向链表	O(N)	O(1)（尾插）	O(1)（头尾删）	✅	队列实现
栈	O(N)	O(1) （push）	O(1)（pop）	❌	调用栈、撤销操作
队列	O(N)	O(1)（尾入）	O(1)（头出）	❌	调度、任务排队
散列表	O(1)	O(1)	O(1)	❌	快速查找、集合
二叉搜索树 (BST)	O(log N)	O(log N)	O(log N)	✅	有序数据、频繁改动
图	O(V+E)	O(1)–O(E)	O(1)–O(E)	✅	关系型数据、网络建模

散列表（哈希表）

核心思想：键 → 散列函数 → 索引格子。
插入、查找、删除：平均 O(1)。
冲突处理：分离链接（链表）等。
负载因子 ≈ 0.7 最佳。
缺点：不保持顺序。

栈与队列

栈 (Stack)：LIFO（后进先出）。操作限制在栈顶。
队列 (Queue)：FIFO（先进先出）。插入在尾，删除在头。
应用：函数调用栈、任务调度。

递归与快速排序

递归：用调用栈实现，必须有基准情形。
快速排序：分区 → 递归子数组 → O(N log N) 平均效率。

链表

单链表：结点 = 数据 + 指针。
- 插入表头：O(1)。
- 查找/遍历：O(N)。
双向链表：结点有前后指针。
- 队列实现可做到插入、删除都是 O(1)。

二叉树

二叉搜索树 (BST)：
- 左子树 < 根 < 右子树。
- 查找、插入、删除：平均 O(log N)。
缺点：若输入有序 → 树退化为链表 → O(N)。
删除规则：无子结点 / 单子结点 / 两子结点（用后继替代）。

图

图：处理关系型数据。
遍历方式：
- BFS（广度优先搜索，用队列）。
- DFS（深度优先搜索，用栈或递归）。
加权图：边带有权重。

C版实现

数组

#include <stdio.h>

int main() 
{
    // 初始化数组和元素个数
    int arr[100] = {10, 20, 30, 40, 50}; // 数组初始值
    int n = 5; // 当前数组元素个数
    int i;

    // 1️⃣ 读取（遍历数组）
    printf("数组元素：");
    for (i = 0; i < n; i++) 
    {
        printf("%d ", arr[i]); // 依次打印每个元素
    }
    printf("\n");

    // 2️⃣ 查找（找到元素的位置）
    int target = 30; // 要查找的元素
    int pos = -1;    // 用于记录找到的位置，-1表示未找到
    for (i = 0; i < n; i++) 
    {
        if (arr[i] == target) 
        { // 如果当前元素等于目标
            pos = i;            // 记录位置
            break;              // 找到后退出循环
        }
    }
    if (pos != -1)
        printf("元素 %d 在位置 %d\n", target, pos);
    else
        printf("未找到元素 %d\n", target);

    // 3️⃣ 插入（在位置 2 插入 25）
    int insertPos = 2; // 插入位置
    int value = 25;    // 要插入的值
    // 将插入位置及之后的元素右移一位
    for (i = n; i > insertPos; i--) 
    {
        arr[i] = arr[i - 1];
    }
    arr[insertPos] = value; // 插入新元素
    n++; // 元素数量增加
    printf("插入后数组：");
    for (i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");

    // 4️⃣ 删除（删除位置 3 的元素）
    int deletePos = 3; // 要删除的元素位置
    // 将删除位置之后的元素左移一位覆盖
    for (i = deletePos; i < n - 1; i++) 
    {
        arr[i] = arr[i + 1];
    }
    n--; // 元素数量减少
    printf("删除后数组：");
    for (i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");

    return 0;
};