Skip to content

算法与数据结构

一、概述📌

Tip

抽象数据类型ADT：

逻辑结构和物理实现分离，不讨论具体实现

二、算法基础📌

1、特征📌

特征
有穷性
确定性
输入0或多个
输出1或多个
可行性 正确的，可读性，健壮性

2、算法表达📌

  • 自然语言
  • 流程图⭐
  • 伪代码⭐
  • PAD图

3、设计方法📌

方法 思想
递推法 根据已知条件逐步推导出结果
递归法 将问题分解为相同类型的子问题，直到基本情况
穷举法 列出所有可能解并逐一检查
贪婪法 每步选择当前最优解，逐步逼近全局最优
分治法 将大问题分解为小问题，合并结果。
动态规划 通过记录子问题解，避免重复计算。
迭代法 通过重复计算逐步逼近目标。

注：排序📌

  1. 选择排序

    • 选择整列最小排到前面

       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
      void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        // 找到未排序部分的最小元素
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

        // 交换
        if (minIndex != i) {
            swap(arr[i], arr[minIndex]);
        }
    }
}

  2. 冒泡排序

    • 冒牌在前 从后往前

    • 冒泡在后 从前往后

      1
2
3
4
5
6
7
      for (i = 0; i < n - 1; i++) {
    for (j = 0; j < n - i - 1; j++) {
        if (arr[j] > arr[j + 1]) {
            // 交换 arr[j] 和 arr[j + 1]
        }
    }
}

  3. 插入排序

    • 逐一加入新元素排序

       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
      void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];  // 当前要插入的元素
        int j = i - 1;     // 已排序部分的最后一个元素

        // 将大于key的元素向后移动
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }

        // 插入key到正确位置
        arr[j + 1] = key;
    }
}

三、数据结构基础📌

数据结构三要素.svg

1、栈📌

2、队列📌

3、树📌

  • 最小生成树🌳

    Tip
    • 排序边（从小到大开始连接）
    • 连接未连通的块，已连通的跳过

4、图📌