数据结构¶

Chapter 0 绪论¶

数据结构研究的数据通常是非数值类数据。**研究问题的一般方法**是抽象、设计算法、编程。

数据的相关定义¶

1. 数据 客观事物的符号表示，能输入计算机进行处理
2. 数据元素 Data Element 数据的基本单位
3. 数据项 Data Item 组成数据元素的、独立的、不可分割的基本单位
4. 数据对象 Data Object 同性质的数据的集合

这里，数据元素（基本单位）包含了数据项（最小单位），可以通过element比item长来记忆。

数据的结构¶

1. 逻辑结构 可分为线性结构和非线性结构，表示数据的内在联系，与数据的储存结构无关
   1. 集合结构
   2. 线性结构
   3. 树结构
   4. 图结构
2. 存储结构
   1. 顺序存储结构
   2. 链式存储结构

抽象数据类型 ADT, Abstract Data Type¶

1. 数据对象 D
2. 数据对象上关系的集合 S
3. 对数据对象的基本操作的集合 P

算法 Algorithm¶

有穷性、确定性、可行性、可选输入、至少一个输出。

• 大O记号 来自*数量级*的英语*Order of Magnitude*，描述函数数量级的渐进上界。数学上，若T(n)和f(n)是定义在Z⁺上的两个函数。则T(n)=O(f(n))表示存在正的常数C和n₀，使得当n≥n₀时都满足0≤T(n)≤Cf(n)。即函数T(n)和f(n)具有相同的增长趋势，且T(n)的增长至多趋向于函数f(n)的增长。
• 最好、最坏和平均时间复杂度 人们更关心平均和最坏条件下的时间复杂度。平均时间复杂度一般不好估计，通常只讨论最坏条件下的时间复杂度。

算法的描述语言¶

相似于C语言，注意成组赋值(a, b, c) = (v1, v2, v3)和结构赋值struct some = { v1, v2, v3}，以及交换赋值a <-> b等补充语法。

Chapter 1 线性表¶

1. 顺序表
2. 线性链表
3. 循环链表 具有合并速度上的优势
4. 双向链表

Chapter 2 栈和队列¶

队列

1. 链式表示 链队列
2. 顺序表示 循环队列

栈

1. 顺序栈
2. 链栈

典型问题¶

1. 带优先级的括号匹配
2. 背包问题
3. 表达式的计算
   1. 后缀表达式
   2. 前缀表达式
   3. 中缀表达式

Chapter 3 串¶

空串"\0"、空格串" "。

定长顺序储存表示（下标0储存字符串长度）、堆分配储存表示（结构体字段储存字符串长度）和块链储存表示（类似链表）。

模式匹配算法¶

1. 朴素的暴风算法 Brute-Force
2. KMP算法

关键：寻找最大的n，使得长度为n的字符串前缀和后缀相同。

// 字符串采用定长顺序表示

// 返回主串str中第一个与模式串匹配的下标位置；如无匹配，返回0
int kmp(string str, string tmp)
{
    int i = 1, j = 1;
    while (i <= str[0] && j <= tmp[0]) {
        if (j == 0 || str[i] == str[j]) { ++i, ++j; }
        else j = next[j];
    }
    if (j > tmp[0]) { // 匹配成功
        return i - tmp[0];
    }
    return 0;
}

// 计算next数组
// next[j] == 0表示下一次匹配应该从主串的第i+1位与模式串的第1位开始
// next[j] != 0表示下一次匹配应该从主串的第i位与模式串的第next[j]位开始
void next(string tmp)
{
    int i = 1, j = 0; next[1] = 0;
    while (i < tmp[0]) {
        if (j == 0 || tmp[i] == tmp[j]) { ++i, ++j, next[i] = j; }
        else j = next[j];
    }
}

// 修正的next算法
// 解决形如此类的next问题
// j        | 1 2 3 4 5
// template | a a a a b
// next     | 0 1 2 3 4
// next-fix | 0 0 0 0 4
void next(string tmp)
{
    int i = 1, j = 0; next[1] = 0;
    while (i < tmp[0]) {
        if (j == 0 || tmp[i] == tmp[j]) {
            ++i, ++j;
            if (tmp[i] != tmp[j]) next[i] = j;
            else next[i] = next[j];
        }
        else j = next[j];
    }
}

