数据结构笔记

村雨在进行数据结构期末复习时整理的笔记。

---

一、绪论

1.数据结构的基本概念

数据由数据元素组成，数据元素由数据项组成。

数据元素是讨论数据结构时涉及的最小数据单位，其中的数据项一般不予考虑。

数据结构：相互之间存在一定关系的数据元素的集合。可以认为是一堆数据元素和这些数据元素之间的关系的总和，换句话说，数据结构是带"结构"的数据元素的集合。

数据结构分为逻辑结构和存储结构（物理结构）

逻辑结构：指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

集合结构： 仅同属一个集合，为使用方便，一般处理为线性结构。

线性结构: 一对一（1:1) 的线性关系

树结构: 一对多（1:n)的层次关系

图 结 构: 多对多 (m:n)的任意关系

存储结构是数据逻辑结构在计算机中的表示，包括数据元素的表示和关系的表示。

存储结构通常有两种：

1. 顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。

2. 链接存储结构：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示 。

2.算法及特性

1.算法（Algorithm）:是对特定问题求解步骤的一种描述，是指令的有限序列。

2.算法的五大特性：
⑴ 输入：一个算法有零个或多个输入。
⑵ 输出：一个算法有一个或多个输出。（必须有输出）
⑶ 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
⑷ 确定性：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。
⑸ 可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。

好算法的特性:易读性，高效性，鲁棒性，正确性

2.算法分析（Algorithm Analysis）：对算法所需要的计算机资源——时间和空间进行估算

时间复杂度

空间复杂度

通常，一个特定算法的执行时间，即“运行工作量”的大小，是随问题规模的增长而增长，只依赖于问题的规模（通常用整数量 n 表示），或者说，它是问题规模的函数f(n)。

因此衡量不同算法的优劣，应该以其随问题规模的增长而“增长的趋势”为准则。称这种算法时间的量度为算法的渐近时间复杂度，简称时间复杂度，记作为：T (n) = O(f(n))

称**T(n)**为算法的(渐近)**时间复杂度。**它表示随着问题规模 n 的增长，算法执行时间的增长率和 f(n) 的增长率相同，把T(n)作为算法的时间度量。

分析算法的时间复杂度的核心是分析算法中基本操作的重复次数。

通常用Ο(1)表示常数计算时间。

（1）对于多项式复杂度来说，计算时去低阶项，去掉常数项，去掉高阶项的系数。

（2）最坏情况复杂性，指在规模为n时，算法所执行的基本运算的最大次数。

以下六种计算算法时间的多项式是最常用的，其关系为：
O(1)<O(㏒n)<O(n)<O(n㏒n)<O(n2)<O(n3)
非多项式时间的关系为：
O(2n)<O(n!)<O(nn)

---

二、线性表

1.线性表及其逻辑结构

线性表：简称表，是n（n≥0）个具有相同类型的数据元素的有限序列。

线性表的长度：线性表中数据元素的个数。

空表：长度等于零的线性表，记为：L=( )。

非空表记为：L＝(a1, a2 , …, ai-1, ai , …, an )

其中，ai（1≤i≤n）称为数据元素；下角标 i 表示该元素在线性表中的位置或序号 。

2.线性表的特性

1. 有限性：线性表中数据元素的个数是有穷的。

2. 相同性：线性表中数据元素的类型是相同的。

3. 顺序性：线性表中相邻的数据元素ai-1和ai之间存在序偶关系(ai-1, ai)，即ai-1是ai的前驱， ai是ai-1的后继；a1无前驱，an无后继

   其它每个元素有且仅有一个前驱和一个后继。

3.线性表的顺序存储结构（顺序表）

顺序表通常使用一维数组，用一段地址连续的存储单元依次存储线性表中的数据元素。

顺序表的存储结构为随机存取结构。

只要确定了顺序表的起始地址（或数组的基地址），就可以计算任意一个元素的存储地址，并且计算时间是相等的。

顺序表的优点：
⑴ 无需为表示表中元素之间的逻辑关系而增加额外的存储空间；
⑵ 随机存取：可以快速地存取表中任一位置的元素。
顺序表的缺点：
⑴ 插入和删除操作需要移动大量元素；
⑵ 表的容量难以确定，表的容量难以扩充；
⑶ 造成存储空间的碎片。

4.线性表的链接存储结构（链表）

用一组任意的存储单元存放线性表的元素。

存储特点：

1.逻辑次序和物理次序不一定相同。

2.元素之间的逻辑关系用指针表示。

单链表是由若干结点构成的。单链表的结点结构：数据域+指针域

**data：**存储数据元素

**next：**存储指向后继结点的地址

单链表是一种顺序存取的链式存储结构。

一些特殊链表：

循环链表:将单链表的首尾相接，将终端结点的指针域由空指针改为指向头结点，构成单循环链表，简称循环链表。

双向链表：在单链表的每个结点中再设置一个指向其前驱结点的指针域。

静态链表：用数组来表示单链表，用数组元素的下标来模拟单链表的指针。

相对于顺序表而言，静态链表有什么优点？

答：优点：在执行插入和删除操作时，只需修改游标，不需要移动表中的元素，从而改进了在顺序表中插入和删除操作需要移动大量元素的缺点。
缺点：没有解决连续存储分配带来的表长难以确定的问题；静态链表还需要维护一个空闲链；静态链表不能随机存取。

顺序表和链表的比较：

1.时间性能的比较：

按位查找：
顺序表的时间为Ｏ(1)，是随机存取；
链表的时间为Ｏ(n)，是顺序存取。
插入和删除：
顺序表需移动表长一半的元素，时间为Ｏ(n)；
链表不需要移动元素，在给出某个合适位置的指针后，插入和删除操作所需的时间仅为Ｏ(1)。

2**.空间性能的比较：**

空间性能是指某种存储结构所占用的存储空间的大小。
定义结点的存储密度：
存储密度＝数据域占用的存储量/整个结点占用的存储量
结点的存储密度：
顺序表：结点的存储密度为1（只存储数据元素），没有浪费空间；
链表：结点的存储密度<1（包括数据域和指针域），有指针的结构性开销。

顺序表：需要预分配存储空间，如果预分配得过大，造成浪费，若估计得过小，又将发生上溢；
链表：不需要预分配空间，只要有内存空间可以分配，单链表中的元素个数就没有限制。

结论：

⑴若线性表需频繁查找却很少进行插入和删除操作，或其操作和元素在表中的位置密切相关时，宜采用顺序表作为存储结构；若线性表需频繁插入和删除时，则宜采用链表做存储结构。

⑵当线性表中元素个数变化较大或者未知时，最好使用链表实现；而如果用户事先知道线性表的大致长度，使用顺序表的空间效率会更高。

三、栈和队列

两种特殊的线性表——栈和队列

但是操作受限，插入和删除只能在表的“端点”进行。

1.栈

栈：限定仅在一端进行插入和删除操作的线性表。

栈顶（top）：允许插入和删除的一端称为栈顶
栈底（bottom）：另一端称为栈底

栈的操作特性：后进先出（Last In First Out，LIFO）（先进后出）

n个元素按次序进栈后的出栈序列个数：
$$
（1/n+1）*C n 2n
$$
栈只是对插入和删除操作的位置进行了限制并没有限定插入和删除操作进行的时间

tip：在输出序列中任意元素后面不能出现比该元素小并且是升序的两个元素。（元素大小体现的是入栈次序，小表示先入栈。）

顺序栈：栈的顺序存储结构

如何表示栈底：用数组的一端作为栈底

如何表示栈顶：设变量top存储栈顶元素所在的下标（从0开始）

链栈：栈的链接存储结构

用链头作为栈顶

链栈无须加头结点

两栈共享空间

使用一个数组来存储两个栈，让一个栈的栈底为该数组的始端，另一个栈的栈底为该数组的末端，两个栈从各自的端点向中间延伸。

