线性结构

线性表

线性表的定义

一个线性表是 n 个元素的有限序列（n≥0），通常表示为（a_1,a_2,a_3,…,a_n）。

线性表的顺序存储（顺序表）

是指用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。

优点：可以随机存取表中的元素，按序号查找元素的速度很快。

缺点：插入和删除操作需要移动元素。

线性表的链式存储（链表）

是指用节点来存储数据元素，元素的节点地址可以连续，也可以不连续。节点空间只有在需要时才申请，无需事先分配。

优点：插入和删除操作不需要移动元素

缺点：只能按顺序访问元素，不能进行随机存取。

链表的类别

单链表

循环链表

双链表

栈

栈和队列都是一种特殊的线性表，栈是按“后进先出”的规则进行操作的。

顺序栈

用一组地址连续的存储单元依次存储自栈顶到栈底的数据元素。

存储空间是预先定义或申请的，因此可能会出现栈满的情况。

每一个元素入栈时都要判断栈是否已满。

需要设置一个头指针指到栈顶。

需要附设指针top指示栈顶元素的位置。

链栈

用链表存储栈中的元素。

栈中元素的插入和删除仅在栈顶进行，因此不必设置头节点，链表的头指针就是栈顶指针。

队列

队列是一种“先进先出”的线性表，队尾入队头出。

队列的顺序存储

顺序队列

循环队列

队列的链式存储（链队列）

为了便于操作，可以给链队列添加一个头节点，并令头指针指向头节点。

队列为空的判定条件就是头指针和尾指针的的值相同，并且均指向头节点。

串

• 字符串是一串文字及符号的简称，是一种特殊的线性表。
• 字符串的基本数据元素是字符，常常把一个串作为一个整体来处理。
• 串是仅由字符构成的有限序列，是取值范围受限的线性表。一般记为 S=’a_1a_2…a_n’，其中 S 是串名，单引号括起来的字符序列是串值。
• 串长：即串的长度，指字符串中的字符个数。
• 空串：长度为0的空串，空串不包含任何字符。
• 空格串：由一个或多个空格组成的串。
• 子串：由串中任意长度的连续字符构成的序列称为子串。
• 串相等：指两个串长度相等且对应位置上的字符也相同。
• 串比较：两个串比较大小时以字符的ASCII码值作为依据。

串的存储结构

顺序存储：用一组地址连续的存储单元来存储串值的字符序列。

链式存储：字符串可以采用链表作为存储结构，当用链表存储串中的字符时，每个结点中可以存储一个字符，也可以存储多个字符。

数组

由于数组一般不做插入和删除，且元素个数和元素之间的关系不再发生变动，那么数组适合采用顺序存储结构。

数组元素的存储方式及相关计算：

二维数组的存储结构可分为以行为主序（按行存储）和以列为主序（按列存储）两种方法。

设每个数据元素占用L个单元，m、n为数组的行数和列数，那么

以行为主序优先存储的地址计算公式为
Loc(a_{ij})=Loc(a_{11})+((i-1)×n+(j-1))×L

以列为主序优先存储的地址计算公式为：
Loc(a_{ij})=Loc(a_{11})+((j-1)×m+(i-1))×L

矩阵

这里主要讨论一些特殊矩阵的压缩存储的问题。

对多个值相同的元素可以只分配一个存储单元，零元素不分配存储单元。

下面主要讨论对称矩阵、三对角矩阵、稀疏矩阵。

对称矩阵

若矩阵 A_{n×n}中的元素有 a_{ij}=a_{ji}(1≤i，j≤n)的特点，则称之为对称矩阵。

则矩阵 A_{n×n}的 n^2 个元素可以压缩存储到可以存放 \dfrac{n(n+1)}2 个元素的存储空间中。假设以行为主序存储下三角（包括对角线）中的元素，并以一个一维数组 B[n(n+1)/2] 作为 n 阶对称矩阵 A 中元素的存储空间，则B[k] (0≤k<\dfrac{n(n+1)}2)与矩阵元素 a_{ij}(a_{ji})之间存在着一一对应的关系：

