数据结构复习笔记

第一章

数据：

对客观事物的符号描述，能输入到计算机中并被计算机程序处理的符号总称。
能被计算机识别、存储和加工处理的信息的载体。

数据元素（记录）：

数据元素是组成数据的基本单位，是数据集合的个体，在计算机中通常作为一个整体进行考虑和处理。

数据项（字段）：

一个数据元素可由若个数据项组成。
数据项是数据不可分割的最小单位。

数据结构（二元组，有特定关系的数据元素的集合）：

数据结构是指相互之间存在一种或多种特定关系的数据元素集合。
数据结构的内容可归纳为三个部分：逻辑结构、存储结构和运算集合。按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机的存储器中，并在这些数据上定义了一个运算的集合，就叫做数据结构。

数据逻辑结构（线性结构，非线性结构）：

线性结构：该结构中的结点之间存在一对一的关系。其特点是开始结点和终端结点都是唯一的，除了开始结点和终端结点以外，其余结点都有且仅有一个前驱结点，有且仅有一个后继结点。
非线性结构：该结构中的结点之间存在一对多或多对多的关系。它又可以细分为树形结构和图形结构两类。
- 树形结构：该结构中的结点之间存在一对多的关系。其特点是每个结点最多只有一个前驱，但可以有多个后继，可以有多个终端结点。非线性结构树形结构简称为树。
- 图形结构：该结构中的结点之间存在多对多的关系。其特点是每个结点的前驱和后继的个数都可以是任意的。因此，可能没有开始结点和终端结点，也可能有多个开始结点、多个终端结点。图形结构简称为图。

存储结构（顺序存储、链式存储）：

链式存储法的缺点：
- 存储空间占用大
- 无法随机访问
链式存储法的优点：
- 便于修改（插入、删除、移动）

抽象数据类型（Abstract Data Type）:

是指用户进行软件系统设计时从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的运算，而不考虑计算机的具体存储结构和运算的具体实现算法。
一个抽象数据类型的模块通常应包含定义（三元组）、表示和实现三部分。

第二章

线性表的定义：

一个线性表是具有n个数据元素的有限序列。

顺序存储线性表（顺序表）的特点：

逻辑结构中相邻的数据元素在存储结构中仍然相邻。
线性表的顺序存储结构是一种随机存取的存储结构。

链式存储线性表的特点：

用一组任意的存储单元存储线性表的元素，不要求逻辑上相邻的元素在物理位置上也相邻。
插入删除时不需要移动大量元素。
失去顺序表可随机存取的优点。

第三章

KMP算法：

int* getNext(char* str) {
    int len = strlen(str);
    int* next = (int*)malloc(sizeof(int) * len);
    if (!next) return NULL;
    next[0] = 0;
    for (int i = 1, j = 0; i < len; i++) {
        while (j > 0 && str[i] != str[j]) {
            j = next[j - 1];
        }
        if (str[i] == str[j]) {
            j++;
        }
        next[i] = j;
    }
    return next;
}

int strStr(char* haystack, char* needle) {
    int* next = getNext(needle);
    if (!next) return -1;
    int len1 = strlen(haystack);
    int len2 = strlen(needle);
    for (int i = 0, j = 0; i < len1; i++) {
        while (j > 0 && haystack[i] != needle[j]) {
            j = next[j - 1];
        }
        if (haystack[i] == needle[j]) {
            j++;
        }
        if (j == len2) {
            return i - len2 + 1;
        }
    }
    return -1;
}

第六章

根：

树有且仅有一个特定的称为根的结点，它没有直接前驱，但有零个或多个直接后继。

结点：

包含一个数据元素及若干指向其子树的分支。

结点的度：

结点拥有的子树个数。

树的度：

树内各结点的度的最大值。

叶子：

度为0的结点，也称为终端结点。

分支结点：

度不为0的结点，也称为非终端结点。除根结点外的分支结点也称为内部结点。

结点的层次：

从根节点开始定义，根为第一层，根的孩子为第二层，以此类推。

树的高度（深度）：

树中结点的最大层次。

满二叉树：

深度为k且有2 ^ k - 1个结点的二叉树。在满二叉树中，每层结点都是满的，即每层结点都具有最大结点数。

