数据结构考研笔记

顺序表与链表

顺序表:数据有序的存储在物理地址连续的存储单元中。将数据排序后,逻辑顺序与物理顺序相同,查找时可以使用二分查找,复杂度为O(\log_2 n),插入和删除数据时需要挪动后面元素让出空位或补空位,所以增删的复杂度为O(n)

链表:数据不需要使用地址连续的存储单元,它通过“指针链”建立元素的逻辑关系。增删只需修改指针,所以复杂度为O(1),但是查找只能从链首开始遍历,复杂度为O(n)

AVL树

顺序表查找快,链表增删快,有没有一种数据结构能将二者的优点都结合起来呢?有,那就是平衡二叉树。平衡二叉树的左子树中的节点都小于根节点,右子树中的节点都大于根节点,假设左右子树相等,搜索时只需判断一次大小就排除了一半的数据,这不就是二分查找么!!!所以查找的复杂度为O(\log_2 n),又因为平衡二叉树是由指针构造的逻辑结构,所以增删节点只需要O(1)

查找 增删(已知节点位置) 增删(先查询节点位置)
有序顺序表 O(\log_2 n) O(n) O(\log_2 n)+O(n) = O(n)
链表 O(n) O(1) O(n)+O(1) = O(n)
平衡二叉树 O(\log_2 n) O(1) O(\log_2 n)+O(1) = O(\log_2 n)

初学时会觉得O(\log_2 n)又不是常数,也没有改善多少嘛,和O(n)有多少区别呢?

举个例子,假如从2^{50}\approx 一千亿条数据中搜索,O(n)大概需要搜索一千亿次,而O(\log_2 n)是二分查找的效率,每次减半,只需要搜索50次。优化效果恐怖如斯,即便是世界上最大的数据库也可以在50次内完成搜索。

AVL树在失衡的时候需要左旋或右旋来重平衡,而左旋、右旋的操作和记忆都比较麻烦,比较好的方法是“3+4重构”,因为调整的目的就是为了平衡,所以我们只需将失衡的节点按照平衡时的样子重新组装,无需关注如何旋转。
34重构.svg

伸展树

有没有比平衡二叉树更快的搜索方法?有的,不过只能保证大多数情况。平衡二叉树复杂度中的\log_2 n其实就是平衡二叉树的高度,树越高复杂度越大,那么就想办法降低树高呗!计算机中有个局部性原理,常用的数据只占很小一部分,例如我们计算机中有那么多文件,你常用的是不是就那么几个?伸展树就是利用这个原理,将常用的数据提到树顶,而其它大量的数据又不常用,这相当于无形中降低了树的高度,将原来高度为h的树将为常用数据组成的高度为k的树。伸展树不是平衡的二叉树,在最差的情况复杂度会退化为O(n),不过伸展树不会连续出现这种情况。
k.svg

B树

以上所提到的数据结构都是基于内存的,但是如果数据大到一定程度就需要将数据存储到硬盘中,考察硬盘的特点:

  1. 硬盘的速度比内存慢的多,假如访问内存需要1秒,那么访问硬盘就需要一天。
  2. 从硬盘中读1B和1KB速度几乎是一样的。

B树就是根据硬盘的特点设计出来的m路平衡搜索树
graph.svg
它相当于将二叉树的多个节点结合成一个节点,目的是为了尽量少的访问硬盘,一旦访问硬盘则多读取一些数据。B树还有一个特点就是叶节点的高度完全一致。

B树中任何节点的子节点数量范围为[\lceil\mathrm{m} / 2\rceil,m],换言之B树中任何节点的关键字数量最小为[\lceil\mathrm{m} / 2\rceil-1,m-1],其中m被称为B树的阶。

考研中B树的高度是不包括最下层没有任何关键字的叶节点的(有些书中包括)。

B+树

B+树是B树的扩展,与B树有如下几处不同:

  1. 在B树中,含n个关键字的“超级节点”有n+1个孩子;在B+树中含n个关键字的“超级节点”有n个孩子。
  2. 在B树中,每个节点的关键字个数范围是[\lceil m / 2\rceil-1,m-1];在B+树中每个节点的关键字个数范围是[\lceil m / 2\rceil,m]
  3. 在B树中,非叶节点包含信息,每个关键字在树中仅会出现一次;在B+树中只有叶节点包含信息,而非叶节点只起到索引的作用,所以有些关键字会出现多次。
  4. B+树的叶节点相互串联,便于顺序查找。

