第二章 程序设计基础知识

第一课 程序基本常识

1.算法的特性

第二章 程序设计基础知识 - 图1

2.算法的复杂度

  • 时间复杂度
  • 空间复杂度

3.常见的时间复杂度

  • 增长越快，复杂度越高
  • 增长越慢，复杂度越低

第二章 程序设计基础知识 - 图2

4.练习

第一课 程序基本常识

第二课 C++语言基础

1.数据类型

第二章 程序设计基础知识 - 图3

2.函数

第二章 程序设计基础知识 - 图4

3.递归函数

第二章 程序设计基础知识 - 图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. }

4.练习

第二课 C++语言基础

第三课 排序算法

1.常见算法复杂度与稳定性

第二章 程序设计基础知识 - 图6

2.冒泡排序

  • 小的元素会经由交换慢慢“浮”到顶端，就像泡泡一样，故名“冒泡排序”
  • 它的工作原理是，重复地走访过要排序的元素，依次比较两个相邻的两个元素，如果前面的数比后面的数大就把他们交换过来。
  • 走访元素的工作重复地进行，直到没有相邻元素需要交换
  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. }

3.选择排序

  • 从待排序的数据元素中选出最小的一个元素，存放在序列的起始位置
  • 然后再从剩余的未排序元素中寻找到最小元素，然后放到已排序的序列的后面
  • 以此类推，直到全部待排序的数据元素的个数为零
    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 = i ; j < SIZE; j++){
    8.           if(arr[i] > arr[j])
    9.               swap(arr[i],arr[j]);
    10.       }
    11.   }
    12.   for(int x : arr) cout << x << " ";
    13.   return 0;
    14. }

    4.排序算法作业

    第二章 程序设计基础知识 - 图7 第二章 程序设计基础知识 - 图8 第二章 程序设计基础知识 - 图9

    答案：B A D D A D B A B B C D

5.练习（题目和上面一样，二次练习，不要看答案！！！）

第三课 排序算法

第四课 基础算法

1.常见算法

第二章 程序设计基础知识 - 图10 第二章 程序设计基础知识 - 图11 第二章 程序设计基础知识 - 图12

2.练习

第四课 基础算法

第五课 字符数组与字符串

1.字符串定义

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

2.字符数组相关函数（函数(变量名)）

第二章 程序设计基础知识 - 图13

3.字符串（stl容器）相关函数（对象.函数(变量名)）

第二章 程序设计基础知识 - 图14

4.练习

第五课 字符数组与字符串

第六课 链表

1.数据结构

存储、组织数据的方式

例：数组 array

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

例：链表 linked list

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

2.总结

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

3.练习

《信息学奥赛一本通初赛真题解析》P79~82

第七课 栈和队列

1.栈（stack）

  • 特点：先进后出
  • 应用：网页回溯，撤销操作
  • 栈底：bottom
  • 栈顶：top
  • 数据的出栈和入栈都在栈顶

2.队列（queue）

  • 特点：先进先出
  • 应用：排队
  • 队头：front
  • 队尾：rear/back
  • 我们插入数据在队尾，数据出列在队头

3.练习

《信息学奥赛一本通初赛真题解析》P86~89

第八课 树

1.树的基本概念

1.树的定义

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

2.树的示意图

  1.         A        ← 根节点
  2.        / \
  3.       B   C      ← A的子节点
  4.      / \   \
  5.     D   E   F    ← 叶节点

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

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

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

3.完全二叉树

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

  1. #### ****
  3.        A
  4.       / \
  5.      B   C
  6.     / \ /
  7.    D  E F

3.树的应用场景

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

4.树的基本操作示意图

1.遍历方式

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

2.查找操作

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

3.插入操作

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

5.练习

  1. 《信息学奥赛一本通初赛真题解析》P95~102
  2. 已知结点的前序序列为ABCDEFG，中序序列为CBEDAFG，构造出二叉树，并写出：后序序列。

    答案：后序序列：CEDBGFA

二叉树： 360截图20250719212105312.jpg