读书笔记

软件设计师学习-第三章 数据结构

wiki

本章知识点会涉及单选题型，约占 5 分

1. 线性结构

1. 线性表

基本操作有：插入、删除、查找等。

存储方式有：

  • 顺序存储：用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻
    • 优点：可以随机存取表中元素
    • 缺点：插入与删除需要移动元素
  • 链式存储：通过指针链接起来的结点来存储数据元素，有单链表、循环链表（循环单链表、循环双链表）等
    • 优点：插入与删除不需要移动元素
    • 缺点：不能对数据元素进行随机访问

2. 栈

栈是只能从一端来实现数据存储、检索的一种线性结构，又称为 “后进先出”（LIFO）的线性表。

  • 栈顶（Top）：进行插入和删除操作的一端
  • 栈底（Bottom）：栈的另一端

3. 队列

队列是一种 “先进先出”（FIFO）的线性表，即在表的一端插入元素，在另一端删除元素。

  • 队尾（rear）：允许插入元素的一端
  • 队头（front）：允许删除元素的一端

元素入队时，只需要修改队尾指针，出队时，只需要修改队头指针。

1. 循环队列

存储一定时，队尾指针会有上限值，当队尾指针达到上限时便无法通过修改队尾指针来添加元素。如若将顺序队列设置成环状结构，就可以维持入队、出队
操作：

  • 元素入队时，修改队尾指针 Q.rear = (Q.rear + 1) % MAXSIZE
  • 元素出队时，修改队头指针 Q.front = (Q.front + 1) % MAXSIZE

此时，当队头、队尾指针相同时，无法断定队列状态（空或满），有两种处理方式：

  • 设置标志位来区分
  • 牺牲一个存储单元，约定以 “队尾指针所指位置的下一个位置是队头指针” 来表示 “队列满” 的情况，头尾指针相同时为 “队列空”

2. 双端队列

要求元素进出队列必须在同一端口。

4. 串

串是仅由字符构成的有限序列，是一种线性表。基本概念包括：

  • 空串：长度为 0 的串，不包含任何元素
  • 空格串：由一个或多个空格组成的串
  • 子串：由串中任意长度的连续字符构成的序列称为子串。含有子串的串称为主串。空串是任意串的子串。
  • 串相等：指两个串长度相等且对应序号的字符也相同
  • 串比较：比较字符串编码码值

1. 模式匹配

子串的定位操作常称为串的模式匹配，子串也称模式串。

1. 朴素匹配算法

从主串第一个字符与模式串比较，相等继续，不等就从主串第二个字符重新开始比较，如果在主串找到与模式串相同的子串，称为匹配成功，否则失败。

时间复杂度：最好 O(n+m)，最差 O(n×m)。

2. KMP 算法

每当匹配过程中出现相比较字符不相等时，不需要回退主串的字符位置指针，而利用已得 “部分匹配” 结果将模式串向右滑动进行比较。主要是通过消除主串指针的回溯来提高匹配效率。

时间复杂度：最好 O(n+m)，最差 O(n×m)。

