【软件设计师—基础精讲笔记8】第八章 数据结构

一、线性结构

1、线性表

（1）线性表存储结构：顺序存储、链式存储。

【1】顺序存储

指用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。

• 优点：可以随机存取表中的元素；
  
• 缺点：插入和删除操作需要移动元素；
  

【2】链式存储

是用通过指针链接起来的节点来存储数据元素。其节点地址并不要求是连续的。

• 优点：插入和删除元素不需要移动元素
  
• 缺点：不能进行随机访问元素
  

根据结点中指针域的设置方式，还有其他几种链表结构。

双向链表。每个结点包含两个指针，分别指出当前元素的直接前驱和直接后继。其特点是可以从表中任意的结点出发，从两个方向上遍历链表。

循环链表。在单向链表(或双向链表) 的基础上令表尾结点的指针指向链表的第一个结点，构成循环链表。其特点是可以从表中任意结点开始遍历整个链表。

静态链表。借助数组来描述线性表的链式存储结构，用数组元素的下标表示元素所在结点的指针。

【3】顺序表和链表的对比

2、顺序表

2、栈和队列

栈按“后进先出”的规则进行操作，队列按“先进先出”的规则进行操作。

（1）栈

栈是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。换句话说，栈的修改是按先进后出的原则进行的。因此，栈又称为后进先出的线性表。在栈中进行插入和删除操作的一端称为栈顶，相应地，另一端称为栈底。不含数据元素的栈称为空栈。

栈的存储

顺序存储。栈的顺序存储是指用一组地址连续的存储单元依次存储自栈顶到栈底的数据元素，同时附设指针 top 指示栈顶元素的位置。

链式存储。用链表作为存储结构的栈也称为链栈。由于栈中元素的插入和删除仅在栈顶一端进行，因此不必另外设置头指针，链表的头指针就是栈顶指针。

（2）队列

队列是一种先进先出的线性表，它只允许在表的一端插入元素,而在表的另一端删除元素。在队列中,允许插入元素的一端称为队尾,允许删除元素的一端称为队头。

队列存储

顺序存储。是利用一组地址连续的存储单元存放队列中的元素。由于队列中元素的插入和删除限定在表的两端进行，因此设置队头指针和队尾指针，分别指出当前的队头和队尾。

链式存储。队列的链式存储也称为链队列。这里为了便于操作，给链队列添加一个头结点，并令头指针指向头结点。因此，队列为空的判定条件是头指针和尾指针的值相同，且均指向头结点。

》》》循环队列

队空条件：head=tail

队满条件：(tail+1)%size=head

3、字符串

存储结构：顺序存储、链式存储

（1）模式匹配

【1】布鲁特一福斯算法

其基本思想是从主串的第一个字符起与模式串的第一个字符比较，若相等，则继续逐一对字符进行后续的比较，否则从主串第二个字符起与模式串的第一个字符重新比较，直到模式串中每个字符依次和主串中一个连续的字符序列相等时为止，此时称为匹配成功。如果不能在主串中找到与模式串相同的子串，则匹配失败。

时间复杂度：最好O(n + m)；最坏O(n X m)

【2】KMP算法

其改进之处在于: 每当匹配过程中出现相比较的字符不相等时，不需要回退主串的字符位置指针，而是利用已经得到的“部分匹配”结果将模式串向右“滑动”尽可能远的距离，再继续进行比较。

二、数组、矩阵和广义表

1、数组

数组一般不做插入、删除运算，适合采用顺序存储结构。

对于数组存储位置的计算，可以理解为计算当前位置以要求的存储方式存放时，前面已经存放了多少个元素。

2、矩阵

特殊矩阵：若矩阵中元素的分布有一定的规律，则称之为特殊矩阵。常见的特殊矩阵有对称矩阵、三角矩阵和对角矩阵等。

稀疏矩阵：在一个矩阵中，若非 0 元素的个数远远少于 0 元素的个数，且非 0 元素的分布没有规律，则称之为稀疏矩阵。

3、广义表

广义表是线性表的推广，是由 0 个或多个单元素或子表组成的有限序列。

广义表的长度是指广义表中元素的个数。

广义表的深度是指广义表展开后所含的括号的最大层数。

（1）基本操作

取表头。非空广义表的第一个元素称为表头。

