第二章 程序设计基础知识

第一课 程序基本常识

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

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

  2.        A
  3.       / \
  4.      B   C
  5.     / \ /
  6.    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

4.逻辑结构

1.数据结构

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

2.树的几要素

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

3.二叉树

满二叉树 第二章 程序设计基础知识 - 图18 完全二叉树 第二章 程序设计基础知识 - 图19 满二叉树与完全二叉树的关系 第二章 程序设计基础知识 - 图20 第二章 程序设计基础知识 - 图21 第二章 程序设计基础知识 - 图22 使用总边数一致推导

N0 = N2 + 1 第二章 程序设计基础知识 - 图23

5.二叉树公式

已知二叉树的节点数，求最多几个节点有两个子节点，公式如下：

2*n2+1+n1=节点数

n2：度数为2的节点

n1度数为1的节点

n0度数为0的节点

例题： 第二章 程序设计基础知识 - 图24

答案：A A

6.练习

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

答案：

后序序列：CEDBGFA

二叉树： 360截图20250719212105312.jpg

第九课 图

1.图的基本概念

1.图的定义

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

2.图的分类

  • 无向图：边没有方向
  • 有向图：边有方向

2.顶点与边的关系

1.基本关系

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

2.数学表示

  • 无向图
    • 边记为 (u,v)
    • 顶点度数 = 关联边数
  • 有向图
    • 边记为
    • 出度/入度概念

3.特殊路径概念

1.欧拉路径

  • 经过图中每一条边且每边只经过一次的路径
  • 条件：
    • 无向图：恰好两个顶点度数为奇数
    • 有向图：一个顶点入度=出度+1，另一个出度=入度+1，其余相等

2.欧拉回路

  • 起点和终点相同的欧拉路径
  • 条件：
    • 无向图：所有顶点度数为偶数
    • 有向图：所有顶点入度=出度

3.练习

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

附1：前缀与后缀表达式

1.表达式表示法

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

2.表达式特性对比

1.中辍表达式特性：

  • 人类最易读的形式
  • 需要括号来明确优先级
  • 运算符优先级规则复杂
  • 计算顺序不明确

2.前辍表达式特性：

  • 无需括号即可明确运算顺序
  • 计算顺序从右向左
  • 运算符优先级隐含在结构中
  • 适合递归计算
  • 计算机处理效率高

3.后辍表达式特性：

  • 无需括号即可明确运算顺序
  • 计算顺序从左向右
  • 适合使用栈结构计算
  • 运算符优先级隐含在结构中
  • 计算机处理效率最高

附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

附3：记忆技巧

1.后辍表达式：

  • 运算符”站在”操作数后面
  • 计算顺序：”后进先出，先右后左”
  • 口诀：”先出来的是右边的”

2.前辍表达式：

  • 运算符”站在”操作数前面
  • 计算顺序：”先进后出，先左后右”
  • 口诀：”先出来的是左边的”

附4：综合示例

1.中辍表达式：(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
  2. 3, 6 → 遇到 + → 6 + 3 = 9
  3. 9, 3 → 遇到 / → 9 / 3 = 3

附5：课堂练习

  1. 将 (8 / 4) + (2 * 3) 转换为：
    • 前辍表达式
    • 后辍表达式
    • 并说明除法运算的处理过程
  2. 计算后辍表达式 5 1 2 + 4 * + 3 - 的值

你学废了吗？？？，想学更多编程就找HNAI！！！

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