数据结构与算法 - 第1章: 概论

1.1 什么是数据结构与算法

数据结构的定义

• 数据结构 = 数据的组织 + 存储 + 运算
• 研究数据的逻辑结构、存储结构以及它们上面的运算

算法的定义

• 算法：解决特定问题的有穷指令集
• 算法具有输入、输出、有穷性、确定性和可行性

1.2 基本概念

数据的基本概念

• 数据：信息的载体，能输入到计算机中并被计算机程序识别和处理的符号的总称
• 数据元素：数据的基本单位，在程序中作为一个整体加以考虑和处理
• 数据项：构成数据元素的不可分割的最小单位

数据类型分类

基本数据类型

• 整数类型
• 实数类型
• 字符类型
• 布尔类型
• 指针类型
  • 32位系统中，指针占4个字节
  • 64位系统中，指针占8个字节

复合数据类型

• 数组
• 结构体
• 类

C++中结构体和类的区别：

• 结构体默认的访问权限是public
• 类默认的访问权限是private

1.3 数据结构的三要素

1. 逻辑结构

数据元素之间的逻辑关系，分为：

线性结构

• 有且仅有一个开始节点和终端节点
• 除开始节点外，每个节点有且仅有一个直接前趋
• 除终端节点外，每个节点有且仅有一个直接后继
• 例：线性表、栈、队列

树形结构

• 有且仅有一个根节点
• 每个节点有零个或多个子节点
• 例：树、二叉树

图状结构

• 每个节点可以有任意个前趋和后继
• 例：图

集合结构

• 数据元素之间除”属于同一集合”外无其他关系

2. 存储结构（物理结构）

数据元素及其关系在计算机存储器中的表示：

顺序存储

• 用一组连续的存储单元依次存储数据元素
• 逻辑上相邻的元素存储在物理位置相邻的存储单元中

链式存储

• 用任意的存储单元存储数据元素
• 数据元素的存储关系并不能反映其逻辑关系
• 需要用指针表示数据元素之间的逻辑关系

索引存储

• 在存储数据元素的同时，建立附加的索引表
• 索引表中的每一项称为索引项，由关键字和地址组成

散列存储

• 根据数据元素的关键字直接计算出该元素的存储地址

3. 数据的运算

针对某种逻辑结构，结合存储结构，可以对数据执行的运算包括：

• 运算的定义：针对逻辑结构，指出运算的功能
• 运算的实现：针对存储结构，指出运算的具体操作步骤

1.4 抽象数据类型（ADT）

ADT的定义

• 抽象数据类型：由用户定义的、表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称
• ADT = (D, S, P)
  • D：数据对象
  • S：D上的关系集
  • P：对D的基本操作集

ADT的特点

1. 抽象性：只描述数据对象的逻辑特性，不涉及具体实现
2. 封装性：将数据对象的表示和对数据对象的运算封装在一起
3. 信息隐藏：外部只能通过接口访问，内部实现细节被隐藏

Stack ADT 示例

template <class T>
class Stack {
public:
    void clear();           // 栈置空
    bool push(const T item); // 入栈
    bool pop(T & item);     // 出栈
    bool top(T& item);      // 读栈顶元素
    bool isEmpty();         // 判栈空
    bool isFull();          // 判栈满
};

1.5 算法的基本概念

算法的特性

1. 输入：算法具有0个或多个输入
2. 输出：算法至少有1个或多个输出
3. 有穷性：算法在有穷步骤之后终止
4. 确定性：算法的每一步骤都有确定的含义
5. 可行性：算法的每一步都必须是可行的

算法设计的要求

1. 正确性：算法应能够正确地解决求解问题
2. 可读性：算法应具有良好的可读性，便于阅读、理解和交流
3. 健壮性：算法应具有较好的容错性
4. 高效性：算法应具有较高的效率，这与算法的时间复杂度和空间复杂度相关

1.6 算法复杂度分析

大O表示法

定义

• 大O表示法（Big O Notation）：用于描述函数渐进行为的数学符号
• 表示算法在最坏情况下的复杂度上界
• 定义：如果存在常数 c > 0 和 n₀ > 0，使得当 n ≥ n₀ 时，有 f(n) ≤ c·g(n)，则称 f(n) = O(g(n))

