第一节 什么是数据结构
一、学习目标
- 理解什么是数据结构
- 明确学习数据结构的意义
二、什么是数据结构
1. 引入问题
在计算机科学中，我们经常遇到各种类型的问题。通过以下三个典型问题，我们可以理解数据结构的重要性：
【问题一】建立学生电子信息档案
需要存储学生的各项信息（学号、姓名、性别、院系、专业、籍贯、成绩、获奖情况等），并且方便查询和管理。这类问题涉及大量同类型数据的存储和操作，适合使用线性表（表）结构来解决。
线性表是最基本、最简单、也是最常用的一种数据结构，一个线性表是n个具有相同特性的数据元素的有限序列。
【问题二】N皇后问题
有一个N×N的国际象棋棋盘，要求在上面放置N个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。这类问题具有明显的层次关系和分支特性，适合使用**树（树形结构）**来描述和求解。
树形结构是一种非线性的数据结构，它是由n（n≥0）个有限结点组成一个具有层次关系的集合。
【问题三】地图导航
把各地抽象为点，地点之间的路抽象为连接两点的线。我们可在图中解决和讨论诸如查找路径等问题。这类问题涉及多对多的复杂关系，适合使用**图（图形结构）**来表示。
图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为G(V,E)，其中G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
2. 数据结构的定义
以上三个问题不像数值类问题那样，可以建立合适的数学模型，利用数学方程来求解。我们找不到描述它们的数学方程，而在这几个问题的解决方案中，分别使用了表、树、图之类的数据结构。
三、学习数据结构的意义
1. 程序的本质
著名计算机科学家尼古拉斯·沃思提出了一个著名的公式：
这个公式告诉我们程序的本质是什么：程序的本质就是对确定的问题选择一种好的结构，加上设计一种好的算法。所以我们要想写出好程序，就必须有两方面的知识：算法和数据结构，这两方面正是我们这门课的学习内容。
2. 数据结构课程的内容
数据结构课程主要包含以下内容：
- 常用数据结构：学习各种基本数据结构（如线性表、栈、队列、树、图等）的定义、特性和实现方法
- 经典算法：学习与各种数据结构相关的经典算法，如排序、查找、遍历等
- 评价和优化：学习如何评价算法和数据结构的优劣，以及如何进行优化
- 实际问题解决：将所学知识应用于解决实际问题
第二节 初识算法
一、学习目标
- 掌握算法的定义、特点
- 掌握算法的常用描述方法
- 明确算法设计的要求
二、什么是算法
算法是解决问题的策略或步骤。著名计算机科学家D.E.Knuth在《The Art of Computer Programming》中给出定义：
三、算法的特性
一个算法必须具备以下五个基本特性：
| 特性 | 说明 |
|---|---|
| 有穷性 | 算法必须在执行有穷步之后结束，且每一步都可在有穷时间内完成。这是算法最基本的特征，保证了算法能够终止。 |
| 确定性 | 算法中的每一步运算都必须有确切的含义，不能产生歧义。并且，在任何条件下，算法只有唯一的执行路径。这保证了算法的执行结果是确定的。 |
| 可行性 | 算法中所描述的操作都必须在计算机可处理的范围内，即每个操作都可以通过已经实现的基本运算执行有限次来完成。 |
| 有输入 | 算法执行时，一般会接受一些数据的输入。输入可以是零个或多个，这些输入取自于某个特定的对象集合。 |
| 有输出 | 算法一定要给出一个或多个输出，也就是问题求解的结论。输出是算法对输入数据处理后的结果。 |
四、如何描述算法
算法的描述方法主要有以下几种：
1. 自然语言
使用人们日常使用的语言来描述算法。优点是通俗易懂，不需要专门的训练；缺点是容易产生歧义，不够精确，对于复杂的算法描述起来比较冗长。
2. 流程图
使用图形符号来描述算法。流程图用一些图框来表示各种操作，用箭头来表示算法执行的先后顺序。优点是直观形象，易于理解；缺点是画起来比较麻烦，对于复杂的算法，流程图会变得很大。
3. 高级语言
使用某种高级程序设计语言（如C、C++、Java、Python等）来描述算法。优点是可以直接在计算机上运行，验证算法的正确性；缺点是需要掌握具体的编程语言，且代码细节较多，有时会掩盖算法的主要思想。
4. 伪码语言（类C语言）
使用介于自然语言和高级语言之间的伪代码来描述算法。伪代码采用类似于高级语言的语法结构，但忽略具体的语法细节。优点是突出了算法主体，结构清晰，便于阅读和分析，比较接近程序，便于实现。这是数据结构课程中常用的算法描述方法。
五、怎样才是好算法
一个好的算法应该满足以下四个方面的要求：
| 要求 | 说明 |
|---|---|
| 正确性 | 算法应当满足具体问题的需求，这是最基本的要求。正确的算法能够对所有的合法输入数据都能产生满足规格说明要求的结果。 |
| 可读性 | 算法重在交流，其次才是机器的执行。好的可读性有助于人们对算法的理解。清晰的命名、适当的注释、良好的结构都有助于提高可读性。 |
| 健壮性 | 当算法面对非法输入数据时，要能适当做出反应或处理，而不是产生莫名其妙的输出结果。健壮性要求算法能够对输入数据进行合法性检查，并对非法数据做出恰当的处理。 |
| 效率与低存储 | 高效的算法指用时短，低存储指使用存储空间少。在满足正确性、可读性和健壮性的前提下，应该尽量提高算法的执行效率，减少存储空间的占用。 |
第三节 算法效率的衡量和评价
一、学习目标
- 掌握算法时间、空间性能评价方法
- 熟练掌握时间复杂度评价算法时间性能的方法
- 熟练掌握空间复杂度评价算法空间性能的方法
二、算法时间性能的评价
1. 引入问题
考虑计算a的1500000000次方的问题。如果使用简单的循环乘法，需要进行1500000000-1次乘法，效率极低。而使用快速幂算法，当n为15亿时，仅需要做约45次乘法！这说明不同算法的效率可能相差巨大，因此我们需要科学的方法来评价算法的时间性能。
2. 评价方法
评价算法时间性能通常有两种方法：
（1）事后统计法
依据算法编写出程序，不同算法的程序可通过一组或若干组相同的测试数据，利用计算机内部的计时功能来分辨其优劣。但这种方法有明显缺陷：
- 一是需要将算法编写为程序
- 二是程序的运行时间受到计算机的硬件、软件等因素的影响，会掩盖算法的本质
（2）事前分析估算法
不需要将算法实现为程序，抛开了计算机环境因素的影响，通过对算法本身的分析，计算出算法的时间性能。该方法认为一个特定算法的运行工作量的大小，只依赖于问题的规模，或者说是问题规模的函数。
3. 时间复杂度
设n为问题规模，T(n)为算法的时间复杂性，它描述算法执行过程中所需的时间用量与问题规模n之间的函数关系。
首先，计算算法中原操作重复执行的次数，它是问题规模的函数，将它记为f(n)，以此作为算法时间的度量。
这表示随问题规模n的增大，算法的执行时间的增长趋势和f(n)的增长趋势相同，称作算法的渐进时间复杂度，简称时间复杂度。在同一问题中，可根据时间复杂度判定算法时间效率的优劣。
4. 常见时间复杂度
常见的时间复杂度及其增长趋势如下表所示：
| 时间复杂度 | n=1 | n=2 | n=4 | n=8 | n=16 | n=32 |
|---|---|---|---|---|---|---|
| 常数阶 O(1) | 1 | 1 | 1 | 1 | 1 | 1 |
| 对数阶 O(logn) | 0 | 1 | 2 | 3 | 4 | 5 |
| 线性阶 O(n) | 1 | 2 | 4 | 8 | 16 | 32 |
| 线性对数阶 O(nlogn) | 0 | 2 | 8 | 24 | 64 | 160 |
| 平方阶 O(n²) | 1 | 4 | 16 | 64 | 256 | 1024 |
| 指数阶 O(2ⁿ) | 2 | 4 | 16 | 256 | 65536 | 4.3×10⁹ |
| 阶乘阶 O(n!) | 1 | 2 | 24 | 40326 | 2.1×10¹³ | 2.6×10³⁵ |
三、算法空间性能的评价
1. 空间复杂度
空间复杂度记作S(n)，通常也表示为大O(f(n))。它描述算法执行过程中所需的存储空间与问题规模n之间的函数关系。
2. 算法占用内存空间的成分
算法在运行过程中占用的内存空间主要包括以下几个部分：
- 输入的数据：算法处理所需的原始数据所占用的存储空间
- 程序代码本身：编译后的程序代码所占用的存储空间
- 额外辅助空间：为实现算法所需的额外辅助空间，如临时变量、递归调用栈等
四、本节小结
算法的衡量与评价是数据结构课程的重要内容。通过时间复杂度和空间复杂度，我们可以科学有效地评价算法的性能优劣。在实际应用中，需要在时间效率和空间效率之间进行权衡，选择最适合具体问题的算法。