DS
2.线性表
2.2 顺序表的定义
顺序表的静态分配
1 | //顺序表 静态分配 |
顺序表的动态分配
1 | //顺序表 动态分配 |
2.3 顺序表的插入删除
插入
1 | bool ListInsert(SqList &L,int i,int e){ |
best O(1)
worse O(n)
avg O(n)
删除
1 | bool ListDelete(SqList &L,int i,int &e){ |
动态分配也可以使用
ALL O(1)
按值查找
1 | int LocateElem(SeqList L,ElemType e){ |
best O(1)
worse O(n)
avg O(n)
2.5 单链表的定义
顺序表的优点:可随机存取,存储密度高
顺序表的缺点:要求大片连续空间,改变容量不方便
单链表的优点:不要求大片连续空间,改变容量方便
单链表的缺点:不可随机存取,要耗费一定空间存放指针
常规定义
1 | struct LNode{ |
书本中的定义
1 | typedef struct LNode{ |
等价于1
2
3
4
5
6struct LNode{
ElemType data;
struct LNode *next;
};
typedef struct LNode LNode;
typedef struct LNode *LinkList;
声明头指针:1
2LNode *L;
LinkList L;
强调这是一个单链表 —-使用LinkList
强调这是一个结点 —-使用LNode*
不带头节点的单链表
1 | typedef struct LNode{ |
带头节点的单链表
1 | typedef struct LNode{ |
2.6 单链表的插入删除
按位序插入(带头结点)
1 | bool ListInsert(LinkList &L,int i,ElemType e){ |
best O(1)
worse O(n)
按位序插入(不带头结点)
1 | bool ListInsert(LinkList &L,int i,ElemType e){ |
指定结点的后插操作
1 | bool InsertNextNode(LNode *p,ElemType e){ |
1 | //按位序插入封装 |
指定结点的前插操作
1 | //赋值替换,不用去找前驱结点 |
O(1)1
2
3
4
5
6
7
8
9
10
11bool InsertPriorNode(LNode *p,LNode *s){
if(p==NULL||s==NULL){
return false;
}
s->next=p->next;
p->next=s;
ElemType temp=p->data;
p->data=s->data;
s->data=temp;
return true;
}
按位序删除(带头结点)
1 | bool ListDelete(LinkList &L,int i,ElemType &e){ |
avg worse O(n)
best O(1)
指定结点的删除
1 | bool DeleteNode(LNode *p){ |
O(1)
如果p是最后一个结点,只能从表头开始依次寻找p的前驱,时间复杂度O(n)
2.7 单链表的查找
按位查找
1 | LNode * GetElem(LinkList L,int i){ |
avg O(n)
1 | //王道书版本 |
按值查找
1 | LNode * LocateElem(LinkList L,ElemType e){ |
avg O(n)
求表的长度
1 | int length(LinkList L){ |
2.8 单链表的建立
尾插法
1 | LinkList List_TailInsert(LinkList &L){ |
O(n)
头插法
1 | LinkList List_HeadInsert(LinkList &L){ |
重要应用:链表的逆置
2.9 双链表
定义与初始化
1 | typedef struct DNode{ |
双链表的插入
1 | bool InsertNextDNode(DNode *p,DNode *s){ |
p没有后继结点:
双链表的删除
1 | bool DeleteNextDNode(DNode *p){ |
双链表的销毁
1 | void DestoryList(DLinklist &L){ |
双链表的遍历
1 | while(p!=NULL){ |
双链表不可随机存取,按位查找,按值查找操作都只能用遍历的方式实现O(n)
2.10 循环列表
循环单链表
1 | typedef struct LNode{ |
循环双链表
1 | typedef struct DNode{ |
循环双链表的插入
1 | bool InsertNextDNode(DNode *p,DNode *s){ |
step2 compare to #双链表的插入
循环双链表的删除
1 | bool DeleteNextDNode(DNode *p){ |
step2 compare to #双链表的删除
2.11 静态链表
定义
1
2
3
4
5
6
7
8
9
struct Node{
ElemType data;
int next;
};
void testSLinkList(){
struct Node a[MaxSize];
}
课本上的定义:1
2
3
4
5
typedef struct Node{
ElemType data;
int next;
}SLinkList[MaxSize];
等价于1
2
3
4
5struct Node{
ElemType data;
int next;
}
typedef struct Node SLinkList[MaxSize];
注解:1
2
3void testSLinkList(){
SLinkList a;
}
等价于1
2
3void testSLinkList(){
struct Node a[MaxSize];
}
自己验证一下吧!1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct Node{
int data;
int next;
};
typedef struct{
int data;
int next;
}SLinkList[MaxSize];
int main(){
struct Node x;
printf("sizeX=%d\n",sizeof(x));
struct Node a[MaxSize];
printf("sizeA=%d\n",sizeof(a));
SLinkList b;
printf("sizeof=%d\n",sizeof(b));
}
查找
从头结点出发挨个往后遍历结点 O(n)
插入位序为i的结点
1.找到一个空的结点,存入数据元素
2.从头结点出发找到位序为i-1的结点
3.修改新节点的next
4.修改i-1号结点的next
删除某个结点
1.从头结点出发找到前驱结点
2.修改前驱结点的游标
3.被删除结点next设为-2(空)
总结
静态链表:用数组的方式实现的链表
优点:增,删操作不需要大量移动元素
缺点:不能随机存取,只能从头结点开始依次往后查
找:容量固定不可变
适用场景:
1.不支持指针的低级语言
2.数据元素数量固定不变的场景(如操作系统的文件分配表FAT)
2.12 顺序表和链表的比较
3.栈和队列
3.1 栈的基本概念
栈是只允许在一端进行插入和删除操作的线性表
特点:后进先出 Last First Out (LIFO)
n个不同元素进栈,出栈元素不同排列的个数为,上述公式称为卡特兰(Catalan )数(不要求掌握)
3.2 栈的顺序存储结构
初始化操作
1 |
|
进栈操作
1 | bool Push(SqStack &S,ElemType x){ |
1 | S.top=S.top+1; |
出栈操作
1 | bool Pop(SqStack &S,ElemType &x){ |
1 | x=S.data[S.top]; |
读栈顶元素操作
1 | bool GetTop(SqStack &S,ElemType &x){ |
注意
1 | void InitStack(SqStack &S){ |
则:1
2
3S.data[S.top++]=x;
x=S.data[--S.top];
top==MaxSize
共享栈
1 |
|
3.3 栈的链式存储结构
1 | typedef struct Linknode{ |
根据复习单链表不带头结点的操作
3.4 列队的基本概念
队列是只允许在一端进行插入,在另一端删除的线性表
队列的特点:先进先出First In First Out(FIFO)
3.5 列队的顺序存储结构
队列的顺序实现
1 |
|
入队
1 | bool EnQueue(SqQueue &Q,ElemType x){ |
出队
1 | bool DeQueue(SqQueue &Q,ElemType &x){ |
读取
1 | bool GetHead(SqQueue &Q,ElemType &x){ |
判断队列状态
法一
队列已满:(Q.rear+1)%MaxSize==Q.front
队空:Q.rear==Q.front
队列元素的个数:(rear+MaxSize-front)%MaxSize
法二
1 |
|
插入size++;
删除size--;
队满size==MaxSize;
队空size==0;
法三
1 |
|
队满:front==rear&&tag==1
队空:front==rear&&tag==0
其他
rear指向队尾元素
入队:1
2Q.rear=(Q.rear+1)%MaxSize;
Q.data[Q.rear]=x;
初始化:1
2front=0;
rear=n-1;
队空:1
[Q.rear+1]%MaxSize==Q.front;
队满:
法1:牺牲一个存储单元
法2:增加一个辅助变量
3.6 列队的链式存储结构
1 | typedef struct LinkNode{ |
初始化(带头结点)
1 | void InitQueue(LinkQueue &Q){ |
初始化(不带头结点)
1 | void InitQueue(LinkQueue &Q){ |
入队(带头结点)
1 | void EnQueue(LinkQueue &Q,ElemType x){ |
入队(不带头结点)
1 | void EnQueue(LinkQueue &Q,ElemType x){ |
出队(带头结点)
1 | bool DeQueue(LinkQueue &Q,ElemType &x){ |
出队(不带头结点)
1 | bool DeQueue(LinkQueue &Q,ElemType &x){ |
3.7 双端队列
双端队列:允许从两端插入,两端删除的队列
输入受限的双端队列:允许从两端删除,从一端插入的队列
输出受限的双端队列:允许从两端插入,从一端删除的队列
考点:判断输出序列合法性
3.8 栈在括号匹配中的应用
遇到左括号就入栈
遇到右括号,就”消耗”一个左括号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
33
34
35
36
37
38
39
40
41
typedef struct{
char data[MaxSize]; //静态数组存放栈中元素
int top;
}SqStack;
//初始化栈
void InitStack(SqStack &S)
//判断栈是否为空
bool StackEmpty(SqStack S)
//新元素入栈
bool Push(SqStack &S,char x)
//栈顶元素出栈.用x返回
bool Pop(SqStack &S,char &x)
bool bracketCheck(char str[],int length){
SqStack S;
InitStack(S); //初始化一个栈
for(int i=0;i<length;i++){
if(str[i]=='(' || str[i]=='[' || str[i]=='{'){
Push(S,str[i]); //扫描到左括号,入栈
}else{
if(StackEmpty(S)){ //扫描到右括号,且当前栈空
return false; //匹配失败
}
char topElem;
Pop(S,topElem); //栈顶元素出栈
if(str[i]==')'&& topElem!='(')
return false;
if(str[i]==']'&& topElem!='[')
return false;
if(str[i]=='}'&& topElem!='{')
return false;
}
}
return StackEmpty(S); //检索完全部括号后,栈空说明匹配成功
}
用栈实现括号匹配: 依次扫描所有字符,遇到左括号入栈,遇到右括号则弹出栈顶元素检查是否匹配
匹配失败情况: 1.左括号单身 2.右括号单身 3.左右括号不匹配
3.9 栈在表达式求值中的应用(上)(后缀为重点)
Reverse Polish notation (逆波兰表达式=后缀表达式)
Polish natation(波兰表达式=前缀表达式)
中缀表达式:运算符在两个操作数中间
后缀表达式:运算符在两个操作数后面
前缀表达式:运算符在两个操作数前面
例子:
| 中缀表达式 | 后缀表达式 | 前缀表达式 |
| —- | —- | —- |
| a+b | ab+ | +ab |
| a+b-c | ab+c- | -+abc |
| a+b-c*d | ab+cd*- | -+ab cd* |
中缀表达式转后缀表达式(手算):
1.确定中缀表达式中各个运算符的运算顺序
2.选择下一个运算符,按照[左操作数 右操作数 运算符]的方式组合成一个新的操作数
3.如果还有运算符没被处理,就继续2
如:
((15÷(7-(1+1)))×3)-(2+(1+1))
=> 15 7 1 1 + - ÷ 2 1 1+ + -
A+B*(C-D)-E/F
=> AB CD-*+ EF/ - 或 ABCD-* EF/ -+ (客观来看两种都正确,只是”机算”结果是前者)
运算顺序不唯一,因此对应的后缀表达式也不唯一
“左优先”原则,不要freestyle,保证手算和机算结果相同
“左优先”原则:只要左边的运算符能先计算,就优先算左边的(可保证运算服务顺序唯一)
A+B-C*D/E+F
=> AB+CD*E/-F+
后缀表达式的计算(手算)
后缀表达式的手算方法:
从左往右扫描,每遇到一个运算符,就让运算符前面最近的两个操作数执行对应运算.
合体为一个操作数
注意:两个操作数的左右顺序
后缀表达式的计算(机算)
用栈实现后缀表达式的计算
1.从左往右扫描下一个元素,直到处理完所有元素
2.若扫描到操作数则压入栈,并回到1;否则执行3
3.若扫描到运算符,则弹出两个栈顶元素,执行相应运算,运算结果压倒栈顶,回到1
注意:先出栈的是”右操作数”
若表达式合法,则最后栈中只会留下一个元素,就是最终结果
练习题;
15 7 1 1 + - ÷ 3 × 2 1 1 + + -
答案:5
中缀表达式转前缀表达式(手算)
中缀转前缀的手算方法:
1.确定中缀表达式中各个运算符的运算顺序
2.选择下一个运算符,按照[运算符 左操作数 右操作数]的方式组合成一个新的操作数
3.如果还有运算符没被处理,就继续2
“右优先”原则:只要右边的运算符能先计算,就优先算右边的
A+B*(C-D)-E/F
=> - +AB-CD /EF 或 +A-\B-CD/EF
前缀表达式的计算
用栈实现前缀表达式的计算
1.从右往左扫描下一个元素,直到处理完所有元素
2.若扫描到操作数则压入栈,并回到1;否则执行3
3.若扫描到运算符,则弹出两个栈顶元素,执行相应运算,运算结果压回栈顶,回到1
注意:先出栈的是”左操作数”
3.10 栈在表达式求值中的应用(下)
中缀表达式转后缀表达式(机算)
初始化一个栈,用于保存暂时还不能确定运算顺序的运算符.
从左到右处理各个元素,直到末尾.可能遇到三种情况:
1.遇到操作数.直接加入后缀表达式
2.遇到界限符.遇到”(“直接入栈;遇到”)”则依次弹出栈内运算符并加入后缀表达式,
3.遇到运算符.依次弹出栈中优先级高于或等于当前运算符的所有运算符,并加入后缀表达式,
若碰到”(“或栈空则停止.之后再把当前运算符入栈.
按上述方法处理完所有字符后,将栈中剩余运算符依次弹出,并加入后缀表达式
中缀表达式的计算(用栈实现)
中缀转后缀+后缀表达式求值 两个算法的结合
用栈实现中缀表达式的计算:
初始化两个栈,操作数栈和运算符栈
若扫描到操作数,压入操作数栈
若扫描到运算符或界限符,则按照”中缀转后缀”相同的逻辑压入运算符栈(期间也会弹出
运算符,每当弹出一个运算符时,就需要再弹出两个操作数栈的栈顶元素并执行相应运算,运算结果再压回操作数栈)
3.11 栈在递归中的应用
函数调用的特点:最后被调用的函数最先执行结束(LIFO)
函数调用时,需要用一个栈存储:
1.调用返回地址
2.实参
3.局部变量
适合用”递归”算法解决:可以把原始问题转换为属性相同,但规模较小的问题
Eg1: 计算正整数的阶层n!
Eg2:求斐波那契数列
递归调用时,函数调用栈可称为”递归工作栈”
每进入一层递归,就将递归调用所需信息压入栈顶
每退出一层递归,就从栈顶弹出相应信息
缺点:太多层递归可能会导致栈溢出
缺点:可能包含很多重复计算
3.12 队列的应用
树的层次遍历
图的广度优先遍历
在操作系统中的应用:多个进程争抢着使用有限的系统资源时,FCFS(First Come First Service,先来先服务)是一种常用策略.
Eg:打印数据缓冲区
3.13 特殊矩阵的压缩存储
一维数组的存储结构
ElemType a[10];
起始地址:LOC
各数组元素大小相同,且物理上连续存放.
数组元素a[i]的存放地址=LOC+i*sizeof(EleType)
注:除非题目特别说明,否则数组下标默认从0开始
二维数组的存储结构
ElemType b[2][4];
行优先存储或者列优先存储
M行N列的二维数组b[M][N]中,
若按行优先存储,则
b[i][j]的存储地址=LOC+(iN+j)\sizesof(ElemType)
若按列优先存储,则
b[i][j]的存储地址=LOC+(jM+i)\sizesof(ElemType)
普通矩阵的存储
可用二维数组存储
对称矩阵的压缩存储
策略:只存储主对角线+下三角区
按行优先原则将各元素存入一维数组中
数组大小应为(1+n)*n/2
关于矩阵下标和一维数组下标的映射:
问按照行优先的原则,ai,j 是第(1+i)i/2+j个元素
按照列优先的原则是[[n+(n-1)+…+(n-j+2)]+(i-j)+1]
三角矩阵的压缩存储
压缩存储策略:按行优先原则将橙色区元素存入一维数组中.并在最后一个位置存储常量c
下三角矩阵:按照行优先的原则,是B[0]B[k]开始 k=(1+i)i/2+j-1 ,上三角区域都是(1+n)n/2
上三角矩阵:按照行优先的原则,是B[0]B[k]开始 k=(n+(n-1)+…+(n-i+2))+(j-i) ,下三角区域都是(1+n)n/2
三对角矩阵的压缩存储
一共需要存储3*n-2个元素
前i-1行共3(i-1)-1个元素
ai,j是i行第j-i+2个元素
ai,j是第2i+j-2个元素,k=2i+j-3
反问:若已知数组下标k,如何得到i,j?
第k+1个元素,在第几行?第几列?
前i-1行共3(i-1)-1个元素
前i行共3i-1个元素
显然,3(i-1)-1
由k=2i+j-3得j
稀疏矩阵的压缩存储
稀疏矩阵:非零元素远远少于矩阵元素的个数
压缩存储策略:
顺序存储—三元组<行,列,值>
链式存储—十字链表法
4.串
4.1 串的定义和基本操作
4.2 串的存储结构
串的顺序存储
1 |
|
1 | typedef struct{ |
串的链式存储
1 | typedef struct StringNode{ |
存储密度低,每个字符1B,每个指针4B
解决方案:每个结点存多个字符1
2
3
4typedef struct StringNode{
char ch[4];
struct StringNode * next; //4B
}StringNode,* String;
求子串
1 |
|
比较大小
1 | S.ch ="wangdao" |
定位操作
1 | int Index(SString S,SString T){ |
4.3 朴素模式匹配算法
主串长度为n,模式串长度为m
朴素模式匹配算法:将主串中所有长度为m的子串依次与模式串对比,直到找到一个完全匹配的子串,
或所有的子串都不匹配为止
暴力解法,最多对比n-m+1个子串
代码1就是#定位操作
代码2指针定位算法:
若当前子串匹配模式失败,则主串指针i指向下一个子串的第一个位置,模式串指针j回到 模式串的第一个位置
若j>T.length,则当前子串匹配成功,返回当前子串第一个字符的位置— i-T.length1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17int Index(SString S,SString T){
int i=1;j=1;
while(i<=S.length&&j<=T.length){
if(S.ch[i]==T.ch[j]){
++i;++j;
}
else{
i=i-j+2;
j=1;
}
}
if(j>T.length){
return i-T.length;
}else{
return 0;
}
}
最坏时间复杂度O(nm)
最好时间复杂度O(m)或O(1)
4.4 KMP算法
不匹配的字符之前,一定是和模式串一致的
对于模式串T = ‘abaabc’
当第6个元素匹配失败时,可令主串指针i不变,模式串指针j=3
当第5个元素匹配失败时,可令主串指针i不变,模式串指针j=2
当第4个元素匹配失败时,可令主串指针i不变,模式串指针j=2
当第3个元素匹配失败时,可令主串指针i不变,模式串指针j=1
当第2个元素匹配失败时,可令主串指针i不变,模式串指针j=1
当第1个元素匹配失败时,匹配下-个相邻子串,令j=0, i++, j++
引入next数组来定位j去改变j的值
算法思路:根据模式串T,求出next数组 => 利用next数组进行匹配(主串指针不回溯)1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16int Index_KMP(SString S,SString T,int next[]){
int i=1,j=1;
while(i<=S.length&&j<T.length){
if(j==0||S.ch[i]==T.ch[j]){
++i;
++j;
}else{
j=next[j];
}
}
if(j>T.length){
return i-T.length;
}else{
return 0;
}
}
最坏时间复杂度O(m+n)
其中,求next数组时间复杂度O(m)
4.5 求next数组
任何模式串都一样
第一个字符不匹配时,只能匹配下一个子串,因此,往后余生,next[1]都无脑写0
第二个字符不匹配时,应尝试匹配模式串的第2个字符,因此,往后余生,next[2]都无脑写1
5.二叉树
5.5 二叉树的存储结构
顺序存储
1 |
|
n个结点的二叉链表共有n+1个空链域
5.6 二叉树的先中后序遍历
先序遍历:根左右(NLR)
中序遍历左根右(LNR)
后序遍历:左右根(LRN)1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23//先序遍历
void PreOrder(BiTree T){
if(T!=NULL){
visit(T);
PreOrder(T->Lchild);
preOrder(T->rchild);
}
}
//中序遍历
void InOrder(BiTree T){
if(T!=NULL){
InOrder(T->Lchild);
visit(T);
InOrder(T->rchild);
}
}
//后序遍历
void PostOrder(BiTree T){
if(T!=NULL){
PostOrder(T->Lchild);
PostOrder(T->rchild);
visit(T);
}
O(n)
5.7 二叉树的层次遍历
算法思想:
1.初始化一个辅助队列
2.根节点入队
3.若队列非空,则队头结点出队,访问该结点,并将其左,右孩子插入队尾(如果有的话)
4.重复3直至队列为空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//二叉树的结点(链式存储)
typedef struct BiTNode{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//链式队列结点
typedef struct LinkNode{
BiTNode * data;
struct LinkNode *next;
}LinkNode;
typedef struct{
LinkNode *front,*rear; //队头,队尾
}LinkQueue;
void LevelOrder(BiTree T){
LinkQueue Q;
InitQueue(Q);
BiTree p;
EnQueue(Q,T); //将根结点入队
while(!isEmpty(Q)){ //队列不空则循环
DeQueue(Q,p); //队头结点出队
visit(p); //访问出队结点
if(p->lchild!=NULL){
EnQueQue(Q,p->lchild); //左孩子入队
}
if(p->rchild!=NULL){
EnQueue(Q,p->rchild); //右孩子入队
}
}
}
5.8 由遍历序列构造二叉树
结论:若只给出一棵二叉树的前/中/后/层 序遍历序列中的一种,不能唯一确定一棵二叉树
可以确定的二叉树:
前序+中序遍历序列:
->根节点从前往后分析
后序+中序遍历序列:
->根节点从后往前分析
层序+中序遍历序列:
->根节点 左子树的根 右子树的根
5.9 线索二叉树的概念
1 | typedef struct ThreadNode{ |
tag==0,表示指针指向孩子
tag==1,表示指针是”线索”
n个结点的二叉树,有n+1个空链域!可用来记录前驱,后继的信息
5.10 二叉树的线索化
中序线索化
1 | //用土办法找中序前驱 |
1 | typedef struct ThreadNode{ |
先序线索化
防止循环问题1
2
3
4
5
6
7
8
9void PreThread(ThreadTree T){
if(T!=NULL){
visit(T);
if(T->ltag==0){ //lchild不是前驱线索
PreThread(T->lchild);
}
PreThread(T->rchild);
}
}
后序线索化
不会出现循环问题1
2
3
4
5
6
7void PostThread(ThreadTree T){
if(T!=NULL){
PostThread(T->lchild);
PostThread(T->rchild);
visit(T);
}
}
5.11 在线索二叉树中找前驱后继
中序线索二叉树中找中序后继
1 | //找到以P为根的子树中,第一个被中序遍历的结点 |
O(1)
中序线索二叉树中找中序前驱
1 | //找到以P为根的子树中,最后一个被中序遍历的结点 |
5.12 树的存储结构
双亲表示法(顺序存储)
每个结点中保存指向双亲的”指针”1
2
3
4
5
6
7
8
9
10
typedef struct{
ElemType data;
int parent;
}PTNode;
typedef struct{
PTNode nodes[Max_TREE_SIZE];
int n;
}PTree;
优点:查指定结点的双亲很方便
缺点:空数据导致遍历更慢,查指定结点的孩子只能从头遍历
孩子表示法(顺序+链式存储)
1 | struct CTNode{ |
孩子兄弟表示法(链式存储)
1 | //树的存储--孩子兄弟表示法 |
树和二叉树的转化
树转二叉树
二叉树转树
森林和二叉树的转化
森林转二叉树
二叉树转森林
5.13 树和森林的遍历
树的先根遍历
若树非空,先访问根结点,再依次对每根子树进行先根遍历。1
2
3
4
5
6
7
8void PreOrder(TreeNode *R){
if(R!=NULL){
visit(R);
while(R还有下一个子树T){
PreOrder(T);
}
}
}
利用孩子兄弟表示法转化为二叉树
树的先根遍历序列与这棵树相应二叉树的先序序列相同
树的后根遍历
若树非空,先依次对每颗子树进行后根遍历,最后再访问根结点1
2
3
4
5
6
7
8void PostOrder(TreeNode *R){
if(R!=NULL){
while(R还有下一个子树T){
PostOrder(T);
}
visit(R);
}
}
树的后根遍历序列与这棵树相应二叉树的中序序列相同
树的层次遍历(用队列实现)
1.若树非空,则根节点入队
2.若队列非空,队头元素出队并访问,同时将该元素的孩子依次入队
3重复2直至队列为空
层次遍历—广度优先遍历
先根和后根—层次优先遍历
森林的先序遍历
效果等同于依次对各个树进行先根遍历
效果等同与依次对二叉树的先序遍历
森林的中序遍历
效果等同于依次对各个树进行后根遍历
效果等同于依次对二叉树的中序遍历
紫页p139
| 树 | 森林 |二叉树 |
| :-: | :-: | :-: |
| 先根遍历 | 先序遍历 | 先序遍历 |
| 后根遍历 | 中序遍历 | 中序遍历 |
5.14 二叉排序树
二叉排序树,又称二叉查找树(BST)
左子树上所有结点的关键字均小于根节点的关键字
右子树上所有结点的关键字均小于根节点的关键字
左子树和右子树又各是一棵二叉排序树1
2
3
4
5
6
7
8
9
10
11
12typedef struct BSTNode{
int key;
struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;
BSTNode *BST_Search(BSTree T,int key){
while(T!=NULL&&key!=T->key){
if(key<T->key) T=T->lchild;
else T=T->rchild;
}
return T;
}
递归实现:1
2
3
4
5
6
7
8
9
10
11
12BSTNode *BST_Search(BSTree T,int key){
if(T==NULL){
return NULL;
}
if(key==T->key){
return T;
}else if(key<T->key){
return BSTSearch(T->lchild,key);
}else{
return BSTSrearch(T->rchild,key);
}
}
worst O(h)
best O(1)
二叉树的插入
1 | int BST_Insert(BSTree &T,int k){ |
worst O(h)
二叉排序树的构造
1 | void Creat_BST(BSTree &T,int str[],int n){ |
二叉排序树的删除
先搜索找到目标结点
1.若被删除结点z是叶结点,则直接删除,不会破坏二叉排序树的性质
2.若结点z只有一棵左子树和右子树,则让z的子树成为z父节点的子树,替代z的位置
3.若结点z有左,右两棵子树,则令z的直接后继(或直接前驱)替代z,然后从二叉排序树中删去这个直接后继(或直接前驱),这样就转换成了第一或第二种情况
左子树结点值<根结点值<右子树结点值
EXP:查找右子树中最小的,即进行中序遍历,可以得到一个递增的有序序列
z的后继:z的右子树中最左下结点(该节点一定没有左子树)
z的前驱:z的左子树中最右下结点(该节点一定没有右子树)
参照线索二叉树
查找效率分析
查找长度—在查找运算中,需要对比关键字的次数称为查找长度,反映了查找操作时间复杂度
计算题:查找成功/失败的平均查找长度ASL(Average Search Length)
5.15 平衡二叉树(选择题)
AVL树-树上任一结点的左子树和右子树的高度之差不超过11
2
3
4
5typedef struct AVLNode{
int key;
int balance;
struct AVLNode *lchild,*rchild;
}AVLNode,*AVLTree;
从插入点往回找到第一个不平衡结点,调整以该结点为根的子树
LL
在A的左孩子的左子树中插入导致不平衡
1)LL平衡旋转(右单旋转)。由于在结点A的左孩子(L)的左子树(L)上插入了新结点,A的平衡因子
由1增至2,导致以A为根的子树失去平衡,需要一次向右的旋转操作。将A的左孩子B向右上旋转代替A成
为根结点,将A结点向右下旋转成为B的右子树的根结点,而B的原右子树则作为A结点的左子树。
RR
LR
先左旋后右旋
RL
先右旋后左旋
可以证明含有n个结点的平衡二叉树的最大深度为o(log2n),平衡二叉树的平均查找长度为o(log2n)
5.16 哈夫曼树
结点的权:某种现实含义的数值(如:表示结点的重要性等)
结点的带权路径长度:从树的根到该结点的路径长度(经过的边数)与该结点上权值的乘积
树的带权路径长度:树中所有叶节点的带权路径长度之和 WPL
在含有n个带权叶结点的二叉树中,其中带权路径长度(WPL)最小的二叉树称为哈夫曼树,也称最优二叉树
哈夫曼的构造
很简单,最小的权值结点先相加,依次类推
1.每个初始结点最终都成为叶结点,且权值最小的结点到根结点的路径长度最大
2.哈夫曼树的结点总数为2n-1
3.哈夫曼树中不存在度为1的结点
4.哈夫曼树并不唯一。但WPL必然相同为最优
哈夫曼编码
可变长度编码—允许对不同字符用不等长的二进制位表示
若没有一个编码是另一个编码的前缀,则称这样的编码为前缀编码
前缀编码无歧义
有哈夫曼树得到哈夫曼编码—字符集中的每个字符作为一个叶子结点,各个字符出现的频度作为结点的权值,根据之前介绍的方法构造哈夫曼树
考点:将字符频次作为字符结点权值,构造哈夫曼树,即可得哈夫曼编码,可用于数据压缩
6.图
6.2 邻接矩阵法
1 |
|
无向图:
第i个结点的度=第i行(或第i列)的非零元素个数
有向图:
第i个结点的出度=第i行的非零元素个数
第i个结点的入度=第i列的非零元素个数
第i个结点的度=第i行,第i列的非零元素个数之和
邻接矩阵法存储带权图:1
2
3
4
5
6
7
8
9
typedef char VertexType; //顶点的数据类型
typedef int EdgeType; //带权图中边上权值的数据类型
typedef struct{
VertexType Vex[MaxVertexNum]; //顶点
EdgeType Edge[MaxVertexNum][MaxVertexNum]; //边的权
int vexnum,arcnum; //图的当前顶点数和弧数
}MGraph;
不适合存储稀疏图
6.3 邻接表法
1 | //用邻接表存储的图 |
比较:孩子表示法(顺序+链式存储))
6.4 十字链表,邻接多重表
6.5 图的基本操作
6.6 图的广度优先遍历(BFS)
1.找到与一个顶点相邻的所有顶点
2.标记哪些顶点被访问过
3.需要一个辅助队列
FirstNeighbor(G,x)
NextNeighbor(G,x,y)
对于无向图,调用BFS函数的次数=连通分量数
邻接矩阵存储的图:`时间复杂度=O(|V|^2)
邻接表存储的图:时间复杂度=O(|V|+|E|)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
29bool visited[MAX_VERTEX_NUM]; //访问标记数组
void BFSTraverse(Graph G){ //对图G进行广度优先遍历
for(i=0;i<G.vexum;++i){
visited[i]=FALSE; //访问标记数组初始化
}
InitQueue(Q); //初始化辅助队列Q
for(i=0;i<G.vexnum;++i){ //从0号顶点开始遍历
if(!visited[i]){ //对每个连通分量调用一次BFS
BFS(G,i); //vi未访问过,从vi开始BFS
}
}
}
//广度优先遍历
void BFS(Graph G,int v){
visit(v); //访问初始顶点v
visited[v]=TRUE; //对v做已访问标记
Enqueue(Q,v); //顶点v入队列Q
while(!isEmpty(Q)){
DeQueue(Q,v); //顶点v出队列
for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
//检测v所有邻接点
if(!visited[w]){ //w为v的尚未访问的邻接顶点
visit(w); //访问顶点w
visited[w]=TRUE; //对w做已访问标记
EnQueue(Q,w); //顶点w入队列
}
}
}
}
广度优先生成树由广度优先遍历过程确定.由于邻接表的表示方式不唯一,因此基于邻接表的广度优先生成树也不唯一.
对非连通图的广度优先遍历,可得到广度优先生成森林
6.7 深度优先遍历(DFS)
1 | bool visited[MAX_VERTEX_NUM]; //访问标记数组 |
邻接矩阵存储的图:`时间复杂度=O(|V|^2)
邻接表存储的图:时间复杂度=O(|V|+|E|)
6.8 最小生成树
6.9-11 图算法
Floyd1
2
3
4
5
6
7
8
9
10
11//准备工作,根据图的信息初始化矩阵A和path
for(int k=0;k<n;k++){ //考虑以Vk为中转点
for(int i=0;i<n;i++){ //遍历整个矩阵,i为行号,j为列号
for(int j=0;j<n;j++){
if(A[i][j]>A[i][k]+A[k][j]){ //以Vk为中转点的路径更短
A[i][j]=A[i][k]+A[k][j]; //更新最短路径长度
path[i][j]=k; //中转点
}
}
}
}
7.查找
7.1 查找的基本概念
仅关注查找速度-静态查找表
除了查找速度,也要关注插/删操作是否方便实现
7.2 顺序查找
7.3 折半查找
仅适用于有序的顺序表1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19typedef struct{
ElemType *elem;
int TableLen;
}SSTable;
int Binary_Search(SSTable L,ElemType key){
int low=0,high=L.TableLen-1,mid;
while(low<=high){
mid=(low+high)/2;
if(L.elem[mid]==key){
return mid;
}else if(L.elem[mid]>key){
high=mid-1;
}else{
low=mid+1;
}
return -1;
}
}
右子树结点数-左子树结点数=0或1
折半查找的判定树一定是平衡二叉树
折半查找的判定数中,只有最下面一层是不满的
因此,元素个数为n时树高h=[log2(n+1)]
满足二叉树的定义,失败结点为n+1
7.4 分块查找
分块查找,又称索引顺序查找,算法过程如下:
1.在索引表中确定待查记录所属的分块(可顺序.可折半)
2.在块内顺序查找
若索引表中不包含目标关键字,则折半查找索引表最终停在low>high,要在low所指分块中查找
原因:最终low左边一定小于目标关键字,high右边一定大于目标关键字.而分块存储的索引表中保存的是各个分块的最大关键字
顺序查找索引表 ASL=(b+1)/2+(s+1)/2 当s=√n +1
7.5-7 B树
7.8-9 散列
1.线性探测法:发生冲突时,每次往后探测相邻的下一个单元是否为空
注意:采用”开放定制法”时,删除结点不能简单地将被删除结点的空间置为空,否则将截断在它之后填入散列表的同义词结点的查找路径,可以做一个”删除标记”,进行逻辑删除
2.平方探测法.d=….,k^2,-k^2
散列表长度m必须是一个可以表示成4j+3的素数,才能探测到所有位置
3.伪随机数序列法
8.排列
8.1 排序的基本概念
排序算法的稳定性
关键字相同的元素在排序之后相对位置不变
内部排序:数据都在内存中
外部排序:数据太多,无法全部放入内存
8.2 插入排序
每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中,直到全部记录插入完成.1
2
3
4
5
6
7
8
9
10
11
12int InsertSort(int A[],int n){
int i,j,temp;
for(i=1;i<n;i++){
if(A[i]<A[i-1]){
temp=A[i];
for(j=i-1;j>0&&A[j]>temp;--j){
A[j+1]=A[j];
}
A[j+1]=temp;
}
}
}
哨兵:1
2
3
4
5
6
7
8
9
10
11
12int InsertSort(int A[],int n){
int i,j;
for(i=2;i<n;i++){
if(A[i]<A[i-1]){
A[0]=A[i];
for(j=i-1;A[0]<A[j];--j){
A[j+1]=A[j];
}
A[j+1]=A[0];
}
}
}
优化-折半插入排序1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16void InsertSort(int A[],int n){
int i,j,low.high,mid;
for(i=2;i<=n;i++){
A[0]=A[i];
low=1;high=i-1;
while(low<=high){
mid=(low+high)/2;
if(A[mid]>A[0]) high=mid-1;
else low=mid+1; //查找右半子表
}
for(j=i-1;j>=high+1;--j){
A[j+1]=A[j];
}
A[high+1]=A[0];
}
}
当low>high时折半查找停止,应将[low,i-1]内的元素全部右移,并将A[0]复制到low所指位置
当A[mid]==A[0]时,为了保证算法的稳定性,应继续在mid所指位置右边寻找插入位置
->对链表进行插入排序
avg 0(n^2)
8.3 希尔排序
每次将增量缩小一半1
2
3
4
5
6
7
8
9
10
11
12
13
14void ShellSort(int A[],int n){
int d,i,j;
for(d=n/2;d>=1;d=d/2){
for(i=d+1;i<=n;++i){
if(A[i]<A[i-d]){
A[0]=A[i];
for(j=i-d;j>0&&A[0]<A[j];j-=d){
A[j+d]=A[j];
}
A[j+d]=A[0];
}
}
}
}
仅适用于顺序表
8.4 冒泡排序
1 | void swap(int &a;int &b){ |
8.5 快速排序(代码重点)
用第一个元素把待排序序列划分为两个部分.左边更小,右边更大,该元素的最终位置已确定1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20//快速排序
void QuickSort(int A[],itn low,int high){
if(low<high){ //递归跳出的条件
int pivotpos=Partition(A,low,high); //划分
QuickSort(A,low,pivotpos-1); //划分左子表
QuickSort(A,pivotpos+1,high); //划分右子表
}
}
//用第一个元素将待排序序列划分成左右两个部分
int Partition(int A[],int low,int high){
int pivot=A[low]; //第一个元素作为枢轴
while(low<high){ //用low,high搜索枢轴的最终位置
while(low<high&&A[high]>=pivot) --high;
A[low]=A[high]; //比枢轴小的元素移动到左端
while(low<high&&A[low]<=pivot) ++low;
A[high]=A[low]; //比枢轴大的元素移动到右端
}
A[low]=pivot; //枢轴元素存放到最终位置
return low; //返回存放枢轴位置的最终位置
}
时间复杂度=O(n*递归层数)
空间复杂度=O(递归层数)
把n个元素组织成二叉树,二叉树的层数就是递归调用的层数
最小高度=[log2 n]+1
最大高度=n
若每⼀次选中的“枢轴”将待排序序列
划分为很不均匀的两个部分,则会导
致递归深度增加,算法效率变低
若初始序列有序或逆序,则快速排序
的性能最差(因为每次选择的都是最
靠边的元素)
若每⼀次选中的“枢轴”将待排序序列
划分为均匀的两个部分,则递归深度
最⼩,算法效率最⾼
快速排序算法优化思路:尽量选择可以把
数据中分的枢轴元素。
eg:①选头、中、尾三个位置的元素,取
中间值作为枢轴元素;②随机选⼀个元素
作为枢轴元素
算法稳定性:不稳定
8.6 选择排序
每一趟在待排序元素中选取关键字最小的元素加入有序子序列1
2
3
4
5
6
7
8
9void SelectSort(int A[],int n){
for(int i=0;i<n-1;i++){
int min=i;
for(int j=i+1;j<n;j++){
if(A[j]<A[min]) min=j;
}
if(min!=i) swap(A[i],A[min]);
}
}
不稳定
既可以用于顺序表,也可以用于链表
8.7 堆排序
大根堆:L(i)>=L(2i)且L(i)>=L(2i+1) 在完全二叉树中根>=左,右
小根堆:L(i)<=L(2i)且L(i)<=L(2i+1) 在完全二叉树中根<=左,右
建立大根堆
把所有非终端结点都检查一遍,是否满足大根堆的要求,如果不满足,则进行调整
检查当前结点是否满足根>=左,右 若不满足,将当前结点与更大的一个孩子互换
若元素互换破坏了下一级的堆,则采用相同的方法继续往下调整(小元素不断下坠)1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22//建立大根堆
void BuildMaxHeap(int A[],int len){
for(int i=len/2;i<0;i--){ //从后往前调整所有非终端结点
HeadAdjust(A,i,len);
}
}
//将以k为根的子树调整为大根堆
void HeadAdjust(int A[],int k,int len){
A[0]=A[k]; //A[0]暂存子树的根结点
for(int i=2*k;i<=len;i*=2){ //沿key较大的子节点向下筛选
if(i<len&&A[i]<A[i+1]){
i++; //取key较大的子结点的下标
}
if(A[0]>=A[i]) break; //筛选结束
else{
A[k]=A[i]; //将A[i]调整到双亲结点上
k=i; //修改k值,以便继续向下筛选
}
}
A[k]=A[0]; //被筛选结点的值放入最终位置
}
基于大根堆进行排序
堆排序:每一趟将堆顶元素加入有序序列
并将待排序元素序列再次调整为大根堆1
2
3
4
5
6
7
8
9
10
11
12
13
14//建立大根堆
void BuildMaxHeap(int A[],int len)
//将以k为根的子树调整为大根堆
void HeadAdjust(int A[],int k,int len)
//堆排序的完整逻辑
void HeapSort(int A[],int len){
BuildMaxHeap(A,len); //初始建堆
for(int i=len;i>1;i--){ //n-1趟的交换和建堆过程
swap(A[i],A[1]); //堆顶元素和堆低元素交换
HeadAdjust(A,1,i-1); //把剩余的待排序元素整理成堆
}
}
建堆的过程,关键字对比次数不超过4n,建堆时间复杂度=O(n)
堆排序的时间复杂度=O(n)+O(nlog2n)=O(nlog2n)
空间复杂度O(1)
堆排列是不稳定的
8.8 堆的插入删除
对于小根堆,新元素放到表尾,与父节点对比.若新元素比父节点更小,则二者互换.新元素就这样一路上升,直到无法继续上升为止
被删除的元素用堆底元素替代,然后让该元素不断”下坠”,直到无法下坠为止
关键字对比次数:
每次”上升”调整只需对比关键字1次
每次”下坠”调整可能需要对比关键字2次,也可能只需要对比1次
8.9 归并排序
Merge
归并:把两个或多个已经有序的序列合并成一个
只剩一个子表未合并时,可以将该表中剩余元素全部加到总表
4路归并则每选出一个小元素注需比对关键字3次
结论:m路归并,每选出一个元素需要对比关键字m-1次
在内部排序中一般采用2路归并
核心操作:把数组内的两个有序序列归并为一个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
26int *B=(int *)malloc(n*sizeof(int)); //辅助数组B
void Merge(int A[],int low,int mid,int high){
int i,j,k;
for(k=low;k<=high;k++){
B[k]=A[k]; //将A中所有元素复制到B中
}
for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){
if(B[i]<=B[j]){
A[k]=B[i++]; //将较小值复制到A中
}else{
A[k]=B[j++];
}
}
while(i<=mid) A[k++]=B[i++];
while(i<=high) A[k++]=B[j++];
}
void MergeSort(int A[],int low,int high){
if(low<high){
int mid=(low+high)/2; //从中间划分
MergeSort(A,low,mid); //对左半部分归并
MergeSort(A,mid+1,high); //对右半部分归并
Merge(A,low,mid,high); //归并
}
}
结论:n个元素进行2路归并排序,归并趟数=[log2 n]
时间复杂度O(nlog2 n)
空间复杂度O(n),来自于辅助数组B
稳定的性能
8.10 基数排序
基数排序不是基于”比较”的排序算法
空间复杂度O(r)
时间复杂度O(d(n+r))
基数排序是稳定的
基数排序擅长解决的问题:
1.数据元素的关键字可以方便地拆分为d组,且d较小
2.每组关键字的取值范围不大,即r较小
3.数据元素个数n较大
8.11 外部排序
磁盘的读/写以”块”为单位,数据读入内存后才能被修改,修改完了还要写回磁盘
外部排序:数据元素太多,无法一次全部读入内存进行排序
使用”归并排序”的方法,最少只需在内存中分配3块大小的缓冲区即可对任意一个文件进行排序
“归并排序”要求各个子序列有序,每次读入两个块的内容,进行内部排序后写回磁盘
外部排序时间开销=读写外存的时间+内部排序所需的时间+内部归并所需时间
重要结论:采用多路归并可以减少归并趟数,从而减少磁盘I/O(读写)次数
对 r 个初始归并段,做k路归并,则归并树可⽤ k 叉树表示
若树⾼为h,则归并趟数 = h-1 = ⌈logk r⌉
多路归并带来的负面影响:
1.k路归并时,需要开辟k个输入缓冲区,内存开销增加
2.每挑选一个关键字需要对比关键字(k-1)次,内部归并所需时间增加
结论:若能增加初始归并段的⻓度,则可减少初始归并段数量 r
8.12 败者树—选出最小元素log2 k次
8.13 置换—选择排序 r↓
8.14 最佳归并树
归并过程中的磁盘I/O次数=归并树的WPL*2
#哈夫曼的构造
->多路归并的最佳归并树
注意:对于k叉归并,若初始归并段的数量⽆法构成严格的 k 叉归并树,
则需要补充⼏个⻓度为 0 的“虚段”,再进⾏ k 叉哈夫曼树的构造。
①若(初始归并段数量 -1)% (k-1)= 0,说明刚好可以构成严格k叉树,此时不需要添加虚段
②若(初始归并段数量 -1)% (k-1)= u ≠ 0,则需要补充 (k-1) - u 个虚段