@Bruce1Tone 2020-12-21T13:56:59.000000Z 字数 15334 阅读 834

数据结构服用手册

计算机

绪论

数据结构

基本定义

数据结构包括：

逻辑结构：抽象思考上的

存储结构：实际存储

数据的运算

其中，存储结构是逻辑结构在计算机的映射，所以存储结构不能独立于逻辑结构存在。

抽象数据类型ADT：三元组：{数据对象，数据关系，基本操作集}

逻辑结构

常见的有四种：

集合
线性
树
图

算法

问题规模为n

一般规律：

语言越高级，执行同样算法的效率越低

时间复杂度

常见时间复杂度排序：

表示为 $T(n) = O[f(n)]$ ：

$1 < \log_2n < n < nlog_2n< n^2 < n^3 < 2^n < n! < n^n$
其中，相同问题规模，上式越小的一定越优

空间复杂度

一般空间复杂度与算法无关，因此只算除了输入和程序之外所需要的额外空间

算法原地工作：所需辅助空间为常量，即 $O(1)$

线性表

基本知识

定义

线性表定义：

元素数据类型相同（存储空间大小一样）

有限序列（有先后）

操作函数

部分：

操作函数	操作	解释
LocateElem(L , e)	按值查找	在表L中查找e，并返回索引
GetElem(L , i)	按位查找	在表L中查找索引为i的元素，并返回其值
ListInsert(&L , i , e)	插入	位置i处插入值为e的元素
ListDelete(&L , i , &e)	删除	删除索引为i的元素，并将他放在e中
Empty(L)	判空	如果为空表，返回True

顺序表

定义

顺序表定义：

用连续地址的存储单元依次存储线性表中数据

特点：逻辑顺序与物理顺序相同，逻辑相邻=物理相邻

存取方式：随机存取（给了坐标就可以随意访问）

补充：
顺序存取：访问第N时，必须要访问前N-1个元素
随机存取：可直接按坐标访问

其中，顺序表在物理层常用数组来存储

操作

操作	描述	算法	平均移动次数	时间复杂度
插入	在位置 i 插入	i 之后的元素全部后移一位	$\frac n 2$	$O(n)$
删除	在位置 i 删除	i 之后的元素全部前移一位	$\frac {n-1}2$	$O(n)$
按值查找	查找第一个值为e的元素	顺序遍历对比	$\frac{n+1}2$	$O(n)$

链表

基本信息

常见的有：单链表、双链表、循环链表、静态链表

头节点

链表的第1个结点，其中存储的信息一般为空，或者存储长度等信息。

头指针和尾指针

头指针：指向链表的第一个结点（有表头的就指向表头）
尾指针：指向链表的最后一个结点

image_1enq5qjiu1biu4891tumj8h1rt9.png-84.7kB

单链表

单链表的基本结构

1.本结点数据data
2.后继节点指针*next

最后一个指针指向NULL

两种建立方法：头插法、尾插法

头插法：最简单，但是是逆序
尾插法：需要尾指针

删除操作：
image_1enq6i6u41cbg3j712oi1u0v110213.png-227kB

双链表

双链表结构：

前驱结点指针：*prior

该节点数据：data

后继节点指针：*next

循环链表

循环链表定义：

与普通的单链表、双链表相似，只不过首尾相接

静态链表

静态链表：

借助数组来定义：
用一块连续的内存存储，进行相对编号
指针存储的信息是相对位置int类型，即数组下标

需要提前分配内存

本章小结

各种链表的对比
image_1enq84ee4lo419cb10gn18urrf41g.png-213.5kB

image_1enq8qggfnj82ih1bm711in1uf41t.png-362.7kB

栈和队列

栈的两种存储结构

定义：

栈是限制了存取方式的线性表，其逻辑结构本质还是线性表

#例如以下的顺序栈（数组实现）：
struct Stack{
    int data[size];     #存放栈的内容
    int top;            #存放栈顶指针（下标）
}

如果是链栈，则为*top指针

顺序栈

顺序存储的栈
一般是数组实现

共享栈

即两个栈共用一个数组，一个以数组头为栈底，一个以数组尾为栈底
当top1+1=top2时，即两个栈顶相邻，即判断为栈满

链栈

链式存储的栈
一般是单链表实现

注意！表头才是栈顶，表尾是栈底！

操作

bool StackEmpty(&s)         #判断栈是否为空，top==-1时，栈空
bool Push(&s,x)             #元素x进栈s中，成功入栈返回True
bool Pop(&s,&x)             #弹出s的栈顶元素，并放在x中，成功弹出返回True
bool GetTop(&s,&x)          #获取栈顶元素，并放在x中

注意，push时可能会出现栈满，应该先检查是否满并操作。
同理，pop时可能会空栈报错，应该先检查是否为空
初始化时，top=-1

队列

队列定义

Queue简称队，只能在队头出队，队尾入队
遵循规则FIFO，即First In First Out，先进先出

结构定义

struct Queue{
    ElemType data[size];        #队列元素
    int front,rear;             #front队头，rear队尾
}

初始状态为front=rear=0
入队：rear+1
出队：front+1

操作