B树.svg

多叉树

多叉树有一个重要的公式,高度为h的m叉树至多有(m^h-1)/(m-1)个节点,反过来具有n个节点的m叉树的最小高度为\lceil \log_m(n(m-1)+1)\rceil

任何一棵多叉树都可以转换为二叉树吗?是的。因为,树有多种存储方式,其中一种是孩子兄弟表示法,如果你将多叉树转换为孩子兄弟表示法,从结构上看它就是一颗“二叉树”。
a.svg

多叉树转换为二叉树的规则:每个节点左指针指向它的第一个孩子,右指针指向它在树中的相邻的右兄弟,这个规则又称为“左孩子右兄弟”。

b.svg

中缀表达式就是平时所用的数学表达式,例如(0!+1)^(2*3!+4-5),这是一个字符串,而我们要根据这个字符串计算出该字符串所表达的值。我们不能直接从左向右计算,这是因为运算符有优先级。考虑运算符的优先级比较麻烦,但是我们知道括号里的东西一定是先算的,所以我们可以将每个运算符都加括号,(((0!)+1)^(((2*(3!))+4)-5)),如此处理之后,就可以用栈匹配括号的方式进行计算。

后缀表达式可以不用考虑操作符的优先级,只需简单的从左向右依次计算即可。将加括号后的中缀表达式(((0!)+1)^(((2*(3!))+4)-5))的每一个操作符都移动到对应括号后面(((0)!1)+(((2(3)!)*4)+5)-)^然后去掉括号0!1+23!*4+5-^

队列

两个程序,A分配任务,B执行任务,A分配任务的速度快,B执行任务速度慢,A不想等B,所以常常A将任务放到队列中等B慢慢执行。这是常见的解决速度不匹配的方案,之前我对队列的理解就到这里,认为队列就是个暂存器,可有可无,没有它无非就是速度慢一点。但是层次遍历刷新了我的认知,这是一个没有队列不行的算法。

//层次遍历
void level_traversal(struct tree t,void visit(struct tree_node *e))
{
    struct tree_queue q = tree_init_queue();
    tree_enqueue(&q, t.top->left_child);
    
    while (q.size) {
        struct tree_node *x = tree_dequeue(&q);
        
        visit(x);
        
        if (x->left_child != NULL){
            tree_enqueue(&q, x->left_child);
        }
        
        if (x->right_child != NULL){
            tree_enqueue(&q, x->right_child);
        }
    }
}

散列表

有一种“奇葩”的存储方式,它将记录的关键字与存储位置建立关系,在理想情况下插入和查询的时间复杂度都是O(1)。嗯?那岂不是比平衡二叉树还厉害?那为什么还要花那么多的时间研究平衡二叉树?

我认为主要原因有两点:

  1. 平衡二叉树自带排序,而散列表没有排序。
  2. 散列表需要视情况“定制”散列函数和处理冲突的方法,不够通用,且维护起来比较麻烦。

一个思想实验:有一些数据需要存储,这些数据在查询时以手机号作为关键字进行查询。完全建立一个顺序表,以手机号作为顺序表的序号存储数据,插入和查询的时间复杂度都是O(1)。但是因为手机号是11位的,为了让手机号作为顺序表的序号,哪怕你只存一条记录,也必须创建一个长达11位的顺序表,白白浪费空间。

散列表的核心是对关键字空间进行压缩。散列表的存储方式与上述方法类似,只不过散列表通过散列函数将11位的手机号进行压缩,所以只需要很小的空间。

常用的散列函数有:直接定址法、除留余数法、数字分析法、平方取中法。

处理冲突 - 拉链法:
拉链法.svg
拉链法的缺点是,由于分配的地址不是连续的,这就导致计算机的缓存完全失效。

处理冲突 - 开放地址法:
开放地址法.svg

