东北大学842（13）——没考过的知识点

笔记所有内容参考《东大红皮书》《王道》《天勤》，由本人分析整理。
842没考过的数据结构内容，稍微总结，基本不会考

算法5个特性

• 有穷性：有穷的步骤，有穷的时间内完成；
• 确定性：输入一致，输出一致；
• 可行性：可以实现
• 输入
• 输出

数据的存储结构（物理结构）

• 顺序结构：逻辑上相邻，物理上也相邻
• 链式结构：逻辑上相邻，物理上不相邻
• 索引结构：关键字与地址映射
• 散列结构：数据散列成地址

数据的存取方式

• 随机存取：直接访问第n个数据
• 顺序存取：访问第n个数据，需要先访问前n-1个数据

求时间复杂度

• 非递归情况：
  1. 找出基操作，基本操作规模n；
  2. 构建n = g(t) + k关系，求t = f(n)，o(f(n))。
• 递归情况：
  1. 先找递归出口，如：T(1) = 1;
  2. 寻找递归表达式，如：T(n) = 2T(n/2);
  3. 求解，如：T(n) = log{2, n};。

静态链表

• 一维数组（值，下一个元素的数组下标）；第一个数组元素作为头结点；最后的元素的下一个元素的数组下标为-1。

卡特兰数（Catalan）

1 / (n+1) * c{n, 2n}

• n个不同元素进栈，出栈序列个数；
• 长度为n的先序序列，构成二叉树的个数。

双端队列

1、2、3、4入队

• 输出受限能，输入受限不能：4、2、1、3（记忆方法：出是2B）
• 输入受限能、输出受限不能：4、1、3、2（记忆方法：入是B2）
• 都不能：4、2、3、1

三元组

• 一维数组（行，列，值）；适合稀疏矩阵压缩

广义表

• （表头, 表尾）
• 广义表长度：最上层元素个数
• 广义表深度：括号的最大层数

A = ( ) 长度0，深度1
B = (d, e) 长度2，深度1
C = (b, (c, d)) 长度2，深度2
D = (B, C)， 长度2，深度3
E = (a, E)，长度2，深度无限

树的双亲表示法

• 一维数组（值，双亲的数组下标）；根结点的双亲下标为-1

树的孩子表示法

• 一维数组（结点，孩子结点指针）；
• 孩子结点（孩子的下标，下一个兄弟结点指针）；

并查集

• 一维数组（双亲结点的下标）；
  根为-n，n为结点数
  非根为双亲的下标
• 特别适合做：
  1. 确保了没有环
  2. 容易找祖先

分块查找

• 索引表+查找表。先去查索引表、再去查查找表。

B树、B+树（没写得很细，没考过）

• B树
  m阶
  • 最多m个子树、最多m-1个关键字
  • 最少m/2上取整个子树、最少m/2上取整-1个关键字
  • 根结点不是终端结点时，最少2个子树
  • 所有叶结点都在同一层
• B树结点插入
  1. 像排序树一样插入到叶结点
     1.1. 关键字多于m-1时，分裂叶结点
     1.2. 多出来的一个，合并到双亲
• B树结点删除
  1. 寻找对应结点
  2. 调整，可以合并孩子；可以借孩子
• B+树
  • 关键字数等于孩子数
  • 所有关键字都在叶子
  • 叶子用单链表串一起

kmp

• next（字符串数组ch，整型数组next，nextval从1开始的）
  整型数组next的值：0代表主串后退一位，其他数字表示跳到对应数组ch的下标开始比较
  1. 求子串最长前后缀
  2. 整个数组向后退一位，第一位补-1
  3. 全体+1
• nextval（上面的优化，也是从1开始）
  1. 先求next数组
  2. 比较A = ch[next[i]]; B = ch[i];
     2.1. A != B: nextval[i] = next[i];
     2.2 A == B: nextval[i] = nextval[next[i]];
• 编程少考，和普通的串的模式匹配对比

//kmp字符串从1开始
//主字符串从1开始
//先写index再写getNext，会容易记
void getNext(char substr[], int subLength, int next[]) {
    int i = 1;
    int j = 0;  //注意
    next[1] = 0; //注意
    while(i < subLength) {
        if(j == 0 || substr[i] == substr[j]) {
            ++i;
            ++j;
            next[i] = j; //注意
        } else {
            j = next[j];
        }
    }
}

int Index(char str[], int length, char substr[], int subLength, int next[], int pos) {
    int i = pos;
    int j = 1; //字符串从1开始，从0开始next数组不好写
    while(i < length && j < subLength) {
        //注意 j == 0 ||
        if(j == 0 || str[i] == substr[j]) {
            ++i;
            ++j;
        } else {
            j = next[j];  // j = nextval[j];
            /*普通串的模式匹配，需要从新回到头，匹配
            i = i - j + 2;
            j = 0
            */
        }
    }
    if(j >= subLength) {
        return i - subLength;
    } else {
        return 0;
    }
}

归并排序

1. 把数列一分为二
2. 两数列归并
3. 把1，2递归

void MergeSort(int A[], int low, int high) {
    if(low < high) {
        int mid = (low + high) / 2;
        MergeSort(A, low, mid);
        MergeSort(A, mid + 1, high);
        Merge(A, low, mid, high);
    }
}

int B[Max];
void Merge(int A[], int low, int mid, int high) {
    //需要一个外部的数组拷贝
    for(int k = low; k <= high; ++k) {
        B[k] = A[k];
    }
    for(int i = low,int j = mid + 1, int k = i; i <= mid && j <= high; ++k) {
        if(B[i] < B[j]) {
            A[k] = B[i++];
        } else {
            A[k] = B[j++];
        }
    }
    while(i <= mid) {
        A[k++] = B[i++];
    }
    while(j <= high) {
        A[k++] = B[j++];
    }
}

外部排序

时间瓶颈->内外存IO耗时->减少外存到内存和内存到外存的次数->减少归并次数

1. 置换——选择排序：
   • 目的：获得较长的初始有序归并段，减少归并次数
   • 原理：利用一个数组，预先存放一定的数，方便分配有序的归并段
2. 最佳归并树：
   • 目的：使得总归并次数最小
   • 类似哈弗曼树，优先把较短的归并段归并，然后把较长的归并段归并
3. 败者树：
   • 目的：在m段归并段中取得最小值
   • 类似堆，不破坏全部，调整局部就可以取得最小值；
     • 类似比赛：败者指叶子，胜者（值小的）往上走，最后决出一个胜者（最小的）