2025暑假笔记2

作者：第二章 - 图1

程序设计基础知识

算法的特性

第二章 - 图2

算法的复杂度

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

c++程序设计

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

算法的复杂度

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

c++语言基础

数据类型

第二章 - 图4

函数

第二章 - 图5

示例：

例如编写一求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. }

基础排序

常见算法复杂度与稳定性

第二章 - 图6

冒泡排序

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

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

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

  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 / \ B C / \ \ D E F

完全二叉树

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

满二叉树

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

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

D E F G

树的应用场景

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

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

家谱图: 家族成员关系

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

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

树的基本操作示意图