程序设计基础

算法的特性

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

算法的复杂度

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

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

c++语言基础

数据类型

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

函数

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

递归函数

第二章：程序设计基础 - 图5

示例：

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

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

课堂练习： 使用最优时间复杂度完成：平衡序列

课堂练习：寻找数字

课堂练习：（用求商取余法，不得使用条件判断）

机票打折

基础排序

常见算法复杂度与稳定性

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

常见算法

第二章：程序设计基础 - 图7

第二章：程序设计基础 - 图8

第二章：程序设计基础 - 图9

字符数组与字符串

字符串定义： 字符串实际上是用NULL字符即‘\0’终止的一维字符数组

string类的函数 （ strlen(s) ）

第二章：程序设计基础 - 图10

字符串的方法 （ s.() ）

第二章：程序设计基础 - 图11

树

一、树的基本概念

1.1 树的定义

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

1.2 树的示意图

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

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

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

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

2.3 完全二叉树

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

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

三、树的应用场景

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

四、树的基本操作示意图

4.1 遍历方式

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

4.2 查找操作

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

4.3 插入操作

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