数据结构 | 杨记

线性表，栈和队列，串，数组，广义表，树，二叉树，图，查找，内部排序，外排序，Trie结构，红黑树，伸展树

基本概念

什么是数据结构

1、按某种逻辑关系组织起来的一批数据（逻辑结构）例如：线性表、树、图

2、以一定的方式存于计算机中（存储结构）例如：数组、链表等

3、在这组数据上定义了运算的集合。例如：插入、删除、查找、排序等

程序 = 数据结构 + 算法

术语

数据 data：能够输入到计算机中并被计算机程序处理的信息，包括文字、表格、图像等，都称为数据。

数据元素 data element：数据的基本单位，通常作为一个整体进行考虑和处理。一个数据元素包含若干个数据项data item。

数据元素、数据项和数据的逻辑结构在计算机中的表示又称为结点、数据域和存储（物理）结构。

数据对象：性质相同的数据元素的集合，是数据的一个子集。

数据类型：一个值的集合及定义在这个值集上的一组操作的总称。

抽象数据类型 ADT(Abstract Data Type)：一个数学模型以及定义在此数学模型上的一组操作。

数据的逻辑结构：数据元素之间的逻辑关系。

线性结构：元素之间的关系是一对一的。表，栈，队列，串等
非线性结构
- 树型结构：元素之间的关系是一对多的。二叉树，Huffman树等
- 图状结构：元素之间的关系是多对多的。有向图，无向图等

数据的存储结构：数据在计算机中的存储表示。逻辑结构到物理存储的映射。

顺序存储：数组
非顺序存储：链式
索引存储：
散列存储：hash

算法和算法分析

算法 algorithm：算法是对特定问题求解步骤的一种描述，是指令的有限序列。也即解决问题的一种方法（策略）或一个过程。

程序：用计算机语言实现算法。

算法的五个特性：有穷性，可行性，确定性，输入和输出。

算法分析（设计）的要求：正确性 correctness，可读性 readability，健壮性 robustness，高效率与低存储

算法分析：

时间复杂度 time complexity：算法中各语句执行时间的总和。
空间复杂度 space complesity：算法中所需占用的==辅助==空间。

线性表

线性表逻辑结构

$(a_1,a_2,…,a_n)$ $n(n>=0)$ 个元素的有限集。每个元素的类型是相同的，元素之间的位置关系是一维(线性)的。

线性表存储结构

顺序存储——顺序表
链式存储——链表

线性表的操作

插入，删除，定位，查找，排序等

顺序表

线性表的顺序存储

注意：有容量和表长，容量是线性表的最多保存的数据元素的个数，表长是当前顺序表保存的数据元素个数。

链表

线性表的链式存储。

单向链表

头指针，尾指针，空指针，数据域，指针域，空表，带表头节点的单向链表

注意：头指针可能包含数据，也可能置空。类似于数组的第0位可能不用，也可能存数据

单向循环链表

只有尾指针，尾指针就是头指针

双向链表

两个指针域和一个数据域， prior data next

双向循环链表

栈和队列

栈和队列是特殊的线性表，是操作受限的线性表。

对于栈，所有的插入和删除操作都限制在线性表的同一端进行，是一种后进先出的线性表。

对于队列，所有的插入操作限制在线性表的一端进行，所有的删除操作限制在线性表的另一端进行，是一种先进先出的线性表。

栈是限定在一端（表尾）进行插入或删除操作的线性表。表尾端称栈顶，表头端称栈底

栈对应线性表的两种类型

顺序栈

栈满：top == MAXSIZE - 1

栈空：top == -1

链式栈

队列是限定在表的一端（队尾）进行插入，另一端（队头）进行删除的线性表。出队列的一端称队头，进队列的一端称队尾。

循环队列——顺序存储

1）解决假溢出问题。2）提高效率。

链式队列——非顺序存储

串

串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。

但是串的基本操作和线性表却有很大差别。在线性表的基本操作中，大多以“单个元素”作为操作对象。如：在线性表中查找某个元素、求取某个元素、在某个位置上插入一个元素和删除一个元素等；而在串的基本操作中，通常以“串的整体”作为操作对象，如：在串中查找某个子串、求取一个子串、在串的某个位置上插入一个子串以及删除一个子串等。

串的基本概念

串(string)也称字符串，是由零个或多个字符组成的有限序列。一般记为$S$ = “$a_1a_2…a_n$”。

$S$是串的名字
引号里面是串的内容
$a_i$是串的第$i$个字符
串中字符个数$n$为串长，$n=0$为空串

子串(substring)：一个串中任意个连续字符组成的子序列（含空串）称为该串的子串。

真字串：非空且不为自身的字串。

字符在串中的位置：

子串在主串中的位置：以子串的第一个字符在主串中出现的位置表示。

前缀：起始于位置1的字串

后缀：终止于位置n的字串

真前缀和真后缀：字符串本身之外的所有非空前缀和后缀，分别称为真前缀和真后缀。

串相等：当且仅当两个串的长度相等并且各个对应位置上的字符都相同时，这两个串才是相等的。

C标准函数库 #include \ C++ #include \

求串长 int strlen(char *s);
串复制 char* strcpy(char*s1,char*s2);
串拼接 char* strcat(char*s1,char*s2);
串比较 int strcmp(char*s1,char*s2;
定位 char* strchr(char*s, char c);
右定位 char* strrchr(char*s, char c);
求子串 char* strstr(const char*str1, const char*str2);

串的存储结构

行结构

定长顺序存储：按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区，通常用定长字符数组来实现。

#define MAXSTRLEN 1000		// 定义最长串长1000
typedef struct
{
    char string[MAXSTRLEN]; // 存放字符
    int length;				// 串的实际长度
}SqString;

注意：隐式存储：在串值后面加一个不计入串长的结東标记字符，如C语言中的"0"。此时串长为隐含值，不便于实现涉及串长的操作

堆结构

堆分配存储：仍以一组地址连续的存储单元存放串值，但存储空间是在程序执行过程中动态分配而得。

typedef struct
{
    char* data;		//若是非空串，则按串实际长度分配存储区，否则data为NULL
    int length;		//串长度
}HString;

块链存储

串采用链式存储结构存储时称为链串。链串中的一个结点可以存储多个字符。通常将链串中每个结点所存储的字符个数称为结点大小。

#define CHUNKSIZE 80	//可由用户定义的结点大小
typedef struct Chunk	//自定义结点（数据元素）
{
    char data[CHUNKSIZE];	//存放字符
    struct Chunk* next;		//指针域
}Chunk;
typedef struct
{
    Chunk *head, *tail;		//串的头指针和尾指针
    int length;				//串的当前长度
}LString;

模式匹配

模式匹配：子串在主串中的定位运算(index)。设S和T是给定的两个串，在主串S中查找子串T (T也称为模式串) 的过程称为模式匹配。

匹配结果

匹配成功：即在主串S中找到一个模式串T。T是S的子串，返回T在S中第一次出现的位置。
匹配不成功：即主串S中不存在模式串T。T不是S的子串，返回0

模式匹配的算法

朴素算法——BF(Brute- Force)算法
快速算法——KMP算法

BF算法

采用穷举策略，基本思想：

从主串S的第1个字符开始和模式串T的第1个字符进行比较
若相等，继续比较两者的后续字符；
若不等，从主串S的下ー字符开始和模式T的第一个字符进行比较
直到T中的每个字符依次和S中的一个连续的字符序列相等，则匹配成功，返回T在S中第一次出现的位置，否则匹配失败，返回0。

主串指针回溯，效率低。

BF算法的C/C++实现

// S：主串  T：模式串  sLen：S的长度  tLen：T的长度
int BF(char S[], char T[], int sLen, int tLen)
{
    int i = 0, j = 0;
    while(i < sLen && j < tLen)
    {
        if(S[i] == T[j]) { ++i; ++j; }
        else { i = i - j + 1; j = 0; }
    }
    if(j == tLen) return i - j;
    else return -1;
}

KMP算法

设计思想：

每当出现失配时，指针不回溯，而是利用已经得到的“部分匹配”结果将模式串向右“滑动”尽可能远的一段距离后，继续
比较。从而提高算法的效率。

示例：主串 $S=$ “$ababcabcacbab$” ，模式串$T=$ “$abcac$” 。

问题一：某趟在 $S_i$ 和 $T_j$ “失配”时，模式串”向右滑动”的可行距离有多远，即下一步 $S_i$ 应该与模式串中的哪个字符比较？

设模式串最远滑动到第 $k$ 个字符，此时要满足：（下面字符串下标从1开始，在程序中一般下标一般是0开始）

$T_1$ ~ $T_{k-1}$ $=$ $S_{i-k+1}$ ~ $S_{i-1}$ 和 $T_{j-k+1}$ ~ $T_{j-1}$ $=$ $S_{i-k+1}$ ~ $S_{i-1}$

联立得：$T_1$ ~ $T_{k-1}$ $=$ $T_{j-k+1}$ ~ $T_{j-1}$ $k=max\{k|1<k<j且T_1…T_{k-1}=T_{j-k+1}…T_{j-1}\}$

即：模式中的前$k-1$个字符（最大真前缀）与模式中$T_j$字符前面的$k-1$个字符（最大真后缀）相等时，模式$T$就可以向右”滑动”至使$T_k$和$S_i$对准，继续向右进行比较即可。

问题二：求$k$值?

1) $k$和$j$存在函数关系，模式串中的每一个$T_j$都对应一个$k$值，由当前失配位置$j$,可以计算出滑动位置$k$;

2) 滑动位置$k$仅与模式串$T$有关，因此可以预先为模式串设定一个next数组，若令next[j]=k,则next[j]表明当模式串中的第$j$个字符与主串中相应字符“失配”时，模式串中需要重新和主串中该字符进行比较的字符的位置。

$next[j]=\begin{cases} -1 \quad\quad\quad j=0 \\ max\{k|0<k<j且T_0...T_{k-1}=T_{j-k+1}...T_{j-1}\} \\ 0 \quad\quad\quad 其他情况 \end{cases}$

计算next[j]

next[0] = -1 ，第0个字符不等时，前面没有字符，$i$后移，$j$还是0
next[1] = 0，第1个字符不等时，前面只有第0个字符，$i$不变，$j$变1
next[j] = k，说明$T_0…T_{k-1}=T_{j-k+1}…T_{j-1}$，则next[j+1]有两种可能
- 1、$T_k = T_j$ ：next[j+1] = next[j] + 1 = k + 1
- 2、$T_k\neq T_j$：此时可以把求next函数值问题看成是一个模式匹配问题，整个模式串即是主串又是模式串。设$k’=next[k]$，将模式向右滑动，将$T_j$与$T_k’$进行比较。此时仍会出现两种情况
  - $T_k’ = T_j$ ：与情况①类似，$next[j+1]=k’+1$
  - $T_k’\neq T_j$：与情况②类似，重复②的过程，直到$T_j$与模式中某个字符匹配成功或者不存在可匹配的子串，则$next[j+1]=0$。

示例：模式$T =$ “$abaababc$”

sub	0	1	2	3	4	5	6	7
T	a	b	a	a	b	a	b	c
next	-1	0	0	1	1	2	3	2

求next的C/C++实现

// T是模式串，tLen是T的长度
void getnext(char T[], int next[], int tLen) 
{
	int j = 0, k = -1;
	next[0] = -1;
	while (j < tLen - 1)	// 第j个数决定j+1，所以tLen减1
	{
		if (k == -1 || T[j] == T[k]) {
			++k; ++j;
			next[j] = k;
		}
		else {
			k = next[k];
		}
	}
}

C++测试next

#include <iostream>
using namespace std;
int main()
{
	char T[] = "abaababc";  // -1 0 0 1 1 2 3 2
    // 计算T的大小，注意：动态数组无法用sizeof()计算大小
	int tLen = sizeof(T) / sizeof(char) - 1; // C风格字符串尾还有一个'\0'，所以长度是9不是8，要减1
	//int next[8] = { 0 };
	int* next = new int[tLen];
	getnext(T, next, tLen);	// 上面的next函数
	for (int i = 0; i < 8; ++i) {
		cout << next[i] << " ";
	}
	cout << endl;
	delete[] next;
	return 0;
}

KMP算法的C/C++实现

