计算机系列之数据结构

19、数据结构（重点、考点）

1、线性结构

在这里插入图片描述

线性结构：每个元素最多只有一个出度和一个入读，表现为一条线状。线性表按存储方式分为顺序表和链表。

1、顺序存储和链式存储

存储结构：

顺序存储：用一组地址连续的存储单元依次存储线性表中的数据元素，使得逻辑上相邻的元素物理上也相邻。

链式存储：存储各数据元素的结点的地址并不要求是连续的，数据元素逻辑上相邻，物理上分开。

顺序存储，比如数字 1,2,3,4 按顺序存储，在内存地址上也是连续的，比如 1 存在 8地址上，2存在9地址上，3存在10地址上，4存在11地址上。

链式存储：比如数字1,2,3,4，但物理上比如 1存在 12地址上，2存在7地址上，3存在15地址上，4存在20地址上。此时知道数字1及数字1的地址12之后，如何拿到数字2、3、4的地址呢？这个时候就需要指针了，即指向下一个或上一个相邻数字的存储地址。

顺序存储和链式存储的对比如下图所示：

在这里插入图片描述

在空间方面，因为链表还需要存储指针，因此有空间浪费存在。

在时间方面，当**需要对元素进行破坏性操作（插入、删除）时，链表效率更高，**因为其只需要修改指针指向即可，而顺序表因为地址是连续的，当删除或插入一个元素后，后面的其他节点位置都需要变动。

而当需要对元素进行**不改变结构操作时（读取、查找），顺序表效率更高，**因为其物理地址是连续的，如同数组一般，只需按索引号就可快速定位，而链表需要从头节点开始，一个个的查找下去。

2、栈和队列

队列、栈结构如下图，队列是先进先出，分队头和队尾；栈是先进后出，只有栈顶能进出。

循环队列：

设循环队列Q的容量为 MAXSIZE，初始队列为空，且 Q.rear 和 Q.front 都等于 0.

元素入队时修改队尾指针，即令 Q.rear = (Q.rear + 1) % MAXSIZE（这里求余是为了循环）

元素出队时修改队头指针，即令 Q.front = (Q.front + 1) % MAXSIZE（这里求余是为了循环）

根据队列操作的定义，当出队操作导致队列变为空时，有 Q.rear == Q.front;若入队操作导致队列满，则 Q.rear == Q.front。

在这里插入图片描述

循环队列中：

队尾指针指向最后一个元素的下一个元素（因为最后一个元素的下一个元素为空，可用于插入、写入数据的）；

队头指针指向第一个有值的元素（队头指向第一个非空元素，因为要读到值，这里的读意味着出队，读到之后元素就为空了，因此要加1，指向非空元素。）；

在这里插入图片描述

其二：就是有一个存储单元是空的，不存储。

队尾元素的指针和队尾指针是不一样的哦。

队尾指针是最后一个元素的下一个空间；队尾元素的指针就是最后一个元素所在的空间。

在这里插入图片描述

答案为：需要 % M，防止越界以及实现循环。

实际答案应为：（Q.front + Q.size - 1） % M

而（Q.front + Q.size - 1 + M） % M = （Q.front + Q.size - 1） % M + M % M。

而 M % M = 0

所以答案为 B

3、字符串

字符串是一种特殊的线性表，其数据元素都为字符。
◆空串:长度为0的字符串，没有任何字符。
◆空格串:由一个或多个空格组成的串，空格是空白字符，占一个字符长度。
◆子串:串中任意长度的连续字符构成的序列称为子串。含有子串的串称为主
串，空串是任意串的子串。
◆串的模式匹配:子串的定位操作，用于查找子串在主串中第一次出现的位置
的算法。

模式匹配算法
朴素的模式匹配算法:也称为布鲁特一福斯算法，其基本思想是从主串的第1
个字符起与模式串的第1个字符比较，若相等，则继续逐个字符进行后续的比较否则从主串中的第2个字符起与模式串的第1个字符重新比较，直至模式串中每个字符依次和主串中的一个连续的字符序列相等时为止，此时称为匹配成功否则称为匹配失败。

◆KMP算法:对基本模式匹配算法的改进，其改进之处在于:
每当匹配过程中出现相比较的字符不相等时，不需要回溯主串的字符位置指针，而是利用已经得到的“部分匹配”结果将模式串向右“滑动”尽可能远的距离，再继续进行比较。
◆当模式串中的字符pj与主串中相应的字符si不相等时，因其前j个字符
(“po…pj-1”)已经获得了成功的匹配，所以若模式串中"p0…pk-1"与"pj-k…pj-1’相同，这时可令pk与si进行比较，从而使i无须回退。
◆在KMP 算法中，依据模式串的next 函数值实现子串的滑动。若令next[j]=k，则next[j]表示当模式串中的pj与主串中相应字符不相等时，令模式串的next[j]与主串的相应字符进行比较。

