数据结构 – 期末复习

主要涉及查找、外部排序、图等知识点

查找

ASL (Average Search Length， 平均查找长度) 定义为需要和给定值进行比较的关键字的个数的期望值

静态顺序表与静态树表

顺序查找

表头设置哨兵，值为待查找值，从后往前查找
循环中省掉了一次查找
改进：

  1. 按元素被查找的频率升序排序
  2. 将刚查找的元素移至表尾（已发生的事会重复发生）

二分查找

ASLsucc=n+1nlog⁡2(n+1)−1ASL_{succ}=\frac{n+1}{n}\log_2(n+1)-1
适用于大量的静态数据

Fibonacci查找

int Fib_search(RecType ST[] , KeyType key , int n)
//在长为n的有序表ST中用Fibonacci方法查找关键字为key的记录，其中n=fib(j)
{ int Low=1, High, Mid, f1, f2 ;
High=n; f1=fib(j-1); f2=fib(j-2);
while (Low<=High) {
    Mid=Low+f1-1;
    if ( EQ(ST.[Mid].key, key) ) return(Mid) ;
    else if ( LT(key, ST.[Mid].key) )
        { High=Mid-1 ; f2=f1-f2 ; f1=f1-f2 ; }
    else 
        { Low=Mid+1 ;f1=f1-f2 ; f2=f2-f1 ; }
} return(0);}

插值查找

Key与ST.elem[i]比较，其中
i=Key−ST.elem[l].keyST.elem[h].key−ST.elem[l].key(h−l+1)i =\frac{Key−ST.elem[l].key}{ST.elem[h].key−ST.elem[l].key}(h − l + 1)
适用于关键字均匀分布

次优二叉树

每次取下值最小的节点作为新的根节点
ΔPi=∣∑j=i+1hwj−∑j=li−1wj∣\Delta P_i=|\sum_{j=i+1}^h w_j-\sum_{j=l}^{i-1}w_j|
需要预先求得wjw_j的前缀和swjsw_j数组

索引顺序查找/分块查找

附加一个索引表，块间有序，块内无序
当每块记录数为ss时

ASL=12(ns+s)+1ASL=\frac{1}{2}(\frac{n}{s}+s)+1

动态查找表

二叉排序树（BST）

节点p删除：
方法一：用p的直接前驱（或直接后继）节点s代替p，然后删除s
方法二：取s为p的左子树中最右的节点，将p的右子树作为s的右子树

平衡二叉排序树（AVL）

节点的平衡因子bf（Balance Factor）=左子树深度-右子树深度

AVL树的插入

插入新结点时，从插入位置向根回溯，检查各节点平衡因子
从发生不平衡的节点起，沿刚才回溯的路径取直接下两层的节点
若这三个节点处于一条直线上，则采用单旋转进行平衡化
若这三个节点处于一条折线上，则采用双旋转进行平衡化

AVL树的删除

  1. 若删除的节点为叶子结点，则直接删除，然后一次向上调整为AVL树
  2. 若删除的节点只有左孩子或右孩子，则用孩子替换
  3. otherwise，用左子树的最右节点替换为删除节点，然后删除左子树的最右节点（转换为情况1）

B树（BT）

目的：降低磁盘I/O次数
平衡的多路查找树
m阶B树所有非叶节点均至少含有⌈m/2⌉\lceil m/2\rceil棵子树，最多含有mm棵子树
每个节点包含m个关键字，m个记录指针向量，m+1个子树指针向量
所有叶子结点都在树的同一层上
叶子结点数=总关键字数+1

B树的插入

首先检查在B树中是否存在，若不存在，即在叶子结点处结束，则在叶子结点中插入新元素。根据该节点元素个数判断是否需要分裂。

B树的删除

看相邻兄弟是否丰满
若丰满，则向父节点借元素，父节点向相邻兄弟借元素
若均不丰满，则与相邻的某一兄弟合并成一个节点

B+树

所有非叶节点为索引，叶子结点包含了所有关键字
非叶节点仅含其子树根节点中最大关键字
优点：

  1. 磁盘读写代价低
  2. 查询效率稳定
  3. 便于范围查询

键树

双链树
Trie树

哈希表

合适的哈希函数：函数值能尽可能覆盖整个地址空间且均匀地映射到地址空间，使得发生冲突的可能性尽可能最少