QueueEmpty(Q)           #判断队Q是否为空，如果是返回True
EnQueue(&Q,x)           #入队，将x元素入队到Q的对尾
DeQueue(&Q,&x)          #离队/出队，将Q队头元素弹出并存放在x中
GetHead(Q,&x)          #读取队头元素，并将之赋给x

顺序队列

用数组表示

循环队列

数组表示，使用%来重复利用一个数组空间

注意：
对于循环队列，有三种区分队满队空的方式：

最普遍：rear指向下一个空位
a. 队空：front=rear
b. 队满：(rear+1)%n=front
c. 队里有m个元素：rear=front+m，其中rear指向的是一个空的位置
d. 队的容量：n-1

增加变量size存储队列元素个数:
a. 队空：size=0
b. 队满：size=n
c. 队容量：n

增加变量tag来区分：
a. tag=0时，如果因为删除触发front=rear，则队空
b. tag=1时，如果因为插入出发front=rear，则队满
c. 队容量：n

链队列

好处：

不存在队列溢出，动态分配内存

基本组成：

有队头指针front和队尾指针rear

对于无头结点的链队：
a. 初始化状态：front指向NULL，rear指向NULL
b. 判空：front==rear==NULL

对于有头结点的链队：
a. 初始化状态：front指向头结点，rear也指向头结点
b. 判空：front==rear

压缩矩阵存储

存储方式：

按行优先

按列优先

用数组存储的压缩矩阵：

对称矩阵A[n*n]：
a. 需要空间：上三角的个数，即1+2+...+n

三角矩阵A[n*n]：
a. 上三角需要空间：上三角+常数位置1，即1+2+...+n+1
b. 下三角：与上三角相同

三对角矩阵A[n*n]：
a. 需要空间：3n-2

稀疏矩阵：

有两种存储方法：

三元组：(row,volumn,value)

十字链表法

栈和队列的应用总结

栈的应用：
a. 递归调用需要栈
b. 函数调用，函数的局部变量使用栈存储
c. 括号匹配
d. 中缀表达式转后缀表达式
e. 迷宫求解
f. 进制转换

队列的应用：
a. 层次遍历/广度优先搜索
b. 页面替换算法
c. 缓冲区

串

串的定义

串：

string：是由0个或多个字符组成的有限序列
一般记为:s = 'xxx'
n=0时，s为空串

空格串：

由1个或者多个空格组成的串，不等于空串

串的三种存储

定长顺序存储

地址连续，每个串变量的长度固定

struct String{
    char ch[size];      #size为最大长度，超过部分直接被截断
    int length;         #length为实际长度，小于等于size
}

堆分配存储

地址连续，动态分配内存，使用malloc()和free()动态分配

struct String{
    char *ch;       #指向串的基地址的指针*ch
    int length;
}

块链存储

由链表存储，每个结点定长
当一个结点占不满时，用#占位

串的基本操作

代码	操作	说明
StrAssign(&T , chars)	赋值	把`chars`赋值给`T`
StrCopy(&T , S)	复制	把`S`复制给`T`
StrCompare(S ,T)	比较	如果`S`>`T`，则返回值>0；如果`S`=`T`，则返回值=0；如果`S`<`T`，则返回值<0
SubString(&Sub , S , pos , len)	求子串	求串`S`的从`pos`位置开始，长度为`len`的子串并存放在`Sub`中
Concat(&T , S1 , S2)	合并串	`T`=`S1`+`S2`
Index(S , T)	定位子串	在`S`中找有无等于`T`的子串？如果有，则返回第一次出现的位置如果没有，则返回0
ClearString(&S)	清空	清空`S`为`空串`
DestroyString(&S)	销毁	销毁`S`，并释放内存

串的模式匹配

参考资料

模式匹配:

即子串的定位操作
其中子串又叫模式串

简单匹配

对于长度为n的主串，和长度为m的模式串

暴力求解，一一匹配

每失配一次
a. 主串指针：退回到该趟匹配起点 + 1
b. 模式串指针：退回到首位

时间复杂度：
为O(nm)

KMP算法

对于长度为n的主串，和长度为m的模式串

每失配一次，即模式串第j个字符失配
a. 主串指针：不移动
b. 模式串指针：回退到next[j]位置继续匹配

时间复杂度：
为O(m+n)

注意！

next需要整体+1：当模式串序号从1开始时，需要整体+1

next不需要整体+1：当模式串序号从0开始时，不需要整体+1

重点在于next值的求法：

以下方法都是计算的next数组+1后的值

next的手算法（考试用）

next的机算法（代码实现）

nextval的计算法（改进后的KMP）

树与二叉树

两种二叉树

完全二叉树：只缺少最右下角的几个元素
满二叉树：每层全满

二叉树的存储

顺序存储：适合完全二叉树和满二叉树
链式存储：适合所有

二叉树的性质

非常重要：

结点的度：该节点孩子个数
度为0的结点个数与度为2的结点个数关系：
$n_0 = n_2 + 1$

二叉树的遍历

三种遍历之后，叶子结点的先后顺序都是一样的
知道两种遍历序列，反求二叉树：中序序列是必需的
如果只知道先序和后序，则无法确定孩子在左还是右，得到的二叉树不唯一