k=\left\{\begin{matrix}\dfrac {i (i-1)}{2}+j-1\ 当\\i\ge j \\\dfrac {j (j-1)}{2}+1-1\ 当\\i< j\end{matrix}\right.

三对角矩阵

对角矩阵是指矩阵中的非零元素都集中在以主对角线为中心的带状区域中，其余的矩阵元素都为零。

下面主要考虑三对角矩阵，即只有主对角线及其左右两边为非零元素。

若以行为主序将 n 阶三对角矩阵 A_{n×n} 的非零元素存储在一维数组B[k]$(0≤k<3n-2)$中，则元素位置之间的对应关系为
k=3×(i-1)-1+j-i+1=2i+j-3\ (1≤i,j≤n)

稀疏矩阵

在一个矩阵中，若非零元素的个数远远少于零元素的个数，且非零元素的分布没有规律，则称之为稀疏矩阵。

可以用一个三元组 (i,j,a_{ij})唯一确定矩阵中的一个元素。

树

定义：树是 n(n≥0) 个节点的有限集合。当 n=0 时称为空树。在任一非空树中，有且仅有一个称为根的节点：其余节点可分为 m(m≥0) 个互不相交的有限集 T_1,T_2…,T_m，其中每个集合又都是一棵树，并且称为根节点的子树。

树的相关概念

1. 双亲、孩子和兄弟
2. 节点的度：一个节点的子树的个数记为该节点的度。
3. 叶子节点：也称为终端节点，指度为零的节点。
4. 内部节点：度不为零的节点称为分支节点或非终端节点。除根节点之外，分支节点也称为内部节点。
5. 节点的层次：根为第一层，根的孩子在第二层，依此类推。
6. 树的高度：一棵树的最大层次数记为树的高度（或深度）

二叉树

定义：二叉树是 n(n≥0) 个节点的有限集合，它或者是空树 (n=0)，或者是由一个根节点及两棵不相交的、分别称为左子树和右子树的二叉树所组成。

树和二叉树的区别：

1. 二叉树中节点的子树要区分左子树和右子树，即使只有一棵子树，而树中不用区分。
2. 二叉树中节点的最大度为 2，而树中无限制

二叉树的性质

1. 二叉树第 i(i≥1)层上至多有 2^{i-1} 个节点。
2. 深度为 k 的二叉树至多有 2^{k-1}个节点 (k≥1)。
3. 对任何一棵二叉树，若其终端节点数为 n_0，度为 2 的节点数为n_2，则 n_0=n_2+1。

满二叉树和完全二叉树

满二叉树的定义：若深度为 k 的二叉树有 2^k-1个节点，则称其为满二叉树。

完全二叉树：当深度为 k、有 n 个节点的二叉树，当且仅当其每一个节点都与深度为 k 的满二叉树中编号为 1～n 的节点一一对应时，称之为完全二叉树。

完全二叉树的性质

设深度为 k 的完全二叉树共有 n 个节点，那么可知，除第 k 层外，其余各层都有最多的节点数。

具有 n 个节点的完全二叉树的深度为 INT(\log_2n)+1。

假设有编号为 i 的节点，则有：

1. 若 i=1，则该节点为根节点，无双亲；若 i>1，则该节点的双亲节点为 INT(\dfrac{i}{2})若
2. $2i≤n$，则该节点的左孩子编号为 $2i$，若 $2i>n$，无左孩子。
3. 若 2i+1≤n，则该节点的右孩子编号为 2i+1，若 2i+1>n，无右孩子。

二叉树的存储结构

顺序存储

链式存储

二叉树的遍历

依据访问根节点次序的不同，可分为前序遍历法、中序遍历法、后序
遍历法。

1. 中序遍历法：（左、根、右）
   1. 中序遍历根的左子树。

   2. 访问根节点。

   3. 中序遍历根的右子树。

      依此类推。

2. 前序遍历法：先访问根节点（根、左、右）
3. 后序遍历法：后访问根节点（左、右，根）
4. 层序遍历法：按层从上至下、每层从左至右的顺序遍历。

最优二叉树（哈夫曼树）

最优二叉树又称哈夫曼树，是一类带权路径长度最短的树。

权：是一个人为的概念，表示计算机对每个节点的访问频率。

路径长度：是每一个结点到根节点的路径的长度。

节点的带权路径长度：是指从该节点到根节点之间的路径长度与该节点权的乘积。

树的带权路径长度为树中所有叶子节点的带权路径长度之和。

构造最优二叉树的哈夫曼方法

1. 根据给定的 n 个权值 {w_1, w_2,…,w_n}构成 n 棵二叉树的集合F={T_1,T_2,…,T_n}，其中每棵树 T_i 只有一个带权为 w_i 的根节点，其左右子树均空。

2. 在 F 中选取两棵根节点的权值最小的树作为左右子树，构造一棵新的二叉树，置新构造二叉树的根节点的权值为其左、右子树根节点的权值之和。

3. 从 F 中删除这两棵树，同时将新得到的二叉树加入到 F 中。

   重复 2、3 步，直到 F 中只含一棵树时为止，这棵树便是最优二叉树（哈夫曼树）。

二叉查找树

二叉查找树又称为二叉排序树。它或者是一棵空树，或者是具有如下性质的二叉树：

1. 若它的左子树非空，则左子树上所有节点的关键码值均小于根节点的关键码值。
2. 若它的右子树非空，则右子树上所有节点的关键码值均大于根节点的关键码值。
3. 左、右子树本身就是两棵二叉查找树。
   1. 对二叉查找树进行中序遍历，可得到一个关键码递增有序的节点序列。
   2. 二叉查找树的作用：使用二叉查找树来查找树中的数值比普通的二叉树更为方便。

二叉查找树的查找操作递归实现：

1. 从根节点开始查找，如果树为空，则返回 NULL，否则，若根节点的关键码值等于查找的值，则查找成功。
2. 否则，若小于根节点的码值，则查找其左子树，若大于根节点的关键码值，则查找其右子树。

图

图的定义

一个图 G(\mathrm{Graph}) 是由两个集合：V 和 E 所组成的，V 是有限的非空顶点 (\mathrm{Vertex}) 集合，E是用顶点表示的边 (\mathrm{Edge}) 集合，图 G 的顶点集和边集分别记为 V(G) 和 E(G)，而将图 G 记作 G=(V,E)。

可以看出，一个顶点集合与连接这些顶点的边的集合可以唯一表示一个图。

在图中，数据结构中的数据元素用顶点表示，数据元素之间的关系用边表示。

图的相关概念

有向图：图中每条边都是有方向的。从顶点 v_i 到顶点 v_j 表示为<v_i,v_j>，而从顶点 v_j 到顶点 v_i 表示为 <v_j,v_i>。有向边也称为弧。起点称为弧尾，终点称为弧头。

无向图：图中每条边都是无方向的。顶点 v_i 和 v_j 之间的边用 (v_i,v_j) 表示。在无向图中，(v_i,v_j) 和 (v_j,v_i) 表示的是同一条边。

完全图：若一个无向图具有 n 个顶点，而每一个顶点与其他 n-1 个顶点之间都有边，则称之为无向完全图。显然，含有 n 个顶点的无向完全图共有 \dfrac{n(n-1)}{2}条边，类似地，有 n 个顶点的有向完全图中弧的数目为 n(n-1)，即任意两个不同顶点之间都存在方向相反的两条弧。

度：顶点所连边的数目称为度。

出度和入度：在有向图中，由于边有方向，则顶点的度分为入度和出度。

路径：两顶点之间的路径指顶点之间经过的顶点序列，经过路径上边的数目称为路径长度。

子图：若有两个图 G=(V,E),\ G_1=(V_1,E_2)，若 V_1 是 V 的子集且 E_2 是 E 的子集，称 G_1 是 G 的子图。

连通图：在无向图中，如果两个顶点之间有路径，则称这两个顶点是连通的。

强连通图：在有向图中，两顶点两个方向都有路径，两顶点称为强连通。若任一顶点都是强连通的，称为强连通。有向图中极大强连通子图为有向图的强连通分量。

网：图中每条边上标有某种含义的数值，该数值称为该边的权值。这种图称为带树图，也称作网。

图的存储结构

邻接矩阵表示法

网（带有权值的图）的邻接矩阵的表示

邻接链表表示法

邻接链表是为图的每一个顶点建立一个单链表，第 i 个单链表中的节点
表示依附于顶点 v_i 的表（对于有向图是以 v_i 为尾的弧）。

邻接链表中的表节点有表节点和表头节点两种类型

无向图的邻接链表表示法

有向图的邻接链表表示法

带权值的网的邻接链表表示法

排序算法

直接插入排序

具体做法是：在插入第 i 个记录时，R_1,R_2,…,R_{i-1} 已经排好序，将记录 R_i 的关键字 k_i 依次与关键字 k_{i-1},k_{i-2},…,k1 进行比较，从而找到 R_i 应该插入的位置，插入位置及其后的记录依次向后移动。

待排序列：35 12 67 29 51

第1步：35

第2步：12 35

第3步：12 35 67

第4步：12 29 35 67

第5步：12 29 35 51 67

冒泡排序

首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则交换两个记录的值，然后比较第二个记录和第三个记录的关键字，依此类推。

待排序列：35 12 67 29 51

第一次冒泡排序：

1. 12 35 67 29 51
2. 12 35 67 29 51
3. 12 35 29 67 51
4. 12 35 29 51 67

第二次冒泡排序：

1. 12 35 29 51 67
2. 12 29 35 51 67

简单选择排序

n 个记录进行简单选择排序的基本方法是：

通过 n-i 次关键字之间的比较，从 n-i+1 个记录中选出关键字最小的记录，并和第 i(1≤i≤n)个记录进行交换，当 i 等于 n 时所有记录有序排列。

待排序列：35 12 67 29 51

1. 找出最小值12，与第一个关键字进行交换： 12 35 67 29 51
2. 找出剩下 4 个记录中的最小值 29，与第二个关键字交换：12 29 67 35 51
3. 找出剩下 3 个记录中的最小值 35，与第三个关键字交换：12 29 35 67 51
4. 找出剩下 2 个记录中的最小值 51，与第四个关键字交换：12 29 35 51 67

希尔排序

希尔排序又称“缩小增量排序”，是对直接插入排序方法的改进。

先将整个待排记录序列分割成若干子序列，然后分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。

快速排序

通过一趟排序将待排的记录划分为独立的两部分，称为前半区和后半区，其中，前半区中记录的关键字均不大于后半区记录的关键字，然后再分别对这两部分记录继续进行快速排序，从而使整个序列有序。

具体做法：附设两个位置指示变量 i 和 j ，它们的初值分别指向序列的第一个记录和最后一个记录。设枢轴记录（通常是第一个记录）的关键字为 pivot，则首先从 j 所指位置起向前搜索，找到第一个关键字小于 pivot 的记录时将该记录向前移到i指示的位置，然后从 i 所指位置起向后搜索，找到第一个关键字大于 pivot 的记录时将该记录向后移到 j 所指位置，重复该过程直至 i 与 j 相等为止。

堆排序

堆：对于 n 个元素的关键字序列 {k_1,k_2,…,k_n}，当且仅当满足下列关系时称其为堆。
\left{\begin{matrix}
k_i ≤ k_{2i} \
k_i ≤ k_{2i+1}
\end{matrix}\right.
\ 或\
\left{\begin{matrix}
k_i \ge k_{2i} \
k_i \ge k_{2i+1}
\end{matrix}\right.
基本思想：对一组待排序记录的关键字，首先把它们按堆的定义排成一个序列（即建立初始堆），从而输出堆顶的最小关键字（对于小顶堆而言）。然后将剩余的关键字再调整成新堆，便得到次小的关字，如此反复，直到全部关键字排成有序序列为止。

归并排序

基本思想：把一个有 n 个记录的无序文件看成是由 n 个长度为 1 的有序子文件组成的文件，然后进行两两归并，得到 \dfrac{n}{2}个长度为 2 或 1 的有序文件，再两两归并，如此重复，直至最后形成包含 n 个记录的有序文件为止。

总结

1. 直接插入排序：按顺序插入待排关键字，插入时依次查找位置，直接插入，后面的依次后移。
2. 冒泡排序：依次把相邻的两个记录进行比较，然后交换位置。
3. 简单选择排序：每次选择最小的，与第一个没有排过序的记录交换。
4. 希尔排序：间隔若干个空的记录分为一组，进行直接插入排序，依次将间隔缩小到1为止。
5. 快速排序：设两个指针指示头尾，从尾开始，首尾交替轮流和枢轴记录（第一个记录）进行比较，并交换位置。
6. 堆排序：反复将待排序列建立成堆，并取堆顶。
7. 归并排序：两两归并为一组，再四个记录归并为一组，依此类推。

排序方法	最好时间	平均时间	最坏时间	辅助空间	稳定性
直接插入排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	稳定
简单选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定
冒泡排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	稳定
希尔排序	–	$O(n^{1.25})$	–	$O(1)$	不稳定
快速排序	$O(n\log_2n)$	$O(n\log_2n)$	$O(n^2)$	$O(\log_2n)~O(n)$	不稳定
堆排序	$O(n\log_2n)$	$O(n\log_2n)$	$O(n\log_2n)$	$O(1)$	不稳定
归并排序	$O(n\log_2n)$	$O(n\log_2n)$	$O(n\log_2n)$	$O(n)$	稳定

查找算法

查找表及查找效率

查找表定义：是指由同一类型的数据元素（或记录）构成的集合。

静态查找表：只进行“查询”和“检索”操作。

动态查找表：除了查询和检索外可能还会进行插入和删除操作。

关键字：是数据元素(或记录)的某个数据项的值，用它来识别（标识）这个数据元素(或记录)。

查找：根据给定的某个值，在查找表中确定是否存在一个其关键字等于给定值的记录或数据元素。

平均查找长度(ASL)：对于查找算法来说，其基本操作是“将记录的关键字与给定值进行比较”。因此，通常以“其关键字和给定值进行比较的记录个数的平均值”作为衡量查找算法好坏的依据。

顺序查找

从表中的一端开始，逐个进行记录的关键字和给定值的比较，若找到一个记录的关键字与给定值相等，则查找成功；若整个表中的记录均比较过，仍未找到关键字等于给定值的记录，则查找失败。

查找效率低，但是算法简单且适应面广。

折半查找（二分查找）

基本思想：先令查找表中间位置记录的关键字和给定值比较，若相等，则查找成功；若不等，则缩小范围，直至新的查找区间中间位置记录的关键字等于给定值或者查找区间没有元素时（查找不成功）为止。

这种方法要求查找表进行顺序存储并且按关键字有序排列。

查找效率比顺序查找要高，但要求关键字有序排列。

适用于表不易变动，且又经常进行查找的情况。

折半查找断定树

从折半查找的过程来看，可以用一棵二叉树来描述。通常称这个描述折半查找二叉树的过程称为折半查找判定树。

树表查找

二叉查找树是一种动态查找表，表结构本身是在查找过程中动态生成的。

设关键字序列为{46，25，54，13，29，91}

索引顺序查找(分块查找)

是对顺序查找的一种改进

将表分成若干块，每一块中的关键字不一定有序，但块之间是有序的。

哈希查找

前面几种查找方法中，记录的存储位置和关键码之间不存在确定的关系，因此查找时都要建立在对关键字进行比较的基础之上。

哈希函数：关键字作为自变量，关键字存放的地址作为因变量。
H_i=\mathrm{Hash}(Key)
这一映射过程称为哈希造表或散列，所得的存储位置称为哈希地址或散列地址。

冲突：对于某个哈希函数 \mathrm{Hash} 和两个关键字 K_1 和 K_2，如果 K_1≠K_2而 \mathrm{Hash}(K_1)=\mathrm{Hash}(K_2)，则称出现了冲突。

采用哈希法主要考虑的两个问题是哈希函数的构造和冲突的解决。

冲突的处理：

1. 开放定址法：
   H_i=(\mathrm{Hash}(key)+d_i) \% m\ (i=1,2,…,k\ (k≤m-1)）

   其中，\mathrm{Hash}(key)为哈希函数，m 为哈希表的表长，d_i为增量序列。

   常见的增量序列有如下三种：

   • $d_i=1,2,3,…,m-1$，称为线性探测再散列。
   • $d_i=1^2,-1^2,2^2,-2^2,3^2,…,±k^2 (k≤m/2)$，称为二次探测再散列。
   • $d_i=$ 伪随机序列，称为随机探测再散列。
2. 链地址法：它将具有相同哈希函数值的记录组织成一个链表，当链域的值为 NULL 时，表示已没有后继记录。

   地址里存放的是指针，而不是关键字，将哈希函数值相同的记录组成一个链表

图的相关算法

生成树与最小生成树

生成树的概念：设图 G=(V,E) 是个连通图，如果其子图是一棵包含 G 的所有顶点的树，则该子图称为 G 的生成树。

最小生成树：对于连通网来说，边是带权值的，生成树的各边也带权
值，于是就把生成树各边的权值总和称为生成树的权，把权值最小的
生成树称为最小生成树。

求最小生成树的两种算法：普里姆算法、克鲁斯卡尔算法。

普里姆算法

以顶点为主

克鲁斯卡尔算法

以边为主

求单源点的最短路径算法

单源点最短路径：给定带权有向图 G 和源点 v_0，求从 v_0 到 G 中其余各顶点的最短路径。

迪杰斯特拉算法