数据结构课堂笔记

数据结构的基本概念

线性表

定义：若干数据元素组成的线性序列。

线性表的存储结构

数组表示

链表表示

上述单链表在插入和删除时，需要把头结点作为特殊情况处理，为统一算法，可在单链表的头结点之前增加一个头结点（头结点不放数据），由此构成带表头的单链表。

表头结点≠头结点，表头结点在头结点之前。

单循环链表：尾结点指向头结点。

带表头的单循环链表：尾结点指向表头结点。

双向链表：结点增加一个指针数据指向前一个结点。

堆栈

限定数据进出于表的同一端，先进后出，入栈和出栈都从栈顶元素开始。

顺序栈

数组实现，可令一int数据作为栈顶元素的指示。

链式栈

链表实现，可令一结点指针作为栈顶元素的指示

实际应用

中缀转后缀表达式

设计栈内优先级(In-Stack Priority, ISP) 和 栈外优先级(InComing Priority, ICP)

从头依次扫描中缀表达式中每一元素(字符)

​ 若为操作数，直接输出；

​ 若为界符)，在操作栈中连续出栈，直至出栈元素为界符(，界符( 只出栈不输出；

​ 若为操作符，则比较当前扫描元素的栈外优先级和栈顶元素的栈内优先级，

​ 若前者 ≤ 后者，则执行连续出栈输出操作，直至栈顶元素的栈内优先级＜当前扫描元素的栈内优先级，再将当前扫描元素进栈；

​ 否则，操作符进栈；

扫描完毕，将栈中元素依次出栈输出。

队列

限定数据在表的一端入列，在另一端出列。通常为循环队列表示

数组表示

可令两个int型变量front，rear指向队头和队尾元素，队列容量为m

入列：front后移，front =（front+1）% m

出列：rear后移，rear =（rear+1）% m

front所指存储单元不存放数据

front == rear时表示空队列

（rear+1）%队列容量==front时表示满队列，即此时队列中有m-1个元素。

链表表示

可令两个结点指针front，rear指向队头和队尾元素结点。

数组

一维数组

实际应用

字符串匹配算法

KMP算法

二维数组

行优先存储

列优先存储

实际应用

三角矩阵

稀疏矩阵

稀疏矩阵的快速转置算法

多维数组

可供参考的抽象数据类型：

若干个int型变量，表示维度坐标

一个数据类型指针，指向位于维度坐标上的数据

树与二叉树

定义

基本术语

二叉树

二叉树的五种姿态

性质

1. 第 i ( i ≥ 1)层上最多有2^i-1^个结点
2. 高度为h的二叉数上至多有2^h^-1个结点
3. 包含n个结点的二叉树高度至少为log~2~(n+1)向上取整，最高为n
4. 在一棵二叉树中，叶子结点为N0，度为2的结点数为N2，那么N0=N2+1；

满二叉树

完全二叉树

完全二叉树的两个性质

1. 

2. 将完全二叉树按层次遍历顺序，从0编号

   

扩充二叉树（2-树）

存储表示

1、顺序

2、链表

遍历二叉树（先序，中序，后序递归，以及层次遍历）

层次遍历需要借助队列

赫夫曼树及应用

定义：赫夫曼树又名最优二叉树，是带全路径长度最小的二叉树。如下图：

注意：赫夫曼树并不是满二叉树，是正则二叉树（也叫正规二叉树或最优二叉树），在构造哈夫曼树时,是从叶子节点向根节点的方向进行的,每次都是两个两个成对来形成一个新的分支节点，所以不存在度为1的节点，即其中只有度为0和度为2的结点，因为：
n0 = n2 + 1；//这是二叉树中固有的公式（n0是度为0的结点数，n2是度为2的结点数），具体可见公式推理
n = n0 + n2；//n为所有结点数
所以 n = 2n0 - 1，即n0 = (n + 1) / 2；
又叶子结点n0对应的即是不同的编码，所以在赫夫曼编码中有多少个叶子节点就能得到多少个码字。

赫夫曼树编码

答： 赫夫曼树并不是满二叉树，是正则二叉树（也叫正规二叉树或最优二叉树），在构造哈夫曼树时,是从叶子节点向根节点的方向进行的,每次都是两个两个成对来形成一个新的分支节点，所以不存在度为1的节点，即其中只有度为0和度为2的结点(附带一个二叉树结论：n0=n2+1，其中，n0是度为0的结点数，n2是度为2的结点数)。结点关系有如下：
n=n0+n2;
n=2n2+1;
同时。赫夫曼树的带权值最优路径是所有叶子节点的带权路径之和。
此外，赫夫曼树还有一条规定：左右孩子权值之和为父结点权值，WPL=∑wl（w为个叶子权值，l为叶子的(深度-1)）。
注意：上述是常见的赫夫曼树，除此之外还有度不为2的，也叫最优m叉树。其结点也只有度为0和度为m两种，即X+n0=n（X为度m的结点数，n为总结点数）。那么其结点关系也有如下：
n=X+n0;
n=m*X=1；
赫夫曼树的生成：前提是给定所有叶子结点的权值序列。
1）从序列中找出权值最小的两个节点，作为最底层叶子节点并求和得到父节点，生成子树；
2）然后从剩下的序列和上述子树根节点中找出最小的两个并求和，生成新的子树；
3）重复1）、2）步骤。
如图：

赫夫曼编码（前缀编码）：
1）将给定字符串根据每个符号出现次数的大小，重新排序成一个字符频率由小到大的表格，如图：

2）将字符频率作为权值，对字符进行赫夫曼树生成，如下图：

3）再对叶子进行编码，从上到下，所有左链结0，右链接为1。结果如下图：

故字符串”alibaba“占用的编码空间为：13+22+（3+3）*1=13（bit）。

6、树的孩子-兄弟链表存储方式（树转化为二叉树的方法）和 二叉树转化为森林
（1）孩子-兄弟链表存储方式是左指针指向孩子链，右指针指向兄弟链。这样就可以将普通树结构转化为二叉树结构，经过此转化后，原树的后序遍历变为二叉树的中序遍历，前序遍历依然是前序遍历（注意：树是没有中序遍历的，二叉树才有中序遍历）。

注意：树变成二叉树的情况下，

根节点无右兄弟，右指针域一定为空； -----------------1个
除根节点之外的每个非终端节点都有孩子，其下的分支一定有最终的叶子节点，右指针域为空；-----------------n-1个
其中最后一个非终端节点无右兄弟，右指针域也为空。-------------------加1个
因此，若树有N个非终端结点，那么右指针为空的结点共有n+1个。
（2）二叉树转化为森林正好与森林转化为二叉树相反，即：将二叉树结点的左孩子保留，右孩子变为结点的兄弟。

静态搜索

平均搜索长度

给定值与集合中元素的关键字值的平均比较次数称为平均搜索长度(Average Search Length,ASL)。平均搜索长度可用于衡量搜索算法的时间效率，其计算需要分搜索成功和失败两种情况讨论。

顺序搜索

无序表：从头到尾依次扫描，直至扫描成功，或扫描完毕后不存在

有序表：以从小到大为例，从头开始扫描有序表，逐个比较待搜索元素关键字（以下简称x）和表中的关键字，当表中元素关键字大于等于 x 时，停止搜索。此时若表中元素关键字等于 x ，搜索成功；否则搜索失败。

对半搜索

前提：搜索对象必须是有序表且是顺序存储结构

令low等于表中的某一区间的左端元素下标，hign等于表中的某一区间的右端元素下标，m为low和high的中点（m=(low+high)/2），将 x 与 m 比较，若 x=m，则搜索成功；若 x<m ，则在[low,m-1]区间里进行递归；若 x>m，则在[m+1,high]区间里进行递归；若递归完整个有序顺序表后仍未搜索成功，则搜索失败。

二叉判定树

动态搜索

二叉搜索树

二叉搜索树就像二叉树版的对半搜索。

二叉排序树的删除

叶节点：直接删除

仅有一棵非空子树的节点：接上

有两颗非空子树的节点：用左子树中最大元素所在节点或右子树中最小元素所在节点替代该节点，随后将原本叶节点删去。

二叉平衡树（AVL树）

二叉平衡树具有以下两个性质：

1、其根的左右子树高度之差的绝对值不超过1

2、其根的左右子树都是二叉平衡树

平衡因子：该节点左子树与右子树高度之差的绝对值

二叉平衡树的调整

当新元素的插入破坏了二叉树的平衡时，需要找到从新插入节点回溯到根节点路径上第一个出现的非平衡节点（即平衡因子绝对值大于1的节点，记为 s ），以s节点为根节点的子树称为需要平衡的最小子树，将最小子树平衡后，整棵树也将平衡。

实际中，要操作的是从s节点到新插入节点路径上的前三个节点。

1、单侧（LL或RR）

2、双侧（LR或RL）

m叉搜索树

每个节点最多有m叉，每个节点最多存放m-1个元素，节点与分叉的元素排列都有序

B-树

定义：一棵m阶B-树是一颗m叉搜索树，它为空树，或满足以下性质：

1. 根节点至少有两个孩子
2. 除根节点和失败节点外的每个节点至少有⌈m/2⌉ 个孩子(向上取整)
3. 所有失败节点都在同一层上

B-树的插入

\Tencent\qq缓存文件\1069785399\Image\C2C\B723264F25008CFAA33193CAB021F410.png)

B-树的删除

\Tencent\qq缓存文件\1069785399\Image\C2C\DEE1917912888053132657E23BDF2659.png)