// S：主串  T：模式串  next：滑动到的字符下标  sLen：S的长度  tLen：T的长度
int KMP(char S[], char T[], int next[], int sLen, int tLen)
{
	int i = 0, j = 0;
	while (i < sLen && j < tLen)
	{
		if (j == -1 || S[i] == T[j]) {
			++i; ++j;
		}
		else {
			j = next[j];
		}
	}
	if (j == tLen) return i - j;
	else return -1;
}

C++测试KMP算法

#include <iostream>
using namespace std;
int main()
{
	char T[] = "abaababc";
	char S[] = "abacabaababcabc";
	int tLen = sizeof(T) / sizeof(char) - 1;
	int sLen = sizeof(S) / sizeof(char) - 1;
	int* next = new int[tLen];
	getnext(T, next, tLen);		// 前面的getnext函数
	int pos = KMP(S, T, next, sLen, tLen);	// 前面的KMP函数
	cout << pos << endl;
	delete[] next;
	return 0;
}

next函数的改进

如果next[j]=k且$T_k=T_j$，当 $S_i≠T_j$失配时，不需要再和$T_k$进行比较，而直接和$T_{next[k]}$进行比较，即应使next[j]=next[k]。

// T是模式串，tLen是T的长度
void getnext(char T[], int next[], int tLen) 
{
	int j = 0, k = -1;
	next[0] = -1;
	while (j < tLen - 1)
	{
		if (k == -1 || T[j] == T[k]) {
			++k; ++j;
            if(T[j] != T[k]) next[j] = k;
            else next[j] = next[k];
		}
		else {
			k = next[k];
		}
	}
}

数组

数组的定义

数组(Array)：是元素数量和元素类型固定的有序序列，可以将它看成是线性表的推广。

一维数组：是$n(n>1)$个相同类型数据元素构成的有限序列，其逻辑表示为 $A = (a_0,a_1,…,a_{n-1})$ 。

二维数组：可以看成是每个数据元素都是相同类型的一维数组的一维数组。

$A_{mn}\left[ \begin{matrix} a_{0,0} & a_{0,1} &\cdots & a_{0,n-1} \\ a_{1,0} & a_{1,1} &\cdots & a_{1,n-1} \\ \vdots &\vdots &\ddots &\vdots \\ a_{m-1,0} & a_{m-1,1} &\cdots & a_{m-1,n-1} \end{matrix} \right]$ $可以看成长度为m的线性表$ $B = (b_0,b_2,...b_{m-1}) \quad\quad 其中b_i = (a_{i,0},...a_{i,n-1})$

n维数组：可以看成是数据元素为$n-1$维数组的一维数组。

数组的顺序存储

数组的顺序存储：由于数组一般不做插入或刪除操作，因此，通常采用顺序存储结构，将数组的所有元素存储在一块地址连续的内存单元中。

一维数组的顺序存储：对于一维数组$A=(a_0,a_1,…a_{n-1})$可以直接按照元素顺序依次存储到一块地址连续的内存单元中。

数据元素存储位置计算公式：一旦$a_0$的存储地址$LOC(a_0)$确定，并假设每个数据元素占用$L$个存储单元，则任一数据元素$a_i$的存储地址$LOC(a_i)$就可由以下公式求出：$LOC(a_i)=LOC(a_0)+i*L \quad (0<=i<n)$
二维数组的顺序存储：对于一个$m$行$n$列的二维数组$A_{m,n}$,其存储方式有两种
- 行优先——以行序为主序的存储： $A=((\underbrace{a_{0,0},a_{0,1},...a_{0,n-1}}_{第0行}),(\underbrace{a_{1,0},a_{1,1},...a_{1,n-1}}_{第1行}),...,(\underbrace{a_{m-1,0},a_{m-1,1},...a_{m-1,n-1}}_{第m-1行}))$
  
  数据元素存储位置计算公式：$LOC(a_{i,j})=LOC(a_{0,0})+(in+j)L \quad (0<=i<m,0<=j<n)$
- 列优先——以列序为主序的存储 $A=((\underbrace{a_{0,0},a_{1,0},...a_{m-1,0}}_{第0列}),(\underbrace{a_{0,1},a_{1,1},...a_{m-1,1}}_{第1列}),...,(\underbrace{a_{0,n-1},a_{1,n-1},...a_{m-1,n-1}}_{第n-1行}))$
  
  数据元素存储位置计算公式：$LOC(a_{i,j})=LOC(a_{0,0})+(jm+i)L \quad (0<=i<m,0<=j<n)$

矩阵的压缩存储

矩阵的压缩存储：

为多个值相同的非零元只分配一个存储空间
对零元不分配空间

需压缩存储的两类矩阵：

特殊矩阵：值相同的元素或零元素在矩阵中的分布有一定规律。如：对称矩阵、三角矩阵、对角矩阵
稀疏矩阵：非零元较零元少，且分布没有一定规律。

特殊矩阵的压缩存储

对称矩阵：若一个$n$阶方阵$A$中的元素满足$a_{i,j}=a_{j,i}(0≤i,j<n)$,则称其为$n$阶对称矩阵。

压缩存储：以行序为主序存储下三角+主对角线的元素。

压缩地址计算公式：$a_{i,j} = B_k \quad k = i*(i+1)/2+j \quad (i<=j)$

三角矩阵：分为上三角矩阵和下三角矩阵。

上三角矩阵是指矩阵的下三角（不包括对角线）中的元素均为常数$c$或$0$的$n$阶方阵。
下三角矩阵是指矩阵的上三角（不包括对角线）中的元素均为常数$c$或$0$的$n$阶方阵。

下三角矩阵的压缩存储方法：以行序为主序存储下三角+主对角线的元素，最后用一个存储单元存储常数$c$,并
将压缩结果存储在一维数组$B$中。

压缩地址计算公式：$k=\begin{cases} i(i+1)/2+j & i<=j \\ n(n+1)/2 & i>j \quad常数c\end{cases}$

对角矩阵：若一个$n$阶方阵$A$满足其所有的非零元素集中在以主对角线为中心的带状区域中，则称其为$n$阶对角矩阵。其主对角线上、下方各有$b$条非零元素构成的次对角线，称$b$为矩阵半带宽，$(2b+1)$为矩阵的带宽。

三对角矩阵：当$b=1$时

压缩存储：以行序为主序将$A$带宽中的数据存入一维数组中。

压缩地址计算公式：$k=2*i+j$

稀疏矩阵的压缩存储

稀疏矩阵：假设在一个$m\times n$的矩阵中有$t$个非零元，令$δ=t/(m\times n)$,$δ$称为稀疏因子，通常认为$δ≤0.05$时该矩阵为稀疏矩阵。

压缩存储方法：只存储非零元素。稀疏矩阵中的每一个非零元素需由三元组$(i,j,a_{i,j})$唯一确定，所有非零元素（通常以行序为主序顺序排列）构成三元组线性表（筒称三元组表）。

稀疏矩阵可由表示非零元的三元组表以及其行列数来唯一确定。

三元组表的两种存储方法：顺序表表示法、十字链表表示法。

三元组顺序表存储表示

#define MAXSIZE1000
typedef int ElemType;
typedef struct {
    int i, j; 	// 第i行j列
    ElemType e;	// e:非0值
}Triple;	//三元组类型
typedef struct {
    Triple data[MAXSIZE + 1];
    int mu, nu, tu;	// mu行，nu列，tu个非0元
}TSMarix;	//稀疏矩阵

十字链表：每个非零元用一个结点表示，结点中除了表示非零元所在的行、列和值的三元组$(i,j,e)$外，增加两个指针域。行指针域(right)：用来指向本行中下一个非零元素；列指针域(down)：用来指向本列中下一个非零元素。稀疏矩阵中同一行的非零元通过向右的 right指针链接成了一个线性链表。同一列的非零元也通过down指针链接成了ー个线性链表。每个非零元既是第$i$行链表中的一个结点，又是第$j$列链表中的一个结点，相当于处在一个十字交叉路口，故称这样的存储结构为十字链表。

typedef struct OLNode {
    int i, j;	// 该非0元素的行和列下标
    ElemType e;	// 同上面的自定义，就是int型
    stuct OLNode *right, *down;	// 非0元素所在行表和列表的后继
}OLNode, *OLink;
typedef struct {
    OLink *rhead, *chead;	// 行和列链表头指针向量
    int mu, nu, tu;	// 稀疏矩阵的行数、列数、非0元个数
}CrossList;

示例：

广义表

广义表的基本概念

广义表(Generalized Lists)：广义表是线性表的推广，是$n$个数据元素$(a_1,a_2,…,a_i,…,a_n)$的有限序列，但不同的是，广义表中的$a$既可以是单个元素，还可以是一个广义表，通常记作：$LS=(a_1,a_2,…,a_i,…,a_n)$

LS是广义表的名字
$n$是广义表的长度，$n=0$时称为空表
若$a$是单个元素，则称$a$为广义表$LS$的原子(atom)，若$a$是一个广义表，则称$a$是广义表$LS$的子表(sublist)
为了区别原子和子表，通常用大写字母表示广义表的名称，用小写字母表示原子。

广义表的长度：广义表最外层包含的元素个数

广义表的深度：广义表中所含括号的重数

广义表的表头和表尾：当广义表非空时，即$LS=(a_1,a_2,…,a_n)$，第一个表元素$a_1$称为广义表的表头(head)，其余元素组成的表$(a_2,…,a_n)$称为广义表的表尾(tail)。

示例：

$A=(a,(b,c,(d)),d,(d))$：长度4，深度3，$head=(a)$，$tail=((b,c,(d)),d,(d))$
$B=()$：长度0，深度1，空表无表头表尾
$C=(e)$：长度1，深度1，$head=(e)$，$tail=()$
$E=(a,E)$：递归的表，长度2，深度无穷值，$head=()$，$tail=(E)$

广义表的存储结构

广义表的存储结构：由于广义表$(a_1,a_2,…,a_n)$是一种递归的数据结构，且其中的数据元素可以具有不同的结构(或是原子，或是列表)，因此难以用顺序存储结构表示，通常采用链式存储结构，每个数据元素可用一个结点表示，分别为表结点和原子结点。

链式存储方法：1）头尾链表表示法 2）扩展线性链表表示法

头尾链表表示法：

存储方法：任一非空列表可以分解为表头和表尾，反之，一对确定的表头和表尾可以唯一确定一个广义表。
原子结点：由标志域和值域组成。
表结点：由标志域、指示表头的指针域和指示表尾的指针域组成

$tag=0$，原子结点；$tag=1$，表/子表结点

typedef enum {ATOM, LIST} ElemTag;	// 0 原子 1 子表
typedef struct GLNode
{
    ElemTag tag;	// 标志域，公共部分，用于区分原子结点和表结点
    //union类似于enum。不同的是enum实质上是int类型的，而union可以用于所有类型
    union	// 原子结点和表结点的联合部分
    {
        AtomType atom;	//atom是原子结点的值域，AtomType由用户自定义
        struct{ struct GLNode *hp, *tp; }ptr;	// 表结点的表头和表尾指针域
    };
}*GList;	//广义表类型

除空表的表头指针为空外，任何非空广义表的表头指针均指向一个表结点，且其hp指向该表的表头，tp指向该表的表尾

扩展线性链表表示法：

表结点：由标志域、指示表头的指针域和指示下一元素的指针域组成。
原子结点：由标志域、值域和指示下一元素的指针域组成。

typedef enum {ATOM, LIST} ElemTag; // 0 原子  1 子表
typedef struct GLNode
{
    ElemTag tag;	// 标志域，分原子结点和表结点
    union		// 原子结点和表结点的联合部分
    {
        AtomType atom; //atom是原子结点的值域，AtomType由用户自定义
        struct GLNode *hp; // 表结点的表头指针
    }
    struct GLNode *tp;	//相当于线性链表的next,指向下一个元素结点
}*GList;

树

基本概念

树(Tree)是$n(n>=0)$个结点的有限集。

在任意一棵非空树中
(1)有且仅有一个根结点
(2)除根结点外，其余结点可分为$m(m>=0)$个互不相交的有限集$T_1,T_2,…,T_m$,其中每个集合本身又是一棵树，称为根的子树。

