数据结构
信息技术
逻辑结构
- 线性结构
- 集合结构
- 树形结构
- 图形结构
1 | graph g{ |
物理结构（存储结构）
- 顺序存储（数组，顺序表）
- 链式存储（链表）
- 索引存储
- 散列存储
如何判断某种结构是逻辑结构还是存储结构或数据结构？
当一个结构，如数组、链表、树、图，在逻辑结构中只有一种定义，而在物理结构中却有两种选择，那么这个结构就属于逻辑结构；
相反，当此结构在原有基础上加上了某种限定，使得其在物理结构中只有一种定义，那么这个结构就属于物理（存储）结构；
举例1：栈属于什么结构？
分析：栈在逻辑结构中只能属于线性结构，而在物理结构中它可以使用顺序存储（数组），也可以使用链式存储（链表），所以说栈是一种逻辑结构。
举例2：线索二叉树属于什么结构？
分析：首先，可以得到二叉树是一种逻辑结构，但是线索二叉树是加上线索后的链表结构（不能用顺序存储），也就是说，它是计算机内部的只有一种存储结构，所以是物理结构。
算法
算法满足
- 输入
- 输出
- 确定性：对于相同的输入只能得出相同的输出
- 有穷性
- 可行性
衡量算法的标准
- Correctness 正确性
- Readability 可读性
- Robustness 健壮性
- Efficiency 效率与低存储量需求（核心的）
衡量效率的指标
- 时间复杂度
- 空间复杂度
时间复杂度
大O表示法
一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记为**T(n)*，它是该算法问题规模n的函数，时间复杂度主要分析T(n)的数量级。算法中基本运算（最深层循环内*的语句）的频度与T(n)同数量级，因此通常采用算法中基本运算的频度f(n)来分析算法的时间复杂度。因此，算法的时间复杂度记为$$T(n)=O(f(n))$$
O的含义是T(n)的数量级，其严格的数学定义是：若T(n)和f(n)是定义在正整数集合上的两个函数，则存在正常数C和$n_0$，使得当$n\geqslant n_0$时，都满足$0\leqslant T(n)\leqslant Cf(n)$.图示如下：
可以总结为:
T(n)增长率小于等于f(n)
- 最坏时间复杂度是指在最坏情况下，算法的时间复杂度
- 平均时间复杂度是指所有可能输入实例在等概率出现的情况下，算法的期望运行时间
- 最好时间复杂度是指在最好情况下，算法的时间复杂度
一般总是考虑最坏时间复杂度，以保证算法的运行时间不会比它更长
加法规则
$$T(n)=T_1(n)+T_2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))$$
乘法规则
$$T(n)=T_1(n)\times T_2(n)=O(f(n))\times O(g(n))=O(f(n)\times g(n))$$
常见的时间复杂度
$$O(1)<O(\log_2 n)<O(n)<O(n\log_2 n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)$$
T(n)写法
- 忽略常数
不能写O(2n^2^)，得写成O(n^2^) - 忽略低次项
不能写O(n^2^+n)，得写成O(n^2^)
空间复杂度
算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它是问题规模n的函数。记为$S(n)=O(g(n))$
算法原地工作是指算法所需的辅助空间为常量，即O(1)
第二章 线性表
1 | graph a{ |
定义和基本操作
定义
线性表是具有相同数据类型的n个数据元素的有限序列，其中n为表长，当n=0时该线性表是一个空表。若用L命名线性表，则其一般表示为
$$L=(a_1,a_2,…,a_i,a_{i+1},…,a_n)$$
特点
- 表中元素个数有限
- 表中元素具有逻辑上的顺序性，在序列中各元素排序有其先后次序
- 表中元素都是数据元素，每个元素都是单个元素
- 表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间
- 表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容
注意：线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构，两种属于不同层面的概念，因此不要将其混淆
基本操作
- InitList(&L): 初始化表。构造一个空的线性表
- Length(L): 求表长。返回线性表的长度
- LocateElem(L,e): 按值查找操作。在表中查找具有给定关键字值的元素
- GetElem(L,i): 按位查找操作。获取表中的第i个位置的元素的值
- ListInsert(&L,i,e): 插入操作。在表中的第i个位置上插入指定元素e
- ListDelete(&L,i,&e): 删除操作。删除表中第i个位置的元素，并用e返回删除元素的值
- PrintList(L): 输出操作。按前后顺序输出线性表的所有元素值
- Empty(L): 判空操作。若L为空表，则返回true，否则返回false
- DestroyList(&L): 销毁操作。销毁线性表，并释放线性表L所占用的内存空间
线性表的顺序表示
顺序表的定义
线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。第一个元素存储在线性表的起始位置，第i个元素的存储位置后面紧接着存储的是第i+1个元素。
假定线性表的元素类型为ElemType，则线性表的顺序存储类型描述为
1 |
|
特点
- 表中元素的逻辑顺序与其物理顺序相同
- 随机访问，即通过首地址和元素序号可在时间O(1)内找到指定的元素
- 存储密度高，每个节点只存储数据元素
- 插入和删除操作需要移动大量元素
基本操作的实现
- 插入操作
在顺序表L的第i个位置插入新元素e。若i的输入不合法，则返回false，表示插入失败；否则，将顺序表的第i个元素及其后的所有元素右移一个位置，腾出一个空位置插入新元素e，顺序表长度增加1，插入成功，返回true1
2
3
4
5
6
7
8
9
10
11bool ListInsert(SqList &L,int i,ElemType e) {
if(i<1||i>L.length+1) //判断i的范围是否有效
return false;
if(L.length>=MaxSize) //当前存储空间已满，不能插入
return false;
for(int j=L.length-1;j>=i;j--) //将第i个元素及之后的元素后移
L.data[j]=L.data[j-1];
L.data[i-1]=e; //在位置i处放入e
L.length++; //线性表长度加1
return true;
}
最好情况：在表尾插入（即i=n+1），元素后移语句将不执行，时间复杂度为O(1)
最坏情况：在表头插入（即i=1），元素后移语句将执行n次，时间复杂度为O(n)
平均情况：n/2次
因此线性表插入算法的平均时间复杂度为O(n)
- 删除操作
删除顺序表L中第i个位置的元素，若成功则返回true，并将被删除的元素用引用变量e返回，否则返回false最好情况：删除表尾元素（i=n），无须移动元素，时间复杂度为O(1)1
2
3
4
5
6
7
8
9bool ListDelete(SqList &L,int i,Elemtype &e) {
if(i<1||i>L.length) //判断i的范围是否有效
return false;
e=L.data[i-1]; //将被删除的元素赋值给e
for(int j=i;j<L.length;j++) //将第i个位置后的元素前移
L.data[j-1]=L.data[j];
L.length--; //线性表长度减1
return true;
}
最坏情况：删除表头元素（i=1），需要移动除第一个元素外的所有元素，时间复杂度为O(n)
平均情况：$\frac{n-1}{2}$次
因此线性表删除算法的平均时间复杂度为O(n)
- 按值查找
在顺序表L中查找第一个元素值等于e的元素，并返回其位序最好情况：查找的元素就在表头，仅需比较一次，时间复杂度为O(1)1
2
3
4
5
6
7int LocateElem(SqList L,ElemType e) {
int i;
for(i=0;i<L.length;i++)
if(L.data[i]==e)
return i+1; //下标为i的元素值等于e，返回其位序i+1
return 0; //退出循环，说明查找失败
}
最坏情况：查找的元素在表尾（或不存在时），需要比较n次，时间复杂度为O(n)
平均情况：假设$p_i$是查找的元素在第i个位置上的概率，则平均次数为$$\sum^n_{i=1}p_i\times i=\sum^n_{i=1}\frac{1}{n}\times i=\frac{1}{n}\frac{n(n+1)}{2}=\frac{n+1}{2}$$
因此线性表查找算法的平均时间复杂度为O(n)
线性表的链式表示
单链表的定义
线性表的链式存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。为了建立数据元素之间的线性关系，对每个链表节点，除存放元素自身的信息外，还需要存放一个指向其后继的指针。
单链表中结点类型的描述如下：
1 | typedef struct LNode { //定义单链表节点类型 |
- 优点：不需要大量连续存储空间
- 缺点：附加指针域浪费存储空间
特点：非随机存取的存储结构，即查找某个特定的节点时，需要从表头开始遍历，依次查找
通常用头指针来表示一个单链表，如单链表L，头指针为NULL时表示一个空表。此外，为了操作上的方便，在单链表第一个节点之前附加一个节点，称为头结点。头结点的数据域可以不设任何信息，也可以记录表长等相关信息。头结点的指针域指向线性表的第一个元素节点，如图所示：
头结点和头指针的区分：不管带不带头结点，头指针始终指向链表的第一个节点，而头结点是带头结点的链表中的第一个节点，节点内通常不存储信息
引入头结点后，可以带来两个优点：
- 由于开始节点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作和在表的其他位置上的操作一直，无须进行特殊处理
- 无论链表是否为空，其头指针都是指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就得到了统一
单链表上基本操作的实现
采用头插法建立单链表
每次将读入的新节点插入链表的表头，即头结点之后1
2
3
4
5
6
7
8
9
10
11
12
13
14LinkList List_HeadInsert(LinkList &L) {
LNode *s;int x;
L=(LinkList)malloc(sizeof(LNode)); //创建头结点
L->next=NULL; //初始为空链表
scanf("%d",&x); //输入节点的值
while(x!=9999) { //输入9999表示结束
s=(LNode*)malloc(sizeof(LNode)); //创建新节点
s->data=x;
s->next=L->next;
L->next=s; //将新节点插入表中，L为头指针
scanf("%d",&x);
}
return L;
}采用头插法建立单链表时，读入数据的顺序与生成的链表中的元素的顺序是相反的。每个节点插入的时间为O(1)，设单链表长为n，则总时间复杂度为O(n)
采用尾插法建立单链表
增加一个尾指针r，使其始终指向当前链表的尾结点1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16LinkList List_TailInsert(LinkList &L) {
//从表头到表尾正向建立单链表，每次均在表尾插入元素
int x; //设元素类型为整型
L=(LinkList)malloc(sizeof(LNode));
LNode *s,*r=L; //r为表尾指针
scanf("%d",&x); //输入节点的值
while(x!=9999) {
s=(LNode*)malloc(sizeof(LNode));
s->data=x;
r->next=s;
r=s;
scanf("%d",&x);
}
r->next=NULL; //尾结点指针置空
return L;
}因为附设了一个指向表尾节点的指针，故时间复杂度和头插法的相同
按序号查找节点值
在单链表中从第一个节点出发，顺指针next域逐个往下搜索，直到找到第i个节点为止，否则返回最后一个节点指针域NULL1
2
3
4
5
6
7
8
9
10
11
12
13
14LNode *GetElem(LinkList L,int i) {
//本算法取出单链表L（带头结点）中第i个位置的节点指针
int j=1; //计数，初始为1
LNode *p=L->next; //头结点指针赋给p
if(i==0)
return L; //若i等于0，则返回头结点
if(i<1)
return NULL; //若i无效，则返回NULL
while(p&&j<i) { //从第1个节点开始找，查找到第i个节点
p=p->next;
j++;
}
return p; //返回第i个节点的指针，如果i大于表长，p=NULL，直接返回p即可
}
按序号查找操作的时间复杂度为O(n)
按值查找表节点
从单链表的第一个节点开始，由前往后依次比较表中各节点数据的值，若某节点数据域的值等于给定值e，则返回该节点的指针；若整个单链表中没有这样的节点，则返回NULL1
2
3
4
5
6
7LNode *LocateElem(LinkList L,ElemType e) {
//本算法查找单链表L（带头结点）中数据域值等于e的结点指针，否则返回NULL
LNode *p=L->next;
while(p!=NULL&&p->data!=e) //从第1个结点开始查找data域为e的结点
p=p->next;
return p; //找到后返回该结点指针，否则返回NULL
}插入结点操作
插入结点操作将值为x的新结点插入到单链表的第i个位置上。先检查插入位置的合法性，然后找到待插入位置的前驱结点，即第i-1个结点，再在其后插入新结点
代码片段如下
1 | p=GetElem(L,i-1); //查找插入位置的前驱结点 |
本算法主要的时间开销在于查找第i-1个元素，时间复杂度为O(n)。若在给定的结点后面插入新结点，则时间复杂度仅为O(1)
- 删除结点操作
删除结点操作是将单链表的第i个结点删除。先检查删除位置的合法性，然后查找表中第i-1个结点，即被删结点的前驱结点，再将其删除。
假设结点p为找到的被删结点的前驱结点，为实现这一操作后的逻辑关系的变化，仅需修改p的指针域，即将p的指针域next指向q的下一结点。代码片段如下：
1 | p=GetElem(L,i-1); //查找删除位置的前驱结点 |
和插入算法一样，该算法的主要时间也耗费在查找操作上，时间复杂度为O(n)
- 求表长操作
求表长操作就是计算单链表中数据结点（不含头结点）的个数，需要从第一个节点开始顺序依次访问表中的每个结点，为此需要设置一个计数器变量，每访问一个结点，计数器加1，知道访问到空节点位置。算法的时间复杂度为O(n)
双链表
双链表结点中有两个指针prior和next，分别指向其前驱结点和后继结点
1 | typedef struct DNode { //定义双链表结点类型 |
双链表仅在单链表的结点中增加了一个指向其前驱的prior指针，因此在双链表中执行按值查找和按位查找的操作与在单链表中的相同。但双链表在插入和删除操作的实现上，与单链表有着较大的不同。这是因为“链”变化时也需要对prior指针做出修改
双链表的插入操作
在双链表中p所指的结点之后插入结点*s，代码片段如下1
2
3
4s->next=p->next; //将结点*s插入到结点*p之后
p->next->prior=s;
s->prior=p;
p->next=s;上述代码的语句顺序不唯一，但也不是任意的。前两句必须在第四局之前，否则*p的后继指针就会丢掉，导致插入失败
双链表的删除操作
删除双链表中节点p的后继结点q，代码片段如下1
2
3p->next=q->next;
q->next->prior=p;
free(q); //释放结点空间
循环链表
循环单链表
循环单链表和单链表的区别在于，表中最后一个节点的指针不是NULL，而改为指向头结点，从而整个链表形成一个环，如图
循环单链表中没有指针域为NULL的结点，因此它的判空条件不是头结点的指针是否为空，而是它是否等于头指针循环双链表
头结点的prior指针还要指向表尾结点，如图
在循环双链表L中，某结点*p为尾结点时，p->next==L;当循环双链表为空表时，其头结点的prior域和next域都等于L
静态链表
借助数组来描述线性表的链式存储结点，结点也有数据域和指针域，与前面的链表中的指针不同的是，这里的指针是结点的相对地址（数组下标），又称游标。和顺序表一样，静态链表也要预先分配一块连续的内存空间，如图
静态链表结构类型的描述如下：
1 |
|
静态链表以next==-1来作为其结束的标志。总体来说，静态链表没有单链表使用起来方便吗，但在一些不支持指针的高级语言（如Basic）中，这是一种非常巧妙的设计方法
顺序表和链表的比较
- 存取方式
顺序表可以顺序存取，也可以随机存取，链表只能从表头顺序存取元素 - 逻辑结构与物理结构
采用顺序存储时，逻辑上相邻的元素，其对应的物理存储位置也相邻。而采用链式存储时，逻辑上相邻的元素，其物理存储位置则不一定相邻，其对应的逻辑关系是通过指针链接来表示的 - 查找、插入和删除操作
对于按值查找，顺序表无序时，两者的时间复杂度均为O(n)；顺序表有序时，可采用这般查找，此时的时间复杂度为$O(\log_2n)$
对于按序号查找，顺序表时间复杂度仅为O(1)，而链表则为O(n)。但链表的插入和删除操作要比顺序表方便很多。 - 空间分配
顺序存储在静态存储分配情形下，一旦存储空间装满就不能再加入新元素，因此需要预先分配足够大的存储空间。预先分配过大，可能导致浪费；预先分配过小，可能导致溢出。动态存储分配虽然存储空间可以扩充，但需要移动大量元素，导致操作效率降低，而且若内存中没有更大块的连续存储空间，则会导致分配失败。链式存储的结点空间只在需要时申请分配，只要内存有空间就可以分配，操作灵活、高效
在实际中应该怎样选取存储结构
- 基于存储的考虑
难以估计线性表的长度或存储规模时，不宜采用顺序表；链表不用事先估计存储规模，但链表的存储密度较低，显然链式存储结构的存储密度是小于1的 - 基于运算的考虑
存顺序表中按序号访问的时间复杂度为O(1)，而链表中按序号访问的时间复杂度为O(n)，因此若经常做的运算是按序号访问数据元素，则显然顺序表优于链表
在顺序表中进行插入删除操作时需要移动较多的元素；在链表中进行插入删除操作时，虽然也要找插入位置，但操作主要是比较操作。从这个角度考虑显然后者优于前者 - 基于环境的考虑
顺序表容易实现，任何高级语言中都有数组类型；链表的操作是基于指针的，相对来讲，前者实现较为简单，这也是用户考虑的一个因素
总之两种存储结构各有长短，选择哪一种由实际问题的主要因素决定。通常较稳定的线性表选择顺序存储，而频繁进行插入、删除操作的线性表（即动态性较强）适合选择链式存储
第三章 栈和队列
栈
栈的基本概念
定义
一种特殊的线性表，插入和删除在同一端，该端叫栈顶（top），另一端叫栈底（bottom）
特点：后进先出（LIFO），故也称为后进先出的线性表基操
- InitStack(&S): 初始化一个空栈S
- StackEmpty(S): 判断一个栈是否为空，若栈S为空则返回true，否则返回false
- Push(&S,x): 进栈，若栈S未满，则将x加入使之成为新栈顶
- Pop(&S,x):出栈，若栈S非空，则弹出栈顶元素，并用x返回栈顶元素
- GetTop(S,&x): 读栈顶元素（不弹出）
- ClearStack(&S): 销毁栈，并释放栈S所占用的存储空间（注意，符号“&”是C++特有的，用来表示引用调用，采用C语言中的指针类型“*”也可以达到传址的目的
n个不同元素进栈，出栈元素不同排列的个数是$\frac{1}{n+1}C^n_{2n}$
栈的顺序存储结构
- 顺序栈的实现
1
2
3
4
5
typedef struct {
Elemtype data[MaxSize]; //存放栈中元素
int top; //栈顶指针
} SqStack; - 顺序栈的基本运算
(1) 初始化
1 | void InitStack(SqStack &S) { |
(2) 判栈空
1 | bool StackEmpty(SqStack S) { |
(3) 进栈
1 | bool Push(SqStack &S,ElemType x) { |
(4) 出栈
1 | bool Pop(SqStack &S,ElemType &x) { |
(5) 读栈顶元素
1 | bool GetTop(SqStack S,ElemType &x) { |
注意：这里栈顶指针指向的是栈顶元素，所以进栈时的操作是S.data[++S.top]=x,出栈时的操作是x=S.data[S.top–].若栈顶指针初始化为S.top=0，即栈顶指针指向栈顶元素的下一个位置，则会有变化
- 共享栈
利用栈底位置相对不变的特性，可让两个顺序栈共享一个一位数据空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸
栈的链式存储结构
采用链式存储的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满溢出的情况。通常采用单链表实现，并规定所有操作都是在单链表的表头进行的。这里规定链栈没有头结点，Lhead指向栈顶元素，如图
1 | typedef struct Linknode { |
栈的应用
检查左右括号是否匹配
扫描，碰见左括号入栈，碰见右括号就弹栈进行比对，若为空就报错
结束时，如果栈不为空，则报错
后缀表达式求值
扫描，碰见操作数就将它入栈，碰见运算符就弹两个操作数出栈计算后将结果入栈。结束时取出栈顶元素
中缀表达式转化为后缀表达式
- 如果读到的操作数就直接输出
- 如果读到的是运算符
- 当读到的运算符优先级大于栈顶元素优先级或者栈为空时，将该运算符入栈
- 当读到的是”)”时，不断弹出栈顶元素并输出直到栈顶元素为”(“，此时弹出”(“但不输出
- 当读到的运算符优先级小于栈顶元素优先级时，不断弹出栈顶元素并输出直到读到的运算符优先级大于栈顶元素，此时将读到的运算符入栈
- 将输入的字符序列扫描完毕后，如果栈内还有元素，就不断弹栈输出直到栈空为止
优先级如下表所示，isp是栈内优先（in stack priority)数，icp是栈外优先（in coming priority）数
| 操作符 | # | ( | *, / | +, - | ) |
|---|---|---|---|---|---|
| isp | 0 | 1 | 5 | 3 | 6 |
| icp | 0 | 6 | 4 | 2 | 1 |
栈在递归中的应用
递归解题思路：把规模较大的问题缩小到一目了然
递归包含
- 基本状态（出口）
- 普通状态（递归）
递归运算相当于在栈内运算
递归函数编写不好会导致栈溢出
递归运算每增加一个数时间增长一倍
- 优点：可读性强
- 缺点：冗余太多
用递归的条件
- 深度不能太深
- 可读性明显高
- 时间在同一数量级
队列
定义
一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。
特点：**先进先出(FIFO)**，故又称先进先出的线性表
基操
- InitQueue(&Q): 初始化队列，构造一个空队列Q
- QueueEmpty(Q): 判队列空，若队列Q为空返回true，否则返回false
- EnQueue(&Q,x): 入队，若队列Q未满，将x加入，使之成为新的队尾
- DeQueue(&Q,x): 出队，若队列Q非空，删除队首元素，并用x返回
- GetHead(Q,&x): 读队首元素，若队列Q非空，则将队首元素赋值给x
队列的顺序存储
1 |
|
- 初始状态：Q.front==Q.rear==0
- 队空条件：Q.front==Q.rear
- 进队操作：队不满时，先送值到队尾元素，再将队尾指针加1
- 出队操作：队不空时，先取队首元素值，再将队首指针加1
队列的初始状态
如上图所示，rear=MaxSize并不能作为队列满的条件。最后一张图中队列仅有一个元素，但仍满足该条件，这是一种“假溢出”。这个问题需要循环队列来解决
循环队列
把存储队列元素的表从逻辑上视为一个环，称为循环队列。当队首指针Q.front=MaxSize-1后，再前进一个位置就自动到0，这可以利用除法取余运算（%）来实现
- 初始时：Q.front=Q.rear=0
- 队首指针进1：Q.front=(Q.front+1)%MaxSize
- 队尾指针进1：Q.rear=(Q.rear+1)%MaxSize
- 队列长度：(Q.rear+MaxSize-Q.front)%MaxSize
按照常规做法，队空和队满时都有Q.front==Q.rear
为了区分队空还是队满的的情况，有几种处理方式
- 牺牲一个单元来区分队空和队满，入队时少用一个队列单元，这是一种较为普遍的做法，约定以“队首指针在队尾指针的下一位置作为队满的标志”，如图
- 队满条件：(Q.rear+1)%MaxSize==Q.front
- 队空条件：Q.front==Q.rear
- 队列中元素的个数：(Q.rear+MaxSize-Q.front)%MaxSize
- 类型中增设表示元素个数的数据成员size
- 队空条件：size==0
- 队满条件：size==MaxSize
这两种情况都有Q.front==Q.rear
以牺牲一个单元来判断队空队满的队列的操作代码
- 初始化
1
2
3void InitQueue(SqQueue &Q) {
Q.rear=Q.front=0; //初始化队首指针和队尾指针
} - 判队空
1
2
3
4
5
6bool isEmpty(SqQueue Q){
if(Q.rear==Q.front) //队空条件
return true;
else
return false;
} - 入队
1
2
3
4
5
6
7bool EnQueue(SqQueue &Q, ElemType x){
if((Q.rear+1)%MaxSize==Q.front)
return false; //队满
Q.data[Q.rear]=x;
Q.rear=(Q.rear+1)%MaxSize; //队尾指针加1取模
return true;
} - 出队
1
2
3
4
5
6
7bool DeQueue(SqQueue &Q,ElemType &x){
if(Q.rear==Q.front)
return false;
x=Q.data[Q.front];
Q.front=(Q.front+1)%MaxSize;
return true;
}队列的链式存储
队列的链式存储称为链队列，它实际上是一个同时带有队首指针和队尾指针的单链表。头指针指向队首节点，尾指针指向队尾节点，即单链表的最后一个结点（与顺序存储不同，顺序存储的尾指针指向的是最后一个结点的下标加1）
带头结点的链式队列：
1 | typedef struct { //链式队列结点 |
当Q.front==null且Q.rear==null时，链式队列为空
链式队列的基操
- 初始化
1
2
3
4void InitQueue(LinkQueue &Q) {
Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode)); //建立头结点
Q.front->next=NULL; //初始为空
} - 判队空
1
2
3
4
5
6bool IsEmpty(LinkQueue Q) {
if(Q.front==Q.rear)
return true;
else
return false;
} - 入队
1
2
3
4
5
6
7void EnQueue(LinkQueue &Q,ElemType x) {
LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
s->data=x;
s->next=NULL; //创建新结点
Q.rear->next=s;
Q.rear=s; //插入到队尾
} - 出队
1
2
3
4
5
6
7
8
9
10
11bool DeQueue(LinkQueue &Q,ElemType &x) {
if(Q.front==Q.rear)
return false; //空队
LinkNode *p=Q.front->next;
x=p->data;
Q.front->next=p->next;
if(Q.rear==p)
Q.rear=Q.front; //若原队列中只有一个结点，删除后变空
free(p);
return true;
}
双端队列
双端队列是指允许两端对可以进行入队和出队操作的队列。其元素的逻辑结构仍是线性结构。将队列的两端分别称为前端和后端，两端都可以入队和出队
输出受限的双端队列：允许在一段进行插入和删除，但在另一端只允许插入
输入受限的双端队列：允许在一端进行插入和删除，但在另一端只允许删除。若限定双端队列从某个端点插入的元素只能从该端点删除，则该双端队列就蜕变为两个栈底相邻接的栈
队列的应用
队列在层次遍历（广度优先遍历）中的应用
层次遍历二叉树的过程
- 根节点入队
- 若队空（所有节点都已处理完毕），则结束遍历；否则重复3.操作
- 队列中第一个节点出队，并访问。若其有左子，则将左子入队；若其有右子，则将右子入队，返回2.层次遍历二叉树的过程
1
2
3
4
5
6
7
8graph binaryTree {
node[shape=circle];
A--B,C
B--D
C--E,F
D--G
E--H,I
}
| 序 | 说明 | 队内 | 队外 |
|---|---|---|---|
| 1 | A入 | A | |
| 2 | A出，BC入 | BC | A |
| 3 | B出，D入 | CD | AB |
| 4 | C出，EF入 | DEF | ABC |
| 5 | D出，G入 | EFG | ABCD |
| 6 | E出，HI入 | FGHI | ABCDE |
| 7 | F出 | GHI | ABCDEF |
| 8 | GHI出 | ABCDEFGHI |
队列在计算机系统中的应用
- 解决主机与外部设备之间速度不匹配的问题
以主机和打印机之间速度不匹配的问题为例。主机输出数据给打印机打印，输出数据的速度比打印数据的速度要快得多，由于速度不匹配，若直接把输出的数据送给打印机打印显然是不行的。解决的方法是设置一个打印数据缓冲区，主机把要打印输出的数据依次写入这个缓冲区，写满后就暂停输出，转去做其他的事情。打印机就从缓冲区中按照先进先出的原则依次取出数据并打印，打印完后再向主机发出请求。主机接到请求后再向缓冲区写入打印数据。这样做既保证了打印数据的正确，又使主机提高了效率。由此可见，打印数据缓冲区中所存储的数据就是一个队列 - 解决由多用户引起的资源竞争问题
在一个带有多终端的计算机系统上，有多个用户需要CPU各自运行自己的程序，它们分别通过各自的终端向操作系统提出占用CPU的请求。操作系统通常按照每个请求在时间上的先后顺序，把它们排成一个队列，每次把CPU分配给队首请求的用户使用。当相应的程序运行结束或用完规定的时间间隔后，令其出队，再把CPU分配给新的队首请求的用户使用。这样既能满足每个用户的请求，又能使CPU正常运行
第四章 树与二叉树
树的基本概念
树的定义
树是n(n>=0)个结点的有限集合，n=0时，称为空树，这是一种特殊情况。在任意一棵非空树中应满足：
- 有且仅有一个特定的称为根的结点
- 当n>1时，其余结点可分为m(m>0)个互不相交的有限集合T1,T2,…,Tm,其中每个集合本身又是一棵树，并且称为根节点的子树
树的定义是递归的
特点：
- 树的根节点没有前驱结点，除根节点外的所有节点有且只有一个前驱结点
- 树中所有节点可以有零个或多个后继结点
树中某个结点（除根结点外）最多只和上一层的一个结点（即其父结点）有直接关系，根结点没有直接上层结点，因此在n个结点的树中有n-1条边
树的基本术语
- 根结点
- 兄弟结点
- 内部结点：有子结点
- 外部结点（叶子结点）：没有子结点
- 祖先结点：父结点、爷爷结点、曾爷爷结点……
- 子孙结点
- 结点的深度（Depth）：祖先结点的个数
- 树的高度（Height）：深度最大值（只有根结点为0，空树为-1）
- 结点的度（Degree）：子结点个数
- 树的度：结点的度的最大值
- 子树（Subtree）
- 森林：m棵互不相交的树的集合。森林的概念与树的概念十分相近，因为只要把树的根节点删去就成了森林
树的性质
- 树的结点数等于所有结点的度数加1
- 度为m的树中第i层上至多有$m^{i-1}$个结点（i>=1）
- 高度为h的m叉树至多有$(m^h-1)/(m-1)$个结点
- 具有n个结点的m叉树的最小高度为$[\log_m(n(m-1)+1)]$
二叉树的概念
二叉树的定义及其主要特性
1. 二叉树的定义
特点：
每个节点最多有两个子结点（可以只有一个）
子结点有序，分别称左子结点和右子结点，其次序不能任意颠倒
二叉树是有序树，即使树中节点只有一棵子树，也要区分它是左子树还是右子树
二叉树与度为2的有序树的区别：
- 度为2的树至少有3个结点，而二叉树可以为空
- 度为2的有序树的孩子结点的左右次序是相对于另一孩子结点而言的，若某个结点只有一个孩子结点，则这个孩子结点就无须区分其左右次序，而二叉树无论其孩子数是否为2，均需确定其左右次序，即二叉树的结点次序不是相对于另一结点而言，而是确定的
2. 几个特殊的二叉树
满二叉树
树中每一个层的结点数都达到最大值。满二叉树的叶子结点都集中在二叉树的最下一层，并且除叶子结点之外的每个结点度数均为2
按层从上往下标号，同一层从左往右标1
2
3
4
5
6graph tree{
node[shape=circle]
1--2,3
2--4,5
3--6,7
}结点i的父结点编号是i/2
结点i左子结点编号是2i 右子结点编号是2i+1
满二叉树用数组存最合适完全二叉树
最后一层从右往左可以缺结点
编号和满二叉树对应1
2
3
4
5graph tree{
node[shape=circle]
1--2,3
2--4,5
}二叉排序树
性质：左子树上所有结点的关键字均小于根结点的关键字；右子树上的所有结点的关键字均大于根结点的关键字。左子树和右子树又各是一棵二叉排序树平衡二叉树
树上任一结点的左子树和右子树的深度之差不超过1
3. 二叉树的性质
- 非空二叉树上的叶子结点数等于度为2的结点数加1，即n0=n2+1
- 非空二叉树上第k层上至多有$2^{k-1}$个结点（k>=1）
二叉树的存储结构
1. 顺序存储结构
一般完全二叉树和满二叉树使用
将完全二叉树上编号为i的结点元素存储在某个数组下标在i-1的分量中，然后通过一些方法确定结点在逻辑上的父子和兄弟关系
对于一般的二叉树，为了让数组下标能反映二叉树中结点之间的逻辑关系，只能添加一些并不存在的空结点，让其每个结点与完全二叉树上的结点相对照
满二叉树顺序存储:
普通二叉树顺序存储：
2. 链式存储结构
用一个链表来存储一棵二叉树，二叉树中的每个结点用链表的一个链结点来存储。在二叉树中，结点结构至少包含3个域：数据域data、左指针域lchild、右指针域rchild
1 | typedef struct BiTNode { |
在含有n个结点的二叉链表中，含有n+1个空链域
二叉树的遍历和线索二叉树
遍历
1. 先序遍历
操作过程：
若二叉树为空，则什么也不做；否则：
- 访问根结点
- 先序遍历左子树
- 先序遍历后子树
1
2
3
4
5
6
7void PreOrder(BiTree T) {
if(T!=null){
visit(T); //访问根结点
PreOrder(T->lchild); //递归遍历左子树
PreOrder(T->rchild); //递归遍历右子树
}
}
2. 中序遍历
操作过程:
若二叉树为空，则什么也不做；否则：
- 中序遍历左子树
- 访问根结点
- 中序遍历右子树
1
2
3
4
5
6
7void InOrder(BiTree T) {
if(T!=null){
InOrder(T->lchild); //递归遍历左子树
visit(T); //访问根结点
InOrder(T->rchild); //递归遍历右子树
}
}
3. 后序遍历
操作过程：
若二叉树为空，则什么也不做；否则：
- 后序遍历左子树
- 后序遍历右子树
- 访问根结点
1
2
3
4
5
6
7void PostOrder(BiTree T) {
if(T!=null){
PostOrder(T->lchild); //递归遍历左子树
PostOrder(T->rchild); //递归遍历右子树
visit(T); //访问根结点
}
}
4. 递归算法和非递归算法的转换
借助栈，可以将二叉树的递归遍历算法转换为非递归遍历算法。
以中序遍历为例：先扫描（并非访问）根结点的所有左结点并将它们一一进栈，然后出栈一个节点*p（显然结点*p没有左子结点或左子结点均已访问过），访问它。然后扫描该结点的右子结点，将其进栈，再扫描该右子结点的所有左结点并一一进栈，如此继续，知道栈空为止
1 | void InOrder2(BiTree T) { |
5. 层次遍历
借助一个队列。先将二叉树根结点入队，然后入队，访问该结点，若它有左子树，则将左子树根结点入队；若它有右子树，则将右子树根结点入队。然后出队，对出队结点访问，如此反复，直到队列为空
1 | void LevelOrder(BiTree T) { |
6. 由遍历序列构造二叉树
由二叉树的先序序列和中序序列可以唯一地确定一棵二叉树。在先序遍历序列中，第一个结点一定是二叉树的根结点；而在中序遍历中，根结点必然将中序序列分割成两个子序列，前一个子序列是根结点的左子树的中序序列，后一个子序列是根结点的右子树的中序序列
同理，由二叉树的后序序列和中序序列也可以唯一地确定一棵二叉树
例如，求先序序列（ABCDEFGHI）和中序序列（BCAEDGHFI）所确定的二叉树
1 | graph t1{ |
1 | graph t2{ |
1 | graph t3{ |
线索二叉树
1. 线索二叉树的基本概念
普通二叉树中存在大量的空指针（n个结点的二叉树有n+1个空指针），若利用这些空指针存放指向其直接前驱或后继的指针，则可以更方便地运用某些二叉树操作算法。引入线索二叉树是为了加快查找结点前驱和后继的速度。
线索二叉树的结点结构：
1 | digraph g { |
- ltag=0：lchild域指示结点的左子结点
- ltag=1：lchild域指示结点的前驱
- rtag=0：rchild域指示结点的右子结点
- rtag=1：rchild域指示结点的后继
1 | typedef strcut ThreadNode { |
2. 线索二叉树的构造
对二叉树的线索化，实质上就是遍历一次二叉树，只是在遍历的过程中，检查当前结点左右指针域是否为空，若为空，将它们改为指向前驱结点或后继结点的线索
3. 线索二叉树的遍历
非递归遍历不再需要借助栈，因为它的结点中隐含了线索二叉树的前驱和后继信息
- 求中序线索二叉树中中序序列下的第一个结点：
1
2
3
4
5ThreadNode *Firstnode(ThreadNode *p) {
while(p->ltag==0)
p=p->lchild; //最左下结点（不一定是叶子结点）
return p;
} - 求中序线索二叉树中结点p在中序序列下的后继结点：
1
2
3
4
5
6ThreadNode *Nextnode(ThreadNode *p) {
if(p->rtag==0)
return Firstnode(p->rchild);
else
return p->rchild;
} - 利用上面两个算法，可以写出不含头结点的中序线索二叉树的中序遍历的算法
1
2
3
4void Inorder(ThreadNode *T) {
for(ThreadNode *p=Firstnode(T);p!=null;p=Nextnode(p))
visit(p);
}
树、森林
树的存储结构
1. 双亲表示法
一组连续空间来存储每个节点，同时再每个节点中增设一个伪指针，指示其双亲节点在数组中的位置。根结点下标为0，其伪指针域为-1
1 | graph ptree{ |
| 下标 | data | parent |
|---|---|---|
| 0 | R | -1 |
| 1 | A | 0 |
| 2 | B | 0 |
| 3 | C | 0 |
| 4 | D | 1 |
| 5 | E | 1 |
| 6 | F | 3 |
| 7 | G | 6 |
| 8 | H | 6 |
| 9 | K | 6 |
1 |
|
该存储结构利用了每个结点（根结点除外）只有唯一双亲的性质，可以很快得到每个结点的双亲结点，但求结点的孩子时需要遍历整个结构
2. 孩子表示法
将每个结点的孩子结点都用单链表链接起来形成一个线性结构，此时n个结点就有n个孩子链表
3. 孩子兄弟表示法
孩子兄弟表示法又称二叉树表示法，即以二叉链表作为树的存储结构。孩子兄弟表示法使每个结点包括三部分内容：结点值、指向结点第一个孩子结点的指针，及指向结点下一个兄弟结点的指针（沿次域可以找到结点的所有兄弟结点）
1 | typedef struct CSNode{ |
这种表示法比较灵活，最大的优点是可以方便地实现树转换为二叉树的操作，易于查找结点的孩子等，但缺点是从当前结点查找其双亲结点比较麻烦。若为每个结点增设一个parent域指向其父结点，则查找结点的父结点也很方便
树和森林的遍历
- 先根遍历
若树非空，则先访问根结点，再按从左到右的顺序遍历根结点的每棵子树。其访问顺序与这棵树相应二叉树的先序遍历顺序相同 - 后根遍历
若树非空，则按从左到右的顺序遍历根结点的每棵子树，之后再访问根结点。其访问顺序与这棵树相应二叉树的中序遍历顺序相同
森林的两种遍历方法
- 先序遍历森林。若森林非空，则按如下规则进行遍历：
- 访问森林中第一棵树的根结点
- 先序遍历第一棵树中根结点的子树森林
- 先序遍历除去第一棵树之后剩余的树构成的森林
- 中序遍历森林。若森林为非空，则按如下规则进行遍历：
- 中序遍历森林中第一棵树的根结点的子树森林
- 访问第一棵树的根结点
- 中序遍历除去第一棵树之后剩余的树构成的森林
树、森林、二叉树遍历对应的关系
| 树 | 森林 | 二叉树 |
|---|---|---|
| 先根遍历 | 先序遍历 | 先序遍历 |
| 后根遍历 | 中序遍历 | 中序遍历 |
树的应用——并查集
并查集是一种简单的集合表示，它支持以下3种操作：
- Union(S, Root1, Root2): 把集合S中的子集合Root2并入子集合Root1.要求Root1和Root2互不相交，否则不执行合并
- Find(S,x): 查找集合S中单元素x所在的子集合，并返回该子集合的名字
- Initial(S): 将集合S中的每个元素都初始化为只有一个单元素的子集合
通常用树（森林）的双亲表示作为并查集的存储结构，每个子集合以一棵树表示
将root2并入到root1中
查找x所属于的根节点（或者说是x所属于的集合），就可以一直找array[x]，直到array[x]小于0，则证明找到了根（所在集合）
结构定义：
1 |
|
初始化操作：
1 | void Initial(int S[]){ |
Find操作（找到包含元素x的树的根）
1 | int Find(int S[],int x){ |
Union操作（函数求两个不相交子集合的并集）
1 | void Union(int S[],int Root1,int Root2) { |
树与二叉树的应用
二叉排序树
1. 二叉排序树的定义
二叉排序树（BST），也称二叉查找树。二叉排序树或者是一棵空树，或者是一棵具有下列特性的非空二叉树
- 若左子树非空，则左子树上所有结点关键字值均小于根结点的关键字值
- 若右子树非空，则右子树上所有结点关键字值均大于根结点的关键字值
- 左右子树本身也分别是一棵二叉排序树
对二叉排序树进行中序遍历，可以得到一个递增的有序序列
2. 二叉排序树的查找
若树非空，将给定值与根结点的关键字比较，若相等，则查找成功；若不等，则当根结点的关键字值大于给定关键字值时，在根结点的左子树中查找，否则在根结点的右子树中查找
1 | BSTNode *BST_Search(BiTree T, ElemType key, BSTNode *&p) { |
3. 二叉排序树的插入
若原二叉排序树为空，则直接插入结点；否则，若关键字k小于根结点关键字，则插入左子树，若关键字k大于根结点关键字，则插入右子树
1 | int BST_Insert(BiTree &T, KeyType k) { |
4. 二叉排序树的构造
1 | void Creat_BST(BiTree &T, KeyType str[], int n) { |
5. 二叉排序树的删除
三种情况：
- 若被删除结点z是叶子结点，则直接删除，不会破坏二叉排序树的性质
- 若结点z只有一颗左子树或右子树，则让z的子树称为z父结点的子树，替代z的位置
- 若结点z有左右两颗子树，可以分为以下两步
第一步：查找删除结点右子树中最小的那个值，也就是右子树中位于最左方的那个结点。然后将这个结点的值的父节点记录下来。并且将该节点的值赋给我们要删除的结点。也就是覆盖。
第二步：然后将右子树中最小的那个结点进行删除，该节点肯定符合上述三种情况的某一种情况，所以可以使用上述的方法进行删除。
6. 二叉排序树的查找效率分析
对于高度为h的二叉排序树，其插入和删除操作的运行时间都是O(h)。但在最坏的情况下，即构造二叉排序树的输入序列是有序的，则会行程一个倾斜的单支树，此时二叉排序树的性能显著变坏，输的高度也增加为元素个数n。
二叉排序树查找算法的平均查找长度，主要取决于树的高度。若二叉排序树是一个只有右（左）孩子的单支树，则其平均查找长度和单链表相同，为O(n)。若二叉排序树的左右子树的高度之差的绝对值不超过1，则这样的二叉排序树称为平衡二叉树。它的平均查找长度达到$O(\log_2 n)$
从查找过程看，二叉排序树与二分查找类似。就平均时间性能而言，二叉排序树上的查找和二分查找差不多。但二分查找的判定树唯一，而二叉排序树的查找不唯一，相同的关键字其插入顺序不同可能生成不同的二叉排序树
就维护表的有序性而言，二叉排序树无须移动结点，只需修改指针即可完成插入和删除操作，平均执行时间为$O(\log_2n)$。二分查找的对象是有序顺序表，若有插入和删除结点的操作，所花的代价是O(n)。当有序表是静态查找表时，宜用顺序表作为其存储结构，而采用二分查找实现其查找操作；若有序表是动态查找表，则应选择二叉排序树作为其逻辑结构
平衡二叉树
1. 平衡二叉树的定义
任意结点的左右子树高度差的绝对值不超过1，这样的二叉树称为平衡二叉树，简称平衡树（AVL）。定义结点左子树与右子树的高度差为该结点的平衡因子，则平衡二叉树结点的平衡因子的值只可能是-1,0或1
2. 平衡二叉树的插入
二叉排序树保证平衡的基本思想如下：每当在二叉排序树中插入（或删除）一个结点时，首先检查其插入路径上的结点是否因为此次操作而导致了不平衡。若导致了不平衡，则先找到插入路径上离插入结点最近的平衡因子的绝对值大于1的结点A，再对以A为根的子树，在保持二叉排序树特性的前提下，调整各结点的位置关系，使之重新达到平衡
平衡二叉树的插入过程的前半部分与二叉排序树相同，但在新结点插入后，若造成查找路径上的某个结点不再平衡，则需要做出相应的调整。一般可归纳为下列4种情况
- LL平衡旋转（右单旋转）。在结点A的左孩子（L）的左子树（L）上插入了新结点。此时将A的左孩子向右上旋转代替A成为根结点，将A结点向右下旋转成为B的右子树的根结点，而B的原右子树则作为A结点的左子树
- RR平衡旋转（左单旋转）。基本上和LL一样，将A的右孩子B向左上旋转代替A成为根结点，将A结点向左下旋转成为B的左子树的根结点，而B的原左子树则作为A结点的右子树
- LR平衡旋转（先左后右双旋转）。在A的左孩子的右子树上插入新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置，然后再把该C结点向右上旋转提升到A结点的位置
- RL平衡旋转（先右后左双旋转）。先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置，然后再把该C结点向左上旋转提升到A结点的位置
3. 平衡二叉树的查找
过程与二叉排序树相同。平均查找长度为$O(\log_2n)$
哈夫曼树和哈夫曼编码
哈夫曼树
特殊类型二叉树，高效存储字符，基于使用频率
术语
- 路径 path
- 路径长度 path length
- 结点路径长度
- 二叉树路径长度
- 结点的权重
- 带权路径长度（结点）
- 二叉树带权路径长度
定义
在许多实际应用中，树中结点常常被赋予一个表示某种意义的数值，称为该结点的权。从树根结点到任意结点的路径长度（经过的边数）与该结点上权值的乘积，称为该结点的带权路径长度。树中所有叶子结点的带权路径长度之和称为该树的带权路径长度，记为
$$W!P!L=\sum^n_{i=1}w_il_i$$
其中，$w_i$是第i个叶子结点所带的权值，$l_i$是该叶子结点到根结点的路径长度
在含有n个带权叶子结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称最优二叉树
哈夫曼树的构造
给定n个结点
- 将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F
- 构造一个新结点，从F中选取两棵根结点权值最小的树作为新结点的左右子树，并且将新结点的权值置位左右子树上根结点的权值之和
- 从F中删除选出的两棵树，同时将新得到的树加入F中
- 重复步骤2和3，直至F中只剩下一棵树为止
例子：
1 | graph nodes{ |
1 | graph huffmanTree{ |
哈夫曼树不唯一
哈夫曼编码 Huffman Code
对于待处理的一个字符串序列，若对每个字符用同样长度的二进制位表示，则称这种编码方式为固定长度编码。若允许对不同字符用不等长的二进制位表示，则这种方式成为可变长度编码。可变长度编码可以对频率高的字符赋予短编码，节省空间，但可能有一个编码是另一个编码的前缀，产生二义性。
若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码。
可以利用哈夫曼树得到前缀编码，称为哈弗曼编码。将每个出现的字符当作一个独立的结点，其权值为它出现的频度（或次数），构造出对应的哈夫曼树。所有字符结点都出现在叶子结点中。可将字符的编码解释为从根到该字符的路径上边标记的序列，其中边标记为0表示“转向左孩子”，边标记为1表示“转向右孩子”
左右结点的顺序是任意的，构造出的哈夫曼树并不唯一，但各哈夫曼树的带权路径长度相同且为最优
第五章 图
图的基本概念
图的定义
图G由顶点集V和边集E组成，记为G=(V,E)
$V={v_1,v_2,…,v_n}$，则用|V|表示图G中顶点的个数，也称图G的阶
$E={(u,v)|u\in V, v\in V}$,用|E|表示图G中边的条数
u,v有序则E称为有向边，记作<u,v>
u,v无序则E称为无向边，记作(u,v)
以下是图的一些基本术语
1. 有向图
E是有向边（也称弧）的有限集合时，则图G为有向图。弧是顶点的有序对，记作<v,w>，v称为弧尾，w称为弧头。<v,w>称为从顶点v到顶点w的弧，也称v邻接到w，或w邻接自v
2. 无向图
E是无向边（简称边）的有限集合时，则图G为有向图。边是顶点的无序对，记为(v,w)或(w,v)。可以说顶点w和顶点v互为临界点。边<v,w>依附于顶点w和v，或者说边(v,w)和顶点v,w相关联
3. 简单图
满足
- 不存在重复边
- 不存在顶点到自身的边
4. 多重图
不是简单图的就是多重图
5. 完全图（也称简单完全图）
任意两个顶点间都有边
- 无向图：n(n-1)/2条边
- 有向图：n(n-1)条边
6. 子图
设有两个图G=(V,E)和G’=(V’,E’)，若V’是V的子集，且E’是E的子集，则称G’是G的子图。若V(G’)=V(G)，则称其为G的生成子图
7. 连通、连通图和连通分量
- 连通：在无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的
- 连通图：任意两个顶点间有路径可达的无向图
- 连通分量：极大连通子图（不能是图中某个连通部分的子图）。任何连通图的连通分量都只有一个，即使是其本身；非连通的无向图有多个连通分量
例：
图中连通分量有三个，分别为ALMJBFC，DE，GIKH。而像ACF这样的连通子图则不能称为连通分量
极大连通子图：包含连通子图中所有的边
极小连通子图：只有连通图有极小连通子图，是保持图连通，又要使边数最小的子图。连通图顶点集确定的生成树是该连通图的极小连通子图，不唯一
极大连通子图是讨论连通分量的,极小连通子图是讨论生成树的
8. 强连通图、强连通分量
- 强连通图：任意两个顶点间有路径可达的有向图
- 强连通分量：极大强连通子图
9. 生成树、生成森林
- 生成树：包含图中全部顶点的一个极小连通子图。若图中顶点数为n，则它的生成树的边数为n-1。对生成树而言，若砍去一条边，则会变成非连通图，若加上一条边则会形成一个回路
10. 顶点的度、入度和出度
对于无向图，顶点v的度是指依附于该顶点的边的条数，记为TD(v)
对于有向图，入度是指到达的边的条数，出度是指发出的边的条数，度=入度+出度
11. 边的权和网
在一个图中，每条边都可以标上具有某种含义的数值，该数值称为改边的权值。这种边上带有权值的图称为带权图，也称网
12. 稠密图、稀疏图
边数很少的图称为稀疏图，反之称为稠密图。这是模糊的概念，往往是相对而言的。一般当|E|<|V|log|V|时，可以视为稀疏图
13. 路径、路径长度和回路
- 路径：顶点的序列
- 长度：经过的边的条数
- 加权长度：边的权值之和
- 自环：开始和结束同一个顶点的边
- 回路（环）：起始顶点和结束顶点相同的路径
若一个图有n个顶点，并且有大于n-1条边，则该图一定有环
14. 简单路径、简单回路
- 简单路径：在路径序列中，顶点不重复出现的路径
- 简单回路：除起始顶点和结束顶点外，其余顶点不重复出现的回路
15. 距离
从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。若从u到v根本不存在路径，则记该距离为无穷
16. 有向树
一个顶点的入度为0，其余顶点的入度均为1的有向图，称为有向树
图的存储及基本操作
邻接矩阵法
用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息（即各顶点之间的邻接关系），存储顶点之间邻接关系的二维数组称为邻接矩阵
无权图的邻接矩阵：相邻两点有边记为1，无边记为0，对角线也为0
带权图的邻接矩阵：相邻两点有边记为该边的权值，无边记为无穷大，对角线记为0（不同版本的教材有出入，有些也记为无穷。但对于实际应用（如求最短路径算法）来说，存0更为合理）
代码定义
1 |
|
注意：
- 在简单应用中，可直接用二维数组作为图的邻接矩阵（顶点信息等均可省略）
- 当邻接矩阵中的元素仅表示响应的边是否存在时，EdgeType可定义为值为0和1的枚举类型
- 无向图的邻接矩阵是对称矩阵，对规模特大的邻接矩阵可采用压缩存储
- 邻接矩阵表示法的空间复杂度为$O(n^2)$，其中n为图的顶点数|V|
邻接矩阵有以下特点：
- 无向图的邻接矩阵一定是一个对称矩阵（并且唯一）。因此，在实际存储邻接矩阵时只需存储上（或下）三角矩阵的元素
- 对于无向图，邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的度
- 对于有向图，邻接矩阵的第i行非零元素的个数是第i个顶点的出度，第i列非零元素的个数是第i个顶点的入度
- 用邻接矩阵存储图，很容易确定图中任意两个顶点之间是否有边相连。但是要确定图中有多少条边，则必须按行按列对每个元素进行检测，开销很大
- 稠密图适合使用邻接矩阵存储
邻接表法
当一个图为稀疏图时，使用邻接矩阵存储要浪费大量的存储空间
邻接表结合了顺序存储和链式存储，把顶点存入数组，依附于该顶点的边存入链表。类似于树的孩子表示法
对图G中每个顶点vi建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对于有向图是以顶点vi为尾的弧），这个单链表称为顶点vi的边表（对于有向图则称为出边表）。边表的头指针和顶点的数据信息采用顺序存储（称为顶点表）。所以在邻接表中存在两种结点：顶点表结点和边表结点，如图,左为顶点表结点，右为边表结点
邻接表中边的顺序不重要
1 |
|
邻接表有以下特点：
- 若G为无向图，则所需的存储空间为O(|V|+2|E|)；若G为有向图，则所需的存储空间为O(|V|+|E|)。前者的倍数2是由于无向图中，每条边在邻接表中出现了两次
- 对于稀疏图，采用邻接表表示将极大节省存储空间
- 在邻接表中，给定一顶点，能很容易找出所有它的邻边，因为只需要读取它的邻接表。在邻接矩阵中，相同的操作则需要扫描一行，花费的时间为O(n).但是，若要确定给定的两个顶点之间是否存在边，则在邻接矩阵中可以立刻查到，而在邻接表中则需要遍历边表查找，效率较低
- 在有向图的邻接表表示中，求一个给定顶点的出度只需计算其邻接表中的结点个数；但求其顶点的入度则需要遍历全部的邻接表。因此，也有人采用逆邻接表的存储方式来加速求解给定顶点的入度。当然，这实际上与邻接表是类似的
- 图的邻接表并不唯一，因为边表中结点的顺序可以变
十字链表
十字链表是有向图的一种链式存储结构。在十字链表中，对应于有向图中的每条弧有一个点，对应于每个顶点也有一个结点。这些结点的结构如下图所示：
弧结点中：尾域（tailvex）和头域（headvex）分别指示弧尾和弧头这两个结点在图中的位置；链域hlink指向弧头相同的下一条弧；链域tlink指向弧尾相同的下一条弧；info域指向该弧的相关信息。这样，弧头相同的弧就在同一个链表上，弧尾相同的弧也在同一个链表上
顶点结点中：info（data）域存放顶点相关的数据信息，如顶点名称；firstin和firstout两个域分别指向以该顶点为弧头或弧尾的第一个弧结点
下图为有向图的十字链表表示法。注意，顶点结点之间是顺序存储的
编程语言定义如下：
1 |
|
在十字链表中，既容易找到vi为尾的弧，又容易找到vi为头的弧，因而容易求得顶点的出度和入度。
图的十字链表表示不是唯一的，但一个十字链表表示确定一个图
邻接多重表
邻接多重表是无向图的另一种链式存储结构
在邻接表中，容易求得顶点和边的各种信息，但在邻接表中求两个顶点之间是否存在边而对边执行删除等操作时，需要分别在两个顶点的边表中遍历，效率较低
与十字链表类似，在邻接多重表中，每条边用一个结点表示，其结构如下所示
mark用于标记该条边是否被搜索过；ivex和jvex为该边依附的两个顶点在图中的位置；ilink指向下一条依附于顶点ivex的边；jlink指向下一条依附于顶点jvex的边，info为指向和边相关的各种信息的指针域
每个顶点也用一个结点表示，它由如下所示的两个域组成
其中，data(vertex)域存储该顶点的相关信息，firstedge域指示第一条依附于该顶点的边
在邻接多重表中，所有依附于同一顶点的边串联在同一链表中，由于每条边依附于两个顶点，因此每个边结点同时链接在两个链表中
如图为无向图的邻接多重表表示。注意，每条边只有一个结点
1 | graph l{ |
编程语言定义如下：
1 |
|
图的基操
独立于图的存储结构。对于不同的存储方式，操作算法的具体实现会有不同的性能
图的基本操作主要包括
- Adjacent(G,x,y): 判断图G是否存在边<x,y>或(x,y)
- Neighbors(G,x): 列出图G中与结点邻接的边
- InsertVertex(G,x): 在图G中插入顶点x
- DeleteVertex(G,x): 在图G中删除顶点x
- AddEdge(G,x,y): 若无向边(x,y)或有向边<x,y>不存在，则向G中添加该边
- RemoveEdge(G,x,y): 若无向边(x,y)或有向边<x,y>存在，则从图G中删除该边
- FirstNeighbor(G,x): 求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1
- NextNeighbor(G,x,y): 假设图中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1
- GetEdgeValue(G,x,y): 获取图G中边(x,y)或<x,y>对应的权值
- SetEdgeValue(G,x,y,v): 设置图G中边(x,y)或<x,y>对应的权值为v
图的遍历
广度优先搜索
类似于二叉树的层次遍历
没有往回退的情况，因此不是一个递归的算法。
需要借助一个辅助队列，以记忆正在访问的顶点的下一层顶点
伪代码如下
1 | bool visited[MAX_VERTEX_NUM]; //访问标记数组 |
深度优先搜索
类似于树的先序遍历
1 | bool visited[MAX_VERTEX_NUM]; //访问标记数组 |
注意：对于同样一个图，基于邻接矩阵的遍历所得到的DFS序列和BFS序列是唯一的，基于邻接表的遍历所得到的DFS序列和BFS序列是不唯一的
图的遍历与图的连通性
图的遍历算法可以用来判断图的连通性
无向图如果连通，则从任一结点出发，仅需一次遍历就能访问图中所有顶点；无向图如果不连通，一次遍历只能访问到该结点所在的连通分量。对于有向图来说，如果从初始点到图中每个顶点都有路径，则能够访问到图中的所有顶点，否则不能访问到所有顶点
故在BFSTraverse或DFSTraverse中添加了第二个for循环，再选取初始点，继续进行遍历，以防止一次无法遍历图的所有顶点。对于无向图，上述两个函数调用BFS(G,i)或DFS(G,i)的次数等于该图的连通分量数。有向图情况不同，非强连通分量调用一次BFS(G,i)或DFS(G,i)甚至无法访问到该连通分量的所有顶点
图的应用
最小生成树
连通图的顶点集确定的生成树是图的极小连通子图，它包含图中所有顶点，含有尽可能少的边。如果砍去它的一条边，则会使生成树变成非连通图；若增加一条边，就会形成一条回路
对于一个带权连通无向图G=(V,E)，生成树不同，每棵树的权（所有边权值之和）也可能不同。设R为G的所有生成树的集合，若T为R中边的权值之和最小的那课生成树，则T称为G的最小生成树
性质：
- 最小生成树不唯一。当图G中的各边权值互不相等是，G的最小生成树唯一；若G的边数比顶点数少1，则G的最小生成树为它本身
- 最小生成树的边的权值之和唯一
Kruskal算法
每次在边集中找不会形成环的最小的边，添加到生成树，直到生成树全部连通
适用于求解边稀疏而顶点较多的图
Prim算法
类似于Dijkstra算法
- 假定V={1,2,…,n}，以集合U={1}开始，每次添加一个顶点
- 找当前最短一条边(u,v) u属于U v属于V-U
适用于求解边稠密的图
最短路径
Dijkstra算法
非负权重 单点源头
贪心策略
核心思想：每次得到的最短的暂定最短路径对应的点被添加进已知
一个集合S，用于记录已求得的最短路径的顶点，用一个数组s[]来实现，初始化为0，s[vi]=1时表示将顶点$v_i$放入S，初始时把源点$v_0$放入S
两个辅助数组
- dist[]: 记录从源点$v_0$到其他各顶点的最短路径长度，dist[i]的初值为arcs[v0][i]
- path[]: path[i]表示从源点到顶点i之间的最短路径的前驱结点，在算法结束时，可根据其值追溯得到源点$v_0$到顶点$v_i$的最短路径
步骤
- 初始化
S<–{$v_0$}
dist[j]<–edge[0][j]
- 找最短路径
dist[j]<–min{dist[i]}
S<–S并{k} - 更新
对每一个$i\in V-S$
dist[i]<–min{dist[i],dist[k]+edge[k][i]} - 如果使得S=V，返回。否则重回第一步
算法复杂度为$O(|V|^2)$
Floyd算法
权值均大于0的有向图，对每对顶点$v_i\neq v_j$都求出最短路径和最短路径长度
基本思想：递推产生一个n阶方阵序列$A^{(-1)},A{(0)},…,A^{(n-1)}$，其中$A^{(k)}[i][j]$表示从顶点$v_i$到$v_j$的路径长度，k表示绕行第k个顶点的运算步骤。初始时，对于任意两个顶点$v_i$和$v_j$，若它们之间存在边，则以此边上的权值作为它们之间的最短路长度；若它们之间不存在有向边，则以$\infty$作为它们之间的最短路长度。以后逐步尝试在原路径中加入顶点k(k=0,1,…,n-1)作为中间顶点。若增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径。
算法描述：定义一个n阶方阵序列$A^{(-1)},A^{(0)},…,A^{(n-1)}$，其中
$$A^{(-1)}[i][j]=arcs[i][j]$$
$$A^{(k)}[i][j]=Min{A^{(k-1)}[i][j],A^{(k-1)}[i][k]+A^{(k-1)}[k][j]},k=0,1,…,n-1$$
式中，$A^{(0)}[i][j]$是从顶点$v_i$到$v_j$、中间顶点是$v_0$的最短路径的长度，$A^{(k)}[i][j]$是从顶点$v_i$到$v_j$、中间顶点的序号不大于k的最短路径的长度。Floyd算法是一个迭代的过程，每迭代一次，在从$v_i$到$v_j$的最短路径上就多考虑了一个顶点；经过n次迭代后，所得到的$A^{(n-1)}[i][j]$就是$v_i$到$v_j$的最短路径长度，即方阵$A^{(n-1)}$中就保存了任意一对顶点之间的最短路径长度
算法复杂度为$O(|V|^3)$
代码
1 | for(k=1;k<=n;k++) |
不能解决带有“负权回路”（或者叫“负权环”）的图，因为带有“负权回路”的图没有最短路
网络流
AOV网络（用顶点表示活动的网络）
有向无环图：若一个有向图中不存在环，则称为有向无环图，简称DAG图
AOV网：若用DAG图表示一个工程，其顶点表示活动，用有向边<Vi,Vj>表示活动Vi必须先于活动Vj进行的这样一种关系，则将这种有向图称为顶点表示活动的网络，简称AOV网
边的起点是终点的先决条件，拓扑序列不破坏先决条件
拓扑排序：在凸轮中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序
- 每个顶点出现且只出现一次
- 若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径
生成拓扑排序的步骤：
- 选择一个入度为0的顶点
- 把它加入序列
- 把这个顶点和它发出的边从图里删除
- 重复以上步骤知道图里没有顶点
AOE网络（用边表示活动的网络）
有向边：活动
顶点：指示活动的开始和结束
Number：权值
AOE网络的性质：
- 只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始
- 只有在进入某一顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生
AOE网络可用于求关键路径
仅有一个入度为0的顶点，称为源点，仅有一个出度为0的顶点，称为汇点
从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径，关键路径上的活动称为关键活动
寻找关键活动会用到的参量：
- 最早开始时间 e(ai)
- 最晚开始时间 l(ai)：不影响后续活动的开始时间的最晚时间
l(ai)-e(ai)越大代表事件ai越不重要，越小越重要
第六章 查找
查找的基本概念
- 查找：在数据集合中寻找满足某种条件的数据元素的过程
- 查找表（查找结构）：用于查找的数据集合称为查找表。操作有4种：1.查询某个特定的数据元素是否在查找表中 2. 检索满足条件的某个特定的数据元素的各种属性 3. 在查找表中插入一个数据元素 4. 从查找表中删除某个数据元素
- 静态查找表：只涉及上面1,2两种操作的查找表。反之则称为动态查找表。适合静态查找表的方法有顺序查找、折半查找、散列查找等；适合动态查找表的方法有二叉排序树的查找、散列查找等
- 关键字：数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找
- 平均查找长度：所有查找过程中进行关键字的比较次数的平均值，数学定义为$$ASL=\sum^n_{i=1}P_iC_i$$n是查找表的长度；Pi是查找第i个数据元素的概率，一般认为每个数据元素的查找概率相等，即Pi=1/n；Ci是找到第i个数据元素所需进行的比较次数
顺序查找
顺序查找也称线性查找
1. 一般线性表的顺序查找
基本思想：从线性表的一端开始，逐个检查关键字是否满足给定的条件。算法如下：
1 | typedef struct { //查找表的数据结构 |
在上述算法中，将ST.elem[0]称为“哨兵”。引入它的目的是使得Search_Seq内的循环不必判断数组是否会越界，因为满足i==0时，循环一定会跳出。引入“哨兵”并不是这个算法独有的
缺点：当n较大时，平均查找长度较大，效率低
优点：对数据元素的存储没有要求，顺序存储或链式存储都可。对表中记录的有序性也没有要求，无论记录是否按关键码有序，均可应用
注意，对线性的链表只能进行顺序查找
2. 有序表的顺序查找
假设表L是按关键字从小到大排列的，查找的顺序是从前往后，待查找元素的关键字为key，当查找到第i个元素时，发现第i个元素对应的关键字小于key，但第i+1个元素对应的关键字大于key，这事就可返回查找失败的信息
可用判定树来描述有序顺序表的查找过程。树中的圆形结点表示有序顺序表中存在的元素；树中的矩形结点称为失败结点（注意，若有n个查找成功结点，则必定相应地有n+1个查找失败结点），它描述的是那些不在表中的数据值的集合
折半查找
折半查找又称二分查找，它仅适用于有序的顺序表
算法如下：
1 | int Binary_Search(SeqList L,ElemType key) { |
分块查找
分块查找又称索引顺序查找，它吸收了顺序查找和折半查找各自的优点，既有动态结构，又适于快速查找
基本思想：将查找表分为若干子块，块内的元素可以无序，但块之间是有序的，而第一个块中的最大关键字小于第二个块中的所有记录的关键字，第二个块中的最大关键字小于第三个块中的所有记录的关键字，以此类推。再建立一个索引表，索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址，索引表按关键字有序排列
分块查找的过程分为两步：第一步是在索引表中确定待查记录所在的块，可以顺序查找或折半查找索引表；第二步是在块内顺序查找
B树和B+树
B树及其基本操作
B树，本质为m叉搜索树，有助于减少硬盘读取，m称为B树的阶
一棵m阶B树或为空树，或满足以下要求
树中每个结点至多有m棵子树（即至多含有m-1个关键字）
若根结点不是终端结点，则至少有两棵子树
除根结点外的所有非叶结点至少有[m/2]（向上取整）棵子树（即至少含有[m/2]-1个关键字）
所有非叶子结点的结构如下：
n P0 K1 P1 K2 P2 ... Kn Pn
其中，$K_i(i=1,2,…,n)$为结点的关键字，且满足$K_1<K_2<…<K_n$；$P_i(i=0,1,…,n)$为指向子树根结点的指针，且指针$P_{i-1}$所指子树中所有结点的关键字均小于$K_i$，$P_i$所指子树中所有结点的关键字均大于$K_i$，$n（[m/2]-1\leqslant n\leqslant m-1）$为结点中关键字的个数
- 所有叶子结点在同一层
B树的插入
每次都插入到叶子结点，如果结点所含关键字超过个数限制，取中间的上移，假如有偶数个，就取小的那个，如果上一层也满了，继续取中间的上移
向4阶B树中依次插入6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4，动画如下：
B树的删除
叶子结点直接删
内部结点，找下一层比它大的最小数上移至它的位置
如果删后结点关键字个数太少，打破了[m/2]-1的规则，此时如果左右兄弟结点有多余的结点，则借给它，如果没有，则从父结点借
详细情况见此链接：B树的删除操作，5种情况图解
B+树的基本概念
一种B树的变形树
一棵m阶B+树满足下列条件
- 每个分支结点最多有m棵子树
- 非叶子根结点至少有两棵子树，其他每个分支结点至少有[m/2]棵子树
- 结点的子树个数与关键字个数相等
- 所有叶子结点包含全部关键字及指向相应记录的指针，叶子结点中将关键字按大小顺序排列，并且相邻叶子结点按大小顺序相互链接起来
- 所有分支结点（可视为索引的索引）中仅包含它的各个子结点（即下一级的索引块）中关键字的最大值及指向其子结点的指针
B+树和B树的区别在于
- 非叶子结点只起到索引作用，不包含具体数据
- 每个关键字对应一棵子树
- 每个结点的关键字范围为$[m/2]\leqslant n\leqslant m$
- 叶子结点包含了全部关键字，即在非叶子结点中出现的关键字也会出现在叶子结点中
下图为一个4阶B+树的例子
散列（哈希）
词典存储了很多的键值对，能够更快地搜索
单词名：键 解释：值
散列查找比二分查找更快，拥有常数级的时间复杂度
散列表（Hash table）
支持操作：
- 查找
- 插入
- 删除
数据间没有线性关系，因此不支持以下操作：
- 求最小值或最大值
- 找前驱后继数据
- 找一个范围内的数据
- 按顺序列出数据
不可行的思路
全部键值和位置一一对应 浪费空间
可行的思路
数据的可能取值范围为N，实际为K
散列表的大小设为大于K（多一些），小于N（远远小于）的M，即M<<N
K个数怎么存到M中
通过散列函数 $H(k)$ 计算出相应位置（散列地址）$H(K_i)$
散列函数
一个把查找表中的关键字映射成该关键字对应的地址的函数，记为Hash(key)=Addr（这里的地址可以是数组下标、索引或内存地址等）
散列函数可能会把两个或两个以上的不同关键字映射到同一地址，称这种情况为冲突，发生冲突的不同关键字称为同义词。一方面，设计得好的散列函数应尽量减少这样的冲突；另一方面，由于这样的冲突总是不可避免的，所以还要设计好处理冲突的方法
散列函数的构造方法
在构造散列函数时，必须注意以下几点：
- 散列函数的定义域必须包含全部需要存储的关键字，而值域的范围则依赖于散列表的大小或地址范围
- 散列函数计算出来的地址应该能等概率、均匀地分布在整个地址空间，从而减少冲突的发生
- 散列函数应尽量简单，能够在较短的时间内计算出任一关键字对应的散列地址
1. 直接定址法
直接去关键字的某个线性函数值为散列地址，散列函数为
$$H(key)=a\times key+b$$
式中，a和b是常数。这种方法计算最简单，且不会产生冲突。它适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费
2. 除留余数法
最简单、最常用。假定散列表表长为m，取一个不大于m但最接近或等于m的质数p，利用以下公式把关键字转换成散列地址。散列函数为
$$H(key)=key\mod p$$
除留余数法的关键是选好p，使得每个关键字通过该函数转换后等概率地映射到散列空间上的任一地址，从而尽可能减少冲突
3. 数字分析法
设关键字是r进制数，则r个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀一些，每种数码出现的机会均等；而在某些位上分布不均匀，只有某几种数码经常出现，此时应选取数码分布较为均匀的若干位作为散列地址。这种方法适合于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数
4. 平方取中法
顾名思义，这种方法取关键字的平方值的中间几位作为散列地址。具体取多少位要根据实际情况而定。这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀，适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数
5. 折叠法
将关键字分割成位数相同的几部分（最后一部分的位数可以短一些），然后取这几部分的叠加和作为散列地址，这种方法称为折叠法。关键字位数很多，而且关键字中的每位上数字分布大致均匀时，可以采用折叠法得到散列地址
方法2是重点
实际情况中会用String作为key
- 方法1：把字符的ASCII码相加。缺点是但不能均匀分布
- 方法2：取前三个字母的ASCII码值
- 方法3：将所有字符的ASCII值乘以权重相加
处理冲突的方法
1. 分离链法（拉链法、链接法、chaining）
把所有散列地址一样的放入一条链表中
2. 开放定址法
发生冲突时存到别的位置
数学递推公式为
$$H_i=(H(key)+d_i)\mod m$$
其中，$i=0,1,2,…,k(k\leqslant m-1)$；$m$代表散列表表长；$d_i$为增量序列
怎么找其他位置？
线性探测法 Linear probing
$d_i=0,1,2,…,m-1$
问题：冲突太多，每次都会争夺后一个元素的位置，容易形成簇
一般不用
平方探测法
$d_i=i^2$
问题：初始地址一样的探测地址也一样，会形成二次簇
双散列法（再散列法）
定义两个散列函数。一个求散列地址，一个$Hash_2(key)$。每次往下谈$Hash_2(key)$
当通过第一个散列函数H(key)得到的地址发生冲突时，则利用第二个散列函数$Hash_2(key)$计算该关键字的地址增量。它的具体散列函数形式如下：
$$H_i=(H(key)+i\times Hash_2(key))\mod m$$
i代表冲突的次数，初始为0.双散列法中，最多经过m-1次探测就会遍历表中所有位置，回到$H_0$位置
伪随机序列法
$d_i$为伪随机数序列时
实际上平方探测法用的最多
注意：在开放定址的情形下，不能随便物理删除表中的已有元素，因为若删除元素，则会截断其他具有相同散列地址的元素的查找地址
第七章 排序
概念
- 稳定性：两个关键字同等的元素，排序前后相对的顺序不变。说明不稳定性只要举出反例即可。
- 具有稳定性的算法：直接插入排序、折半插入排序、冒泡排序、归并排序、基数排序
- 不稳定的算法：希尔排序、快速排序、简单交换排序、堆排序
- 内部排序：在排序期间元素全部存放在内存中。
- 外部排序：在排序期间元素无法全部同时存放在内存中，必须根据需要不断地在内存、外村之间移动。外部排序一般是文件太大，必须存放在磁盘上。
插入排序
直接插入排序
- 特点：待排序数组一部分是有序的，另一部分是无序的。
- 时间效率：当数组元素有序时，$f(n)=O(n)$。一般情况下，$f(n)=O(n^2)$。
折半插入排序
- 主要针对直接插入排序的定位算法进行优化。定位更快，插入不变。
- 时间效率：$f(n)=O(n^2)$。
- 希尔排序
- 设置步长d将表分块，在不同块中使用直接插入排序，逐步缩小d指到1。
- 不稳定的算法
- 仅适用于顺序存储的线性表
- 时间效率：较佳情况下$f(n)=O(n^{1.3})$，最坏情况$f(n)=O(n^2)$。
交换排序
- 冒泡排序
- 时间效率：当数组元素有序时，$f(n)=O(n)$。一般情况下$f(n)=O(n^2)$。
- 快速排序
通过一趟排序将排序表划分为左右两部分，使得左边所有元素小于右边所有元素。
从前往后查看元素，标记为i；从后往前查看元素，标记为j。
先从j开始，如果a[j]>a[i],则j–；否则swap（a[i],a[j]）,并将主动权给到i。
从i开始后，如果a[j]>a[i],则i++；否则swap（a[i],a[j]）,并将主动权还给j。
最后直到满足一轮排序的要求。效率：当数组元素有序时，$f(n)=O(n^2)$。一般情况下，$f(n)=O(n*log_2n)$
在快排中，不会产生有序序列，但每趟排序会将一个元素放到最终位置上。
选择排序
简单选择排序
- 每一趟选一个最小的放到最前面
堆排序
堆的定义：n个关键字序列$L[1…n]$称为堆，当且仅当该序列满足其中一条：
- $L(i)\leqslant L(2i)$且$L(i)\leqslant L(2i+1)$
- $L(i)\geqslant L(2i)$且$L(i)\geqslant L(2i+1)$
小根堆：最小元素存放在根结点中，对任意非根结点，它的值$\geqslant$其双亲结点的值。
堆排序：一种树形排序方法，将$L[1…n]$看作一棵完全二叉树的顺序存储结构。
堆的构造：先按初始序列建造成完全二叉树的形式，再进行调整，反复调整。
堆的删除：只能删除堆顶元素，删除前先将最后一个元素和堆顶元素交换，再向下调整。
堆的插入：插入在堆的末端，再向上调整。
空间复杂度：$O(1)$
时间复杂度：建堆时间$O(n)$，调整时间$O(h)$。排序时间始终是$O(nlog_2n)$。
归并排序
- 归并：将两个或两个以上的有序表组合成一个新的有序表。
- 空间复杂度：$O(n)$
- 时间复杂度：每趟归并$O(n)$，归并次数$log_2n$。最终时间$O(nlog_2n)$。
优点：
- 归并排序的效率达到了巅峰：时间复杂度为O(nlogn)，这是基于比较的排序算法所能达到的最高境界
- 归并排序是一种稳定的算法（即在排序过程中大小相同的元素能够保持排序前的顺序，3212升序排序结果是1223，排序前后两个2的顺序不变），这一点在某些场景下至关重要
- 归并排序是最常用的外部排序方法（当待排序的记录放在外存上，内存装不下全部数据时，归并排序仍然适用，当然归并排序同样适用于内部排序）
基数排序
- 多关键字排序思想。对单关键字采用“分配”和“收集”两种操作。
- r是辅助存储空间，即r个队列。n是n个元素。
- 空间复杂度：$O(r)$
- 时间复杂度：$O(d(n+r))$ d是关键字位数
总结
1） 快速排序和堆排序相比，选择堆排序的理由：
- 快排需要使用递归栈，堆排序辅助空间只有$O(1)$。
- 快排最慢可达到$O(n^2)$，堆排序始终是$O(nlog_2n)$。