数据结构基础算法

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。本思维导图是对计算机考研的数据结构的整理，这个是数据结构基础算法的两大部分：查找和排序。希望可以帮到小伙伴们！

数据结构基础算法

• 查找
  • 基本查找方法
    • 顺序查找法：从表的一端开始顺序扫描线性表，依次将扫描到的关键字和给定值比较
    • 折半查找法：找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表
    • 分块查找法：把线性表分为若干块，要求前一块中的最大关键字一定要小于后一块。建立一个索引表，把每块中的最大关键码值作为索引表的关键码值，按块的顺序存放到一个辅助数组中，查找时，首先在索引表中进行查找，确定要找的节点所在的块。由于索引表是排序的，因此，对索引表的查找可以采用顺序查找或折半查找；然后，在相应的块中采用顺序查找，即可找到对应的节点，属于前两种方法的结合
  • 适用于查找的数据结构
    • 二叉树
      • 二叉排序树
        • 基本性质：若左子树不空，则左子树上所有节点的值均小于它的根节点的值；若右子树不空，则右子树上所有节点的值均大于它的根节点的值；没有键值相等的节点
        • 基本操作
          • 查找：从根节点依次向下找
          • 插入：对于一个不存在于二叉排序树中的关键字，其查找不成功的位置即为插入位置
          • 删除：若为叶子结点可直接删除，若该结点只有左右子树中的一个删去改点后将其子树直接连接在其双亲结点上，若该结点同时有左右子树，则在其左子树或者右子树中寻找能够替代其位置的结点
      • 平衡二叉树
        • 基本性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
        • 构建方法：将数组的元素一一放入树中，若出现BF值为负数的结点，若其左子树低于右子树，则以该结点为中心逆时针旋转改变当前层次根节点后微调，若其右子树低于左子树，则以该结点为中心顺时针旋转改变当前层次根节点后微调
    • 多叉树
      • B-树（B树）
        • 基本性质：若为m叉树，则根节点的分支至少有两个，非根非叶结点至少有[m/2]（[]为取整函数）个分支；每个结点可以有多个关键字，m叉树结点最多容纳m-1个关键字；同一层次的结点的关键字按大小顺序从左到右排列，从结点最左/右端或者两个关键字之间可以引出一个分支，分支所连接的结点内的关键字大小必须在所连接的上一层次的关键字之间（若从左端点引出则应小于左端关键字，从右端点引出应大于右端关键字）
        • 基本操作
          • 查找：从根节点依次向下找
          • 插入：对于一个不存在于B-树中的关键字，其查找不成功的位置即为插入位置。如果插入之后结点关键字数大于m-1，则需要对结点进行拆分：将插值后的结点当中数值居中的关键字归并进入上一级结点，若上一级结点关键字数也超标则重复操作
          • 删除
            • 所删除结点位于终端节点
              • 结点关键字个数大于[m/2]-1：直接删除
              • 结点关键字个数等于[m/2]-1
                • 该关键字左、右结点中存在关键字数大于[m/2]-1的情况则向关键字数大于[m/2]-1的结点中借字填充原位
                • 改关键字左、右结点关键字数均等于[m/2]-1，则在删除该关键字后将其左、右结点合并为一个结点
            • 所删除结点不在终端节点
              • ①沿着该关键字的左指针来到其子树根节点②沿着根节点中最右端的关键字的右指针往下走，用同样的方法一直走到终端结点上③用该终端结点取代欲删除的结点，然后用删除终端结点的方法来进行该终端结点向上取代之后的后续处理
      • B+树
        • 基本性质：含有n个关键字的结点（包括终端结点）有n个分支，其中[m/2]<=n<=m
        • 与B-树的区别：B+树中，所有非叶子结点仅起到一个索引的作用，不含有该关键字对应记录的存储地址，只在每个叶子结点的指针所指向的记录中有全部关键字的存储地址；B-树中每个关键字对应一个记录的存储地址
    • 散列表
      • 基本性质：根据给定的关键字来计算关键字在表中的地址
      • 构造方法
        • 直接定址法：取关键字或者关键字的某个线性函数为Hash地址
        • 数字分析法：取关键字的若干数位组成Hash地址
        • 平方取中法：取关键字平方后的中间几位作为Hash地址
        • 除留余数法：取关键字被某个不大于Hash表表长的数（常取不大于表长的最大素数），用关键字除以该数所得余数作为Hash地址
      • 冲突处理方法
        • 开放地址法
          • 线性探查法：出现重复地址后，以该地址为起点向后探查直至出现未被使用的地址数
          • 平方探查法：将发生冲突的地址d进行（d²+1）的处理并将计算值作为地址
        • 链地址法：把所用同义词用单链表连接起来的方法