大O表示法的特点

1. 渐进性：只关心 n 趋于无穷大时的情况，忽略低阶项和常数系数
2. 上界性：给出算法复杂度的上界，表示”不会比这个更坏”
3. 简化性：简化复杂度分析，便于算法比较

大O表示法的运算规则

1. 常数项忽略：O(3n) = O(n)，O(5) = O(1)
2. 低阶项忽略：O(n² + n + 1) = O(n²)
3. 最高阶项保留：O(2n³ + n² + n) = O(n³)
4. 加法规则：O(f(n)) + O(g(n)) = O(max(f(n), g(n)))
5. 乘法规则：O(f(n)) × O(g(n)) = O(f(n) × g(n))

时间复杂度

• 表示算法运行时间随输入规模增长的趋势
• 用大O记号表示：T(n) = O(f(n))

常见时间复杂度（由优到差）

1. O(1) - 常数时间

   • 算法执行时间不随输入规模变化
   • 例：数组按索引访问、栈的push/pop操作

2. O(log n) - 对数时间

   • 每次操作都能将问题规模减半
   • 例：二分查找、平衡二叉树的查找

3. O(n) - 线性时间

   • 算法执行时间与输入规模成正比
   • 例：线性查找、数组遍历

4. O(n log n) - 线性对数时间

   • 常见于高效的排序算法
   • 例：归并排序、堆排序、快速排序（平均情况）

5. O(n²) - 平方时间

   • 常见于双重循环算法
   • 例：冒泡排序、选择排序、插入排序

6. O(n³) - 立方时间

   • 常见于三重循环算法
   • 例：矩阵乘法的朴素算法

7. O(2ⁿ) - 指数时间

   • 算法执行时间呈指数增长
   • 例：递归计算斐波那契数列、TSP问题的暴力解法

复杂度增长对比

当 n = 1000 时的操作次数对比：

• O(1): 1 次
• O(log n): 约 10 次
• O(n): 1,000 次
• O(n log n): 约 10,000 次
• O(n²): 1,000,000 次
• O(2ⁿ): 2¹⁰⁰⁰ 次（天文数字）

空间复杂度

• 表示算法运行过程中临时占用存储空间大小的度量
• 同样用大O记号表示：S(n) = O(f(n))
• 包括：
  • 辅助空间：算法执行过程中临时占用的存储空间
  • 输入空间：存储输入数据所需的空间（通常不计入空间复杂度）

空间复杂度示例

• O(1)：原地排序算法（如堆排序）
• O(n)：需要额外数组的算法（如归并排序）
• O(n²)：需要二维数组的动态规划算法

二分查找算法示例

template <class Type>
int BinSearch(vector<Item<Type>*>& dataList, int length, Type k){
    int low=1, high=length, mid;
    while (low<=high) {
        mid=(low+high)/2;
        if (k<dataList[mid]->getKey())
            high = mid-1;
        else if (k>dataList[mid]->getKey())
            low = mid+1;
        else return mid;
    }
    return 0;
}

• 时间复杂度：O(log n)
• 空间复杂度：O(1)

1.7 问题求解的基本步骤

1. 问题分析：理解问题的本质和要求
2. 数学建模：将实际问题抽象为数学模型
3. 设计算法：针对数学模型设计求解算法
4. 编程实现：用程序设计语言实现算法
5. 测试调试：验证程序的正确性
6. 运行维护：保证程序正常运行并进行必要的维护

1.8 算法策略简介

贪心算法

• 在每一步选择中都做出在当前看来最好的选择
• 例：图着色问题中选择度数最大的顶点优先着色

分治算法

• 将原问题分解为若干个规模较小但结构与原问题相似的子问题
• 递归地求解这些子问题，然后将各子问题的解合并得到原问题的解

动态规划

• 通过把原问题分解为相对简单的子问题的方式求解复杂问题
• 与分治法不同，动态规划适用于子问题重叠的情况

回溯算法

• 采用试探的搜索策略
• 当发现不满足求解条件时，就”回溯”返回，尝试别的路径