数据结构
数据结构
ccb数据结构
线性表:具有相同特性的数据元素的一个有限序列。
具有有穷性、一致性(所有元素的性质相同)、序列性(所有元素的相对位置是线性的,即存在唯一的开始元素和终端元素,除此之外每个元素只有唯一的前驱元素和后继元素)。
线性表的顺序存储结构:顺序表,借助数组实现(数组存放线性表元素、另外一个int型的值存放线性表长度)。
顺序表求线性表长度、按索引取元素的时间复杂度为O(1),按值查找元素的时间复杂度为O(n),插入、删除元素的平均时间复杂度为O(n)。
1 链表
线性表的链式存储结构:链表。
可分为单链表、双链表、循环链表。
链表可用来表示线性表,也可以用来表示各种非线性的数据结构。
1.1 单链表
单链表结点类型描述如下:
1 | typedef struct LNode { |
单链表的建立:
头插法
常用在将一个已存在的链表逆序。
1
2
3
4
5
6
7
8ListNode * L = new ListNode(-1);
L->next = NULL;
for(int i=0;i<n;i++){
ListNode * s = new ListNode(-1);
s->data = a[i];
s->next = L->next; // 头插法
L->next = s;
}**==使用头插法将链表x逆序==**:
1
2
3
4
5
6
7
8
9
10
11
12
13typedef struct item{
char C;
struct item next:
}Item;
Item *Routinel (Item *x) {
Item *prev=NULL, *curr=x;
while(curr) { // 遍历结点
Item next=curr->next;
curr->next=prev; // 头插法
prev=curr; // 更新指针
curr=next;
return prev;
}尾插法
需要增加一个尾指针,始终指向当前链表的尾结点。
1
2
3
4
5
6
7
8
9ListNode * L = new ListNode(-1);
ListNode * r;
r = L; // 初始化尾指针r
for(int i=0;i<n;i++){
ListNode * s = new ListNode(-1);
s->data = a[i];
r->next = s; // 尾插法
r = s;
}单链表的插入、删除、取元素的时间复杂度均为O(n);求线性表长度的时间复杂度为O(n);求线性表中某个元素的值、按值查找元素、以及插入、删除元素的时间复杂度均为O(n)。
顺序表和链表的比较:
- 存取方式
顺序表可以顺序存取,也可以随机存取,链表只能从表头顺序存取元素。
- 查找、插入和删除操作
对于按值查找,当顺序表在无序的情况下,两者的时间复杂度均为O(n);而当顺序表有序时,可采用折半查找,此时时间复杂度为O(log2n)。 对于按序号查找,顺序表支持随机访问,时间复杂度仅为O(1),而链表的平均时间复杂度为O(n)。 顺序表的插入、删除操作,平均需要移动半个表长的元素,因此平均时间复杂度为O(n)。链表的插入、删除操作时,只需要修改相关结点的指针域即可,时间复杂度均为O(n)。
3)空间分配
链式存储的结点空间在需要的时候申请分配,操作灵活、高效。
1.2 快慢指针
快慢指针中的快慢指的是移动的步长,即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动2,慢指针每次向前移动1次。
用途:
==判断单链表是否存在环==
如果链表存在环,就好似操场的跑道是一个环形。此时让快、慢指针都从链表头开始遍历,快指针每次向前移动两个位置,慢指针每次向前移动一个位置;如果快指针到达NULL,说明链表以NULL为结尾,没有环。如果快指针追上慢指针,则表示有环。
==寻找循环链表的入口==
假设链表存在环,那么怎么寻找环的入口呢?
假设链表长为L,起始点到环入口长度为a,环长度为r,则L=atr, 如图11-3所示。
在快指针进入环到慢指针进入环前的这段时间,若环的长度较短,也许快指针已经走了好几圈了,然后慢指针进入环。
设慢指针和快指针在环内相遇时,慢指针在环内走了X步,走的总步数(包括环内与环外)为S步(显然
S=X+a
),那么快指针走了多少步呢?
快指针在环内已经走了n圈加X步,即nr+X
步,其中n最少为1,而走的总步数为nr+X+a
步。由于快指针走的总步数为慢指针的2倍,故nr+X+a=(X+a)*2
。由上式得a+X = nr
,即a = nr-X = (n-1)r+r-X
;因此a和r-x相差r的整数倍,也就是说,若令快慢指针的步长均为1,慢指针从链表头开始走,快指针从相遇点也继续往前走,两者走的距离为
a = (n-1)r+r-X
时,两者相遇,此时就是环入口的位置。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21ListNode* FindBeginning (ListNode* head) {
ListNode* n1=head;
ListNode* n2=head;
while (n2->next != NULL) {//寻找相遇点
n1=n1->next;
n2=n2->next->next;
if(n1==n2){ // 有环
break;
//没有相遇,因而没有环
if (n2->next == NULL) {
return NULL;
}
/*确定环入口,将n1从head开始移动,n2从相遇点处移动*/
n1=head;
while (n1 != n2) {
n1=n1->next;
n2=n2->next;
}
// 现在n2指向的就是环入口
return n2;
}在有序链表中寻找中位数
利用快慢指针可不借助计数器变量实现寻找中位数的功能。
原理是:快指针的移动速度是慢指针移动速度的2倍,因此当快指针到达链表尾时,慢指针到达中点。程序还要考虑链表结点个数的奇偶数因素,当快指针移动x次(每次2步)后到达表尾,说明链表有奇数个结点,直接返回慢指针指向的数据即可。如果快指针是倒数第二个结点,说明链表结点个数是偶数,这时可以根据“规则”返回上中位数或下中位数或(上中位数+下中位数)的一半。
事实上,像快慢指针这种用两个指针分别前进来查找某个结点,还有其他的形式。
例1:==寻找倒数第K个结点==。
我们可以定义两个指针,第一个指针从链表的头指针开始遍历向前走k-1步,第二个指针保持不动;从第k步开始,第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在k-1,当第一个指针到达链表的尾结点时,第二个指针正好是倒数第k个结点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14ListNode* findKthtoTail (ListNode* P, unsigned int k) {
assert(p != NULL && k >= 1);
ListNode* pa=p, *pb=p;
for(int i=0; i < k-1; ++i) {
pa-pa->pNext;
if(pa == NULL)
return NULL;// 当链表p的长度小于k的时候,返回NULL;
}
while (pa->pNext != NULL) {
pa=pa->pNext;
pb=pb->pNext;
}
return pb;
}例2:==确定两个单向链表是否相交,若相交找出第一个公共结点。==
解答:首先利用快慢指针判断链表是否有环。
- 如果都不存在环,则如果两个单向链表有公共的结点,也就是说两个链表从某一结点开始,它们的后继结点指针都指向同一个结点。但由于是单向链表的结点,每个结点只有一个next指针,因此从第一个公共结点开始,之后它们所有结点都是重合的,如下图所示。
如何寻找相较的第一个结点:
首先两个链表各遍历一次,求出两个链表的长度L1、 L2, 然后可得出两个链表的长度差L。然后先在长的链表上遍历L个结点,之后再同步遍历,于是在遍历中,第一个相同的结点就是第一个公共的结点。此时,如果第一个链表的长度为m,第二个链表的长度为n,该方法的时间复杂度为O(m+n)。
如果一个存在环,另一个不存在环,则这两个链表是不可能相交的;
如果利用快慢指针发现两个链表都存在环,则判断任意一个链表上快慢指针相遇的那个结点在不在另一条链表上(共环,末尾结点存在环中)。如果在,则相交,如果不在,则不相交。若相交,两个链表的入口点可能并不是环上同一个结点,则再利用本节的方法各自找出两个链表环的入口点,可以定义任一入口点为相交的第一个结点。
1.3 双链表
使得查找某个结点的前驱结点的时间复杂度从O(n)变为了O(1)。
双链表的插入操作
在双链表中p所指结点之后插入结点s
1
2
3
4s->next = p->next; // 将s结点插入p结点之后
p->next->prior = s;
s->prior = p;
p->next = s; // 最后修改p->next双链表的删除操作
删除双链表中结点p的后继结点q
1
2
3p->next = q->next;
q->next->prior = p;
free(q);
2 栈与队列
栈与队列同样是线性表,具有和线性表相同的逻辑结构,但是操作受限。
2.1 栈(堆栈)
栈,也叫堆栈,其限制是仅允许在表的一端进行插入和删除。人们把此端称为栈顶,栈顶的第一个元素被称为栈顶元素,相对地,把另一端称为栈底。向一个栈插入新元素又称为进栈或入栈(push),它是把该元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称为出栈或退栈(pop),它是把栈顶元素删除掉,使其下面的相邻元素成为新的栈顶元素。
由于堆栈数据结构只允许在一端进行操作,因而按照后进先出(LIFO, Last In First Out)的原理运作。
栈的顺序存储结构
1 | typedef struct{ |
栈空的条件:s->top == -1
。
栈满的条件:s->top == MaxSize-1
。
进栈:
1 | bool Push(SqStack * &s, ElemType e){ |
出栈:
1 | bool Pop(SqStack * &s, ElemType &e){ // 注意e为引用 |
取栈顶元素:
1 | bool GetTop(SqStack * &s, ElemType &e){ // 注意e为引用 |
销毁栈:free(s)。
栈的链式存储结构——链栈
1 | typedef struct linknode{ |
栈空的条件:s->next == NULL
。
栈满的条件:不考虑。
进栈:插入头节点之后
1 | bool Push(LinkStNode * &s, ElemType e){ |
出栈:
1 | bool Pop(LinkStNode * &s, ElemType &e){ // 注意e为引用 |
取栈顶元素:
1 | bool GetTop(LinkStNode * &s, ElemType &e){ // 注意e为引用 |
2.2 栈的应用
中缀表达式和后缀表达式
中缀表达式:运算符在数之间,如A+B*(C-D)-E/F
,需要考虑运算符的出现顺序、优先级,以及括号的使用。
后缀表达式(逆波兰式):把运算符放在两个运算对象之后。不存在括号,也不存在优先级的差别,计算过程按照运算符出现的先后次序进行。比如A+B*(C-D)-E/F
对应的后缀表达式为ABCD-*+EF/-
。
==中缀表达式转换为后缀表达式:==
方法一:使用两个栈实现
要使用到2个栈,stack栈用来存放运算符,post栈用来存放最后的后缀表达式。
转换原则是:从左向右扫描中缀表达式,若读到的是操作数,则直接存入post栈;若读到的是运算符:
该运算符为”(“,则直接存入stack栈;
该运算符为”)”,则将stack栈中第一个”(“前的所有运算符依次出栈,并依次存入post栈,但是”(“和”)”都不存入post栈;
若该运算符为非括号,则将该运算符和stack栈顶运算符进行比较,若高于栈顶运算符,则直接存入stack栈,否则将栈顶运算符出栈,存入post栈,然后继续与新的栈顶元素比较,直到该运算符能存入stack。(使得post中优先级高的运算符在前,或者说接近栈底)当扫描完后,stack栈中还有运算符时,则将所有的运算符出栈,存入post栈。
A+B*(C-D)-E/F
转换为后缀表达式的过程如下:
方法二:使用语法树实现
方法三:加括号法
- 先按照运算符的优先级对中缀表达式加括号,变成
((a+(b*c))+(((d*e)+f)*g))
- 将运算符移到括号的后面,变成
((a(bc)*)+(((de)*f)+g)*)+
- 去掉括号,得到
abc*+de*f+g*+
后缀表达式的求值
通过后缀表示计算表达式值的过程为:
顺序扫描表达式的每一项,然后根据它的类型做如下相应操作:如果该项是操作数,则将其压入栈中;如果该项是操作符<op>,则连续从栈中退出两个操作数Y和X,形成运算指令X<op>Y,并将计算结果重新压入栈中。当表达式的所有项都扫描并处理完后,栈顶存放的就是最后的计算结果。
2.3 Catalan数
卡特兰数(Catalan number)是组合数学中一个常出现在各种计数问题中的数列。
数列的前几项为:1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …
相关的经典问题:
进出栈序列
n个元素进栈序列为:1,2,3,4,…,n,则有多少种出栈序列?
将进栈表示为 +1,出栈表示为 -1,根据栈本身的特点,每次出栈的时候,必定之前有元素入栈,即对于每个 -1 前面都有一个 +1 相对应。因此,出栈序列的 所有前缀和 必然大于等于 0,并且 +1 的数量 等于 -1 的数量。
当出现某一前缀和小于0时(即出现前缀和等于-1的情况,-1的数量比+1多一个),该出栈序列就是非法的。假设+1和-1的数量均为n,将该前缀取反之后,就会变成+1的数量比-1多一个,即存在n+1个+1,n-1个-1。取反后的序列与之前的序列是一一对应的。因此,非法序列的数量有$C^{n+1}{2n}$。因此,合法的出栈序列的数量为$\LARGE C^{n}{2n}-C^{n+1}{2n}=\frac{C^{n}{2n}}{n+1}$。此时我们就得到了卡特兰数的通项$\LARGE \frac{C^{n}_{2n}}{n+1}$。
括号序列
n 对括号,则有多少种 “括号匹配” 的括号序列
左括号看成 +1,右括号看成 -1,那么就和上题的进出栈一样,每次有右括号的时候,必定之前有左括号匹配,且序列的 所有前缀和 必然大于等于 0,并且 +1 的数量 等于 -1 的数量。因此共有$\LARGE \frac{C^{n}_{2n}}{n+1}$种序列。
二叉树
n + 1
个叶子节点能够构成多少种形状不同的(国际)满二叉树(结点要么是叶子结点,要么它有两个子结点,且叶子节点均在最后一层)
使用深度优先搜索这个满二叉树,向左扩展时标记为 +1,向右扩展时标记为 -1。
由于每个非叶子节点都有两个左右子节点,所有它必然会先向左扩展,再向右扩展。总体下来,左右扩展将会形成匹配,即变成进出栈的题型。n + 1
个叶子结点会有 2n 次扩展,构成$\LARGE \frac{C^{n}_{2n}}{n+1}$种形状不同的满二叉树。
基本上所有的卡特兰数问题经过一定的转换都可以还原成进出栈问题,其中都会存在一种匹配关系,如进出栈匹配,括号匹配等。一旦计数问题中存在这种关系,那我们就需要去考虑这是否是卡特兰数问题。此外,我们还可以记住序列前四项:1, 1, 2, 5
,这些将有利于我们联想到卡特兰数。
例如,以下问题的题解均为卡特兰数:
有2n个人排成一行进入剧场。 入场费5元。其中只有n个人有一张5元钞票,另外n人只有10元钞票,剧院无其他钞票,问有多少种方法使得只要有10元的人买票,售票处就有5元的钞票找零? $\LARGE \frac{C^{n}{2n}}{n+1}$种。
一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她从不穿越(但可以碰到)从家到办公室的对角线,那么有多少条可能的道路? $\LARGE \frac{C^{n}{2n}}{n+1}$种。
在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数? $\LARGE \frac{C^{n}{2n}}{n+1}$种。
矩阵连乘:p=$a_1$x$a_2$x…x$a_n$,依据乘法结合律,不改变其顺序,只用括号表示成对的乘积,试问有几种括号化的方案? $\LARGE \frac{C^{n}{2n}}{n+1}$种。
2.4 队列
一种操作受限的线性表,仅允许在表的一端(队尾)进行插入操作(入队),而在表的另一端(队首)进行删除操作(出队)。因此,队列也叫做先进先出表。
队列的顺序存储结构
1 | typedef struct{ |
队空的条件:q->front == q->rear
。
队满的条件:q->rear == MaxSize-1
。
进队:rear增1,然后将元素e插入到该位置。
1 | bool enQueue(SqQueue *&q, ElemType e){ |
出队:front增1,然后将该位置的元素赋给e。
1 | bool deQueue(SqQueue *&q, ElemType &e){ |
队列的元素个数:rear-front
。
进队时rear增1,出队时front增1,这样整个队列会在数组中慢慢向右移动,容易出现假溢出的情况。
环形队列
按照q->rear == MaxSize-1
的队满条件判断时,可能存在假溢出的情况,另一端仍然存在空位置。解决的办法是把data数组的前后端连接在一起,形成环形队列(循环队列)。用数组实现队列的话,循环队列一般是必需的。
环形队列的队空条件:q->front == q->rear
。
环形队列的队满条件:(q->rear+1) % MaxSize == q->front
。
环形队列的进队:rear增1,然后将元素e插入到该位置。
1 | bool enQueue(SqQueue *&q, ElemType e){ |
环形队列的出队:front增1,然后将该位置的元素赋给e。
1 | bool deQueue(SqQueue *&q, ElemType &e){ |
环形队列的元素个数:(rear-front+MaxSize) % MaxSize
。
队列的链式存储结构——链队
链队中的数据结点类型DataNode的声明如下:
1 | typedef struct qnode{ |
链队头结点类型LinkQuNode的声明如下:
1 | typedef struct{ |
队空的条件:q->front == NULL
或者q->rear == NULL
。
队满的条件:不考虑。
进队:新建结点存放元素e(由p指向它),将结点p插入作为尾结点。要注意原来队列为空的情况。
1 | bool enQueue(LinkQuNode *&q, ElemType e){ |
出队:取出队首结点的data值并将其删除。要注意原来的队列仅有一个数据结点的情况。
1 | bool deQueue(LinkQuNode *&q, ElemType &e){ |
3 树
3.1 树的基本概念和性质
基本概念
树是N (N>=0)个结点的有限集。当N=0时, 树为空树。N>0时,有且仅有一个结点作为树的 根节点。
树中一个结点的子结点个数称为该 结点的度 ,树中结点的最大度数称为 树的度。通常将度为m的树成为 m次树。
度不为0的结点称为 分支结点,度为0的结点称为 叶子结点。
结点的层次从树根开始定义,根结点为第1层,它的子结点为第2层,以此类推。结点的深度是从根结点开始自顶向下逐层累加的;结点的高度是从叶结点开始自底向上逐层累加的。树中结点的最大层数称为树的高度或深度。
有序树和无序树:将子结点视为有顺序的树称为有序树,反之则称为无序树。有序树中,一个结点其子结点按从左到右顺序出现是有关联的。
森林是m (m≥0)棵互不相交的树的集合。森林的概念与树的概念十分相近,因为只要把树的根结点删去就成了森林。反之,只要给n棵独立的树加上一个结点,并把这n棵树作为该结点的子树,则森林就变成了树。
性质
树具有如下最基本的性质:
- 树中的结点数等于所有结点的度数加1。
- 度为m的树中第i层上至多有$m^{i-1}$个结点(i≥1)。
- 高度为h的m叉树至多有$(m^h-1)/(m- 1)$个结点。(1、$m$、$m^2$、…、$m^{h-1}$的等比数列求和)
- 具有n个结点的m叉树的最小高度为$[log_{m}(n(m -1)+1)]$。 (根据$n=(m^h-1)/(m- 1)$计算得到)
树的存储结构
双亲存储结构
树的一种顺序存储结构,用一组连续空间存储树的所有结点,每个结点中设有一个伪指针指示其双亲结点的位置。固定根结点的双亲结点位置为-1。
1
2
3
4typedef struct{
ElemType data; // 存放结点的值
int parent; // 存放双亲结点位置
}PTree[MAxSize];特点:容易查找某个结点的双亲结点,但是在求某个结点的孩子结点时需要遍历整个树。
孩子链存储结构
每个结点的存储空间不仅包括结点值,还有指向其所有孩子结点的指针。需要按照树的度来设计结点的孩子结点指针的指针域个数。
1
2
3
4typedef struct node{
ElemType data; // 存放结点的值
struct node *sons[MaxSons]; // 指向孩子结点,MaxSons为最多的孩子结点个数,即该树的度
}PTree[MAxSize];特点:查找孩子结点方便,但是查找双亲结点费时,并且当树的度较大时存在较多的空指针域。
孩子兄弟链存储结构
每个结点设计了3个域,包括数据元素域、一个指向该结点的左边第一个孩子的指针域、一个指向该结点的下一个兄弟结点的指针域。这样每个结点就固定只有2个指针域,且这两个指针域是有序的(类似二叉树的存储结构)。
1
2
3
4
5typedef struct tnode{
ElemType data; // 存放结点的值
struct tnode *hp; // 指向兄弟结点
struct tnode *vp; // 指向孩子结点
}TSBNode;
3.2 二叉树
二叉树是另一种树形结构(是n (n≥0)个结点的有限集合),其特点是每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分,其次序不能任意颠倒。
二叉树是有序树,若将其左、右子树颠倒,就成为另一棵不同的二叉树。即使树中结点只有一棵子树,也要区分它是左子树还是右子树。
**注意:**二叉树与度为2的有序树的区别:度为2的树至少有3个结点,而二叉树可以为空;度为2的有序树的孩子结点的左右次序是相对于另一孩子结点而言的,如果某个结点只有一个孩子结点,这个孩子结点就无须区分其左右次序,而二叉树无论其孩子数是否为2,均需确定其左右次序。
下面介绍几种特殊的二叉树。
满二叉树
叶子结点都集中在二叉树的最下一层, 并且除叶子结点之外的每个结点度数均为2的二叉树称为满二叉树,即树中的每一层都含有最多的结点,如图13-1(a)所示。或者也可以说一棵高度为h且含有$2^h-1$ 个结点的树为满二叉树。
可以对满二叉树按层序编号:约定编号从根结点(根结点编号为1) 起,自上而下,自左向右。这样每个结点对应一一个编号, 对于编号为i的结点,如果有双亲,其双亲为⌊i/2⌋,如果有左孩子,则左孩子为2i;如果有右孩子,则右孩子为2i+1。
完全二叉树
设一个高度为h,有n个结点的二叉树,当且仅当其每一个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时,称为完全二叉树,如图13- 1(b)所示。这种树的特点如下:
① 若$i≤\lfloor n/2 \rfloor$,则结点i为分支结点,否则为叶子结点。(层次遍历,前一半的结点均为分支结点,后一半均为叶子结点)
② **叶子结点只可能在层次最大的两层上出现。最大层次中的叶子结点都依次排列在该层最左边的位置上**。
③ 如果有度为1的结点,只可能有一个,且该结点只有左孩子而无右孩子。
④ 按层序编号后,一旦出现某结点(其编号为i)为叶子结点或只有左孩子,则编号大于i的结点均为叶子结点。
⑤ 若n为奇数,则每个分支结点都有左孩子和右孩子;若n为偶数,则编号最大的分支结点(编号为n/2)只有左子女,没有右子女,其余分支结点左、右子女都有。
注意:性质3中表明完全二叉树中,度为1的结点数 要么为0,要么为1。当总结点数为偶数时,度为1的结点数为1;当总结点数为奇数时,度为1的结点数为0。叶子结点数 为:总结点数/2。
二叉树的性质
二叉树的性质
- 非空二叉树上叶子结点(度为0)数等于度为2的结点数加1,即$\large N_0=N_2+1$。
证明:设度为0、1和2的结点个数分别为$N_0$、$N_1$和$N_2$,结点总数$N$=$N_0$+$N_1$+$N_2$。再看二叉树中的分支数,除根结点外,其余结点都有一个分支进入,设B为分支总数,则$N=B+1$。由于这些分支是由度为1或2的结点射出的,所以又有$B$ =$N_1$+$2N_2$。于是得$\large N_0=N_2+1$.
非空二叉树上第K层上至多有$2^{k-1}$个结点(K≥1)。
**高度为H的二叉树至多有$2^H-1$个结点(H≥1)**。
对完全二叉树按从上到下、从左到右的顺序依次编号1, 2, …, N,则有以下关系:
a) 当i>1时,结点i的双亲结点编号为⌊i/2⌋,即当i为偶数时,其双亲结点的编号为i/2,它是双亲结点的左孩子;当i为奇数时,其双亲结点的编号为(i -1)/2,它是双亲结点的右孩子。
b) 当2i≤N时,结点i的左孩子编号为2i,否则无左孩子。
c) 当2i+1≤N时,结点i的右孩子编号为2i+1, 否则无右孩子。
d) 结点i所在层次(深度)为$⌊log_2i⌋+1$。
- 具有N个(N>0)结点的 完全二叉树的高度 为$\lfloor log_2N \rfloor +1$ 或者 $\lceil log_2(N+1) \rceil \space$。
例题:
二叉树的存储结构
二叉树的顺序存储结构
顺序存储就是用一组地址连续的存储单元依次自上而下、自左而右存储完全二叉树的结点元素,即将完全二叉树编号为i的结点元素存储在某个数组下标为i-1的分量中。对于一般二叉树,则应将其每个结点与完全二叉树上的结点相对照,存储在一维数组的相应分量中。
1
typedef ElemType SqBinTree[MaxSize]; # 为方便运算,一般下标为0的位置空着,空结点用"#"表示
然而,在最坏的情况下,一个高度为H且只有H个结点的单支树却需要占据接近$2^H-1$个存储单元。因此,顺序存储结构一般仅适用在完全二叉树中。
二叉树的链式存储结构
每个结点由三个域组成,包括数据域、指向该结点左孩子结点的指针域、指向该结点右孩子结点的指针域。
1
2
3
4
5typedef struct node{
ElemType data;
struct node *lchild;
struct node *rchild;
}BTNode;容易验证,在有n个结点的二叉树中,每个结点有2个指针域,因此一共存在2n个链域。其中,除根结点外,其余结点均有指针指向,因此,有n-1个有效链域,n+1个空链域。
==二叉树的遍历==
很多问题的求解是借助二叉树的遍历完成的。重点为二叉树遍历的非递归算法。
- ==先序遍历==
1 | /*-------------递归-------------*/ |
1 | /*-------------非递归(使用顺序栈实现)-------------*/ |
- ==中序遍历==
1 | /*-------------递归-------------*/ |
1 | /*-------------非递归(使用顺序栈实现)-------------*/ |
- ==后序遍历==
1 | /*-------------递归-------------*/ |
1 | /*-------------非递归(使用顺序栈实现)-------------*/ |
- 层序遍历(借助队列实现)
1 | /*-------------使用队列实现-------------*/ |
3.3 二叉树的应用
- 判断两颗二叉树是否相同。
运用递归的方法,按照先序遍历对比即可。
1 | typedef struct node { |
进一步的,比较两棵可以旋转的二叉树是否相等。二叉树的左右子结点可以旋转是指可以把二叉树的左结点旋转成为右结点,右结点旋转成为左结点。(2012. 百度)
若左右子结点可以旋转的话,需要将递归的return代码改为如下内容:
1 | return (isEqual (node1->left, node2->left) && isEqual (node1->right, node2->right)) || |
- 求二叉树的深度
从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。(相当于做后序遍历)
1 | typedef struct node { |
- 求二叉树中结点的最大距离
如果我们把二叉树视为一个图,父子结点之间的连线视为双向的,我们姑且定义“距离”为两结点之间边的个数。写一个程序求一棵二叉树中相距最远的两个结点之间的距离。
分析:计算-一个二叉树的最大距离有两个情况:
情况A:路径经过左子树的最深结点,通过根结点,再到右子树的最深结点。
情况B:路径不穿过根结点,而是左子树或右子树的最大距离路径,取其大者。
只需要计算这两个情况的路径距离,并取其大者,就是该二叉树的最大距离。
1 | typedef struct node { |
一棵二叉树每个结点包含一个整数,请设计一个算法输出所有满足条件的路径:此路径上的所有结点之和等于给定值。注意此类路径不要求必须从根结点开始,满足条件的路径不唯一。
该题可利用先序遍历:
1 | // 输出结果 |
- 由遍历序列构造二叉树(重建二叉树)
在先序遍历序列中,第一个结点一定是二叉树的根结点,而在中序遍历中,根结点必然将中序序列分割成两个子序列,前一个子序列就是根结点的左子树的中序序列,后一个子序列是根结点的右子树的中序序列。根据这两个子序列,可以在先序序列中找到对应的左子序列和右子序列。在先序序列中,左子序列的第一个结点是左子树的根结点,右子序列的第一个结点是右子树的根结点。如此递归地进行下去,便能唯一地确定这棵二叉树。即先序序列和中序序列可以唯一地确定一棵二叉树。
同理,由二叉树的后序序列和中序序列也可以唯一地确定一棵二叉树,因为后序序列的最后一个结点就如同先序序列的第一个结点, 可以将中序序列分割成两个子序列,然后采用类似的方法递归地进行划分,就可以得到一棵二叉树。
由二叉树的层序序列和中序序列也可以唯一地确定一棵二叉树。需要注意的是,如果只知道二叉树的先序序列和后序序列,是无法唯一确定一棵二叉树的。
例1:求先序序列(ABCDEFGHI)和中序序列(BCAEDGHFI)所确定的二叉树。
由先序序列确定根结点,再由中序序列确定该根结点的左子树、右子树。再依次递归下去。
例2:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1, 2, 4, 7, 3, 5, 6, 8}和中序遍历序列{4, 7, 2, 1, 5, 3, 8, 6},则重建二叉树并输出它的后序遍历序列。(剑指Offer例题)
1 | typedef struct node { |
3.4 树的应用
二叉排序树 BST
二叉排序树,也称为二叉查找树,二叉搜索树,或BST。二叉排序树或者是一棵空树,或者是一棵具有下列特性的非空二 叉树:
若左子树非空,则左子树上所有结点关键字值均小于根结点的关键字值。
若右子树非空,则右子树上所有结点关键字值均大于根结点的关键字值。
左、右子树本身也分别是一棵二叉排序树。
由此定义可知,二叉排序树是一个递归的数据结构。
根据二叉排序树的定义,有**左子树结点值 < 根结点值 < 右子树结点值**。所以对二叉排序树进行中序遍历,可以得到一个递增的有序序列。
二叉排序树的查找操作的时间复杂度是$O(log_2N)$,比较次数与树的深度有关。
例如,图13-5的二叉排序树的中序遍历序列为123468。
判断一个二叉树是否为二叉排序树
使用中序遍历二叉树,判断是否为递增序列,复杂度O(n)。
1 | int prev1 = INT_ MIN; //定义为最小的整数 |
平衡二叉树 AVL
为了避免树的高度增长过快,降低二叉排序树的性能,我们规定在插入和删除二叉树结点时,要保证任意结点的左、右子树高度差的绝对值不超过1,并将这样的二叉排序树称为平衡二叉树,简称平衡树(AVL树)。定义结点左子树与右子树的高度差为该结点的平衡因子,则平衡二叉树结点的平衡因子的值只可能是-1、0或1。
因此,平衡二叉树可定义为它或者是一棵空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且 左子树和右子树的高度差的绝对值不超过1。
平衡二叉树的操作效率(查询,插入,删除)效率较高,时间复杂度是$O(log_2N)$,即树的深度。
图13-6(b)所示是不平衡的二叉树。结点中的值为该结点的平衡因子。
判断一棵二叉树是不是平衡二叉树。
解法一:递归的思路,遍历树的每个结点,求出其左右子树的深度,计算深度差。
1 | bool IsBalanced (BTNode* root) { |
解法二:解法一虽然简洁但是每个结点会被遍历多次,效率较低。如果我们用后序遍历的方式遍历二叉树的每一个结点, 在遍历到一个结点之前我们已经遍历了它的左右子树。只要在遍历每个结点的时候记录它的高度,我们就可以一边遍历一边判断每个结点是不是平衡的。下面是这种思路的参考代码:
1 | bool IsBalanced (BTNode* root, int* Depth) { |
解法三:除此之外,下面的方法也是可行的,且形式更加简洁。求出根结点的最大深度与最小深度,则最大深度与最小深度之差dis就是树中任一子树深度差最大值,所以只要dis小于等于1,此树就是平衡二叉树,代码如下:
1 | // 求树的最大深度 |
B树和B+树
参考:https://www.cnblogs.com/xiaofengshan/p/15443140.html
B树和B+树都是多路查找树,为了解决数据量大,树的高度大增(二叉树)而产生的一种数据结构。
B树
B树又称为多路平衡查找树,是二叉排序树的扩展,满足平衡的性质,所有结点的平衡因子均等于0,结点又拥有多个子树,对于组织和维护外存文件系统非常有效(数据库)。
把树中结点所拥有的最大的子树数目称为 B树的阶。通常记为m。一颗m阶B树或为空树,或为满足如下特性的m叉树:
- 树中每个结点至多有m个孩子结点。(同时至多含有m-1个关键字,每两颗子树指针夹着一个关键字);
- 若根结点不是叶子结点,则至少有两个孩子结点。(至少一个关键字);
- 除根结点外的所有非叶子结点至少有$\lceil m/2 \rceil$棵子树。(即至少含有$\lceil m/2 \rceil -1$个关键字);
- 所有的外部结点出现在同一个层次上,不带信息,但是计算B树的高度时需要考虑外部结点。(就像是折半查找判断树中查找失败的结点)。
- **每一个结点中的关键字按递增的顺序排列**,关键字两边为指向孩子结点的指针。
B树中的非叶子结点对应数据库查找时的关键字,叶子结点对应要查找的详细记录,而外部结点对应查找失败,指向它的指针为NULL,不含有任何信息。一颗含有n个关键字的B树有n+1个外部结点。
B树的插入
向B树插入结点时,只能向叶子结点插入。
当叶子结点的关键字个数小于m-1时,直接在该结点增加关键字即可,注意保持递增。
当叶子结点的关键字个数等于m-1时,无法继续增加关键字。这时采用 分裂法,比如一棵3阶B树,结点的关键字个数最多为2。有一关键字为50的结点需要插入,定位到在叶子节点{20、30}中插入时,发现关键字已满。
此时对该叶子结点进行分裂,选取{20、30、50}的中位数30作为双亲结点提升到上一层中,其余关键字作为孩子结点留在本层。若关键字30提升到双亲结点后,造成双亲结点的关键字数量超过m-1,那么双亲结点也进行同样的分裂。
B树的删除
删除关键字时,同样也要考虑结点内原本关键词的数量,保证结点始终拥有至少$\lceil m/2 \rceil$-1个关键字:
当结点内关键字数量大于$\lceil m/2 \rceil$-1,这时删除这个关键字不会破坏B树的定义要求,所以直接删除即可。
比如删除关键字9;
当结点内关键字数量等于$\lceil m/2 \rceil$-1,并且其左右兄弟结点中存在关键字数量大于$\lceil m/2 \rceil$-1的结点,则删除后 去兄弟结点中借关键字;
比如删除关键字2,而每个结点应至少有1个关键字,所以结构调整子树结构为根结点为5,7为左孩子,9为右孩子。
当结点内关键字数量等于$\lceil m/2 \rceil$-1,并且其左右兄弟结点中不存在关键字数量大于$\lceil m/2 \rceil$-1的结点,则需要 进行结点合并;
比如删除关键字16后,无法向兄弟结点借关键字,所以调整子树结构为如下:
如果删除的关键字不在终端结点上(最底层非叶子结点):需要先转换成在终端结点上(找相邻关键字替换),再按照在终端结点上的情况来分别考虑对应的方法。
B+树
B+树是B树的一些变形,是常用于数据库和操作系统的文件系统中的一种用于查找的数据结构,包括oracle、Mysql等主流数据库。
B+树的性质:
- m阶B+树的每个分支结点至多有m个子树,不用来保存数据而是保存数据的索引。
- 除根结点外的所有非叶子结点至少有$\lceil m/2 \rceil$棵子树。根结点要么没有子树,要么至少有2个子树。
- 有n棵子树的结点恰好有n个关键字。
- **所有的叶子结点中包含了全部关键字的信息**,及指向含这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。非叶子结点的元素在叶子结点上有冗余,非叶子结点的数据只是作为索引来帮助查找叶子结点元素。
- 所有的非终端结点可以看成是索引部分,结点中仅含其子树中的大(或小)关键字。
- B+树中,数据对象的插入和删除仅在叶节点上进行。
- B+树**有2个头指针,一个是树的根节点root(用于随机查找),一个是小关键码的叶节点指针sqt(用于顺序查找/范围查找)。且叶子结点之间有指针**。
Mysql索引使用的是B+树,因为索引(非叶子结点)是用来加快查询的。同时而B+树通过对数据进行排序,所以是可以提高查询速度的,并且一个结点中可以存储多个元素,从而可以使得B+树的高度不会太高。
在Mysql中一个Innodb页就是一个B+树结点,一个Innodb页默认16kb(存储本结点关键字),所以一般情况下一棵两层的B+树可以存2000万行左右的数据(B+树一般不会超过3层),然后通过利用B+树叶子结点存储了所有数据并且进行了排序,并且叶子结点之间有指针,可以很好的支持全表扫描,范围查找等SQL语句。
B树和B+树的区别:
① 在B+树中,具有n个关键字的结点只含有n棵子树,即每个关键字对应一颗子树;而在B树中,具有n个关键字的结点含有(n+1)棵子树。
② 在B+树中,每个结点(非根内部结点)关键字个数n的范围是[m/2]<=n<=m(根结点1<=n<=m),在B树中,每个结点(非根内部结点)关键字个数n的范围是[m/2]-1<=n<=m-1(根结点:1<=n<=m-1)。
③ 在B+树中,叶结点包含信息,所有非叶结点仅起到索引的作用,非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针,不含有该关键字对应的存储地址。
④ 在B+树中,叶结点包含了全部关键字,即在非叶结点中出现的关键字也会出现在叶结点中;而在B树中,叶结点包含的关键字和其他结点包含的关键字是不重复的。
⑤ 在B+树中,有一个指针指向关键字最小的叶子结点,所有叶子结点连接成一个单链表。
红黑树
参考:https://blog.csdn.net/cy973071263/article/details/122543826
背景
若插入和删除操作总在平衡二叉树(AVL)的某一子树进行,那么大多数的结点都会在根结点的右侧或左侧,此时,二叉搜索树就接近于一个链表,它的操作效率就降低了。为了不断维持平衡二叉树的平衡状态,就需要对AVL进行旋转处理。红黑树的出现是为了解决维持平衡二叉树AVL而导致的成本高的问题。
比如下面进行平衡二叉树的插入时,就需要进行旋转,重新维持平衡。
概念
自平衡二叉查找树,以前也叫平衡二叉B树。红黑树具有良好的效率,它可在 O(logN) 时间内完成查找、增加、删除等操作。
红黑树为具备了某些特性的二叉搜索树,能解决非平衡树问题,是一种**接近平衡**的二叉树(说它是接近平衡因为它并没有像AVL树的平衡因子的概念,它只是靠着满足红黑节点的5条性质来维持一种接近平衡的结构,进而提升整体的性能,并没有严格的卡定某个平衡因子来维持绝对平衡)。红黑树同时具有平衡和排序的特点,既接近平衡二叉树,又是二叉搜索树BST。
性质
首先,红黑树是一个二叉搜索树,它在每个结点增加了一个存储位记录节点的颜色,可以是RED,也可以是BLACK;通过任意一条从根到叶子简单路径上颜色的约束,红黑树保证最长路径不超过最短路径的二倍,因而近似平衡(最短路径就是全黑节点,最长路径就是一个红结点一个黑结点,当从根结点到叶子结点的所有路径上黑色结点数目相同时,最长路径刚好是最短路径的两倍)。它同时满足以下特性:
- 结点是红色或黑色
- 根是黑色
- 叶子结点(外部结点,空结点)都是黑色
- 红色结点的子结点都是黑色,红色结点的父结点都是黑色,从根结点到叶子结点的所有路径上不能有 2 个连续的红色结点
- 从任一结点到叶子结点(空结点)的所有路径都包含相同数目的黑色结点
哈夫曼树及哈夫曼编码
概念
结点的权值:给树的结点赋予的有某种意义的数值;
结点的带权路径长度WPL:从根结点到该结点之间的路径长度与该结点的权值的乘积;
树的带权路径长度WPL:树中所有叶子结点的带权路径长度之和,记为$WPL=\sum_{i=1}^n{w_i*l_i}$。式中,$w_i$是第i个叶结点所带的权值,$l_i$是该叶结点到根结点的路径长度。
哈夫曼树:在$n_0$个带权叶子节点构成的所有二叉树中,带权路径长度WPL最小的二叉树称为哈夫曼树。(原则:权值越大的叶子结点越靠近根结点,权值越小的叶子结点越远离根结点)
哈夫曼树的构造
给定n个权值分别为$w_1$,$w_2$,…,$w_n$的结点。构造哈夫曼树的算法描述如下:
- 将这n个结点分别作为n棵仅含一个结点的二叉树,构成森林F。
- 从F中选取两棵根结点权值最小的树作为左、右子树来构造一个新二叉树,并且将新二叉树根结点的权值置为左、右子树上根的权值之和。
- 从F中,用新得到的树代替刚才选出的两棵树。
- 重复步骤2)和3),直至F中只剩下一棵树为止。
哈夫曼编码
固定长度编码:每个字符使用相同长度的二进制位来表示;
可变长度编码:允许对每个字符使用不同长度的二进制位来表示;
可变长度编码比固定长度编码好得多,其特点是对频率高的字符赋予短编码,而对频率较低的字符则赋予较长一些的编码,从而可以使平均编码长度减短,起到压缩数据的效果。哈夫曼编码是一种被广泛应用而且非常有效的数据压缩编码,它是可变长度编码。
前缀编码:没有一个编码是另一个编码的前缀。前缀编码的解码操作相对简单,无需考虑重复前缀。哈夫曼编码属于前缀编码。
构造哈夫曼编码首先要构造一棵哈夫曼树。 首先,将每个出现的字符当作一个独立的结点, 其权值为它出现的频度(或次数),然后构造出对应的哈夫曼树。显然,所有字符结点都出现在叶结点中。我们可以将字符的编码解释为从根至该字符的路径上边标记的序列,其中边标记为0表示“转向左孩子”,标记为1表示“转向右孩子”。图13-7所示为-一个由哈夫曼树构造哈夫曼编码的示例,矩形方块
表示字符及其出现的次数。这棵哈夫曼树的WPL为:WPL=1*45+3*(13+12+16)+4*(5+9)=224
此处的WPL可以视为最终编码得到二进制编码的长度,共224位。如果采用3位固定长度编码,则得到的二进制编码长度为300位。可见哈夫曼编码共压缩了约25%的数据。利用哈夫曼树可以设计出总长度最短的二进制前缀编码。
3.5 并查集
并查集是一种树形的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。常常在使用中以森林来表示,进行快速规整。
并查集保持一组不相交的动态集合 S={S1, S2, ….., Sk }。**每个集合通过一个代表来识别**, 代表即集合中的某个成员。在某些应用中,哪一个成员被选作代表是无所谓的。在一些应用中,如何选择代表可能存在着预先说明的规则,例如选择集合中的最小元素。
集合中的每一个元素是由一个对象表示的,设x表示一个对象,则并查集应支持以下操作:
make_set(x):建立一个新的集合,其唯一成员就是 x (x此时即是代表)。因为各集合是不相交的,故要求x没有在其他集合中出现过。
union_set(x, y):如果x、y分属不同集合,则将包含x和y的动态集合合并为一个新的集合。
find_set(x):返回一个指针,指向包含x所在的集合的代表。
单链表实现
要实现并查集数据结构,一种简单的方法是每一个集合都用一个链表来表示。每个链表的第一个对象作为它所在集合的代表。链表中的每一个对象都包含一个集合成员、 一个指向包含下一个集合成员的对象的指针,以及指向代表的指针。每个链表都含head指针指向链表的代表,以及tail指针指向链表中最后的对象。
并查集森林
并查集的另一种更快的实现是用有根树来表示集合:每棵树表示一个集合, 树中的结点对应一个成员。在下图所示的并查集森林中,每个成员仅指向其父结点,父结点为其代表。每棵树的根为整个集合的代表,并且是它自己的父结点。
图13-8中左侧是两棵表示两个集合的树,左边的树表示集合{b, c, e, h}, 其中c为代表;右边的树表示集合{d, f, g}, 其中f为代表。右侧为union_set(e, g)的结果。
make_set创建一棵仅包含一个结点的树。
在执行find_set操作时,要沿着父结点指针一直找下去,直至找到树根为止。
union_set操作使得一棵树的根指向另一棵树的根。
两种并查集森林的改进策略
第一种是按秩合并,其思想是union_set操作使包含较少结点的树的根指向包含较多结点的树的根。
这种方法并不显式记录以每个结点为根的子树的大小,而是采用了一种能够简化分析的方法:对每个结点,用秩表示结点高度的一个上界。在按秩合并中,具有较小秩的根在union_set操作中要指向具有较大秩的根。
第二种是路径压缩,这种方法简单有效。它使一棵树的每个结点都直接指向根结点,如图13-9所示。
假如已知有n个人和m对好友关系(存于数字r)。如果两个人是直接或间接的好友(好友的好友的好友..),则认为他们属于同一个朋友圈,请写程序求出这n个人里一共有多少个朋友圈。
假如:n=5, m=3, r={ {1,2},{2,3},{4,5} }, 表示有5个人,1 和2是好友,2和3是好友,和5是好友,则1、2、3属于一个朋友圈,4、5属于另一个朋友圈,结果为2个朋友圈。
最后请分析所写代码的时间、空间复杂度。评分会参考代码的正确性和效率。
int friends(int n, int m, int* r[]);
1 | int set [10001]; // 存储每个元素的代表 |
参考:https://blog.csdn.net/qq_40378034/article/details/103224445
4 图
4.1 图的基本概念
图G由顶点集V和边集E组成,记为G=(V, E),其中V(G)表示图G中顶点的有限非空集;E(G)表示图G中顶点之间的关系(边)集合。若 V = {$v_1$, $v_2$, …, $v_n$},用|V|表示图G中顶点的个数,也称为图G的阶,E={(u, v)|u∈V, v∈ V},用E表示图G中边的条数。
注意:线性表可以是空表,树可以是空树,但图不可以是空图。就是说,图中不能一个顶点也没有,图的顶点集V一定非空,但边集E可以为空,此时图中只有顶点而没有边。
有向图:若E是有向边(也称为弧)的有限集合时,则图G为有向图。
无向图:若E是无向边(简称边)的有限集合时,则图G为无向图。
在无向图中,如果任意两个顶点之间都存在边,则称该图为无向完全图。含有n个顶点的无向完全图有n(n-1)/2条边。
在有向图中,如果任意两个顶点之间都存在方向相反的两条弧,则称该图为有向完全图。含有n个顶点的有向完全图有**n(n-1)**条有向边。
设有两个图G=(V, E)和G’=(V’, E’),若V是V的子集,且E是E的子集,则称G是G的子图。若有满足V(G)=V(G’)的子图G,则为G的生成子图。
在无向图中,若从顶点v到顶点w有路径存在,则称v和w是连通的。若图G中任意两个顶点都是连通的,则称图G为连通图,否则称为非连通图。无向图中的极大连通子图称为连通分量。如果一个图有n个顶点,并且有小于n-1条边,则此图必是非连通图。如图14-1(a)所示,图G有3个连通分量。
在有向图中,若从顶点v到顶点w和从顶点w到顶点v之间都有路径,则称这两个顶点是强连通的。若图中任何一对顶点都是强连通的,则称此图为强连通图。有向图中的极大强连通子图称为有向图的强连通分量,图G2的强连通分量如图14-2 所示。
图中每个顶点的度定义为以该顶点为一个端点的边的数目。对于无向图,顶点v的度是指依附于该项点的边的条数,记为TD(1)。在无向图中,**无向图的全部顶点的度之和等于边数的两倍**,这是因为每条边和两个顶点相关联。
对于有向图,顶点v的度分为入度和出度,入度是以顶点v为终点的有向边的数目;而出度是以顶点v为起点的有向边的数目。 顶点v的度等于其入度和出度之和,在有向图中,**有向图的全部顶点的入度之和与出度之和相等并且等于边数**。这是因为每条有向边都有一个起点和终点。
4.2 图的存储及基本操作
邻接矩阵法
所谓邻接矩阵存储,就是用一个二维数组存储图中边的信息( 即各顶点之间的邻接关系),存储顶点之间邻接关系的二维数组称为邻接矩阵。
结点数为n的图G=(V, E)的邻接矩阵A是n*n的。将G的顶点编号为$v_1$, $v_2$, …, $v_n$。若$(v_i, v_j)∈E$,则$A[i][j]=1$,否则,$A[i][j]=0$。
$A[i][j]=\begin{cases} 1,\quad若(v_i, v_j)或<v_i,v_j>是E(G)中的边\ 0,\quad若(v_i, v_j)或<v_i,v_j>不是E(G)中的边 \end{cases}$
对于带权图而言,若顶点$v_i$和$v_j$之间有边相连,则邻接矩阵中对应项存放着该边对应的权值,若顶点$v_i$和$v_j$不相连,则用∞来代表这两个顶点之间不存在边。
$A[i][j]=\begin{cases} w_{ij},\quad若(v_i, v_j)或<v_i,v_j>是E(G)中的边\ 0或\infty,\quad若(v_i, v_j)或<v_i,v_j>不是E(G)中的边 \end{cases}$
1 |
|
图的邻接矩阵存储表示法具有以下特点:
无向图的邻接矩阵一定是一个对称矩阵(并且唯一)。
对于无向图,邻接矩阵的第i行(或第i列)非零元素(或非∞元素)的个数正好是第i个顶点的度。
对于有向图,邻接矩阵的第i行(或第i列)非零元素(或非∞元素)的个数正好是第i个顶点的出度(或入度)。
用邻接矩阵方法存储图,很容易确定图中任意两个顶点之间是否有边相连。但是,要确定图中有多少条边,则必须按行、按列对每个元素进行检测,所花费的时间代价很大。
稠密图适合使用邻接矩阵的存储表示。
邻接表法
所谓邻接表就是对图G中的每个顶点v建立一个单链表, 第i个单链表中的结点表示关联于顶点$v_i$的边(对于有向图则是以顶点$v_i$的起点的边),这个单链表就称为顶点$v_i$的的边表(对于有向图则称为出边表)。边表的头指针和顶点的数据信息采用顺序存储(称为顶点表),所以在邻接表中存在两种结点:顶点表结点和边表结点,如图144所示。顶点表中,data存储顶点$v_i$的名称或其他信息,firstarc指向顶点$v_i$的单链表中的首结点;边表的adjvex表示与顶点$v_i$邻接的顶点编号,nextarc指向下一个边结点,另外还可以有一个weight数值域,存放边的权值等信息。
1 | // 顶点表(头结点) |
图的邻接表存储方法具有以下特点:
1 )如果G为无向图,则所需的存储空间为O (V+2|E|);如果G为有向图,则所需的存储空间为O (V+|E|)。前者的倍数2是由于无向图中,每条边在邻接表中出现了两次。
2) 对于稀疏图,采用邻接表表示将极大地节省存储空间。
3) 在邻接表中,给定一顶点,能很容易地找出它的所有邻边,因为只需要读取它的邻接表就可以。在邻接矩阵中,相同的操作则需要扫描一行, 花费的时间为O(n)。但是,如果要确定给定的两个顶点间是否存在边,则在邻接矩阵里可以立刻查到,在邻接表中则需要在相应结点对应的边表中查找另一结点,效率较低。
4.3 图的遍历
==深度优先搜索DFS==
深度优先搜索(DFS)类似于树的先序遍历。它的基本思想如下:首先访问图中某一起始顶点v,然后由v出发,访问与v邻接且未被访问的任一顶点$w_1$,再访问与$w_1$邻接且未被访问的任一顶点$w_2$, ……重复上述过程。当不能再继续向下访问时,依次退回到最近被访问的顶点,若它还有邻接顶点未被访问过,则从该点开始继续上述搜索过程,直到图中所有顶点均被访问过为止。
1 | /*以邻接表为存储结构的深度优先遍历算法*/ |
==广度优先搜索 BFS==
广度优先搜索(BFS)类似于二叉树的层序遍历算法,它的基本思想是:首先访问起始项点v,接着由v出发,依次访问v的各个未访问过的邻接顶点$w_1$, $w_2$, …, $w_i$,然后再依次访问$w_1$, $w_2$, …, $w_i$的所有未被访问过的邻接顶点;再从这些访问过的顶点出发,再访问它们所有未被访问过的邻接顶点…..以此类推,直到图中所有顶点都被访问过为止。类似的思想还将应用于Dijkstra单源最短路径算法和Prim最小生成树算法。
广度优先搜索是一种分层的查找过程,每向前走一步可能访问一批顶点,不像深度优先搜索那样有往回退的情况,因此它不是一个递归的算法。为了实现逐层的访问,算法必须借助一个辅助队列,以记忆正在访问的顶点的下一层顶点。
1 | void BFS(AdjGraph *G, int v){ |
4.4 图遍历算法的应用
- 判断图的连通性
图的遍历算法可以用来判断图的连通性。对于无向图来说,如果无向图是连通的,则从任一结点出发,仅需一次遍历就能够访问图中所有顶点;如果无向图是非连通的,则从某一个顶点出发,一次遍历只能访问到该顶点所在连通分量的所有顶点,而对于图中其他连通分量的顶点,则无法通过这次遍历访问。对于有向图来说,若从初始点到图中的每个顶点都有路径,则能够访问到图中的所有顶点,否则不能访问到所有顶点。
- 遍历解答树
在问题求解时,对所有可能的问题解构成一棵树,而最优解或者符合要求的解就是该树的一条路径或者一个结点。这种树称为解答树。
例1:比如1,2…n的排列一共有n!个,生成它们至少需要n!的时间。图14-6是生成123的全排列的解答树。通过深度优先遍历DFS就可以输出1,2…n的全排列
1 | const int N=13; //n 的最大值 |
按照相同的原理,输出数组的全排列:
1 | void perm(int list[], int k, int m) { // k表示遍历解答树的深度,m表示数组下标最大值 |
例2:有1分,2分,5分,10分四种硬币,每种硬币数量无限,给定Target分钱,求有多少种组合可以组合成Target分钱?
依然是解答树的深度优先遍历DFS问题(回溯法):
参考:https://blog.csdn.net/huangxy10/article/details/8026464
1 | int count=0; //统计有多少种组合 |
01背包问题,使用深度优先遍历的思想解决
0-1背包问题除了用动态规划解决以外,是不是也可以利用深度优先遍历解决呢?下图为有ABCD若干件物品的背包问题解答树。
我们利用深度优先遍历遍历至每个叶子结点,求出小于背包容量的最大值即可。代码如下:
1 | const int N=100; //物品最大件数 |
4.5 图的基本应用
最小生成树
连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为n,则它的生成树含有n-1条边。对于生成树而言,若砍去它的一条边,则会变成非连通图,若加上一条边则会形成一个回路。在非连通图中,连通分量的生成树构成了非连通图的生成森林。
注意区分极大连通子图和极小连通子图:极大连通子图是无向图的连通分量,极大即要求该连通子图包含其所有的边;极小连通子图是连通无向图的生成树,极小既要保持图连通,又要使得边数最少,只有生成树满足条件,砍去生成树的任一条边, 图将不再连通。
构造最小生成树有多种算法,但大多数算法都利用了最小生成树的下列性质:
假设G=(V,B)是一个带权连通无向图,U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值的边,其中u∈U,v∈V-U,则必存在一棵包含边(u, v)的最小生成树。
基于该性质的最小生成树算法主要有:Prim 算法和Kruskal算法,它们都基于贪心算法的策略。
**==prim算法==**(运用BFS)
Prim算法的步骤如下:
初始化:向空树$T=(V_T,E_T)$中添加图$G=(V,E)$的任一顶点$u_o$,使$V_T={u_0}$,$E_T=\emptyset$。
循环(重复下列操作至$V_T=V$):从图G中选择满足${(u,v)|u \in V_T, v \in V-V_T}$且具有最小权值的边(u,v),并置$V_T = V_T \bigcup {v}$,。$E_T = E_T \bigcup {(u,v)}$。
Prim算法的时间复杂度为$O(|V|^2)$,不依赖于|E|,因此它适用于求解边稠密的图的最小生成树。虽然采用其他方法可以改进Prim算法的时间复杂度,但增加了实现的复杂性。
==kruskal算法==
与Prim算法从顶点开始扩展最小生成树不同,Kruskal 算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。假设N=(V,E)是连通网,对应的最小生成树$T=(V_T,E_T)$,KVruskal 算法的步骤如下:
初始化:使$V_T=V$,$E_T=\emptyset$。 即每个顶点构成一棵独立的树, T此时是一个仅含|V|个顶点的森林;
循环(重复下列操作至T是一棵树):按G的边的权值递增顺序依次从$E = E_T$中选择一条边,如果这条边加入T后不构成回路,则将其加入E,否则舍弃,直到E中含有n-1条边。
通常在Kruskal算法中,采用堆来存放边的集合,则每次选择最小权值的边只需O(log|E|)的时间。又生成树T中所有边可以视为一个等价类,每次添加新的边的过程类似于求解等价类的过程,由此可以采用并查集的数据结构来描述T,从而构造T的时间复杂度为O(|E|log|E|),因此,Kruskal 算法适合于边稀疏而顶点较多的图。
最短路径
求解最短路径的算法通常都依赖于一种性质,也就是两点之间的最短路径也包含了路径上其他顶点间的最短路径。这种最优子结构性质是动态规划和贪心算法是否适用的一个标记。
带权有向图G的最短路径问题,一般可分为两类:一是单源最短路径,即求图中某一顶点到其他各顶点的最短路径,可通过经典的Djkstra 算法求解,此算法也是基于贪心算法的策略;二是求每一对顶点间的最短路径,可通过Floyd-Warshall算法来求解,此算法是基于动态规划的思想。
==Dijkstra算法==(BFS+贪心)求单源最短的径问题
参考:https://www.bilibili.com/video/BV1zz4y1m7Nq
求带权有向图中某个源点到其余各顶点的最短路径,最常用的是Dijkstra 算法。该算法设置一个集合s,记录已求得的最短路径的顶点,初始时把源点v的放入S中。此外,在构造过程中还设置了两个辅助数组:
**dist[]**:记录了从源点$v_0$到其他各顶点当前的最短路径长度,dist[i]初值为arcs[0][i]。
**path[]**:path[i]表示从源点到顶点i之间的最短路径的前驱结点,在算法结束时,可根据其值追溯得到源点$v_0$到顶点V的最短路径。
假设从顶点0出发,即$v_0=0$,集合S最初只包含顶点0,邻接矩阵arcs表示带权有向图,arcs[i][j]表示有向边<i, j>的权值,若不存在有向边<i, j>,则arcs[i][j]为∞。
Djkstra 算法的步骤如下(不考虑对path[]的操作):
初始化:集合S初始为{0},dist[]的初始值dist[i]= arcs[0][i],i=1, 2, …, n-1。
从未入选S的顶点集合V-S中选出距离出发点$v_0$最近(即dist最小)的结点$v_j$,也就是满足$dist[j]=Min{dist[i]|v_i \in V-S}$,$v_j$就是当前求得的一条从$v_0$出发的最短路径的终点,将其收录进S,即令$S=S \bigcup {j}$。
修改从$v_0$出发到集合V-S上的$v_k$可达的最短路径长度dist[k],$v_k$为$v_j$的邻近顶点:如果$v_0$经过结点$v_j$到达$v_k$的距离小于已知的到达$v_k$的距离,即dist[j]+arcs[j][k] < dist[k],则更新disk[k],令dist[k]=dist[j]+arcs[j][k]。
重复2) ~3)操作共n-1次,直到所有的顶点都包含在S中。
算法计算过程举例
例如,表14-1所示为应用Djkstra算法对图14-11中的图从顶点1出发,求其到其余顶点的最短路径。
第一趟:与结点1直接相连的有结点2、5,距离分别为10、5。而其余结点不能直达,所以距离为无限。这样每个结点都有一个初始化的距离。更新结点2、5的距离,并将距离最短的结点5加入S;
第二趟:上一趟在S中加入了结点5,因此对于与结点5直连且未选入S的结点2、3、4,计算其距离与出发点1的距离。计算时,判断经过结点5的路径和已知路径哪个更短。对于结点2,经过结点5的路径长度为5+3=8,不经过则为已知的10,因此更新其最短路径长度为8(path数组中可以更新结点2的值为5,表示到达结点2的最短路径中终点的前驱结点为5)。同理,对于结点3,5+9=14<$\infty$,其最短路径长度更新为14。对于结点4,5+2=7<$\infty$,其最短路径长度更新为7。接着,选择V-S中有路径长度最短的结点4加入S;
第三趟:重复第二趟中的过程,更新结点4的邻近结点3(未加入S)的最短路径长度,7+6=13<14,因此更新为13,然后选择V-S中路径最短的结点2加入S;
第四趟:继续重复,更新结点2的邻近结点3(未加入S)的最短路径长度,8+1=9<13,因此更新为9,然后选择V-S中路径最短的结点3加入S;
这样所有结点均加入S,计算完毕。
特点
显然,Dijkstra 算法是基于贪心策略的。若使用邻接矩阵表示,它的**时间复杂度为$O(|V|^2)$。若使用带权的邻接表表示,虽然修改dist[]的时间可以减少,但由于在dist[]中选择最小分量的时间不变,其时间复杂度仍为$O(|V|^2)$。注意:如果边的权值为负,则dijkstra算法不适用。**
==Floyd算法==(动态规划)
参考:https://www.bilibili.com/video/BV1LE411R7CS
基本思想
Floyd算法的基本思想是:递推产生一个n阶方阵序列$A^{(-1)}$ ,$A^{(0)}$, … , $A^{(K)}$, … ,$A^{(n-1)}$,其中$A^{(K)}[i][j]$表示从顶点$v_i$到顶点$v_j$的最短路径长度,k表示绕行第k个顶点的运算步骤。
初始时,对于任意两个顶点$v_i$和$v_j$,若它们之间存在边,则以此边上的权值作为它们之间的最短路径长度;若它们之间不存在有向边,则以∞作为它们之间的最短路径长度。逐步尝试在原路径中加入顶点k(k=0, 1, …, n-1)作为中间顶点。如果增加中间顶点后,得到的路径比原来的路径长度减少了,则以此新路径代替原路径。算法的描述如下:
定义一个n阶方阵序列:$A^{(-1)}$ ,$A^{(0)}$, … , $A^{(K)}$, … ,$A^{(n-1)}$,其中:
$A^{(-1)}[i][j]=arcs[i][j]$(也就是不经过任何顶点的路径,路径长度就直接等于邻接矩阵的值)
$A^{(k)}[i][j]=Min{A^{(k-1)}[i][j], \space A^{(k-1)}[i][k]+A^{(k-1)}[k][j] }, \space k=0,1,…,n-1$(经过和不经过顶点$v_k$的路径长度,取最小值,得到考虑k个顶点的情况下的最短路径)
Floyd 算法是一个迭代的过程,每迭代一次, 在从$v_i$到$v_j$的最短路径上就多考虑了一个顶点;经过n次迭代后所得到的$A^{(n-1)}[i][j]$考虑了路径上可能遇到的所有结点,所以就得到了从$v_i$到$v_j$的最短路径长度,即方阵$A^{(n-1)}$中就保存了任意一对顶点之间的最短路径长度。
算法计算过程举例
如图14-12 所示为带权有向图G及其邻接矩阵,下面通过实例来说明Floyd算法的过程见表14-2。
第一个矩阵$dist^{(-1)}$记录所有顶点之间的初始的路径长度,直连的两顶点的dist值就是其边权值,否则为$\infty$。
第二个矩阵$dist^{(0)}$将顶点$V_0$纳入路径的考虑中。将已知的顶点$V_i$和顶点$V_j$之间的路径长度$dist^{(-1)}[i][j]$与经过顶点$V_0$的路径长度$dist^{(-1)}[i][0]+dist^{(-1)}[0][j]$相比较,取其最小值作为$dist^{(0)}[i][j]$的值。
比如$dist^{(-1)}[2][1]$初始为$\infty$,而考虑经过顶点$V_0$时,路径长度为$dist^{(-1)}[2][0]+dist^{(-1)}[0][1]=5+6=11<\infty$。因此$dist^{(0)}[2][1]=11$。(此处可以有一个path二维数组,用于存储顶点之间的最短路径所经过的顶点,默认值为-1。比如这里可以令$path[2][1]=0$表示顶点2到顶点1的最短路径要经过顶点0。查找路径时,再继续查找$path[2][0]$和$path[0][1]$即可,这样就可以查找到完整路径)
同理,第三个矩阵$dist^{(1)}$将顶点$V_1$纳入路径的考虑中。对于顶点$V_i$和顶点$V_j$之间的路径,对比经过$V_1$和不经过$V_1$的情况,取路径长度的最小值得到$dist^{(1)}[i][j]$。
继续循环下去,直到得到矩阵$dist^{(n-1)}$,考虑了所有的n个顶点。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33void Floyd(int n, float MGraph[ ][n],int Path[][n]) { // n为顶点个数
int i, j,v;
int A[n] [n];
// 初始化dist数组和path数组
for(i=0;i<n;++i){
for(j=0;j<n;++j){
A[i][j] = MGraph[i][j];
Path[i][j] = -1;
}
}
// 迭代dist数组
for(v=0;V<n;++v){ // 考虑路径上可能的n个结点
for(i=0;i<n;++i){ // 所有的顶点对vi、vj
for(j=0;j<n;++j){
if(A[i][j] > A[i][v]+A[v][j]) { // 经过和不经过顶点v,哪个路径更短
A[i][j] = A[i][v] + A[v][j] ; // 更新dist矩阵
Path[i][j] = v; // 经过顶点v,则将path数组也更新
}
}
}
}
}
// 根据path数组输出路径
void printPath(int u, int V, int path[][max] ){
if (path[u][v] == -1 )
cout<<"<"<<u<<", "<<v<<">"; //直接输出
else{
int mid = path[u] [v] ;
printPath(u, mid, path) ;
printPath (mid, V, path) ;
}
}特点
Floyd算法的时间复杂度为$O(|V|^3)$。不过由于其代码很紧凑,而且并不包含其他复杂的数据结构,因此隐含的常数系数是很小的,即使对于中等
规模的输入来说,它仍然是相当有效的。Floyd算法允许图中有带负权值的边,但不允许有包含带负权值的边组成的回路。Floyd 算法同样也适用于带权无向图,因为带权无向图可以视为
有往返二重边的有向图。也可以用单源最短路径算法来解决每对顶点之间最短路径问题。每一次运行时, 轮流将一个顶点作为源点,并且若所有边权值均为非负时,可以采用上面提到的Dijkstral算法,其时间复杂度为$O(|V|^2)*|V|=O(|V|^3)$。
拓扑排序
有向无环图:一个有向图中不存在环,则称为有向无环图,简称DAG图。
AOV网:如果用DAG图表示一个工程, 其顶点表示活动,用有向边$<V_i,V_j>$表示活动$V_i$必须先于活动$V_j$进行的这样一种关系, 则将这种有向图称为顶点表示活动的网络,记为AOV网。在AOV网中,活动$V_i$是活动$V_j$的直接前驱,活动$V_j$是活动$V_i$的直接后继,这种前驱和后继关系具有传递性,且任何活动$V_i$不能以它自己作为自己的前驱或后继。
拓扑排序:在图论中,由一个有向无环图的顶点组成的序列,当且仅当满足下列条件时,称为该图的一个拓扑排序。
每个顶点出现且只出现一次。
若项点A在序列中排在顶点B的前面,则在图中不存在从顶点B到顶点A的路径。或者定义为:拓扑排序是对有向无环图的顶点的一种排序,它使得如果存在一条从顶点A到顶点B的路径,那么在排序中顶点B出现在顶点A的后面。每个DAG图都有一个或多个拓扑排序序列。
对一个DAG图进行拓扑排序的算法有很多,下面介绍比较常用的一种方法的步骤:
- 从DAG图中选择一个没有前驱的顶点并输出。
- 从图中删除该顶点和所有以它为起点的有向边。
- 重复1和2直到当前的DAG图为空或当前图中不存在无前驱的顶点为止。而后一种情况,即当前图中不存在无前驱的顶点,则说明有向图中必然存在环。
5 排序
参考:
https://blog.csdn.net/qq_16775293/article/details/107821256?spm=1001.2014.3001.5502
https://mp.weixin.qq.com/s/ekGdneZrMa23ALxt5mvKpQ
https://www.bilibili.com/video/BV1Ur4y1w7tv
算法的稳定性:如果待排序表中有两个元素$R_i$、$R_j$,其对应的关键字$key_i=key_j$,且在排序前$R_i$在$R_j$前面,如果使用某排序算法排序后,$R_i$仍然在$R_j$的前面,则称这个排序算法是稳定的,否则称排序算法是不稳定的。
注意:对于不稳定的排序算法,只需举出一组关键字的实例说明它的不稳定性即可。
在排序的过程中,根据数据元素是否完全在内存中,可将排序算法分为两类:内部排序是指在排序期间元素全部存放在内存中的排序;外部排序是指在排序期间元素无法全部同时存放在内存中,必须在排序的过程中根据要求不断地在内、外存之间移动的排序。
1 | /* 待排序的顺序表中数据元素的类型声明如下 */ |
5.1 插入排序
基本思想在于每次将一个待排序的记录, 按其关键字大小插入到前面已经排好序的子序列中,直到全部记录插入完成。
直接插入排序
1 | void InsertSort (RecType R[], int n){ // n为数组长度 |
复杂度
直接插入排序的时间复杂度为$O(n^2)$,空间复杂度为$O(1)$。
在最好情况下,表中元素已经有序,此时每插入一个元素,都只需比较一次而不用移动元素,因而时间复杂度为$O(n)$。
稳定性
由于每次插入元素时总是从后向前先比较再移动,所以不会出现相同元素相对位置发生变化的情况,即直接插入排序是一个稳定的排序方法。
缺点:
1)寻找插入位置(耗时,需要从后往前一个个扫描);
2)移动元素(需要将插入位置的元素全部后移);
优化
1)对于寻找插入位置的优化,可以使用二分查找法,由此引出折半插入排序。
折半插入排序:在有序区查找插入位置时,将从后往前的逐个比较优化为折半查找方法,找到插入位置后再集中将后面的元素后移,最后插入。
折半插入排序其实仅减少了元素的比较次数,对移动元素的性能并没有改善。其平均时间复杂度依然为$O(n^2)$,空间复杂度为$O(1)$,是一种稳定的排序方法。
2)携带多个元素进行插入,每次可以移动更多位数,减少移动次数
3)将数组改为链表结构,无需移动元素
4)希尔排序
希尔排序
基本思想:先将待排序表分割成若干形如$L[i, i+d, i+2d, ……, i+kd]$的“特殊”子表,分别进行直接插入排序,当整个表中元素已呈“基本有序”时,再对全体记录进行一次直接插入排序。
希尔排序的排序过程如下:
先取一个**小于n的步长$d_1$**,把表中全部记录分成$d_1$个组,所有距离为$d_1$的倍数的记录放在同一个组中,在各组中进行直接插入排序;然后取第二个步长$d_2<d_1$,重复上述过程,直到所取到的$d_t=1$,即所有记录已放在同一组中,再进行直接插入排序,由于此时已经具有较好的局部有序性,故可以很快得到最终结果。到目前为止,尚未求得一个最好的增量序列,希尔提出的方法是$d_1=n/2$,$d_{i+1}=\lfloor d_i/2 \rfloor $,并且最后一个增量等于1。
每一步的步长$d_t$逐渐减小,先让序列大致有序,然后随着$d_t$减小调整分组方式,组序列越来越长,整体序列也逐渐趋向有序。
比如,如下图片中,透明方块一行代表待排序序列,总共15个元素,所以$d_1=15/2=7$,步长为7,序列会被划分为7个组,第二行中同色方块代表同组元素(7种颜色),第三行代表在每组中进行直接插入排序后的序列:
接着,$d_2=7/2=3$,步长为3,所有元素被划分为3个组,图中第二行有三种颜色,第三行代表在每组中进行直接插入排序后的序列:
最后,$d_3=3/2=1$,步长为1,所有元素被划分为1个组,也就是对序列整体进行一次直接插入排序,所以图中第二行只有一种颜色,第三行代表直接插入排序后的序列,这样就得到了最终排序好的序列:
希尔排序的 核心思想 是化远为近,将相隔较远的元素放在一组,组成短序列进行直接插入排序,逐渐使序列整体趋近有序,减少了查找次数和元素移动的次数。
1 | void ShellSort (RecType R[], int n){ // n为数组长度 |
复杂度
希尔排序的时间复杂度依赖于增量序列的函数,这涉及数学上尚未解决的难题,难以分析,一般认为其平均时间复杂度为$O(n^{1.3})$,最坏情况下为$O(n^2)$。希尔排序空间复杂度为$O(1)$。
稳定性
当相同关键字的元素被划分到不同的分组时,可能会改变它们之间的相对次序,因此,希尔排序是一一个不稳定的排序方法。
5.2 交换排序
冒泡排序
基本思想
假设待排序表长为n,从后往前(或从前往后)两两比较相邻元素的值,若为逆序(即R[i-1]>R[i]),则交换它们,直到序列比较完。我们称它为一趟冒泡,结果将最小的元素交换到待排序列的第一个位置。下一趟冒泡时, 前一趟确定的最小元素不再参与比较,待排序列减少一个元素,每趟冒泡的结果把序列中的最小元素放到了序列的最终位置。这样最多做n-1趟冒泡就能把所有元素排好序。
1 | void BubbleSort(RecType R[], int n){ |
复杂度
最坏情况下时间复杂度为$O(n^2)$,最好情况下(表中元素基本有序)时间复杂度为$O(n)$,其平均时间复杂度为$O(n^2)$。空间复杂度为$O(1)$。
稳定性
冒泡排序是一个稳定的排序方法。
注意:冒泡排序中所产生的有序子序列一定是全局有序的(不同于直接插入排序),也就是说有序子序列中的所有元素的关键字一定小于或大于无序子序列中所有元素的关键字,这样每一趟排序都会将一个元素放置到其最终的位置上。
==快速排序==(常考)
基本思想
基于**分治法。首先从待排序序列中取一个元素作为基准数;然后扫描序列,将比基准数小的元素全部放到它的左边,大于或等于基准数的元素全部放到它的右边,得到左右两个区间**;接着再对左右区间重复第二步,直到各区间少于两个元素。
代码实现中,采用了**挖坑填数**的方法。首先取出基准数的位置(挖坑),从右往左扫描出小于基准数的元素填坑(得到新坑),再从左往右扫描出大于等于基准数的元素填新坑,这样循环下去直到两指针重合,将基准数填入即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22int paritition(RecType R[], int left, int right) { // 一趟划分
int tmp = R[left]; // 第一个数做为基准数
while (left < right) { // 指针未重合时
while (left < right && R[right] >= pivot) // 定位到右区间中小于基准数的元素
--right;
R[left] = R[right]; // 填坑
while (left < right && R[left] <= pivot) // 定位到左区间中大于基准数的元素
++left;
R[right] = R[left]; // 填坑
}
R[left] = tmp;
return left;
}
void QuickSort(RecType R[], int left, int right) { //快排函数
int tmp;
if (left < right) {
tmp = paritition(R, left, right);
QuickSort(R, left, tmp-1);
QuickSort(R, tmp+1, right);
}
}时间复杂度
快速排序的运行时间与划分是否对称有关,而后者又与具体使用的划分算法有关。快速排序的最坏情况发生在两个区域分别包含n-1个元素和0个元素时,这种最大程度的不对称性若发生在每一层递归上,即对应于初始排序表基本有序或基本逆序时,就得到最坏情况下的时间复杂度为$O(n^2)$;最好情况下,每次划分都能对称,即基准数就是区间的中值,那么最好情况下时间复杂度为$O(nlog_2n)$。
空间复杂度
由于快速排序是递归的,需要借助一个递归工作栈来保存每一层递归调用的必要信息,其容量应与递归调用的最大深度一致。最好情况下,所取基准数就是区间的中值,每次能划分出长度相等的左右区间,所以递归树高度为$\lceil log_2n \rceil$;最坏情况下,因为要进行n-1次递归调用,所以栈的深度为$O(n)$;平均情况下,栈的深度为$O(log_2n)$。因而空间复杂度在最坏情况下为$O(n)$,平均情况下为$O(log_2n)$。
稳定性:
在划分算法中,若右端区间存在两个关键字相同,且均小于基准值的元素,则在交换到左端区间后,它们的相对位置会发生变化,即快速排序是一个不稳定的排序方法。
注意:在快速排序算法中,并不产生有序子序列,但每一趟排序后会将一个元素(基准元素)放到其最终的位置上。
优化
1)当递归过程中划分得到的子序列的规模较小时不要再继续递归调用快速排序,可以采用直接插入排序算法进行后续的排序工作。
2)尽量选取一个可以将数据中分的基准数。如从序列的头尾以及中间选取三个元素,再取这三个元素的中间值作为最终的基准数;或者随机从当前序列中选取基准数,这样做使得最坏情况在实际排序中几乎不会发生。
在最理想的状态下,即partition可能做到最平衡的划分,得到的两个子问题的大小都不可能大于n/2,在这种情况下,快速排序的运行速度将大大提升,此时,时间复杂度为$O(nlog_2n)$。 好在快速排序平均情况下运行时间与其最佳情况下的运行时间很接近,而不是接近其最坏情况下的运行时间。
快速排序是所有内部排序算法中平均性能最优的排序算法。
快排一次排序的应用
例1:一个数组中存储有且仅有大写和小写字母,编写一个函数对数组内的字母重新排列,让小写字母在所有大写字母之前。(2012. 中兴、2013 ●腾讯)
该题直接使用快排的一次区间划分即可,左右指针索引从两端向中间扫描,挖坑填数。代码略。
例2:给定含有n个元素的整型数组a,其中包括0元素和非0元素,对数组进行排序,要求:(2012.人民搜索)
- 排序后所有0元素在前,所有非零元素在后,且非零元素排序前后相对位置不变
- 不能使用额外存储空间
该题需要使用快排的一次空间划分,相当于基准数为0。注意,由于需要保持非零元素排序前后相对位置不变,所以不能使用左右指针索引从两端向中间扫描的办法。这里使用的是将相对位置在左的非0元素依次与在右的0元素交换的方法,这样不会破坏排序前元素的相对位置,代码如下:
1 | void partition(int R[], int p, int r){ |
或者从前往后遍历:
1 | void partition(int R[], int p, int r){ |
例3:进阶——荷兰国旗问题
将乱序的红白蓝三色小球排列成同颜色在一起的小球组(按照红白蓝排序),这个问题称为荷兰国旗问题。这是因为我们可以将红白蓝三色小球想象成条状物,有序排列后正好组成荷兰国旗。序列中,0表示红球,1表示白球,2表示蓝球。
这个问题类似于快排的区间划分问题,但是这里需要使用3个指针索引,而不是2个。使用begin指针指向0元素应该在的位置,current用于跳过1元素,end用以指向2元素应该在的位置。begin和current都初始化指向数组首部,end初始化指向数组尾部。代码如下:
1 | while (current<=end) { |
例4:最小的k个数
输入n个整数,输出其中最小的k个。(2012.网易)
例如输入1, 2, 3,4, 5,,6, 7, 8这8个数字,则最小的4个数字为1, 2, 3, 4。
最简单的思路莫过于把输入的n个整数排序,这样排在最前面的k个数就是最小的k个数。只是这种思路的时间复杂度为O(nlogn)。这里同样可以使用快排区间划分的方法:
我们设最小的k个数中最大的数为A。在快速排序算法中,我们先在数组中随机选择一个数字,然后调整数组中数字的顺序,使得比选中的数字小的数字都排在它的左边,比选中的数字大的数字都排在它的右边( 即快排一次排序)。 如果快排一次划分后这个选中的数字的下标刚好是k-1 (下标从0开始),那么这个数字(就是A)加上左侧的k-1个数字就是最小的k个数。如果它的下标大于k-I,那么A位于它的左边,我们可以接着在它的左边部分的数组中查找;如果它的下标小于k-1,那么A应该位于它的右边,我们可以接着在它的右边部分的数组中查找。
可见,这是一个递归问题,但是注意我们找到的k个数不一定是有序的。可以用如下代码实现:
1 | /* input是输入的数组,元素个数为n, output是用来保存最小k个数的数组*/ |
注意上述方法平均时间复杂度为O(n)。
5.3 选择排序
简单选择排序
从头至尾扫描序列,找出最小的一个元素和第一个元素交换,接着从剩下的元素中继续这种选择和交换方式,最终
得到一个有序序列。
1 | void SelectSort(RecType R[], int n){ |
复杂度:
简单选择排序过程中,元素移动的操作次数很少,不会超过3(n-1)次(一次swap需要3次元素移动),最好的情况是移动0次,此时对应的表已经有序;但元素间比较的次数与序列的初始状态无关,始终是n(n-1)/2次,所以时间复杂度始终是$O(n^2)$。空间复杂度:$O(1)$。
稳定性:不稳定。
选择排序中,每一趟选择最小元素前移后,该元素都是处于其最终的位置上。
堆排序
Heapsort 是指利用堆这种数据结构所设计的一种排序算法。
堆积具有以下特点:
1)完全二叉树
2)子结点的键值或索引总是小于等于(或者大于等于)它的父节点。
在大根堆中,最大元素存放在根结点中,且对其任一非根结点,它的值小于等于其双亲结点值。小根堆的定义刚好相反,根结点是最小元素。
对于关键字序列$(R_1,R_2,…,R_n)$构建的完全二叉树,结点$R[i]$的左孩子为$R[2i]$,右孩子为$R[2i+1]$。由于一般待排序的数组从0开始编号,所以改为结点$R[i]$的左孩子为$R[2i+1]$,右孩子为$R[2i+2]$。
算法思想:
https://www.bilibili.com/video/BV1Ur4y1w7tv?p=20&vd_source=854e3e80724343215a332be36ec7cf83
- 将初始待排序关键字序列$(R_0,R_1,…,R_{n-1})$构建成大顶堆,此堆为初始的无序区;
- 将堆顶元素R[0]与最后一个元素$R[n-1]$交换,此时得到新的无序区$(R_0,R_1,…,R_{n-2})$和新的有序区$(R_{n-1})$,且满足$R[1,2,…,n-2]<=R[n-1]$;
- 由于交换后新的堆顶$R[0]$可能违反堆的性质,因此需要对当前无序区调$(R_0,R_1,…,R_{n-2})$调整为新堆,然后再次将$R[0]$与无序区最后一个元素交换,得到新的无序区$(R_0,R_1,…,R_{n-3})$和新的有序区$(R_{n-2}, R_{n-1})$。不断重复此过程直到有序区的元素个数为n-1,则整个排序过程完成。
下面的代码已经调整为从R[0]开始存储元素,所以左右孩子结点分别为2i+1、2i+2。调整堆后根结点为R[0]。
1 | // 调整根索引为start,最大结点索引不超过end的完全二叉树为大根堆,或者说从中筛选出最大值作为根结点 |
大根堆的初始化如下图,对应上述代码中的:
1 | for(i=n/2-1; i>=0; i--){ |
复杂度
大根堆的调整中,即调用sift函数,向下调整的时间与树高有关,为O(h),即 $O(log_2n)$。建堆过程中每次向下调整时,大部分结点的高度都较小。因此,可以证明在元素个数为n的序列上**建堆的时间复杂度为 O(n)**,这说明可以在线性时间内,将一个无序数组建成一个大顶堆。
在最好、最坏和平均情况下,堆排序的时间复杂度为$O(nlog_2n)$;空间复杂度为$O(1)$。
稳定性:不稳定。
上述代码中的 AdjustDown函数 是向下调整大根堆,适用于根结点被交换(删除),使堆的性质被破环的情况。比如删除堆顶元素后,应该使用最后一个元素替换堆顶,然后比较堆顶和其左右孩子,交换,然后继续向下调整;而如果是作为叶子结点向堆中插入元素,那么就需要向上调整堆,代码如下:
1
2
3
4
5
6
7
8
9
10void AdjustUp(RecType R[], int k){ // n为所插入的结点索引,也为新堆的结点个数,结点索引从0开始编号
R[0] = R[k]; // 将R[k]暂存到根结点R[0]
int i = (k-1)/2; // i始终指向k的父节点
while(i>0 && R[i].key<R[0].key){
swap(R[k], R[i]); // 父节点下调
k = i; // 更新父节点为k,继续向上比较
i = (k-1)/2;
}
R[k] = R[0];
}
堆排序的应用
==最小的k个数==
输入n个整数,输出其中最小的k个。例如输入1, 2, 3, 4, 5, 6, 7和8这8个数字,则最小的4个数字为1, 2, 3和4。(2012. 网易)
在讲快排的时候,已经提出了利用快排的一次划分来解此题,时间复杂度为O(n)。但此种方法也有其限制,首先我们需要一次性读入所有数据,其次,需要修改输入的数组。
其实此题也可以利用堆排序来解决,此种方法特别适合于处理海量数据。
首先我们读入k个数创建一个大小为 k 的大根堆,然后我们依次读入剩余数据,如果当前数据比大根堆的堆顶小,则用这个数替换当前堆顶,并调整堆使其保持大根堆的性质;如果当前数据比堆顶大,那么这个数不可能是最小的k个整数之一,故可以抛弃此数。**此种方法总的时间复杂度是O(nlogk)**。
1 | int a[n];// 数组a中存储输入的n个数 |
当需要求最大的k个数时,只需将大根堆改为小根堆即可,原理相同。
5.4 归并排序
“归并”的含义是将两个或两个以上的有序表组合成一个新的有序表。
二路归并排序
参考:https://www.bilibili.com/video/BV1Ur4y1w7tv?p=17
假定待排序表含有n个元素,首先可以视为n个有序的子表,每个子表长度为1,然后两两归并,得到$\lceil n/2 \rceil$个长度为2或1的有序表;再两两归并,如此重复,直到合并成一个长度为n的有序表为止,这种排序方法称为二路归并排序。如图15-4所示为二路归并排序的例子。
1 | // 将有序的R[left…mid]和R[mid +1 …right]归并到辅助数组rf[left…right] |
复杂度:
最坏情况下,合并两个大小为n的已排序数组所需要的比较次数为2n-1,所以每一趟归并的时间复杂度为$O(n)$,共需进行$\lceil log_2n \rceil$趟归并,所以算法的时间复杂度为$\lceil nlog_2n \rceil$。
Merge()操作中,由于辅助空间刚好要占用n个单元,但每一趟归并后这些空间就被释放了,所以归并排序的空间复杂度为$O(n)$。
稳定性:由于Merge()操作不会改变相同元素的相对次序,所以二路归并排序算法是一个稳定的排序方法。
原地归并排序
多路归并排序
外部排序指的是大文件的排序,即待排序的记录存储在外部存储器上,待排序的文件无法一次装入内存,需要在内存和外部存储器之间进行多次数据交换,以达到排序整个文件的目的。
外部排序最常用的算法是多路归并排序,即将原文件分解成多个能够一次性装入内存的部分, 分别把每一部分调入内存完成排序。 然后,对已经排序的子文件进行归并排序。
从二路到多路(k路),增大k可以减少外存信息读写时间,但k个归并段中选取最小的记录需要比较k-1次,为了降低选出每个记录需要的比较次数k,引出了“败者树”的概念。
败者树 是对树形选择排序的一种变形,可以视为一棵完全二叉树。每个叶结点存放各归并段在归并过程中当前参加比较的记录,内部结点用来记忆左右子树中的“失败者”,而让胜者往上继续进行比较,一直到根结点。如果比较两个数,大的为失败者、小的为胜利者,则根结点指向的数为最小数。
5.5 计数排序
计数排序统计小于等于该元素值的元素的个数i,于是该元素就放在目标数组的索引i位(i≥0)。
- 计数排序基于一个假设,待排序数列的所有数均为整数,且出现在(0,k)的区间之内。
- 如果 k(待排数组的最大值) 过大则会引起较大的空间复杂度,不适合数范围大的情况,一般是用来排序 0 到 100 之间的数字的最好的算法(比如考试分数排名),但是它不适合按字母顺序排序人名。
- 计数排序不是比较排序,排序的速度快于任何比较排序算法。
- 计数排序是稳定的排序算法。
算法思想:
- 找出待排序的数组中最大元素;
- 统计数组中每个值为 i 的元素出现的次数,存入数组 C 的第 i 项;
- 向填充目标数组:将每个元素 i 填充进新数组,填充次数为 C[i] ;
1 | void CountSort(vector<int>& vecRaw, vector<int>& vecObj) |
- 稳定性:稳定。
- 缺点:空间浪费。其需要长度为最大值的计数空间,但是其间的很多数值可能并未出现。
- 优化:使用长度为最大值-最小值+1的计数空间。
==5.5 桶排序==(重要)
桶排序 (Bucket sort)是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。
参考:https://www.bilibili.com/video/BV1Ur4y1w7tv
工作原理:
假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。
- 设置一个定量的数组当作空桶子。
- 寻访序列,并且把项目一个一个放到对应的桶子去(比如一位数放到一个桶、两位数放到一个桶、三位数放到一个桶)。
- 对每个不是空的桶子进行排序(递归或者使用其他排序算法)。
- 从不是空的桶子里把项目再放回原来的序列中,合并。
1 | public class BucketSort implements IArraySort { |
由于桶中将要存放多少元素是不确定的,因此最好将桶定义为链表数据结构。
- 复杂度
桶排序的时间复杂度取决与对各个桶之间数据进行排序的时间复杂度,因为其它部分的时间复杂度都为O(n)。很显然,桶划分的越小,各个桶之间的数据越少,排序所用的时间也会越少,但相应的空间消耗就会增大。
5.5 基数排序(重要)
基数排序是桶排序的扩展,是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。
算法描述:
- 取得数组中的最大数,并取得位数;
- arr为原始数组,从最低位开始取每个位组成radix数组;
- 对radix进行计数排序(利用计数排序适用于小范围数的特点);
- 按个位数分配桶:
- 然后依次从桶中收集元素,同一桶中的元素,先进桶的在前,此序列的个位数是有序的:
- 接着,按照第一次收集的序列顺序,再依次入桶,这次按十位数分配桶:
- 然后依次从桶中收集元素,同一桶中的元素,先进桶的在前,此序列的十位个位组成的数是有序的:
- 接着,按照第二次收集的序列顺序,再依次入桶,这次按百位数分配桶:
- 然后依次从桶中收集元素,同一桶中的元素,先进桶的在前,此序列的个十百位组成的数都是有序的:
1 | def radix(arr): |
- 稳定性:稳定。
5.6 不同排序算法的比较
稳定性
所有简单排序(时间复杂度为0(n)都是**稳定排序,选择排序除外**;
所有时间复杂度为$O(nlog_2n)$的排序都是不稳定排序,归并排序、基数排序除外。希尔排序是不稳定排序,基数排序是稳定排序。
时间复杂度(比较次数)
比较次数与初始排列无关的是选择排序(简单选择排序、堆排序)。
在初始序列基本有序 的情况下,最优的是插入排序 ,此时插入排序时间复杂度为O(n),其次是冒泡排序,时间复杂度也为O(n), 快速排序在此时性能最差,时间复杂度为$O(n^2)$。同时,快速排序在初始序列逆序的时候,性能也最差,此时时间复杂度也为$O(n^2)$。
堆排序对初始数据集的排列顺序不敏感,在最好、最坏和平均情况下,堆排序的时间复杂度均为$O(nlog_2n)$。
空间复杂度
基于比较的排序算法中(插入排序、交换排序、选择排序、归并排序),归并排序的空间复杂度最高,为$O(n)$,其次为快速排序,为$O(logn)$,其余的为$O(1)$。
6 查找
6.1 基本概念
查找结构(查找表):用于查找的数据集合称为查找结构(查找表),它可以是一个链表,也可以是一个数组或其他数据类型。对于查找表经常进行的操作一般有四种:
- 查询 某个特定的数据元素是否在查找表中;
- 检索 满足条件的某个特定的数据元素的各种属性;
- 在查找表中 插入 一个数据元素;
- 从查找表中 删除 某个数据元素。
如果一个查找表的操作只涉及1和2的操作,则无须动态地修改查找表,此类查找表称为静态查找表。与此对应,需要动态地修改的查找表则称为动态查找表。
适合静态查找表的查找方法有:顺序查找、折半查找、散列查找等;适合动态查找表的查找方法有二叉排序树的查找、散列查找等。
平均查找长度:在查找的过程中,一次查找的长度是指需要比较的关键码次数,而平均查找长度则是所有查找过程中进行的关键码比较次数的平均值,其定义如下:
$$
ASL=\sum_{i=1}^np_ic_i
$$
式中,$p_i$为查找第i个元素的概率,一般认为每个元素的查找概率相等;$c_i$为找到第i个元素所需的比较次数。平均查找次数ASL是衡量查找算法效率的最主要指标。
例1:查找一个整数数组中第二大的数。(2012,迅雷)
1 | const int minNum = -32767; // int型最小值 |
6.2 折半查找
折半查找又称为 二分查找,仅适用于事先已经排好序的顺序表。
基本思路
首先将给定值K与表中中间位置元素的关键字比较,若相等,则查找成功,返回该元素的存储位置;若不等,则所需查找的元素只能在中间数据以外的前半部分或后半部分中。然后在缩小的范围中继续进行同样的查找,如此重复直到找到为止。算法如下:
1 | int BinSearch (RecType R[], int n, KeyType k) { |
因为折半查找需要方便地定位查找区域,所以适合折半查找的存储结构必须具有随机存取的特性。因此,二分查找法仅适合于线性表的顺序存储结构,不适合链式存储结构,且要求元素按关键字有序排列。
例1:有一个循环有序数组A,如{7, 8, 9, 0, 1, 2, 3, 4, 5, 6},不知道其最小值的位置。那么如何从这样的数组中寻找一个特定的元素呢? (2012,百度,2012,人民搜索)
解答:可以将这个循环有序数组看作两个有序子数组,前一个子数组的元素均大于后一个数组。在二分查找的过程中,增加一个判断,确定中间元素位于哪一个子数组。
1 | /* |
上述算法对数组元素重复的时候不支持,比如{2, 2, 3, 2, 2},此时只能依次遍历。
判定树
折半查找的过程可用图16-1所示的二叉树来描述,称为 判定树。树中每个圆形结点表示一个记录,结点中的值为该记录的关键字值;树中最下面的叶结点都是方形的,它表示查找不成功的情况。从判定树可以看出,查找成功时的查找长度为从根结点到目的结点的路径上的结点数,而查找不成功时的查找长度为从根结点到对应失败结点的父结点路径上的结点数;每个结点值(mid)均大于其左子结点值(low),且均小于其右子结点值(high)。若有序序列有n个元素,则对应的判定树有n个圆形的非叶结点和n+1个方形的叶结点。
图16-1中,n个圆形结点(代表有序序列有n个元素)构成的树的深度与n个结点的完全二叉树的深度(高度)相等,均为$\lfloor log_2N \rfloor +1$ 或者 $\lceil log_2(N+1) \rceil \space$。
折半查找的时间复杂度为$O(log_2N)$ ,最坏的情况下查找次数也不会超过为$\lfloor log_2N \rfloor +1$ ,不管有没有查找成功。比顺序查找的效率高。
在图16-1所示的判定树中,在等概率的情况下,查找成功的ASL=(1x1+2x2+3x4+4x4)/11=3(每个结点的深度为其查找长度,深度为1的结点有1个,深度为2的结点有2个,深度为3的结点有4个,深度为4的结点有4个),查找不成功的ASL=(3x4+4x8)/12=11/3。
由上述的分析可知,用折半查找法查找到给定值或查找失败的比较次数最多不会超过树的高度,如在图16-1中,查找成功与查找不成功,最坏的情况下,都需要比较4次($\lfloor log_2N \rfloor +1$ ,即树高)。
例5:有一类数组,例如{1,2, 3, 4, 6, 8, 9, 4, 8, 11, 18, 19, 100},前半部分是一个递增数组,后半部分还是递增数组,但整个数组不是递增数组,怎么最快地找出其中一个数(有大量查询待进行) ?(2011●百度)
解答:开始时找出两个数组的分界线,有两个,一个是前一个数组的最末元素,另一个是后一个数组的最初元素,分别设为preMax和aftMin。
然后处理每个查询,查询过程为:
- 分析要查找的数,若此数刚好等于preMax或aftMin,则返回相应位置;
- 否则,若此数小于preMax,则在前一个数组二分查找;
- 若此数大于aftMin,则也在后一个数组二分查找;
- 若此数大于preMax且小于aftMin,则不存在。
6.3 键树
键树的定义与Trie树
键树又称为数字查找树(Digital Search Trees)。
键树其结构受启发于一部大型字典的“书边标目”。字典中标出首字母是A, B, C, …, Z的单词所在页,再对各部分标出第二字母为A, B, C, …, Z的单词所在的页等。
它是一棵度大于等于2的树,树中的每个结点中不是包含一个或几个关键字, 而是只含有组成关键字的符号。例如,若关键字是数值,则结点中只包含一个数位:若关键字是单词,则结点中只包含一个字母字符。
假设有如下16个关键字的集合:{CAI、CAO、LI、LAN、CHA、CHANG、WEN、CHAO、YUN、YANG、LONG、WANG、ZHAO、LIU、WU、CHEN}。可对此集合作如下的逐层分割,首先按首字母分成不同子集,然后再在子集中按第二个字符进行分割….直到每个小子集中只包含一个关键字为止。如图16-2所示。
从根到叶子结点路径中结点的字符组成的字符串表示一个关键字, 叶子结点中的特殊符号S表示字符串的结束。
键树的存储通常有两种方式:
用树的孩子兄弟链表来表示键树(称为双链树)
每个Node有三个域:
symbol域:存储关键字的一个字符;
son域:存储指向第一棵子树的根的指针;
brother域:存储指向右兄弟的指针。
这时的键树又称为双链树。图16-2所示键树的双链树如图16-3所示。
查找过程是,从根结点出发,顺着son查找,如果相等,继续下一个son。否则沿着brother查找。直到到了空指针为止。此时若仍未完成key的匹配,查找不成功。
在双链树中插入或删除一个关键字,相当于在树中某个结点上插入或删除一棵子树。
用多重链表表示(又称为Trie树,字典树)
如果以树的多重链表表示键树,则树的每个结点中应包含d个(d 为关键字符的基,如:字符集由英文大写字母构成时,则d=26)指针域,此时的键树又称为Trie树。
Trie树的思想是利用字符串的公共前缀来降低时空开销。
由hello、her、hi、how、see、so组成的Trie树如下:
Trie树的典型应用是用于统计和排序大量的字符串(但不仅限于字符串),比较适合的是查找前缀匹配的字符串,所以经常被搜索引擎系统用于文本词频统计。
Trie树的优点是最大限度地减少无谓的字符串比较。
Trie树的缺点是如果存在大量字符串且这些字符串基本没有公共前缀,则相应的Trie树将非常消耗内存。
**构建Trie树时间复杂度是 O(n)*(n是Trie树中所有元素的个数,即单词的个数单词的平均长度)
**查询Trie树时间复杂度是 O(k)**(k 表示要查找的字符串的长度,即单词的平均长度)
例1:已知n个由小写字母构成的平均长度为10的单词,判断其中是否存在某个串为另一个串的前缀子串。
解答:使用Trie树。假设要查询的单词是abc,显然以b, c, d…等不是以a开头的字符串就不用查找了。首先建立一棵Trie树,然后将每个单词插入Trie树,时间复杂度为O(n*len),其中len为单词的平均长度10,然后依次查询每个单词,每个单词查询的时间复杂度为单词的长度。查询时看是否存在有单词与已有单词结点重合即可。
例2:给定一个单词 a,如果通过交换单词中字母的顺序可以得到另外的单词b,那么定义b是a的兄弟单词,例如单词army和mary互为兄弟单词。现在给定一个字典,用户输入一个单词,如何根据字典找出这个单词有哪些兄弟单词?要求时间和空间效率尽可能高。(2012. 百度)
解法一:使用hash_map和链表。
首先使兄弟单词具有相同的id,比如army和mary具有相同的id为amry(相当于对单词的字母进行排序)。然后使用hash_map,生成id到链表的映射,链表用来存储id所对应所有兄弟单词。开始时,先遍历字典,将每个单词按照其id加入hash_map对应的链表中去。当需要查找某一单词的兄弟单词时,只需计算其id,然后根据hash_map找到id所对应的链表,这样就可以确定其兄弟单词。其中,创建hash_map的时间复杂度为$O(n)$,查找兄弟单词的时间复杂度为$O(1)$。
解法二:也是使用hash_map和链表。(此方法无需对单词的字母进行排序来生成id)
将每个字母对应一个 质数,这样单词就可以对应为其字母的质数之积。将得到的值进行hash,这样兄弟单词就具有相同的hash值。将hash值与其对应的所有兄弟单词组成的链表进行hash_map映射,key单词的乘积,value为链表起始地址。当需要查找某一单词的兄弟单词时,只需计算其单词乘积,然后查找hash_map,遍历链表就能得到所有兄弟单词。其中,创建hash_map的时间复杂度为$O(n)$,查找兄弟单词的时间复杂度为$O(1)$。
解法三:利用Trie树。
单词插入Trie树之前,先按照字母排序,如army与mary排完序都是amry。然后将amry插入Trie树,在Trie树的结点中增加一个vector,记录所有的兄弟单词。这样查询的时候,只需先将查询词排序,然后把排序后的单词拿去查询,当所有字母都遍历后,读出对应结点的vector,里面存储的即是此单词的所有兄弟单词。
键树的两种实现的对比
双链树和Trie树是键树的两种不同表示方法,它们有各自的特点。
从其不同的存储结构特性可见,若键树中结点的度较大,则采用Trie树结构较双链树更为合适。
综上,键树的查找过程都是从根结点出发,走了一条从根到叶子( 或非终端结点)的路径,其查找时间依赖于单词的长度。
6.4 后缀树与后缀数组
后缀树
键树只适合前缀匹配和全字匹配,而后缀树(Sufix Tree)适合后缀和子串匹配。它与键树的最大不同在于,后缀树的单词集合是由指定字符串的后缀子串构成的。
比如字符串“minimize” 的后缀子串分别如下:minimize, inimize, nimize, imize, mize, ize, ze, e
然后对这些子串的集合建立一棵键树, 即为“minimize”的后缀树。若字符串s为BIBS,则其建
立的后缀树如图16-4所示。含有所有的后缀子串BIBS、IBS、BS、S。
后缀树常用于在串s中查询子串P是否存在。
**查询效率为O(n)**,n为单词长度。
后缀树还可以用来找出字符串S的最长重复子串S1、找出字符串S1和S2的最长公共子串、找出字符串s的最长回文子串S1等。
后缀数组
后缀树实现较为复杂,通常可以用其变形后缀数组代替,使用数组来存储所有的后缀子串。
比如,若输入字符串为”banana”,该数组将表示这些后缀:
a[0]:banana a[1]:anana a[2]:nana a[3]:ana a[4]:na a[5]:a
可见,由于数组a中的指针分别指向字符串中的每个后缀,所以将数组a命名为”后缀数组”。
找出字符串S的最长重复子串S1,比如abcdabcd的最长重复子串是abcd,abcdabcda的最长重复子串是abcda,最长重复子串可以重叠。
解法一:直接遍历。时间复杂度为$O(n^3)$。
1 | int comlen(char *p, char *q) { // 返回p、q数组的最大公共长度 |
解法二:使用后缀数组
生成后缀数组,然后对后缀数组进行快速排序,将后缀相近的子串集中在一一起。比如输入字符串为”banana”,则排序后的后缀数组如下:
a[0]:a a[1]:ana a[2]:anana a[3]:banana a[4]:na a[5]:nana
然后通过比较邻接元素,找出最长的重复字符串。
1 |
|
时间复杂度分析:处理过程为先对一个字符串生成相应的后缀数组,然后再排序,排完序依次检测相邻的两个字符串的开头公共部分,其中生成后缀数组时间复杂度为$O(n)$,排序时间复杂度为$O(nlognn)$,依次检测相邻的两个字符串时间复杂度为$O(n^2)$,故总的时间复杂度是$O(n^2logn)$,优于第一种方法的$O(n)$。
6.5 哈希表(重点)
基本概念
哈希表,也叫散列表,它是基于快速存取的角度设计的,是一种典型的“空间换时间”的做法。哈希表是普通数组的一种推广,因为数组可以直接寻址,故可在$O(1)$时间内访问数组的任意元素。
哈希表是根据关键字(Key value)而直接进行访问的数据结构。它将关键字通过某种规则映射到数组中某个位置,以加快查找的速度。这个映射规则称为哈希函数(散列函数),存放记录的数组称为 哈希表。哈希表建立了关键字和存储地址之间的一种直接映射关系。
若多个不同的关键字通过哈希函数计算得到相同的数组下标,称其发生了 冲突(碰撞),这些发生冲突的不同关键字称为 同义词。一方面,设计好的Hash函数应尽量减少这样的冲突;另一方面,由于这样的冲突总是不可避免的,所以还要设计好处理冲突的方法。
hash函数
如果两个散列值是不相同的(根据同一函数),那么这两个散列值的原始输入也是不相同的。这个特性使散列函数具有确定性的结果,具有这种性质的散列函数称为 单向散列函数。
典型的散列函数都有无限定义域,比如任意长度的字节字符串,和有限的值域,比如固定长度的比特串。
典型的哈希算法包括MD4、MD5和SHA-1,MD5和SHA-1 (安全哈希算法)可以说是目前应用最广泛的Hash算法,而它们都是以MD4为基础设计的。
MD4
MD是Message Digest的缩写。MD4的摘要长度为128位比特,可以用来表示32位的十六进制数字,适用于32位字长的处理器。
MD5
MD5是一种面向工业标准的hash方案,摘要长度为128位比特。MD5比MD4要复杂,所以速度也更慢一些,但是更安全,在抗分析和抗差分方面表现更好。
SHA-1
SHA-1是由美国国家安全局(NSA)设计,美国国家标准与技术研究院(NIST)发布的密码散列函数,SHA-1会从一个最大$2^{64}$位元的信息中产生一串160位元的摘要,SHA-1设计时基于和MD4相同原理,并且模仿了该算法。
hash函数的应用包括:文件校验、数字签名、鉴权协议。hash函数不能用来加密。
处理冲突(碰撞)的方法
任何哈希函数都不可能绝对地避免冲突,为此必须考虑冲突发生时应如何进行处理,即为产生冲突的关键字寻找下一个“空”的Hash地址,于是提出了处理冲突的各种方法。
链地址法(hash值对应一个链表,存放多个记录)
链地址法是指把所有的冲突关键字(同义词)存储在一个线性链表中,这个链表由其散列地址唯一标识。
开放定址法(在冲突hash值基础上增量)
开放定址法是指可存放新表项的空闲地址,既向它的同义词表项开放,又向它的非同义词表项开放。一个地址往后的空间按照增量大小依次存放多个hash值。其数学递推公式为($H_i$表示冲突发生后第$i$次探测的散列地址):
$$
H_i=(H(key)+d_i)%m
$$
式中,$i=1, 2, …, k (k<=m-1)$,m为散列表表长,$d_i$为增量序列,$d_i$通常有以下几种取法:当$d=1, 2, …, m-1$时,称为线性探测法。其特点是,冲突发生时顺序查看表中下一个单元,直到找出一个空单元或查遍全表。
当$d=1^2, -1^2, 2^2, -2^2,…,k^2, -k^2$时,其中k<=m/2,又为二次探测法。
当$d_i$=伪随机数序列时,称为伪随机探测法。
在开放定址的情形下,不能随便删除表中已有元素,因为若删除元素将会截断其他具有相同散列地址的元素的查找地址。所以若想删除一个元素时, 给它做一 个删除标记,进行逻辑删除。但这样做的副作用是,在执行多次删除后,表面上看起来散列表很满,实际上只是逻辑删除,物理上有许多位置没有利用,因此需要定期维护散列表,要把做删除标记的元素物理删除。
再散列法
当发生冲突时,利用另一个哈希函数再次计算一个地址,直到冲突不再发生,这种方法称为再哈希法。
建立一个公共溢出区
一旦由哈希函数得到的地址冲突,就都填入溢出表。
进行hash表的查找时,计算查找成功的平均查找长度ASL时,平均的概念是对表中当前非空元素而言的,并非是整
个表长。计算查找失败的平均查找长度ASL时,平均的概念是针对表长。
6.6 一致性哈希
如何快速定位数据在集群中的存储位置,关系到集群的性能。
普通集群
普通集群把固定的key映射到固定的结点上,结点只存放各自key的数据,如图16-5所示。
此种方法将key和结点的关系作为一张单独的表格进行维护,当其中一个结点宕机, 结点上的数据需要迁移,此表格也要重新维护。此种方法的问题是,当需要查找某个key值对应的数据时,必须遍历所有表格,直到寻找到存放
此key值的结点,然后再去对应结点读取数据,可见查找速度慢。
hash集群
为了不想维护上节所述的表格,降低复杂性和其他开销,容易想到对数据的key(假设key为整型,如果不是整型,可通过一个哈希函数映射为一个整型)进行哈希(对结点数取模)。
比如我们原本有四个结点,如图16-6所示。图16-6中,nodeA、 node B等为服务器(结点),key1、key2等为数据的key。可见寻找数据时,只需将key值对结点数取模,然后再去访问对应结点即可。
此种方法的不足是:假如某个时候其中一个结点宕机了,那这个结点的数据就完全不可用了。如要进行数据迁移的话,因为这时候结点少了,变为3,对key重新模3的话,只能整个集群的数据都重新映射一遍才能达到效果。
一致性哈希
一致性哈希是一种哈希算法,在移除或添加一个结点时,它能够尽可能小地改变已存在key的映射关系。
一致性哈希将整个哈希值空间组织成一个虚拟的圆环,现假设某哈希函数Hash的值空间为0~$2^{32}$-1(即哈希值是一一个32位无符号整型),那么整个哈希空间环如图16-7所示。
基本思想:使用相同的哈希算法(即假设的哈希函数Hash)将数据和结点都映射到上图的环形哈希空间中。
把数据映射到Hash空间
假设有4个数据object1~object4,那么通过哈希函数计算出的哈希值key在环上的分布如图16-8所示。
把结点映射到哈希空间
具体可以选择结点服务器的IP或主机名作为关键字进行哈希,这样每台机器就能确定其在哈希环上的位置。
假设当前有A, B和C共3台服务器(结点),那么其映射结果将如图16-9所示,它们在哈希空间中以对应的哈希值排列。
把数据映射到结点
现在结点和数据都已经通过同一个哈希算法Hash映射到哈希数值空间中了,接下来要考虑的就是如何将数据映射到结点上(确定了映射关系,也就确定了存储关系)。在这个环形空间中,如果沿着顺时针方向(当然也可以约定为逆时针)从数据的key值出发,直到遇见一个结点机器,那么就将该数据存储在这个结点上,因为数据和结点的哈希值是固定的,因此这个结点必然是唯一和确定的。这样就确定了一种数据和结点的一对一映射方法。如图16-10所示。
移除结点
考虑假如node B出现问题,根据上面讲到的映射方法,这时受影响的将仅是那些沿node B逆时针遍历直到下一个node (本例为nodeA)之间的数据,即本来映射到node B上的那些数据。
因此这里仅需要变动数据object4,将其重新映射到nodeC上即可,如图16-11所示。
添加结点
考虑已有nodeA、B、C的情况下,再添加一台新的node D的情况。假设在这个环形哈希空间中,node D被映射在数据object2和object3之间。这时受影响的将仅是那些沿node D逆时针遍历直到下一个node (本例是node B)之间的数据(它们本来是映射到node C),将这些数据重新映射到node D上即可。因此这里仅需要变动数据object2,将其重新映射到nodeD上,如图16-12所示。
虚拟结点
在上面的例子中,假设仅部署node A和nodeC,那么在4个数据中,node A仅存储了object1,而node C则存储了objec2、object3 和object4,可见分布是很不平衡的。为了解决这种情况,一致性哈希引入了 “虚拟结点”的概念。
“虚拟结点”(Virtual Node)是实际结点在哈希空间的复制品,一个实际结点对应了若干“虚拟结点”,这个对应个数也称为“复制个数”,“虚拟结点”在哈希空间中以哈希值排列。
仍以仅部署node A和node C的情况为例,现在我们引入虚拟结点,并设置“复制个数”为2,这就意味着一共会存在4个“虚拟结点”,node A1, node A2代表了node A;node C1,node C2代表了nodeC。假设一种比较理想的情况,参见图16-13。
此时,数据object1和objec2被映射到了nodeA上,而objec3和object4映射到了nodeC上。平衡性有了很大提高。
6.7 海量数据处理
所谓海量数据处理,就是基于海量数据的查找、统计、运算等操作。所谓海量数据,就是数据量太大,所以导致要么是无法在较短时间内迅速解决,要么是数据太大导致无法一次性装入内存。从而导致传统的操作无法实现。
分治——hash映射
所有散列函数都有抗碰撞性:如果两个散列值是不相同的(根据同一函数),那么这两个散列值的原始输入也是不相同的。这个特性使散列函数具有确定性的结果。
在对大文件进行处理时,若文件过大,无法一次性读入内存,可以考虑采取Hash映射的方法将文件中的元素映射到不同小文件中,然后再依次处理各个小文件,最后合并处理结果,这样就降低了问题规模。
top K 问题
在大规模数据处理中,经常会遇到的一类问题:如何寻找出最大的前K个数、或最小的K个数。
若这些数据能一次性读入内存,快排一次排序是时间复杂度为O(n)的解决办法;
但当面对着海量数据时,快排的一次划分就不能再使用。但依然可以使用堆(求最大K个数采用小根堆,求最小K个数采用大根堆),时间复杂度为O(nlogk),空间复杂度为0(1)。故堆也是海量数据处理经常采用的工具。
对单词hash后取余,按余数将文件内的单词分散到多个文件,每个文件大小不超过内存限制。然后按照分治法的思想,在每个小文件内对单词进行频率统计(trie树或者hash_map),然后对每个文件的频率前100的单词进行归并排序。
Bit-map
Bit-map的原理就是使用位数组来表示某些元素是否存在,一个元素对应一位,由于采用了bit 为单位来存储数据,因此在存储空间方面,可以大大节省,故适用于海量数据的快速查找、判重、删除等。
假设我们要对值区间为0~7的5个元素(4, 7, 2, 5, 3) 排序(这里假设这些元素没有重复)。那么我们就可以采用Bit-map的方法来达到排序的目的。要表示8个数,我们就只需要8个bit (1Bytes),首先我们开辟1Byte的空间,bit位依次编号为01234567,将这些空间的所有bit位都置为0,得到00000000。然后遍历待排序表,将元素值所对应的bit位置1,得到00111101。最后依次输出该位为1的编号即可:2, 3, 4, 5, 7。
位图排序的时间复杂度是O(n),它是以空间换时间(需要一个n位的串)。
在程序设计中,经常需要判断集合中是否存在重复的问题,当数据量比较大时,位图法比较适合。
例2:已知某个文件内包含一些电话号码, 每个号码为8位数字,统计不同号码的个数。
解答:8位数字表示的最大数为99999,可以理解为从0~99999999的数字,一共10的8次方个数字。用bit-map解决,则每个数字对应一个 bit位,所以只需要约12MB(约等于10的8次方)。这样,就用了只有12M左右的内存表示了所有的8位数的电话。依次读入每个电话号码,然后将bitmap相应位置为1,最后统计bit- map中为1的位数即为不同号码的个数。
位图法还可用来快速判断集合中某个数据是否存在。
例3:给40亿个不重复的unsigned int 的整数,没排过序的,然后再给一个数, 如何快速判断这个数是否在40亿个数当中?
解答:unsigned int最多有$2^{32}$个数,用Bit-map的方法,申请512M (512*20*8=$2^{32}$) 的内存,一个bit位代表个unsigned int值。读入40亿个数,设置相应的bit位,读入要查询的数,查看相应bit位是否为1,为1表示存在,为0表示不存在。
本题若限制进一步节省内存,但可以允许一定的错误率,那么可以采用下节将要介绍的Bloom filter。
例4:在2.5亿个整数中找出只出现一次的整数,内存不足以容纳这2.5亿个整数。
方案1:采用2-Bitmap (每个数分配2bit, 00表示不存在,01表示出现一次, 10表示多次,11无意义)进行,共需内存$2^{32}$*2bit=1GB内存,其中$2^{32}$是因为整数最多有$2^{32}$个。然后依次扫描这2.5亿个整数,查看Bitmap中对应位,如果是00变01, 01变10,10 保持不变。扫描结束后,查看bitmap,把对应位是01的整数输出即可。
方案2:也可采用Hash映射的方法,划分成多个小文件。然后在小文件中利用hash_map找出不重复的整数。
Bloom Filter
Bloom Filter(布隆过滤器)可以视为对Bit-map的扩展。Bit-map的作法是申请一个N位(N为集合中最大整数)的数组,然后每一位对应一个特定整数。
Bloom Filter 的基本原理是位数组与Hash函数联合使用,使用多个hash函数将元素映射到位数组的多个位上,多个置1的位共同表示该元素存在。具体而言,Bloom Filter 是一个包含了N位的位数组,数组的每一位都初始化为0,然后定义k个不同的Hash函数,每个Hash函数都可以将集合中的元素映射到位数组中的某一位。
当向集合中 插入 一个元素时,根据k个Hash函数可以得到位数组中的k个位,将这些位全部设置为1(如果一个位置多次被置为1,那么只有第一次会起作用,后面几次将没有任何效果);
当要 查询 某个元素是否属于集合时,就使用k个哈希函数得到此元素对应的k个位,如果所有点都是1,那么元素在集合内(其实是可能在这个集合,因为有可能某个为1的位是被别的元素置1的,所以存在出错的可能);如果有0,元素则不在集合内。
Bloom Filter的位数m通常要比集合中的最大元素小得多,可见,Bloom Filter是一种空间效率和时间效率很高的随机数据结构,但这种高效是有一-定代价的:在判断一个元素是否属于某个集合时,有可能会把不属于这个集合的元素误认为属于这个集合。因此,Bloom Filter不适合那些“零错误”应用场合。而在能容忍低错误率的应用场合下,Bloom Filter通过极少的错误换取了存储空间的极大节省。
倒排索引法
正向索引是用来存储每个文档所包含的单词的列表,在正向索引中,文档占据了中心的位置,每个文档指向了一个它所包含的索引项的序列。倒排索引则相反,其存储包含某个单词的文档列表。
倒排索引也常被称为反向索引、置入档案或反向档案,是一种索引方法,被用来存储在全文检索下某个单词在一个文档或者一组文档中的存储位置的映射。它是文档检索系统中最常用的数据结构。
适用范围:搜索引擎的关键字查询。
以英文为例,下面是要被索引的文本:
T0 = “it is what it is”
T1 = “what is it”
T2 = “it is a banana”
我们就能得到下面的反向文件索引:(0、1、2代表上述3个文本,集合代表出现了该单词的文本)
“a”:{2}
“banana”:{2}
“is”:{0, 1, 2}
“it”:{0, 1, 2}
“what”:{0, 1}
那么当用户检索的条件为”what”, “is”和I”it”,则将分别查询这三个关键词对应的文本集合,即{0, 1, 2}、{0, 1, 2}、{0, 1},然后求对应集合的 交集,得到{0, 1},这样就能确定包含关键字的文本。
可见,倒排索引在处理复杂的多关键字查询时,可在倒排表中先完成查询的并、交等逻辑运算,得到结果后再对记录进行存取。