基本术语：

结点
- 父结点、子结点
- 兄弟、堂兄弟
- 分枝结点、叶子
结点的度：一个结点拥有子树的个数
树的度
祖先、子孙
层数
树的高度或深度
路径和路径长度
有序树与无序树

森林是$m(m>=0)$棵互不相交的树的集合。

存储结构

双亲数组存储表示

#define n0 30
#define dataType char
struct element {
    dataType data;
    int parent;
}
struct tree {
    struct element t[n0+1];
    int root;
}

孩子链表存储表示

#define n 30
#define dataType char
struct node {
    int sub;
    struct node* next;
}
struct element {
    dataType data;
    struct node* children;
}
struct tree {
    struct element t[n + 1];
    int root;
}

孩子——兄弟链存储表示

二叉树

二叉树分类

二叉树：由一个根结点和两棵互不相交的、分别称为这个根的左子树和右子树的二叉树组成。

满二叉树：有$2^k-1 \quad(k>0)$ 个结点的二叉树，即所有的叶子都在同一层。

完全二叉树：至多只有最下面的两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上

二叉树的性质

在二叉树的第$i(i>0)$层上至多有$2^{i-1}$个结点。
深度为$k$的二叉树中至多有$2^k-1$个结点$(k>0)$
对任何二叉树，若其终端结点数为$n0$，度数为2的结点数为$n2$，则$n0 = n2 + 1$。
有$n$个结点的完全二叉树的深度为 $d+1 \quad d为<=log_2n的最大整数$
对有$n$个结点的完全二叉树按层序从$1$开始编号，对任一结点$i$ $(1<=i<=n)$：
- $i=1$是根结点；$i>1$，父节点是$i/2$
- $2i<=n$，左孩子是$2i$
- $2i+1<=n$，左孩子是$2i$，右孩子是$2*i+1$

二叉树的存储

顺序存储
二叉链存储
- 静态二叉链
- 动态二叉链

顺序存储：用数组，按完全二叉树的顺序存储；对于一般的二叉树，在二叉树中补上虚拟结点使其成为完全二叉树。注意数组空出第0位。

二叉链存储：每个结点包括数据域和指针域。数据域存储结点的数据，指针域有两个分别指向左孩子和右孩子的指针。

typedef struct btnode
{
    dataType data;	// 用户定义的数据类型
    struct btnode *lchild, *rchild;
}BTnode, *BiTree;

静态二叉链

struct sbtnode
{
    dataType data;		//数值字段
    int llink, rlink;	//指针字段
}tree[n + 1];	// n：二叉树的结点个数，不能这样直接创建数组tree[n+1]

二叉树的遍历

二叉树的遍历：按某条搜索路径访问二叉树中每一个结点，使得每个结点被访问一次且仅被访问一次。

遍历方法：先序遍历、中序遍历、后序遍历、层次遍历。

先序遍历：根——>左子树——>右子树

中序遍历：左子树——>根——>右子树

后序遍历：左子树——>右子树——>根

层次遍历：按层次，每层从左到右遍历

示例：

注：已知二叉树的先序遍历和中序遍历，则该二叉树能唯一确定

遍历算法实现

层次遍历伪代码

void levelOrder(BiTree* T)
{
    initqueue(q);	// 创建一个空队列
    enqueue(q, T);		// T入队
    while(!empty(q))
    {
        dequeue(q, T);	// q的队首结点出队给T
     	visite(T->data);	//访问结点T;
        if(T->lchild) enqueue(q, T->lchild); //如果T存在左孩子，左孩子入队
        if(T->rchild) enqueue(q, T->rchild); //如果T存在右孩子，右孩子入队
    }
}

递归实现

先序遍历递归伪代码

void preOrder(BiTree* T)
{
    // 先序遍历以T为根的二叉树
    if(T != NULL) {
        visite(T->data);		//访问根结点
        preOrder(T->lchild);	//先序遍历左子树
        preOrder(T->rchild);	//先序遍历右子树
    }
}

中序遍历递归伪代码

void inOrder(BiTree* T)
{
    // 中序遍历以T为根的二叉树
    if(T) {
        inOrder(T->lchild);	//中序遍历左子树
        visite(T->data);	//访问根节点
        inOrder(T->rchild);	//中序遍历右子树
    }
}

后序遍历递归伪代码

void postOrder(BiTree* T)
{
    // 后序遍历以T为根的二叉树
    if(T) {
        postOrder(T->lchild);	//后序遍历左子树
        postOrder(T->rchild);	//后序遍历右子树
        visite(T->data);		//访问根节点
    }
}

非递归实现

先序遍历的非递归伪代码

void preOrder(BiTree* T)
{
    initstack(s);	// 创建一个空栈s
    while(T || !empty(s))
    {
        if(T) {	// 若T不空，访问T
        	visite(T->data);	//访问根结点
            push(s, T);			//T入栈
            T = T->lchild;		//沿左子树遍历
    	}
        else {
            pop(s, T);			//栈顶元素出栈给T
            T = T->rchild;		//沿右子树遍历
        }
    }
}

中序遍历的非递归伪代码

void inOrder(BiTree* T)
{
    initstack(s);	// 创建一个空栈s
    while(T || !empty(s))
    {
        if(T) { 	// 若T不空，T入栈，出栈的时候访问
            push(s,T);	
            T = T->lchild;	//沿左子树遍历
        }
        else {
            pop(s, T);		//栈顶元素出栈给T
            visite(T->data);
            T = T->rchild;	//沿右子树遍历
        }
    }
}

后序遍历的非递归伪代码

void postOrder(BiTree* T)
{
    initstack(s);
    initstack(tag);	// 存放0和1，用于判断是否读取s出栈结点的data，1表示从左子树回退，0表示从右子树回退
    while(T || !empty(s))
    {
        while(T) {
            push(s, T);
            push(tag, LEFT);	//LEFT是1
            T = T->lchild;
        }
        pop(s, T);				//将s中的栈顶结点弹给T
        pop(tag, flag);			//将T对应的标识弹出
        if(flag == LEFT) {		//如果从左子树回来
            push(tag, RIGHT);	//标识改为右子树入栈
            push(s, T);			//T也入栈
            T = T->rchild;		//T指向右孩子
        }
        else {					//如果从右子树回来
            visite(T->data);	//读取数据
            T = NULL;			// T值空，继续弹栈
        }
    }
}

线索二叉树

遍历二叉树是按一定的规则将二叉树中结点排列成一个线性序列；这实际上是把一个非线性结构进行线性化的操作。

线索二叉树也是一种用来表示二叉树的二叉链表。在这种二叉链表中，每个结点的空的左孩子指针域中放入了在某种遍历次序下该结点的前驱结点的地址；每个结点的空的右孩子指针域中放入了在这种遍历次序下该结点的后继结点的地址。这种附加的指针值称为线索。给二叉树的二叉链表存储结构加上线索的过程称为线索化二叉树。这个过程可通过对二叉树进行相应次序的遍历来实现。根据遍历方法的不同，线索二叉树一般分前序线索二叉树、中序线索二叉树和后序线索二叉树三种。

struct ThrTreeNode {
   	// 线索二叉树中每个结点的结构 
   	TElemType data;
   	ThrTreeNode *lchild,*rchild;
    int ltag, rtag;
};

先序线索二叉树和先序线索二叉树链 （先序遍历序列：$abcdfge$）

前驱和后继是按先序的规则来确定的，如图中的$g$前驱指向$f$，后继指向$e$，对应顺序$gfe$

以上结构构成的二叉链表作为二叉树的存储结构，叫做线索二叉链
指向结点前驱或后继的指针叫做线索
加上线索的二叉树叫线索二叉树
对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化

中序线索二叉树（中序遍历序列：DGBAEHCF）

前驱和后继是按中序的规则来确定的，如图中的$H$前驱指向$E$，后继指向$C$，对应顺序$EHC$

先序遍历伪代码

void preOrder(struct ThrTreeNode* p)
{
    // 先序遍历以p为根的线索二叉树
    while(p != NULL)
    {
        visite(p->data);	//访问根结点
        p = p->lchild;		//p指向左孩子或前驱结点
    }
}

中序遍历伪代码

void inOrder(struct ThrTreeNode* p)
{
    // 中序遍历以p为根的线索二叉树
    while(p->ltag == 0) p = p->lchild;	//从根开始找到一个无前驱的结点p
    while(p != NULL) {
     	visite(p->data);	// 访问根结点
        p = p->rchild;		// p指向右孩子或后继结点
    }
}

静态线索二叉链：$+$：左、右孩子；$-$：前驱、后继线索

Huffman树

二叉树的带权路径长度：$WPL=\sum_{k=1}^nw_kl_k$ ，其中:

$n$：树叶结点的个
$w_k$：第$k$个结点的权
$l_k$：第$k$个叶子到根的路径长度

Huffman树是一个带权路径长度最小的二叉树，又称最优二叉树。构建方法：

将$\{w_1,w_2,…,w_n\}$看成$n$个二叉树
选择2个根结点最小的二叉树，构造新的二叉树，重复至剩1个树

例：$Z:2,K:7,M:24,C:32,U:37,D:42,L:42,E:120$

静态三叉链：

#define n 5
struct htnode {
    float weight;
    int llink, rlink, plink; // 左孩子 右孩子 双亲
};

Huffman编码

Huffman编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%~90%之间。Huffman编码算法用字符在文件中出现的频率表来建立一个用0,1串表示各字符的最优表示方式。给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。

前缀码：对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其它字符代码的前缀，这种编码称为前缀码。

二叉树C的Huffman编码是：$E:0,U:100,D:101,L:110,C:1110,Z:111100,K:111101,F:11111$

树、森林转换二叉树

树转换成二叉树

森林转换成二叉树

树A的先序遍历：oabcdfeg 对应二叉树B的先序遍历：oabcdfeg

树A的后序遍历：bafdecgo 对应二叉树B的中序遍历：bafdecgo

图

基本概念

图(Graph)是一种较线性结构和树更为复杂的数据结构。对于图来说，图中任意两个结点之间都可以直接相关。

图是一个二元组，$G=(V,E)$。其中， $V$：顶点的有限集, $E$：关系(边)的有限集。

例：

无向图 $G1=(V,E)\quad V＝\{v_1, v_2, v_3, v_4, v_5\}\quad E＝\{(v_1,v_2), (v_1,v_4), (v_2,v_3), (v_2,v_5), (v_3,v_4), (v_3,v_5)\}$

有向图 $G2=(V,E)\quad V＝\{v_1, v_2, v_3, v_4\}\quad E＝\{, , , \}$

图是一种网状的数据结构，其中的结点之间的关系是任意的，即图中任何两个结点之间都可能直接相关。

顶点：图中的数据元素

边：两个顶点之间的关系。

对于无向图，图中的顶点偶对（边）是无序的
而对于有向图，图中的顶点偶对（弧）是有序的

完全图：有$n(n-1)/2$条边的无向图，即每个结点之间都有且只有一条边。

有向完全图：有$n(n-1)$条边的有向图。

稠密图：有很少的边或弧的图。

稀疏图：有很多的边或弧的图。

权：与图的边相关的数值。

网：带权的图。

子图：设两个图$G＝(V, E)$和$G’=(V’,E’)$，如果$V’\subseteq V$且$E’\subseteq E$，则称$G’$为$G$的子图。

邻接点：

对于无向图$G＝(V,E)$，若存在顶点对$(x,y)\in E$，则称顶点$x$和$y$互为邻接顶点。即$x$和$y$相邻接（相关联）。
对于有向图$G＝(V,E)$，若存在顶点对$\in E$，则称顶点$x$邻接到顶点$y$，顶点$y$邻接于到顶点$x$。

顶点的度：

在无向图中，和该顶点相关联的边的数目称为顶点的度。
在有向图中，若$$是一条弧，以$x$为尾的弧的数目称为顶点$x$的出度；以$x$为头的弧的数目称为顶点$x$
的入度。顶点的度等于该顶点的入度与出度之和。

路径：在图$G＝( V, E )$中, 若从顶点 $x$ 出发，经过一些顶点 $v_1, v_2, … , v_m$ 到达顶点$y$。则称顶点序列 $(x,v_1,v_2, … ,V_m, y)$ 为从顶点 $x$ 到顶点 $y$ 的路径。