在这里插入图片描述

j = 1 时，输出 0

j = 其他情况，输出 1

当 j = 2，则 1 < k < 2，而 k 为正整数，所以此时为其他情况，输出 1

当 j = 3，则 1 < k < 3，而 k 为正整数，所以 k = 2，则此时 p₁…p_k-1 = p₁ = a；

p_j-k+1…p_j-1 = p₂ = b; 此时 a 不等于 b。所以此时 j = 3 也属于其他情况，所以输出 1.

当 j = 4,则 1 < k < 4，所以 k= 2 或 k = 3，此时k等于2时， p₁…p_k-1 = p₁ = a；p_j-k+1…p_j-1 = p₃ =a; 此时 a = a，满足条件。所以此时k=2是可以的；同理当k = 3 时，不满足条件。

所以当j=4时，k= 2.

当j = 5，则…同理可推算。

所以答案是 B。

4、数组

数组是定长线性表在维度上的扩展，即线性表中的元素又是一个线性表。N维数组是一种“同构”的数据结构，其每个数据元素类型相同、结构一致。

在这里插入图片描述

假设每个数组元素占用存储长度为 len，起始地址为 a，存储地址计算如下（默认从0开始编号）：

一维数组：a[n]，a[i]的存储地址为：a + i * len

二维数组：a [ m ] [ n ]，a [i] [j]按行存储地址为：a + (i * n + j) * len

a [i] [j]按列存储地址为：a + (j * m + i) * len

这样的存储地址只需要举出具体例子、特殊值模拟计算即可（即给出假定的数组即可）。m 表示行，n 表示列。

5、矩阵

特殊矩阵：矩阵中的元素（或非0元素）的分布有一定的规律。常见的特殊矩阵有对称矩阵、三角矩阵和对角矩阵。

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

存储方式为三元组结构：即存储每个非零元素的（行，列，值）。

在这里插入图片描述

1≤k≤3*n-2，表示B[k]从1开始。

按行存储表示：A(1,1) 存在B(1)里，A(1,2)存在B(2)里，A(2,1)存在B(3)里，A(2,2)存在B(4)里…

因此带入公式即可：i=1,j=1,k=1;i=1,j=2,k=2… 因此答案是 A。

第二题同样只要带入公式就能推算出答案是 C。

A[0,0] -> B[1]

A[n-1,n-1] -> B[3n-2]

6、广义表