先序遍历

先序遍历：
$根左右$
$根 > 左 > 右$
递归算法的时间复杂度为 $O(n)$ ，递归工作栈的栈深度=树的高度h

#先序遍历递归法遍历:
PreOrder(T):
    if T != NULL:
        visit(T)
        PreOrder(T->left)
        PreOrder(T->right)
/

PreOrder(T):
    InitStack(S)
    p = T
    while(p != NULL || !IsEmpsty(S)):
        if(p != NULL):
            visit(p)
            Push(S,p)
            p = p->left
        else:
            Pop(S,p)
            p = p->right

中序遍历

中序遍历：
$左根右$
$左 > 根 > 右$

#中序遍历 非递归方法:（栈）
InOrder(T):
    InitStack(S)
    p = T       #p是遍历指针
    while(p!=NULL || !IsEmpty(S)):
        if (p != NULL):
            Push(S,p)
            p = p->left
        else:
            Pop(S,p)
            visit(p)
            p = p->right

中序遍历
非递归方法描述
重复执行以下直到栈空or遍历结束：

if p有左孩子：
左孩子入栈，并一路向左

否则：
栈顶出栈，并访问栈顶元素
然后从栈顶元素向右走

后序遍历

后序遍历：
$左右根$
$左 > 右 > 根$
非递归实现比较繁琐

线索二叉树

X序线索二叉树构建规则：

三种线索二叉树的作用：

先序线索二叉树：查后继结点快
后续线索二叉树：查前驱方便
中序线索二叉树：查前查后都方便

树、森林

双亲表示法

顺序存储，每个节点存双亲的位置

孩子表示法

链式存储，每个节点后接上自己的孩子的位置

孩子兄弟表示法

最常用，树转二叉树的方法

二叉链表存储：
1. 孩子在左子树
2. 兄弟在右子树

森林转二叉树

第一棵树作为root

各个树的根结点是兄弟结点

森林变成T1为root的树，然后二叉树化：左孩子右兄弟

二叉排序树（二叉查找树）BST

基本规则

$左根右$
$左 < 根 < 右$
其左右子树也分别是两棵二叉排序树
进行中序遍历可以得到递增序列

插入

if TreeEmpty:
作为根节点

if 大于p：
向右

if 小于p：
向左

直到插入的数是叶子节点

删除

删除操作的文字描述：

delete z：

if z是叶子结点:
直接删除

if z只有一个子树：
子树直接替代z，即原来指向z的直接指向z->child

if z有左右子树：
a. 找到z的直接后继z->next，然后用后继替代z
b. delete z->next

伪代码：

delete(z):
    if z->left == NULL && z->right == NULL:
        free(z)
    elif z->left == NULL:
        z->pre->next = z->left
        free(z)
    elif z->right == NULL:
        z->pre->next = z->right
        free(z)
    elif z->left != NULL && z->right != NULL:
        z->data = z->next->data
        delete(z->next)

平衡二叉树

定义：

平衡二叉树：左右子树深度相差小于等于1
公式

设构建h层平衡二叉树需要的最小结点数为 $n_h$ ，则有递推式：

$n_h = 1 +n_{h-1} + n_{h-2}$

平衡二叉树的插入

左旋：

我变成你爹，我的左孩子变成你的右孩子

右旋：

我变成你爹，我的右孩子变成你的左孩子

LL

插入路径为A的左-左：

RR

插入路径为A的右-右：

LR和RL

哈夫曼树

即带权路径长度WPL最小的树

不存在度为1的结点

构建过程

对于n个带权结点

构建n棵树的森林F

在F中选择根节点权值最小的两棵树：
a. 新建结点
b. 把刚刚两棵树接到该结点上，并且该结点权值等于两孩子之和

重复2，直到F变成一棵树，得到哈夫曼树

哈夫曼编码

要求：
都得是前缀编码

前缀编码：即没有一个编码是另一个编码的前缀

注意：

哈夫曼编码一定是前缀编码
但前缀编码不一定是哈夫曼编码（哈夫曼是效率最高的前缀编码）

构建过程：

对于需要编码的n个字母，分别统计其出现的频数，作为结点权值

构建哈夫曼树

从root开始，查找到结点的路径：左记0，右记1
例如：

b的路径是LLRLL，则编码为00100
c的路径是LR，则编码为01

图

图的基本概念

图G：

顶点集V：不能为空，至少一个
边集E：可以为空

有向图和无向图：

有向图：<a,b>
无向图：(a,b)

简单图：

满足以下：
1. 无重复边
2. 无自己到自己的边

多重图：

满足其一或同时满足：
1. 有重复边
2. 有自己到自己的边

完全图（简单完全图）
定义：

每两个顶点间都有通路的简单图
对于无向图：两点间一条边
对于有向图：两点间一来一回

生成子图

包含原图所有顶点的子图

连通图和连通分量

对于无向图：
1. 连通图：所有顶点都连通的图
2. 连通分量：最大连通子图（不仅包含所有点，还要包含所有边）

极大、极小连通子图

极大连通子图：保证连通，且包含所有的边
极小连通子图：保证连通的情况下边最少

强连通图

