第1章 绪论

_开篇_数据结构在学什么.pdf

数据结构在学什么？

• 如何用程序代码把现实世界的问题信息化

• 如何用计算机高效地处理这些信息从而创造价值

1.1 数据结构

数据结构的基本概念.pdf

• 数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

• 数据元素：数据的基本单位，通常作为一个整体进行考虑和处理。

• 数据项：一个数据元素可由若干数据项组成，数据项是数据元素的不可分割的最小单位。

---

• 数据对象：是具有相同性质的数据元素的集合，是数据的一个子集。

• 数据结构：指互相之间存在着一种或多种特定关系的数据元素的集合，包括逻辑结构，存储结构和对数据的运算。（数据元素都不是孤立存在的）

---

• 数据类型：是程序设计语言中的一个概念，它是一个值的集合和在此集合上的操作的总称。

  • 原子类型：其值不可再分的数据类型

  • 结构类型：其值可以再分解为若干分量的数据类型

• 抽象数据类型(ADT)：指一个数学模型以及定义在该模型上的一组操作，只取决于它的一组逻辑特性，用一个三元组表示(DSP)。

---

• 逻辑结构：是指数据之间关系的描述，与数据的存储结构无关。分为线性结构和非线性结构，通常分为四类结构：

  • 集合：结构中的数据元素除了同属于一种类型外，别无其它关系。

  • 线性结构：结构中的数据元素之间存在一对一的关系。（对应第2章 线性表、第3章 栈和队列、第4章 串）

  • 树型结构：结构中的数据元素之间存在一对多的关系。（对应第5章 树与二叉树）

  • 图状结构：或网状结构，结构中的数据元素之间存在多对多的关系。（对应第6章 图）

• 物理结构：是指数据结构在计算机中的表示，又称为数据的存储结构。它包括数据元素的表示和关系的表示，通常由四种基本的存储方法实现：

  • 顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系体现。存储密度大，有些操作（如插入、删除）效率较差。

  • 链式存储：逻辑上相邻的元素在物理位置上可以不相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。这种方式不要求存储空间连续，便于动态操作（如插入、删除等），但存储空间开销大（用于指针），且不能折半查找。

  • 索引存储：在存储元素信息的同时，还建立附加的索引表。索引表的每项称为索引项，一般形式是(关键字,地址)，指示存储结点的存储位置（下标）或存储区间端点（下标）。

  • 散列存储：又称哈希存储，通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将散列函数的值解释成关键字所在元素的存储地址。其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取。

• 数据的运算：施加在数据上的运算，包括运算的定义和实现。运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤

1.1.3 本节习题精选

选择题：题目、解析

综合题：题目、解析

1.2 算法

程序=数据结构+算法。

数据结构即如何用数据正确地描述现实世界的问题，并存入计算机；

算法即如何高效地处理这些数据，以解决实际问题

1.2.1 算法的基本概念

算法的基本概念.pdf

• 算法：是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。

• 算法的特性

  • 有穷性：一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成

  • 确定性：算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出

  • 可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来时间

  • 输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合

  • 输出：一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量

• 算法的设计目标

  • 正确性：算法应能够正确地解决问题

  • 可读性：算法应具有良好的可读性，以帮助人们理解

  • 健壮性：输入非法数据时，算法能适当地作出反应或进行处理，而不会产生莫名其妙的输出结果

  • 高效率：花的时间少，时间复杂度低

  • 低存储量：不费内存，空间复杂度低

注：算法和程序十分相似，但又有区别。程序不一定具有有穷性，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。一个算法若用程序设计语言来描述，则它就是一个程序。

1.2.2 算法的时间复杂度

事前预估算法的时间开销 $T(n)$ 与问题规模 $n$ 之间的关系

算法的时间复杂度.pdf

• 如何计算？

  1. 找到一个基本操作（最深层循环)

  2. 分析该基本操作的执行次数 $x$ 与问题规模 $n$ 的关系 $x=f(n)$

  3. $x$ 的数量级 $O(x)$ 就是算法时间复杂度 $T(n)$：$O(x)=T(n)$

• 常用技巧

  • 加法规则：$O(f(n))+O(g(n))=O(\max (f(n),g(n)))$

  • 乘法规则：$O(f(n))\times O(g(n))=O(f(n)\times g(n))$

  • 常对幂指阶： $O(1)<O({\log }_{2}n)<O(n)<O(2^n)<O(n!)<O(n^n)$

• 三种复杂度

  • 最坏时间复杂度：考虑输入数据“最坏”的情况。

  • 平均时间复杂度：考虑所有输入数据都等概率出现的情况。

  • 最好时间复杂度：考虑输入数据“最好”的情况。

• 注意：算法的性能问题只有在 $n$ 很大时才会暴露出来

【例】下列函数的时间复杂度是( )。

int func(int n) {

int i = 0, sum = 0;

while(sum < n) sum += ++i;

return i;

}

$A.O(\log n)$

$B.O(n^{\frac{1}{2}})$

$C.O(n)$

$D.O(n\log n)$

解：B。首先把 sum += ++i; 拆开，这是两个程序语句：++i; sum += i;，即先 i 自加，再 sum+i。基本运算不能直接推出，所以使用归纳法，i=1，sum=0+1;，i=2，sum=0+1+2;，令执行次数为 $t$，从而得到 $sum=0+1+\cdots +t=(1+t)t/2$，所以 $t+t^2<2n$，所以时间复杂度为 $O(n^{\frac{1}{2}})$。

1.2.3 算法的空间复杂度

算法的空间复杂度.pdf

• 普通程序：

  1. 找到所占空间大小与问题规模相关的变量

  2. 分析所占空间 $x$ 与问题规模 $n$ 的关系 $x=f(n)$

  3. $x$ 的数量级 $O(x)$ 就是算法空间复杂度 $S(n)$

• 递归程序：

  1. 找到递归调用的深度 $x$ 与问题规模 $n$ 的关系 $x=f(n)$

  2. $x$ 的数量级 $O(x)$ 就是算法空间复杂度 $S(n)$

1.2.5 本节习题精选

选择题：题目、解析

综合题：题目、解析