完全二叉树：

深度为k，结点数为n的二叉树，如果其结点1 ~ n的位置序号分别与满二叉树的结点1 ~ n的位置序号一一对应，则为完全二叉树。

二叉树的性质：

在二叉树的第i层至多有2 ^ (i - 1)个结点（i >= 1）。
深度为k的二叉树至多有2 ^ k - 1个结点（k >= 1）。
对任意一棵二叉树，若终端结点数为n0，度为2的结点数为n2，则n0 = n2 + 1。
具有n个结点的完全二叉树的深度为[log2(n)] + 1或[log2(n + 1)]。
对完全二叉树中编号为i的结点（1 <= i <= n, n >= 1, n为结点数）有：
1. - 若i = 1，则结点i是二叉树的根，无双亲。
  - 若i > 1，则它的双亲结点的编号为[i / 2]。当i为偶数时，其双亲结点的编号为i / 2，它是双亲结点的左孩子结点；当i为奇数时，其双亲结点的编号为(i - 1) / 2，它是双亲结点的右孩子结点。
2. - 若编号为i的结点有左孩子结点，则左孩子结点的编号为2i；若编号为i的结点有右孩子结点，则右孩子结点的编号为2i + 1。
  - 当2i > n，则结点i无左孩子，无左孩子则结点i为叶子结点；当2i + 1 > n，则结点无右孩子。
3. - 若n为奇数，则每个分支结点都既有左孩子结点，也有右孩子结点；若n为偶数，则编号最大的分支结点（编号为n / 2）只有左孩子结点，没有右孩子结点，其余分支结点都有左、右孩子结点。

二叉树空链域求法：

空链域数：2n - (n - 1) = n + 1。
n个结点的二叉树，有2n个指针，有n - 1条边（根结点没有父节点），减去边数的指针数即为空链域数。

树、森林与二叉树的相互转换：

树转换为二叉树：
1. 在所有相邻兄弟结点之间加一水平连线。
2. 对每个非叶结点k，除了其最左边的孩子结点外，删去k与其他孩子结点的连线。
3. 所有水平线段以左边结点为轴心顺时针旋转45度，使之结构层次分明。
森林转换为二叉树：
1. 将森林中的每棵树转换成相应的二叉树。
2. 第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连在一起后，所得到的二叉树就是由森林转换得到的二叉树。
二叉树还原为树或森林
1. 若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子……都与该结点的双亲结点用线连起来。
2. 删掉原二叉树中所有双亲结点与右孩子结点的连线。
3. 整理由(1)、(2)两步所得到的树或森林，使之结构层次分明。

由先序、中序序列构造二叉树的算法：

BiTNode* CreateBT(char* pre, char* in, int n) {
    // 创建结点
    BiTNode* s = (BiTNode*)malloc(sizeof(BiTNode));
    if (!s) exit(-1);
    s->data = *pre;
    s->lchild = s->rchild = NULL;
    // 若只有一个结点，则直接返回
    if (n == 1) return s;
    // 在中序序列中找根结点的位置
    char* p;
    for (p = in; p < in + n; p++)
        if (*p == *pre)
            break;
    int k = p - in;
    if (k) s->lchild = CreateBT(pre + 1, in, k);
    if (n - k - 1) s->rchild = CreateBT(pre + k + 1, p + 1, n - k - 1);
   	return s;
}

由后序、中序构造二叉树的算法：

BiTNode* CreateBT(char* post, char* in, int n) {
    // 创建结点
    BiTNode* s = (BiTNode*)malloc(sizeof(BiTNode));
    if (!s) exit(-1);
    s->data = *(post + n - 1);
    s->lchild = s->rchild = NULL;
    // 若只有一个结点，则直接返回
    if (n == 1) return s;
    // 在中序序列中找根结点的位置
    char* p;
    for (p = in; p < in + n; p++)
        if (*p == *post)
            break;
    int k = p - in;
    if (k) s->lchild = CreateBT(post, in, k);
    if (n - k - 1) s->rchild = CreateBT(post + k, p + 1, n - k - 1);
    return s;
}

构造哈夫曼树（哈夫曼算法）：