数据结构 - 绪论
01.绪论
1. 概念
1.1 数据结构
- 数据 Data：信息的载体。能被计算机识别并处理的符号的集合。
- 数据元素 Data element：数据的基本单位，通常作为一个整体进行考虑和处理。一个数据元素往往由若干数据项组成。数据项是组成数据元素的不可分割的最小单位。
如学生的信息记录就是一个数据元素，它由学号、姓名、性别等组成。
-
数据对象 Data object：具有相同性质的数据元素的集合，是数据的一个子集。
-
数据类型 Data type：一个值的集合和定义在此集合上的一组操作的总称。
- 抽象数据类型ADT(
Abstract Data Type)：一个数学模型（逻辑结构）及在其上定义的一组操作。
- 抽象数据类型ADT(
-
数据结构 Data structure：相互之间存在一种或多种特定关系的数据元素的集合。数据结构包含三方面内容：逻辑结构、存储结构、数据的运算。
- 逻辑结构： 数据结构的逻辑抽象、数据元素之间的数学关系.
- 存储结构： 又称存储映像或结点，数据结构在计算机中的表示，也称物理结构.
::: tip 结点与节点
结点：数据结构的物理存储结构.
节点：在计算机网络中通常指拥有数据存储、转发能力的计算机设备终端.
在数据结构中两者可以通用，但前者常用.
:::
1.2 算法
1. 定义
算法通常是指按照一定规则解决某一类问题的明确和有限的步骤。
算法组成要素：操作、控制结构、数据结构
- 操作：
- 算术运算：加、减、乘、除。
- 关系比较：大于、小于、等于、不等于。
- 逻辑运算：与、或、非。
- 数据传输：输入、输出、赋值（计算）。
- 算法的控制结构：
算法的控制结构给出了算法的框架，决定了各操作的执行顺序。- 顺序结构：个操作依次进行。
- 选择结构：有条件是否成立来决定选择执行。
- 循环结构：有些操作要重复执行，直到满足某个条件才结束，这种控制结构也称为重复或迭代结构。
- 数据结构：
算法操作的对象是数据，数据的逻辑关系、存储方式和处理方式即是数据结构。
2. 特性
算法是满足下列性质的指令序列.
- 有穷性：一个算法总是执行有穷步数后结束，且每一步都在有穷时间内完成。
- 确定性：算法中每条指令必须有确切含义，没有二义性，只有唯一一条执行路径。对于相同的输入只有相同的输出。
- 可行性：算法是可执行的，其操作可以通过已经实现的基本操作执行有限次来实现。
- 输入：一个算法有零个或多个输入。
- 输出：一个算法有一个或多个输出。
3. 算法设计要求
- 正确性 correctness
- 没有语法错误
- 对于精心选择的，苛刻的***难的数据也能输出正确的结果
- 程序对于一切合法的输入数据都能得到正确的输出结果
- 可读性 readability
- 健壮性 robustness
- 指当输入非法数据的时候，算法能够恰当的做出反应或进行相应处理，而不是输出莫名其妙的结果
- 处理出错的方法，不应是中断程序的执行，而应是返回一个表示错误或者错误性质的值，以便在更高抽象层次上进行处理
- 高效性 efficiency
要求算法花费尽量少的时间（时间效率）和尽量低的存储需求（空间效率）。
4. 计算机问题求解步骤
- 分析问题： 分析问题的输入、要求和输出.
- 数据结构设计： 选择或设计能有效表示和存储问题所涉及的数据对象的、能支持算法实现的数据结构.
- 算法设计： 选择算法策略、描述和逐步细化算法步骤.
- 算法分析： 完善改进数据结构和算法.
- 程序实现： 用某种编程语言定义数据结构、编写实现算法的代码并运行调试.
2. 数据结构的两种层次
2.1 逻辑结构
描述数据元素之间的逻辑关系，与数据的存储无关，独立于计算机；是从具体问题抽象出来的数学模型。
1. 线性结构
有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。
例如：线性表、栈（特殊线性表）、队列（特殊线性表）、串、数组、广义表等
2. 非线性结构
一个结点可能有多个直接前趋和直接后继。
例如：树 (一对多) 和 图 (多对多)
- 集合结构：数据元素除了“同属一个集合”外没有其他关系.
- 树：数据元素存在一对多的关系. 棋盘预测分析，数据像树木一样展开
- 图：数据元素存在多对多关系. 地图最短路径，数据像一张网格一样错综复杂
2.2 存储结构（物理结构）
数据元素及其关系在计算机存储器中的结构（存储方式）。
1. 顺序存储结构
用一组连续的存储单元依次存放数据。数据元素之间的逻辑关系由元素的存储位置来表示
C语言中的数组、C++中的vector容器都是顺序存储结构
- 优点： 实现随机存取、每个元素占用最少的存储空间
- 缺点： 只能使用相邻的一整块存储单元，可能产生较多的外部碎片
2. 链式存储结构
存储空间不连续，元素之间的逻辑关系用结点的指针表示。
- 优点： 不会出现碎片现象，充分利用所有存储单元。在表示各种逻辑结构时往往比顺序结构更加方便。
- 缺点： 指针额外占用存储空间、只能实现顺序存取。
3. 索引存储结构
建立附加的索引表，其中每项称为索引项
- 优点： 检索速度快。
- 缺点； 索引表额外占用存储空间。增删数据也要修改索引表
4. 散列(哈希)存储结构
根据元素的关键字直接计算出该元素的存储地址
- 优点： 检索、增删改查结点的操作都很快。
- 缺点： 若散列函数不好，可能出现存储单元冲突，解决冲突会增加时间和空间开销。
3. 算法和算法分析
3.1 时间复杂度
-
一个语句的频度是该语句在算法中被重复执行的次数。
-
算法运行时间=
$$\sum_{
\begin{subarray}{l}
\end{subarray}}语句的频度×语句执行一次所需时间$$ -
算法中所有语句的频度之和记为
T(n)，它是问题规模n的函数。时间复杂度主要分析T(n)的数量级。算法中基本运算（最深层循环内的语句）的频度与
T(n)同数量级。用
f(n)表示算法中的基本运算的频度。
若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于0的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度（O是数量级的符号），简称时间复杂度
用 O(f(n)) 表示 f(n) 中随 n 增长最快的项，将其系数置1作为时间复杂度的度量（渐进时间复杂度）。
T(n)=O(f(n)) 如f(n)=an3+bn2，则时间复杂度为O(n^3)
::: tip 问题规模n的含义
- 循环：条件判断执行次数
- 排序：n为数组中元素个数
- 矩阵：n为矩阵阶数或行列数
- 多项式：n为多项式的项数
- 集合：n为元素个数
- 树：n为树的节点个数
- 图：n为图的顶点数或边数
:::
计算时间复杂度重点是找到问题规模n与基本语句频度t之间的数学关系。
::: tip 时间复杂度具体求法
- 循环主体中的变量参与循环条件的判断
- 找出基本操作
- 设基本操作执行次数为T(n)，根据初始条件和基本操作语句确定变量与次数的关系式
- 带回循环条件，求出T(n)，确定O(n)
- 循环主体中的变量与循环条件无关
- 递归程序
- 确定递推关系（注意这里确定的是基本操作次数的递推关系，不要和变量的值搞混）
- 推出递推关系与执行次数的表达式
- 令低级递推关系中的次数为常数（0或1），整理式子
- 推导出T(n)
- 非递归程序
- 等比、等差数列求和
:::
- 等比、等差数列求和
- 递归程序
平均时间复杂度A(n)
- 最坏情况下的时间复杂度W(n).
算法求解输入规模为 n 的实例所需要的最长时间. - 平均状况下的时间复杂度A(n).
在给定同样规模为 n 的输入实例的概率分布下，算法求解这些实例所需要的平均时间.
设 S 是规模为 n 的实例集，实例 I∈S 的概率是 P_I
算法对实例I执行的基本运算次数是 t_I
在某些情况下可以假定每个输入实例概率相等.
example1
x=0,y=0 //1次
for(int k=0;k<n;k++) //n+1(判断语句执行n+1，循环体执行n)
x++; //n
for(int i=0;i<n;i++) //n+1
for(int j=0;j<n;j++) //n(n+1)
y++; //n*n
T(n)=O(n^2)
example2
for (i=1;i<n;i++) //
for (j=1;j<=i;j++)
for (k=1;k<=j;k++)
x=x+1;
第二重是 j 到 i，j是变量，相当于 1+2+3+…+i 等于i*（i+1）/2
example3
i=1;
while (i<=n)
i=i*2;//找出基本运算
设循环体执行次数为 $x$ ，令 $2^x≤n$，得$x≤log_2n$
$T(n)=O(log_2n)$
有时，$f(n)$（基本操作执行次数）随问题的输入数据集的不同而不同。
::: tip 加法规则和乘法规则
将复杂算法分解为几个部分，有
- 顺序：T(n)=T1(n)+T2(n)=O(max(
f(n)+g(n))) - 嵌套、循环：T(n)=T1(n)*T2(n)=O(
f(n)*g(n))
:::
渐进时间复杂度按递增顺序：
O(1) < O(log2n) < O(n) < O(nlog2n) < O(n^k) < O(2^n) < O(n!) < O(n^n)
3.2 空间复杂度
空间复杂度：该算法所耗费的存储空间，它是问题规模n的函数。
S(n)=O(g(n)).