◆广义表是线性表的推广，是由0个或多个单元素或子表组成的有限序列。
◆广义表与线性表的区别:线性表的元素都是结构上不可分的单元素，而广义
表的元素既可以单元素，也可以是有结构的表。
◆广义表一般记为:LS=(a1,a2,…,an)
其中LS是表名，ai是表元素，它可以是表(称为子表)，也可以是数据元素(称
为原子)。其中n是广义表的长度(也就是最外层包含的元素个数)，n=0的广
义表为空表;而递归定义的重数就是广义表的深度，即定义中所含括号的重数
(单边括号的个数，原子的深度为0，空表的深度为1)。
head()和tai():取表头(广义表第一个表元素，可以是子表也可以是单元素
和取表尾(广义表中，除了第一个表元素之外的其他所有表元素构成的表，非
空广义表的表尾必定是一个表，即使表尾是单元素)操作。

2、树与二叉树

1、树

◆树是n个节点的有限集合(n>=0)，当n=0时称为空树，在任一颗非空树中，有且仅有一个根节点。其余结点可分为m(m>=0)个互不相交的有限子集T1，T2，…，Tm，其中，每个Ti又都是一棵树，并且称为根结点的子树。

在这里插入图片描述

◆树的基本概念如下
(1)双亲、孩子和兄弟。结点的子树的根称为该结点的孩子;相应地，该结点称为其子结点的双亲。具有相同双亲的结点互为兄弟。比如上图 B 是 A 的孩子结点，也是 E 和 F 的双亲结点。
(2)结点的度。一个结点的子树的个数记为该结点的度。例如A的度为3，B的度为2，C的度为0，D的度为1。
(3)叶子结点。叶子结点也称为终端结点，指度为0的结点。例如，E、F、C、G都是叶子结点。
(4)内部结点。度不为0的结点，也称为分支结点或非终端结点。除根结点以外，分支结点也称为内部结点。例如，B、D都是内部结点。
(5)结点的层次。根为第一层，根的孩子为第二层，依此类推，若某结点在第i层，则其孩子结点在第i+1层。例如，A在第1层，B、C、D在第2层，E、F和G在第3层。
(6)树的高度。一棵树的最大层数记为树的高度(或深度)。例如，图中所示树的高度为3。
(7)有序(无序)树。若将树中结点的各子树看成是从左到右具有次序的，即不能交换则称该树为有序树，否则称为无序树。

2、二叉树

在这里插入图片描述

满二叉树：除了最后一层的叶子结点，其余节点的度都为2。

完全二叉树：除最后一层外，其余层都是满的，最后一层从左到右是连续的、不间断的（可以右侧缺少，但从左到右中间不缺）

二叉树的计算可以用特殊值法，即举例子进行验证、计算。

二叉树的顺序存储结构：

顺序存储，就是用一组连续的存储单元存储二叉树中的节点，按照从上到下，从左到右的顺序依次存储每个节点。

二叉树的链式存储结构：

在这里插入图片描述

二叉链表：左右指针

三叉链表：左右指针、父指针

二叉树的遍历：

一颗非空的二叉树由根节点、左子树、右子树三部分组成，遍历这三部分，也就遍历了整棵二叉树。这三部分遍历的基本顺序是先左子树后右子树，但根节点顺序可变，以根节点访问的顺序为准有三种遍历模式：

先序（前序）遍历：根左右

中序遍历：左根右

后序遍历：左右根

在这里插入图片描述

前序：12457836

中序：42785136

后序：48752631

层次遍历：按层次，从上到下，从左到右。

反向构造二叉树：

仅仅有前序和后序是无法构造二叉树的，**必须要是和中序遍历的集合才能构造出二叉树。**即必须前序+中序或后序 + 中序才能构造出二叉树。

构造时，**前序和后序遍历可以确定根节点，中序遍历用来确定根节点的左子树和右子树节点，**而后按此方法进行递归，直至得出结果。

◆引入线索二叉树是为了保存二叉树遍历时(前序、中序、后序)某节点的前驱节点和后继节点的信息，二叉树的链式存储只能获取到某节点的左孩子和右孩子结点，无法获取其遍历时的前驱和后继节点，因此可以在链式存储中再增加两个指针域，使其分别指向前驱和后继节点，但这样太浪费存储空间，考虑下述实现方法:
◆若n个节点的二又树使用二叉链表存储，则必然有n+1个空指针域，利用这些空指针域来存放节点的前驱和后继节点信息，为此，需要增加两个标志，以区分指针域存放的到底是孩子结点还是遍历节点，如下:

在这里插入图片描述

◆若二叉树的二叉链表采用上述结构，则称为线索链表，**其中指向前驱、后继节点的指针称为线索，**加上线索的二叉树称为线索二叉树：

在这里插入图片描述

3、最优二叉树

**最优二叉树又称为哈夫曼树，是一类带权路径长度最短的树，**相关概念如下：

路径：树种一个结点到另一个结点之间的通路。

结点的路径长度：路径上的分支数目。

树的路径长度：根节点到达每一个叶子结点之间的路径长度之和。

权：结点代表的值。

结点的带权路径长度：该结点到根节点之间的路径长度乘以该结点的权值。

树的带权路径长度（树的代价）：树的所有叶子节点的带权路径长度之和。

在这里插入图片描述

哈夫曼树的求法（要掌握、会考）：

给出一组权值，**将其中两个最小的权值作为叶子节点，其和作为父节点，组成二又树，而后删除这两个叶子节点权值，并将父节点的值添加到该组权值中。**重复进行上述步骤，直至所有权值都被使用完。

在这里插入图片描述

◆若需要构造哈夫曼编码(要保证左节点值小于右节点的值，才是标准的哈夫曼树)，将标准哈夫曼树的左分支设为0，右分支设为1，写出每个叶节点的编码，会发现，哈夫曼编码前缀不同，因此不会混淆，同时也是最优编码。

哈夫曼：左小于右

4、查找二叉树与平衡二叉树

◆查找二叉树上的每个节点都存储一个值，且每个节点的所有左孩子结点值都小于父节点值，而所有右孩子结点值都大于父节点值，是一个有规律排列的二叉树，这种数据结构可以方便查找、插入等数据操作。（左小于父，右大于父。）
◆二叉排序树的查找效率取决于二叉排序树的深度，对于结点个数相同的二叉排序树，平衡二叉树的深度最小，而单枝树的深度是最大的，故效率最差。
◆平衡二叉树又称为AVL树，它或者是一棵空树，或者是具有下列性质的二叉树：
它的左子树和右子树都是平衡二又树，且左子树和右子树的高度之差的绝对值不超过1。若将二叉树结点的平衡因子(Balance Factor，BF)定义为该结点左子树的高度减去其右子树的高度，则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。

在这里插入图片描述

先序、后序遍历可以确定根节点；中序遍历可以确定左右节点；

先序（根左右）为 cabfedg，所以 c 为根节点，中序（左根右）中 abcdefg 所以，ab 为左子树、defg 为右子树。

在这里插入图片描述

此时 a、b 不知道左右、先后，此时再看先序(根左右)，cab，所以a为根。即：

在这里插入图片描述

此时，需要确定b到底是左子树还是右子树，则需要看中序（左根右）abc，a 是根，b在 a后，所以b是右子树，所以：

在这里插入图片描述

接下来判断defg。还是先看先序，先序中为fedg(根左右)，所以 f 为根。而中序中 defg 所以 de 为左，g为右（左根右），所以：

在这里插入图片描述

此时，需要确定 de，先看先序（根左右）ed，所以 e 为根，同时中序（左根右）de，所以d为左子树，所以得到最终结果：

在这里插入图片描述

完全二叉树：除最后一层，都是满的。

最优二叉树：哈夫曼树，带全路径。

平衡二叉树：左子树、右子树深度差绝对值不超过1.（即深度差为-1或0或1）

满二叉树：所有层都是满的。

所以答案为：C。

二叉树的关键码序列就是根据给与的顺序是否尅构造出符合条件的二叉树，比如下方：

在这里插入图片描述

不可能的答案是：C。因为其他按照顺序都能构造出上图右侧中的二叉树。

3、图

◆无向图:图的结点之间连接线是没有箭头的，不分方向。
◆有向图:图的结点之间连接线是箭头，区分A到B，和B到A是两条线
◆完全图:无向完全图中，节点两两之间都有连线，n个结点的连线数为(n-
1)+(n-2)+…+1= n * (n-1)/2;有向完全图中，节点两两之间都有互通的两个箭头，n个节点的连线数为n * (n-1).
◆度、出度和入度:顶点的度是关联与该顶点的边的数目。在有向图中，顶点
的度为出度和入度之和。
◆路径:存在一条通路，可以从一个顶点到达另一个顶点。
◆子图:有两个图G=(V, E)和G’=(V’,E’)，如果V’属于V且E’属于E，则称G’为G 的子图
◆连通图和连通分量:针对无向图。若从顶点v到顶点u之间是有路径的，则说
明v和u之间是连通的，若无向图中任意两个顶点之间都是连通的，则称为连通图。无向图G的极大连通子图称为其连通分量。
◆强连通图和强连通分量:针对有向图。若有向图任意两个顶点间都互相存在
路径，即存在v到u，也存在u到v的路径，则称为强连通图。有向图中的极大连通子图称为其强连通分量。
◆网：边带权值的图称为网。

1、图的存储

邻接矩阵:假设一个图中有n个节点，则使用n阶矩阵来存储这个图中各节点的
关系，规则是若节点i到节点j有连线，则矩阵Ri,j=1，否则为0，示例如下图所示：

在这里插入图片描述

◆邻接链表:用到了两个数据结构，先用一个一维数组将图中所有顶点存储起来，而后，对此一维数组的每个顶点元素，使用链表挂上其出度到达的结点的编号和权值，示例如下图所示:

在这里插入图片描述

◆存储特点:图中的顶点数决定了邻接矩阵的阶和邻接表中的单链表数目，边
数的多少决定了单链表中的结点数，而不影响邻接矩阵的规模，因此采用何种存储方式与有向图、无向图没有区别，要看图的边数和顶点数，完全图适合采用邻接矩阵存储。

◆图的遍历是指从图的任意节点出发，沿着某条搜索路径对图中所有节点进行访问且只访问一次，分为以下两种方式:
◆深度优先遍历:从任一顶点出发，遍历到底，直至返回，再选取任一其他节
点出发，重复这个过程直至遍历完整个图;
◆广度优先遍历:先访问完一个顶点的所有邻接顶点，而后再依次访问其邻接
顶点的所有邻接顶点，类似于层次遍历。

在这里插入图片描述

◆图的最小生成树

假设有n个节点，那么这个图的最小生成树有n-1条边(不会形成环路，是树非图)这n-1条边应该会将所有顶点都连接成一个树，并且这些边的权值之和最小，因此称为最小生成树。共有下列两种算法:

◆普里姆算法:任意顶点出发，找出与其邻接的边权值
最小的，此此边的另外一个顶点自动加入树集合中，而后再从这这个树集合的所有顶点中找出与其邻接的边权值最小的，同样此边的另外一个顶点加入树集合中，依次递归，直至图中所有顶点都加入树集合中，此时此树就是该图的最小生成树。普里姆算法的时间复杂度为0(n^2)，与图中的边数无关，因此该算法适合于求边稠密的网的最小生成树。

在这里插入图片描述

先从 A（任意顶点）开始，找与A相邻的边权值最小的，就到了的 b。

然后再找出 A、C 两个顶点中相邻的边里最小的，此时与 C 相邻的 CF 边，在 A、C各自相邻边种最小（AB = 6,AD = 5，BC=5，CD=5，CE=6,CF=4，其中 CF 最小）。因此得到 c。

同理就再找 A、C、F 各自相邻边种最小的，FD 最小，于是得到 d。

此时，再找 A、C、F、D 各自相邻边最小的（此时 BC = 5,CD=5,AD=5,需要注意的是不能选择 AD、CD，因为不能形成环路，如果选择了 BC 也会形成环路，则此时就不能找最小的5了，就要选择6了，比如 CE、EF，而此时BC 不是环路，所以可以得到 e 图），于是得到 e。

然后得到最终的图 f。

◆克鲁斯卡尔算法（推荐）:这个算法是从边出发的，因为本质是选取权值最
小的n-1条边，因此，就将边按权值大小排序，依次选取权值最小的边，直至囊括所有节点，要注意，每次选边后要检查不能形成环路。

克鲁斯卡尔算法的时间复杂度为o(eloge)，与图中的顶点数无关，因此该算法适合于求边稀疏的网的最小生成树。

在这里插入图片描述

首先，将边移除，然后选择全图中权值最小的，就是 AC，于是连接AC，得到 b。

然后，再选剩下图中权值最小的，于是得到 DF，于是连接 DF，得到 c。

然后再选图中权值最小的，于是得到 BE，于是连接 BE，得到 d。

然后再选图中权值最小的，于是得到 CF，于是连接 CF，得到 e。

最后再选择图中权值最小的，BC = 5，CD = 5，AD = 5,注意不能形成环路，于是得到 BC，于是连接 BC，得到最终的 f。

◆拓扑序列
若图中一个节点入度为0，则应该最先执行此活动，而后删除掉此节点和其关联的有向边，再去找图中其他没有入度的结点，执行活动，依次进行，示例如下(有点类似于进程的前趋图原理)

在这里插入图片描述

a 图中，②③④⑤都是有箭头指向它的，即入度不为0.只有①、⑥是入度为0的。有箭头指向它，意思就是前者执行完（①执行完）后者（②）才能执行。

因此要先执行①或⑥，假如这里先执行⑥（先执行①或⑥都可以）。则把⑥相关的出度的箭头都删除掉。于是得到图 b。

此时 ①和④入度为0.假如这里先执行①（这里先执行①或④都可以）。则①执行完后，把①相关的出度的箭头都删除掉，于是得到 c。

同理可以得到 d、e、f。

在这里插入图片描述

4、查找

1、顺序查找

顺序查找的思想:将待查找的关键字为key的元素从头到尾与表中元素进行比
较，如果中间存在关键字为key的元素，则返回成功;否则，则查找失败。

在这里插入图片描述

假如 1…n个数字，最短查找1次，即就是查找1；最长查找n次，即就是查找n。

所以就是 1 + 2 + 3 + … + n = （1 + n）* n / 2；平均 n 个，所以平均查找长度就是 (1+n) * n / 2 / n = (1 + n ) / 2。

2、折半查找

◆只适用于待查找序列中的元素是有序排列的情况。
◆设查找表的元素存储在一维数组r[1…n]中，在表中元素已经按照关键字递增(或递减)方式排序的情况下，进行折半查找的方法是:

1、首先将待查元素的关键字(key)值与表r中间位置上(下标为mid)记录的关
键字进行比较，若相等，则查找成功;
2、若key>r[mid].key，则说明待查记录只可能在后半个子表r[mid+1…n]中，下一步应在后半个子表中查找;
3、若key<r[mid].key，说明待査记录只可能在前半个子表r[1…mid-1]中，下一步应在r的前半个子表中查找;
4、重复上述步骤，逐步缩小范围，直到查找成功或子表为空失败时为止
要注意两点:中间值位置求出若为小数，应该向下取整，即4.5=4，非四舍五入；中间值已经比较过不相等，在划分下一次比较区间时，无需将中间值位置再纳入下一次比较区间。
折半查找的时间复杂度为 O(log₂n)