浙大数据结构的期末复习笔记

最后刚好90分。 这个真的也不能随波逐流，要自己弄明白。

image.png 这一题，在对数上

学过对数之后就会知道 n log n² = 2n log n 2. image.png CCC 析：再散列将散列表扩大一倍，表长变为20，然后取最近的质数23作为表长。

排序

基数排序

基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。 在r与m确定情况下，时间复杂度为线性。

image

LSD(次位优先)——MSD（主位优先）

效率分析

时间效率 [1] ：设待排序列为n个记录，d个关键码，关键码的取值范围为radix，则进行链式基数排序的时间复杂度为O(d(n+radix))，其中，一趟分配时间复杂度为O(n)，一趟收集时间复杂度为O(radix)，共进行d趟分配和收集。 空间效率：需要2*radix个指向队列的辅助空间，以及用于静态链表的n个指针。

希尔排序

希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。

图

在任一有向图中，所有顶点的入度之和等于所有顶点的出度之和

最小生成树

  1. 是一颗无回路的树
  2. 是包含全部顶点的生成树
  3. 边的权重和最小
  4. 生成树存在->图连通

贪心算法

  1. 每一步都要最好的
  2. 每次都选择权重最小的边
  3. 约束：
    1. 只能用图原有的边
    2. 只能正好用掉v-1条边
    3. 不能有回路

Prim

普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。

大致思想是：设图G顶点集合为U，首先任意选择图G中的一点作为起始点a，将该点加入集合V，再从集合U-V中找到另一点b使得点b到V中任意一点的权值最小，此时将b点也加入集合V；以此类推，现在的集合V={a，b}，再从集合U-V中找到另一点c使得点c到V中任意一点的权值最小，此时将c点加入集合V，直至所有顶点全部被加入V，此时就构建出了一颗MST。因为有N个顶点，所以该MST就有N-1条边，每一次向集合V中加入一个点，就意味着找到一条MST的边。

拓扑排序

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

排序方法

随时将入度变为0的顶点放到容器里

相关问题有关键路径问题——由绝对不允许延误的活动组成的路径

树

二叉搜索树

  1. 非空左子树的所有键值小于其根结点的键值。
  2. 非空右子树的所有键值大于其根结点的键值。

并查集

并查集问题可以用树进行实现，树的每个结点代表一个集合元素 采用数组存储形式。每个结点包含两部分

  1. Data
  2. Parent
  3. 其中 Parent 负数表示根结点，非负数表示Rarent结点的下标
  4. 查找元素所在集合——返回根结点
  5. 并运算。找到各自的根结点，不同根，则将一个根结点的Parent指针设置成另一个根结点的数组下标

平衡二叉树

  1. 平衡因子：为左右子树高度的差值
  2. 空树、任意节点平衡因子不大于1的树为平衡二叉树。
  3. 结点数为N的AVL树的最大高度为$O(log_{2N})$
  4. 一棵平衡二叉树的所有非叶结点的平衡因子都是0，则其必为完美二叉树

最小堆

  1. 结构满足完全二叉树
  2. 对于任一子树都满足，根大于（或小于）左右子树的要求。一般为最小堆，是小于
  3. 其插入时间复杂度为logN，
  4. 插入——放入树的底层，满足完全二叉树，然后自下而上调整。
  5. 删除，去除根结点，将树底层最右一个元素移动至根，然后自上而下调整。时间复杂度均为logN

哈夫曼树

  1. 目的是根据结点不同的查找频率构造更有效的搜索树
  2. 也叫，最优二叉树。即带权路径长度（WPL）最小的二叉树
  3. 没有度为1的结点
  4. n个叶子结点共有2n-1个结点
  5. 任意非叶节点的左右子树交换后仍然是哈夫曼树
  6. 对于同一组权值，可能存在不同构的两颗哈夫曼树
  7. 哈夫曼树的它的字母都在叶子节点上，因此不会出现一个字母的编码为另一个字母编码左起子串的情况。

哈夫曼树是一棵满二叉树，树中只有两种类型的节点，即叶子节点和度为2的节点，所以树中任意节点的左子树和右子树同时存在。构建步骤如下：

对字符集合按照字符频率进行升序排序，并构建一颗空树； 遍历字符集合，将每一个字符添加到树中，添加规则为：

  1. 若树为空，则作为根节点；
  2. 若字符频率不大于根节点频率，则字符作为根节点的左兄弟，形成一个新的根节点，频率值为左、右子节点之和；
  3. 若字符频率大于根节点频率，则字符作为根节点的右兄弟，形成一个新的根节点，频率值为左右子节点之和。

散列

冲突处理方法

  1. 换个位置：开放地址法
    1. 线性探测
    2. 平方探测：有定理显示，如果散列表长度TableSize是某个4k+3形式的素数时，其可以探查到整个散列表空间
    3. 双散列：使用另一个散列函数，并保证所有散列存储单元都能被探测到
    4. 开放地址法中，删除操作要很小心，只能懒惰删除。即只增加一个删除标记（Deleted）。确保查找时不会“断链”。其空间可以在下次插入时重用。
  2. 同一位置的冲突对象组织在一起： 链地址法——将相应位置上冲突的所有关键词存储在同一个单链表中
  3. 再散列：装填因子过高时，拓展存储空间

性能分析

平均查找长度（ASL）度量