数据结构知识详解 第一章 绪论

知识框架

知识框架.png

1. 数据结构的基本概念

1.1 基本概念和术语

1.1.1 数据

定义：是信息的载体，是描述客观事实属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合

数据的组成：

• 整型、实型等数值类型
• 字符及声音、图像、视频等非数值类型

1.1.2 数据元素

定义：数据元素是数据的基本单位，通常作为一个整体进行考虑和处理，有一定意义的基本单位，在计算机中通常作为整体处理，也被称为元素、记录

数据元素组成：由若干数据项组成

例子：个人信息表的每一行就是一个数据元素

数据元素.png

1.1.3 数据项

定义：构成数据元素的不可分割的最小单位，若干数据项可以组成数据元素。
注：数据项是数据的最小单位

1.1.4 数据对象

定义：具有相同性质的数据元素的组合，是数据的子集。

例子

数据对象.png

1.1.5 抽象数据类型

定义：抽象数据组织及与之相关的操作

组成：

• 数据对象
• 数据关系
• 基本操作集

抽象数据类型的标准格式：

抽象数据类型的标准格式.png

1.1.6 数据类型

定义：一个值的集合和定义在此集合上的一组操作的总称

作用：

• 用来说明变量或表达式的取值范围
• 说明所能进行的操作

分类：

• 原子类型
  定义：值不可再分的数据类型
  例子：int整型
• 结构类型
  定义：值可以再分为若干成分(分量)的数据类型
  例子：int整型
• 抽象数据类型
  定义：值可以再分为若干成分(分量)的数据类型
  例子：int整型

1.1.7 数据结构

定义：相互之间存在一种或多种特定关系的数据元素的集合

数据结构三要素：

• 逻辑结构
  对问题抽象后进行研究
• 存储结构
  对具体细节进行研究
• 数据的运算

1.2 数据结构三要素

1.2.1 数据的逻辑结构

逻辑结构是指数据对象中数据元素之间的逻辑关系，即从逻辑关系上描述数据。

数据的逻辑结构.png

1. 线性结构：

定义：结构中的数据元素之间只存在一对一的关系

例子

线性结构.png

2. 非线性结构：

定义：结构中数据元素之间存在非一对一关系

树形结构

一对多关系

树形结构.png

图形结构

多对多关系

图形结构.png

集合

除同属一个集合外，再无其他关系

集合.png

1.2.2 数据的存储结构

定义：数据对象在计算机中的存储表示，也称为物理结构

数据域：数据元素由若干个数据项构成时，数据项的表示称为数据域

数据结构的存储方法：

1. 顺序存储方法

定义：将逻辑上相邻的节点存储在物理位置上也相邻的存储单元中，节点之间的关系由存储单元的邻接关系来体现

优点：

• 可以实现随机存取（也可以顺序存取）
• 每个元素占用最少的空间

缺点：

• 只能使用相邻的一整块存储单元，可能产生较多的外部碎片

存取结构

• 随机存取：就是存取第N个数据时，不需要访问前(N-1)个数据，直接就可以对第N个数据操作
• 非随机存取（又称顺序存取）：就是存取第N个数据时，必须先访问前(N-1)个数据

2 链式存储方法：

定义：不要求逻辑上相邻的节点在物理位置上也相邻，借助指示节点存储地址的指针来表示节点之间的逻辑关系

优点：

• 不会出现碎片现象，能充分利用所有存储单元

缺点：

• 每个元素因存储指针而占用额外的存储空间
• 只能顺序存取

注：

• 节点内存储单元地址：一定连续
• 相邻节点存储空间：不一定连续

3. 索引存储方法

定义：存储元素信息时，建立附加的索引表

优点：

• 检索速度快

缺点：

• 附加的索引表额外占用空间
• 增、删数据时也要修改索引表，会花费更多的时间

注：

• 索引表的每项称为索引项，索引项的一般形式是<关键字，地址>
• 关键字：标识唯一一个节点
• 地址：指向上述节点的指针

4. 散列（Hash）存储方法

定义：根据节点的关键字直接计算出该节点的存储地址，形如location = Hash(key)

优点：

• 检索、增加和删除节点操作很快

缺点：

• 散列函数不好，会出现元素存储单元冲突，解决冲突会增加时间和空间开销

注：

• 该方法本质上是顺序存储方法的扩展
• key：关键字
• Hash()：计算地址的方法，散列函数
• location：存储该节点的地址

1.2.3 数据的运算

定义：施加在数据上的运算，包括运算的定义、实现

注：

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

2 算法和算法评价

2.1 算法的基本概念

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

2.1.1 指令

指令能被人或机器等计算装置执行，可以是计算机指令，也可以是我们平时的语言文字

1. 算法

为了解决某个或某类问题，需要把指令表示成一定的操作序列，操作序列包括一组操作，每一个操作都完成特定的功能

2. 算法例子

把大象装进冰箱：

