2025暑假笔记2

作者：第二章 - 图2

程序设计基础知识

算法的特性

第二章 - 图3

算法的复杂度

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

c++程序设计

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int a(int x){
  5.     if (x==1)return 1;
  6.     return a(x-1)+x;
  8. }
  9. int main ()
  10. {
  11. int n;
  12. cin>>n;
  13. cout<<n;
  14.     return 0;
  17. }<bookstack-summary></bookstack-summary>

算法的复杂度

时间复杂度 空间复杂度 第二章 - 图4

c++语言基础

数据类型

第二章 - 图5

函数

第二章 - 图6

示例：

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

  1.  #include <iostream>
  2. using namespace std;
  3. int add(int n){
  4.     if(n==1) {
  5.         return 1;
  6.     }
  7.     return add(n-1) + n;
  8.     1 + 2 + 3  
  9. }
  10. int main(){
  11.     cout <<  add(4);
  12.     return 0;
  13. }

基础排序

常见算法复杂度与稳定性

第二章 - 图7

冒泡排序

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

它的工作原理是，重复地走访

  • 过要排序的元素，依次比较两个相邻的两个元素，如果前面的数比后面的数大就把他们交换过来。

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

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

数据结构

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

数组

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

链表

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

栈

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

队列

先进后出 对头、队尾

树

树的定义

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

树的示意图

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

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

D E F

完全二叉树

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

满二叉树

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

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

D E F G

树的应用场景

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

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

家谱图: 家族成员关系

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

决策树: 机器学习中的分类模型 第二章 - 图8

树的基本操作示意图

遍历方式

前序遍历: 根→左→右

中序遍历: 左→根→右

后序遍历: 左→右→根

查找操作

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

插入操作

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

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

2 * n2 + 1 + n1 = 10

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

第二章 - 图9

逻辑结构

第二章 - 图10

第二章 - 图11

树的几要素：

第二章 - 图12

二叉树

满二叉树 第二章 - 图13 完全二叉树 第二章 - 图14 满二叉树与完全二叉树的关系： 第二章 - 图15

第二章 - 图16 第二章 - 图17 使用总边数一致推导： N0 = N2 + 1

第二章 - 图18

图的基本概念

图的定义：

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

图的分类：

无向图：边没有方向

有向图：边有方向

顶点与边的关系

顶点与边的关系

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

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

数学表示

无向图：

边记为 (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

回文检测

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main(){
  4. string str;
  5. cin>>str;
  6. int n=str.size();
  7. bool isplalindorme=true;
  8. for(int i=0;i<n/2;i++){
  9.     isplalindorme=false;
  10. }
  11. if(isplalindorme)
  12. cout<<"YES"<<endl;
  13. else
  14. cout<<"NO"<<endl;
  16.    return 0;
  17. }

找到第一个只有出现一次的数

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main(){
  4. int t[256];
  5. string s;
  6. int i;
  7. cin>>s;
  8. for(i=0;i<256;i++)
  9.     t[i]=0;
  10. for(i=0;i<s.length();i++)
  11. t[s[i]]++;
  12. for(i=0;i<s.length();i++)
  13. if(t[s[i]]){
  14.     cout<<s[i]<<endl;
  15.     return 0;
  16. }
  17. cout<<"no"<<endl;
  18.    return 0;
  19. }

排序算法

给定两个有序数列，合并成一个升序数列

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. void merge(vector<int>& arr, int left, int mid, int right) {
  4.     vector<int> temp(right - left + 1);
  5.     int i = left, j = mid + 1, k = 0;
  6.     // 合并：取较小值放入temp
  7.     while (i <= mid && j <= right) {
  8.         if (arr[i] <= arr[j]) temp[k++] = arr[i++];
  9.         else temp[k++] = arr[j++];
  10.     }
  11.     // 拷贝剩余元素
  12.     while (i <= mid) temp[k++] = arr[i++];
  13.     while (j <= right) temp[k++] = arr[j++];
  14.     // 拷贝回原数组
  15.     for (int idx = 0; idx < k; idx++) 
  16.         arr[left + idx] = temp[idx];
  17. }
  18. // 归并排序主函数
  19. void mergeSort(vector<int>& arr, int left, int right) {
  20.     if (left >= right) return; // 递归终止条件
  21.     int mid = left + (right - left) / 2;
  22.     mergeSort(arr, left, mid);   // 递归排序左半部
  23.     mergeSort(arr, mid + 1, right); // 递归排序右半部
  24.     merge(arr, left, mid, right);  // 合并有序数组
  25. }
  26. // 调用示例
  27. int main() {
  28.     vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
  29.     mergeSort(arr, 0, arr.size() - 1);
  30.     return 0;
  31. }

二分

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int arr[10]={0,11,22,33,44,55,66,77,88,99};
  4. int a(int x){
  5. int l=0,r=9+1;
  7. while(l+1<r){
  8. int m=(l+r)/2;
  9. if(x==arr[m]){
  10.     return m;
  11. }else if(x>arr[m]){
  12.     l=m;
  13. }else{
  14.     r=m
  15. }
  16. }
  17. return -1;
  18. }
  19. int main() {
  20. cout<<a(66);
  21.     return 0;
  22. }

意义不明

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int x[100],y[100],f[100];
  4. int n,j,m,a;
  5. int main(){
  6. cin>>n;
  7. for(int i=0;i<=n;i++ ){
  8.     cin>>x[i]>>y[i];
  9.     m=0;
  10. }
  11. for(int i=1;i<=n;i++){
  12.     f[i]=0;
  13.     for(j=1;j<=n;j++){
  14.         if(x[j]<x[i]&&y[j]<y[i]){
  15.             f[i]++;
  17.         }
  18.         if(f[i]>m){
  19.             a=1;
  20.         }
  21.     }
  22. }
  23.     return 0;
  24. }

意义不明

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int a[114514],b[114514];
  4. int n,j,m,a;
  5. int r(int x){
  6.     while(l+1<r){
  7. int m=(l+r)/2;
  8. if(x==arr[m]){
  9.     return m;
  10. }else if(x>arr[m]){
  11.     l=m;
  12. }else{
  13.     r=m
  14. }
  15. }
  16. return -1;
  17. }
  18. int main() {
  19. cout<<a(66);
  20.     return 0;
  21. }
  22. }
  23. int main(){
  24.     int n,m;
  25.     cin>>n>>m;
  26.     for(int i=1;i<=n;i++){
  27.         cin>>a[i];
  28.     }
  29. for(int i=1;i<=n;i++){
  30.         cin>>b[i];
  31.     }
  32.     sort(a+1,a+1+n);
  33.     sort(b+1,b+1+n);
  34.     for(int i=1;i<=m;i++){
  35.         if(r(b[i])){
  36.             cout<<b[i]<<" "
  37.         }
  38.     }
  39.     return 0;
  40. }