对于有向图：
1. 强连通图：所有顶点u和v都有路径<u,v>和<v,u>（但不一定两个点之间有弧）
2. 强连通分量：最大强连通子图（只有单边的顶点不包含在内）

稀疏图

边少的图
反之就是稠密图

生成树、生成森林

生成树：

包含连通图全部顶点的极小连通子图（即两点间有一条边就够了）

生成森林：

由多个连通分量分别的生成树组成的森林

顶点的度

无向图：

度：顶点上连的几条边

有向图：

入度：指进来的条数
出度：指出去的条数

简单路径，简单回路

简单路径：

顶点不重复的路径（除了首尾重复一次）

简单回路：

顶点不重复的回路（除了首尾重复一次）

图的存储

邻接矩阵

稠密图（边多）适合
无向图的邻接矩阵是对称矩阵，可以压缩存储。只存储三角矩阵
带权的网，无通路时存为 $\infty$

补充：

若图G的邻接矩阵为A，则 $A^m$ 的元素 $a_{ij}$ 表示：

从顶点i到j，长度为m的路径有 $b_{ij}$ 条

邻接表

稀疏图（边少）适合
组成：
将该顶点的所有邻接点接在该结点的后面
1. 顶点表：顶点值data+边表头指针firstarc
2. 边表：邻接点域adjvex+指针域nextarc

对于无向图：顶点后的是所有邻边
对于有向图：顶点后的只有出去的边

十字链表

存有向图

邻接多重表

存无向图

图的遍历

广度优先BFS

相当于层次遍历
时间复杂度：

邻接矩阵： $O(V^2)$
邻接表： $O(V+E)$ ，空间复杂度 $O(V)$

非递归算法，需要借助队列

伪代码：

InitQueue(Q)
for i in range(len(G.v)):
    visited[i] = False          #初始化所有点为未访问
//先访问第一个点
visited[root] = True
for i in G.v:
    if visited[i] == False:
        BFS(G,i)
def BFS(G,root):
    visit(root)
    visited[root] = True
    EnQueue(Q,root)
    while(!IsEmpty(Q)):
        Dequeue(Q,root)
        for i in root.neighbor:
            if visited[i] == False:
                visit(i)
                visited[i] = True
                EnQueue(Q,i)

文字描述：

从root出发，访问root，root入队Q

如果Q不为空，则进行以下循环：
a. 出队，弹出元素到v
b. 检查v的所有邻接点，没有访问过的邻接点全部入队

以上过程可以完成对一个连通分量的BFS，重复多次，对图G的所有连通分量BFS

BFS应用

当边不带权值时，求单源最短路径：

在BFS过程中，深度每增加一层，该层的distance就+1

深度优先DFS

相当于先序遍历
时间复杂度：

邻接矩阵： $O(V^2)$
邻接表： $O(V+E)$ ，空间复杂度 $O(V)$

递归算法，需要借助递归工作栈

伪代码：

for i in G.V:
    visited[i] = False
for i in G.v:
    if visited[i] == False:
        DFS(Q,i)
def DFS(Q,root):
    visit(root)
    visites[root] = True
    for i in root.neighbor:
        if visited[i] == False:
            DFS(G,i)

文字描述：

从root出发，先访问root

检查root的每一个邻接结点：
a. if该点没访问过，则从该点开始DFS

即：只要有路就向前，没路了再退回上一个分叉路

总结

邻接矩阵：BFS和DFS的结果是唯一的
邻接表：结果不唯一

最小生成树

Prim算法

Prim算法描述：
1. 选定起点root，此时访问集T={root}
2. 在T和非T之间，找一条最短的边，并将该边和顶点加入到T
3. 重复以上过程n-1边，构建n-1条边，得到最小生成树

Kruskal算法

Kruskal算法描述：
1. 找到图中最小的边，加入T
2. 重复以上过程n次，得到最小生成树

两种算法对比

算法	时间复杂度	适用范围	备注
Prim普里姆	$O(V^2)$	边很多，顶点少
Kruskal克鲁斯卡尔	$O(E\log E)$	边稀疏，顶点多	用`堆`存储边集

最短路径

Dijkstra算法

求单源到各个点的最短路径

参考资料

注意：
边上带有负权值时，不能使用Dijkstra算法。
时间复杂度是 $O(V^2)$

文字描述：

dist[i]存储从v0到vi的最短路径，并初始化

集合S初始选定一个起点root，即S={root}

在非S中找到一条到v0最小的边，并把其顶点v1包括进S

更新dist[i]，其中
$\mathrm{dist}[i] = \min\bigg\{\{\mathrm{dist}[i]\}, \{\mathrm{dist}[v_1] + (v_1,i)\} \bigg \}$

重复n-1次，使所有顶点都包含在S内，结束。其中path[i]存放了从v0到vi的最短路径的前驱

S内都是最短路径找好了的顶点

Floyd算法

求任意两点的最短路径

参考资料

注意：
时间复杂度是 $O(V^3)$
可以有负权，但是不能有带负权的回路
无向图和有向图都适用

文字描述：

初始邻接矩阵记为 $A_0$