路径长度：

非带权图的路径长度是指此路径上边的条数。
带权图的路径长度是指路径上各边的权之和。

简单路径：序列中顶点不重复出现的路径。

回路(环)：第一个顶点和最后一个顶点相同的路径。

简单回路(环)：除第一个和最后一个顶点，其余顶点不重复出现的路径。

连通：在无向图中，如果从$x$到$y$存在路径，则称$x$和$y$是连通的。

连通图：无向图$G$中如果任意两个顶点$x,y$之间都是连通的，则称图$G$是连通图。

强连通图：有向图$G$中任意两个顶点$x,y$之间都是相互可达的。称图$G$是强连通图。

连通分量：无向图中的极大连通子图（即把原图中任意一个不在子图中顶点加进去，子图从连通变为不连通，则为极大连通子图）。

强连通分量：有向图中的极大连通子图。

树图：极小连通子图（无环图），在$n$个顶点的情形下，有$n-1$条边。

存储结构

数组表示法（邻接矩阵）

图需要存储的信息：顶点和边。

邻接矩阵：表示顶点之间相邻关系的矩阵。$a_{ij}=\begin{cases}1\quad \in E \\ 0\quad others \end{cases}$

网的邻接矩阵：$A[i][j]=\begin{cases}W_{i,j}\quad \in E \\ 0\quad i=j \\ \infty \quad others \end{cases}$

邻接矩阵的特点：

无向图的邻接矩阵一定是一个对称矩阵。
无向图的邻接矩阵的第$i$行（或第$i$列）非零元素（或非$\infty$元素）个数为第$i$个顶点的度$D(v_i)$。
有向图的邻接矩阵的第$i$行非零元素（或非$\infty$元素）个数为第$i$个顶点的出度$OD(v_i)$，第$i$列非零元素（或非$\infty$元素）个数就是第$i$个顶点的入度$ID(v_i)$。

邻接表（邻接链表）

#define n 100
struct arcnode {
    int info;
    int vertex;
    struct arcnode* nextarc;
};
struct node {
    int degree;
    struct acrnode* firstarc;
};

图的遍历

图的遍历：从图中某一顶点出发访遍图中其余结点，使每一个结点被访问且仅被访问一次。

图的遍历通常有两种方法：深度优先搜索和广度优先搜索。它们对有向图和无向图都适用。

深度优先搜索(Depth First Search)

类似于树的先根遍历，是树的先根遍历的推广。

  从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图,   直至所有与v有通路的顶点都被访问到；若此时图中还有顶点未被访问到，则另选图中未被访问的顶点作起点，重复上述过程，直到图中所有顶点都被访问到为止。

void dfs(graph g, vtxptr v0)
{
    //从v0出发深度优先遍历图g,
    // g是连通图 或 非连通图中的一个连通分量访问v0;
    w = v0的第一个连接点;
    while(当邻接点w存在时) {
        if(w未访) dfs(g, w);
        w = 下一邻接点;
    }
}

广度优先搜索(Breadth First Search)

类似于树的层次遍历。

  从图中某个顶点v出发，在访问了v之后，依次访问v的各个未曾访问过的邻接点(并保证先被访问的顶点的邻接点“要先于”后被访问的顶点的邻接点被访问),     直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中还有未被访问的顶点，则任选其中之一作为起点，重新开始上述过程，直至图中所有顶点都被访问到。

void bfs(graph g, vtxptr v0)
{
    //从v0出发广度优先遍历图g（g是连通图或连通分量）
    visite(v0); mark[v0] = 1;
    initqueue(Q);
    enqueue(Q, v0); // v0进队列Q
    while(!empty(Q)) {
        dequeue(Q, v);
        w = v的第一个邻接点;
        while(w存在) {
            if(w未访) {
            	visite(w); mark[w] = 1; enqueue(Q, w);
                w = 下一邻接点;
            }
        }
    }
}

最小生成树

生成树：按深度遍历得到的生成树称为深度优先生成树；按广度遍历得到的生成树称为广度优先生成树。

连通图或有根有向图可以生成树。

有根的图：存在一个顶点X,从该顶点出发可以沿着有向路径到达图中其余各顶点的有向图。顶点X为图的根。

生成树林：从非连通图中任意一个顶点出发，或者从非强连通图中任意一个非根顶点出发，都不可能沿着边
访问到图中的所有顶点。

最小生成树：生成树中边的权值（代价）之和最小的树。

Kruscal算法

基本思想：设$T=(U,TE)$是$G=(V,E)$的最小生成树，$U$的初值等于$V$，$TE$的初值为空集。将图中的边按权值从小到大的顺序依次选取，若选取的边使生成树$T$不形成回路，则把它并入$TE$中，保留作为$T$的一条边；若选取的边使生成树T形成回路，则将其舍去。如此进行下去，直到$TE$中包含有$n-1$条边为止。

T = {V, E};
while(T的边数 < n - 1) {
    在E中选择代价最小的边(u, v);
    并置 E = E - (u, v);
    if(不构成回路) {
        T = T + {u, v};
    }
}

prim算法

从某一顶点开始，找$n-1$条不构成回路的最小边（顶点偶对）。

void minispantree_prim(graph g, int u) 
{
    // 从u出发构造网g的最小生成树
	for(v = 1; v <= vtxnum; v++) { // 初始化
        if(v != u) {
            closedge[v].vex = u;
            closedge[v].lowcost = g[u][v];
        }
    }
    for(i = 1; i <= vtxnum - 1; ++i) { 
        k=最小边所在下标位置;输出生成树的边;
        closedge[k].lowcost = 0; ////顶点k并入U集
        for(v = 1 ; v <= vtxnum; ++v) {
    		if(g[k][v] < closedge[v].lowcost) { // 选择具有最小代价的边
   				closedge[v].lowcost=g[k][v]; 
                closedge[v].vex=k;  
            } 
        }
    }
}

拓扑排序

用顶点边表示活动的网络，简称AOV网络(Activity On Vertices)

顶点：一个工程中的活动(Activity)

边：活动的顶点间的优先关系(Relation)

可以用有向图表示一个工程。在这种有向图中，用顶点表示活动。有向边$$表示：$V_i$必须先于活动$V_j$进行。这种有向图叫做顶点表示活动的AOV网络(Activity On Vertices)

在AOV网络中，如果活动$V_i$，必须在活动$V_j$，之前进行，则存在有向边$$，AOV网络中不能出现有向回路，即有向环。在AOV网络中如果出现了有向环，则意味着某项活动应以自己作为先决条件。因此，对给定的AOV网络，必须先判断它是否存在有向环。

将各个顶点（代表各个活动）排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系
都能得到满足——拓扑序列。

这种构造AOV网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。

存储结构（邻接表）：

typedef struct arcnode {
    int adjvex;
    arcnode *nextarc;
}* pointer;	// 表结点
struct node {
    char vexdata;
    int id; // 顶点的入度
    pointer firstarc;
}dig[100];	//一组头结点

拓扑排序的方法：

首先建立(n个顶点的)AOV网。

1、在AOV网络中选一个没有直接前驱的项点（入度为0的顶点），并输出之；

2、从图中删去该顶点，同时删去所有它发出的边；

重复(1)和(2)，直到全部顶点均已输出，

拓扑有序序列形成，拓扑排序完成：

若图中还有未输出的顶点，但已跳出处理循环。这说明图中存在环

关键路径

用边表示活动的网络，简称 AOE网络 (Activity On Edges)

边：一个工程中的活动(Activity)

边上权值：活动持续时间(Duration)

顶点：事件 (Event)

完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径(Critical Path)。

1）先求所有事件的$Ve$ $\quad$ 2）通过$Ve$反向求所有事件$Vl$

事件$V_j$的最早可能开始时间$Ve[j]$——从源点$V1$ 到顶点$V_j$的最长路径长度。

$Ve(1)=0$
$Ve(j)=max\{Ve(i)+的权\} $

事件$V_i$ 的最迟允许开始时间$Vl[i]$ ——在保证汇点$Vn$ 在$Ve[n]$时刻完成的前提下，事件$V_i$的允许的最迟开始时间。

$Vl(n)=Ve(n)$
$Vl(i)=min\{Vl(j)-的权\}$

最短路径

最短路径问题：如果从图中某一顶点(称为源点)到达另一顶点（称为终点）的路径可能不止一条，如何找到一条路径使得
沿此路径上各边上的权值总和达到最小。

解法：

单源最短路径问题——Dijkstra算法
所有顶点之间的最短路径——Floyd算法

Dijkstra算法

单源最短路径问题：给定一个带权有向图D与源点v，求从v到D中其它顶点的最短路径（限定各边上的权值大于或等于0）。

按路径长度的递增次序，逐步产生最短路径。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点v到其它各顶点的最短路径全部求出为止。

引入一个辅助数组$dist$。它的每一个分量$dist[i]$表示当前找到的从源点$v_0$到终点$v_i$的最短路径的长度。初始状态：
- 若从源点$v_0$到顶点$v_i$有边，则$dist[i]$为该边上的权值
- 若从源点$v_0$到顶点$v_i$没有边，则$dist[i]$为$+\infty$
假设 $S$ 是已求得的最短路径的终点的集合。
首先，在 $dist$ 数组中求最小值$v_k(v_k\in V-S)$ ，将$v_k$加入集合 $S$
然后，对所有的$v_i\in V-S$，修改其$dist[i]$值（$v_0->v_i$短，还是$v_0->v_k->v_i$更短）
重复上述过程

void Dijkstra(int n, int v)
{
	//a[i][j]:(vi,vj)的权，dist[j]:当前求到的从顶点v 到顶点j的最短路径长度, 
	//同时用数组path[j]:存放求到的最短路径, 0 <= j < n
    for(i = 0; i < n; ++i) {
        dist[i] = a[v][i];	// dist数组初始化
        S[i] = 0;
        if(i != v && dist[i] < MAXNUM) path[i] = v;
        else path[i] = -1;	//path数组初始化
    }
    S[v] = 1; 	// 顶点v加入顶点集合
    dist[v] = 0;
    for ( i = 0; i < n-1; i++ ) {			
		u = 当前不在集合S中且具有最短路径的顶点;
		S[u] = 1;  //将顶点u加入集合S
        for (int w = 0; w < n; w++)  {  //修改 
			if ( !S[w] && a[u][w] < MAXNUM && dist[u] + a[u][w] < dist[w] ) {
				dist[w] = dist[u] + a[u][w]; 
				path[w] = u;
            } 
      	}
	} 
}

Floyd算法

所有顶点之间的最短路径：对每一对顶点$v_i\neq v_j$，要求求出$v_i$与$v_j$之间的最短路径和最短路径长度。

Floyd算法的基本思想：

定义一个$n$阶方阵序列：$A^{(0)},A^{(1)},…,A^{(n)}$

其中 $A^{(0)}[i][j] = a[i][j] \\ A^{(k)}[i][j] = min\{A^{(k-1)}[i][j],A^{(k-1)}[i][k] + A^{(k-1)}[k][j]\} \quad k = 1,2,…, n $

$A^{(k)}[i][j]$是从顶点$v_i$到$v_j$，中间顶点的序号不大于$k$的最短路径的长度，$A^{(n)}[i][j]$是从顶点$v_i$到$v_j$的最短路径长度。

//伪代码
void floyd() 
{
    for(i = 1, i <= n; ++i) {	//矩阵a与path初始化
        for(j = 1; j <= n; ++j) {
            if(i != j && a[i][j] < MAXINT) {
                path[i][j] = i;	// i到j有路径
            }
            else {
                path[i][j] = 0;	// i到j无路径
            }
        }
    }
    for(k = 1; k <= n; ++k) { //产生a(k)及path(k)
        for(i = 1; i <= n; ++i) {
            for(j = 1; j <= n; ++j) {
				if ( a[i][k] + a[k][j] < a[i][j] ) { 
					a[i][j] = a[i][k] + a[k][j];
		  			path[i][j] = k;
                }   //缩短路径长度(i-- k -- j )
            }
        }
    }
}

查找

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

关键字：记录中某一数据项的值。

主关键字：能唯一确定一个元素的关键字（如学号、商品号）。