• 指令1. 打开冰箱门
• 指令2. 把大象塞进去
• 指令3. 关上冰箱门

2.1.2 算法的5个特性

1. 有穷性

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

例子：
经常写出死循环的代码，这就是不满足有穷性

2. 确定性

每一条指令必须有确切的含义，相同的输入只能得出相同的输出，读者对其理解不会产生二义性

3. 可行性

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

4. 输入

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

5. 输出

输出是算法进行信息加工后得到的结果，无输出的算法是没有意义的

2.1.3 算法的评价（四个方面）

1. 正确性

算法能正确地解决求解问题

正确的层次：

1. 算法程序没有语法错误
2. 算法程序对于合法的输入数据能够产生满足要求的输出结果
3. 算法程序对于非法的输入数据能够得出满足规格说明的结果
4. 算法程序对于精心选择的，甚至刁难的测试数据都有满足要求的输出结果

层次1要求最低，层析4是最困难的，我们几乎不可能逐一验证所有的输入都得到正确的结果，一般情况下，把层次3作为一个算法是否正确的标准

2. 可读性

有助于人们阅读、理解和交流

3. 健壮性

输入非法数据时，算法能适当地做出反应或进行处理，而不是产生莫名其妙的错误

4. 高效率与低存储量需求

效率：指时间，效率越高越好，时间短的算法效率高。
存储量：指空间，存储量越低越好，指算法在执行过程中需要的最大存储空间。

2.2 算法效率的度量

2.2.1 度量标准

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

2.2.2 度量方法

1. 事后统计方法

主要是通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低

缺陷

• 必须依据算法事先编制好程序，通常需要花费大量的时间和精力
• 时间的比较依赖计算机硬件和软件等环境因素，有时会掩盖算法本身的优劣
• 所用的操作系统、编译器、运行框架等软件的不同，也可以影响它们的结果
• 程序的运行时间往往还与测试数据的规模有很大的关系，效率高的算法在小的测试数据面前往往得不到体验

2. 事前分析估算方法

在计算机程序编制前，依据统计方法对算法进行估算

程序在计算机上运行时所消耗的时间取决于下列因素：

1. 算法采用的策略和方法 —— 算法好坏的根本
2. 编译产生的代码质量 —— 由软件来支持
3. 问题的输入规模
4. 机器执行指令的速度

2.2.3 时间复杂度

1. 频度

定义：一个语句在算法中被重复执行的次数

2. T(n)

定义：算法中所有语句的频度之和

• n：表示该算法问题的规模
• T(n)是该算法问题规模n的函数
• 分析时间复杂度，主要是分析T(n)的数量级

3. 算法的基本运算

定义：最深处循环内语句

算法的基本运算的频度与T(n)同数量级

4. 算法时间复杂度

定义：用算法的基本运算的频度f(n)来分析

算法时间复杂度标记：T(n)=O(f(n))

1. O：T(n)的数量级
2. 常见阶的叫法
   O(1)：常数阶；O(2)：线性阶；O(logn)：对数阶；O(n²)：平方阶
3. 常见T(n)的大小关系
   O(1)≤O(log₂(n))≤O(n)≤O(n·log₂(n))≤O(n²)≤O(n³)≤O(2ⁿ)≤O(n!)≤O(nⁿ)
4. 复杂度计算规则
   • 加法规则
     T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))
   • 乘法规则
     T(n)=T1(n)T2(n)=O(f(n))O(g(n))=O(f(n)*g(n))
5. 影响时间复杂度的因素
   • 问题规模n
   • 输入数据的性质（输入数据的初始状态）
6. 最坏情况与平均情况
   • 最坏时间复杂度
     定义：最坏情况下的时间复杂度
   • 平均时间复杂度
     定义：所有输入等概率的情况下，算法期望运行的时间
   • 最好时间复杂度
     定义：最好情况下的时间复杂度

2.2.4 空间复杂度

算法的空间复杂度：记为S(n)，表示该算法所消耗的空间，它是问题规模n的函数

渐进空间复杂度：简称为空间复杂度，记为S(n)=O(g(n))

分析空间复杂度，只需分析除输入和程序之外的额外空间

2.2.5 分析时空复杂度的方法

1. 观察法（循环主体中变量与循环条件无关）

（1）计算方法：通过列举、归纳得出
（2）分类：

• 递归类：递归程序一般使用公式进行递推
  T(n)=1+T(n-1)=1+1+T(n-2)=···=n-1+T(1)即T(n)=O(n)
• 非递归类
  直接计数

（3）例子

• 递归类

  
  fun.png

时间复杂度为O(n)

• 非递归类

  
  求n的阶乘.png

时间复杂度为O(n²)

2. 设循环次数t方法（循环主体中变量与循环条件有关）

（1）计算方法：设t次结束
（2）例子

循环t次.png

时间复杂度为O(log₂(n))

制作不易，有帮助的话还希望能给个 一键三连 支持下，谢谢大家。