第1次更新：
a. 两点间允许通过v1中转的话，更新 $A_0$
b. 更新规则是：
$a_{ij} = \min \bigg\{ a_{ij} , \{a_{i1} + a_{1j}\} \bigg\}$
c. 运行 $V^2$ 次，更新完后，矩阵变为 $A_1$

...

第m次更新，更新规则为：
$a_{ij} = \min \bigg\{ a_{ij} , \{a_{im} + a_{mj}\} \bigg\}$
更新完的矩阵变成 $A_m$

更新n次，得到矩阵 $A_n$

$A_n$ 就存储了任意两点之间的最短路径长度

拓扑排序

DAG图

DAG：有向无环图，可以把二叉树的相同子项公用，就变成了DAG图

拓扑排序

定义：
一个有向无环图满足以下条件，称为该图的一个拓扑排序：
1. 每个顶点只出现一次
2. A在B前，则不存在B到A的路径（但也不一定存在A到B的路径）

AOV网

用V顶点表示活动的DAG图，记为AOV网
边：仅表示先后顺序

每个AOV网，都有一个或多个拓扑排序序列

拓扑排序算法：

选择AOV网中，无前驱的结点v1，输出v1

在AOV网中删除v1，并删除他出发的所有边

重复1、2，直到：
a. AOV网为空（正常情况）
b. 不存在无前驱的结点了（说明肯定有环）

对于一般的图来说，如果邻接矩阵三角矩阵，则存在拓扑排序。反之不一定

逆拓扑排序：

在AOV网的拓扑排序过程中，选择无后继的点

AOE网与关键路径

参考资料

AOE网：

边：表示活动，即过程耗时
顶点：表示事件，即表示之前的活动都完成了，后面的活动可以开始了

特点：每个事件需要等他的所有前驱活动都完成了才能结束，并开始后面的活动

事件的最早发生时间Ve

从源点v1到事件vk：
Ve[k]表示了：从v1到vk所有路径里最长的一条的距离即Ve[k]的最早开工时间

Ve[k]代表了，保证vk的前驱事件全部都做完了的时间
再早的话前面的活动就没做完了

计算方法：

初始化所有时间的Ve[i]=0

去掉入度为0的点（源点，即起始点）：
a. 从源点v1开始，输出v1
b. 计算v1的所有后继的Ve值，计算方法是：Ve[k]=max{Ve[k],Ve[1]+<1,k>}

重复第2步，直到所有的顶点都输出

事件的最迟发生时间Vl

Vl[k]表示了：在不推迟整个工期的情况下，vk的最晚开工时间

即，Vl[k]为事件vk的各个后续事件，倒推回来必须开工的时间里最早的一个
再晚的话，后面的活动就做不完了

计算方法：

初始化所有事件的Vl[k]=Ve[k]

用栈S记录拓扑排序，栈顶为排序的最后一个元素
a. 栈顶元素vm出栈并输出
b. 计算vm的所有前驱事件的Vl值，计算方法是：Vl[k]=min{Vl[k],Vl[m]-<k,m>}

重复第2步直到所有元素都出栈了

活动的最早发生时间Ee

Ee[k]表示了：活动k=<k.begin,k.end>最早能开始的时间，也是k的头事件k.begin最早发生的时间Ve[k.begin]

再早的话，k.begin事件就还没发生，没有条件进行k活动

计算方法：

Ee[k]=Ve[k.begin]

活动的最晚发生时间El

El[k]表示了：活动k最晚多久必须开始，也是k的尾事件k.end最晚发生时间-k需要的时间

再晚的话，k的后继活动就会没法按时展开推迟工期了

计算方法：

El[k]=Vl[k.end]-len(k)

关键路径与关键活动

关键路径：整个工程开始到结束耗时最长的一条路径
关键活动：关键路径上的活动

所有El[k]=Ee[k]的活动k都是关键活动
即该活动最早开始时间和最晚开始时间一样，也就是说，时间一到必须立马开工不能拖延
一旦关键活动发生拖延，整个工程就会延期
缩短工期：必须所有的关键路径都同时缩短，工期才能缩短

最短完成时间

最短完成时间=关键路径的长度=最大路径长度的一条路径
表示整个工程最早什么时候能完成

查找

查找表/查找结构

需要满足的操作：
1. 增
2. 删
3. 查
4. 改

动态与静态查找表

静态查找表：适合顺序查找、折半查找、散列查找等
动态查找表：适合二叉排序树、散列查找等

顺序查找

无序线性表的顺序查找

平均查找长度：

$成功$
$ASL_{成功}=\frac{n+1} 2$
不成功平均长度：

$不成功$
$ASL_{不成功} = n+1$
对于线性链表只能顺序查找

有序线性表的顺序查找

查找成功的ASL一样
查找失败的结果优化了一下，如果查找的元素已经大于关键值，则返回没找到

$成功不成功$
$ASL_{成功} = \frac{n+1} 2 \\ ASL_{不成功} = \frac n 2 + \frac n {n+1}$

折半查找/二分查找

必须有序，且只能顺序存储
定义指针low high mid
其中：
$mid = \lfloor \frac {low + high} 2 \rfloor$
即向下取整
判定过程中，若key ≠ mid，则：