Chapter 4 数组和广义表¶

数组¶

1. （高维）数组的定义 只有修改而没有插入或者删除操作
2. 二维（高维）数组的顺序表示
   1. 行序主序方式 谁为主序，谁就在储存空间上连续；行为主序，则内存中第一块为第一行内存，第二块为第二行的内存……
   2. 列序主序方式
   3. 高维数组，通常假定高维为主序

3. 由基地址和下标确定元素在内存中的储存位置

   Loc(j1, j2, ..., jn) = Loc(0, 0, ..., 0) + Σ[i=1, n]{CiJi}（实际求值中累加次序从n到1，以便利用下面的递推公式）

   其中Ji为数组第i维的下标，Bi为数组第i维的大小，Loc(j1, j2, ..., jn)为对应下标的数组元素在寄存器中的位置。
   Cn = L，为单位数组元素在内存空间中占据的大小，C_{i-1} = Ci * Bi

数组的应用：矩阵的压缩储存¶

特殊的矩阵类型

1. 对称矩阵
2. 上/下三角矩阵
3. 对角矩阵

广义表¶

1. 广义表的定义

   1. 表头 表中的第一个元素

   2. 表尾 表中除第一个元素以外所有元素构成的*广义表*

      广义表	表头	表尾
      ()	无定义	无定义
      (a)	a	()
      (a, b)	a	(b)

   3. 深度 广义表中括号的层数

   4. 长度 不递归地求解所有元素的个数

2. 广义表的储存结构

广义表的应用¶

1. m元多项式的表示
2. 广义表的递归算法

Chapter 5 树和二叉树¶

1. 树的定义 注意到树的定义中使用了递归定义
2. 二叉树的定义 度数不大于2的**有序树**。

可以用图、嵌套集合（类似文氏图）、广义表、凹入表示法（类似书的编目）等描述树的结构。

树的基本概念¶

竹子是节点，因为竹子是直的，节点在中间位置。树上结果，果子在尾端。再绳子结点，指交汇的位置。

结点是从英文node翻译过来的，node本身有“结”的意思，所以是结点。而且，node/结点形象地表示了交结在一点的这个意思，节则表示分段之间的连接部分，显然结点符合数据结构中的实际结构。

1. 结点（Node）
2. 结点的度 注意与图论中的度区分，这里的度指结点“拥有子树的个数”。
3. 终端节点/叶子节点/非终端节点
4. 双亲和孩子、兄弟、祖先、子孙、层次、堂兄弟
5. 深度/高度 注意根节点的深度为1。
6. 有序树/无序树 依据各个子树的次序是否可以交换区分。
7. 森林

满二叉树 非叶子节点的度均为2，且叶子节点分布于同一层。满二叉树具有以下性质：

1. k层的满二叉树至多有2ᵏ-1个结点。
2. n₀ = n₂ + 1。（度为0的结点个数比度为2的结点个数多1，推导时可以消去度为1的结点的个数。）

完全二叉树 前k-1层为满二叉树，第k层可以不满，但结点集中于左侧。

1. n个结点的完全二叉树深度为⌊log₂(n) + 1⌋或⌈log₂(n + 1)⌉。
2. 根节点的编号为1，左子节点为2i，右子节点为2i+1。

树的储存结构¶

1. 双亲表示法
2. 孩子表示法
3. 孩子兄弟法

二叉树的储存结构

1. 数组
2. 二叉链表
3. 三叉链表

线索二叉树¶

n个结点的二叉链表有n+1(2n-(n-1)=n+1)个空指针域。

充分利用二叉链表的空指针域的数据结构。本质是将非线性结构转换为线性结构。

针对二叉树的一种遍历方法（对应先序、中序或后序线索二叉树），重载LChild, RChild的含义。
LChild当结点的左孩子不空时存入左孩子，否则存入结点的直接前驱。RChild当结点的右孩子不空时存入有孩子，否则存入结点的直接后继。
利用布尔标记来区分LChild和RChild的两种状态。

• 线索 指向前驱节点/后继节点的指针。
• 线索化 将原本的二叉链表表示法中的空指针改为指向前驱或后继结点的指针。

线索二叉树的构建方法待添加。

将任意树转换为二叉树¶

1. 将所有兄弟节点用树枝相连
2. 双亲结点仅保留与长子的连接
3. 将树绕根节点顺时针旋转45°

