本章重点
数据结构的研究内容
通常，用计算机解决一个问题的步骤：
- 具体问题抽象为数学模型
- 设计算法
- 编程、调试、运行
其中第一步的实质就是：
- 分析问题
- 提取操作对象
- 找出操作对象之间的关系
- 用数学语言描述 => 数据结构
随着计算机应用领域的发展，计算机越来越多的用于非数值计算领域。
举例
例一：学生学籍管理系统
操作对象：每位学生的信息(学号、姓名、专业…)
操作算法：查询、插入、修改、删除等。
操作对象之间的关系：线性关系
数据结构：线性数据结构、线性表
类似的还有图书管理系统、人事管理系统、仓库管理系统…
例二：人机对弈问题
之所以能对弈：策略已经输入计算机，可以根据当前棋盘格局，来预测棋局发展的趋势，甚至最后结局。
操作对象：各种棋局状态，即描述棋盘的格局信息。
算法：走棋，即选择一种策略使棋局状态发送变化(由一个格局派生出另一个格局)
操作对象之间的关系：非线性关系，树结构
更明显的树结构的例子就是：文件系统的系统结构图。
例三：地图导航—求最短路径
问题：找到图中两点之间的最短路径或最经济路径。
操作对象：各地点及路的信息。
算法：设置信号灯，求出各个可同时通行的路的集合。
对象之间的关系：非线性关系、网状结构
综上所述
- 这些问题的共性都是无法用数学的公式或方程来描述，是一些”非数学计算”的程序问题。
- 描述非数值计算问题的数学模型不是数学方程，而是诸如表、树和图之类的具有逻辑关系的数据。
- 数据结构是一门研究非数值计算的程序设计中计算机的操作对象以及它们之间的关系和操作的学科。
基本概念和术语
数据、数据元素、数据项和数据对象
- 数据
- 是能输入计算机且能被计算机处理的各种符号的集合
- 信息的载体
- 是对客观事物符号化的表示
- 能够被计算机识别、存储和加工
- 包括
- 数值型数据：整数、实数等
- 非数值型数据：文字、图像、图形、声音等
数据元素
- 是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
- 也简称为元素，或称为记录、结点或顶点。
- 一个数据元素可由若干个数据项组成
数据项
- 构成数据元素的不可分割的最小单位
关系图
数据、数据元素、数据项三者之间的关系：数据 > 数据元素 > 数据项
例如：学籍表 > 个人信息记录 > 学号、姓名…
数据对象
- 是性质相同的数据元素的集合，是数据的一个子集。
例如：
- 整数数据对象的集合是N = { …-1,0,1,2,… }
- 字母字符数据对象集合C = { ‘A’,’B’,’C’ … }
- 学籍表也可以看作一个数据对象
数据元素和数据对象
它们之间的关系：
- 数据元素——组成数据的基本单位
- 与数据的关系：集合的个体
- 数据对象——性质相同的数据元素的集合
- 和数据的关系：集合的子集
数据结构
数据元素不是孤立存在的，它们之间存在着某种关系，数据元素相互之间的关系称为结构。是指相互之间存在的一种或多种特定关系的数据元素集合，或者说，数据结构是带结构的数据元素的集合。
数据结构包括以下三个方面的内容：
- 数据元素之间的逻辑关系，也称为逻辑结构。
- 数据元素及其关系在计算机内存中的表示(又称为映像)，称为数据的物理结构或数据的存储结构，
- 数据的运算和实现，即对数据元素可以施加的操作以及这些操作在相应的存储结构上的实现。
数据结构的两个层次
逻辑结构：
- 描述数据元素之间的逻辑关系
- 与数据的存储无关，独立于计算机
- 是从具体问题抽象出来的数学模型
物理结构(存储结构)：
- 数据元素及其关系在计算机存储器中的结构(存储方式)
- 是数据结构在计算机中的表示
逻辑结构和存储结构的关系：
- 存储结构是逻辑关系的映像与元素本身的映像。
- 逻辑结构是数据结构的抽象，存储结构是数据结构的实现。
- 两者综合起来建立的数据元素之间的结构关系。
逻辑结构的种类
划分方法一
- 线性结构
- 有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。
- 例如：线性表(学籍表)、栈、队列、串
- 非线性结构
- 一个结点可能有多个直接前趋和直接后继。
- 例如：树(人机对弈问题)、图
划分方法二——四类基本逻辑结构
- 集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无其他任何关系。
- 线性结构：结构中的数据元素之间存在着一对一的线性关系。
- 树形结构：结构中的数据元素之间存在着一对多的层次关系。
- 图状结构或网状结构：结构中的数据元素之间存在着多对多的任意关系。
存储结构的种类
四种基本的存储结构：
- 顺序存储结构
- 链式存储结构
- 索引存储结构
- 散列存储结构
顺序存储结构：
- 用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。
- C语言中用数组来实现顺序存储结构。
链式存储结构
- 用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示。
- C语言中用指针来实现链式存储结构
索引存储结构
- 在存储结点信息的同时，还建立附加的索引表。
- 索引表中的每一项称为一个索引项。
- 索引项的一般形式是：(关键字,地址)
- 关键字是能唯一标识一个结点的那些数据项。
- 若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引。若一组结点在索引表中只对应一个索引项，则该所以把称之为稀疏索引。
- 如我们手机中的通讯录索引
散列存储结构
- 格局结点的关键字直接计算出该节点的存储地址。
- 在后面查找的章节中再详细讲解
数据类型和抽象数据类型
在使用高级程序设计语言编写程序时，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。
高级语言中的数据类型明显的或隐含的规定了在程序执行期间变量和表达的所有可能的取值范围，以及在这些数值范围上所允许进行的操作。
数据类型的作用：
- 约束变量或常量的取值范围。
-
数据类型
定义：数据类型是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称。
数据类型 = 值的集合 + 值集合上的一组操作抽象数据类型
定义：是指一个数学模型以及定义在此数学模型上的一组操作。
由用户定义，由问题抽象出数据模型(逻辑结构)。
- 还包括定义在数据模型上的一组抽象运算(相关操作)。
- 不考虑计算机内的具体存储结构于运算的具体实现算法。
抽象数据类型的形式定义
抽象数据类型可用(D, S, P)三元组表示。
其中：D是数据对象；S是D上的关系集；P是对D的基本操作集。
一个抽象数据类型定义格式如下：
ADT 抽象数据类型名 {数据对象:<数据对象的定义>数据关系:<数据关系的定义>基本操作:<基本操作的定义>} ADT 抽象数据类型名
其中，数据对象、数据关系的定义用伪代码描述。
基本操作的定义格式为：
- 基本操作名(参数表)
- 初始条件：<初始条件描述>
- 操作结构：<操作结果描述>
基本操作定义格式说明：
参数表：
- 赋值参数 只为操作提供输入值。
- 应用参数 以&打头(地址)，除可提供输入值外，还将返回操作结果。
初始条件：描述操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。若初始条件为空，则省略之。
操作结果：说明操作正常完成之后，数据结构的变化状况和应返回结果。
总结
抽象数据类型如何实现
- 抽象数据类型可用通过固有的数据类型(如整型、实型、字符型等)来表示和实现。
- 即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。
算法和算法分析
算法的定义：对特定问题的求解方法和步骤的一种描述，它是指令的有限序列，其中每个指令表示一个或多个操作。
算法的描述
- 自然语言：英语、中文
- 流程图：传统流程图、NS流程图
- 伪代码：类语言：类C语言
-
算法与程序
算法是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有多种算法。
- 程序是用某种程序设计语言对算法的具体实现。
- 程序 = 数据结构 + 算法
- 数据结构通过算法实现操作
- 算法根据数据结构设计程序
算法的五个特性
- 有穷性：一个算法必须是执行有穷步之后结束，且每一步都必须在有穷时间内完成。
- 确定性：算法中每一条指令必须有确切的含义，没用二义性。
- 可行性：算法是可执行的，算法描述的操作可以通过已经实现的基本操作执行有限次来实现。
- 输入：一个算法有零个或多个输入。
- 输出：一个算法有一个或多个输出。
算法设计的要求
- 正确性
- 算法程序没有语法错误。
- 算法程序对于合法的输入数据能够产生满足要求的输出结果。
- 算法程序对于非法的输入数据能够得到满足规格说明的结果。
- 算法程序对于精心选择的，甚至刁难的测试数据都有满足要求的输出结果。
- 可读性
- 算法应该利于人的理解
- 另一方面，晦涩难读的代码不易于排错和调试。
- 健壮性
- 当输入非法的数据时，算法做出相应的处理。
- 处理出错的方法，不应是中断程序的执行，而是返回一个表示错误或错误性质的值。
- 高效性
- 要求花费尽量少的时间和尽量低的存储需求
算法分析
概述
对于同一个问题，可以用许多不同的算法。那么如何判断这些算法的优劣程度呢？这就需要使用算法分析。
算法分析的目的是看算法是否实际可行，并在同一问题存在多的算法时可进行性能上的比较，以便从中挑选出比较优的算法。
一个号的算法首先要考虑算法设计的四个需求，在前三个需求都满足的情况下，主要考虑算法的效率，通过算法的效率高低来评判不同算法的优劣程度。
算法的效率主要体现在以下两方面：
- 时间效率：算法耗费的时间
- 空间效率：算法执行过程中所耗费的存储空间。
时间效率和空间效率有时候是矛盾的，我们需要综合考虑算法的各个要求。
算法时间效率的度量
- 算法时间效率可以根据该算法编制的程序在计算机上执行所消耗的时间来度量
- 两种度量方法
- 事后统计
- 将算法实现，测算其时间和空间开销。
- 缺点：编写程序需要消耗较多的时间和精力，并且实验结果还依赖于计算机软硬件等环境因素，掩盖了算法本身的优劣性。
- 事前分析
- 对算法所消耗资源的一种估算方法。
- 更加常用。
- 事后统计
事前分析方法：
算法运行时间 = 每条语句的执行次数 该语句执行一次所需的时间
每条语句执行一次所需的时间，一般是随机器时间而异的，是有机器本身软硬件环境决定的，它与算法无关。
所以，我们可假设执行每条语句所需的时间均为单位时间。此时对算法和运行时间的讨论就可转化为讨论该算法中所有语句的执行次数，即*频度之和。
这就可以独立于不同机器的软硬件来分析算法的时间性能了。
案例
两个n*n的矩阵相乘的算法可描述为：
for (i = 0; i <= n; i++) { // n+1次for (j = 1; j <= n; j++) { // n*(n+1)次c[i][j] = 0; // n*n次for (k = 0; k < n; k++) { // n*n(n+1)次c[i][j] = c[i][j] + a[i][k] * b[k][j]; // n*n*n次}}}
我们先计算每条语句的执行次数，如注释部分，然后将次数相加，即为该算法中每条语句的频度之和，则上述算法的时间消耗T(n)为：T(n) = 2n^3 + 3n^2 + 2n + 1
但是这也太麻烦了，有些算法的语句很多，一条一条计算也不太方便，其实还有一种方法，就是比较这个函数的数量级就行了。
例如：有两个不同的算法，时间消耗分别是： T1(n) = 10n^2 与 T2 = 5n^3 这两个哪个好呢？这里由于T1的数量级比较小，所有T1这个算法比较好。
若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于0的常数，则称f(n)和T(n)的同数量级函数。记作T(n) = O(f(n))，称O(f(n))为算法的渐进时间复杂度(O是数量级的符号)，简称时间复杂度。
回到矩阵相乘问题，算法耗费时间：
T(n) = 2n^3 + 3n^2 + 2n + 1
n -> 无穷时，T(n)/n^3 -> 2，这表示n充分大时，T(n)与n^3是同阶或同数量级，引入大”O”记号，则T(n)可记作：T(n) = O(n^3)，这就是求解矩阵问题的算法的渐进时间复杂度。
算法时间复杂度定义
算法中基本语句重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作：T(n) = O(f(n))
它表示随着n的增大，算法执行的时间的增长率和f(n)的增长率相同，称渐进时间复杂度。
基本语句：
- 算法中重复执行次数和算法的执行时间成正比的语句。
- 对算法运行时间贡献最大。
- 执行次数最多
问题规模n：
- n越大算法的执行时间越长。
- 排序：n为记录数
- 矩阵：n为矩阵的阶数
- 多项式：n为多项式的项数
- 集合：n为元素个数
- 树：n为树的结点个数
- 图：n为图的顶点数或边数
一般情况下，不必计算所有操作的执行次数，而只考虑算法中基本操作执行的次数，它是问题规模n的某个函数，用T(n)表示。
我们可以通过以下定理求时间复杂度更加简单：
若f(n) = a**mnm + am-1nm-1 + … + a1n + a0 是m次多项式，则 T(n) = O(nm**)。
忽略所有低次幂项和最高次幂系数，体现出增长率含义。
由定理可概括出，分析算法时间复杂度的基本方法：
- 找出语句频度最大的那条语句作为基本语句。
- 计算基本语句的频度得到问题规模n的某个函数f(n)。
- 取其数量级用符号”O”表示。
示例1：计算下列代码段的时间复杂度
int x = 0, y = 0;//循环1for (k = 0;k < n; k++) { // n+1次x++; // n次}//循环2for (i = 0; i < n; i++) { // n+1次for (j = 0; j < n; j++) { // n*(n+1)次y++; // n*n次}}
上面两个循环中，我们不用考虑过多的哪些次数加起来最多，我们只需要看循环2中循环次数最多的，即f(n)=n(n+1)，可得到T(n)=O(n2)，这就是算出来的时间复杂度。
示例2：计算下列代码段的时间复杂度
void exam (float x[][],int m,int n) {float sum[];for (int i = 0; i < m; i++) {sum[i] = 0.0;for (int j = 0; j < n; j++) {sum[i] += x[i][j]; // m*n次}}for ( i = 0; i < m; i++) {cout << i << ":" << sum[i] << endl;}}
我们直接看嵌套最深的语句就好了，这里嵌套最深的语句是mn次，即f(n)=mn，可得到T(n)=O(m*n)，时间复杂度是由嵌套最深层语句的频度决定的。
示例3：计算下列代码段的时间复杂度
int i = 1; //语句1while (i <= n) {i *= 2; //语句2}
关键是要找出来执行次数x与n的关系，并表示成n的函数
若循环执行一次：i = 12 = 2
若循环执行二次：i = 22 = 22
若循环执行三次： i = 222 = 23
若循环执行x次：i = 2x
设语句2执行次数为x次，由循环条件i<=n，所以2x<=n，x<=log2n
所以该程序段的时间复杂度T(n) = O(log2n)
时间复杂度特殊情况
请注意：有的情况下，算法中基本操作重复执行的次数还随着问题的输入数据集不同而不同，如：
//顺序查找，在数组a[i]中查找值等于e的元素，返回其所在位置。for (i = 0; i < n; i++) {if (a[i] == e) return i+1; //返回位置}return 0;
在以上这个算法中，查找的次数就分为三种情况：
- 最坏时间复杂度：最坏情况下时间复杂度。
- 平均时间复杂度：所以可能输入实例在等概率情况下，算法的期望运行时间。
- 最好时间复杂度：最好的情况下，算法的时间复杂度。
一般总是考虑最坏情况下的时间复杂度，以保证算法的运行时间不会比它更长。
对于复杂的算法，可以将它分成几个容易估算的部分，然后利用大O加法法则和乘法发展，计算算法的时间复杂度：
- 加法法则：
- 乘法法则：
当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。
时间复杂度T(n)按数量级递增顺序为：
| 常数阶 | 对数阶 | 线性阶 | 线性对数阶 | 平方阶 | 立方阶 | … | K次方阶 | 指数阶 |
|---|---|---|---|---|---|---|---|---|
| O(1) | O(log2n) | O(n) | O(nlog2n) | O(n2) | O(n3) | O(nk) | O(2n) |
复杂度由低到高
算法空间复杂度定义
空间复杂度：算法所需存储空间的度量，记作：S(n) = O(f(n))，其中n为问题的规模(或大小)
算法要占据的空间包括：
- 算法本身要占据的空间，输入/输出，指令，常数、变量等。
- 算法要使用的辅助空间。
示例：将一维数组a中的n个数逆序存放到原数组中。
【算法1】
for (i = 0; i < n/2; i++) {t = a[i];a[i] = a[n-i-1];a[n-i-1] = t;}
这个算法利用了二分查找的思维，只需要交换n/2次就可以完成任务，借用的变量t，就是此算法使用的辅助空间。
【算法2】
for (i = 0; i < n; i++) {b[i] = a[n-i-1];}for (i = 0; i < n; i++) {a[i] = b[i];}
这个算法借用了另一个数组的空间，通过把第一个数组逆序放到另一个数组中，再取回来的方法完成了任务。
分析：那么这两个算法的空间复杂度是多少呢？
- 算法1借用了一个临时变量，所以它的空间复杂度是S(n) = O(1)，也被称为原地工作。
- 算法2借用了一个和数组a一样大的数组b，所以它的空间复杂度为S(n) = O(n)。n越大，需要的空间越大。
- 可以看出，算法1的空间效率是更高的。
设计好算法的过程
抽象数据类型 = 数据逻辑结构 + 抽象运算(运算的功能描述)
- 针对数据逻辑结构可以采取不同的数据存储结构。
- 针对不同的存储结构我们可以有不同的算法。
- 针对不同的算法进行算法分析(时间复杂度 && 空间复杂度)
- 最后得到一个良好的算法
若有收获，就点个赞吧
0 人点赞