散列表的平均查找长度依赖于装填因子\alpha = \frac{表中记录数n}{散列表长度m}\alpha越大,散列表越满,发生冲突的可能性越大,反之发生冲突的可能性越小。

字符串

暴力算法

以主串中每一个字符作为开头,与模式串进行比较。复杂度O(mn)

特点是比较的时候主串和模式串的指针都前移,失败后主串和模式串的指针都后移。

KMP算法

kmp.svg
当B和C匹配失败的时候,之前的匹配一定是成功的,也就是说主串失败点B之前一定是ABCA,那么下一次匹配的时候可以直接将模式串A与主串中第二个A对齐,然后从主串失败点B继续匹配。

根据这个原理可以预先计算一个next表:

失败时模式串的字符 A B C A C
- 1 1 1 2

当失败在模式串C处,查表得next值为2,也就是从模式串的第二个位置继续匹配。

实际匹配过程中动的只有指针,主串指针从左向右依次移动,没有后退没有跳跃。模式串指针则根据next表进行跳跃。复杂度为O(n+m)

BM算法

BM.svg
先比较主串最后一个字符B与模式串最后一个字符F,匹配失败,我们知道如果要匹配成功,主串中B也一定与模式串中b匹配,而模式串后面一大段都没有“B”,所以可以快速将模式串移动到两个B对齐的位置。
根据这个原理可以预先计算一个bc表:

失败时主串的字符 A B C D E F H I J K L
1 2 3 4 5 6 0 0 0 0 0

我们同样可以预先计算一张bc表,当匹配失败时可以查表快速移动。这种策略通常从后向前比较,因为大多数的字符串匹配不成功的概率比匹配成功的概率大,所以从后向前比较效率更高。

BM算法同样兼顾KMP算法的思想,不过BM算法是从后向前匹配,所以需要生成一个倒着的next表,称之为gs表。

BM算法每当匹配失败时,分别查bc表和gs表,取这两个表中移动最快的值。

匹配过程中主串指针有跳跃的情况,这就说明它的效率可以超过线性。最好的情况复杂度为O(n/m),最坏情况为O(n+m)

哈夫曼树

节点的带权路径长度 = 节点的权值 x 该节点的路径长度
树的带权路径长度 = 所有叶节点的带权路径长度之和

带权路径长度.svg
上述3棵树的带权路径长度分别为:
WPL = 7x2 + 5x2 + 2x2 + 4x2 = 36
WPL = 4x2 + 7x3 + 5x3 + 2x1 = 46
WPL = 7x1 + 5x2 + 2x3 + 4x3 = 35

带权路径长度最小的树称为哈夫曼树。

给定n个权值分别为w_1,w_2,...,w_n的结点,构造哈夫曼树的算法描述如下:
1)将这n个结点分别作为n棵仅含一个结点的二叉树,构成森林F。
2)构造一个新结点, 从F中选取两棵根结点权值最小的树作为新结点的左、右子树,并且将新结点的权值置为左、右子树上根结点的权值之和。
3)从F中删除刚才选出的两棵树,同时将新得到的树加入F中。
4)重复步骤2)和3),直至F中只剩下一棵树为止。

哈夫曼编码

哈夫曼编码是哈夫曼树的重要应用之一。在数据通信中,对高频字符赋以短编码,对低频字符赋以较长编码,这样可以缩短平均编码长度。若没有一个编码是另一个编码的前缀,则称这样的编码为前缀编码。前缀编码的解码是唯一的。例如:若A、B、C的编码为0,101,100,则编码00101100的解码为AABC。若A、B、C、D的编码为0,101,100,00,则编码00101100的解码不唯一。

由哈夫曼树可以得到平均编码长度最短的前缀编码。我们可以根据以往数据通信中字符的频率构造出哈夫曼树,传输数据时根据哈夫曼树进行编码,解码根据哈夫曼树进行解码。

优先级队列 && 堆

优先级队列希望将队列里的元素按照优先级排序,显然AVL树以优先级为关键字肯定能实现需求。不过,大多数情况,我们只关心优先级最高或最低的元素,用AVL树有点杀鸡用牛刀之嫌,是能够完成这个任务的一个更精简的数据结构。

