数据结构一天速成

绝大部分学校的数据结构课程应该是：

作者：不吃鱼的喵酱

链接：https://www.zhihu.com/question/303208441/answer/538673362

先说第一块，线性结构。这里涉及的主要知识点就是顺序表和链表，以及衍生出来的栈和队列。顺序表不必多说，就是内存中一块连续的区域，紧密排列了若干个相同类型的数据。显然，这种设计需要事先知道同样的元素一共有多少，不然就无法开辟出合适的内存区域（即会存在浪费或者不足）。为了解决数组这种元素数量不灵活的缺点而提出的方法就是链表。链表的基本单位是节点，每个节点拥有一个数据区和一个next指针，其中数据区用于存放数据，next指针指向下一个节点。与顺序表相比，链表可以根据需要自由选择节点的数量，从而解决了内存分配不合适的问题。

但是链表并不是万能的，是否选用链表要根据实际情况进行斟酌（后面是重点）。第一，顺序表可以随机访问其中的元素，也就是说，使用顺序表可以以一个恒定的小代价访问其中的任意一个元素，即查找的时间复杂度为O(1)；链表查找其中某一个位置的特定元素则必须从头开始一个一个的沿着next指针数过去，即查找的时间复杂度为O(N)。第二，顺序表在插入和删除元素的时候需要找到特定位置的元素，然后将其后面的全部元素都向前移动或者向后移动，以填补或腾出空位，因此顺序表的插入和删除的时间复杂度都是O(N)；但是链表只需要摘去或者挂上一个节点就行了，因此链表的插入和删除的时间复杂度都是O(1)。

顺序表的构造思路十分简单，只要一个一个往里塞就行。在实践中，一般使用一个下标保存当前顺序表的结尾位置，插入元素时直接在这里插入，然后让下标向后移动。链表一般分为头插法和尾插法两种方式。头插法就是把新节点直接插在节点链的头部，比较适合构造栈；尾插法把新节点插在链表末尾，比较适合构造队列，而且需要额外的指针指向尾节点。插入过程如下：

第一步，将新节点的next指针指向要插入的位置的后一个节点（new_node->next = p->next;） 第二步，把要插入的位置的前一个节点的next指针指向新节点（p->next = new_node;）

删除节点过程如下：

第一步，将要删除的节点的上一个节点的next指针指向被删除的节点的下一个节点（p->next = deleted_node->next;） 第二步，释放被删除的节点（free(delete_node);）

双链表在单链表的基础上增加了一个前向指针previous，即对于每一个节点可以同时找到它的上一个和下一个节点。这能让链表在构造的时候代码更好写，具体情况参考书上。双链表一般不怎么考，根据需要选用。

队列和栈是被特化了规则的线性结构，属于逻辑结构的范畴，并不拘泥于某种特定的物理结构实现。换句话说，任何满足先进先出（FIFO）的结构都可以被描述成队列，而任何满足后进先出（LIFO）的结构都可以被描述成栈。

使用顺序表构造队列需要一个头指针和一个尾指针。进入的元素在尾指针处插入，取出的元素从头指针处去除；使用链表构造队列需要使用尾插法，并从头部移除元素。队列就是简单的排队，在诸如计算机网络的分组交换、CPU时间片轮转等场合有广泛的应用。

使用顺序表构造栈只需要一个栈顶指针。元素从栈顶指针处入栈（push），同样从栈顶指针处出栈（pop）。使用链表构造栈需要使用头插法，并从头部移除元素（此时指向链表头结点本身的指针即为栈顶指针）。栈在诸如编译时的括号匹配、程序运行时的函数跳转等场合有广泛的应用。

在上文中，我们会发现，在使用顺序表实现队列，并频繁地插入和移除元素后，两个指针渐渐会来到表的结尾，这时候我们就需要逻辑上的环来避免这一问题。将节点自增从pointer ;改成( pointer)%length;即可解决这一问题。当指针来到结尾处时会由于模运算回到开头。链表则需要把尾节点的next从悬空改成指向头结点，并且让原来指向头结点的指针指向尾节点即可。这样一来，p即为末尾，而p->next即为开头。

块状表是一种结合了顺序表和链表的结构。块状表吸收了链表的next指针所带来的动态优势，同时把链表的数据区扩展成一个小的顺序表。这样一来，既可以满足动态请求内存的需要，又可以避免查找元素时O(N)复杂度的困扰（事实上可以把O(N)降低到O(N/M 1)，M是小顺序表的长度）。块状表是一种相对折中的方案，可根据需要选取，并且一般考试不会考。

伴随着线性结构而来的就是常用的各种排序算法，我这里只说思路不说实现，并且只提供平均时间复杂度。