取表尾。除表头外，其余元素构成的表称为表尾。

（2）存储结构

通常采用链式存储结构

三、树

1、基本概念

结点的度：一个结点的子树的个数记为该结点的度。

叶子结点：度为0的结点。

树的高度：一棵树的最大层数记为树的高度。

有序树：树中结点的各子树从左到右是具有次序的，则称该树为有序树。

二叉树：结点最大度为2的树。左侧结点称左子树，右侧结点称右子树。

2、二叉树

（1）性质

》》》满二叉树：

》》》完全二叉树：深度为 k、有 n 个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从 1至 n 的结点一一对应时，称之为完全二叉树。

（2）存储结构

顺序存储

链式存储

（3）二叉树遍历

根据访问根节点位置不同，有3种遍历方法：前序、中序、后序。+ 层次遍历

前序：根，左，右

中序：左，根，右

后序：左，右，根

时间复杂度：O(n)；空间复杂度：最坏O(n)

（4）线索二叉树

（5）最优二叉树（哈夫曼树）

是一类带权路径长度最短的树。

构造方法

》》》哈夫曼编码

（6）树和森林

【1】树的存储

常用的树的存储有双亲表示法、孩子表示法和孩子兄弟表示法。

【2】树的遍历

先根遍历：树的先根遍历是先访问树的根结点，然后依次先根遍历根的各棵子树。对树的先根遍历等同于对转换所得的二叉树进行先序遍历。

后根遍历：树的后根遍历是先依次后根遍历树根的各棵子树，然后访问树根结点。树的后根遍历等同于对转换所得的二叉树进行中序遍历。

【3】树与森林、二叉树转换

《1》树转二叉树：一棵树可转换成唯一的一颗二叉树。转换后的二叉树，其根一定没有右子树。

《2》森林转二叉树：先把树转换成二叉树，再把转换后的二叉树，依次挂在所要构建的树的右子树上。

四、图

1、基本概念

有向图：<vi,vj>

无向图：（vi,vj）

完全图：图中每一个顶点与其他的各个顶点都有联系，称为完全图。无向完全图共有n(n-1)/2条边；有向完全图共有n(n-1)条弧。

度：顶点的度是指关联于该顶点的边的数目。

存储结构：邻接矩阵、邻接链表

邻接矩阵

邻接链表

2、图的遍历

2种：深度优先搜索、广度优先搜索。

（1）深度优先搜索

从图 G 中任结点v出发按深度优先搜索法进行遍历的步骤如下

(1) 设置搜索指针 p，使p 指向顶点 v。

(2) 访问 p 所指顶点，并使 p 指向与其相邻接的且尚未被访问过的顶点。

(3) 若 p 所指顶点存在，则重复步骤 (2)，否则执行步骤 (4)。

(4) 沿着刚才访问的次序和方向回溯到一个尚有邻接顶点且未被访问过的顶点，并使p 指向这个未被访问的顶点，然后重复步骤(2)，直到所有的顶点均被访问为止。