在逻辑上可以看作是一颗遵循堆序性的完全二叉树,堆序性是指任何节点的关键字都不大于(小于)它的父亲。在物理存储上是用顺序表存储的,因为完全二叉树除了最后一层,每一层都是满的,所以可以由位置关系将完全二叉树与顺序表相对应。
堆.svg
因为堆序性,堆中的最大元素(最小元素)必然在堆顶。

当插入节点时,仅需将其插入到末尾,如果违反堆序性递归的将其与其父亲交换位置,目标节点一直往上走,所以这一过程称为上滤。

当删除元素时,用末元素填补空位,然后递归的将其与更大(小)的孩子交换,目标节点一直往下走,这一过程被称为下滤。

初始化堆

将长度为n的顺序表初始化成堆,逻辑上相当于为完全二叉树增加堆序性。有两种简明的做法,一是对所有元素做上滤,二是对所有元素做下滤。两种方法都可以为每个元素增加堆序性。然而这两种方法的效率是完全不同的。
初始化堆.svg

下滤时,节点走的距离是节点的高度,上滤时,节点走的距离是节点的深度,而树形结构下面的节点远比上面的节点多,这就造成了所有节点的深度之和要大于所有节点的高度之和。所以对所有节点上滤的复杂度为O(n\log n),对所有节点下滤的复杂度为O(n)。所以初始化堆时应选择对所有节点下滤。

查找

顺序查找

int search_seq(int *A,int len,int key){
    A[0] = key;    //"哨兵"
    for(i=len;A[i]!=key;--i);
    return i;
}

A S L_{\text {成功 }}=\sum_{i=1}^{n} P_{i}(n-i+1)=\frac{n+1}{2}
A S L_{\text {无序表失败}}=n+1
A S L_{\text {有序表失败}}=\sum_{j=1}^{n} q_{j}\left(l_{j}-1\right)=\frac{1+2+\cdots+n+n}{n+1}=\frac{n}{2}+\frac{n}{n+1}

二分查找

版本一:

int bin_search(){
    int low=0;high=L.len-1,mid;
    while(low<=high){
        mid=(low+high)/2;
        if(L.elem[mid]==key)
            return mid;
        else if(L.elem[mid]>key)
            high=mid-1;
        else
            low=mid+1;
    }
    return -1;
}

版本二:

//二分查找
int vector_bin_search(struct vector v,int e,int lo,int hi)
{
    while (lo<hi) {
        int mi = (lo+hi)>>1;
        
        if(e<*(v.elem+mi)){
            hi = mi;
        }else{
            lo = mi + 1;
        }
    }
    
    return --lo;
}

A S L_{\text {成功 }}=\frac{1}{n} \sum_{i=1}^{n} l_{i}=\frac{1}{n}\left(1 \times 1+2 \times 2+\cdots+h \times 2^{h-1}\right)=\frac{n+1}{n} \log _{2}(n+1)-1 \approx \log _{2}(n+1)-1
A S L_{\text {失败 }}=\left\lceil\log _{2}(n+1)\right\rceil

分块查找

A S L_{\text {索引表顺序查找 }}=L_{\mathrm{I}}+L_{\mathrm{S}}=\frac{b+1}{2}+\frac{s+1}{2}
A S L_{\text {索引表折半查找 }}=L_{\mathrm{I}}+L_{\mathrm{S}}=\left\lceil\log _{2}(b+1)\right\rceil+\frac{s+1}{2}
最理想的块长为s=\sqrt{n}

排序

插入排序

插入排序包含直接插入排序、折半插入排序和希尔排序。
直接插入排序:
插入排序.svg
只需逐个将第i个无序元素插入到前面的有序序列中。

折半插入排序:
折半插入只不过是将直接插入排序中从后向前寻找改为二分查找,减少了比较的次数。但是元素移动的次数并未减少,所以折半插入排序相对直接插入排序只是在常数意义上改善了复杂度。

希尔排序:
希尔排序.svg

交换排序

交换排序包含冒泡排序和快速排序。
冒泡排序:
从前向后两两比较,若为逆序交换元素位置,直到序列结束。第i次冒泡总能将第i大的元素就位,所以最多n-1趟冒泡就能将所有元素排序。

