程序设计基础
- 算法的特性
- 算法的复杂度
c++语言基础
基础排序
- 常见算法复杂度与稳定性
- 冒泡排序
常见算法
字符数组与字符串
- string类的函数（ strlen(s) ）
- 字符串的方法（ s.() ）
树

程序设计基础

算法的特性

算法的复杂度

时间复杂度
空间复杂度

c++语言基础

数据类型

函数

递归函数

示例：

例如编写一求1+2+..+n的值，其中n<=20

#include <iostream>
using namespace std;
int add(int n){
    if(n==1) {
        return 1;
    }
    return add(n-1) + n;
    1 + 2 + 3  
}
int main(){
    cout <<  add(4);
    return 0;
}

课堂练习：使用最优时间复杂度完成：平衡序列

课堂练习：寻找数字

课堂练习：（用求商取余法，不得使用条件判断）

机票打折

基础排序

常见算法复杂度与稳定性

冒泡排序

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

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

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

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

常见算法

字符数组与字符串

字符串定义：字符串实际上是用NULL字符即‘\0’终止的一维字符数组

string类的函数（ strlen(s) ）

字符串的方法（ s.() ）

树

一、树的基本概念

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 二叉树

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

       A
      / \
     B   C
    / \   \
   D   E   F

2.2 满二叉树

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

       A
      / \
     B   C
    / \ / \
   D  E F  G

2.3 完全二叉树

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

       A
      / \
     B   C
    / \ /
   D  E F

三、树的应用场景

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

四、树的基本操作示意图

4.1 遍历方式

前序遍历: 根→左→右
中序遍历: 左→根→右
后序遍历: 左→右→根

4.2 查找操作

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

4.3 插入操作

在C节点下插入G:
       A
      / \
     B   C
    / \   \
   D   E   G

一棵节点已知的二叉树，求至多有多少个节点有2个子节点公式：`2 * n2 + 1 + n1 = 10`

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

逻辑结构

树的几要素：

二叉树

满二叉树

完全二叉树

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

使用总边数一致推导：

N0 = N2 + 1

一、图的基本概念

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

二、顶点与边的关系

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. 后辍表达式中的除法处理
#### 计算规则：
1. 从左到右扫描表达式
2. 操作数压入栈
3. 遇到运算符时：
   - 弹出栈顶两个元素
   - **第一个弹出的是右操作数**
   - **第二个弹出的是左操作数**
#### 示例：`a b /`
1. 压入 a
2. 压入 b
3. 遇到 `/`：
   - 弹出 b (右)
   - 弹出 a (左)
   - 计算 a / b
### 3. 前辍表达式中的除法处理
#### 计算规则：
1. 从右到左扫描表达式
2. 操作数压入栈
3. 遇到运算符时：
   - 弹出栈顶两个元素
   - **第一个弹出的是左操作数**
   - **第二个弹出的是右操作数**
#### 示例：`/ a b`
1. 从右到左扫描：
   - 压入 b
   - 压入 a
2. 遇到 `/`：
   - 弹出 a (左)
   - 弹出 b (右)
   - 计算 a / b
## 四、记忆技巧
### 后辍表达式：
- 运算符"站在"操作数后面
- 计算顺序："后进先出，先右后左"
- 口诀："先出来的是右边的"
### 前辍表达式：
- 运算符"站在"操作数前面
- 计算顺序："先进后出，先左后右"
- 口诀："先出来的是左边的"
## 五、综合示例
### 中辍表达式：`(6 + 3) / (4 - 1)`
#### 1. 转换为后辍表达式：
- 步骤：`6 3 + 4 1 - /`
- 计算过程：
  1. 6, 3 → 遇到 + → 6 + 3 = 9
  2. 4, 1 → 遇到 - → 4 - 1 = 3
  3. 9, 3 → 遇到 / → 9 / 3 = 3
#### 2. 转换为前辍表达式：
- 步骤：`/ + 6 3 - 4 1`
- 计算过程：
  1. 从右到左：
     - 1, 4 → 遇到 - → 4 - 1 = 3
     - 3, 6 → 遇到 + → 6 + 3 = 9
  2. 9, 3 → 遇到 / → 9 / 3 = 3
## 六、课堂练习
1. 将 `(8 / 4) + (2 * 3)` 转换为：
   - 前辍表达式
   - 后辍表达式
   - 并说明除法运算的处理过程
2. 计算后辍表达式 `5 1 2 + 4 * + 3 -` 的值

第二章：程序设计基础