• 排序
  • 内部排序：待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列
    • 时间复杂度为O（n²）的方法
      • 冒泡排序：①比较相邻的元素。如果第一个比第二个大，就交换他们两个②对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数③针对所有的元素重复以上的步骤，除了最后一个④持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较
      • 简单选择排序：设所排序序列的记录个数为n。i取1,2,…,n-1,从所有n-i+1个记录（Ri,Ri+1,…,Rn）中找出排序码最小的记录，与第i个记录交换。执行n-1趟 后就完成了记录序列的排序
      • 直接插入排序：先将第一个数据排在第一位上，接下来每一趟将一个待排序的数据，按其关键字的大小插入到已经排好序的一组记录的适当位置上，直到所有待排序数据全部插入为止
    • 时间复杂度为O（n^3/2）的方法
      • 希尔排序：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<…<d2<d1)
    • 时间复杂度为O（nlog2n）的方法
      • 堆排序：将待排序的序列构造成一个二叉树，然后进行换位调整保证所有子结点均小于其父结点，此时根结点值必为最大值，将该结点取出后再次建立二叉树，重复以上操作
      • 二路归并排序：①形成若干二元组并调整使组内有序②有序二元组两两归并成一组并调整至组内有序③所有数据归并到一组之内则完成排序
    • 时间复杂度为O (nlog(r)m)的方法 （r为所采取的基数，而m为堆数）
      • 基数排序：设置十个空间，分别命名为0空间,1空间,…,9空间，先按个位的数值将序列中的记录一一对应于各大空间并置入，在各空间内完成排序，之后从0空间开始取出各记录构成一个新序列，接下来在更高位重复该工作，直至完成最高位排序
  • 外部排序：待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的
    • 主流算法
      • 归并排序：将初始序列分为m个规模较小的记录段，并对这些记录段进行排序，不断地从各记录段的最小端对比取出最小值，直至完成排序
    • 重要子算法
      • 败者树：归并排序检测最小值时，不使用败者树则需要对读入的k个值进行k-1次比较，使用之后只需要进行log2k次，选最值时间复杂度为O(log2k),建树时间复杂度为O(klog2k),败者树高度为[log2k]+1
        • 建立
          • ①对读入的k个记录，以任意两个结点为一组建立二叉树，每一组取小值为胜者，败者对应的序列序号作为两者的父结点，胜者对应的序列序号作为父结点的父结点，若余下一个记录则下一趟处理②处理多余的那个记录，将其序列序号与某一个二叉树相比，按照胜者在上的准则归并为一颗树，并在该结点处连接多余记录值作为其子结点③将各二叉树相比较，按照胜者在上的准则归并为一颗树（败者树的根节点只有一个分叉，其余符合二叉原则）
        • 调整
          • 取出败者树中的最小值后，要加入新读入的记录组成败者树，此时需要对败者树进行调整以满足败者树的准则。调整方法：用新读入的记录补上空缺位置，然后由下而上逐级比较，胜者序号为败者序号的父结点，直至调整完毕
      • 置换-选择排序：根据缓冲区大小，由外存读入一段记录，当记录充满缓冲区后，选择最小的写回外存，其空缺位置由下一个读入记录取代，输出的记录成为当前初始归并段的一部分。如果新输入的记录比取出进入归并段的记录小则将它生成其他初始归并段的可选择项。反复进行以上操作
      • 最佳归并树：由置换-选择排序得出不同长度的归并段，根据其长度将每一段置于一颗赫夫曼树上（方法见树这一章节），从根节点出发到达每一个结点所经过的边数之和的两倍即为最佳归并树对应的I/O次数（最少I/O次数）