$或者$
$high = mid - 1 或者 low = mid + 1$
他的判定过程是一个平衡二叉判定树
平均查找长度为
$ASL \approx \log_2(n+1) - 1$
时间复杂度为 $O(log_2n)$

分块查找/索引顺序查找

块内无序，块间有序
每块记录了块内最大元素和首元素地址
是顺序查找和折半查找的结合
设有b块，每块s个元素，则 $n=bs$
块间折半查找，块内顺序查找，平均查找长度为：
$ASL = \lceil \log_2{b+1} \rceil +\frac {s+1} 2$
其中，当 $s = \sqrt n$ 时，平均查找长度最小：
$ASL_{min} = \sqrt n + 1$

B树（不考）

参考资料

散列查找/哈希查找

基本概念

散列函数：即hash()，将关键词映射到地址的函数，Hash(key)=Addr
冲突/碰撞：n个不同的key对应同一个hash值，也就是同一个地址
散列表：是一种数据结构，可以根据关键字直接访问。他构成了关键字和存储地址的直接映射

散列函数构造方法

直接定址

hash(key) = key
优点：不会冲突，计算简单
缺点：浪费空间，空位多
适用于：基本连续

除留余数法(最常用)

hash(key) = key%p
关键在于选好质数p

数字分析法

选取n位数中的m位，作为散列地址
要求数码在这m位中分布较均匀
适合：已知关键字的集合，如果更换了关键字，需要重新构造hash()

平方取中法

取key的平方值的中间几位直接作为散列地址

处理冲突的方法

1. 开放定址法

开放定址法：即空闲地址对同义词和非同义词都开放
数学递推公式是：
$H_i = (\mathrm {hash}(key) + d_i)%m$

注意：

在开放定址法中，不能随便删除元素，需要先做删除标记，进行逻辑删除
再进行

线性探测法：

d = 0,1,2,3,4...

查找成功也至少有1次探测！

缺点：容易产生堆积或聚集

平方探测法：

d = $0^2,1^2,-1^2,2^2,-2^2...,k^2,-k^2$

其中 $k\leq m / 2$

其中m必须是可以表示为4k+3的一个质数

又叫二次探测法

优点：较好处理堆积的问题

缺点：访问不满，但是至少能探测一半

再散列法：

d_i = hash_2(key)

散列函数为 $\mathrm{Addr} = \bigg[\mathrm{hash}(key) + i × \mathrm{hash_2}(key)\bigg] \% m$

i为冲突次数

最多经过m-1次探测，就会遍历表中的所有位置

伪随机序列法

即d为伪随机数

2. 链接法

把所有的同义词存储在一个线性链表中
适用于：经常插入和删除的表

散列查找的性能

查找效率取决于：

散列函数

处理冲突的方法

装填因子a：
$表中记录数散列表长度$
$\alpha = \frac{表中记录数n}{散列表长度m}$

排序

注意：稳定与否并不能影响算法的优劣，他只是性质

插入排序

时间复杂度都是 $O(n^2)$ ，都是内部排序
包括：

直接插入排序

前面i个数的序列有序，新元素在前面的有序序列顺序查找

有a[0]作为哨兵，不存储信息

稳定

可顺序存储，可链式存储

折半插入排序

与直接插入法一致，只不过在有序表中采用折半查找位置

有a[0]作为哨兵，不存储信息

稳定

只能顺序存储

希尔排序(缩小增量排序)

方法：

间隔为d的一组数据内部进行直接插入排序

缩小间隔为d-1，重复步骤1

a[0]不是哨兵，仅作为暂存单元

不稳定

只能顺序存储

交换排序

包括：

冒泡排序

依此比较相邻位，若为逆序则交换，相等不交换

每次排序有1个元素到最终位置

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

最多比较次数： $\frac {n(n-1)} 2$

最多移动次数： $\frac {3n(n-1)} 2$

快速排序

参考资料

趟：所有未归位元素处理一遍

现在剩下n个无序子序列，则下一趟就要有n个元素归位（绝对位置）

空间效率

最好： $\log_2n$ ，也就是递归栈的最小深度

最坏： $n$ ，递归栈最大深度

平均： $O(\log_2n)$

时间效率

最好/平均： $O(n\log_2n)$

最坏： $O(n^2)$

不稳定

是所有内部排序算法中平均性能最优的算法

适用情况：

最好：枢轴元素每一次都将子序列划分成等长两个序列

最坏：基本有序

选择排序

包括：

简单选择排序

类似于冒泡排序，每一趟选择i后面的最小值，与i交换位置。

与初始序列无关！！

i之前都为有序，之后都为无序

时间效率：

$O(n^2)$

比较次数： $\frac {n(n-1)} 2$

移动次数： $\leq 3(n-1)$

不稳定

堆排序

参考资料

堆概念定义：一棵顺序存储的完全二叉树，并且爸爸永远比儿子大/小

大根堆：爸爸永远比儿子大

小根堆：爸爸永远比儿子小

算法过程：

建立初始堆：
将原始数据填入完全二叉树，并从顺序的末尾元素开始检查
有不符合堆的子树，就交换根和最大/小孩子的值，并依此检查所有元素

输出根节点，作为排序的第一个元素。
然后将最后一个元素移到根节点位置，再次检查调整堆

