2025暑假笔记2

作者：

程序设计基础知识

算法的特性

算法的复杂度

-时间复杂度 -空间复杂度

c++程序设计

#include <bits/stdc++.h>
using namespace std;
int a(int x){
    if (x==1)return 1;
    return a(x-1)+x;
}
int main ()
{
int n;
cin>>n;
cout<<n;
    return 0;
}<bookstack-summary></bookstack-summary>

算法的复杂度

时间复杂度 空间复杂度

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;
}

数据结构

无论数组还是链表，都是数据结构中的物理结构 数据结构中还有逻辑结构 逻辑结果是抽象，依附于物理结构

数组

顺序存储，要用到连续的空间

链表

随机存储，有效利用碎片空间

栈

先进后出 栈底，顶 数据输出入都在栈顶

队列

先进后出 对头、队尾

树

树的定义

树是一种非线性的数据结构

树的示意图

每个节点最多有两个子节点(左子节点和右子节点) A / \ B C / \ \ D E F

完全二叉树

每个节点都有0或2个子节点，且所有叶节点在同一层 A / \ B C / \ / D E F

满二叉树

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

   A
  / \
 B   C
/ \ / \

D E F G

树的应用场景

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

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

家谱图: 家族成员关系

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

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

树的基本操作示意图

遍历方式

前序遍历: 根→左→右

中序遍历: 左→根→右

后序遍历: 左→右→根

查找操作

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

插入操作

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

一棵节点已知的二叉树，求至多有多少个节点有2个子节点公式：

2 * n2 + 1 + n1 = 10

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

逻辑结构

树的几要素：

二叉树

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

使用总边数一致推导： N0 = N2 + 1

图的基本概念

图的定义：

由顶点(点)和边组成的结构

图的分类：

无向图：边没有方向

有向图：边有方向

顶点与边的关系

顶点与边的关系

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

关联关系：边与顶点之间的关系

数学表示

无向图：

边记为 (u,v)

顶点度数 = 关联边数

有向图：

边记为

出度/入度概念

特殊路径概念

欧拉路径

经过图中每一条边且每边只经过一次的路径

条件：

无向图：恰好两个顶点度数为奇数

有向图：一个顶点入度=出度+1，另一个出度=入度+1，其余相等

欧拉回路

起点和终点相同的欧拉路径

条件：

无向图：所有顶点度数为偶数

有向图：所有顶点入度=出度

前辍与后辍表达式

表达式表示法

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

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

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

表达式特性对比

中辍表达式特性：

人类最易读的形式

需要括号来明确优先级

运算符优先级规则复杂

计算顺序不明确

前辍表达式特性：

无需括号即可明确运算顺序

计算顺序从右向左

运算符优先级隐含在结构中

适合递归计算

计算机处理效率高

后辍表达式特性：

无需括号即可明确运算顺序

计算顺序从左向右

适合使用栈结构计算

运算符优先级隐含在结构中

计算机处理效率最高

除法运算详解

中辍表达式中的除法

明确运算顺序：a / b 表示 a 除以 b

带括号的情况：(a + b) / (c - d)

除法的优先级高于加减法

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

计算规则：

从左到右扫描表达式

操作数压入栈

遇到运算符时：

弹出栈顶两个元素

第一个弹出的是右操作数

第二个弹出的是左操作数

示例：a b /

压入 a

压入 b

遇到 /：

弹出 b (右)

弹出 a (左)

计算 a / b

前辍表达式中的除法处理

计算规则：

从右到左扫描表达式

操作数压入栈

遇到运算符时：

弹出栈顶两个元素

第一个弹出的是左操作数

第二个弹出的是右操作数

示例：/ a b

从右到左扫描：

压入 b

压入 a

遇到 /：

弹出 a (左)

弹出 b (右)

计算 a / b

记忆技巧

后辍表达式：

运算符”站在”操作数后面

计算顺序：”后进先出，先右后左”

口诀：”先出来的是右边的”

前辍表达式：

运算符”站在”操作数前面

计算顺序：”先进后出，先左后右”

口诀：”先出来的是左边的”

综合示例

中辍表达式：(6 + 3) / (4 - 1)

转换为后辍表达式：

步骤：6 3 + 4 1 - /

计算过程：

6, 3 → 遇到 + → 6 + 3 = 9

4, 1 → 遇到 - → 4 - 1 = 3

9, 3 → 遇到 / → 9 / 3 = 3

转换为前辍表达式：

步骤：/ + 6 3 - 4 1 计算过程：

从右到左：

1, 4 → 遇到 - → 4 - 1 = 3

3, 6 → 遇到 + → 6 + 3 = 9

9, 3 → 遇到 / → 9 / 3 = 3