\Tencent\qq缓存文件\1069785399\Image\C2C\EE2B64CE6669C0AF7ECE0075E2642335.png)

散列表（哈希表）

散列函数

一个合适的，用来生成存放地址（数组地址）的函数

• 除留余数法：h(key)=key mod M 其中M是散列表长度，一般而言，选择一个不超过M的最大素数P，令h(key)=key mod P 效果相对较好。

• 平方取中法：

  $$h(key)=⌊\frac{M}{W}(key^2\mod W)⌋$$

  其中W=2^w^和M=2^k^都是 2 的幂，W是计算机位长（32、64等），M是散列表长

• 折叠法：按一定长度将关键字key划分，再将每小段相加，结果为h(key)。若 结果超过位数，则将最高位去掉，直至符合要求。

• 数字分析法

散列冲突处理

开拉链法

为每个散列地址建立一个单链表，散列地址相同的元素都排在单链表里（有序无序都行）

开地址法

元素按照某种探查方法直接存放在一个足够大的主表中

线性探查法

h~i~=(h(key)+i) mod M, i=0,1,2,…,M-1

二次探查法

h~2i+1~(key)=(h(key)+i^2^) mod M, i=0,1,2,…,(M-1)/2

h~2i~(key)=(h(key)-i^2^) mod M, i=0,1,2,…,(M-1)/2