查找：根据给定的关键字，在查找表中确定一个其关键字等于给定值的数据元素（记录）的过程

平均查找长度(ASL)：查找一个结点所作的平均比较次数（ASL是衡量一个查找算法优劣的主要标准）

静态表的查找

静态表——以顺序结构存储的表(顺序表)

在表上所作的操作—— 查询某个数据元素是否在查找表中

顺序查找

算法思想：

从表的一端开始，用给定值k与表中各个结点的关键字逐个比较。
- 查找成功——找出相等的值；
- 查找失败——已到达表的另一端，即表中所有结点的关键字值都不等于k。
可在此设置一个监视哨，作为下标越界的条件

监视哨的作用：作为越界（即已查完）的检测条件省去在循环中每次均要判定是否越界，从而节省比较的时间。

typedef struct {
    keytype key;
    datatype info;
}sstable;
int search(elemtype r[], int n, keytype k) 
{
    //在n个结点的顺序表r[1]..r[n]中查找关键字 k
	int i = n; // 从表尾开始向前查找
    r[0].key = k;	//设置监视哨
    while(r[i].key != k) i--;
    return i;
    //若r[i].key==k , 则返回i （i≠0） , 否则返回0(未找到）
}

算法分析

查找成功的平均查找长度（在等概率的前提下）$ASL=(1+2+……+n)/n =(n+1)/2$
查找失败的平均查找长度 $n+1$

二分(折半)查找

二分查找的先决条件：表中结点按关键字有序，且顺序（一维数组）存储。

二分法思想：取中，比较

求有序表的中间位置$mid$，若$r[mid].key==k$，查找成功；
若$r[mid].key>k$，在左子表中继续进行二分查找；
若$r[mid].key<k$，则在右子表中继续进行二分查找。

int Search_bin(elemtype r[], int n, keytype k)
{
    //  r[1]..r[n] 是按key排序的n个元素，在表中查找 k
    i = 1; j = n;
    while(i <= j) {
        mid = (i + j) / 2;
        if(k == r[mid].key) return mid;	//查找成功
        else if(k < r[mid].key) j = mid - 1;	//在左半部分继续查找
        else i = mid + 1;	//在右半部分继续查找
    }
    return 0;	//k不在该有序表中
}

二分查找判定树

折半查找算法的执行时间为$O(log_2n)$，比顺序查找速度快。

与顺序查找方法相比，折半查找方法的缺点是需要对n个元素预先进行排序，而且只能用顺序方法存储这些元素。

索引顺序表的查找

分块查找，又称索引顺序查找。它是顺序查找的一种改进。在此查找方法中，需要建立一个“索引表”。

查找方法：先确定待查记录所在的块（子表）；然后在块中顺序查找。

静态树表的查找

建立静态树表：

动态表的查找

动态表的查找，也即树表的查找。一种以树的形式来组织查找表的方法，以实现动态高效率的查找

二叉排序树 BST: Binary Sort(Seachar) Tree
平衡二叉树
B-树
B+树

二叉排序树BST

二叉排序树（Binary Sort Tree）又称二叉查找树（Binary Search Tree）

二叉排序树或空，或满足如下性质：

有一个根，若根的左子树非空，则左子树上所有结点的关键字值均小于根结点的值。若根的右子树非空，则右子树上的所有结点的关键字值均大于根结点的值。
左右子树同样是二叉排序树。

二叉排序树的特点

中序遍历得一有（升）序序列

查找方法

若根结点的关键字值等于查找的关键字，查找成功。
若小于根结点的关键字值，查其左子树。
若大于根结点的关键字的值，则查其右子树。
在左右子树上的操作类似。

结点结构：

struct bnode {
    keytype key;
    datatype data;
    struct bnode *lchild;
    struct bnode *rchild;
};
typedef struct bnode bstnode;

算法伪代码：

bstnode *bstsearch(bstnode *t, keytype k)
{
    //  t:指向根结点, k:待查找关键字
    if(t == NULL || t->key == K) return t;
    else if(t->key > k) return bstsearch(t->lchild, k); // 在左子树上查找
    else return bstsearch(t->rchild, k); // 在右子树上查找
}

二叉排序树的插入

若二叉树为空。则生成根结点。
若二叉树非空
- 首先找到被插结点的父结点。
- 判断被插结点是其父结点的左、右儿子，将其作为叶子结点插入。

二叉排序树的删除

删除叶子结点：直接删除。如删除24
删除子树的根结点：若被删结点的左儿子为空或者右儿子为空。如删除100
删除子树的根结点且被删结点的左子树和右子树均不空。如删除12
一般情况

平衡二叉树AVL

平衡二叉树(Balanced Binary Tree)又称AVL树。它或是空树，或是具有下列性质的二叉排序树。

它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。

平衡因子(Balance Factor)

左子树的深度 - 右子树的深度
即平衡二叉树中每一结点的平衡因子为：0，1，-1。

平衡二叉树的查找

与二叉排序树查找方法相同。

平衡二叉树的插入

找插入位置并插入结点
若插入后导致不平衡，则进行调整

平衡旋转

LL旋转（LL：表示新插入的结点在危机结点的左子树的左子树上）
LR旋转（LR：表示新插入的结点在为危机结点的左子树的右子树上）
RR旋转（RR：表示新插入的结点在为危机结点的右子树的右子树上）
RL旋转（RL：表示新插入的结点在为危机结点的右子树的左子树上）

B-树

$m$阶B-树或空，或满足

树中每个结点最多有$m$个子树；
若根结点不是叶子结点，则至少有2个子树；
除根结点外的所有非叶子结点至少有ceil((double)m/2) 个子树，ceil是向上取整，如：4阶则至少2个，5阶至少3个
所有的非叶子结点中包含的数据信息为：$(n,A0,K1,R1,A1,K2,R2,A2, ………,Kn,Rn,An,parent)$，其中
- $n$：关键字的个数
- $Ki$：关键字
- $Ai$：$> Ki$ 且 $< Ki+1$ 的结点地址（A0： <K1 的结点的地址）
- $Ri$：关键字 $= Ki$ 的数据记录在硬盘中的地址 $K1 <=K2 <= …… <= Kn$,
- $Parent$：父结点的地址，这个可以没有
所有的叶子结点都出现在同一层上，且不带信息

B-树是一个$m$叉平衡排序树

B-树的查找

类似于二叉树的查找

B-树查找算法伪代码

result srch_mbtree(mblink t; keytype k) //在B-树中查找k
{
	p=t; q=NULL; i=0;  //初始化
    while(p) {
        i = Search(p, k);
        //在p->key[1...n]中查找
        //直至p->key[i] <= k < p->key[i+1] 止, 0<=i<=n
		if( i > 0 && p->key[i] = k ) return (p, i, 1);	//查找成功
        else { q = p; p = p->ptr[i]; }
    }
    return (q, i, 0);	//查找不成功，返回插入位置信息
}

B-树的插入

问题：若插入一元素时，使得某一结点>m叉？例如插入60

解决方法：分裂！将一个结点分成两个结点

B-树的删除

B+树

B+树是 B-树的变形树。

m 阶 B+树与m阶B-树的差异在于：

有n个子树的结点中含有n个关键字
所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接
所有的非终端结点可以看成是索引部分，结点中仅含有其子树（根结点）中的最大（或最小）关键字。

B+树的查找

B+树的插入

B+树的删除

hash(散列)查找

hash表：根据设定的散列函数和相应解决冲突的方法为一组结点建立的一张表，表中的结点的存储位置依赖于设定的散列函数和处理冲突的方法。

hash（又称散列、杂凑）的基本思想：以结点的关键值$k$为自变量，通过一定的函数关系 $h$ 计算出对应的函数值 $h(k)$，把这个值解释为结点的存储地址（散列地址），将结点存入该地址中去。

设计1个hash函数，计算 Hash函数，其函数值恰好是 key 在 hash 表中的地址 $hash(key)=i (0..m-1)$

冲突

若对于不同的键值$k1$和$k2$，且$k1\neq k2$，但$h(k1)=h(k2)$，即具有相同的散列地址，这种现象称为冲突。称 $k1$、$k2$称为同义词

例：$key=\{3,15,20,24\}$，$m=5$（表长），$hash(k)=k%5$
则：$hash(15)=hash(20)=0$ 产生冲突。

表长m的选取

参考：$n / m≈ 3 / 4$

m: hash表的表长
n: hash表中关键字个数

装填（负载）因子

$\alpha=表中填入的记录数\div hash表的长度$

构造hash函数

构造hash函数需要考虑的因素

计算hash函数的效率；
关键字的长度（包括是否等长）；
hash表的大小；
关键字的公布情况；
记录的查找频率。

1、直接定址法

哈希函数为关键字的线性函数。$H(key) = key$ 或者 $H(key) = a\times key+b$

仅限于：地址集合的大小 = 关键字集合的大小。如：$H(key)=key-1949$

2、数字分析法

假设关键字集合中的每个关键字都是由$s$位数字组成$(k1, k2, …, kn)$，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。

仅限于：能预先估计出全体关键字的每一位上各种数字出现的频度。

3、平方取中法

若关键字的每一位都有某些数字重复出现频度很高的现象，则先求关键字的平方值，以通过“平方”扩大差别，同时平方值的中间几位受到整个关键字中各位的影响。

例如：$a=0100$, 则 $a^2=0010000$
$i =1100$, 则 $i^2 =1210000$
$j =1200$, 则 $j^2 =1440000$

若超出范围时，可再取模

问题：在数字分析法和平方取中法，取哪几位作为hash地址？“中间几位”由表长决定。如表长为1000,Hash表的地址空间为000-999，所以取中间3位。

4、折叠法

若关键字的位数比较长，则可将其分割成几部分，然后取它们的叠加和为哈希地址。

两种处理方法：移位叠加和间界叠加

5、除留余数法

选择一个适当的正整数 $p$，用$p$去除关键值，取其余数作为散列地址，即：$hash(key)=key%p$ $p≤m(表长)$

$p$ 应为不大于$m$ 的最大质数

例：设表长 $m=8，16，32，64，128，1001$
则 $p=7，13，31，61，127，1001$

6、随机数法

$H(key) = Random(key)$

采用何种构造哈希函数的方法取决于关键字集合的情况(包括关键字的范围和形)，总的原则是使产生冲突的可能性降到尽可能
的小。

冲突处理

1、链地址法

将具有相同散列地址的记录都存储在同一个线性链表中。

例：以$\{14,1,68,27,55,23,11,10,19,20,79,84\}$构造hash表。
分析： $n=12\quad n/m=3/4$ , 所以 $m=16$ , 则 $p=13 \quad hash(key)=key % 13$

2、开放定址法

当冲突发生时，使用某种方法在散列表中形成一个探查序列，沿着此序列逐个地址去探查，直到找到一个开放的地址（空位置），将发生冲突的键值放到该地址中。$H_i=(H(key)+d_i)%m$

线性探查法 $d_i = 1,2,3,…,m-1$
二次探查法 $d_i=1^2,-1^2,2^2,-2^2,…,k^2,-k^2$
伪随机探测法 $d_i = 伪随机数序列$
再散列探测法

2.1 线性探测法

对给定的关键值 $k$，若地址$d$ (即$h(k)=d$)的单元发生冲突，则依次探查下述地址单元（设$m$为表长）：$d+1,d+2,…,m-1, 0 ,1,…d-1$

设增量函数为$d(i)=1,2,3,……m-1$ （$i$: 为探测次数）

2.2 二次探测法

对给定的关键值 $k$，若地址$d$ (即$h(k)=d$)的单元发生冲突，则探查下述地址单元：$d+1,d-1,d+4,d-4,d+9,d-9,…$

设增量函数为 $d(i)=1^2,-1^2,2^2,-2^2,……,k^2,-k^2\quad (k<=m/2)$

2.3 伪随机探测法

2.4 再散列探测法

设$m$为表长，当 $h1(k1)=h2(k2)=d$ 时，

使探查序列为： $(d+h2(k))%m \\ (d+2h2(k))%m \\ (d+3h2(k))%m \\ …… $

$h2$的选取方法为：

若$m$为素数：$h2(k)=k%(m-2)+1$
若$m$为$2^i$：$h2(k)=1～m-1$之间的任一奇数。（这样总保证使$h2(k)$和$m$互质）