next 函数计算规律：

  1. 利用公式计算 next[j]=max{k|00...pk-1=pj-k...pj-1"}
  2. 计算第 n 位时，next[n] 的值来自于第 n-1 位的字符，通过跟第 next[n-1] 位字符比较，如果相同 next[n]=next[n-1]+1，如果不相同，就跟第 next[next[n-1]] 位的字符比较，就这样迭代直到相同的时候，加上1，如果实在没有，就为0

例如：设模式串为 abaabcac，next 值为 -1 0 0 1 1 2 0 1。

方法一：利用公式计算

j 0 1 2 3 4 5 6 7
模式串 a b a a b c a c
next -1 0 0 1 1 2 0 1
p下标 k=1,0=2 k=1,0=3 k=2,01=34 k=1,0=6
k 0<k<1 0<k<2 0<k<3 0<k<4 0<k<5 0<k<6 0<k<7

方法二：计算第 n 位

第0位，取 -1

第1位，取 0

第2位，第1位为 b ，与 next=0 位不等，取 0

第3位，第2位为 a ，与 next=0 位相等，取 1

第4位，第3位为 a ，与 next=1 位不等，再与 j=1 的 next=0 位相等，取 1

第5位，第4位为 b ，与 next=1 位相等，取 1+1=2

第6位，第5位为 c ，与 next=2 位不等，再与 j=2 的 next=0 位不等，取 0

第7位，第6位为 a ，与 next=0 位相等，取 1

2. 非线性结构

1. 二维数组

数组是定长线性表在维数上的拓展，即线性表中的元素又是一个线性表。

二维数组特点如下：

  • 数据元素数目固定，不能更改
  • 数据元素具有相同的类型
  • 数据元素的下标关系具有上下界约束且下标有序

二维数组的存储结构可以分为以行为主序和以列为主序。

设每个元素占用 L 个单元，m、n 为数组的行数和列数，Loc(a11) 表示元素 a11 的地址，存储的地址的计算公式：

  • 以行为主序优先为：Loc(aij)=Loc(a11)+((i-1)×n+(j-1))×L
  • 以列为主序优先为：Loc(aij)=Loc(a11)+((j-1)×m+(j-1))×L

2. 三对角矩阵

若以行为主序将 n 阶三对角矩阵 An×n 的非 0 元素 aij 存储在一维数组 B[k]（1≤k≤3×n-2）中，则元素位置之间的对应关系为：k=3×(i-1)-1+j-i+1+1=2i+j-2（1≤i，j≤n）

3. 树

树是 n（n≥0）个结点的有限集合，当 n=0 时，集合为空，称为空树。在任意一非空树中（n＞0），有且仅有一个称为根的结点，其余结点可以分成 m（m≥0）个不相交的有限结点的集合 T1,T2,…,Tm，其中每个 T1 又都是一棵树，并且称为根的子树。

1. 树基本概念

  • 双亲、孩子、兄弟：结点的子树的根称为该节点的孩子结点，相应地，该结点称为其子结点的双亲。具有相同双亲的结点互为兄弟。
  • 结点的度：一个结点拥有子树的个数称为该结点的度
  • 叶子结点：也叫终端结点，叶子结点是指度为 0 的结点
  • 内部结点：也叫非终端结点或分支结点，指除根结点外，度不为 0 的结点
  • 结点的层次：根为第一层，根的孩子为第二层，以此类推
  • 树的深度：一棵树的最大层数为该树的深度（或高度）
  • 有序、无序树：如果树中各结点的各个子树是从左到右有序排列且不能交换时，则称该树为有序树，否则称为无序树

2. 二叉树

二叉树与普通树的区别在于，二叉树中结点的子树分为左子树和右子树，另外，二叉树节点最大的度为 2。

3. 满二叉树与完全二叉树

  • 满二叉树：深度为 k 的二叉树有 2k-1 个结点，则称其为满二叉树。
  • 完全二叉树：在一个深度为 h 的完全二叉树中，除第 h 层外（最后一层），其他各层都是满的，第 h 层所有的结点都必须从左到右依次放置，不能留空，成为完全二叉树；有留空时，成为非完全二叉树。

4. 二叉树性质

  • 在二叉树的第 i 层上最多有 2i-1 个结点（i≥1）
  • 深度为 k 的二叉树最多有 2k-1 个结点（k≥1）
  • 对于任何一棵二叉树，如果其叶子结点数为 n0，度为 2 的结点数为 n2，则 n0=n2+1
  • 具有 n 个结点的完全二叉树的深度为 log2n + 1
  • 如果对一棵有 n 个结点的完全二叉树的结点按层序编号（从第 1 层到 log2n + 1 层，每层从左到右），则对任一结点 i（1≤i≤n）有：
    • 如果 i=1，则该结点是二叉树的根，无双亲；如果 i＞1，则该结点是 i/2
    • 如果 2i≤n，则该结点左子树的编号是 2i；否则，无左子树
    • 如果 2i+1≤n，则该结点右子树的编号是 2i+1；否则，无右子树

5. 二叉树存储结构

  • 二叉树的顺序存储：在采用顺序存储时，完全二叉树与一般二叉树相比节省了空间，这是因为一般二叉树需要添加一些 “虚结点” 而造成了空间的浪费
  • 二叉树的链式存储：二叉树的链式存储可以分为二叉链表和三叉链表的存储结构

6. 二叉树的遍历

二叉树的遍历方式

7. 哈夫曼树（最优二叉树）

哈夫曼树又称为最优二叉树，是一种带权路径长度最短的二叉树。

  • 路径：一个节点到另一个节点之间的通路
  • 路径长度：路径上的分支数目
  • 树的路径长度：从树根到每一个叶子节点之间的路径长度之和
  • 权：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权
  • 节点的带权路径长度：从根结点到该节点的路径长度与该节点权值的乘积
  • 树的带权路径长度：树中所有的叶子结点的带权路径长度之和

树的带权路径长度记为：WPL=(W1×L1+W2×L2+W3×L3+…+Wn×Ln)，N 个权值 Wi（i=1,2,…,n）构成一棵有 N 个叶结点的二叉树，相应的叶结点的路径长度为 Li（i=1,2,…,n）。

构造哈弗曼树的步骤如下：

  1. 根据给定的 n 个权值 {w1,w2,…,wn,}，构成 n 棵二叉树的集合 F={T1,T2,…,Tn}，其中每棵树 Ti 中只有一个带权为 wi 的根结点，其左、右子树均空；
  2. 在 F 中选取两棵权值最小的树作为左、右子树构造一棵新的二叉树，置新构造二叉树的根结点的权值为其左、右子树根结点的权值之和；
  3. 从 F 中删除这两棵树，同时将新得到的二又树加入到 F 中重复 2，3 步，直到 F 中只含一棵树时为止，这棵树便是最优二叉树（哈夫曼树）。
1. 哈夫曼编码
  • 等长编码：每个字符编制长度相同的编码称为等长编码。
  • 前缀码：任一字符的编码都不是另一个字符的编码的前缀，这种编码称为前缀码。前缀码用来设计长度不等的编码。
  • 哈夫曼编码：基于哈夫曼树的一种编码方式，又称为带权路径长度最短的二叉树

8. 树和森林

树的存储结构有 3 种：

  • 双亲表示法：以一段连续空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲结点到链表中的位置。特点是找双亲容易，找孩子难。
  • 孩子表示法：每一个结点有多个指针域，其中每个指针指向一个子树的根节点，我们把这种方法叫做多重链表表示法。特点是找孩子易，找双亲难。
  • 孩子兄弟表示法：任何一棵树，它的结点的第一个孩子如果是唯一的，它的右兄弟如果存在也是唯一的，设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。

树的孩子兄弟表示法为实现树、森林与二叉树之间的转换提供了可能。

4. 图

图是由集合 V 和 E 构成的二元组，记作 G=(V,E)，其中，V 是图中顶点的非空有限集合，E 是图中边的有限集合。

1. 图的基本概念

图的要素：

  • 路径：从顶点 vi 到 vj 的路径指所有路径的序列
  • 度：顶点的度指关联于该点的边数目。无向图的度指与顶点相连的边的数量，有向图的度是出度和入度之和。
  • 出度：出度指作为起点的有向边数目
  • 入度：入度是作为终点的有向边数目

图分类：

  • 有向图：所有边都有方向的图。定点关系用 vi, vj 表示，有向起点 vi 称为弧尾，有向终点 vj 称为弧头
  • 无向图：所有边都有方向的图
  • 完全图：若一个无向图有 n 个顶点，且其与其他 n-1 个顶点都有边，称为无向完全图，边都有方向的称为有向完全图
  • 子图：若有两个图 G=(V,E) 和 G’=(V’,E’)，如果 V’⊆V 且 E’⊆E，则称 G’ 为 G 的子图。图的子集，子图中的顶点和边都是原图中的元素。

图的描述：

  • 连通图：无向图中，从顶点 vi 到 vj 有路径，则称顶点 vi 和 vj 是连通的，任意两个顶点的都是连通的无向图，称为连通图
  • 连通分量：极大连通子图称为其连通分量
  • 强连通图：在有向图中的连通量，如果任意两个顶点之间都存在双向的路径的图
  • 强连通分量：在有向图中的连通分量
  • 网：边或弧带权值的图
  • 有向树：如果一个有向图恰好有一个顶点入度为 0，其余顶点入度均为 1，它就是一棵有向树

2. 图的存储结构

1. 邻接矩阵

邻接矩阵表示法是指用一个矩阵来表示图中顶点之间的关系。对于具有 n 个顶点的图 G=(V,E)，其邻接矩阵是一个 n 阶方阵且定点 A[i][j] 满足：

  • 等于 1，表示 (vi, vj) 是 E 中的边
  • 等于 0，表示 (vi, vj) 不是 E 中的边
2. 邻接表

邻接表表示法是指为图中的每一个顶点建立一个单链表。

3. 图的遍历

图的遍历可以分为深度优先遍历、广度优先遍历两种方式，深度优先遍历类似于二叉树的前序遍历，而广度优先遍历则相当于二叉树的层次遍历。

4. 生成树

  • 生成树：对一个具有 n 个点的连通图进行遍历，对于遍历后的子图，其包含原图中所有的点且保持图连通，最后的结构一定是一个具有 n-1 条边的树，通常称为生成树。
  • 最小生成树：就是对于一个有 n 个点的无向连通图的生成树，其包含原图中的所有点，且保持图连通的边权值总和最少的边。

最小生成树算法有：

  • 普里姆（Prim）算法：时间复杂度为 O(V*V)，适合稠密图
  • 克鲁斯卡尔（Kruskal）算法：时间复杂度 为 O(ElogE)，适合稀疏图

5. 拓扑排序和关键路径

1. AOV 网

在有向图中，以顶点表示活动，以有向边表示活动之间的优先关系，则称其为已顶点表示活动的网（Activity On Vertex network，AOV 网）。

AOV 图常代表一项工程计划，通过构造拓扑排序，来判断其中是否存在回路，即查看所有顶点是否在拓扑排序序列中。

2. AOE 网

在带权的图中，以顶点表示事件，以有向边表示活动，以边上的权值表示活动持续时间，则这种带权有向图称为用边表示活动的网（Activity On Edge network，AOE 网）。

AOE 图代表一项工程计划时，入度为 0 的点表示开始事件，称为源点，出度为 0 的点表示结束时间，称为汇点。

  • 关键路径：从源点到汇点的最长路径称为关键路径
  • 关键活动：关键路径上的所有活动都是关键活动，缩短关键活动可以缩短工期

顶点事件：

  • 最早发生时间 ve(j)：从源点 v0 到 vj 的最长路径（时间）
  • 最晚发生时间 vl(i)：在不推迟整个工期的前提下，时间 vi 的最晚发生时间

活动时间：

  • 活动 ak 的最早开始时间 e(k)
  • 活动 ak 的最晚开始时间 l(k)

3. 数据运算

1. 查找

1. 顺序查找

将待查的元素从头到尾与表中元素进行比较，如果存在，则返回成功；否则，查找失败。此方法效率不高。顺序查找的平均查找长度为 (n+1)/2。

2. 二分查找（折半查找）

二分查找的前提是元素有序（一般是升序）。

3. 哈希查找

将序列使用哈希函数进行对应计算，对于产生的冲突，哈希函数可以采用线性探测法解决冲突。

2. 排序

1. 直接插入排序

在插入第 i 个记录时，R1,R2,…,Ri-1 均已排好序，这时将第 i 个记录依次与 Ri-1,…,R2,R1 进行比较，找到合适的位置插入，插入位置及之后的记录依次向后移动。

最好情况下的时间复杂度为 O(n)，在最坏情况下的时间复杂度为 O(n2)。

2. 冒泡排序

通过相邻元素（i 与 i-1）之间的比较和交换，将排序码较小的元素逐渐从底层移向顶层。

冒泡排序的时间复杂度为 O(n2)。

3. 简单选择排序

每一趟从待排序的数据元素中选出最小的元素，顺序放在待排序数列的最前面，直到全部待排序的数据元素全部排完。

简单选择排序的时间复杂度为 O(n2)。

4. 希尔排序

先将整个待排元素序列分成若干个子序列（由相隔某个 “增量” 的元素组成）后分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。

希尔排序的时间复杂度为 O(n1.3)。

5. 快速排序

快速排序是对冒泡排序的一种改进。通过一趟排序将要排序的数据分成独立的两个部分，其中一部分的所有数据都比另外一部分的所有数据要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

最好情况下的时间复杂度为 O(nlog2n)，在最坏情况下的时间复杂度为 O(n2)。

6. 堆排序

对于堆这种数据结构所设计的排序方法。堆的性质：

  • 一棵完全二叉树
  • 每个节点的值都大于或等于其子节点的值，为最大堆；反之为最小堆

堆排序的基本思路是：对于一组待排序记录的关键字，首先按堆的定义排成一个序列（建立初始堆），之后输出堆顶最大关键字（对于大顶堆而言），然后将剩余的关键字再调整成新堆，从而得到次大关键字，如此反复，直到全部关键字排成有序序列为止。

堆排序的时间复杂度为 O(nlog2n)。

7. 归并排序

归并排序过程分为三步：

  • 分解：将 n 个元素分成各含 n/2 个元素的子序列
  • 求解：用归并排序对两个子序列递归地排序
  • 合并：合并两个已经排好序的子序列以得到排序结果

8. 总结

各种排序方法的性能比较

4. 其他

1. 关键码构造二叉排序树

  • 二叉树排序树：数值大小为 “左子树 < 树根 < 右子树” 的顺序
  • 关键码序列：数值序列

排序原则是：

  1. 第一个为根节点；
  2. 依次将后面的元素值与根节点比较，将第一个小于的，放在根的左子树上，第一个大于的，放在根的右子树上，然后从序列中删除该值；
  3. 不断的迭代循环步骤 2，直到序列为空。