最基础的就是冒泡排序，基于交换思想。其想法是将每一个元素与它后边的元素相比，如果前面的更大就交换位置。对于每一个元素来讲，当交换停止时，都满足前面的元素小于它，后面的元素大于它，因此整个数组有序。冒泡排序的平均复杂度是O(N²）。

除了交换的思想，还有一种常用的思想是插入。基于这种思想的排序法是插入排序和选择排序。插入排序会维护一个小的有序队列，在排序开始时这个队列的长度是0，此后，每一次将一个新的元素插入这个有序队列中合适的位置，则当全部的元素都插入这个队列时排序完成。插入排序平均复杂度是O(N²)。选择排序则是每一次都遍历所有未排序的元素，从中选出最小的或者最大的元素插入有序队列的头或者尾，平均复杂度同样是O(N²)。

同样基于插入思想却又与上两者不同的方法是希尔排序和桶排序。希尔排序与插入排序基本相同，但是在开始时会规定一个增量（一般是数组长度的一半），并且每一趟将这个增量缩小至之前的一半，直至增量变为1。希尔排序根据增量把每隔N个的所有元素分为同一组，对每一组内使用插入排序。当增量为1时，对整组元素逐个排序。尽管希尔排序的平均复杂度也是O(N²)，但是在实践中一般比插入排序更快（因为每一次处理的都是部分有序的数列，移动元素的次数较少）。桶排序则更好的体现了插入的思想，事先将最小值到最大值之间的区间分成N个桶，每个桶涵盖了相同的数据范围。每次从数组中取出一个元素放入对应的桶内，并将其插入到桶内的所有元素组成的小数组中的合适位置，以此完成排序。最后只需要按顺序把每个桶中的所有元素倒出来就行了。桶排序对于空间的需求相对较大，但是相应的会减少时间上的需求，平均复杂度我懒得算了，但是可以确定是log级别平方级别之间的，但是在桶划分不合理时会退化到O(N²)。

快速排序则是基于分治法，属于最难理解的一个。快速排序从局部数组中（在第一趟中，这个局部指的是整个数组）随机选取一个中间数，然后将大于它的数全部移动到右边，小于它的数全部移动到左边，再对左右两个局部数组递归进行上述操作，直至在某一趟中每个局部数组都只有一个元素。在交换结束时，每一个数都满足左边的比它小，右边的比它大，因此整个数组有序。快排的平均复杂度是O(N*logN)，因此叫快速排序，但是在整个数组已经有序时会退化为O(N²)。

归并排序同样基于分治法，也是上述所有排序法中唯一一个外部排序法。归并排序的基本思想是合并N个有序数组，当N为1时排序完成。归并排序主要分为两步，第一步把大数据集分成N个小数据集，并使用任意一种内部排序法对每一个小数据集进行排序；第二步是每次将其中的K个已经有序的小数据集进行合并（称为K路归并）。归并排序的平均复杂度是O(MNlogN)，其中M为每个小数据集中数据的个数，N为小数据集的数量，log的底数为K。

基数排序则是最无聊的一种排序法。假设有一个数据集是{456, 123, 789}，基数排序先比较个位数字并排列有序，再比较十位数字并排列有序，最后比较百位数字并排列有序。人类在查找纸质字典的目录时就是在进行基数排序。基数排序不太容易衡量复杂度，也不太可能考。

还有一些常用的排序方法，比如堆排序和二叉排序树，我们会在后面讨论。另外，要是有人跟你说睡排序和猴子排序，请直接把他打死。

讲完线性结构，我们再来讲讲树状结构。树状结构最基础的就是二叉树，我们就从这里入手，顺便看看复杂度中的log是怎么来的。

首先要先普及一些概念：每一棵树有唯一的根节点，在此基础上向下生长。每一个节点的所有直接后代称为它的孩子节点，孩子的直接先代称为父亲节点。没有孩子的节点称为叶子节点。树中不能有环，每一个节点都必须有且仅有一个父亲节点（根节点除外）。根据定义我们同样可以推理出，以每个非叶节点的每一个孩子节点作为根节点，都可以得到一棵子树。从根节点到叶子结点的最长路径称为树的度（或者深度）。

在此基础上，每个非叶节点至多只有两个孩子的树称为二叉树。显然二叉树的深度介于log₂N与N之间。当深度为N时，二叉树退化为线性表。二叉树节点的两个孩子分别称为左孩子和右孩子，同理会衍生出左子树和右子树的概念。

链式存储的二叉树十分直接，每个节点包含一个数据区和两个孩子指针。数据区用于存储数据，孩子指针分别指向两个孩子，如果没有孩子就悬空。这一节的重难点其实在二叉树的线性存储，即将二叉树保存在顺序表中。这种方式会成为堆排序的理论基础，并且在存储完全二叉树时有明显的优势。下面我们将展开来讲。

在说明线性存储之前，我们必须要引入满二叉树的概念。根据定义，除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树被称为满二叉树。如下图

对于一棵满二叉树，我们按照从左到右，从上到下的顺序给每一个节点编上号（我的教材是从1开始编号，因为方便运算），就能轻易发现一个事实：假设某一个节点的编号是N，那它的的两个孩子节点的序号分别是2N和2N 1。下面，我们把这个编号作为数组下标，就可以得到二叉树的线性存储方式了。

对于不满的二叉树，我们要先把它补齐成满二叉树，然后把补上的节点空出来，就可以完成线性存储。存储一棵二叉树所需的总的线性空间与它的度有关，即2的N次方。显然，满二叉树极少浪费线性空间，而偏差较大的二叉树会极大地浪费线性空间。

建立一棵二叉树十分简单，一般有两种方式：从根向叶子和从叶子向根。前者可以被用来建立二叉排序树，一会儿会讲到；后者可以用来建立哈夫曼树，网上资料很多，有看不明白的地方自己再查一下。这两种树都属于常考内容，应用也十分广泛。

正常的树都是从根向叶子生长，所以逆生长的哈夫曼树就显得比较特别。哈夫曼树一般用于压缩算法，可以用来生成前缀码。前缀码指的是，在一套编码体系中，任何一个字的密文都不是其他字的密文的前缀，或者说对于任何一个字的密文，从头开始连续截取任意长度，得到的结果都不能构成另外一个字的密文。不是前缀这个特性保证了编码没有歧义，因此可以按顺序处理而不必担心出现错误。摩斯电码是非前缀码，因此每两个字之间需要提供明显的停顿用以显示表明这是不同的两个字。如果这个停顿不够明显，也就是发报速度比较快，就比较容易造成歧义。

前缀码的一个特性就是每个字长短不一，显然出现频率更高的字使用更短的密文能获得较大的空间和时间优势。所以，哈夫曼树的第一步就是从统计字频开始的。这一步只需要遍历文本流就可以，很简单，按下不表。

第二步就要开始建树了。由于哈夫曼树是逆生长树，采取的是合并子树的思想，所以最先被选择的一定是最深的子树。合并子树的方法如下：在最开始的时候，把每一个节点都视为一棵只有一个根节点的树。每一次迭代，选取频率最低的两棵子树进行合并，直到最后只剩下一棵树为止。举例来说，假设刚开始有a，b，c三棵子树，频率分别是0.1，0.2，0.7，那么第一次迭代就会选择0.1跟0.2进行合并，得到一棵频率为0.3的新子树，然后再把这棵新子树与0.7合并完成建树。显然，从根节点开始，寻找c只需要一步，而寻找a和b各需要两步，平均字长为1.3。

建立哈夫曼树的目的是为了进行哈夫曼编码。前文也提到了，这是一种压缩算法。压缩的过程就是建立上述的哈夫曼树，然后遍历哈夫曼树写出每个字的密文，再按照查字典的方式把每个字转换过去。而解压缩的时候，则需要先重建哈夫曼树，再一位一位对照密文从树根开始向下寻找，找到叶子结点就可以认为解码出了一个字，然后下一位回到树根重新寻找。解码的过程比较类似状态机模型，要写成模块化的模式还真不是太好写，反而是面向过程的方式比较好写。在具体编码过程中，指定左孩子的编码为1或是右孩子的编码为1都不会影响结果，事实上也没什么标准，甚至在中途随意翻转都可以。不同的程序员跑出来的哈夫曼编码结果不同是很正常的一件事，只要不影响编码和解码的使用就行。

说完了不正常生长的哈夫曼树，再来说说正常生长的二叉排序树。二叉排序树的定义是：每一个节点的左孩子小于它，而右孩子大于它（等于的情况事先声明一下放左还是放右就行，对于结果无实质影响）。根据这个定义，我们可以递归地得出性质：对于每一个节点，其左子树全部小于它，其右子树全部大于它。因此，为了满足性质，在建立二叉排序树时只需要从根节点开始，递归地比较每一层元素，如果其比要插入的元素大则走向其左孩子，反之走向其右孩子，直至最终来到叶子结点，并把该元素插入。当全部的元素都被插入了，二叉排序树就建立完成了。

接下来就要取出其中的有序数列了，也就是进行二叉树的遍历。二叉树的遍历一般分为先序遍历、中序遍历和后序遍历三种。先序遍历即先访问根节点，再寻找左孩子，最后寻找右孩子。中序遍历是先寻找左孩子，再访问根节点，最后寻找右孩子。后序遍历先寻找左孩子，再寻找右孩子，最后访问根节点。可以说，先中后指的是访问根节点的时机。由于遍历是递归的，使用中序遍历一路寻找到的最“左”的左孩子就是二叉排序树中的最小元素，且中序遍历的输出顺序就是从小到大的顺序。根据前序遍历和中序遍历或后序遍历和中序遍历可以重建整棵树，这也是考试的热点和难点。

二叉排序树的平均复杂度是O(N*logN)，其中的log就来自于二叉树的深度。当数组已经有序时二叉排序树会退化为O(N²)，而且绝大部分时候都建不出漂亮的二叉树，所以这个log其实是有很大水分的。

为了尽量建出漂亮的二叉树，人们想出了很多办法，其中一项就是平衡二叉树（AVL树）。平衡二叉树是指每一个节点满足左子树的度与右子树的度相差不超过1的二叉排序树。由于其限制了节点的左右孩子，因此能让整棵树更加紧凑，从而大量挤出了log中的水分。建立AVL树需要用到复杂的旋转操作，几乎不会考到，所以我不讲了。

使用二叉排序树排序尽管复杂度较低，而且十分容易理解，但是需要O(N)级别的辅助空间，并不是很划算。仔细想一想，既然能把二叉树存放在顺序表里，那顺序表本身是不是也能被看成是线性存储的二叉树呢？答案是肯定的。一张顺序表可以被看做是一个完全二叉树，即除了最后一层外每一层元素都是满的，且最后一层的元素全都集中在左边的二叉树。显然，满二叉树是完全二叉树。

堆就是完全二叉树的一种应用，硬要说的话也属于反向生长。常用的堆分为大顶堆和小顶堆两种，前者满足父亲节点大于孩子节点，后者满足父亲节点小于孩子节点。根据递归我们可以推算出，大顶堆堆顶的元素是最大的，小顶堆堆顶的元素是最小的。堆排序就是在不断地重复建堆并移走堆顶元素的过程，显然平均复杂度是O(N*logN)，而且由于完全二叉树的性质，这个log没有水分。

堆排序最神奇的地方就是它不需要借助一个链式的二叉树的辅助，而是直接在顺序表中操作元素，因此它的空间复杂度是O(1)级别的。回想一下二叉树的线性存储相关的内容，我们会猛然想起父亲节点与孩子节点的序号之间的关系，从而明白为什么不需要辅助树。

第一步，在逻辑上建堆。这一步要求我们根据实际情况（即数组下标从1或者0开始）来推演父亲节点与孩子节点真实的下标关系，在脑海中建立这个堆。第二步，满足堆的性质。这一步我们要对所有的非叶子节点从下到上进行调整，使其满足大顶堆或者小顶堆的性质。具体做法是找到第一个非叶子节点，并对它与它的孩子节点进行调整，使其满足堆的性质；然后从这个节点开始向前线性地调整每一个非叶子节点，直至根节点。此时整个堆都满足性质。第三步，取得堆顶元素。这一步会把堆顶元素与堆内序号最大的元素进行交换，并且堆内元素数量减一。显然这个堆顶元素满足剩余未排序元素都比它小或比它大，而前面的已排序元素都比它大或比它小，因此它在已排序队列中的相对位置是确定的，即头或尾。第四步，恢复堆的性质。由于刚才把一个无序元素插入了堆顶，导致堆的性质被破坏，接下来我们需要恢复它的性质。这一步不需要逆序遍历，而是从堆顶开始，将刚插入的元素逐步向下落，直至停在合适的位置。举例来讲，对于大顶堆，要保证堆顶元素是最大的，因此要把它分别与左右孩子进行比较，并且把三者中最大的一个升上堆顶。由于左右孩子在刚才的操作中都没有变动，因此各自满足在子树中是最大的的性质，此时若堆顶元素比他们两个都大，便能推理出堆顶元素是最大的。同理，升上去的三者中最大的元素也能满足这个推理。将堆顶元素向下落的操作要递归地进行到该元素不需要再进行交换为止，此时整个堆恢复性质。第五步，重复第三步和第四步的操作，直至堆被清空。此时，整个数列有序。

堆排序非常喜欢考，不仅考方法论还要考实现，而且这东西略抽象，不是很好掌握。刚才突然心血来潮写了个实现，凑合着看一下吧。我比较懒，用CPU时间换了内存，数组下标里面各种运算。其实可以拿临时变量装一下来节省CPU的。C语言需要事先声明函数才能使用，我也没照顾可读性写函数原型，看的时候记得倒着看。

#include 

void reconstruct_heap(int a[], int index, int last)
{
    int tmp;
    
    if(index * 2   1 > last)  // 检查是否有孩子
    {
        return;
    }
    
    if(index * 2   1 == last)  // 检查是否只有左孩子
    {
        if(a[last] > a[index])
        {
            tmp = a[index];
            a[index] = a[last];
            a[last] = tmp;
        }
    }
    else
    {
        if(a[2 * index   1] > a[index]