有两种情况可以优化:
未命名.svg
第一种是冒泡到一半的时候前缀已经有序了,这时可以直接结束程序。
冒泡排序.svg
第二种情况是当冒泡到某一时刻,会有大量有序后缀,这些后缀完全没必要参与后面的冒泡。

void bubble_sort(int *e,int lo, int hi)
{
    while (lo < hi) {
        hi = bubble(e,lo,hi);
    }
}

int bubble(int *e, int lo, int hi)
{
    int last = lo;
    while (++lo < hi) {
        if (e[lo-1] > e[lo]) {
            last = lo;
            swap(e[lo-1] , e[lo]);
        }
    }
    // 返回最后更新位置,下次只需冒泡到这里,并且作为标志证明前缀不是完全有序
    return last;
}

快速排序:
轴点.svg
假设我们能在待排序序列中找到一个轴点,轴点的左边均小于轴点,轴点的右边均大于轴点,那么只需递归的将轴点左边和右边分别排序,然后将它们组合起来即完成整个序列的排序。

下面示例讲解如何寻找轴点:
快速排序.svg

选择排序

选择排序包含简单选择排序和堆排序。
选择排序.svg
每次从无序序列中选择选择一个最小的放到第i个位置。

堆排序:
堆排序的原理是将所有元素放入堆中,然后依次取最大或最小的元素即可完成排序,不过堆排序的巧妙之处在于,它不需要额外分配空间。
堆排序.svg

归并排序

归并排序.svg

合并过程,就是比较两组元素的首元素大小,依次取首元素最小的元素放入相应位置,因为合并后的元素有可能覆盖掉第一组元素,所以要先复制一份,这也是归并排序空间复杂度为O(n)的原因。

归并合并.svg

基数排序(桶排序)

基数排序.svg

其实就是先按个位排序,然后按十位排序,再按百位排序。基数排序的顺序很重要,一定要先排权重低的,后排权重高的,因为后面的排序会将前面的排序覆盖掉。比如说最后一次排序是按个位排的,那么结果就会按个位排序,最后一次按百位排的,结果就会按百位排序。

内部排序算法比较

\begin{array}{|c|c|c|c|c|c|}
\hline
  & 最好情况                    & 平均情况& 最坏情况 & 比较次数               & 空间复杂度       & 稳定性 \\ \hline
直接插入排序 & O(n)        & O(n^2)            & O(n^2)    &        & O(1)        & 稳定  \\ \hline
希尔排序   & -                  & -   & O(n^2)   &   & O(1)        & 不稳定 \\ \hline
冒泡排序   & O(n)        & O(n^2)            & O(n^2)     &       & O(1)        & 稳定  \\ \hline
快速排序   & O(n \log_2 n)            & O(n \log_2 n) & O(n^2)    &   & O( \log_2 n) & 不稳定 \\ \hline
简单选择排序 & O(n^2)      & O(n^2)            & O(n^2)         &  n(n-1)/2 & O(1)        & 不稳定 \\ \hline
堆排序    & O(n \log_2 n) & O(n \log_2 n)       & O(n \log_2 n)    &   & O(1)      & 不稳定 \\ \hline
2路归并排序   & O(n \log_2 n) & O(n \log_2 n)       & O(n \log_2 n)     &  & O(n)        & 稳定  \\ \hline
基数排序   & O(d(n+r))      & O(d(n+r)) & O(d(n+r)) & 0 & O(r)    & 稳定  \\ \hline
\end{array}

  1. 若n较小,可采用直接插入排序或简单选择排序。由于直接插入排序所需的记录移动次数较简单选择排序的多,因而当记录本身信息量较大时,用简单选择排序较好。
  2. 若文件的初始状态已按关键字基本有序,则选用直接插入或冒泡排序为宜。
  3. 若n较大,则应采用时间复杂度为O(n \log_2 n)的排序方法:快速排序、堆排序或归并排序。快速排序被认为是目前基于比较的内部排序方法中最好的方法,当待排序的关键字随机分布时,快速排序的平均时间最短。堆排序所需的辅助空间少于快速排序,并且不会出现快速排序可能出现的最坏情况,这两种排序都是不稳定的。若要求排序稳定且时间复杂度为O(n \log_2 n), 则可选用归并排序。但本章介绍的从单个记录起进行两两归并的排序算法并不值得提倡,通常可以将它和直接插入排序结合在一 起使用。先利用直接插入排序求得较长的有序子文件,然后两两归并。直接插入排序是稳定的,因此改进后的归并排序仍是稳定的。
  4. 在基于比较的排序方法中,每次比较两个关键字的大小之后,仅出现两种可能的转移,因此可以用一棵二叉树来描述比较判定过程,由此可以证明:当文件的n个关键字随机分布时,任何借助于“比较”的排序算法,至少需要O(n \log_2 n)的时间。
  5. 若n很大,记录的关键字位数较少且可以分解时,采用基数排序较好。
  6. 当记录本身信息量较大时,为避免耗费大量时间移动记录,可用链表作为存储结构。