3、公共溢出区法

将关键字相同（即具有相同散列地址）的记录都存储在同一个溢出区中。

hash表的查找

查找过程和造表过程一致。

假设采用开放定址处理冲突，则查找过程为:

对于给定值$K$, 计算哈希地址 $j = H(K)$

若$r[j] = NULL$ 则查找不成功
若$ r[i].key = K$ 则查找成功
否则求下一地址$j$，直至$r[j] = NULL$ (查找不成功)或$r[j].key = K$ (查找成功)

用线性探测法解决冲突

int hashsize = {997, ...} 	// 哈希表容量递增表，一个合适的素数序列
typedef struct {
    ElemType *elem;	//数据元素存储基址，动态分配数组
    int count;		//当前数据元素个数
    int sizeindex;	//hashsize[sizeindex]为当前容量
}HashTable;

#define SUCCESS 1
#define UNSUCCESS 0
#define DUPLICATE -1

Status SearchHash(HashTable H, KeyType k, int &p, int &c) 
{
    j = Hash(k);
    while(shtable[j] != nullrecd && shtable[j].key != k) j = (j + 1) % m;
    if(shtable[j] == nullrecd) return nulladr;	//未找到
    else if(shtable[j].key == k) return j;		//查找成功
}

用链地址法解决冲突

j = Hash(k);
p = shtable[j];
while(p && p->key != k) p = p->next;
if(!p) return NULL;		//未找到
else if(p->key == k) return p;	//查找成功

决定哈希表查找的ASL的因素：

选用的哈希函数;
选用的处理冲突的方法;
哈希表饱和的程度，装载因子$α=n/m$ 值的大小。
一般情况下，可以认为选用的哈希函数是“均匀”的，则在讨论ASL时，可以不考虑它的因素。

hash表的查找分析：

装填（负载）因子：$α=表中填入的记录数\div hash表的长度$

查找成功

线性探测再散列 $S_{nl}\approx \frac{1}{2}(1+\frac{1}{1-\alpha})$
链地址法 $S_{nc}\approx 1+\frac{\alpha}{2}$
随机探测再散列、二次探测再散列 $S_{nr}\approx -\frac{1}{\alpha}\ln(1-\alpha)$

查找失败

线性探测再散列 $S_{nl}\approx \frac{1}{2}(1+\frac{1}{(1-\alpha)^2})$
链地址法 $S_{nc}\approx \alpha + e^{-\alpha}$
随机探测再散列、二次探测再散列 $S_{nr}\approx \frac{1}{1-\alpha}$

排序

概念及分类

排序：将一组任意顺序的数据，重新排列成按关键字有序的序列。

一般情况下，假设含$n$个记录的序列为：$\{R_1, R_2,…,R_n\}$

其相应的关键字序列为：$\{K_1,K_2,…,K_n\}$

关键字相互之间可以进行比较，即存在关系：$K_{p1}≤K_{p2}≤…≤K_{pn}$（其中$p1, p2, ……, pn$ 为$1,2,……,n$的一种排列）

将$\{R_1,R_2,…,R_n\}$ 中的记录重新排列为 $\{R_{p1}, R_{p2}, …R_{pn}\}$的操作称为排序。

分类：

内部排序：待排序记录存放在计算机随机存储器中进行的排序过程
- 插入排序
  - 直接插入排序
  - 希尔排序
- 交换排序
  - 冒泡排序
  - 快速排序
- 选择排序
  - 简单选择排序
  - 树形排序
  - 堆排序
- 归并排序
- 分配排序
外部排序：待排序记录的数量很大，以致内存不能容纳全部记录

稳定性：若记录序列中的任意两个记录 $Rx、Ry$ 的关键字 $Kx = Ky$ ；如果在排序之前和排序之后，它们的相对位置保持不变，则这种排序方法是稳定的，否则是不稳定的

存储结构

#define MAXSIZE 10000	//一个用作示例的最大长度
typedef int KeyType;	//	定义关键字类型为整数类型
typedef struct {
	KeyType key;
	InfoType otherinfo;	//其它数据项
}RecordType;
typedef struct {	
	RecordType r[MAXSIZE + 1];	//r[0]闲置或作监视哨
	int length;					//顺序表长度
}SqList;

内部排序

插入排序

直接插入排序

排序策略：基于有序插入

在有序表的恰当处插入一个新元素，并保持该有序表的有序性。也即，当第$i$个元素插入时，第$1$到第$i-1$个元素已按关键字排序

算法实现

void InsertSort() {//对记录序列r[1]..r[n]作直接插入排序
	for(i = 2; i <= n; ++i) { //从第二个元素开始比较
        r[0] = r[i];		//r[0]为监视哨
        j = i - 1;
        while(r[0].key < r[j].key) {
            r[j + 1] = r[j]; --j;	//记录后移，边移动边找插入位置
        }
        r[j + 1] = r[0];	//插入到正确位置
    }
}

算法分析

时间复杂度：$T(n)=O(n^2)$

空间复杂度：$S(n)=O(1)$

稳定性：稳定

适用范围：$n$较小，局部有序

希尔(shell)排序

希尔排序（Shell’s Sort）又叫“缩小增量排序”，是对直接插入排序所作的改进。

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

算法设计

void Shellsort() {  // 对记录序列r[1]..r[n]作shell排序,增量是 d 
	d = n / 2;		// 取d = n / 2; d = d / 2; 分组排序
    while(d >= 1) {
        for(i = d + 1; i <= n; ++i) {
            r[0] = r[i]; j = i - d;	//r[0]是暂存单元
            while(j > 0 && r[0].key < r[j].key) {
                r[j + d] = r[j]; 
                j = i - d;
            }	////记录后移，查找插入位置
            r[j + d] = r[0];
        }
        d = d / 2;
    }
}

算法分析

时间复杂度：$T(n)=O(nlog2n)$

空间复杂度：$S(n)=O(1)$

稳定性：不稳定

交换排序

冒泡排序

排序方法：相邻的两个元素的关键字进行比较，小的元素向上冒，大的元素向下沉。

排序算法：

void BubbleSort() {
    // 对r[1]..r[n] 进行冒泡排序
    // 策略：从上至下逐个进行两两比较
	for(i = 1; i <= n; ++i) {
        for(j = 1; j <= n - i; ++j) {
            if(r[j].key > r[j + 1.key]) {
                r[0] = r[j + 1]; r[j + 1] = r[j]; r[j] = r[0];
            }
        }
    }
}

算法改进：

void BubbleSort() {
	// 对r[1]..r[n] 进行冒泡排序，策略：从上至下逐个进行两两比较
    int swap = 1; 
	for(i = 1; i <= n && swap; ++i) { // 进行n-1趟冒泡排序 或 某趟无交换止
        swap = 0;
        for(j = 1; j <= n - i; ++j) {
            if(r[j].key > r[j + 1.key]) {
                r[0] = r[j + 1]; r[j + 1] = r[j]; r[j] = r[0];
                swap = 1;
            }
        }
    }
}

算法分析：

时间复杂度分析：$T(n)=O(n^2)$

空间复杂度分析：$S(n)=O(1)$

稳定性：稳定的

快速排序

排序策略：任选一个元素的关键字（如[1].key）作为标准，将序列分成两部分。其中左半部分的结点的关键字小于等于该元素的关键字，右半部分的结点的关键字大于等于该元素的关键字。然后, 对左右两部分分别进行类似的处理，直至排好序为止

算法实现：

// 一趟快速排序
int Partition(int i, int j) {
    // 对r[i]..r[j]中的记录进行一趟排序，将它们分成两部分
    // 使：[…这部分的值<=x…] x […这部分的值>=x…]
    r[0] = r[i]; x = r[i].key;	//用子表的第一个记录作为界点记录
    while(i < j) {	 // 从表的两端交替地向中间扫描
        while(r[j].key > x && i < j) --j;
        r[i] = r[j];	// 将比界点记录小的记录交换到低端
        while(r[i].key < x && i < j) ++i;
        r[j] = r[i];	// 将比界点记录大的记录交换到高端
    }
    r[i] = r[0];	
    return i;		//返回界点所在位置
}//Partition

//快速排序
void QuickSort(int low, int high) {
    // 对记录序列r[low]..r[high]进行快速排序
    if(low >= high) return;	// 长度小于1
    int mid = Partition(low, high);
    QuickSort(low, mid - 1);
    QuickSort(mid + 1, high);
}

算法分析

时间复杂度：$T(n)=O(log_2n)$

空间复杂度：$S(n)=O(log_2n)$

稳定性：不稳定

适用范围：n较大且表无序时

选择排序

简单选择排序

排序策略：在待排序的数据中选择最小值。

算法实现

void SelectSort() {
    //对记录序列r[1]..r[n]进行简单选择排序
    int i, j, k;
    for(i = 1; i <= n-1; ++i) {	//进行n-1趟
     	k = i;
        for(j = i + 1; j <= n; ++j) {
            if(r[j] < r[k]) k = j; // 保持r[k]的关键字最小
        }
        if(i != k) {
            r[0] = r[i]; r[i] = r[k]; r[k] = r[0]; //在待排序的数据中选择最小值，并存入r[i]处
        }
    }
}

算法分析

时间分析：$T(n)=O(n^2)$

空间分析：$S(n)=O(1)$

稳定性：不稳定

适用范围：1）$n$较小时，2）在$n$个待排序的数据中选择前$k(k<<n)$个最小值时

树形排序

树形选择排序(Tree Selection Sort)又称锦标赛排序(Tournament Sort)

堆排序(Heap Sort)

堆的定义：$n$个元素的序列$\{k_1,k_2,…k_n\}$，满足： $\begin{cases} k_i >= k_{2i} \\ k_i >=k_{2i+1} \end{cases} 或 \begin{cases} k_i <= k_{2i} \\ k_i <=k_{2i+1} \end{cases}$

堆是一个完全二叉树。

堆排序：输出堆顶的最小值（最大值）后，将剩下的$n-1$个元素序列重新建成一个堆，得到次小值（次大值）。反复执行，得到一个有序序列。

构造堆：按堆的定义将$r[1]…r[n]$调整为堆

$r[n]$与$r[1]$互换，将$r[1]…r[n-1]$调整为堆。再将$r[n-1]$与$r[1]$互换，将$r[1]…r[n-2]$调整为堆。……，直至排序完成。

堆的调整：在选出某段序列最大（小）值后，要将剩下的序列调整

左右孩子比较
父子比较

算法实现

void sift(int i, int m) {  //堆的调整，也是建堆
    //把以 t 为根的完全二叉树r[i]..r[m]调整成一个堆 
 	//初值：i的左右子树均是堆
    int j = i * 2;	//j指向左孩子
    r[0] = r[i];	//将r[i]暂存在r[0]中
    while(j <= m) {
        if(j < m && r[j].key < r[j + 1].key) ++j; //左孩子与右孩子进行比较，找较大孩子，确定筛选方向
        if(r[0].key < r[j].key) {
            r[i] = r[j]; i = j; j = 2 * i;	// 继续筛选
        }
        else j = m + 1;	//筛选完毕
        r[i] = r[0];
    }  
}

void heapsort() {	//将r[1]...r[n]进行堆排序
    for(j = n / 2; j >= 1; --j) sift(j, n);	//建堆，得最大值r[1]
    for(j = n; j >= 2; --j) {
        r[0] = r[1]; r[1] = r[j]; r[j] = r[0];
        //堆顶（根）结点与最后结点的值对换
        sift(1, j - 1);	//调整堆
    }
}

算法分析

时间分析：$T(n)=O (nlog2n)$

空间分析：$S(n)=O(1)$

稳定性：不稳定

适用范围：1）$n$较大。2）选取前$k(K<<n)$个最小（大）元素时

归并排序

归并排序（Merging Sort）就是将两个或两个以上的有序表合并成一个有序表的过程。将两个有序表合并成一个有序表的过程称为2-路归并，2-路归并最为简单和常用。

排序示例：

二路归并算法：