哈希函数的构造

直接定址法

数字分析法

计算各位数字中符号分布均匀度
λk=∑i=1r(aik−n/r)2\lambda_k=\sum_{i=1}^r(a_i^k-n/r)^2
其中，aika_i^k表示第i个符号在第k位上出现的次数，
n/r 表示各种符号在 n 个数中均匀出现的期望值
计算出的λk\lambda_k值越小，表明在该位 (第 k 位) 各种符号分布得越均匀

平方取中法

除留余数法

折叠法：移位叠加、间界叠加

保留余数法

随机数法

冲突的处理方法

开放定址法

线性探测再散列
二次探测再散列（表长为4k+3型素数）
伪随机探测再散列

再哈希法

构造若干个哈希函数
优点：不易产生冲突的聚集现象
缺点：计算时间增加

链地址法

建立公共溢出区

哈希查找的性能分析

关键字与给定值比较的次数取决于：
哈希函数
处理冲突的方法
哈希表的饱和程度，装满因子α\alpha
α=表中填入的记录数哈希表长度\alpha=\frac{表中填入的记录数}{哈希表长度}
哈希表的ASL是α\alpha的函数
详见PPT

外部排序

k路平衡归并

若使用“败者树”从k个归并段中选最小者，则排序码比较次数与k无关，总的内部归并时间不会随k的增大而增大。

败者树的重构跟胜者树是不一样的，败者树的重构只需要与其父结点比较。

采用败者树来生成初始归并段。
胜败者判断条件：

  • 首先比较两个记录所在归并段的段号, 段号小者为胜者，段号大者为败者。
  • 在归并段的段号相同时, 排序码小者为胜者，排序码大者为败者。

最佳归并树

归并过程中的磁盘I/O次数=归并树的WPL*2
使用m-叉霍夫曼树

图

图的定义和术语

有向图 Digraph：弧 Arc
无向图 Undigraph：边 Edge
欧拉路径 Euler path：边
哈密顿路径 Hamilton path：点

图的存储结构

邻接矩阵

邻接表

十字链表（有向图）/ 邻接多重表（无向图）

图的连通性问题

有向图的强连通分量

  1. 对原图取反，从任意一个顶点开始对反向图进行逆后续DFS遍历
  2. 按照逆后续遍历中栈中的顶点出栈顺序，对原图进行DFS遍历，一次DFS遍历中访问的所有顶点都属于同一强连通分量

不论从哪个顶点开始，图中有多少个强连通分量，逆后续遍历的栈中顶点的顺序一定会保证：被指向的强连通分量的至少一个顶点排在指向这个连通分量的所有顶点前面。

最小生成树（Minimum Cost Spanning Tree）

Prim算法

逐步添加结点w，w要满足：新添加的w和已经在生成树上的顶点v之间存在一条边，该边的权值在所有连通顶点w和v之间的边中取值最小

O(n2)O(n^2)，适用于稠密图

Kruskal算法

先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若添加它不会使得SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止

考虑到需要对边进行排序，可以用堆存放边，使得每次选取最小权值的边仅需O(loge)O(loge)

关键：判断回路（将生成树T的连通分量看成等价类，并查集）

O(elog⁡e)O(e\log{e})，适用于稀疏图

关节点和重连通分量

重连通图：没有关节点的连通图

连通度k：连通图上至少删去k个顶点才能破坏图的连通性
一个表示通信网络的图的连通度越高，其系统越可高

  1. 若生成树的根结点有两个或两个以上的分支，则此顶点(生成树的根)必为关节点

  2. 对生成树上的任意一个内部结点v(非叶子结点)，若其某棵子树的根或子树中的其它结点没有和v祖先相通的回边，则该结点v必为关节点

定义：

  • low(v) = Min{visited[v], low[w], visited[k] }
  • 其中
    • 顶点w 是生成树上顶点v的孩子
    • 顶点k 是生成树上和顶点v由回边相联接的祖先
    • visited记录深度优先生成树的前序序列中的序号
    • low由后续遍历深度优先生成树求得
  • 若对顶点v，在生成树上存在一个子树根w， 且low[w] ≥ visited[v]，则顶点v为关节点

有向无环图

AOV网的拓扑排序

有向无环图（directed acycline graph, DAG）
AOV网（Activity on Vertex Network）

