• 数据结构三要素

    • 逻辑结构
    • 物理结构（存储结构）
    • 数据的运算（基本操作）

  • 复杂度

    • 时间复杂度
    • 空间复杂度

  • 线性表（具有相同数据类型的 n 个数据元素的有限序列）

    • 顺序表（顺序存储）
    • 链表（链式存储）
      • 单链表
      • 双链表
      • 循环链表
        • 循环单链表
        • 循环双链表
      • 静态链表（存储在连续空间）

  • 栈

    • 顺序存储
    • 链式存储

  • 队列

    • 存储方式
      • 顺序存储
      • 链式存储
    • 双端队列
      • 双端队列（只允许从两段插入、两段删除的线性表）
      • 输入受限的双端队列（只允许从一端插入，两端删除的线性表）
      • 输出受限的双端队列（只允许从两端插入，一端删除的线性表）

  • 特殊矩阵

  • 串

    • 朴素匹配
    • KMP 算法

  • 树

    • 二叉树
      • 存储
        • 顺序存储
        • 链式存储
      • 遍历
        • 先序遍历
        • 中序遍历
        • 后序遍历
        • 层次遍历
    • 线索二叉树
    • 存储结构
      • 双亲表示法（顺序存储，每个结点保存指向双亲的指针）
      • 孩子表示法（顺序+链式存储，每个结点中保存孩子链表头指针）
      • 孩子兄弟表示法（链式存储，左指针指向左第一个孩子，右指针指向右兄弟）
    • 森林和二叉树的转换（通过孩子兄弟表示法）
    • 树的遍历
      • 先根遍历
      • 后根遍历
      • 层次遍历
    • 森林的遍历
      • 先序遍历
      • 中序遍历
    • 哈夫曼树（带权路径长度最小的二叉树）

  • 并查集（未看）

  • 图（未看）

    • 基本概念
      • 无向图，有向图
      • 简单图（不存在重复边，不存在顶点到自身的边），多重图
      • 顶点的度、入度、出度
      • 路径，回路，简单路径，简单回路，路径长度，点到点的距离
      • 连通图，强连通图
      • 连通分量（无向图中的极大连通子图）
      • 强连通分量（有向图中的极大强连通子图）
      • 生成树（包含图中全部顶点的一个极小连通子图）
      • 生成森林
      • 无向完全图，有向完全图，稀疏图，稠密图
      • 树，有向树
    • 存储
      • 邻接矩阵
      • 邻接表
      • 十字链表
      • 邻接多重表
    • 遍历
      • 广度优先遍历
      • 深度优先遍历
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      void DFS(vector<vector<int>>& G, vector<int>& visited, int n, int i) {
          for (int j = 0; j < n; j++) {
              if (G[i][j] == 1 && !visited[j]) {
                  visited[j] = 1;
                  DFS(G, visited, n, j);
              }
          }
      }

      int DFSTraverse(vector<vector<int>>& G) {
          int n = G.size();
          vector<int> visited(n);
          int res = 0;
          for (int i = 0; i < n; ++i) {
              if (!visited[i]) {
                  DFS(G, visited, n, i);
                  ++res;
              }
          }
          return res;
      }

  • 查找

    • 顺序查找
    • 折半查找（二分查找）
    • 分块查找（索引表保存每个分块的最大关键字和分块的存储区间，块内无序，块间有序，块内顺序查找）
    • 二叉排序树（二叉搜索树）（左子树结点值 < 根结点值 < 右子树结点值）
    • 平衡二叉树（树上任一结点的左子树和右子树的高度之差不超过 1）
    • [[红黑树]]
    • B 树
    • B+ 树

  • 排序

    • 冒泡排序

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    void bubbleSort(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n-1; ++i) {
            bool flag = false;
            for (int j = 0; j < n - i - 1; ++j) {
                if (nums[j] > nums[j+1]) {
                    flag = true;
                    swap(nums[j], nums[j+1]);
                }
            }
            if (!flag)
                break;
        }
    }

    • 选择排序（往后查找最小值进行交换）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    void selectionSort(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n-1; ++i) {
            int min = i;
            for (int j = i + 1; j < n; ++j) {
                if (nums[j] < nums[min])
                    min = j;
            }

            swap(nums[i], nums[min]);
        }
    }

    • 插入排序

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    // 基于顺序查找
    void insertSort(vector<int> &nums) {
        int i, j, tmp;
        int n = nums.size();
        for (i = 1; i < n; ++i) {
            if (nums[i] >= nums[i-1]) continue;
            tmp = nums[i];
            for (j = i - 1; j >= 0 && nums[j] > tmp; --j)
                nums[j+1] = nums[j];
            nums[j+1] = tmp;
        }
    }

    // 基于折半查找
    void insertSort(vector<int> &nums) {
        int i, j, tmp, low, high, mid;
        int n = nums.size();
        for (i = 1; i < n; ++i) {
            if (nums[i] >= nums[i-1]) continue;
            tmp = nums[i];
            low = 0, high = i - 1;

            while(low <= high) {
                mid = (low + high) / 2;
                if (nums[mid] <= tmp)
                    low = mid + 1;
                else
                    high = mid - 1;
            }

            for (j = i - 1; j > high; --j)
                nums[j+1] = nums[j];
            nums[low] = tmp;
        }
    }