void Merge(RedType R[], RedType T[], int low, int mid, int high) {
    // 将两个有序表R[low]..R[mid]和R[mid+1]..r[high]归并为一个新的有序表T[low]..r[high]
    i = low; j = mid + 1; k = low;	//初值i,j,k为指示器
    while(i <= mid && j <= high) {
        if(R[i].key <= R[j].key) T[k++] = R[i++];
        else T[k++] = R[j++];
    }
    while(i <= mid) T[k++] = R[i++];	//将剩余的R[i]..R[mid]放入T中
    while(j <= high) T[k++] = R[i++];	//将剩余的R[j]..R[high]放入T中
}

void mergeSort(RedType R[], RedType &T[], int low, int high) {
    //R[low]..R[high]归并排序后放入T[low]..T[high]中
    if(low < high) {
        mid = (low + high) / 2;		//将当前序列一分为二，分裂点mid
        mergeSort(R, S, low, mid);		//对子序列R[low..mid]递归归并排序
        mergeSort(R, S, mid + 1, high);	//对子序列R[mid+1..high]递归归并排序
        Merge(R, T, low, mid, high);	//将S[low..mid]和S[mid+1..high]归并到T[low..high]
    }
}

算法分析

时间复杂度：$T(n)=O(nlog_2n)$

空间复杂度：$S(n) = O(n)$

稳定性：稳定

适用范围：$n$较大时

基数排序

基数排序（Radix Sorting）是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。

多关键字的排序

假设$n$个记录的序列$\{R_1,R_2,…R_n\}$，且每个记录$R_i$含有$d$个关键字$(K_i^0,K_i^1,…,K_i^{d-1})$

序列$\{R_1,R_2,…R_n\}$对关键字$(K_i^0,K_i^1,…,K_i^{d-1})$有序：对于序列中任意两个记录$R_i$和$R_j(1<=i<j<=n)$满足： $(K_i^0,K_i^1,...,K_i^{d-1}) < (K_j^0,K_j^1,...,K_j^{d-1})$ 其中$K^0$称为最主位关键字，$K^{d-1}$称为最次位关键字。

法一：最高位优先法（Most Significant Digit first）MSD

对最主位关键字$K^0$排序，将序列分成若干个子序列，每个子序列中的记录有相同的$K^0$值
对每个子序列按$K^1$排序，每个序列再分成更小的序列，依次重复至对每个序列进行$K^{d-1}$排序后
将所有子序列依次联接称为一个有序序列

法二：最低位优先法（Least Significant Digit first）LSD

和MSD相反

示例：10进制数排序

队列的表示

顺序队列

问题：每一个队列的长度是多少？
缺点：空间开销大。
链式队列

需设 2rd 个指针，rd：基数。如10进制数，rd=10

存储结构

#define KEY_NUM	10
struct node {
    int key[KEY_NUM];	//d: 关键字的位数
    infoType data;
    struct node *next;
};

算法实现

void distribute(struct node *head, int i, ) {
    //分配算法，考察每一个元素的第i个关键字，并放入相应的队列中
    for(j = 0; j < KEY_NUM; ++j) f[j] = NULL;	//队列初始化，f保存每个子序列的头
    p = head->next;	//头指针不存储数据
    while(p != NULL) {
        j = p->key[i];	//考察p所指结点的第i位
        if(f[j] == NULL) f[j] = p;
        else r[j]->next = p;
        r[j] = p;		//r记录每个子序列的尾
        p = p->next;	//p后移
    }
}
void collect(struct node &head) {
    //收集算法：从队列0到队列9进行收集
    j = 0;
    while(f[j] == NULL) ++j;	//找第一个非空队列
    head->next = f[j]; t = r[j]; //head:收集后链表的头指针，t:尾指针
    while(j < 9) {
        j++;
        if(f[j] != NULL) {
            t->next = f[j];
            t = r[i];
        }
    }
    t->next = NULL;
}
void radixSort(struct node *head) {
    //基数排序：从低位开始
    create link_list(head);	//建立链表，head:头指针
    for(i = KEY_NUM - 1; i >= 0; --i) {	//进行KEY_NUM趟分配和收集
    	distribute(head, i);
        collect(head);
    }
}

算法分析

时间复杂度：$T(n)=O(d(n+rd))=O(n)$ 关键码$d$位，对 rd 个队列收集

空间复杂度：$S(n)=O(n+2rd)$

稳定性：稳定

小结

排序方法	平均时间	最坏情况	辅助存储空间	稳定性
直接插入排序	$O(n^2)$	$O(n^2)$	$O(1)$	Y
冒泡排序	$O(n^2)$	$O(n^2)$	$O(1)$	Y
简单选择排序	$O(n^2)$	$O(n^2)$	$O(1)$	Y
快速排序	$O(nlog_2n)$	$O(n^2)$	$O(log_2n)$	N
堆排序	$O(nlog_2n)$	$O(nlog_2n)$	$O(1)$	N
归并排序	$O(nlog2n)$	$O(nlog_2n)$	$O(n)$	Y
基数排序	$O(n)$	$O(n)$	$O(rd)$	Y

外部排序

内存和外存

计算机存储器主要有两种：

主存储器 ( primary memory 或者 main memory ，简称“内存”，或者“主存”)
- 随机访问存储器 ( Random Access Memory, 即 RAM )
- 高速缓存 ( cache )
- 视频存储器 ( video memory )
外存储器 ( peripheral storage 或者 secondary storage，简称“外存”，或“辅存”)
- 硬盘 (几百$G$ - 几百$T$， $10^{12B} $)
- 磁带 (几个$P$， $10^{15}B$ )
- 磁盘

内存的优缺点

优点：访问速度快
缺点：造价高，存储容量小，断电丢数据
CPU 直接与主存沟通，对存储在内存地址的数据进行访问时，所需要的时间可以看作是一个很小的常数，看作随机存取

外存的优缺点

优点：价格低、信息不易失、便携性
缺点：存取速度慢
- 一般的内存访问存取时间的单位是纳秒（1 纳秒 = $10^{-9}$ 秒）
- 外存一次访问时间则以毫秒（1 毫秒 = $10^{-3}$ 秒）或秒为数量级
牵扯到外存的计算机程序应当尽量减少外存的访问次数，从而减少程序执行的时间

单位

$KB$ (kilo byte) $10^3B$ (页块)
$MB$ (mega byte) $10^6B$ (高速缓存)
$GB$ (giga) $10^9B$ (内存、硬盘)
$TB$ (tera) $10^{12}B$ (磁盘阵列)
$PB$ (peta) $10^{15}B$ (磁带库)
$EB = 10^{18}B；ZB = 10^{21}B；YB = 10^{24}B$
$Googol$ 是 10 的 100 次方

磁带

磁带大约1/2英寸宽，绕在一个卷盘上。使用时，将磁带盘放在磁带机上，驱动器控制磁带盘转动，带动磁带向前移动。通过读/写头就可以读出磁带上的信息或把信息写入磁带中。

磁带不是连续转动的设备，而是一种启停设备（启停时间约5毫秒）。由于读写信息应在旋转稳定时进行，而磁带从静止转态启动后，需经历加速阶段；读/写结束后，需经历减速阶段。因此，在磁带上相邻两个字符组（记录）之间要留有一空白区，叫做间隙IRG(Inter Record Gap)。

为有效利用磁带，常常用组成块的长度的方法来减少 $IRG$ 的个数。在每次写信息时，不是按用户给出的字符组记入磁带，而是将若干个字符组合并成一块后一次写入磁带。字符组间没有了 $IRG$ ，变成块间的间隙 $IBG$ (Inter Block Gap) 。

成块的好处和限制：

减少 $IRG$，提高磁带利用率
减少 I/O 操作
物理块不能太大，通常 1K~8K 字节。太大容易出错，内存开辟的缓冲区也越大。

磁带上读取一块信息所需时间由两部分组成：$T_{I/O}=t_a+n\times t_w$

$t_a$ 为延迟时间，读/写头到达传输信息所在物理块起始位置所需时间
$t_w$ 传输一个字符的时间

顺序存储设备的主要缺点是检索和修改信息不方便。因此主要用于处理变化少，只进行顺序存取的大量数据。

磁盘

磁盘是一种直接存取的存储设备（DASD）。可以直接存取任何字符组，容量大，存取速度比磁带快得多。

磁盘是一个扁平的圆盘，盘面有许多磁道记载信息。磁盘可以是单片，也可以是若干个盘片组成盘组。每一片有两个面，最顶上和最底下盘片的外侧面不存信息。

磁盘可分为固定头盘和活动头盘。

固定头盘的每一道上都有独立的磁头，固定不动，专负责读/写某一道上的信息。
活动头盘的磁头可移动，盘组可变。一个面上只有一个磁头，可以从该面上的一道移到另一道。
- 磁头装在动臂上，不同面的磁头是同时移到的，并处于同一圆柱面。
- 各面上半径相同的磁道组成一个圆柱面。
- 磁盘是上表面一个具体信息必须用一个三维地址：柱面号、盘面号、块号。
- 柱面号确定读/写头的径向运动，块号确定信息在盘片圆圈上的位置。

访问信息：

先找柱面，磁头移动到所需柱面上（称为定位或寻查）
等待要访问的信息转到磁头下
读/写信息

读写信息所需时间：$T_{I/O}=t_{seek}+t_{la}+n\times t_{wm}$

$t_{seek}$ 寻查时间(seek time)：读/写头定位的时间
$t_{la}$ 等待时间(latency time)：等待信息块的初始位置旋转到读写头下的时间
$t_{wm}$ 传输时间(transmission time)

外部排序的方法

外部排序基本由两个相对独立的阶段组成。

1）按可用内存大小，将外存上含 $n$ 个记录的文件分成若干长度为 $l$ 的子文件或段（segment），依次读入内存并利用有效的内部排序方法对它们进行排序，并将排序后得到的有序子文件重新写入外存。通常称这些有序子文件为归并段或顺串（run）

2）对这些归并段逐趟归并，使归并段逐渐由小至大，直至得到整个有序文件为止。

第一阶段是内部排序的内容，主要是第二阶段即归并的过程。

示例：2-路平衡归并

在内存中将两个有序段归并成一个有序段很简单。但是，在外部排序中实现两两归并时，要进行外存的读／写，因为不可能将两个有序段及归并结果段同时存放在内存中的缘故。假设在上例中毎个物理块可以容纳200个记录，则每一趟归并需进行50次“读”和50次“写”,4趟归并加上内部排序时所需进行的读／写使得在外排中总共需进行500次的读 / 写。

一般情况下，$外部排序所需总的时间＝$$内部排序（产生初始归并段）所需的时间 (m\times t_{IS})+ \\ 外存信息读写的时间 (d\times t_{IO})+ \\ 内部归并所需的时间 (s\times ut_{mg})$

$t_{IS}$ 是为得到一个初始归并段进行内部排序所需时间的均值
$t_{IO}$ 是进行一次外存读／写时间的均值
$ut_{mg}$ 是对 $u$ 个记录进行内部归并所需时间
$m$ 为经过内部排序之后得到的初始归并段的个数
$s$ 为归并的趟数
$d$ 为总的读／写次数

由此，上例10000个记录利用2﹣路归并进行外排所需总的时间为：$10\times t_{IS}+500\times t_{IO}+4\times 10000t_{mg}$

$t_{IO}$ 取决于所用的外存设备，比 $t_{mg}$ 大得多。提高外排效率主要是减少外存信息读写的次数 $d$ 。

若对上例采取5-路平衡归并，仅需两趟归并，外排时总的读写次数便减至 $2\times 100+100=300$ ，比2-路平衡归并少了200次读写。

一般情况下：对 $m$ 个起始归并段进行 k-路平衡归并 时，归并趟数：$s=$ int $(log_km)$ 即 $log_km$向下取整

多路平衡归并

增加 $k$ 可以减少 $s$ ，从而减少外存读／写的次数。但单纯增加 $k$ 将导致增加内部归并的时间 $ut_{mg}$ 。

在2﹣路归并中，令 $u$ 个记录分布在两个归并段上。每得到归并后的一个记录，仅需一次比较即可，则得到含 $u$ 个记录的归并段需进行 $u-1$ （不应该是 $u$ 次比较吗）次比较。