算法：

  1. 在AOV网中选择一个没有前驱的顶点并输出
  2. 在AOV网中删除该顶点以及从该顶点出发的(以该顶点为尾的弧)所有有向弧(边)
  3. 重复执行前两步，直到图中全部顶点都已输出(图中无环)或图中不存在无前驱的顶点(图中必有环)

设立栈，用来暂存入度为0的顶点

O(n+e)O(n+e)：

  • 统计各顶点的入度：时间复杂度是O(n+e)O(n+e) ；
  • 入度为0的顶点入栈：时间复杂度是O(n)O(n) ；
  • 排序过程：顶点入栈和出栈操作执行n次，入度减1的操作共执行e次，时间复杂度是O(n+e)O(n+e)

有向图无环时，也可利用深度优先遍历进行拓扑排序

AOE网的关键路径

AOE网（Activity On Edge Network）

定义：

  • e(i)表示活动ai的最早开始时间
  • l(i)表示在不影响进度的前提下，活动ai的最晚开始时间

则：l(i)-e(i)表示活动ai的时间余量，若l(i)-e(i)=0表示活动ai是关键活动

定义：

  • ve(i)表示事件（顶点）vi的最早发生时间，即从起点到顶点vi的最长路径长度
  • vl(i)表示事件（顶点）vi的最晚发生时间，即从顶点vi到汇点的最短路径长度

则：{e(i)=ve(j)l(i)=vl(k)−dut(<j,k>)\left\{\begin{aligned} &e(i)=ve(j)\\ &l(i)=vl(k)-dut(<j,k>) \end{aligned}\right.

算法：

  1. 从拓扑排序的序列的第一个顶点(源点)开始，按拓扑顺序依次计算每个事件的最早发生时间ve(i)
  2. 从拓扑排序的序列的最后一个顶点(汇点)开始，按逆拓扑顺序依次计算每个事件的最晚发生 时间vl(i)
  3. 计算e(i),l(i)，找到l(i)-e(i)=0的活动

为了2，增设一个栈以记录拓扑有序序列，则在计算求得各顶点的ve值之后，从栈顶至栈底便为逆拓扑有序序列；亦可利用DFS函数，在退出DFS函数之前计算顶点v的vl值。

O(n+e)O(n+e)

最短路径

Dijkstra算法

边上权值非负情形的单源最短路径问题

类似Prim算法

O(n2)O(n^2)

Bellman-Ford算法

边上权值为任意值的单源最短路径问题

Floyd算法

所有顶点之间的最短路径

算法：

  1. 设顶点集S(初值为空)，用数组D的每个元素D[i][j]保存从Vi只经过S中的顶点到达Vj的最短路径长度
  2. 将图中一个顶点Vk加入到S中，修改D[i][j]的值
    D[i][j]=Min{D[i][j],(D[i][k]+D[k][j])}D[i][j]=Min \{D[i][j] , (D[i][k]+D[k][j]) \}
  3. 重复上一步，直到G的所有顶点都加入到S中为止

O(n3)O(n^3)

动态存储管理

可利用空间表

链式可利用空间表的分配方式

  • 首次拟合法
  • 最佳拟合法
  • 最差拟合法

边界标识法（Boundary Tag Method）

伙伴系统（Buddy System）

无用单元收集（Garbage Collector, GC）

要及时释放共享结点所占的空间，必须给每个结点增设一个共享计数器，记录本结点被几个链共享，当结点从某一链中被删除时，就将此计数器减1，反之在插入时计数器加1，一旦该计数器被减到0时，说明该结点在结构中不再有用，便可以回收。

引用计数(Reference Counting)

  • 在所使用的数据结构/对象中增加一个计数域，它的值为指向该数据结构/对象的指针数目
  • 当该计数器值为0时，该数据结构才被释放
  • 不足：不能应对循环引用

标记后清除(Mark and Sweep)

  • 当可用空间表为空时，(Mark)暂停执行程序，从根集合(root set)开始，将内存整个遍历一次，标记被根集合直接或间接引用的对象；(Sweep)遍历整个内存，将未标记的对象都当作垃圾，把这些空间链接在一起，形成一个新的可用空间表，然后，再继续程序执行
  • Mark阶段：用递归或非递归进行遍历
  • 不足：需要中断程序执行

发表评论

%d 博主赞过：