算法的特征

程序设计 - 图1

算法的复杂度

时间复杂度

空间复杂度

c++语言基础

数据类型

程序设计 - 图2

函数

程序设计 - 图3

递归函数

程序设计 - 图4

基础排序

常见算法复杂度与稳定性 程序设计 - 图5

冒泡排序

小的元素会经由交换慢慢“浮”到顶端，就像泡泡一样，故名“冒泡排序”。

它的工作原理是，重复地走访过要排序的元素，依次比较两个相邻的两个元素，如果前面的数比后面的数大就把他们交换过来。

走访元素的工作重复地进行，直到没有相邻元素需要交换

字符串定义

字符串实际上是用null字符即‘\0’终止的一维字符数组。

string类函数

程序设计 - 图6

字符串方法

程序设计 - 图7

常见算法

程序设计 - 图8 程序设计 - 图9

数据结构

数据结构加算法

数据结构：存储、组织数据的方式

数组 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. / \   \
  5. D   E   F

2.2 满二叉树

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

  1.     A
  2.    / \
  3.   B   C
  4.  / \ / \
  5. D  E F  G

2.3 完全二叉树

除最后一层外，其他层都填满，且最后一层节点靠左排列
  1.     A
  2.    / \
  3.   B   C
  4.  / \ /
  5. D  E F
三、树的应用场景
文件系统: 文件夹和文件的层级结构
组织结构图: 公司部门层级关系
家谱图: 家族成员关系
HTML DOM树: 网页元素嵌套关系
决策树: 机器学习中的分类模型
四、树的基本操作示意图
4.1 遍历方式
前序遍历: 根→左→右
中序遍历: 左→根→右
后序遍历: 左→右→根
4.2 查找操作
查找E节点路径: A → B → E
4.3 插入操作
在C节点下插入G:
  1.     A
  2.    / \
  3.   B   C
  4.  / \   \
  5. D   E   G
  6. 一、树的基本概念

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

1.2 树的示意图 A ← 根节点 / \ B C ← A的子节点 / \ \ 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.   / \   \
  5.  D   E   F

2.2 满二叉树 每个节点都有0或2个子节点，且所有叶节点在同一层

  1.      A
  2.     / \
  3.    B   C
  4.   / \ / \
  5.  D  E F  G

2.3 完全二叉树 除最后一层外，其他层都填满，且最后一层节点靠左排列

  1.      A
  2.     / \
  3.    B   C
  4.   / \ /
  5.  D  E F

三、树的应用场景

文件系统: 文件夹和文件的层级结构
组织结构图: 公司部门层级关系
家谱图: 家族成员关系
HTML DOM树: 网页元素嵌套关系
决策树: 机器学习中的分类模型

四、树的基本操作示意图

4.1 遍历方式
前序遍历: 根→左→右
中序遍历: 左→根→右
后序遍历: 左→右→根

4.2 查找操作

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

4.3 插入操作

在C节点下插入G:
  1.     A
  2.    / \
  3.   B   C
  4.  / \   \
  5. D   E   G

一棵节点已知的二叉树，求至多有多少个节点有2个子节点公式：2 * n2 + 1 + n1 = 10 n2：度数为2的节点，n1度数为1的节点，n0度数为0的节点 程序设计 - 图10 逻辑结构 程序设计 - 图11 程序设计 - 图12 树的几要素： 程序设计 - 图13 二叉树 程序设计 - 图14

一、图的基本概念

1.图的定义：由顶点(点)和边组成的结构
2.图的分类：
  1.   无向图：边没有方向
  2.   有向图：边有方向

二、顶点与边的关系

1. 基本关系

邻接关系：两个顶点之间有边直接相连
关联关系：边与顶点之间的关系

2. 数学表示

无向图：
边记为 (u,v)
顶点度数 = 关联边数
有向图：
边记为
出度/入度概念
三、特殊路径概念

1. 欧拉路径

经过图中每一条边且每边只经过一次的路径
条件：
无向图：恰好两个顶点度数为奇数
有向图：一个顶点入度=出度+1，另一个出度=入度+1，其余相等

2. 欧拉回路

起点和终点相同的欧拉路径
条件：
无向图：所有顶点度数为偶数
有向图：所有顶点入度=出度
前辍与后辍表达式

1. 表达式表示法

中辍表达式：运算符位于操作数中间 (如 a + b)
前辍表达式：运算符位于操作数前面 (如 + a b)
后辍表达式：运算符位于操作数后面 (如 a b +)

2. 表达式特性对比

中辍表达式特性：
人类最易读的形式
需要括号来明确优先级
运算符优先级规则复杂
计算顺序不明确
前辍表达式特性：
无需括号即可明确运算顺序
计算顺序从右向左
运算符优先级隐含在结构中
适合递归计算
计算机处理效率高
后辍表达式特性：
无需括号即可明确运算顺序
计算顺序从左向右
适合使用栈结构计算
运算符优先级隐含在结构中
计算机处理效率最高

三、除法运算详解

1. 中辍表达式中的除法

明确运算顺序：a / b 表示 a 除以 b
带括号的情况：(a + b) / (c - d)
除法的优先级高于加减法

2. 后辍表达式中的除法处理

计算规则：
从左到右扫描表达式
操作数压入栈
遇到运算符时：
弹出栈顶两个元素
第一个弹出的是右操作数
第二个弹出的是左操作数
示例：a b /
压入 a
压入 b
遇到 /：
弹出 b (右)
弹出 a (左)
计算 a / b

3. 前辍表达式中的除法处理

计算规则：
从右到左扫描表达式
操作数压入栈
遇到运算符时：
弹出栈顶两个元素
第一个弹出的是左操作数
第二个弹出的是右操作数
示例：/ a b
从右到左扫描：
压入 b
压入 a
遇到 /：
弹出 a (左)
弹出 b (右)
计算 a / b

四、记忆技巧

后辍表达式：
运算符”站在”操作数后面
计算顺序：”后进先出，先右后左”
口诀：”先出来的是右边的”
前辍表达式：
运算符”站在”操作数前面
计算顺序：”先进后出，先左后右”
口诀：”先出来的是左边的”

五、综合示例

中辍表达式：(6 + 3) / (4 - 1)
1. 转换为后辍表达式：
步骤：6 3 + 4 1 - /
计算过程：
6, 3 → 遇到 + → 6 + 3 = 9
4, 1 → 遇到 - → 4 - 1 = 3
9, 3 → 遇到 / → 9 / 3 = 3
2. 转换为前辍表达式：
步骤：/ + 6 3 - 4 1
计算过程：
从右到左：
1, 4 → 遇到 - → 4 - 1 = 3
3, 6 → 遇到 + → 6 + 3 = 9
9, 3 → 遇到 / → 9 / 3 = 3