重复以上步骤，直到堆空

空间效率： $O(1)$

时间效率：

总： $O(n\log_2n)$

建堆： $O(n)$

调整堆：共调整 $n-1$ 次，每次时间复杂度为 $O(h)$ ，即 $O(\log_2n)$

不稳定

归并排序和基数排序

2路归并排序

算法详解：每一趟将相邻2个子序列合并，直到只剩一个序列

Merge(A1,A2)合并 = A：

合并A1和A2时，先将A1和A2存在辅助空间B

然后分别取A1和A2的第一个元素进行对比，小的取出放进A

空间效率：n个单元， $O(n)$

时间效率：

总： $O(n\log_2n)$

每趟归并 $O(n)$ ，一共进行 $\lceil \log_2n \rceil$ 趟归并

稳定

基数排序

一般有两种，最高为优先MSD和最低位优先LSD，其中默认为最低位优先

算法详解：

数码是k进制的，则按照数码划分成k个子序列

分配：先按最低位，将元素放到对应的子序列上

整理：依此输出每个子序列上的元素，同序列要分先来后到

直到进行到最高位，最后一次输出得到升序序列

空间效率： $O(k)$

时间效率：

总： $O(d(n+k))$ ，其中d为数码的位数，k为数码的进制

有d位数，就要进行d趟分配+收集
其中，分配为 $O(n)$ ，收集为 $O(k)$

稳定的，与初始序列无关

内部排序的比较

算法种类	平均时间复杂度	空间复杂度	稳定吗	适用于	最好时间复杂度	最差时间复杂度
直接插入	$n^2$	1	稳定	顺序、链式存储	$n$	$n^2$
冒泡	$n^2$	1	稳定	顺序、链式存储	$n^2$	$n^2$
简单选择	$n^2$	1	不稳定	顺序、链式存储	$n^2$	$n^2$
希尔	约 $n^{1.3}$	1	不稳定	仅顺序	？	$n^2$
快速排序	$n\log_2n$	递归栈： $\log_2n$	不稳定	顺序	$n\log_2n$	$n^2$
堆排序	$n\log_2n$	1	不稳定	顺序	$n\log_2n$	$n\log_2n$
2路归并	$n\log_2n$	n	稳定	顺序	$n\log_2n$	$n\log_2n$
基数排序	$d × (n + k)$	k	稳定	顺序	$d × (n + k)$	$d × (n + k)$

C/C++相关

三种传递（值传递、指针、引用）

值传递：函数内都是副本，不影响本体
指针：指向实际内存，对实际值操作
引用：在函数内同一地址的别名，例如b = &a，则对b操作就是对a操作

&和*详解

&表示传地址和引用
*表示指针变量，例如

取地址的用法：

int *b = &a;
# 以下语块与上句等价
int *b;         # int*类型的变量b，即b是个指针，指向一个int值
b = &a;         # 指针b存放a的地址

引用的用法

a = 100;
int &b = a;     # int&类型的变量b，作为a的引用。对b操作就等于对a操作
b += 1;
cout<<a;        #此处输出a的值为101

其他

中缀转后缀表达式

参考资料

基本思路：

遇到操作数，直接输出，如：a,b,c

遇到运算符，将当前运算符的栈外优先级与栈顶元素的栈内优先级作比较，有下列两种情况：
a. 栈外优先级高，则入栈，等待后续计算
b. 栈内优先级高，则栈顶元素出栈输出，直到栈顶元素优先级<当前读取的栈外元素优先级，然后栈外元素入栈