外部排序

外部排序.svg

然后将排好序的小段归用归并排序。

外部排序归并.svg

对于外部排序,I/O访问速度要远小于内存的访问速度,所以要增加速度,主要需要减少I/O的访问。我们发现每一次归并都需要访问所有的元素,所以减少I/O的最好办法就是减少归并的次数,即增加归并路数。例如上图中2路归并,将所有数据访问了3遍,如果改为8路归并,只需访问所有数据一次。
外部归并2.svg

然而我们不能无限的增加归并路数m,因为:

比较次数 = 归并趟树\times关键字个数\times求得最小关键字比较次数=\lceil \log_m r \rceil(n-1)(m-1)

增加m会使总的比较次数增加。

败者树

败者树是一颗完全二叉树。我认为叫做“亚军树”更为形象,因为二叉树的非叶节点保存了当前分支“第二小的”,所以每次选最小的只需要一路向上和“亚军”比就行了。所以比较次数为树的高度,即\log_2 m,比较次数可以化为:

比较次数 =\lceil \log_m r \rceil(n-1)\lceil \log_2 m \rceil = \lceil \log_2 r \rceil(n-1)

比较次数与m无关,所以在内存允许的情况下可以无限增加m,以减少I/O访问次数。

败者树1.svg

置换选择排序

从公式中可知减小初始归并段个数r,也可以减少总比较次数,也就是要增加归并段长度。基于内部排序,归并段最长也就是内存的长度,而置换选择排序可以在排序的同时给出超过内存长度的归并段。

算法思想:
1)从待排序文件FI输入w个记录到工作区WA;
2)从内存工作区WA中选出其中关键字取最小值的记录,记为MINIMAX;3)将MINIMAX记录输出到FO中;
4)若FI未读完,则从FI输入下一个记录到WA中;
5)从WA中所有关键字比MINIMAX记录的关键字大的记录中选出最小的关键字记录,作为新的MINIMAX;

最佳归并树

归并段划分好之后,接下来是归并中的“合并”过程。与内部排序的归并排序不同的是,这里的归并段是不等长的,谁先合并谁后合并会有性能差异,相当于下面这道题:

【2012统考真题】设有6个有序表A,B,C,D,E,F,分别含有10,35,40,50,60和200个数据元素,各表中的元素按升序排列。要求通过5次两两合并,将6个表最终合并为1个升序表,并使最坏情况下比较的总次数达到最小。请回答下列问题:
1)给出完整的合并过程,并求出最坏情况下比较的总次数。
2)根据你的合并过程,描述n(n≥2)个不等长升序表的合并策略,并说明理由。

这个合并过程可以由哈夫曼树优化。

例如:初始归并段有12个,长度分别为4,4,4,4,5,5,5,5,5,6,6,7,采用5路归并。

首先,要计算一下需要补充几个虚段。

k叉树有公式n_0 + n_k = kn_k +1,整理得n_k = (n_0-1)/(k-1),取余数u = (n_0-1) \bmod (k-1),可知多出来几个归并段。

要添加的虚段个数 = k-u-1,因为这个新组成的分支要去代替树中的一个节点,而哪个节点原本就有一个归并段,所以要减1。

外部排序合并.svg


我的代码:https://github.com/swimmingwhale/data-struct

posted @ 2020-11-10 18:49:36
评论加载中...

发表评论