奇加偶减

双散列法

需要用到两个散列函数h~1~、h~2~

H~i~=(h~1~(key)+i*h~2~(key)) mod M, i=0,1,2,…,M-1

h~2~应满足：对任意key，h~2~(key)应小于M，且最好与M互质。
这样形成的探查序列就能够保证最多经过M次探查就可以遍历散列表中的所有地址。

图

图的相关基础知识

由顶点和边构成图，根据边是否有向分为有向图和无向图，有向图记为G1=（V1，{A1}），无向图记为G2=（V2{E2}）。
路径：无向图中从顶点v到v’称为路径；
简单路径：路径中所有顶点不重复出现的称为;
关键路径：从源点到汇点的路径长度最长的路径叫关键路径；
第一和最后顶点相同的路径称为环，除了第一和最后顶点外，其余顶点不重复出现的称为简单环。
连通分量：连通分量是指无向图中的极大连通子图；有向图中的极大强连通子图称做有向图的强连通分量。
有向完全图：有向完全图是指图中各边都有方向，且每两个顶点之间都有两条方向相反的边连接的图。故n个顶点的有向完全图有n(n-1)条边。
图的存储：可以用邻接矩阵、邻接表、十字链表、邻接多重表存储。
邻接矩阵：为方阵，阶数等于顶点数，矩阵元素就是边的权值（若两点无连接则权值为无穷大），元素所在行列则为边两端的顶点。注意：无向图的邻接矩阵具有对称性，所以一般采用压缩模式，只填写矩阵上三角或下三角。（可见，邻接矩阵大小只和图的顶点数有关）
邻接表：图的每一个顶点都建立一个单链表，该链表中的每个结点是以该顶点为尾的边（无向图则为依附于该顶点的边）。故同顶点数的有向图的邻接表结点数是无向图一半。
有向图的拓扑排序：
（1）从图中找到无前驱的顶点输出；
（2）删除该顶点及以其为尾弧；
（3）重复（1）（2），直至删完所有顶点。

图的遍历