将森林转换为二叉树的方法类似，可以看成存在超级树根为森林中各个子树的双亲结点，按上述算法转换，最后将超级树根从结果中去除即可。

树的遍历¶

1. 先序遍历（先根遍历）
2. 后序遍历（后跟遍历）
3. 中序遍历

根据二叉树的遍历来确定二叉树的序列 可以根据中序遍历和先序遍历、中序遍历和后序遍历唯一确定二叉树的序列，但不能根据线序遍历和后序遍历唯一确定二叉树的序列。

二叉树的递归算法¶

1. 深度计算
2. 统计节点个数

二叉树的应用¶

1. 波兰式/逆波兰式/中序表达式 分别对应表达式树的先序、后序和中序遍历。

哈夫曼树（最优编码二叉树）¶

1. 路径 从一个结点到另一个结点的分支
2. 路径长度
3. 树的路径长度（Path Length） 树的根节点到各个结点的路径长度之和
4. 带权路径长度
5. 树的带权路径长度（Weighted Path Length） 每个结点的权值与该节点到根节点的路径长度的乘积之和

哈夫曼算法是利用哈夫曼树生成最优编玛的算法。

哈夫曼树的性质

1. n个叶子结点的哈夫曼树有(2n-1)个结点。

Chapter 6 图¶

图的定义¶

1. 弧（有向边） 弧头、狐尾
2. 连通 连通图 连通分量（极大连通子图） 生成树（极小连通导出子图）
3. 图与网的区别是网中的结点时带权的。

图的储存结构¶

1. 邻接矩阵表示法 表示有向图时先行后列
2. 邻接表表示法
   1. 顶点的邻接表
   2. 有向图的邻接表（出边表/邻接表、入边表/逆邻接表）

图的遍历¶

1. DFS
2. BFS

最小代价生成树¶

1. 点优先Prim算法
2. 边优先的Kruskal算法

最短路径¶

1. 单源点最短路径 Dijkstra
2. 所有顶点间的最短路径 Floyd

拓扑排序¶

按出度或入度将顶点排序。

Chapter 7 查找¶

评价查找算法的性能：平均查找长度（关键字的平均比较次数）。

线性表的查找¶

技巧：

1. 使用哨兵以减少比较次数。
2. 对于有序线性表使用折半查找。

树表的查找（二叉排序树）¶

• 性质 左节点值小于根节点，右节点值大于或等于根节点。
• 生成算法 即使序列中元素相同，但根据插入顺序的不同就会生成不同形态的二叉排序树。将第一个插入的值作为根节点的值，随后根据性质来进行插入。
• 删除算法
  1. 若待删除的结点结点没有左子树和右子树，则直接删除。
  2. 若结点无右子树，用左子树代替根节点。
  3. 若结点无左子树，用右子树代替根节点。
  4. 若结点有左子树和右子树，则用右子树中序遍历的第一个元素（即“最左子孙”）替代根节点。注意此时右子树的结构相应地发生变化，需要*递归*调用删除算法。
• 平均查找长度ASL 最好情况 log₂(n) 最坏情况 (n+1)/2

散列表的查找¶

哈希函数的建立：

1. 直接定址法 Hash(key) = a * key + b
2. 除留余数法 Hash(key) = key % p

冲突是不可避免的，解决冲突的方法包括：

1. 线性探查法 NextHash(hash) = (hash + d) % p
2. 二次探测法 NextHash(hash) = (hash + di) % p，其中di为±1, ±2, ±4...
3. 拉链法
4. 伪随机探测法 d为随机增量。

Chapter 8 排序¶

• 稳定排序 若键值相等的两个元素在排序前a排在b之前，若排序后a仍然在b之前，则称算法是稳定的。
• 不稳定排序

插入排序¶

• 直接插入排序 稳定排序 注意插入位置的确定是由后往前的循环。
• 折半插入排序 稳定排序 利用折半查找寻找插入位置。
• 希尔排序（缩小增量排序） 不稳定排序 分组使用插入排序。

交换排序¶

• 冒泡排序 稳定排序
• 快速排序

选择排序¶

选择关键字最小的记录，放入有序序列的最后一个元素之后。稳定排序算法。

• 简单选择排序
• 堆排序

归并排序¶

递归地进行有序表的异地归并。