目录
- 1.1 什么是数据结构
- 1.2 什么是算法
- 2.1 线性表及其实现
- 2.2 堆栈及实现
- 2.3 队列及实现
- 3.1 树与树的表示
- 4.1 二叉搜索树
- 5.1 堆
- 5.2 哈夫曼树与哈夫曼编码
- 5.3 集合及运算
- 6.1 什么是图
- 6.2 图的遍历
- 7.1 有向图最短路径问题
- 8.1 最小生成树问题
- 9.1 简单排序
- 9.4 归并排序
- 10.1 快速排序
- 10.2 表排序
- 10.3 基数排序
- 10.4 排序算法的比较
- 11.1 散列表
- 11.2 散列函数的构造方法
- 11.3 冲突处理方法
- 11.4 散列表的性能分析
- 12.1 串的模式匹配
1.1 什么是数据结构
1.1 解决问题方法的效率
（1）图书管理：和数据组织方式有关
（2）printN：和空间利用率有关
（3）多项式加法：和算法的巧妙程度有关
- 用clock来打点计时，clock_t型数据，除以CLOCKS_PER_SEC
1.2 数据结构的定义
-
数据结构是关于数据对象在计算机中的组织方式
-
包括逻辑结构和物理存储结构
-
数据对象必定与一系列加在其上的操作相关，完成这些操作的方法就是算法
1.3 抽象数据类型
-
数据类型：数据对象集和相关联的操作集
-
抽象：描述数据类型的方法不依赖于具体实现
1.2 什么是算法
1.2.1 算法指标
-
空间复杂度S(n)：占用存储单元的长度
-
时间复杂度T(n)：耗费时间的长度
-
n是数据规模
1.2.2 复杂度的渐进表示法
-
O(f(n))是T(n)的最小上边界
-
T1(n)+T2(n)=max(O(f1(n), O(f2(n))
-
T1(n)*T2(n)=O(f1(n))* O(f2(n))
-
若T(n)是关于n的k阶多项式，那T(n)=O(n^k)
-
for循环的复杂度为循环次数乘以循环体代码的复杂度
-
if-else复杂度为三者中最大
1.2.3 例子—求最大连续子列和
-
分而治之: T(n)=O(nlogn)
-
在线处理：每输入一个数据就进行即时处理，在任何一个地方中止输入，算法都能给出当前的正解
2.1 线性表及其实现
2.1.1 引子—多项式的表示
-
顺序存储结构：结构数组
-
链表结构
2.1.2 线性表
（1）线性表定义
- 由同类型数据元素构成有序序列的线性结构
（2）线性表的抽象数据类型描述
- 类型名称：线性表（List）
- 数据对象集：n个元素构成的有序序列
- 操作集：初始化、查找元素、查找位置、插入、删除
2.1.2 顺序存储
- 利用数组连续存放
- 下标从0开始
typedef struct LNode *List;
struct LNode{
ElementType Data[MAXSIZE];
int Last;
};
struct LNode L;
List PtrL;
2.1.3 链式存储
- 下标从1开始
typedef struct LNode *List;
struct LNode{
ElementType Data; //节点对应的数据
List Next; //下一个节点的位置
};
struct Lnode L;
List PtrL;
2.1.4 广义表与多重链表
- 二元多项式用广义表表示
- 广义表的定义
typedef struct GNode *GList;
struct GNode{
int Tag; /*标志域：0表示结点是单元素，1表示结点是广义表 */
union { /*子表指针域Sublist与单元素数据域Data复用，即共用存储空间*/
ElementType Data;
GList SubList;
} URegion;
GList Next; /* 指向后继结点 */
};
- 多重链表：链表中的节点可能同时隶属于多个链
- 采用十字链表来存储稀疏矩阵
2.2 堆栈及实现
2.2.1 什么是堆栈
（1）计算机如何进行表达式求值
- 利用栈求后缀表达式
- 堆栈也是线性表，只在一端做插入、删除
2.2.2 堆栈的顺序存储实现
- 结构体：Data数组和Top值
2.2.3 堆栈的链式存储实现
- 结构体：Data值和Next指针
- Top指针指向头结点
2.2.4 堆栈应用：表达式求值
（1）将中缀表达式转化为后缀表达式
-
从头到尾读取 中缀表达式的每个对象 ，对不同对象按不同的情况处理
① 运算数：直接输出；
② 左括号：压入堆栈；
③ 右括号：将栈顶的运算符弹出并输出，直到遇到左括号（ 出栈，不输出）；
④ 运算符：- 若优先级大于栈顶运算符时，则把它压栈；
- 若优先级小于等于栈顶运算符时，将栈顶运算符弹出并输出；再比较新的栈顶运算符，直到该运算符大于 栈顶运算符优先级为止，然后将该运算符压栈；
⑤ 若各对象 处理完毕，则把堆栈中存留的运算符一并输出。
（2）函数调用及递归实现
（3）回溯算法
2.3 队列及实现
2.3.1 队列及顺序存储实现
（1）队列的定义
- 具有一定操作约束的线性表，只能在一端插入，另一端删除
（2）队列的顺序存储实现
-
由一个一维数组和一个记录队列头位置的变量front和记录尾的变量rear组成
- 插入rear+1，删除front+1
-
循环队列：充分利用空间，front=rear时队列为空
2.3.2 队列的链式存储实现
- 在链表头部做删除（front指向头），在链表尾部做插入（rear指向尾）
struct Node{
ElementType Data;
struct Node *Next;
};
struct QNode{ /* 链队列结构 */
struct Node *rear; /* 指向队尾结点 */
struct Node *front; /* 指向队头结点 */
};
2.4 应用实例：多项式加法运算
3.1 树与树的表示
3.1.1 引子
- 树的分层管理在查找上效率更高
（1）查找
- 根据给定关键字，从集合R中找出关键字与K相同的记录
- 静态查找：集合中记录是固定的
- 动态查找：集合中记录是动态变化的，可以插入和删除
（2）顺序查找
- 建立哨兵，可以减少一个判断条件，不成功则返回0
- O(N)
（3）二分查找
- 时间负责度O(logN)
（4）二分查找判定树
- 判定树上每个结点需要的查找次数刚好为所在的层数
- 查找成功时次数不会超过树的深度
- 以树的形式存储数据，可以方便插入和删除，解决动态查找问题
3.1.4 树的定义和术语
（1）定义
- 根和子树
- 子树不相交；除根结点外，每个结点有且仅有一个父结点；一颗N结点的树有N-1条边
（2）结点
- 结点的度：结点的子树个数
- 树的度：树的所有结点中最大的度数
- 树的深度：所有结点中的最大层次是这颗树的深度
- 兄弟结点
3.1.5 树的表示
- 链表：儿子兄弟表示法
- 旋转45度变为二叉树
3.2.1 二叉树的定义及性质
（1）定义
- 由根节点和左子树、右子树组成
- 二叉树有左右子树之分，普通二叉树没有
（2）特殊二叉树
- 完美二叉树
- 完全二叉树
（3）重要性质
- 深度为k的二叉树最大结点总数为2^k-1
- n_0=n_2+1
（4）遍历方法
- 先序、中序、后续、层次遍历
3.2.2 二叉树的存储结构
（1）顺序存储结构
-
完全二叉树，按顺序编号，父结点的序号是[i/2]，左孩子结点是2*i，右孩子结点是2*i+1
-
一般的补为完全二叉树，有空间浪费
（2）链表存储
- 指向左右孩子
3.3.1 先序中序后序递归遍历
（1）先序遍历
- 先访问根节点，先序遍历其左子树，先序遍历其右子树
（2）中序遍历
- 中序遍历左子树，访问根节点，中序遍历右子树
（3）后序遍历
- 后序遍历左子树，后序遍历右子树，访问根节点
3.3.2 中序非递归遍历
- 遇到一个结点，压栈，遍历其左子树
- 左子树遍历结束后，从栈顶弹出这个结点并访问
- 再去中序遍历该结点的右子树
3.3.3 层序遍历
- 从队列中取出一个元素
- 访问该元素
- 将左孩子右孩子入队列
3.3.4 树的同构
- T1通过若干次左右孩子互换变成T2，就称同构
4.1 二叉搜索树
4.1.1 二叉搜索树及查找
（1）特点
- 左子树上的所有结点小于根节点
- 右子树上所有结点大于根节点
（2）相关函数
- 查找特定值函数，查找最小值函数，查找最大值函数
- 插入和删除函数
（3）Find函数
- 尾递归（在函数返回时递归）函数改为迭代函数
Position IterFind( ElementType X, BinTree BST )
{
while( BST ) {
if( X > BST->Data )
BST = BST->Right; /* 向右子树中移动 ， 继续查找*/
else if( X < BST->Data )
BST = BST->Left; /* 向左子树中移动 ， 继续查找*/
else /* X == BST->Data */
return BST; /* 查找成功 ， 返回结点的找到结点的地址*/
}
return NULL; /* 查找失败*/
}
- 查找的效率取决于树的高度->平衡二叉树
（4）查找最小值和最大值函数
- 查找指针指向最左和最右结点
4.1.2 二叉搜索树的插入
BinTree Insert( ElementType X, BinTree BST )
{
if( !BST ){
/* 若原树为空 ， 生成并返回一个结点的二叉搜索树*/
BST = malloc(sizeof(struct TreeNode));
BST->Data = X;
BST->Left = BST->Right = NULL;
}else /* 开始找要插入元素的位置*/
if( X < BST->Data )
BST->Left = Insert( X, BST->Left);
/* 递归插入左子树*/
else if( X > BST->Data )
BST->Right = Insert( X, BST->Right);
/* 递归插入右子树*/
/* else X 已经存在 ， 什么都不做 */
return BST;
}
4.1.3 二叉搜索树的删除
（1）分三种情况
- 删除叶结点：直接删除，修改父节点指针为null
- 删除结点只有一个孩子：将父节点的指针指向要删除的结点的孩子结点
- 删除结点有两个孩子：用右子树的最小元素或者左子树的最大元素替代被删除结点
（2）代码
BinTree Delete( ElementType X, BinTree BST )
{ Position Tmp;
if( !BST ) printf(" 要删除的元素未找到");
else if( X < BST->Data )
BST->Left = Delete( X, BST->Left); /* 左子树递归删除 */
else if( X > BST->Data )
BST->Right = Delete( X, BST->Right); /* 右子树递归删除 */
else /* 找到要删除的结点 */
if( BST->Left && BST->Right ) { /* 被删除结点有左右两个子结点 */
Tmp = FindMin( BST->Right );
/* 在右子树中找最小的元素填充删除结点*/
BST->Data = Tmp->Data;
BST->Right = Delete( BST->Data, BST->Right);
/* 在删除结点的右子树中删除最小元素*/
} else { /* 被删除结点有一个或无子结点*/
Tmp = BST;
if( !BST->Left ) /* 有右孩子或无子结点*/
BST = BST->Right;
else if( !BST->Right ) /* 有左孩子或无子结点*/
BST = BST->Left;
free( Tmp );
}
return BST;
}
4.1.4 什么是平衡二叉树
-
平均查找长度ASL
-
平衡因子BF：某一结点左右子树的高度差
-
平衡二叉树（AVL树）：对任一结点，BF<=1
4.1.5 平衡二叉树的调整
- 破坏者和被破坏者
- RR旋转
- LL旋转
- LR旋转
- RL旋转
- 下面平衡了上面就平衡了
5.1 堆
5.1.1 什么是堆
- 结构性：用数组表示的完全二叉树
- 有序性：任意结点的关键字是其子树所有结点的最大/最小值（大顶堆/小顶堆）
5.1.2 堆的插入
（1）最大堆的创建
- 完全二叉树用数组存储
（2）最大堆的插入
- 找到最后一个结点，和父节点进行比较，大的话往上挪
void Insert( MaxHeap H, ElementType item )
{ /* 将元素item 插入最大堆H ， 其中H->Elements[0] 已经定义为哨兵 */
int i;
if ( IsFull(H) ) {
printf(" 最大堆已满");
return;
}
i = ++H->Size; /* i 指向插入后堆中的最后一个元素的位置 */
for ( ; H->Elements[i/2] < item; i/=2 )
H->Elements[i] = H->Elements[i/2]; /* 向下过滤结点 */
H->Elements[i] = item; /* 将item 插入 */
}
5.1.3 堆的删除
（1）最大堆删除根节点
- 最后一个元素补充到根节点处
- 如果左右子树有大于根节点的，将根节点往下移
5.1.4 堆的建立
- 将N个元素按输入顺序存入
- 从低层开始，逐步向上，将根节点调整为堆
- 时间复杂度为O(n)
5.2 哈夫曼树与哈夫曼编码
5.2.1 什么是哈夫曼树
-
场景：找到一颗判定树，使得查找效率最高
-
方法：根据结点不同的查找频率来构造有效的搜索树
-
带权路径长度（WPL）：每个叶子结点带有权值，算总和
-
最优二叉树（哈夫曼树）：WPL最小的二叉树
5.2.2 哈夫曼树的构造
- 每次把权值最小的两颗二叉树合并
- 算法，复杂度为O(N*logN)，借助最小堆完成
typedef struct TreeNode *HuffmanTree;
struct TreeNode{
int Weight;
HuffmanTree Left, Right;
}
HuffmanTree Huffman( MinHeap H )
{ /* 假设H->Size 个权值已经存在H->Elements[]->Weight 里 */
int i; HuffmanTree T;
BuildMinHeap(H); /* 将H->Elements[] 按权值调整为最小堆*/
for (i = 1; i < H->Size; i++) { /* 做H->Size-1 次合并*/
T = malloc( sizeof( struct TreeNode) ); /* 建立新结点*/
T->Left = DeleteMin(H);
/* 从最小堆中删除一个结点 ， 作为新T 的左子结点*/
T->Right = DeleteMin(H);
/* 从最小堆中删除一个结点 ， 作为新T 的右子结点*/
T->Weight = T->Left->Weight+T->Right->Weight;
/* 计算新权值*/
Insert( H, T ); /* 将新T 插入最小堆*/
}
T = DeleteMin(H);
return T;
}
5.2.3 哈夫曼编码
- 给定一段字符串，如何对字符编码，使得该字符串编码的存储空间最少
- 不等长编码避免二义性：使用前缀码，将二叉树用于编码
- 将字符频率作为权值，求哈夫曼树
5.3 集合及运算
5.3.1 集合的表示及查找
（1）并查集运算
- 集合并、查某元素属于什么集合
- 电脑联通性问题
（2）集合的存储
- 用树结构表示集合，每个结点代表一个集合元素，根结点代表集合
- 双亲表示法：孩子指向双亲
- 采用数组存储形式
5.3.2 集合运算
- 查找某个元素所在的集合，用根结点表示
- 并运算：分别找到两个元素所在集合树的根节点，如果不同根，将其中一个根节点的Parent设置为另一个根节点的数组下标
6.1 什么是图
6.1.1什么是图
- 表示多对多的关系
- 包含一组顶点V和一组边E
- 不考虑重边和自回路
- 无向图、有向图、带权重的图（网络）
6.1.2 邻接矩阵表示法
-
无向图只用存一半节省空间
-
求邻接点和度方便
-
存稀疏图浪费空间时间
6.1.3 邻接表表示法
6.2 图的遍历
6.2.1 DFS
- 类似树的先序遍历，栈
- 邻接矩阵O(N^2)，邻接表O(N+E)
6.2.2 BFS
- 类似树的层次遍历，队列
- 邻接矩阵O(N^2)，邻接表O(N+E)
6.2.3 图不连通怎么额办
-
连通：从V到W存在一条路径
-
路径：V到W的路径是顶点的集合，若集合中所有顶点不同，称简单路径
-
回路：起点等于终点的路径
-
连通图：图中任意两顶点均连通
-
连通分量：无向图的极大连通子图（极大顶点数和极大边数）
-
强连通：有向图中V和W之间存在双向路径
-
强连通和强连通分量
-
弱连通：不是强连通且变为无向图后连通
-
对于不连通的图，每个连通分量都遍历一遍
7.1 有向图最短路径问题
7.1.1 概述
- 最短路径的源点和终点
- 单源最短路径问题：从某固定源点除法，求到所有其他顶点的最短路径
- 多源最短路径问题：求任意两顶点间的最短路径
7.1.2 无权图的单源最短路径
- 按照递增顺序通过BFS逐步找出到各个顶点的最短路径
void Unweighted ( Vertex S )
{ Enqueue(S, Q);
while(!IsEmpty(Q)){
V = Dequeue(Q);
for ( V 点 的每个邻接点 W )
if ( dist[W]==-1 ) {
dist[W] = dist[V]+1;
path[W] = V;
Enqueue(W, Q);
}
}
}
7.1.3 有权图的单源最短路
- Dijkstra算法，不考虑负值圈
（1）分析
- S={源点s+已经确定了最短路径的顶点vi}
- 对任一未收录的顶点v，dist[v]为s到v的最短路径长度，但该路径长度仅经过S中的顶点
- 路径是按照递增长度的顺序生成的
- 真正的最短路径必然只经过S中的顶点
- 每次从未收录的顶点中选dist最小的收录（贪心）
- 收录v进入s，只可能影响到同v相邻的未收录w的dist值
（2）代码
void Dijkstra(Vertex s) {
while(1){
v=未收录顶点中找dist最小者；
if (v不存在)
break;
collected[v]=true;
for(v的每一个邻接点w){
if(collected[w]==false){
if(dist[w]>dist[v]+E<v,w>){
dist[w]=dist[v]+E<v,w>;
path[w]=v;
}
}
}
}
/*开始算法前，将所有dist置为无穷，s自己置为0，s的邻接点置为权重*/
（3）时间复杂度
- 直接扫描所有未收录顶点：T=O(V^2+E)，对于稠密图效果好
- 将dist存在最小堆中：T=O(VlogV+ElogV)，对于稀疏图效果好
7.1.4 多源最短路算法
（1）Floyd算法
- Dk[i][j]=路径{i->{l<=k}->j}的最小长度
- 最初的D-1是邻接矩阵，不连通的顶点为无穷
- 从Dk-1到Dk:
- 如果k不在i到j的最短路径上，Dk=Dk-1
- 如果k在j到j的最短路径上，Dk[i][j]=Dk-1[i][k]+Dk-1[k][j]
（2）代码
void Floyd()
{ for ( i = 0; i < N; i++ )
for( j = 0; j < N; j++ ) {
D[i][j] = G[i][j];
path[i][j] = -1;
}
for( k = 0; k < N; k++ )
for( i = 0; i < N; i++ )
for( j = 0; j < N; j++ )
if( D[i][k] + D[k][j] < D[i][j] ) {
D[i][j] = D[i][k] + D[k][j];
path[i][j] = k;
}
}
（3）输出路径
- i到j的路径由三段组成，path[i][k]、k和path[k][j]，递归输出
（4）时间复杂度
- T=O(v^3)
8.1 最小生成树问题
8.1.1 Prim算法
（1）什么是最小生成树（MST）
-
无回路，包含图中全部顶点，包含V-1条边
-
任加一条边都会构成回路
-
图连通 = 存在最小生成树
（2）贪心算法
- 每一步都要最好的，即权重最小的边，不能有回路
（3）Prim算法
- 让一颗小树不断长大
（4）代码
void Prim(){
MST = {s}；
while(1){
V = 未收录顶点中dist最小者；
if (V不存在)
break;
dist[V]=0; //收录进来
for(V的每个邻接点W){
if(dist[W] != 0){
if(dist[W] > E<V,W>){
dist[W] = E<V,W>
parent[W] = V
}
}
}
if (MST中的顶点不到V个) //dist为无穷，图不连通
Error(“生成树不存在”)；
}
//初始化：dist[v] = E<s,V>或无穷, parent[s] = -1
//用父亲结点数组表示最小生成树
（5）时间复杂度
- T=O(V^2)
- 用在稠密图中
8.1.2 Krustal算法
- 将森林合并成树
void Kruskal ( Graph G )
{ MST = { } ;
while ( MST到中不到|V|-1条边 && E中还有边 ) {
从E边中取一条权重最小的边E<v,w>; //利用最小堆
将E<v,w>从E中删除;
if(E<v,w>不在MST中构成回路) //利用并查集，看v,w是否在两颗树上
将E<v,w>加入MST;
else
彻底无视E<v,w>;
}
if(MST中不到|V|-1条边 )
Error ( “ 生成树不存在” );
}
- 时间复杂度O(ElogE)，用在稀疏图中
8.1.3 拓扑排序
- AOV (Activity On Vertex)网络：结点代表某一活动，边代表先后关系
- 拓扑序 ：如果图中从V 到W有一条有向路径，则V 一定排在W之前。满足此条件的顶点序列称为一个拓扑序
- AOV 如果有合理的拓扑序，则必定是有向无环图（DAG）
- 算法一
void TopSort()
{ for ( cnt = 0; cnt < |V|; cnt++ ) {
V = 未输出的入度为0 的顶点; //O(V)
if(这样的V在不存在 ) {
Error(“图中有回路”);
break;
}
输出V，或者记录V 的输出序号;
for (V的每个邻接点W)
Indegree[W]––;
}
}
//T=O(V^2)
- 算法二，随时将入度变为0的顶点放到队列中
void TopSort()
{ for (图中每个顶点V)
if (Indegree[V]==0)
Enqueue(V,Q);
while (!IsEmpty(Q)){
V = Dequeue( Q );
输出V ，或者记录V的输出序号; cnt++;
for (V点的每个邻接点 W )
if (––Indegree[W]==0 )
Enqueue( W, Q );
}
if (cnt != |V|)
Error(“图中有回路”);
}
//T=O(V+E)
8.1.4 关键路径问题
- 关键路径是由绝对不允许延误的活动组成的路径，即从头到尾不含机动时间的路径
9.1 简单排序
9.1.1 冒泡排序
（1）算法
void Bubble_sort(ElementType A[], int N){
for (P=N-1; P>=0; P--){
flag=0;
for (i=0; i<P; i++){ //一趟冒泡下来，保证最大数沉底
if(A[i]>A[i+1]){
swap(A[i], A[i+1]);
flag=1;
}
}
if (flag==0) //一趟全程无交换，已有序，退出
break;
}
}
（2）时间复杂度
- O(N^2)
（3）优点
-
可用于链表存储的数值排序
-
稳定性：任意两个相等的数据，排序前后的相对位置不发生改变
9.1.2 插入排序
（1）算法
void insertion_sort(ElementType A[], int N){
for (P=1; P<N; P++) {
Tmp = A[P];
for (i=P; i>0 && A[i-1]>Tmp; i--){
A[i] = A[i-1]; //移出空位
}
A[i] = Tmp; //插入
}
}
（2）时间复杂度
- O(N^2)
9.1.3 时间复杂度下限
-
交换2个相邻元素正好消去1个逆序对
-
任意N个不同元素组成的序列平均具有N(N-1)/4个逆序对
-
任何以交换两元素来排序的算法，平均时间复杂度为Ω(N^2)
-
提高算法效率的关键：每次消去多个逆序对；每次交换相隔较远的元素
9.2.1 希尔排序
- 定义一个增量序列，D(M)>D(M-1)>...>D(1)=1，对序列进行D(k)间隔插入排序
void Shell_sort( ElementType A[], int N )
{ for ( D=N/2; D>0; D/=2 ) { /* 希尔增量序列为D(M)=N/2*/
for ( P=D; P<N; P++ ) { /* 插入排序，把1替换为D*/
Tmp = A[P];
for ( i=P; i>=D && A[i-D]>Tmp; i-=D )
A[i] = A[i-D];
A[i] = Tmp;
}
}
}
- Sedgewick增量序列：{1, 5, 19, 41, 109, … }
9.3.1 选择排序
void Selection_Sort ( ElementType A[], int N )
{ for ( i = 0; i < N; i ++ ) {
MinPosition = ScanForMin( A, i, N–1 );
/* 从A[i]到A[N–1]中找最小元，并将其位置赋给MinPosition */
Swap( A[i], A[MinPosition] );
/* 将未排序部分的最小元换到有序部分的最后位置*/
}
}
- 只用做N次交换
- 关键在于快速找到最小元
9.3.2 堆排序
- 算法一，需要额外O(N)空间
void Heap_Sort ( ElementType A[], int N )
{ BuildHeap(A); /* O(N) */
for ( i=0; i<N; i++ )
TmpA[i] = DeleteMin(A); /* O(logN) */
for ( i=0; i<N; i++ ) /* O(N) */
A[i] = TmpA[i];
}
- 算法二，建立最大堆，将根节点放到最后位置
void Heap_Sort ( ElementType A[], int N )
{ for ( i=N/2; i>=0; i-- ) /* BuildHeap */
PercDown( A, i, N ); //建立一个根节点位于i处，结点数量为N的最大堆
for ( i=N-1; i>0; i-- ) {
Swap( &A[0], &A[i] ); /* DeleteMax */
PercDown( A, 0, i );
}
}
9.4 归并排序
9.4.1 有序子列的归并
/*L = 左边起始位置, R = 右边起始位置, RightEnd = 右边终点位置*/
void Merge( ElementType A[], ElementType TmpA[],int L, int R, int RightEnd )
{
LeftEnd = R - 1; /*左边终点位置。假设左右两列挨着*/
Tmp = L; /*存放结果的数组的初始位置*/
NumElements = RightEnd - L + 1;
while( L <= LeftEnd && R <= RightEnd ) {
if ( A[L] <= A[R] ) TmpA[Tmp++] = A[L++];
else TmpA[Tmp++] = A[R++];
}
while( L <= LeftEnd ) /*直接复制左边剩下的 */
TmpA[Tmp++] = A[L++];
while( R <= RightEnd ) /*直接复制右边剩下的 */
TmpA[Tmp++] = A[R++];
for( i = 0; i < NumElements; i++, RightEnd -- )
A[RightEnd] = TmpA[RightEnd];
}
9.4.2 递归算法
- 分而治之，将序列拆分为一半一半，再归并
void MSort( ElementType A[], ElementType TmpA[], int L, int RightEnd )
{
int Center;
if ( L < RightEnd ) {
Center = ( L + RightEnd ) / 2;
MSort( A, TmpA, L, Center );
MSort( A, TmpA, Center+1, RightEnd );
Merge( A, TmpA, L, Center+1, RightEnd );
}
}
-
时间复杂度T(N)=O(NlogN)
-
统一函数接口
void Merge_sort( ElementType A[], int N )
{
ElementType *TmpA;
TmpA = malloc( N * sizeof( ElementType ) ); //在最外面开辟临时数组的空间
if ( TmpA != NULL ) {
MSort( A, TmpA, 0, N-1 );
free( TmpA );
}
else Error( “ 空间不足" );
}
9.4.3 非递归算法
void Merge_pass( ElementType A[], ElementType TmpA[], int N, int length ) /*一趟归并，length = 当前有序子列的长度 */
{
for ( i=0; i <= N–2*length; i += 2*length )
Merge1( A, TmpA, i, i+length, i+2*length–1 );
if ( i+length < N ) /* 归并最后2个子列 */
Merge1( A, TmpA, i, i+length, N–1);
else /* 最后只剩1列 个子列 */
for ( j = i; j < N; j++ ) TmpA[j] = A[j];
}
void Merge_sort( ElementType A[], int N )
{
int length = 1; /* 初始化子序列长度 */
ElementType *TmpA;
TmpA = malloc( N * sizeof( ElementType ) );
if ( TmpA != NULL ) {
while( length < N ) {
Merge_pass( A, TmpA, N, length );
length *= 2;
Merge_pass( TmpA, A, N, length ); //做两次，保证TmpA拷贝到A处
length *= 2;
}
free( TmpA );
}
else Error( “ 空间不足" );
}
10.1 快速排序
10.1.1 算法概述
- 分而治之，选pivot，划分左右两边，递归
10.1.2 选主元
-
最好情况：每次正好中分，O(NlogN)
-
最坏情况：每次都选中最值，O(N^2)
-
选头中尾的中位数
ElementType Median3( ElementType A[], int Left, int Right )
{
int Center = ( Left + Right ) / 2;
if ( A[ Left ] > A[ Center ] )
Swap( &A[ Left ], &A[ Center ] );
if ( A[ Left ] > A[ Right ] )
Swap( &A[ Left ], &A[ Right ] );
if ( A[ Center ] > A[ Right ] )
Swap( &A[ Center ], &A[ Right ] );
/* A[ Left ] <= A[ Center ] <= A[ Right ] */
Swap( &A[ Center ], &A[ Right-1 ] ); /* 将pivot藏到右边 */
/* 只需要考虑 A[ Left+1 ] … A[ Right–2 ] */
return A[ Right-1 ]; /*返回 pivot */
//三者中最小数放到左边，最大放到右边，中位数放到R-1处
}
10.1.3 算法原理
- 左右指针，pivot位于最右边，左边小或者右边大时移动指针，否则就停住，都停住后交换两个值
- 当左右指针相等时，停止比较，将pivot放到指针处
- 快速排序快在一次排序就将pivot放到了准确的位置，不会再改变
10.1.4 小规模数据的处理
- 使用了递归，小规模数据还不如插入排序快
- 程序中定义一个cutoff阈值，当数据规模小于它时，停止递归，使用插入排序
10.1.5 算法实现
void Quicksort( ElementType A[], int Left, int Right )
{
if ( Cutoff <= Right-Left ) {
Pivot = Median3( A, Left, Right );
i = Left; j = Right – 1;
for( ; ; ) {
while ( A[ ++i ] < Pivot ) { }
while ( A[ ––j ] > Pivot ) { }
if ( i < j )
Swap( &A[i], &A[j] );
else break;
}
Swap( &A[i], &A[ Right-1 ] );
Quicksort( A, Left, i-1 );
Quicksort( A, i+1, Right );
}
else
Insertion_Sort( A+Left, Right-Left+1 );
}
void Quick_Sort(ElementType A[],int N)
{
Quicksort( A, 0, N-1 );
}
10.2 表排序
10.2.1 算法概述
-
存放一本书/电影，直接移动数据代价过大，移动指向其的指针
-
简介排序：定义一个指针数组作为“表”，指向序列，移动指针进行排序
10.2.2 物理排序
- 需要移动序列位置
-
N个数字的排列由若干个独立的环组成
-
挪出A[0]，依次补上A[3]、A[1]、A[5]，然后将A[0]放到A[5]处
-
判断一个环的结束：if( table[i] == i)
10.3 基数排序
10.3.1 桶排序
- 取值有限，N个学生，M=101个不同的成绩值，排序
void Bucket_Sort(ElementType A[], int N)
{
count[] 初始化;
while (读入1个学生成绩grade)
将该生插入count[grade] 链表;
for ( i=0; i<M; i++ ) {
( if ( count[i] )
输出整个count[i]链表;
}
}
- 时间复杂度O(M+N)
10.3.2 基数排序
- 假设N=10，M=1000>>N，桶排序效率低
- 以10-基数为例，按照个位数、十位数、百位数的顺序，依次将序列挂入链表
10.3.3 多关键字的排序
10.4 排序算法的比较
11.1 散列表
11.1.1 引子
-
查找的本质：已知对象找位置
- 有序安排对象：二分查找、二叉搜索树
- 直接计算出对象位置：散列
-
散列查找的两项任务：
- 计算位置：构造散列函数确定关键词存储位置
- 解决冲突：应用某种策略解决多个关键词位置相同的问题
11.1.2 散列表
- 装填因子：设散列表空间大小为m，填入表中元素个数是n，则n/m为散列表的装填因子
- 散列(Hashing)基本思想：以关键字key为自变量，通过散列函数h，计算出对应的函数值h(key)，作为数据对象的存储地址
11.2 散列函数的构造方法
11.2.1 数字关键词的散列函数构造
-
一个好的散列函数要考虑以下两个因素
- 计算简单
- 地址空间分布均匀，减少冲突
-
直接定址法：取关键词的线性函数值
-
取留余数法：h(key)=key mod p, p一般取素数
-
数字分析法：取关键字上比较随机的位作为散列地址
-
折叠法：把关键词分割成位数相同的几部分，然后叠加
-
平方取中法
11.2.2 字符串关键词的散列函数构造
- 取ASCII码
- 移位法
Index Hash ( const char *Key, int TableSize )
{
unsigned int h = 0; /* 散列函数值, 初始化为0*/
while ( *Key != ‘\0’) /* 位移映射 */
h = ( h << 5 ) + *Key++;
return h % TableSize;
}
11.3 冲突处理方法
11.3.1 开放地址法
- 处理冲突的方法
- 换个位置：开放定址法
- 同一位置的冲突对象组织在一起：链地址法
（1）定义
- 一旦产生冲突，就按规则寻找另一空地址
（2）方法
11.3.2 线性探测
- 线性探测易形成聚集
- 散列函数h(key)=key mod 11，因此，分为11类分析
11.3.3 平方探测
- 定理显示，如果散列表长度是某个4k+3形式的素数时，平方探测法可以探查到整个散列表空间
11.3.5 平方探测的实现
- 懒惰删除：增加一个删除标记(Deleted)，而并不是真正删除它，以便查找时不会“ 断链 ”，其空间可以在下次插入时重用。
typedef struct HashTbl *HashTable;
struct HashTbl{
int TableSize;
Cell *TheCells;
}H;
Position Find( ElementType Key, HashTable H ) /* 平方探测*/
{
Position CurrentPos, NewPos;
int CNum; /* 记录冲突次数 */
CNum = 0;
NewPos = CurrentPos = Hash( Key, H->TableSize );
while( H->TheCells[ NewPos ].Info != Empty &&
H->TheCells[ NewPos ].Element != Key ) {
/* 字符串类型的关键词需要 strcmp 函数!! */
if(++CNum % 2){ /* 判断冲突的奇偶次 */
NewPos = CurrentPos + (CNum+1)/2*(CNum+1)/2;
while( NewPos >= H->TableSize )
NewPos -= H->TableSize;
} else {
NewPos = CurrentPos - CNum/2 * CNum/2;
while( NewPos < 0 )
NewPos += H->TableSize;
}
}
return NewPos;
}
- 再散列，装填因子过大时，查找效率下降，需要加倍扩大散列表，该过程叫再散列
11.3.6 分离链接法
- 将相应位置上冲突的所有关键词存储 在同一个单链表中
typedef struct ListNode *Position, *List;
struct ListNode {
ElementType Element;
Position Next;
};
typedef struct HashTbl *HashTable;
struct HashTbl {
int TableSize;
List TheLists;
};
Position Find( ElementType Key, HashTable H )
{
Position P;
int Pos;
Pos = Hash( Key, H->TableSize ); /*初始散列位置*/
P = H->TheLists[Pos]. Next; /*获得链表头*/
while( P != NULL && strcmp(P->Element, Key) )
P = P->Next;
return P;
}
11.4 散列表的性能分析
-
影响冲突的因素：散列函数是否均匀，处理冲突的方法，装填因子
-
散列法的查找效率期望是常数O(1)
-
散列表应用：文件中单词词频统计
12.1 串的模式匹配
（1）c的库函数strstr
-
char *strstr(char *string, char *pattern)
-
strstr返回子串头指针
-
时间复杂度T=O(n*m)
（2）KMP算法
-
match函数的子列是可以交叉的
-
当第j个匹配不上时，不用移动string指针，只用将pattern指针移动到match[j-1]处，从该处往后再比较
-
时间复杂度T=O(n+m)
（3）KMP的代码
Position KMP( char *string, char *pattern )
{
int n = strlen(string);
int m = rlenrn t st e (patte );
int s, p, *match;
match = (int *)malloc(sizeof(int) * m);
BuildMatch(pattern, match);
s = p = 0;
while (s<n && p<m) {
if (string[s]==pattern[p]) { s++; p++; }
else if (p>0) p = match[p-1]+1;
else s++;
}
return (p == m)? (s-m) : NotFound;
}
（4）BuildMatch的实现
（5）BuildMatch的代码
void BuildMatch(char *pattern, int *match)
{
int i, j;
int m = strlen(pattern);
match[0] = -1;
for (j=1; j<m; j++) {
i = match[j-1];
while ((i>=0) && (pattern[i+1]!=pattern[j]))
i = match[i];
if (pattern[i+1]==pattern[j])
match[j] = i+1;
else match[j] = -1;
}
}
//时间复杂度T=O(m)