什么时候栈1为空？top1== -1

什么时候栈2为空？top2== StackSize

什么时候栈满？top2== top1+1

2.队列

队列：只允许在表的一端进行插入操作，在另一端进行删除操作

队尾：允许插入的一端，相应地，位于队尾的元素称为队尾元素（入队）

队头：允许删除的一端，相应地，位于队头的元素称为队头元素（出队）

队列的操作特性：先进先出（First In First Out，FIFO）

顺序队列：队列的顺序存储结构

如何表示队头：用数组的一端作为队头，从下标 0 处开始存放

如何表示队尾：设变量rear存储队尾元素所在的下标

如何改进出队操作的时间性能？

设置队头、队尾两个位置指针。front和rear

约定：队头front指向队头元素的前一个位置，队尾rear指向队尾元素

入队、出队时间性能均是O(1)

产生的问题：整个队列会向数组下标较大方向移动（单向移动性）

从而造成假溢出：数组空间发生上溢，但数组的低端还有空闲空间

解决方法：循环队列

循环队列

队列采用顺序存储，并且数组是头尾相接的循环结构

程序技巧：求模（正余数）使得数组下标循环。如rear = (rear + 1) % 5

链队列：队列的链接存储结构

链头作为队头，出队时间为O(1)，队头指针front指向单链表的头结点

链尾作为队尾，入队时间为O(n)，队尾指针rear指向单链表的尾结点

可以没有头结点，但增加头结点的目的是使空队列和非空队列的操作一致

循环队列和链队列的比较

时间性能:循环队列和链队列的基本操作都需要常数时间O (1)。

空间性能:

循环队列：必须预先确定一个固定的长度，所以有存储元素个数的限制和空间浪费的问题。

链队列：没有队列满的问题，只有当内存没有可用空间时才会出现队列满，但是每个元素都需要一个指针域，从而产生了结构性开销。

3.栈和队列的应用

数值转换

括号匹配

表达式求值

表达式的三种标识方法：设 Exp = S1 + OP + S2 （OP为运算符）

则称 OP + S1 + S2 为前缀表示法

​ S1 + OP + S2 为中缀表示法

​ S1 + S2 + OP 为后缀表示法（逆波兰式）（所有的运算符都在对应的操作数后面出现）

为了在后缀表达式中区分相邻的操作数，在每个操作数末尾添加一个字符“#”。后缀表达式中没有括号，只有操作数和运算符，越放在前面的运算符优先级越高。计算机就是**先将中缀表达式转换为后缀表达式，**然后再对后缀表达式求值。

前缀式的运算规则为: 连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式;

后缀式的运算规则为: 运算符在式中出现的顺序恰为表达式的运算顺序; 每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式。

中缀表达式求值：