再看 k﹣路归并。令 $u$ 个记录分布在 E 个归并段上，显然，归并后的第一个记录应是 $k$ 个归并段中关键字最小的记录，即应从毎个归并段的第一个记录的相互比较中选出最小者，这需要进行 $k-1$次比较。同理，每得到归并后的有序段中的一个记录，都要进行 $k-1$ 用次比较。显然，为得到含 $u$ 个记录的归并段需进行 $(u -1)(k-1)$ 次比较。由此，对 $n$ 个记录的文件进行外排时，在内部归并过程中进行的总的比较次数为 $s(k-1)(n-1)$ 。

假设所得初始归并段为 $m$ 个，则内部归并过程中进行比较的总的次数为

内部归并时间亦随 $k$ 的增长而增长。这将抵消由于增大 $k$ 而减少外存信息读写时间所得效益。然而，若在进行 k﹣路归并时用 败者树( Tree of Loser )，则可使在 $k$ 个记录中选出关键字最小的记录时仅需进行 $[log_2k]$ 次比较。

败者树( Tree of Loser )：类似于堆排序里面的完全二叉树，只不过败者树非叶子结点保存的是子孙比较中的败者。

胜者树( Tree of Winner )：和败者树相反

$k$ 值的选择并非越大越好，如何选择合适的 $k$ 是一个需要综合考虑的问题。

算法实现

K_Merge简单描述利用败者树进行 K-路平衡排序归并的过程，避开了外存信息存取的细节，可认为归并段已读入内存。

Adjust描述在从败者树选得最小关键字的记录之后，如何从叶到根调整败者树选得下一个最小关键字。

CreateLoserTree初建败者树的过程。

typedef int LoserTree[k];	//败者树是完全二叉树且不含叶子，可采用顺序存储结构
typedef struct {
    KeyType key;
}ExNode, External[k + 1];	//外结点，只存放待归并记录的关键字

void K_Merge(LoserTree &ls, External &b) {
    //利用败者树 ls 将编号从 0 到 k-1 的 k 个输入归并段中的记录归并到输出归并段
    //b[0]至b[k-1]为败者树上的k个叶子结点，分别存放k个输入归并段中当前记录的关键字
    for(i = 0; i < K; ++i) input(b[i].key);	//分别从k个输入归并段读入该段当前第一个记录的关键字到外接点
    CreateLoserTree(ls);	//建败者树ls，选得最小关键字为 b[ls[0]].key
    while(b[ls[0]].key != MAXKEY) {
        q = ls[0];	//q指示当前最小关键字所在归并段
        output(q);	//将编号为q的归并段中当前（关键字为b[q].key）的记录写至输出归并段
        input(b[q].key, q);	//从编号为q的输入归并段读入下一个记录的关键字
        Adjust(ls, q);		//调整败者树，选择新的最小关键字
    }
    output(ls[0]);	//将含最大关键字MAXKEY的记录写至输出归并段
}

void Adjust(LoserTree &ls, int s) {	
    //沿从叶子结点b[s]到根结点ls[0]的路径调整败者树
    t = (s + k) / 2;	//ls[t]是b[s]的双亲结点
    while(t > 0) {
        if(b[s].key > b[ls[t]].key) s<-->ls[t];      //s指向新的胜者                           
        t = t / 2;                                                                    
    }
    ls[0] = s;
}

void CreateLoserTree(LoserTree &ls) {
    // 已知b[0]到b[k-1]为完全二叉树ls的叶子结点存有k个关键字，沿叶子到根的k条路径将ls调整成败者树
    b[k].key = MINKEY;	//设MINKEY为关键字可能的最小值
    for(i = 0; i < k; ++i) ls[i] = k;	//设置ls中“败者”的初值
    for(i = k - 1; i >= 0; --i) Adjust(ls, i);	//依次从b[k-1]...b[0]出发调整败者
}

置换-选择排序

归并的趟数和 $k$ 成反比，也和 $m$ 成正比。因此，减少 $m$ 是减少 $s$ 的另一条途径。

$m$ 是外部文件经过内部排序之后得到的初始归并段的个数，显然，$m=ceil(n/l)$(向上取整)，其中 $n$ 为外部文件中的记录数，$l$ 为初始归并段中的记录数。但这依赖于进行内部排序时可用内存工作区的大小，则 $m$ 也随其而限定。若要减小 $m$，即增加 $l$，就必须探索新的排序方法。

置换-选择排序（Replacement-Selection Sorting）是在树形选择排序的基础上得来的，它的特点是：在整个排序（得到所有初始归并段）的过程中，选择最小（或最大）关键字和输入、输出交叉或平行进行。

例子：已知初始文件含有24个记录，它们的关键字分别为：51,49,39,46,38,29,14,61,15,30,1,48,52,3,63,27,4,13,89,24,46,58,33,76

假设内存工作区可容纳6个记录，则按前面讨论的选择排序可求得如下4个初始归并段：

RUN1：29,38,39,46,49,51
RUN2：1,14,15,30,48,61
RUN3：3,4,13,27,52,63
RUN4：24,33,46,58,76,89

若按置换-选择排序进行排序，则可求得如下3个初始归并段：（过程见下文）

RUN1：29,38,39,46,49,51,61
RUN2：1,3,14,15,27,30,48,52,63,89
RUN3：4,13,24,33,46,58,76

假设初始待排文件为输入文件$FI$,初始归并段文件为输出文件$FO$，内存工作区为$WA$，$FO$和$WA$的初始状态为空，并设内存工作区的容量可容纳 $w$ 个记录，则置换-选择排序的操作过程为：

① 从FI输入w个记录到工作区WA。
② 从WA中选出其中关键字取最小值的记录，记为MINIMAX记录。
③ 将MINIMAX记录输入到FO中去。
④ 若FI不空，则从FI输入下一个记录到WA中。
⑤ 从WA中所有关键字比MINIMAX记录的关键字大的记录中选出最小关键字记录，作为新的MINIMAX记录。
⑥ 重复③～⑤，直至WA中选不出新的MINIMAX记录为止，由此得到一个初始归并段，输出一个归并段的结束标志到FO中去。
⑦ 重复②～⑥，直至WA为空。由此得到所有初始归并段。

在$WA$中选择MINIMAX记录的过程需利用败者树来实现。

说明：

（1）内存工作区中的记录作为败者树的外部结点，而败者树中根结点的双亲结点指示工作区中关键字最小的记录。

（2）为了便于选出MINIMAX记录，为每个记录附设一个所在归并段的序号，在进行关键字的比较时，先比较段号，段号小者为胜者；段号相同的则关键字小的为胜者。

（3）败者树的建立可从设工作区中所有记录的段号均为 $0$ 开始，然后从$FI$逐个输入$w$个记录到工作区时，自上而下调整败者树。由于这些记录的段号为 $1$，则它们对于 $0$ 段的记录而言均为败者，从而逐个填充到败者树的各结点中去。

算法实现：

Replacd_selection是置换﹣选择排序的简单描述，其中，求得一个初始归并段的过程如算法11.5所述。算法11.6和算法
11.7分别描述了置换﹣选择排序中的败者树的调整和初建的过程

typedef  struct
{
   RedType rec;                 //记录
   KeyType key;                 //从记录中抽取的关键字
   int rnum;                    //所属归并段的段号
}RcdNode,WorkArea[w];           //内存工作区，容量为w
WorkArea wa;

void Construct_Loser(LoserTree &ls, WorkArea &wa) { //初建败者树
    //输入w个记录到内存工作区wa，建立败者树ls，选出关键字最小的记录并由s指示其在wa中的位置
    for(i = 0; i < w; ++i) {
        wa[i].rnum = wa[i].key = ls[i] = 0;	//工作区初始化
    }
    for(i = w - 1; i > 0; --i) {
        freed(&wa[i].rec, sizeof(RcdType), 1, fi);	//输入一个记录
        wa[i].key = wa[i].rec.key;					//保存该记录的关键字
        wa[i].rnum = 1;								//其段号为 1 
        Select_MiniMax(ls, wa, i);					//调整败者
    }
}yu

void Select_MiniMax(LoserTree &ls, WorkArea wa, int q) {	//选出MINIMAX
    //从wa[q]起到败者树的根比较选择MINIMAX记录，并由q指示它所在的归并段
    t = (w + q) / 2;
    for(p = ls[t]; t > 0; t = t / 2) {
        if(wa[p].rnum < wa[q].rnum || (wa[p].rnum == wa[q].rnum && wa[p].key < wa[q].key)) {
            q <--> ls[t];	//q指向新的胜利者
        }
        ls[0] = q;
    }
}

void Replacd_selection(LoserTree &ls, WorkArea &wa, FILE *fi, FILE *fo) {
    //在败者树ls和内存工作区wa上用置换-选择排序求初始归并段，fi为输入文件（只读文件）指针
    //fo为输出文件（只写文件指针）
    Construct_Loser(ls, wa);	//创建败者树
    rc = rmax = 1;	//rc指示当前生成的初始归并段的段号，rmax指示wa中关键字所属初始归并段的最大段号
    while(rc <= rmax) { // rc = rmax + 1 表示输入文件的置换-选择排序已完成
    	get_run(ls, wa); //求得一个初始归并段
        fwrite(&RUNEND_SYMBOL, sizeof(struct RcdNode), 1, fo);	//将段结束标志写入输出文件
        rc = wa[ls[0]].rnum;	//设置下一段的段号
    }
}

void get_run(LoserTree &ls, WorkArea &wa) {
    //求得一个初始归并段，fi为输入文件指针，fo为输出文件指针
    while(wa[ls[0]].rnum == rc) { 	//选得的MINIMAX记录属当前段时
        q = ls[0];			//q指示MINIMAX记录在wa中的位置
        minimax = wa[q].key;	
        fwrite(&wa[q].rec, sizeof(RcdType), 1, fo); 	//将刚选好的MINIMAX记录写入输出文件
        if(feof(fi)) {	//输入文件结束，虚设记录（属rmax+1段）
            wa[q].rnum = rmax + 1;
            wa[q].key = MAXKEY;
        }
        else {			//输出文件非空时
            fread(&wa[q].rec, sizeof(RcdType), 1, fi);	//从输入文件读入下一记录
            wa[q].key = wa[q].rec.key;	//提取关键字
            if(wa[q].key < minimax) {	//新读入的记录属下一段
                rmax = rc + 1;
                wa[q].rnum = rmax;
            }
            else wa[q].rnum = rc;	//新读入的记录属当前段
        }
        Select_MiniMax(ls, wa, q);	//选出新的MINIMAX记录
    }//while
}//get_run

置换-选择排序所得初始归并段的长度不等。且可证明，当输入文件中记录的关键字为随机数时，所得初始归并段的平均长度为内存工作区大小 $w$ 的两倍。

假设一台扫雪机在环形路上等速进行扫雪，又下雪的速度也是均衡的（即每小时落到地面上的雪量相等），雪均匀地落在扫雪机的前、后路面上，边下雪边扫雪。显然，在某个时刻之后，整个系统达到平衡状态，路面上的积雪总量不变。且在任何时刻，整个路面上的积雪都形成一个均匀的斜面，紧靠扫雪机前端的积雪最厚，其深度为$h$，而在扫雪机刚扫过的路面上的积雪深度为零。若将环形路伸展开来，路面积雪状态如图所示。假设此刻路面积雪的总体积为$w$，环形路一圈的长度为$l$，由于扫雪机在任何时刻扫走的雪的深度为$h$，则扫雪机在环形路上走一圈扫掉的积雪体积为$lh$即$2w$。

最佳归并树

假设由置换-选择得到9个初始归并段，其长度（即记录数）依次为9，30，12，18，3，17，2，6，24。现作3-路平衡归并，其归并树（表示归并过程的图）如图(b)所示，图中每个圆圈表示一个初始归并段，圆圈中数字表示归并段的长度。假设每个记录占一个物理块，则两趟归并所需对外存进行读/写次数为 $(9+30+12+18+3+17+2+6+24)×2×2=484$。若将初始归并段的长度看成是归并树中叶子结点的权，则此3叉树的带权路径长度的两倍恰为484。若对长度不等的$m$个初始归并段，构造一棵哈夫曼树作为归并树，便可使在进行外部归并时所需对外存进行读/写次数达最少。对上述9个初始归并段可构造一棵如图(a)所示的归并树，按此树进行归并，仅需对外存进行446次读/写，这棵归并树便称做最佳归并树。