TOC]

算法的特性

算法的定义及特征

可行性

确切性

有穷性

输入

输出

算法的复杂度

时间复杂度

空间复杂度

常见的书将复杂度

增长越快，复杂度越高

增长越慢，复杂度越低

如图 ：空白文档 - 图1

基础排序

复杂度与稳定性

空白文档 - 图2

冒泡排序

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int SIZE = 10;
  4. int arr[SIZE] = {2,7,8,4,36,78,1,91,42,13};
  5. int main(){
  6.     for(int i = 0 ; i < SIZE - 1; i++){
  7.         for(int j = 0 ; j < SIZE-1 -i; j++){
  8.             if(arr[j] > arr[j+1])
  9.                 swap(arr[j],arr[j+1]);
  10.         }
  11.     }
  12.     for(int x : arr) cout << x << " ";
  13.     return 0;
  14. }

选择排序

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int SIZE = 10;
  4. int arr[SIZE] = {2,7,8,4,36,78,1,91,42,13};
  5. int main(){
  6.     for(int i = 0 ; i < SIZE - 1; i++){
  7.         for(int j = i+1 ; j <= SIZE-1; j++){
  8.             if(arr[i] > arr[j]){
  9.                 swap(arr[i],arr[j]);
  10.             }
  11.         }
  12.     }
  13.     for(int x : arr) cout << x << " ";
  14.     return 0;
  15. }

字符数组与字符串

（字符串实际是让用null字符即‘\0’终止的一堆字符里）

字符串

C++提供了两种字符串表达形式

1、C语言风格字符串，再头文件cstring中

2、C++引入的string类，在头文件string中

string类型：

空白文档 - 图3

字符串的方法

空白文档 - 图4

存储、组织数据的方式

数据array

(顺序存储，需要用到连续内存间)

链表linked list

(随机存储，有效利用零碎的内存空间)

无论是数组还是链表，都是数据中的物理结构

数据结构中还有逻辑结构

逻辑结构是抽象且依附于物理结构

栈stack

先进后出应用：网易回溯，撤销操作

栈底bottom 栈顶top

数据的出战和入栈都在栈顶

队列 queue

先进先出应用：排队

对头front 队尾rear/back

我们插入数据在队尾，数据出头额在对头

树

一、树的基本概念

1.1 树的定义

树是一种非线性的数据结构，由n(n≥0)个有限节点组成一个具有层次关系的集合。

1.2 树的示意图

  1.     A        ← 根节点
  2.    / \
  3.   B   C      ← A的子节点
  4.  / \   \
  5. D   E   F    ← 叶节点

1.3 树的组成部分

根节点(Root): 树的最顶层节点(如A)

父节点/子节点: B是A的子节点，A是B的父节点

叶节点(Leaf): 没有子节点的节点(如D,E,F)

边(Edge): 连接两个节点的线

深度: 从根到该节点的边数(A深度为0，B为1，D为2)

高度: 从该节点到最深叶节点的边数

二、树的常见类型

2.1 二叉树

每个节点最多有两个子节点(左子节点和右子节点)

  1.    A
  2.   / \
  3.  B   C
  4. / \   \

D E F

2.2 满二叉树

每个节点都有0或2个子节点，且所有叶节点在同一层

  1.    A
  2.   / \
  3.  B   C
  4. / \ / \

D E F G

2.3 完全二叉树

除最后一层外，其他层都填满，且最后一层节点靠左排列

  1.    A
  2.   / \
  3.  B   C
  4. / \ /

D E F

三、树的应用场景

文件系统: 文件夹和文件的层级结构

组织结构图: 公司部门层级关系

家谱图: 家族成员关系

HTML DOM树: 网页元素嵌套关系

决策树: 机器学习中的分类模型

四、树的基本操作示意图

4.1 遍历方式

前序遍历: 根→左→右

中序遍历: 左→根→右

后序遍历: 左→右→根

4.2 查找操作

查找E节点路径: A → B → E

在C节点下插入G:

  1.    A
  2.   / \
  3.  B   C
  4. / \   \

D E G

n2：度数为2的节点，n1度数为1的节点，n0度数为0的节点

空白文档 - 图5

逻辑结构

空白文档 - 图6

树的几要素：

空白文档 - 图7

二叉树

空白文档 - 图8

满二叉树

空白文档 - 图9

完全二叉树

空白文档 - 图10

满二叉树与完全二叉树的关系：

空白文档 - 图11 空白文档 - 图12 空白文档 - 图13

使用总边数一致推导：

N0 = N2 + 1

空白文档 - 图14 capture_20250721171745042.jpg