遇到(，直接入栈。为了实现这一点，即(的栈外优先级最高，栈内优先级最低

遇到)，栈顶元素依次出栈输出，直到遇到(，停止

遇到#，表示表达式结束

image_1ensm2bcr1uvt1j9j1ada1ofdlng2n.png-436.5kB

其中，isp为In Stack Priority，即栈内优先级
icp为In Coming Priority，即输入序列优先级/栈外优先级
优先级表如下所示：

规律如下：

同等级运算符，isp=icp+1

(在栈外最高，在栈内最低；)刚好相反

保证临时栈内从底到顶是单调递增的

#测试样例
infix_expression = 'a+b-a*((c+d)/e-f)+g'        #中缀表达式
suffix_expression = 'ab+acd+e/f-*-g+'           #后缀表达式

层次遍历（队列的应用）

算法描述：

根节点入队

如果
a. 队列为空，则结束遍历
b. 队列不为空，则第一个元素出队并输出

访问出队的元素，如果：
a. 有左孩子，左孩子入队
b. 有右孩子，右孩子入队
c. 返回2

伪代码：

EnQueue(root);                      #根节点入队
while(!QueueEmpty):                 #只要队不是空的
    DeQueue(front);                 #第一个元素出队并输出
    if front->left != NULL:         
        EnQueue(front->left);       #如果有左孩子，则左孩子入队
    elif front->right != NULL;
        EnQueue(front->right);      #如果有右孩子，则右孩子入队
return;         #当队列为空时，遍历结束

试题集

1.(p7.5)时间复杂度？

int fact(int n){
    if(n<=1) return 1;
    return n*fact(n-1);
}

2.(p9.2)时间复杂度？

for(i=1;i<=n;i++){
    for(j=1;j<=i;j++){
        for(k=1;k<=j;k++)
            x++;
    }
}

3.(p37.6)在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入结点s，则执行？

A. s->next = p->next;   p->next = s;
B. p->next = s->next;   s->next = p;
C. q->next = s ;        s->next = p;
D. p->next = s;         s->next = q;

4.(p38.12)说法正确的是？

A. 对一个设有头指针和尾指针的单链表执行删除最后一个元素的操作与链表长度无关
B. 线性表中每个元素都有一个直接前驱和直接后继
C. 为了方便插入和删除数据，可以使用双链表存放数据
D. 取线性表第i个元素的事件与i的大小有关

5.(p40.25)某线性表用带头节点的循环单链表存储，头指针为head，当head->next->next=head成立时，线性表长度可能是？

A. 0
B. 1
C. 2
D. 0或1

6.(p68.8)向一个栈顶指针为top的链栈中插入一个x结点，则执行？

A. top->next = x;
B. x->next = top->next;     top->next = x;
C. x->next = top;           top = x;
D. x->next = top;           top = top->next;

7.(p68.7)设链表无头结点，操作在表头，则不适合作为链栈的是？

A. 有头指针，无尾指针，双向循环
B. 有尾指针，无头指针，双向循环
C. 有头指针，无尾指针，单向循环
D，有尾指针，无头指针，单项循环

8.(p70.22)一个栈的入栈序列1,2,3,...,n，出栈序列P1,P2,...,Pn，若P2=3，则P3可能的取值个数？

A. n-3
B. n-2
C. n-1
D. 无法确定

9.(p84.8)循环队列存储在A[0...n-1]中，队列非空时，front和rear分别指向队头元素和对位元素。若初始队列为空，且要求第一个进入队列的元素存储在A[0]处，则初始front和rear值是？

10.(95.11)中缀表达式为a+b-a*((c+d)/e-f)+g，在转换成后缀表达式ab+acd+e/f-*-g+的过程中，临时存放操作符的栈最大的同时存放数是多少？

11.(176.12)若森林F有15条边，25个结点，则F包含树的个数是？

12.(133.20)已知一棵有2011个结点的树，其叶结点的个数是116，该树对应的二叉树中无右孩子的结点个数是？

13.(146.5)在二叉树中有两个结点m和n，若m是n的祖先，则使用( )遍历可以找到从m到n的路径？

14.(149.34)先序序列为a,b,c,d的不同二叉树的个数是( )

15.(175.7)设F是一个森林，B是由F变换来的二叉树，若F中有n个非终端结点，则B中右指针域为空的结点有多少个？

16.(194.27)若度为m的哈夫曼树中，叶子结点个数为n，则非叶子结点的个数为?

17.(194.33)在任意一棵非空平衡二叉树T1中，删除某结点v之后形成平衡二叉树T2，再将v插入T2形成平衡二叉树T3，下列关于T1和T3的叙述中，正确的是（）

若v是T1的叶结点，则T1与T3可能不相同

若v不是T1的叶结点，则T1与T3一定不相同

若v不是T1的叶结点，则T1与T3一定相同

18.(212.7)若无向图G=(V,E)中含有7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是（）

19.(212.8)以下关于图的叙述中，正确的是（）

A. 强连通有向图的任何顶点到其他所有顶点都有弧
B. 图的任意顶点的入度等于出度
C. 有向完全图一定是强连通有向图
D. 有向图的边集的子集和顶点集的子集可构成原有向图的子图

20.(248.5)正确的是（）

最小生成树的代价唯一

所有权值最小的边一定会出现在所有的最小生成树中

使用Prim算法从不同顶点开始得到的最小生成树一定相同

使用Prim算法和Kruskal算法得到的最小生成树总不相同

A. 仅1
B. 仅2
C. 仅1、3
D. 仅2、4

21.(250.21)求AOE网的哪些活动加快了，就可以缩短工期？

A. c和d
B. d和c
C. f和d
D. f和h

22.(275.2)n个元素的两个表，一个递增表，一个无序表。采用顺序查找，且递增表查到超过当前元素还不成功，就返回不成功并停止。则两种表中成功查找（）

A. 递增表的ASL更小
B. 两种相同
C. 无序表ASL更小
D. 无法确定

23.(276.8)已知长度为16的顺序表，其元素按关键字有序排列，如果折半查找一个不存在的元素，则比较次数最多为？

24.(276.14)12个关键字的有序表，每个关键字概率相同，则成功的平均长度？失败的平均长度？

25.(276.15)

答案速查

$O(n)$
$O(n^3)$
C，因为p和q是已知的所以单链表不会断裂
C
D，表头不算长度，且含有0个元素的时候也可以
C，表头才是栈顶
C
C，除3以外的所有都可能
0，n-1，注意看rear指向队尾元素
5个
10个
1896，特殊值法
后序遍历
14个，即“入栈顺序为abcd的，出栈顺序有多少种？”
n+1个
$\lceil (n-1)/(m-1) \rceil$
仅1
16条
C
A
C，因为只有他包含了每条关键路径
B
5
37/12，49/13