（1）深度优先搜索：类似树的先根遍历；（用栈作为辅助数据结构，这是根据结点遍历顺序决定的）
（2）广度优先搜索：类似树的按层搜索。（用队列作为辅助数据结构，这是根据结点遍历顺序决定的）
广度优先搜索（BFS）是最适合解决无权值或权值相等的单源最短路径问题的。无权值或权值相等的单源最短路径是指：从图中某一点作为顶点出发，向终点搜索，找到最短的一条路径。
深度优先遍历图的方法是，从图中某顶点v出发：
①访问顶点v;
②依次从v的未被访问的邻接点（任何一个邻接点即可，不一定是深度最大的那个邻接点）出发，对图进行深度优先遍历;直至图中和v有路径相通的顶点都被访问;
③若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。

（3）BFS和DFS生成树算法
①根据深度优先遍历思想，BFS生成树算法所生成的树高是要小于或等于DFS算法省的树高；
②有向环的判断方式 ：
拓扑排序（找不到无前驱，但顶点未删完，表示有环）；
深度优先排序（找到重复访问的顶点表示有环）。

（1）事件发生时间

事件 D 的最早发生时间：
从源点 A 开始到达 D 的所有路径加和的最大值 max{<a1,a3>,<a2,a5>} = 6；
事件 D 的最迟发生时间 ：
首先求出汇点 F 的最早发生时间 max{<a1,a4,a8>,<a1,a3,a7>,<a2,a5,a7>,<a2,a6>} = 8
汇点 F 的最早发生时间 - max{汇点逆向到事件 D 的路径累加之和} = 8- max{} = 5；
（2）活动发生时间

活动a3的最早发生时间：
以 a3 该活动为出发点的事件
B—a3—>D ， 即， B 事件的最早发生时间；
活动a3的最迟发生时间：
以a3 该活动对应的箭头所指向的事件的最迟发生时间 - a3 活动持续时间
B—a3—>D ， 即， D 事件的最迟发生时间 - a3 活动的持续时间 = 5 - 2 = 3 。

综上所述，无论事件还是活动：
最早发生时间，事件=活动，是从前往后计算；
最迟发生时间，都是从后往前计算（活动最迟发生时间与活动持续时间有关）。

（3）补充：

AOE网( Activity On Edge Network )： 在带权有向无环图中，以顶点表示事件，有向边表示活动，边上的权值表示该活动持续的时间（上述例子就是AOE）；

AOV网( Activity On Vertex Network )： 在有向图中若以顶点表示活动，有向边表示活动之间的先后关系。

求图的最短路径（迪杰斯特拉算法、弗洛伊德算法）

迪杰斯特拉算法

①迪杰斯特拉算法是典型的单源最短路径算法，用于计算图中一个源节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

②算法过程：
(a)初始化：用起点v到该顶点w的直接边(弧)初始化最短路径，否则设为∞；
(b)从未求得最短路径的终点中选择路径长度最小的终点u：即求得v到u的最短路径；
©修改最短路径：计算u的邻接点的最短路径，若(v,…,u)+(u,w)<(v,…,w)，则以(v,…,u,w)代替；
(d)重复(b)©，直到求得v到其余所有顶点的最短路径。

③时间复杂度=O(n^2)；

弗洛伊德算法

①弗洛伊德算法是求解图中任意两点间的最短路径的一种算法，它是一种经典的动态规划算法；

②算法思想：每次从 vi 到 vj 的所有可能存在的路径中，选出一条长度最短的路径。一共进行n次；

③时间复杂度=O(n^3)；

排序算法

稳定性：排序前后关键字相同的元素前后位置是否变化，不变，稳；变，不稳

以下表格均以从小到大排序为结果

算法名称	简介	时间复杂度	稳定性
简单选择	每趟寻找最小元素与待排序列第一个元素交换，而后待排序列缩减一元素		稳定
直接插入	每趟将待排序列的第一个元素向前挪，直到其在前方的有序序列中有序安置，而后待排序列缩减一元素		稳定
冒泡			稳定
快速	每趟在待排(子)序列中选择一个元素作为标准，小于标准的划分到左序列，大于标准的划分到右序列，直到待排子序列中只有一个元素	最好/平均：O(nlogn) 最坏：O(n^2^)	不稳定
两路合并	每趟两两合并有序(子)序列，若为奇数则最后一个不合并，而后待排序列扩增 合并：另建一个临时数组用于存放		稳定
堆排	先将待排序列建成最大堆；每趟将堆顶元素与末尾元素交换，而后待排序列缩减一元素		不稳定