用邻接矩阵存储时，时间复杂度：O(n*n）；用邻接表存储时，时间复杂度：O(n+e)

（2）广度优先搜索

（1）从图中的某个顶点v出发，先访问v

（2）在访问了v之后，依次访问 v的各个未被访问过的邻接点

（3）按照“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”，分别从这些邻接点再出发依次访问它们的邻接点，直到图中所有已被访问的顶点的邻接点都被访问到

（4）若此时还有未被访问的顶点，则另选图中的一个未被访问的顶点作为起点，重复上述过程，直到图中所有的顶点都被访问到为止。

用邻接矩阵存储时，时间复杂度：O(n*n）；用邻接表存储时，时间复杂度：O(n+e)

3、生成树及最小生成树

常用的最小生成树算法：普里姆算法、克鲁斯卡尔算法。

（1）普利姆算法

普里姆算法构造最小生成树的过程是以一个顶点集合 U={v0}作为初态，不断寻找与 U中顶点相邻且代价最小的边的另一个顶点，扩充 可集合直到 U=V时为止。

（2）克鲁斯卡尔算法

克鲁斯卡尔算法是以选择权值最小的边为目标，直到图中所有顶点都在同一个连通分量上为止。

4、拓扑排序和关键路径

（1）拓扑排序

拓扑排序是将AOV网中的所有顶点排成一个线性序列的过程，并且该序列满足：若在 AOV网中从顶点 v到v有一条路径，则在该线性序列中，顶点v必然在顶点“之前。

（2）拓扑排序方法

(1) 在 AOV 网中选择一个入度为 0(没有前驱) 的顶点且输出它

(2) 从网中删除该顶点及与该顶点有关的所有弧

(3) 重复上述两步，直到网中不存在入度为 的顶点为止。

拓扑排序时间复杂度：O(n+e)

（3）关键路径

顶点事件的最早发生时间 ve(j)：ve(j)是指从源点 v0到vj 的最长路径长度(时间)。

顶点事件的最晚发生时间 vl(i)：vl(i)是指在不推迟整个工期的前提下，事件vi的最晚发生时间。

活动 ak的最早开始时间 e(k)：e(k)是指弧<i,j>所表示的活动 ak最早可开工时间。

活动 ak的最晚开始时间 l(k)：l(k)是指在不推迟整个工期的前提下，该活动的最晚开始时间。

5、最短路径

（1）单源点最短路径

（2）每对顶点间的最短路径

五、查找

1、基本概念

（1）平均查找长度

2、查找方法

（1）顺序查找

基本思想：从表的一端开始，逐个将记录的关键字和给定值比较，若找到个记录的关键字与给定值相等，则查找成功；若整个表中的记录均比较过，仍未找到关键字等于给定值的记录，则查找失败。

（2）折半查找

（3）分块查找

在分块查找过程中，首先将表分成若干块，每一块的关键字不一定有序，但块之间是有序的，即后一块中所有记录的关键字均大于前一个块中最大的关键字。此外，还建立了一个“索引表”，索引表按关键字有序。

因此，分块查找过程分为两步：第一步在索引表中确定待查记录所在的块；第二步在块内顺序查找。

3、动态查找表

（1）二叉排序树

二叉排序树又称二叉查找树，它或者是一棵空树，或者是具有以下性质的二叉树。

• (1) 若它的左子树非空，则左子树上所有结点的值均小于根结点的值。
  
• (2) 若它的右子树非空，则右子树上所有结点的值均大于根结点的值。
  
• (3) 左、右子树本身是二叉排序树。
  

【1】查找过程

【2】插入过程

【3】删除过程

（2）平衡二叉树

它或者是一棵空树，或者是具有下列性质的二叉树。它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差的绝对值不超过 1。

【1】查找过程

【2】插入过程

【3】删除过程

（3）B-树

4、哈希表

解决冲突的方法

（1）开放定址法。线性探测

（2）链地址法。把冲突形成一个链表

（3）在哈希法。

（4）公共溢出法。

六、排序

1、基本概念

稳定排序：能保证两个相等的数，排序前的位置和排序后的位置不变。

不稳定排序：不能保证顺序相同。

2、简单排序

（1）直接插入排序

对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

（2）冒泡排序

比较相邻的元素，如果前一个比后一个大，就调换位置。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。

（3）简单选择排序

从初始序列中找到最小元素，放到起始位置作为已排序序列；然后，再从剩余未排序元素中继续寻找最小元素，放到已排序序列的末尾。以此类推。

3、希尔排序

将待排序数组按照步长gap进行分组，然后将每组的元素利用直接插入排序的方法进行排序；每次将gap折半减小，循环上述操作；当gap=1时，利用直接插入，完成排序。

4、快速排序

从序列中挑出一个元素，作为"基准"；再把所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准的后面；对每个分区递归地进行以上操作，递归的结束条件是序列的大小是0或1，这时整体已经被排好序了。

5、堆排序

首先将序列构建称为大顶堆，拿走堆顶的值；然后，对剩余n-1个序列元素进行调整，使其满足大顶堆的性质；重复以上步骤。

【1】构建初始大根堆

【2】调整为新堆过程 （输出最大值后，调整生成新堆）

6、归并排序

将已有的子序列合并，达到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

7、基数排序

将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

七、总 结

       笔记总结不易，如果喜欢，请关注、点赞、收藏。

完整笔记下载地址：（后续完成后更新）

基础精讲课件地址：（请关注、点赞、收藏后，私信我）

基础精讲视频地址：（请私信我）