1.运算符的优先级从高到低依次为( )、*和/ 、+和-、#；
2.有括号出现时先算括号内的，后算括号外的，多层括号由内向外进行计算；
3.左右括号优先级相等（唯一相等的情况）；
4.左括号大于它左边的其它运算符（即其它<(），小于它右边的其它运算符（即(<其它）；
5.右括号小于所有其它运算符（实际只能跟它左边的运算符比较）；
6.优先级相同的普通运算符（如+和- ， *和/ ），谁在前优先级谁高。

计算机中后缀表达式求值规则：

从左到右遍历表达式的每个数字和符号，遇到数字就进栈，遇到运算符就将处于栈顶的两个数字弹出并进行运算，然后将运算结果进栈，一直到获得最终结果。

中缀表达式转后缀表达式规则：

1.从左到右遍历中缀表达式，如果是数字就直接输出，如果是运算符，则执行步骤2

2.判断其与栈顶运算符的优先级，若优先级相等，则肯定是“）”，栈顶的“（”直接出栈即可；

若优先级高，则直接入栈；

若优先级低，则栈顶元素依次出栈并输出，直到栈顶元素优先级低于当前运算符，当前运算符再入栈。

3.执行步骤1、2，一直遍历到表达式结束，栈中运算符依次出栈到栈空为止。

“(”=“)”

先入栈运算符<“(”,“(”<后入栈运算符

")"小于所有其他运算符

+和-、*和/谁在前谁的优先级高

四、串和矩阵

1.串

串，由零个或多个字符组成的有限序列，是一种特殊类型的线性表，也叫字符串。

非空串：长度不为0的串，通常记为：S = " s1 s2 …… sn "

其中：S是串名，双引号是定界符，双引号内部是串值 ，si（1≤i≤n）是一个任意字符。
空串：长度为0的串，记为"" 。

strCmp串比较：通过组成串的字符（ASCII码）之间的比较来进行

• [ ] 给定两个串：X="x1x2…xn"和Y=“y1y2…ym”，则：

1. 当且仅当n=m且x1=y1，…，xn=ym时，称X=Y；
2. 当下列条件之一成立时，称X＜Y：
   ⑴ n＜m且xi=yi（1≤ i≤n）；
   ⑵存在k≤min(m,n)，使得xi=yi(1≤i≤k-1)且xk＜yk。
3. 其它情况，称X>Y。

串和线性表的比较

在线性表的基本操作中，大多以“单个元素”作为操作对象；

在串的基本操作中，通常以“串的整体”作为操作对象。

串有两种存储方式：

1.顺序存储方式

2.块链存储方式

串的顺序存储

就是要用一段地址连续的存储空间存储串的内容。

如何记录存储空间的首地址？如何记录串的长度？

方法1：用数组的0号单元存放串长，从1号单元作为存储空间首地址。

方法2：在串尾存储一个不会在串中出现的特殊字符作为串的终结符，表示串的结尾。

串的块链储存

链表存储串的例子：“shujujiegou”的存储

可用链表来存储串，由于串的数据元素是一个字符，因此每个链表结点的数据域为1个字符，占用内存的1个字节，而指针域为4个字节，存储密度低。

存储密度 = 数据元素存储空间/实际分配的存储空间

上述例子的存储密度为：1/（1+4）=1/5

链表存储串方法的改进-块链：“shujujiegou”的存储

链表各结点存储多个字符，存储密度高。

上述例子的存储密度为4/（4+4）=1/2

串的模式匹配

给定主串S=“s1s2…sn”和子串T=“t1t2…tm”，在S中寻找T 的过程称为模式匹配，又称为子串定位。

如果匹配成功，返回T 在S中的位置；如果匹配失败，返回-1。

在模式匹配操作中，S又可以称为目标串，T又称为模式串。

模式匹配算法：BF算法和KMP算法

BF算法

即Brute Force算法，特点是暴力匹配。

基本思想：

从目标串S的第一个字符开始和模式串T 的第一个字符进行比较。

若相等，则继续比较两者的后续字符；否则，从主串S的第二个字符开始和模式T 的第一个字符进行比较，重复上述过程。

直到T 中的字符全部比较完毕，则说明本趟匹配成功；或S中的字符全部比较完，则说明匹配失败。

过程：

1. 在串S和串T中设比较的起始下标i和j；
2. 循环直到S或T的所有字符均比较完
   2.1 如果S[i]=T[j]，继续比较S和T的下一个字符；
   2.2 否则，将i和j回溯，准备下一趟比较；
3. 如果T中所有字符均比较完，则匹配成功，返回匹配的起始比较下标；否则，匹配失败，返回0；

代码实现：

KMP算法

是对BF算法的改进，主要是消除了主串指针的回溯，从而使算法效率有了较大程度的提升。

核心步骤是要求出T模式串的next[j]函数。

如下图所示，其实就是找前后缀相同。

找到next[j]函数后，进行以下操作。

下图的next[j]=[-1,0,0,1,2]

判断j在哪一个位置匹配失败，然后找到对应位置的next值k，下一趟则让j指向T[k]，

只不过并不是令j回溯，而是令T模式串整体向右移动，使得j指向T[k]，

如果i=j，说明匹配成功，i和j同时右移一位。

KMP比较抽象，但是却大幅度地优化了BF算法。

2.数组

数组：由一组类型相同的数据元素构成的有序集合，每个数据元素称为一个数组元素（简称为元素）

数组的特点：

1.元素本身可以具有某种结构，属于同一数据类型；
2.数组是一个具有固定格式和数量的数据集合。

在数组上一般不能执行插入或删除某个数组元素的操作

数组的基本操作：

存取：给定一组下标，读出对应的数组元素

修改：给定一组下标，存储或修改与其相对应的数组元素

如何存储（多维）数组呢？

按行优先：先存储行号较小的元素，行号相同者先存储列号较小的元素

按列优先：先存储列号较小的元素，列号相同者先存储行号较小的元素

3.特殊矩阵

矩阵中很多值相同的元素并且它们的分布有一定的规律。主要形式有对称矩阵、三角矩阵、对角矩阵等，都是方阵。（n*n型）

存储的基本思路：为多个值相同的元素只分配一个存储空间；保证随机存取，即在O(1)时间内寻址。

对称矩阵的压缩存储：只存储下三角部分的元素。

三角矩阵的压缩存储：只存储上三角部分（或下三角）的元素和其余部分的任意c 值。（相同的常数）

对角矩阵的压缩存储：所有非零元素都集中在以主对角线为中心的带状区域中，除了主对角线和它的上下方若干条对角线的元素外，所有其他元素都为零。

4.稀疏矩阵

稀疏矩阵：矩阵中有很多零元素，非零元个数远远小于矩阵元素总个数。

非零元的分布没有规律，具有随机性。存储的基本思路：对零元素不分配存储空间。

稀疏矩阵的压缩存储：只存储非零元素。

注意：稀疏矩阵中的非零元素的分布没有规律。

**三元组顺序表：**将稀疏矩阵中的每个非零元素表示为一个三元组：(行号，列号，非零元素值)

三元组顺序表可表示为下图

三元组顺序表不适用于稀疏矩阵的加法、乘法等操作，非零元素的个数及位置都会发生变化，则在三元组顺序表中就要进行插入和删除操作，顺序存储就十分不便。

十字链表

采用链接存储结构存储三元组表

十字链表可表示为下图

五、树和二叉树

1.树的引入

树的定义：

n（n≥0）个结点的有限集合。当n＝0时，称为空树；任意一棵非空树满足以下条件：有且仅有一个特定的称为根的结点；当n＞1时，除根结点之外的其余结点被分成m（m>0）个互不相交的有限集合T1,T2,… ,Tm，其中每个集合又是一棵树，并称为这个根结点的子树。

二叉树的定义：

n(n≥0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

特点：（1）每个结点最多有两棵子树；（2）两棵子树是有序的，不能任意颠倒；（3）即使结点只有一棵子树，也有左右之分。

二叉树是另一种树型结构，不是树的子集。与度为2的树的区别：

（1）度为2的树至少有一个结点的度为2，而二叉树没有这个要求；

（2）度为2的树中的结点如果只有一棵子树，是不区分左右的，而二叉树需要严格区分左右。

2.树的存储结构

树的基本术语

结点的度：结点所拥有的子树的个数。

树的度：树中各结点度的最大值max。

叶子结点：度为0的结点，也称为终端结点。

分支结点：度不为0的结点，也称为非终端结点。

孩子、双亲：树中某结点子树的根结点称为这个结点的孩子结点，这个结点称为其孩子结点的双亲结点；

兄弟：具有同一个双亲的孩子结点互称为兄弟。

路径：如果树的结点序列n1, n2, …, nk有如下关系：结点ni是ni+1的双亲（1<=i<k），则把n1, n2, …, nk称为一条由n1至nk的路径；

路径长度：路径上经过的边的个数称为路径长度。

祖先、子孙：在树中，如果有一条路径从结点x到结点y，则x称为y的祖先，而y称为x的子孙。

结点所在层数：根结点的层数为1；对其余任何结点，若某结点在第k层，则其孩子结点在第k+1层。

树的深度：树中所有结点的最大层数max，也称高度。

层序编号：将树中结点按照从上层到下层、同层从左到右的次序依次给他们编以从1开始的连续自然数。

有序树、无序树：如果一棵树中结点的各子树从左到右是有次序的，称这棵树为有序树；反之，称为无序树。

（数据结构中讨论的一般都是有序树）

森林：m (m≥0)棵互不相交的树的集合。

树的遍历

从根结点出发，按照某种次序访问树中所有结点，使得每个结点被访问一次且仅被访问一次。

遍历的实质：树结构（非线性结构）→线性结构。

遍历的方式：

前序遍历：根左右

中序遍历：左根右

后序遍历：左右根

层序遍历：从上到下，从左到右

如何表示结点的双亲和孩子，而这种关系很难用存储位置来体现，所以树一般没有顺序存储结构。

树的表示法

1.双亲表示法

用一维数组来存储树的各个结点（一般按层序存储）

示意图：

2.孩子链表表示法

1.用一维数组来存储树的各个结点（一般按层序存储）；

2.把每个结点的孩子排列起来，看成是一个线性表，且以单链表存储，则n个结点共有 n 个孩子链表；

示意图：

3.双亲孩子表示法

融合了双亲表示法和孩子链表表示法

示意图：

4.孩子兄弟表示法

任一结点的第一个孩子是惟一的，右兄弟是惟一的，设置两个分别指向该结点的第一个孩子和右兄弟的指针。

但这种表示方法同样不方便查找结点的双亲信息

3.二叉树的逻辑结构

特殊的二叉树

斜树

1.所有结点都只有左子树的二叉树称为左斜树；
2.所有结点都只有右子树的二叉树称为右斜树；
3.左斜树和右斜树统称为斜树。

特点：在斜树中，每一层只有一个结点；斜树的结点个数与其深度相同。

满二叉树

在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上。

特点：叶子只能出现在最下一层；只有度为0和度为2的结点。

完全二叉树

对一棵具有n个结点的二叉树按层序编号，如果编号为i（1≤i≤n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同。

结点集中在下面，左面

特点：

1.叶子结点只能出现在最下两层且最下层的叶子结点都集中在二叉树的左面；
2.完全二叉树中如果有度为1的结点，只能有一个，且该结点只有左孩子；
3.深度为k的完全二叉树在k-1层上一定是满二叉树；
4.在同样结点个数的二叉树中，完全二叉树的深度最小。

在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全二叉树。

二叉树的基本性质

性质1

二叉树的第i层上最多有2^(i-1)^个结点（i≥1).

性质2

一棵深度为k的二叉树中，最多有2k-1个结点，最少有k个结点。

性质3

在一棵二叉树中，如果叶子（度为0）结点数为n0，度为2的结点数为n2，则有: n0＝n2＋1。

性质4

具有n个结点的完全二叉树的深度为[$\log_2{n}$]+1。（向下取整）

性质5（完全二叉树的基本性质）

对一棵具有n个结点的完全二叉树中**从1开始按层序编号，**则对于任意的序号为i（1≤i≤n）的结点（简称为结点i），有：

1.如果i＞1，则结点i的双亲结点的序号为 [i/2]；如果i＝1，则结点i是根结点，无双亲结点。
2.如果2i≤n，则结点i的左孩子的序号为2i；如果2i＞n，则结点i无左孩子。
3.如果2i+1≤n，则结点i的右孩子的序号为2i+1；如果2i+1＞n，则结点 i无右孩子。

4.二叉树的存储结构

二叉树的顺序存储结构

用一维数组存储二叉树中的结点，并且结点的存储位置（下标）应能体现结点之间的逻辑关系——双亲和孩子关系。

完全二叉树（包括满二叉树）中结点的序号可以唯一地反映出结点之间的逻辑关系 。

二叉树的顺序存储结构一般仅存储完全二叉树，不适合存储一般的二叉树。

例如非完全二叉树：

二叉树的链表存储结构

令二叉树的每个结点对应一个链表结点，链表结点除了存放与二叉树结点有关的数据信息外，还要设置指示左右孩子的指针。

二叉树前序、中序和后序遍历的非递归实现

先空着，哈哈

二叉树的构造

为了能唯一构造一颗二叉树，可以采取两类方法：

1.采用两个不同的遍历序列

前序遍历序列+中序遍历序列可以构造二叉树

中序遍历序列+后序遍历序列可以构造二叉树

但是 前序遍历序列+后序遍历序列不可以**构造二叉树（找不到根结点）

2.采用扩展二叉树：

二叉树的应用

1.求二叉树的结点个数

void Count(BiNode *root)  //count为全局量并已初始化为0
{
    if (root == NULL) return;
    else {
         Count(root->lchild);
         count++;
         Count(root->rchild);
   }
}

2.按前序次序打印二叉树中的叶子结点

void PreOrder(BiNode *root)
{
    if (root == NULL) return;
    else {
        if (!root->lchild && !root->rchild)
               cout<<root->data;
        PreOrder(root->lchild);
        PreOrder(root->rchild);
   }
}

3.求二叉树的深度

int  Depth(BiNode *root)
{
    if (root == NULL) return 0;
    else {
         hl= Depth(root->lchild);
         hr= Depth(root ->rchild);
         return max(hl, hr)+1;
    }
}

5.三叉链表

在二叉链表的基础上增加了一个指向双亲的指针域。

示意图：

6.线索链表

对于有n个结点的二叉链表来说，共有2n个指针域，其中用来存放孩子信息的指针域只有n-1个，剩余n+1个指针域的值为nullptr。

可以利用这些空闲的指针域存放遍历时的前驱后继关系来加快遍历的进程，减少时间的开销。

方法：增加两个标志域，分别指示对应的指针域存储的是孩子还是前驱或后继

将空闲的左孩子域指向结点的前驱，将空闲的右孩子域指向后继。

标志域为1，则说明存在线索。标志域为0，说明存在孩子。

示意图：

因为中序遍历为“左根右”，所以这里的前驱后继关系并不是指父子关系，而是指访问的次序。比如根的前驱是左，根的后继是右。

7.树、森林和二叉树的相互转换

树转换为二叉树

1.加线，在所有兄弟结点之间加一条连线

2.抹线，只保留双亲与第一个孩子的连线，删去与其它孩子的连线

3.顺时针旋转，使结构层次分明

示意图：

森林转换为二叉树

1.先把每棵树都转换为二叉树（加线，抹线，顺时针旋转）

2.连接，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连起来后，此时所得到的二叉树就是由森林转换得到的二叉树。

示意图：

二叉树转换为树或森林

1.加线，在二叉树中，若某结点x是其双亲y的左孩子，则把结点x的右孩子、右孩子的右孩子、……，都与结点y用线连起来；

2**.抹线**，删去原二叉树中所有结点与其右孩子结点的连线

3.调整，使结构层次分明

示意图：

树和二叉树遍历的关系

1.树的前序遍历=二叉树的前序遍历

2.树的后序遍历=二叉树的中序遍历

8.哈夫曼树和哈夫曼编码

**权：**对树结点赋予一个有实际含义的数值

带权路径长度：根结点到某一结点路径长度与权值的乘积

哈夫曼树

给定n个权值作为n个叶子结点，构造一颗二叉树，若该树的带权路径长度达到最小，这样的二叉树就叫做哈夫曼树，也称为最优二叉树。

特点：

1.权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。

2.只有度为0（叶子结点）和度为2（分支结点）的结点，不存在度为1的结点。

3.同一组权值，对应的哈夫曼树不唯一

哈夫曼树的构造：选取最小的两个结点，合并。重复此步骤。

示意图：

哈夫曼编码

等长编码：表示一组对象的二进制位串的长度相等，如ASCII码

不等长编码：表示一组对象的二进制位串的长度不相等。使用频率高的用短码，使用频率低的用长码。

前缀编码：设计不等长编码时必须保证某字符的编码不是另一个字符的前缀（最左子串），这种编码就叫做前缀编码。

哈夫曼编码是一种前缀编码，该方法以字符出现的频率为权值来构建哈夫曼树，并得到平均长度最短的码字。

例如：一组字符{A, B, C, D, E, F, G}出现的频率分别是{9, 11, 5, 7, 8, 2, 3}，设计最经济的编码方案。

**译码：**从Huffman树根开始，从待译码电文中逐位取码。

若编码是**“0”，则向左走**；若编码是**“1”，则向右走**；一旦到达叶子结点，则译出一个字符；再重新从根出发，直到电文结束。

例如：电文编码：010110011011010

译文只能是 CDFDB

注意：编码方和译码方的哈夫曼树必须一致，否则不能正确译码。

六、图

1.图的基本概念

图由顶点的有穷非空集合和顶点之间边的集合组成（点集和边集），通常表示为： G=(V，E)

在线性表中有空表，元素个数为零；

在树中有空树，结点个数为零；

但在图中，顶点个数不能为零，但可以没有边。

图无法采用顺序存储结构。

---

无向边：(vi，vj) 有向边(弧）:<vi，vj>

简单图：在图中，若不存在顶点到其自身的边，且同一条边不重复出现。

邻接、依附:

1.无向图中，对于任意两个顶点vi和顶点vj，若存在边(vi，vj)，则称顶点vi和顶点vj互为邻接点，同时称边(vi，vj)依附于顶点vi和顶点vj。

2.有向图中，对于任意两个顶点vi和顶点vj，若存在弧<vi，vj>，则称顶点vi邻接到顶点vj，顶点vj邻接自顶点vi，同时称弧<vi，vj>依附于顶点vi和顶点vj 。

在线性结构中，元素之间的关系为前驱和后继；

在树结构中，结点之间的关系为双亲和孩子；

在图结构中，顶点之间的关系为邻接。

---

无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。

有向完全图：在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图。

含有n个顶点的无向完全图有n×(n-1)/2条边。 含有n个顶点的有向完全图有**n×(n-1)**条弧。

稀疏图：称边数很少的图为稀疏图；

稠密图：称边数很多的图为稠密图。

顶点的度：在无向图中，顶点v的度是指依附于该顶点的边数，通常记为TD (v)。

顶点的入度：在有向图中，顶点v的入度是指以该顶点为弧头的弧的数目（进入该点），记为ID (v)；

顶点的出度：在有向图中，顶点v的出度是指以该顶点为弧尾的弧的数目（离开该点），记为OD (v)。

在无向图中，度数和=边数的2倍

在有向图中，入度和=出度和=弧数

权：是指对边赋予的有意义的数值量。

网：边上带权的图，也称网图。

路径：例如无向图---->

路径长度：

非带权图——路径上边的个数

带权图——路径上各边的权之和

回路（环）：第一个顶点和最后一个顶点相同的路径。(回到自身)

简单路径：序列中顶点不重复出现的路径。

简单回路（简单环）：除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。

子图：若图G=（V，E），G’=（V’，E’），如果V’属于V 且E’ 属于 E ，则称图G’是G的子图。

连通图：在无向图中，如果从一个顶点vi到另一个顶点vj(i≠j)有路径，则称顶点vi和vj是连通的。如果图中任意两个顶点都是连通的，则称该图是连通图。

连通分量：非连通图的极大连通子图称为连通分量。（两个连通分量只要再加一条边就可成为连通图）

连通分量是对无向图的一种划分

强连通图：在有向图中，对图中任意一对顶点vi和vj (i≠j)，若从顶点vi到顶点vj和从顶点vj到顶点vi均有路径，则称该有向图是强连通图。

强连通分量：非强连通图的极大强连通子图。（两个强连通分量只要再加一条边就可成为强连通图）

强连通分量是对有向图的一种划分

---

生成树：n个顶点的连通图G的生成树是包含G中全部顶点的一个极小连通子图。

图的生成树唯一性不能确定

对于无向连通图，例如左侧，有6个结点的生成树，一定有5条边。

再任意添加1条属于原图中的边必定会产生回路。

再任意减少1条边，则必然变成非连通。

---

对于有向连通图，例如右侧，有4个结点的生成树中，只有1个入度为0的顶点v2，其他顶点的入度均为1

生成森林：在非连通图中，由每个连通分量都可以得到一棵生成树，这些连通分量的生成树就组成了一个非连通图的生成森林。

2.图的遍历

图的遍历是在从图中某一顶点出发，对图中所有顶点访问一次且仅访问一次。

要解决的问题：

1.在图中，如何选取遍历的起始顶点？

答：从编号小的顶点开始 。

2.从某个起点始可能到达不了所有其它顶点，怎么办？

答：多次调用从某顶点出发遍历图的算法

3.因图中可能存在回路，某些顶点可能会被重复访问，那么如何避免遍历不会因回路而陷入死循环。

答：附设访问标志数组visited[n] 。

4.在图中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，如何选取下一个要访问的顶点？

答：深度优先遍历和广度优先遍历。

---

深度优先遍历

基本思想：（重点在"深"）

⑴ 访问顶点v；

⑵ 从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历；（递归）

⑶ 重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。

广度优先遍历

基本思想：（重点在"广"）

⑴ 访问顶点v；

⑵ 依次访问v的各个未被访问的邻接点v1, v2, …, vk；

⑶ 分别从v1，v2，…，vk出发依次访问它们未被访问的邻接点，并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问。直至图中所有与顶点v有路径相通的顶点都被访问到。

3.图的存储

邻接矩阵

用一个一维数组存储图中顶点的信息，用一个二维数组（称为邻接矩阵）存储图中各顶点之间的邻接关系。

两顶点之间有边为1，无边为0；自身和自身无边，为0。

示意图1：无向图的邻接矩阵—>

如何求顶点i的度？

答：邻接矩阵的第i行（或第i列）非零元素的个数。

示意图2：有向图的邻接矩阵—>

如何求顶点 i 的出度？

答:邻接矩阵的第 i 行元素之和。

如何求顶点 i 的入度？

答:邻接矩阵的第 i 列元素之和。

示意图3：网图的邻接矩阵—>

邻接矩阵特点：

优点：容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。

缺点：n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。 对稀疏图而言尤其浪费空间。

邻接表

对于图的每个顶点vi，将所有邻接于vi的顶点链成一个单链表，称为顶点vi的边表（对于有向图则称为出边表），所有边表的头指针和存储顶点信息的一维数组构成了顶点表。

示意图1:无向图的邻接表—>

如何求顶点 i 的度？

答:顶点i的边表中结点的个数。

示意图2：有向图的邻接表—>

如何求顶点 i 的入度？

答：整个邻接表中邻接点域值是i的结点个数

如何求顶点 i 的所有邻接点？

答:遍历顶点 i 的边表，该边表中的所有结点都是顶点 i 的邻接点。

邻接表与邻接矩阵的比较

1.联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于该行中非零元素的个数。

2.区别：

① 对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但**邻接表不唯一（**链接次序与顶点编号无关）。

因为顶点指向的单链表各个节点的顺序是任意的

② 邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。

3.用途：邻接矩阵多用于稠密图的存储（e接近n(n-1)/2)；而邻接表多用于稀疏图的存储（e<< n(n-1)/2)

4.最小生成树

生成树的代价：设G = (V, E)是一个无向连通网，生成树上各边的权值之和称为该生成树的代价。

最小生成树：在图G所有生成树中，代价最小的生成树称为最小生成树。

MST性质：假设G=(V, E)是一个无向连通网，U是顶点集V的一个非空子集。若(u, v)是一条具有最小权值的边，其中u∈U，v∈V－U，则必存在一棵包含边(u, v)的最小生成树。

示意图：

普里姆（Prim）算法

基本思想：设G=(V, E)是具有n个顶点的连通网，T=(U, TE)是G的最小生成树，T的初始状态为U={u0}（u0∈V），TE={ }，

重复执行下述操作：在所有u∈U，v∈V-U的边中找一条代价最小的边(u, v)并入集合TE，同时v并入U，直至U=V。

流程图：

克鲁斯卡尔（Kruskal）算法

基本思想：设无向连通网为G＝(V, E)，令G的最小生成树为T＝(U, TE)，其初态为U＝V，TE＝{ }。

操作：按照边的权值由小到大的顺序，考察G的边集E中的各条边。若被考察的边的两个顶点属于T的两个不同的连通分量，则将此边作为最小生成树的边加入到T中，同时把两个连通分量连接为一个连通分量；若被考察边的两个顶点属于同一个连通分量，则舍去此边，以免造成回路，如此下去，当T中的连通分量个数为1时，此连通分量便为G的一棵最小生成树。

流程图：

---

两个算法的比较

5.图的最短路径

最短路径：

在非网图中，最短路径是指两顶点之间经历的边数最少的路径。

在网图中，最短路径是指两顶点之间经历的边上权值之和最短的路径。

单源点最短路径问题

问题描述：给定带权有向图G＝(V, E)和源点v∈V，求从v到G中其余各顶点的最短路径。

应用实例——计算机网络传输的问题：怎样找到一种最经济的方式，从一台计算机向网上所有其它计算机发送一条消息。

迪杰斯特拉(Dijkstra)算法

基本思想：设置一个集合S存放已经找到最短路径的顶点，S的初始状态只包含源点v，对vi∈V-S，假设从源点v到vi的有向边为最短路径。以后每求得一条最短路径v, …, vk，就将vk加入集合S中，并将路径v, …, vk , vi与原来的假设相比较，取路径长度较小者为最短路径。重复上述过程，直到集合V中全部顶点加入到集合S中。

流程图：

---

每一对顶点之间的最短路径问题

解决办法1：每次以一个顶点为源点调用Dijkstra算法。显然，时间复杂度为O(n3)。

解决办法2：弗洛伊德提出的求每一对顶点之间的最短路径算法——Floyd算法，其时间复杂度也是O(n3)，但形式上要简单些。

弗洛伊德(Floyd)算法

基本思想：对于从vi到vj的弧，进行n次试探：首先考虑路径vi,v0,vj是否存在，如果存在，则比较vi,vj和vi,v0,vj的路径长度，取较短者为从vi到vj的中间顶点的序号不大于0的最短路径。在路径上再增加一个顶点v1，依此类推，在经过n次比较后，最后求得的必是从顶点vi到顶点vj的最短路径。

流程图：

6.有向无环图及其应用

AOV网

在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，称这样的有向图为顶点表示活动的网，简称AOV网。

特点：

1.AOV网中的弧表示活动之间存在的某种制约关系。

2.AOV网中不能出现回路 。

示意图：

拓扑排序

拓扑序列：设G=(V，E)是一个具有n个顶点的有向图，V中的顶点序列v1, v2, …, vn称为一个拓扑序列，当且仅当满足下列条件：若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在顶点vj之前。

拓扑排序：对一个有向图构造拓扑序列的过程称为拓扑排序 。

拓扑序列使得AOV网中所有应存在的前驱和后继关系都能得到满足。

基本思想：
⑴ 从AOV网中选择一个没有前驱的顶点并且输出；
⑵ 从AOV网中删去该顶点，并且删去所有以该顶点为尾的弧；
⑶ 重复上述两步，**直到全部顶点都被输出，**或AOV网中不存在没有前驱的顶点。

示意图：

AOE网

在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，边上的权值表示活动的持续时间，称这样的有向图叫做边表示活动的网，简称AOE网。

AOE网中没有入边的顶点称为始点（或源点），没有出边的顶点称为终点（或汇点）。

AOE网的性质：
⑴ 只有在某顶点所代表的事件发生后，从该顶点出发的各活动才能开始；
⑵ 只有在进入某顶点的各活动都结束，该顶点所代表的事件才能发生。

示意图：

AOE网可以回答下列问题：

1. 完成整个工程至少需要多少时间?
2. 为缩短完成工程所需的时间, 应当加快哪些活动?

例如：

最短工期为：a1+a3=6+4=10

---

**关键路径：**在AOE网中，从始点到终点具有最大路径长度（该路径上的各个活动所持续的时间之和）的路径称为关键路径。

关键活动：关键路径上的活动（边）称为关键活动。

关键路径可能不只一条，重要的是找到关键活动

---

求最短路径方法：

---

核心在于求出：

顶点的事件最早发生时间Ve（从起点向终点，依次加上活动时间，多路径选最大值）

顶点的事件最迟发生时间Vl（从终点向起点，依次减去活动时间，多路径选最小值)

注意：起点和终点的事件最早发生时间与事件最迟发生时间对应相同

边的活动最早开始时间e（从起点向终点，该活动对应弧尾顶点的最早发生时间）

边的活动最晚开始时间l（从终点向起点，该活动对应弧头顶点的最迟发生时间-该活动的权值）

时间余量l-e

最终时间余量为0时对应的活动就是关键活动，进而可以找到对应的关键路径

关键活动中的任意一个不能按时完成，整个工程的工期就会被拖延。

虽然理论上缩短关键活动的时间可以加快工程进度，但在实际情况下，需要综合考虑技术、资源、成本和对其他活动的影响，以确定是否可以成功缩短关键活动的时间，并提前完成整个工程。

七、查找技术

1.概述

查找 ：在具有相同类型的记录构成的集合中找出满足给定条件的记录。

把查找条件限制为“匹配”，即查找关键码等于给定值的记录。

查找的结果 ：若在查找集合中找到了与给定值相匹配的记录，则称查找成功；否则，称查找失败。

平均查找长度：将查找算法进行的关键码的比较次数的数学期望值定义为平均查找长度，即：ASL

---

静态查找 ：不涉及插入和删除操作的查找 。

查找集合一经生成，便只对其进行查找，而不进行插入和删除操作，或经过一段时间的查找之后，集中地进行插入和删除等修改操作；

动态查找 ：涉及插入和删除操作的查找。

查找与插入和删除操作在同一个阶段进行，例如当查找成功时，要删除查找到的记录，当查找不成功时，要插入被查找的记录。

---

查找结构 ：面向查找操作的数据结构 ，即查找所依赖的数据结构。

线性表：适用于静态查找，主要采用顺序查找技术和折半查找技术。

树表：适用于动态查找，主要采用二叉排序树的查找技术。

散列表：静态查找和动态查找均适用，主要采用散列技术。

查找算法时间性能通过关键码的比较次数来度量。

---

2.线性表的查找技术

顺序查找（线性查找）

基本思想：从线性表的一端向另一端逐个将关键码与给定值进行比较，若相等，则查找成功，给出该记录在表中的位置；

若整个表检测完仍未找到与给定值相等的关键码，则查找失败,给出失败信息。

对顺序查找作出改进：设置“哨兵”。

哨兵就是待查值，将它放在查找方向的尽头处，免去了在查找过程中每一次比较后都要判断查找位置是否越界，从而提高查找速度

不用每次查找都判断一次i位置是否小于0。

---

折半查找（二分查找）

使用条件：线性表中的记录必须按关键码有序；必须采用顺序存储。

基本思想：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；

若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；

若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。

判定树：折半查找的过程可以用二叉树来描述，树中的每个结点对应有序表中的一个记录，结点的值为该记录在表中的位置。

通常称这个描述折半查找过程的二叉树为折半查找判定树，简称判定树。

时间复杂度:O($\log_2{n}$)

3.树表的查找技术

二叉排序树

二叉排序树（也称二叉查找树）：或者是一棵空的二叉树，或者是具有下列性质的二叉树：左<根<右。它的左右子树也都是二叉排序树。

示意图：

---

二叉排序树的插入

根据动态查找表的定义，“插入”操作在查找不成功时才进行；

分析：若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。

---

二叉排序树的构造

从空的二叉排序树开始，依次插入一个个结点 。

数据元素的输入顺序不同，则得到的二叉排序树形态也不同。

总结：

一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列;
每次插入的新结点都是二叉排序树上新的叶子结点;
找到插入位置后，不必移动其它结点，仅需修改某个结点的指针；
新插入的结点没有破坏原有结点之间的关系**

---

二叉排序树的删除

和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。

情况1——被删除的结点是叶子结点

操作：将双亲结点中相应指针域的值改为空。

示意图:

情况2——被删除的结点只有左子树或者只有右子树

操作：将双亲结点的相应指针域的值指向被删除结点的左子树（或右子树）。

示意图：

情况3——被删除的结点p既有左子树PL也有右子树PR

可知中序遍历的序列为PL，p，PR。

为了替换被删除结点p而保持二叉树有序的性质，

可以用PL中最大的结点替换p，也可以用PR中最小的结点替换p，然后删除用来替换的重复结点。

示意图：

二叉排序树的查找

查找成功：从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点;

查找失败：从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。

例如：

二叉排序树的查找性能取决于二叉排序树的形状，O($\log_2{n}$)在和O(n)之间。

示意图：

平衡二叉树

平衡二叉树：或者是一棵空的二叉排序树，或者是具有下列性质的二叉排序树：

⑴ 根结点的左子树和右子树的深度最多相差1

⑵ 根结点的左子树和右子树也都是平衡二叉树

平衡因子：结点的平衡因子定义为该结点的左子树的深度与右子树的深度之差。(每个结点都要满足)

示意图：

最小不平衡子树：在平衡二叉树的构造过程中，以距离插入结点最近的、且平衡因子的绝对值大于1的结点为根的子树。

设结点A为最小不平衡子树的根结点，对该子树进行平衡调整归纳起来有以下四种情况：

1. LL型
2. RR型
3. LR型
4. RL型

---

LL型（左子树的左子树）

插入位置在最小不平衡子树根结点左孩子的左子树上

操作：向右旋转，换子树。

示意图：

RR型（右子树的右子树）

插入位置在最小不平衡子树根结点右孩子的右子树上

操作：向左旋转，换子树。

示意图：

LR型（左子树的右子树）

插入位置在最小不平衡子树根结点左孩子的右子树上

操作：旋转两次，先向左旋转，再向右旋转，先局部后整体，同样要换子树。

示意图：

RL型（右子树的左子树）

插入位置在最小不平衡子树根结点右孩子的左子树上

操作：旋转两次，先向右旋转，再向左旋转，先局部后整体，同样要换子树。

示意图：

4.散列表的查找技术

散列的基本思想：在记录的存储地址和它的关键码之间建立一个确定的对应关系。

这样，不经过比较，一次读取就能得到所查元素的查找方法。

散列表：采用散列技术将记录存储在一块连续的存储空间中，这块连续的存储空间称为散列表。

散列函数：将关键码映射为散列表中适当存储位置的函数。

散列地址：由散列函数所得的存储地址 。

示意图：

散列既是一种查找技术，也是一种存储技术。

散列技术的关键问题：

⑴ 散列函数的设计。如何设计一个简单、均匀、存储利用率高的散列函数。

1.计算简单。散列函数不应该有很大的计算量，否则会降低查找效率。

2.函数值即散列地址分布均匀。函数值要尽量均匀散布在地址空间，这样才能保证存储空间的有效利用并减少冲突。

⑵ 冲突的处理。如何采取合适的处理冲突方法来解决冲突。

1.拉链法（开散列方法）

2.开放定址法（闭散列方法）

---

冲突：对于两个不同关键码ki≠kj，有H(ki)＝H(kj)，即两个不同的记录需要存放在同一个存储位置,ki和kj相对于H称做同义词。

开放定址法（闭散列方法）

由关键码得到的散列地址一旦产生了冲突，就去寻找下一个空的散列地址，并将记录存入。

1.线性探测法

若发生冲突，则挨个向后找

示意图：

2.二次探测法

若发生冲突，则左右横跳

示意图：

3.随机探测法（不重要）

当发生冲突时，下一个散列地址的位移量是一个随机数列，即寻找下一个散列地址的公式为：

Hi=(H(key)+di)% m （di是一个随机数列，i=1，2，……，m-1）

---

拉链法（开散列方法）

也叫做链地址法

基本思想：将所有散列地址相同的记录，即所有同义词记录存储在一个单链表中（称为同义词子表），

在散列表中存储的是所有同义词子表的头指针。

用拉链法处理冲突构造的散列表叫做开散列表。

开散列表不会出现堆积现象。

设n个记录存储在长度为m的散列表中，则同义词子表的平均长度为n / m。

示意图：

开散列表和闭散列表的比较

5.B树

B树是一种多路平衡查找树，能够保持数据的有序性，使数据的查找、插入、删除等操作都在对数时间内完成。

B树定义为一颗m阶的B树，或者为空树，或为满足下列特性的m叉树：（也满足左<根<右）

1.树中每个结点最多有m颗子树

2.若根结点不是终端结点，则至少有两颗子树

3.除根结点之外的所有非终端结点至少有[m/2]颗子树（向上取整）

4.有n个子节点的非终端结点拥有n-1个关键码

5.所有的叶子结点位于同一层

示意图：

B树的插入

假定要在m阶B树中插入关键码k，关键码数目的最大值为m-1。

查找过程分为两个阶段：

1.查找-定位

2.分裂-提升

B树的构造

B树的构造就是逐一插入各个关键码的过程

流程图：

B树的删除

假定key是结点q中第i个关键码，若要删除key，有以下几种情况：

1.若结点q不是终端结点，则用子树中的最小键值x来"替换key"，然后删除原有x

2.如果q是终端结点，且关键码的个数**大于[m/2]-1，**则可直接删除key

例如：

3.如果q是终端结点，删除一个关键码后，关键码的个数<[m/2]-1,则不符合m阶B树的要求，需要从兄弟结点借关键码或合并结点，

分为两种情况：

(1)兄弟结点的关键码个数>[m/2]-1,足够借，那么q就从该兄弟借一个关键码，

借来的关键结点上移到父结点，父结点相应的关键码下移到被删结点中。

例如：

(2)如果兄弟结点的关键码格个数<=[m/2]-1,不够借，则将双亲结点相应关键码下沉并合并，

合并过程可能一直上传到根结点，并使B树的树高减少一层。

例如：

八、排序技术

排序：将杂乱无章、毫无规律的数据元素，按照一定的方法以其关键码顺序排列成升序或降序的过程

排序算法的稳定性：假定在待排序的记录集中，存在多个具有相同键值的记录，

若经过排序，这些记录的相对次序仍然保持不变，即在原序列中，ki=kj且ki在kj之前，而在排序后的序列中，ki仍在kj之前，则称这种排序算法是稳定的；否则称为不稳定的。

排序的分类

1. 内排序：在排序的整个过程中，待排序的所有记录全部被放置在内存中
2. 外排序：由于待排序的记录个数太多，不能同时放置在内存，而需要将一部分记录放置在内存，另一部分记录放置在外存上，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。

1.插入排序

直接插入排序

基本思想：在插入第 i（i＞1）个记录时，前面的 i-1个记录已经排好序。

示意图：

---

插入的流程图：

关键问题：

1.如何构造初始的有序序列？

答：在第一趟进行插入排序时假定初始有序序列只有一个记录的关键码。

将第1个关键码看成是初始有序序列，然后从第2个记录的关键码依次插入到有序序列中，直至将第n个记录插入。

2.如何查找待插入关键码的插入序列？

答：这相当于在一个有序序列中进行查找，在对第i个记录进行插入时，

首先初始化带比较元素的下标k=i-1，将待插入关键码保存在下标为0的单元。

---

直接插入排序算法的时间复杂度为O(n^2^)

空间性能：需要一个记录的辅助空间。

直接插入排序算法是一种稳定的排序算法。

直接插入排序算法简单、容易实现，适用于待排序记录基本有序或待排序记录较小时。

当待排序的记录个数较多时，大量的比较和移动操作使直接插入排序算法的效率降低。

如何改进直接插入排序?

注意到，在插入第 i（i＞1）个记录时，前面的 i-1 个记录已经排好序，

则在寻找插入位置时，可以用折半查找来代替顺序查找，从而减少比较次数。

---

希尔排序

基本思想：将整个待排序记录分割成若干个子序列，在子序列内分别进行直接插入排序，

待整个序列中的记录基本有序时，对全体记录进行直接插入排序。

分割待排序记录的目的:

1. 减少待排序记录个数；
2. 使整个序列向基本有序发展。

流程图：

关键问题：

1.如何分割待排序记录？

答“将相隔某个“增量”的记录组成一个子序列。

增量应如何取：希尔最早提出的方法是d1=n/2，d(i+1)=di/2。

2.子序列内如何进行直接插入排序？

答：在插入记录r[i]时，自r[i-d]起往前跳跃式（跳跃幅度为d）搜索待插入位置，并且r[0]只是暂存单元，不是哨兵。

当搜索位置＜0，表示插入位置已找到。
在搜索过程中，记录后移也是跳跃d个位置。
在整个序列中，前d个记录分别是d个子序列中的第一个记录，所以从第d+1个记录开始进行插入。

希尔排序的时间性能在O(n^2^)和**O($\log_2{n}$)**之间。当n在某个特定范围内，希尔排序所需的比较次数和记录的移动次数约为O(n1.3 ) 。

---

2.交换排序

交换排序的主要操作是交换，其主要思想是：（反序则交换）

在待排序列中选两个记录，将它们的关键码相比较，如果反序（即排列顺序与排序后的次序正好相反），则交换它们的存储位置。

冒泡排序

基本思想：两两比较相邻记录的关键码，如果反序则交换，直到没有反序的记录为止。

示意图：

关键问题：

1.如何区分有序区和无序区？

答：设变量exchange记载记录交换的位置，则一趟排序后，exchange记载的一定是这一趟排序中记录的最后一次交换的位置，

且从此位置以后的所有记录均已经有序。

因此，可以用exchange来标记有序区和无序区。有序区的元素不进行后续的两两比较。

示意图:

2.如何确定起泡排序的范围？

答：bound位置的记录是无序区的最后一个记录，则每趟起泡排序的范围是r[1] ~ r[bound]。

在一趟排序后，从exchange位置之后的记录一定是有序的，所以bound=exchange。

3.如何判别起泡排序的结束？

答：在每一趟起泡排序之前，**令exchange的初值为0，**在以后的排序过程中，只要有记录交换，exchange的值就会大于0。

这样，在一趟比较完毕，就可以通过exchange的值是否为0来判别是否有记录交换，从而判别整个起泡排序的结束。

冒泡排序的时间复杂度为O(n^2^)

---

快速排序

基本思想：首先选一个轴值（即比较的基准），通过一趟排序将待排序记录分割成独立的两部分，（二分法）

前一部分记录的关键码均小于或等于轴值，后一部分记录的关键码均大于或等于轴值，

然后分别对这两部分重复上述方法，直到整个序列有序。

关键问题：

1.如何选择轴值？

选择轴值的方法：
1.使用第一个记录的关键码；
2.选取序列中间记录的关键码；
3.比较序列中第一个记录、最后一个记录和中间记录的关键码，取关键码居中的作为轴值并调换到第一个记录的位置；
4.随机选取轴值。

选取不同轴值的后果：

决定两个左右子序列的长度，左右子序列的长度最好相等。

2.如何实现一次划分？

答：一次划分也称为分割操作，根据轴值将待排序序列分为左右两个子序列，

所有比轴值小的元素摆放在轴值的前面，所有比轴值大的元素摆放在轴值的后面

流程图：

3.如何递归地处理分割后的子序列？

只需要将分割后的两个子序列进一步递归地分割为更小的子序列即可，直到子序列无法再继续分割为止。

快速排序的时间复杂度为O(n$\log_2{n}$)

大多数情况下，快速排序要比其他排序算法更快。

3.选择排序

选择排序的主要操作是选择，其主要思想是：每趟排序在当前待排序序列中选出关键码最小的记录，添加到有序序列中。

简单选择排序

基本思想：第i 趟在n-i+1（i=1,2,…,n-1）个记录中选取关键码最小的记录作为有序序列中的第i个记录。

流程图：

简单选择排序思路非常简单，只需要从无序区选择最小关键码，并交换至无序区第一个元素即可。

每一趟排序只交换一对元素，有序区长度增加1，无序区长度减少1，直至整个序列有序，因此总共需要进行n-1次交换。

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

---

堆排序

改进的着眼点：如何减少关键码间的比较次数。

若能利用每趟比较后的结果，也就是在找出键值最小记录的同时，也找出键值较小的记录，则可减少后面的选择中所用的比较次数，从而提高整个排序过程的效率。

堆是具有下列性质的完全二叉树：

1**.每个结点的值都小于或等于其左右孩子结点的值（称为小根堆**），

2.每个结点的值都大于或等于其左右孩子结点的值（称为大根堆）。

---

基本思想：首先将待排序的记录序列构造成一个大根堆，此时，选出了堆中所有记录的最大者，然后将它从堆中移走，并将剩余的记录再调整成堆，这样又找出了次小的记录，以此类推**，直到堆中只有一个记录。**

堆调整：将剩余关键码序列重新调整成为堆，这样会在堆顶得到剩余关键码序列中的最大值。

关键问题：

1.如何将n个关键码的序列建成堆？

答：将初始序列看成一个完全二叉树，将初始序列序列的关键码按初始顺序从上到下，从左到右依次填充到完全二叉树中。

根据n个结点的完全二叉树的性质，最后一个分支结点的结点下标为[n/2],（向下取整）那么从该结点为根的子树开始向前逐一进行堆调整，

使每一颗子树均成为堆，直到根结点。（自下而上调整）

2.如何处理堆顶记录，进行排序？

答：根据大根堆的性质，根结点就是序列的最大值，而序列的次大值位于根结点的左、右孩子之一。

因此建队以后，只需要输出根结点，再将剩余关键码调整成堆即可。

将堆顶的根结点与堆的最后一个元素，即堆中最下层最右侧的元素进行交换，交换后，将最大值排除在待排序序列之外。

示意图：

3.输出堆顶关键码后，调整剩余关键码，使其成为一个新堆

答：在输出堆的根结点之后，剩下n-1个元素。此时，堆已经被破坏，但只有根结点不满足堆的条件。

因此，对根结点进行堆调整即可。

当所有结点都输出时，堆排序结束。

堆排序的时间复杂度为：O(n$\log_2{n}$)

---

4.归并排序

归并排序的主要操作是归并，其主要思想是：将若干有序序列逐步归并，最终得到一个有序序列。

归并：将两个或两个以上的有序序列合并成一个有序序列的过程。

---

二路归并排序

基本思想：将一个具有n个待排序记录的序列看成是n个长度为1的有序序列，然后进行两两归并，

得到n/2个长度为2的有序序列，再进行两两归并，得到n/4个长度为4的有序序列，……，直至得到一个长度为n的有序序列为止。

例如：

关键问题：

1.如何将两个有序序列合成为一个有序序列？

示意图：

2.怎样完成一趟归并？

在一趟归并中，除最后一个有序序列外，其它有序序列中记录的个数相同，用长度h表示。

设参数i指向待归并序列的第一个记录，归并的步长是2h，在归并过程中，有以下三种情况：

①若i≤n-2h+1，则相邻两个有序表的长度均为h，执行一次归并，完成后i加2h，准备进行下一次归并；

②若i＜n-h+1，则表示仍有两个相邻有序表，一个长度为h，另一个长度小于h，则执行两个有序表的归并，完成后退出一趟归并。

③若i≥n-h+1，则表明只剩下一个有序表，直接将该有序表送到r1的相应位置，完成后退出一趟归并。

3.如何控制二路归并的结束？

答：开始时，有序序列的长度h=1，结束时，有序序列的长度h=n，用有序序列的长度来控制排序的结束。

二路归并排序算法的时间复杂度：O(n$\log_2{n}$)

5.分配排序

分配排序是基于分配和收集的排序方法，其基本思想是：

先将待排序记录序列分配到不同的桶里，然后再把各桶中的记录依次收集到一起。

桶式排序

基本思想是：假设待排序记录的值都在0～m-1之间，设置m个桶，

首先将值为i的记录分配到第i个桶中，然后再将各个桶中的记录依次收集起来。

关键问题：

1.如何在计算机中表示桶？

由于具有相同键值的记录可能会有多个，所以，应采用链接存储，

为保证排序的稳定性，可以设m个链队列作为桶的存储结构。

为避免在分配和收集的过程中移动元素，采用静态链表作为链队列和待排序记录序列的存储结构

示意图：

桶排序流程图：

桶式排序的时间复杂度为O(n+m)。

---

基数排序

桶式排序适用于单键排序的情况，在一定条件下具有很高的时间效率，但桶的个数m极大限制了排序的应用。

基数排序是对桶式排序的改进和推广；如果说桶式排序是一维的基于桶的排序，那么基数排序就是多维的基于桶的排序。

举个例子：用桶式排序对[0,99]之间的数进行排序，需要100个桶，分配一次，收集一次，完成排序；

而基数排序只需要0-9总共10个桶（即关键字为数字0-9），依次进行个位和十位的分配和收集从而完成排序。

对多关键码排序有以下两种基本方法：

1.最主位优先法(MSD)

2.最次位优先法(LSD)

例如：采用最次位优先法

基数排序的时间复杂度为O(d(n +m))，d为关键码的个数

---

6.总结

各种排序算法时间复杂度的比较：

各种排序算法空间复杂度的比较：

各种排序算法稳定性的比较：

稳定的：直接插入排序、起泡排序、归并排序和分配排序；

不稳定的：希尔排序、简单选择排序、快速排序和堆排序。

---

各种排序算法简单性的比较：

简单算法：直接插入排序、简单选择排序和起泡排序

改进后的算法：希尔排序、堆排序、快速排序和归并排序，这些算法都很复杂。

从待排序的记录个数n的大小看，

n越小，采用简单排序方法越合适，

n越大，采用改进的排序方法越合适。

因为n越小，O(n2)同O(nlog2n)的差距越小，并且输入和调试简单算法比输入和调试改进算法要少用许多时间。

---

记录本身信息量越大，移动记录所花费的时间就越多，所以对记录的移动次数较多的算法不利。

当待排序记录按关键码有序时，插入排序和起泡排序能达到**O(n)**的时间复杂度；

对于快速排序而言，这是最坏的情况，此时的时间性能蜕化为O(n2)；

选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。

---

数据结构复习笔记初步整理完毕！

一定会有所收获！！！