导图社区 数据结构思维导图
- 39
- 0
- 0
- 举报
数据结构思维导图
这是一篇关于数据结构的思维导图，包含数据机构的基本概念、线性表、栈和队列等。希望对你有所帮助！
编辑于2023-11-07 11:40:27- 线性表
- 栈和队列
- 考研数据结构
- 相似推荐
- 大纲
数据结构
第一章 绪论
1.数据结构的基本概念
1.基本概念和术语
1.数据
信息的载体,是描述客观事物属性的数,字符及所有能被计算机识别和处理的符号的集合
2.数据元素
数据的基本单位,由数据项组成,不可分割的最小单位
3.数据对象
具有相同性质的数据元素的集合,数据的一个子集
4.数据类型
一个值的集合和定义在集合上的一组操作的总称
原子类型
值不可再分
结构类型
值可以再分
抽象数据类型
5.抽象数据类型
1.定义: 一个数学模型和定义在模型上的一组操作
2.特点: 定义仅取决于它的一组逻辑特性,与在计算机内部如何表示和实现无关
3.表示: (数据对象,数据关系,基本操作集)
6.数据结构
1.结构: 数据元素之间的相互关系
2.定义: 相互之间存在一种或多种特定关系的数据元素的集合
3.内容: 逻辑结构,存储结构,数据的运算
逻辑结构: 一个算法的设计
存储结构: 一个算法的实现
2.数据结构三要素
1.数据的逻辑结构
1.定义: 数据元素之间的逻辑关系,与存储无关,独立于计算机
2.分类
线性结构
线性表
一对一
非线性结构
集合
同属一个集合
树
一对多
图/网状
多对多
2.数据的存储结构
1.定义: 数据结构在计算机中的表示(又称映像/物理结构)
2.包括: 数据元素的表示和关系的表示
3.分类
顺序存储
优点: 随机存取,元素占用最少存储空间
缺点: 只能使用相邻的一整块存储单元,产生较多的外部碎片
链式存储
优点: 不会出现碎片现象
缺点: 存储指针占用额外的存储空间; 只能顺序存取
索引存储
定义: 建立附加的索引表,每项称为索引项(关键字,地址)
优点: 检索速度快
缺点: 占用较多存储空间; 增加和删除数据要修改索引表,花费较多时间
散列存储
定义: 根据元素的关键字直接计算出该元素的存储地址(Hash存储)
优点: 检索,增加和删除结点都很快
缺点: 若散列函数不好,出现元素存储单元冲突,会增加时间和空间的开销
3.数据的运算
1.运算的定义: 针对逻辑结构,指出运算的功能
2.运算的实现: 针对存储结构,指出运算的具体操作步骤
题目总结
1.易错
1.属于逻辑结构
有序表
2.循环队列是用顺序表表示的队列,是数据结构,不是抽象数据结构
3.不同结点的存储空间可以不连续,但结点内的存储空间必须连续
4.两种不同的数据结构,逻辑结构和物理结构可以完全相同,但数据的运算不同
二叉树与二叉排序树,对于查找结点的时间不同
2.算法和算法评价
1.算法的基本概念
1.定义: 对特定问题求解步骤的描述,指令的有限序列
2.特性
1.有穷性
2.确定性
3.可行性
4.输入
5.输出
3.好的算法
1.正确性
2.可读性
3.健壮性
4.效率与低存储量需求
2.算法效率的度量
1.时间复杂度O(n)
定义: 衡量算法随着问题规模增大,算法执行时间增长的快慢
2.空间复杂度S(n)
1.定义: 衡量算法随着问题规模增大,算法所需空间增长的快慢
2.算法原地工作: 算法所需要的辅助空间为常数,即O(1)
题目总结
1.易错
1.将长度为m,n的两个升序链表,合并为m+n的降序链表(取较小元素,头插法)
1.最好情况: O(min(m,n))
只需比较少的那个
2.最坏情况: O(max(m,n)) =O(m+n)
两个链表都遍历了一遍
2.时间复杂度计算
1.sum += ++i;
O(n^1/2)
第k次: sum = 1+2+3+...+k ≥n
2.i=i*2
O(log₂n)
3.递归算法
1.T(n)=2T(n/2)+n (n>1) (n=1时: T(n)=1)
O(nlog₂n)
2.设n=2^k,先根据递归条件,找到T(2^k)的通式,再转化为n,即得到时间复杂度
3.同一个算法,实现的语言的级别越高级,执行效率越低
第二章 线性表
1.线性表的定义和基本操作
1.线性表的定义
1.定义: 相同数据类型的有限序列
2.注意: 线性表是逻辑结构,顺序表和链表指存储结构
2.线性表的基本操作
1.注意: & 表示C++中的引用,若传入指针型变量且在函数体内要进行改变,要用到指针变量的引用(C中用指针的指针也可以)
2.主要操作
2.线性表的顺序表示
1.顺序表的定义
1.顺序表需要三个部分
存储空间的起始位置
顺序表最大存储空间
顺序表当前的长度
2.静态分配
3.动态分配
4.动态分配语句
C语言: L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);
C++: L.data=new ElemType[InitSize];
5.注意: 动态分配不是链式存储,同样属于顺序存储结构,物理结构没有变化:随机存取方式,只是分配的空间大小可以在运行时决定
6.特点: 随机访问,存储密度高,插入和删除需要移动大量元素
2.顺序表上基本操作的实现
1.插入操作 O(n)
2.删除操作 O(n)
3.按值查找(顺序查找) O(n)
题目总结
1.易错
1.线性表必须是有限序列
2.在顺序表的第i个位置插入一个数,i的合法取值: 1≤i≤n+1
在第n+1个位置插入相当于在表尾追加
2.算法
1.将顺序表的所有元素逆序
1.扫描前半部分,对于第i个元素(0≤i<n/2)将其与后半部分的对应元素(n-i-1)进行交换
空间O(1)
1.1 在数组A[m+n]存在两个长度为m,n的顺序表,实现位置互换
1.思想
1.先将A中所有元素逆序(n,n-1,...,m,m-1,...,1)
2.再对前n个元素和后m个元素分别使用逆序算法
2.实现
1.设置函数Reverse()实现从任意left到right位置的逆序
2.设置函数Exchange()实现两个长度为m,n的顺序表的位置互换
3.Reverse()三个参数,第一个为需要逆序的数组,仿照上述方法, 将第left个元素与其对应的(right-left-1)元素进行交换
4.Exchange()三个参数,第一个为数组A,剩下为长度m和n
5.Exchange()调用Reverse(),第一次传参(A,0,m+n-1) 第二次(A,0,n-1),第三次(A,n,m+n-1)
3.同类描述
1.将A中元素左移p个位置
1.将前p个元素视为数组B
2.将后n-p个元素视为数组C
3.完成B,C位置的互换
时间O(n),空间O(1)
2.顺序表(非有序)删除所有值为x的数据元素
1.用k记录不等于x的元素个数(初值=0),即当前应该插入的位置
2.扫描顺序表,若不为x,将此元素放入第k个位置,k自加1
3.最后修改表的长度=k
时间O(n),空间O(1)
2.1 顺序表(非有序)删除所有值在s与t之间的所有元素
1.只需要把k改为记录小于s或大于t的元素个数即可
3.有序顺序表删除给定值s与t之间的所有元素
1.先找第一个≥s的元素(第一个删除的元素)
2.再找第一个>t的元素(最后一个删除元素的下一个元素)
3.直接将后面的元素前移,最后修改表长
4.有序表删除所有其值重复的元素
1.思想类似于直接插入排序,初始时将第一个元素视为非重复的有序表
2.依次判断后面元素是否与前面非重复有序表的最后一个元素相同
3.两个指针: i一直指向有序表最后一个元素,j为工作指针
4.1 将有序表改为无序表
1.使用散列表,时间为O(n)
5.将两个有序表合并为一个有序表,由函数返回结果
1.函数有三个参数,最后一个为结果链表,引用类型
2.按顺序依次比较两个链表表头元素,取较小的放入新表中
3.看哪个表还有剩余,将剩下的部分加到新表后面
6.长度为L的升序序列S,中位数为┍L/2┑ 求两个等长升序序列A,B的中位数
1.先分别求出A,B的中位数a,b,进行比较
2.若a=b,则a即为所求中位数
3.若a<b,舍弃A中较小的一半,舍弃B中较大的一半,要求两次舍弃的长度相等
4.若a>b,舍弃A中较大的一半,舍弃B中较小的一半,要求两次舍弃的长度相等
5.重复2,3,4,直到两个序列都只含一个元素为止,较小者为所求中位数
注: 为保证每次舍弃长度相等
1.序列为奇数时,都保留中间点
2.序列为偶数时,因为中间点的位置相对在前, 所以舍弃较小部分时应连中间点一起舍去, 才能保证舍弃的长度和较大部分相等
3. 3,4两种情况都需分奇偶讨论
时间O(log₂n),空间O(1)
7.若值为x的元素个数>n/2,称为主元素,求A的主元素
1.选取候选的主元素
1.将第一个数a作为候选主元素放入c中,记录a出现次数为1
2.若下一个元素=a,计数+1,否则计数-1
3.当计数减到0时,更换候选主元素,将下一个数放入c中,重新计数=1
4.重复过程,直到结束
2.判断c中元素是否为真正的主元素
1.再次扫描统计c的出现次数,若>n/2,为主元素
时间O(n),空间O(1)
注:若用计数排序: 时间O(n),空间O(n)
8.找出数组中未出现的最小正整数,时间少
1.用空间换取时间,分配用于标记的数组B[n],记录是否出现1-n中的正整数,初值全0
2.对于小于等于0,或大于n的数不采取任何操作
3.若0<A[i]≤n,令B[A[i]-1]=1,否则不做操作
4.遍历B,找到第一个B[i]==0,返回i+1,若全部不为0,返回i+1(跳出循环时i=n)
3.线性表的链式表示
1.单链表的定义
1.结点类型的描述
2.特点: 浪费空间,非随机存取
3.头指针和头结点区别
1.不管带不带头结点,头指针始终指向链表的第一个结点
2.头结点是带头结点的链表中的第一个结点,通常不存储信息
4.引入头结点的优点
1.在链表第一个位置上的操作和其他位置上的一致
2.无论链表是否为空,头指针都指向头结点的非空指针,空表和非空表处理一致
2.单链表上基本操作的实现
1.头插法建立链表
2.尾插法建立链表
3.按序号查找结点值
4.按值查找表结点
5.插入结点操作
前插操作: 先找到前一个结点,时间复杂度为O(n)
扩展: 将前插操作转化为后插操作,然后交换两个结点的数据,时间复杂度为O(1)
6.删除结点操作
先找到前驱节点,再删除结点,O(n)
扩展: 先和后继结点交换数据,再删除后继结点,O(1)
7.求表长操作
计算数据结点的个数
3.双链表
1.双链表中结点类型的描述
2.插入操作
3.删除操作
4.循环链表
1.循环单链表
1.判空条件: 头结点的指针是否指向头指针
2.对单链表在表头和表尾操作时: 不设头指针仅设尾指针,效率更高
3.可以从任意一个结点开始遍历整个链表
2.循环双链表
判空条件: 头结点的prior域和next域都指向头指针
5.静态链表
1.定义: 用数组描述链式存储结构,也有数据域和指针域.指针是结点的相对地址(数组下标),又称游标
2.形式
3.结束标志: next==-1
4.注意
1.和顺序表一样,也要预先分配一块连续的内存空间
2.插入和删除只需要修改指针,不需要移动元素
3.在不支持指针的高级语言(Basic)中很巧妙
6.顺序表和链表的比较
1.存取方式
顺序表可顺序存取,可随机存取. 链表只能从表头顺序存取
2.逻辑结构与物理结构
3.查找,插入和删除
1.按值查找
无序时,都为O(n)
有序时,顺序表可以折半查找,O(log₂n)
2.按序号查找
顺序表为O(1),链表为O(n)
4.空间分配
5.怎样选取存储结构
1.基于存储的考虑
难以估计长度和存储规模时用链表,但链表的存储密度较低
2.基于运算的考虑
经常做按序号访问数据元素用顺序表
3.基于环境的考虑
顺序表容易实现,链表基于指针
较稳定选顺序表,动态性较强选链表
题目总结
1.易错
1.链式存储结构比顺序存储结构更方便地表示各种逻辑结构
2.顺序存储不只能用于存储线性结构,还能存储图和树的结构(满二叉树)
3.静态链表需要分配较大的连续空间,插入和删除不需要移动元素
4.若用单链表表示队列,应选用带尾指针的循环链表
5.给定一维数组,建立一个有序单链表的最低时间为O(nlog₂n)
先对数组进行排序,再构造单链表
6.链表常用操作为在最后一个元素之后插入,删除第一个元素,最节省时间的是
1.不带头结点且有尾指针的单循环链表
2.即使是双链表,只要不带尾指针,都要找到尾结点,时间为O(n)
注意点
1.插入结点时: 先对插入结点的后继结点操作,再对原结点进行操作
第三章 栈和队列
1.栈
1.栈的基本概念
1.栈的定义: 一端进行插入和删除的线性表
2.栈的特点: 后进先出
3.栈的基本操作: 未做限制,可直接使用
2.栈的顺序存储结构
1.顺序栈的实现
1.栈顶指针:S.top 栈顶元素:S.data[S.top]
2.进栈: 指针先加1,再送值到栈顶元素
3.出栈: 先取栈顶元素值,再将栈顶指针减1
4.判空和判满条件: 因实际给出条件不同而变化
2.顺序栈的基本运算
3.共享栈
1.定义: 将两个栈的栈底设置在共享空间的两端,两个栈顶向中间延伸
2.判空: top0=-1 top1=MaxSize
3.判满: top1-top0=1
只有在上述判空的条件下,该式子才成立,若条件不同,式子也不同
4.进栈: top0先加1再赋值,top1先减1再赋值,出栈相反
注意: 栈顶指针指向栈顶元素和栈顶元素下一个元素(S.top=0)的不同操作
1.栈顶元素
进栈:S.data[++S.top]=x 出栈:x=S.data[S.top--]
2.栈顶元素下一个元素
进栈:S.data[S.top++]=x 出栈:x=S.data[--S.top]
3.栈空和栈满的判断条件也会变化
3.栈的链式存储结构
1.优点: 便于多个栈共享储存空间,提高其效率,不会栈满上溢
2.特点: 所有操作在表头进行,通常没有头结点,将头指针作为栈顶指针,便于结点插入/删除
4.栈的出栈序列
1.出栈序列中每一个元素后面所有比它小的元素组成一个递减系列
对于递增序列来说
2.f(n)=
f(2)=2, f(3)=5, f(4)=14
题目总结
1.易错
1.栈和队列具有相同的逻辑结构,不是存储结构
线性表,栈,队列都属于线性结构
2.链表不带头结点且所有操作在表头进行,最不适合作为链栈的是
1.只有表头结点指针,没有表尾结点指针的单向循环链表
2.原因: 插入结点后,仍需将其变为循环单链表,需找到尾结点,时间为O(n)
3.解决方法
1.若带头结点时: 栈顶取第一个结点,栈指针取头结点
2.若不带头结点: 栈顶取第二个结点,栈指针取第一个结点
3.两者都保持第一个结点不会被改变,不需要找到表尾元素
3.向一个栈顶指针为top的链栈(不带头结点)中插入一个x结点
x->next=top; top=x
4.入栈序列为1,2,...,n,出栈为P1,P2,...,Pn,若P2=3,则P3可能取值个数为n-1
1.显然3之后的4,5,...,n都可以取到
2.P1可能为1,P3可取2
3.P1可能为2,P3可取1
4.P1可能为4,P3可取1,3,4之外所有数
5.采用非递归方式重写递归程序时不一定适用栈
1.计算斐波拉契数列迭代只需要一个循环即可
6.栈顶,队头与队尾的指针的定义是不唯一的,务必要仔细审题
2.算法
1.判断一个链表是否中心对称
1.将前一半元素依次入栈,处理后一半时,访问一个链表元素就从栈中弹出一个元素,判断是否相等
2.注意偶数时没有异常,奇数时应先跳过中心结点
3.不需要真正的栈,用数组充当栈即可,用工作指针i充当栈顶指针
2.队列
1.队列的基本概念
1.定义: 只允许在表的一端进行插入,在另一端进行删除的线性表
2.基本操作
2.队列的顺序存储结构
1.队列的顺序存储
1.两个指针: front指示队头元素,rear指向队尾元素下一个位置
2.初始状态(队空): Q.front==Q.rear==0
3.进队: 先送值到队尾元素,再将队尾指针加1
4.出队: 先取队头元素值,再将队头指针加1
5.存在假溢出
6.类型描述
2.循环队列
1.初始状态(队空): Q.front==Q.rear==0
2.队首指针进一: Q.front=(Q.front+1)%MaxSize
3.队尾指针进一: Q.rear=(Q.rear+1)%MaxSize
4.队列长度: (Q.rear+MaxSize-Q.front)%MaxSize
5.区分队空和队满
1.牺牲一个单元,入队少用一个单元(常用)
队满: (Q.rear+1)%MaxSize==Q.front
队空: Q.front==Q.rear
队列中元素个数: (Q.rear+MaxSize-Q.front)%MaxSize
2.增设表示元素个数的数据成员: Q.size
3.增设tag数据成员: tag=0删除操作:队空, tag=1插入操作:队满
3.循环队列的操作
3.队列的链式存储结构
1.队列的链式存储
1.类型描述
2.带头结点的单链表: 插入和删除操作统一
3.适合数据元素变动较大的情形,不存在队满溢出,多个队列不存在存储分配不合理
2.链式队列的基本操作
4.双端队列
1.定义: 允许两端(前端,后端)都可以入队和出队的队列
2.逻辑结构: 线性结构
3.输入受限的双端队列
4.输出受限的双端队列
题目总结
1.易错
1.用链式存储队列进行删除操作时,头尾指针可能都要修改
一般情况仅需修改队头指针,若只有一个元素,要修改尾指针
2.链队列中,x所指元素入队时,执行操作
1.rear->next=x,x->next=null,rear=x;
2.因为x插入到队尾,所以必须置为空(中间一句),更严密
2.题型
1.判断循环队列初始和列满的情况
1.数组A[0...n-1],front指向队头,rear指向队尾 第一个存储在A[0],问初始情况
1.进队时,front不动,rear+1,最终都指向A[0] 所以初始front=0,rear=n-1
注: 具体问题时,可用一些特殊情况(画简单草图)来判断空和满的情况,比直接思考更快
2.判断输入/输出受限的双端队列不能得到的序列
1.直接根据4个选项一一代入,用排除法
2.一般错误情况: 后进队列的不可能夹在比它先进的两个数的中间(2,3,1)
3.栈和队列的应用
1.栈在括号匹配中的应用
1.思想
1.设置一个空栈,顺序读入括号
2.若为 ) ,与栈顶 ( 配对出栈或者不合法
3.若为 ( ,作为新的更急迫的期待压入栈中
4.算法结束,栈为空,否则括号序列不匹配
2.栈在表达式求值中的应用
1.后缀表达式: 运算符在操作数之后,没有括号
2.中缀转后缀过程
1.按运算符优先级对所有运算符和它的操作数加括号(原本有括号不用加)
2.把运算符移到对应的括号后面
3.去掉括号
注: 前缀表达式把运算符提到括号前面,其他一样
3.中缀转后缀算法思想
1.数字: 直接加入后缀表达式中
2.若为 ( : 入栈
3.若为 ) : 依次把栈中运算符加入后缀表达式,直到 ( 并删除栈中 (
4.若为 + - * /
1.栈空,入栈
2.栈顶为 ( ,入栈
3.高于栈顶元素优先级,入栈[若为同级,同样执行4]
4.否则[低于或等于栈顶优先级],依次弹出运算符,直到比它低的运算符或 ( 或栈空 为止,入栈
5.遍历完成,若栈非空依次弹出所有元素
4.后缀计算表达式过程
1.顺序扫描表达式的每一项
2.操作数: 压入栈中
3.操作符<op>: 连续从栈中退出两个操作数x,y,形成运算指令x<op>y,将计算结果重新压入栈中
3.栈在递归中的应用
1.两个条件
1.递归表达式(递归体)
2.边界条件(递归出口)
2.递归的精髓: 能否将原始问题转化为属性相同但规模更小的问题
3.缺点: 递归次数多,容易造成栈溢出; 包含很多重复计算,效率不高
4.优点: 代码简单,容易理解
5.转化: 需要借助栈来实现
4.队列在层次遍历中的应用
5.队列在计算机系统中的应用
1.解决主机与外部设备之间速度不匹配的问题
1.设置一个打印数据缓冲区,写满后暂停输出,做别的事,等待打印机发出请求
2.解决由多用户引起的资源竞争问题
1.按照每个请求在时间上的先后顺序,排成一个队列,每次把CPU分配给队首用户使用
题目总结
子主题
4.特殊矩阵的压缩存储
1.数组的定义(逻辑结构)
2.数组的存储结构(顺序存储)
1.两种映射方法: 按行优先,按列优先
3.矩阵的压缩存储
1.压缩存储: 多个值相同的元素只分配一个空间,0不分配空间
2.特殊矩阵: 许多相同矩阵元素或零元素,分布有规律
1.对称矩阵
2.三角矩阵
1.下三角矩阵
2.上三角矩阵
3.三对角矩阵
4.稀疏矩阵
1.存储: 将非零元素及相应的行和列构成一个三元组(行标,列标,值)
2.缺点: 失去了随机存取特性
第四章 树和二叉树
1.树的基本概念
1.树的定义
2.基本术语
1.结点的度
一个结点的子结点个数
2.树的度
树中结点的最大度数
3.结点的深度
从根结点开始自顶向下逐层累加
4.结点的高度
从叶结点开始自底向上逐层累加
5.树的高度(深度)
树中结点的最大层数
6.两结点之间的路径
两结点之间经过的结点序列
7.路径长度
路径上经过的边的个数
8.注意
树中的分支是有向的(双亲指向孩子),路径从上向下,两个孩子之间不存在路径
3.树的性质
1.结点数 = 所有结点的度数+1
2.度为m的树的第i层最多有m^(i-1)个结点
3.高度为h的m叉树至多有(m^h-1)/(m-1)个结点
等比数列求和
2.二叉树的概念
1.二叉树的定义及其主要特性
1.二叉树的定义
1.子树有左右之分,次序不能任意颠倒
2.二叉树与度为2的有序树的区别
1.度为2的树至少有3个结点,二叉树可为空
2.度为2的有序树的孩子的左右次序相对于另一个孩子,一个孩子无须区分左右 二叉树的左右次序是确定的
2.几个特殊的二叉树
1.满二叉树
树中的每层都含有最多的结点
2.完全二叉树
1.定义: 每个结点都与满二叉树对应,不一定每层都最多
2.性质
1.叶子结点只在最大的两层上
2.若有度为1的结点,只有一个,该结点只有左孩子
3.二叉排序树
1.左子树上所有结点的关键字小于根结点
2.右子树上所有结点的关键字大于根结点
3.左右子树又各是一颗二叉排序树
4.二叉平衡树
任一结点的左右子树的深度之差不超过1
3.二叉树的性质
1.n0=n₂+1
叶子节点数 = 度为2的结点数+1 (n=n0+n₁+n₂=n₁+2n₂+1)
2.第n层最多有2^(n-1)个结点
3.高度为h的二叉树最多有2^h-1个结点
4.对完全二叉树
1.结点i的双亲结点i/2(取下界)
2.结点i的左孩子为2i,右孩子为2i+1
3.结点i所在层次㏒₂i(取下界)+1
5.n个结点的完全二叉树高度 ㏒₂n(取下界)+1
2.二叉树的存储结构
1.顺序存储
1.适合完全二叉树和满二叉树
2.一般二叉树添加一些不存在的空结点
3.注意: 从数组下标1开始存储,才能满足上述性质
写程序容易忽略
4.区别树和二叉树的顺序存储
1.树中: 数组下标为结点编号,下标上内容指示结点之间关系
2.二叉树中: 下标既表示结点编号,又表示结点之间关系
2.链式存储
1.二叉链表3个域: data,lchild,rchild
2.n个结点的二叉链表有n+1个空链域(根结点不用指针)形成线索链表
3.二叉树的遍历和线索二叉树
1.二叉树的遍历
1.先序遍历
2.中序遍历
3.后序遍历
序 指根结点何时被访问
4.递归算法与非递归算法的转化(中序)
1.思想
1.先扫描(未访问)根结点的所有左结点,一一入栈
2.出栈一个结点(无左孩子或已经访问),访问它
3.扫描它的右孩子,入栈
4.再扫描右孩子的所有左结点,一一入栈
5.如此继续,直到栈为空
2.算法实现
3.非递归算法的执行效率高于递归算法
5.层次遍历(队列)
1.思想
1.先将根结点入队,然后出队,访问该结点
2.若有左子树,将左子树根结点入队
3.若有右子树,将右子树根结点入队
4.然后出队,访问出队结点
5.反复,直到队列为空
2.算法实现
6.由遍历序列构造二叉树
1.先序和中序
1.先序中: 第一个为根结点
2.中序中: 根结点分割成两个子序列,前左子树,后右子树
3.先序中: 找到两个子序列,各自的第一个结点又是根结点
2.后序和中序
后序最后一个结点相当于先序第一个结点
3.先序和后序不可以
2.线索二叉树
1.基本概念
1.目的: 加快查找结点前驱和后继的速度
2.规定
1.无左子树,令lchild指向前驱结点;无右子树,令rchild指向后继结点
前驱,后继由具体的遍历方式决定
2.增加两个标志域标明当前指针指的是前驱(1)还是左孩子(0)
3.线索: 指向前驱和后继的指针
4.线索化: 对二叉树以某种次序遍历使其成为线索二叉树的过程
2.构造
1.线索化的实质
1.遍历一次二叉树,检查结点左右指针域是否为空,为空,改为指向前驱和后继的线索
2.中序遍历序列中: 第一个结点为最左侧结点,最后一个结点为最右侧结点
3.前驱结点
1.左指针为线索,指向结点为前驱结点
2.左指针为左孩子,其左子树的最右侧结点为前驱结点
4.后继结点
1.右指针为线索,指向结点为后继结点
2.右指针为右孩子,其右子树的最左侧结点为后继结点
2.中序遍历线索化实现
3.有时在线索链表也添加一个头结点,构成双向线索链表
1.lchild指向根结点,rchild指向中序遍历最后一个结点
2.中序遍历第一个结点lchild和最后一个结点rchild指向头结点
3.遍历
1.利用线索二叉树可以实现二叉树遍历的非递归算法
1.中序下第一个结点Firstnode(最左侧结点)
2.中序下的后继结点Nextnode
2.算法实现
4.树,森林
1.树的存储结构
1.双亲表示法
1.定义: 连续空间存储,每个结点增设一个伪指针,指示双亲在数组中位置,根结点下标为0,其伪指针为-1
2.特点: 可以很快得到双亲,但求孩子要遍历整个结构
2.孩子表示法
1.定义: 将每个结点的孩子用单链表连成线性结构
2.特点: 求孩子很方便,求双亲不方便
3.孩子兄弟表示法(左孩子右兄弟)
1.定义: 左指针指向第一个孩子,右指针指向第一个兄弟,二叉链表作为存储结构
2.优点: 方便实现树转化为二叉树,易于查找孩子
3.缺点: 查找双亲麻烦,若增设parent指向双亲,会方便
2.树,森林与二叉树的转换
1.树转换为二叉树
左指针指向第一个孩子,右指针指向第一个兄弟,根没有兄弟,二叉树没有右子树
2.森林转换为二叉树
每棵二叉树的根依次作为上一颗二叉树的右子树
3.二叉树转换为森林(唯一的)
1.二叉树的根及左子树作为第一棵树的二叉树形态,再转换为树(右孩子变为兄弟)
2.根的右子树及其左孩子作为第二棵树,右孩子作为第三棵树,反复下去
3.树和森林的遍历
1.树的先根遍历
先访问根,再从左到右遍历每棵子树,与相应二叉树的先根遍历相同
2.树的后根遍历
从左到右遍历每棵子树,再访问根,与相应二叉树的中根遍历相同
3.先序遍历森林
与二叉树先根遍历同
4.中序遍历森林
与二叉树中根遍历同
4.树的应用--并查集
1.3种操作
1.Union(S,Root1,Root2): 合并两个子集合,将根Root2连接到根Root1下
S[Root2]=Root1
2.Find(S,x): 查找包含x的树的根,直到找到负数为止
while(s[x]>=0) x=S[x]; return x;
3.Inital(s): 集合S中每个元素初始化为只有单元素的子集合(所有元素赋值为-1)
2.存储结构: 树的双亲表示法,根结点下标为子集合名,根结点的双亲结点为负数,大小为子集合结点数量
5.树与二叉树的应用
1.二叉排序树(二叉查找树 BST)
1.定义
1.左子树上所有结点的关键字小于根结点
2.右子树上所有结点的关键字大于根结点
3.左右子树又各是一颗二叉排序树
中序遍历可得到递增有序数列
2.查找
1.非递归实现,递归简单但效率低
3.插入
1.插入的新结点一定是某个叶结点(只有树为空的时候才会插入)
4.构造
1.即使插入元素相同,顺序不同时,构造的BST也不同
5.删除
1.叶结点: 直接删除
2.i只有一棵左/右子树: 让i的子树成为i父结点的子树,替代i位置
3.i有左右两棵子树: 令i的中序直接后继/前驱代替i,再删去直接后继/前驱,转换为1,2情况
6.查找效率分析
1.平均查找长度ASL=(每层个数*对应层数)/总个数
2.最坏情况: 类似有序单链表O(n)
3.最好情况: 平衡二叉树O(㏒₂n)
4.查找过程: 与二分查找类似,但二分查找的判定树唯一
2.平衡二叉树(AVL树)
1.定义
1.平衡二叉树: 任一结点的左右子树的高度差的绝对值不超过1
2.平衡因子: 结点左右子树的高度差 -1,0,1
2.插入(先插入再调整)
1.每次调整的对象都是最小不平衡子树
2.LL平衡旋转(右单旋转)
0.A是最小不平衡子树的根结点,一定找清楚A
1.原因: A的左孩子B的左子树L上插入了新结点(可左可右),A为根的子树失去了平衡
2.方法
1.将A的左孩子B向右上旋转代替A成为根结点
2.A向右下旋转成为B的右子树的根结点
3.B的原右子树作为A的左子树
3.RR平衡旋转(左单旋转)
4.LR平衡旋转(先左后右双旋转)
1.原因: A的左孩子B的右子树c上插入了新结点(可左可右),A为根的子树失去了平衡
2.方法
1.将A的左孩子B的右子树的根结点c向左上旋转提升到B结点的位置
2.再把该c结点向右上旋转提升到A结点的位置
5.RL平衡旋转(先右后左双旋转)
3.查找
1.含有n个结点的平衡二叉树最大深度为O(㏒₂n),平衡查找长度为O(㏒₂n)
3.哈夫曼树和哈夫曼编码
1.定义
1.该结点的带权路径长度(WPL)
根结点到任意结点的路径长度(边数)与该结点上权值的乘积
2.树的带权路径长度
所有叶节点的带权路径长度之和
3.哈夫曼树(最优二叉树)
带权路径长度最小的二叉树
2.构造
1.构造过程
1.选取权值最小的两个结点构造一个新结点,权值为两个结点之和
2.再选取剩下的权值最小的结点,与新结点构造,重复过程
2.特点
1.初始结点都为叶结点,权值越小到根结点的路径长度越大
2.新建n-1个结点,一共2n-1个结点
3.不存在度为1的结点
3.哈弗曼编码
1.固定长度编码
对每个字符用同样长度的二进制表示
2.可变长度编码
对不同字符用不等长的二进制位表示
3.前缀编码
没有一个编码是另一个编码的前缀
4.哈弗曼编码过程
从根结点到该字符的路径上边标记的序列,0转向左孩子,1转向右孩子
第五章 图
1.图的基本概念
1.图的定义
0.G=(V,E),V(G):顶点的有限非空集 E(G):边集合 |V|:顶点个数(图的阶) |E|:边的条数
0.1 注意: 线性表可为空表,树可为空树,但图不可为空图: 顶点集一定非空,边集可空
1.有向图
<v,w>:从v到w的弧(v邻接到w/w邻接自v) v:弧尾 w:弧头
2.无向图
(v,w)=(w,v)
3.简单图
不存在重复边,不存在顶点到自身的边
4.多重图
存在重复边,存在顶点到自身的边
5.完全图(简单完全图)
1.无向完全图: 任意两个顶点之间都存在边,n(n-1)/2条
2.有向完全图: 任意两个顶点存在方向相反的两条弧,n(n-1)条
6.子图
生成子图: 顶点集相同的子图
7.连通,连通图,连通分量(无向图)
1.极大连通子图(连通分量): 连通子图包含所有的边,不一定包含所有顶点(不一定是连通图)
2.极小连通子图: 保持图连通又要使得边数最小的子图(可为一个单独顶点)
极小,极大相对于边
8.强连通图,强连通分量(有向图)
9.生成树,生成森林
1.连通图的生成树; 包含全部顶点的一个极小连通子图(n个顶点有n-1条边)
2.非连通图中,连通分量的生成树构成了非连通图的生成森林
10.顶点的度,入度,出度
1.顶点的度: 以该顶点为一个端点的边的数目
1.结点的度
一个结点的子结点个数
2.无向图中: 全部顶点的度之和=边数*2
3.有向图中: 顶点的度=入度+出度,全部顶点入度之和=出度之和=边数
11.边的权,网
1.带权图(网): 边上带有权的图
12.稠密图,稀疏图
13.路径,路径长度,回路
1.回路/环: 第一个顶点和最后一个顶点相同的路径
14.简单路径,简单回路
1.简单路径: 顶点不重复出现的路径
2.简单回路: 除第一个顶点和最后一个顶点,其余顶点不重复出现的回路
15.距离
1.v到w的最短路径若存在为距离,不存在记为无穷
16.有向树
1.一个顶点的入度为0,其余顶点的入度均为1的有向图
2.图的存储及基本操作
1.邻接矩阵法(顺序)
1.定义
1.一个一维数组存储顶点信息,一个二维数组存储边信息
2.特点
1.无向图/有向图: 第i行非零元素的个数为第i个顶点的度/出度
2.容易确定是否存在边,不易确定有多少边
3.稠密图适合用邻接矩阵
4.Aⁿ[i][j]: 顶点i到顶点j的长度为n的路径的数目
2.邻接表法(链接)
1.定义
1.结合顺序和链式存储,每个顶点i建立一个单链表
2.顶点表: 顶点域(data)+指向第一条邻接表的指针(firstarc)
3.边表: 邻接点域(adjvex)+指向下一条邻接表的指针域(nextarc)
2.特点
1.无向图: 存储空间O(|V|+2|E|) 有向图:O(|V|+|E|)
2.稀疏图用邻接表法节省空间
3.十字链表(有向图)
1.定义: 有向图的一种链式存储
2.结构
1.弧结点(ArcNode): 5个域
1.尾域(tailvex),头域(headvex): 指示弧尾和弧头
2.链域hlink,tlink: 指示弧头/弧尾相同的下一条弧
<v,w>:从v到w的弧(v邻接到w/w邻接自v) v:弧尾 w:弧头
3.info域: 弧的相关信息
2.顶点指针(VNode): 3个域
1.data域: 顶点的数据信息(顶点名称)
2.firstin域,firstout域: 以该顶点为弧头/弧尾的第一个结点
3.注意: 顶点结点是顺序存储的
3.特点
1.既容易找到vi为尾的弧,又容易找到vi为头的弧,容易求顶点出度/入度
2.表示不唯一,但确定一个图
4.邻接多重表(无向图)
1.定义: 无向图的另一种链式存储
2.结构
1.每条边用一个结点表示
1.mark标志域: 该条边是否被搜索过
2.ivex,jvex: 该边依附的两个顶点在图中位置
3.ilink,jlink: 指向下一条依附于顶点ivex/jvex的边
4.info: 各种信息的指针域
2.顶点用一个结点表示
1.data域: 顶点的相关信息
2.firstedge域: 第一条依附于该顶点的边
3.特点
1.依附于同一顶点的边串联在同一链表中,每个边结点同时链接在两个链表中
2.每条边只有一个结点
5.图的基本操作
1.独立于图的存储结构,不同存储方式有不同性能
2.具体操作
3.图的遍历
1.广度优先搜索(BFS)
1.定义
类似于二叉树的层次遍历算法,优先考虑最早发现的结点
2.思想
1.首先访问起始顶点v
2.依次访问v的所有未访问过的邻接顶点
3.再从这些顶点出发,访问它们所有未被访问过的结点
3.算法描述
1.分层查找,前进一步访问一批结点,不像深度优先有往回退情况,不是递归
2.借助 队列+辅助标记数组(顶点是否被访问)
3.算法实现
4.性能分析
1.空间复杂度: O(|V|)
借助辅助队列,顶点都入队一次
2.时间复杂度
1.邻接表:O(|V|+|E|)
2.邻接矩阵:O(|V|²)
遍历图的实质: 对每个顶点查找其邻接点的过程
5.BFS求解单源最短路径问题
5.广度优先生成树
1.定义: 广度遍历过程中,得到的一颗遍历树
2.特点: 邻接矩阵中唯一,邻接表中不唯一
DFS也一样
2.深度优先搜索(DFS)
1.定义
类似于树的先序遍历,优先考虑最后发现的结点
2.思想
1.首先访问起始顶点v
2.访问v的未访问过的任一邻接顶点w
3.再访问w的未访问过的任一邻接顶点w2
4.重复下去,直到不能继续向下访问,依次退回到最近被访问的顶点
3.算法描述
1.从一个顶点开始,采用递归形式
2.算法实现
4.性能分析
1.空间复杂度: O(|V|)
借助递归工作栈
2.时间复杂度
1.邻接表:O(|V|+|E|)
2.邻接矩阵:O(|V|²)
5.深度优先生成树/森林(非连通图)
3.图的遍历与图的连通性
1.无向图
1.连通的: 一次遍历访问所有顶点
2.非连通: 一次遍历访问连通分量的所有顶点
2.有向图
1.若初始顶点到每个顶点都有路径,能访问所有顶点,否则不能
3.算法中添加了第二个for循环,再选取初始点
第一个for循环初始化顶点为FLASE
4.无向图: 调用BFS或DFS次数=图的连通分量数
4.图的应用
1.最小生成树(MST)
1.定义
边的权值之和最小的生成树
2.特点
1.树形不唯一,边的权值之和唯一
2.边数=顶点数-1
3.通用思想
当T未形成生成树,找到一条最小代价边,加入T后不会产生回路
4.两种算法
1.Prim算法(普里姆)
1.思想(从顶点扩展)
1.初始化: 先任选一个顶点作为初始顶点
2.循环(直到包含所有顶点): 再选择这个顶点的邻边中权值最小的边且不会构成回路
3.再选择这两个顶点的邻边中权值最小的边且不会构成回路
2.特点
1.时间复杂度: O(|V|²),不依赖于|E|,适合边稠密的图
2.Kruskal算法(克鲁斯卡尔)
1.思想(权值递增)
1.初始化: 先包含所有的顶点,没有边
2.循环(直到成为一棵树): 按权值递增的顺序选择边且不构成回路,直到包含n-1条边
2.特点
1.采用堆存放边集合,时间复杂度O(|E|log|E|),适合边稀疏而顶点较多的图
2.最短路径
1.Dijkstra算法求单源最短路径
1.辅助变量
1.集合S: 记录已求得的最短路径的顶点,初值为0
2.dist[]: 记录从源点v0到其他各顶点当前(不断更新)的最短路径长度,初值为arcs[v0][i]
3.path[]: path[i]为源点到i最短路径的前驱结点,可根据其值追溯到v0到vi的最短路径
2.思想
1.初始化: 集合S为{0},dist[]为初始顶点0到各个顶点的距离,没有为无穷 path[]中初始顶点0为-1(一直不变),0到其他点有距离为0,没有为无穷
2.在dist[]中选剩下值最小的点j,若dist[j]+arcs[j][k]<dist[k],则更新dist[k] 在集合S中加入此点,若更新了dist[k],则令path[k]=j
3.再在集合S中剩下的点中重复操作,直到S包含所有点
3.特点
1.单源时间复杂度为O(|V|²),所有结点对为O(|V|³)
2.边上带有负权值时,算法不适用
2.Floyd算法求各顶点间最短路径
1.思想
1.递推产生一个n阶方阵序列,从A﹣¹开始到Aⁿ﹣¹
矩阵上标加括号
2.初始时: 若任意两个顶点存在边,权值作为最短路径,不存在为无穷
3.以后逐步在原路径中加入顶点k(k从0到n-1)作为中间顶点,若路径减少,则替换原路径
4.A(k)[i][j]: 从顶点i到顶点j,中间结点的序号不大于k的最短路径的长度
2.特点
1.时间复杂度: O(|V|³)
2.允许带负权值的边,不允许包含负权值的边组成回路
3.适用于带权无向图,视为有往返二重边的有向图
3.拓扑排序
1.有向无环图(DAG图)
有向图中不存在环
2.顶点表示活动的网络(AOV网)
DAG图表示一个工程,顶点表示活动,有向边<vi,vj>表示活动i必须先于活动j
3.拓扑排序(DAG图中)
1.定义
1.每个顶点出现且只出现一次
2.若A在B前面,则不存在从B到A的路径
2.实现方法
1.从DAG图中选择一个没有前驱的顶点并输出
2.删除该顶点和所有以它为起点的有向边
3.重复1,2,直到图为空/不存在无前驱的结点(图中必有环)
3.特点
1.时间复杂度O(|V|+|E|)
输出顶点同时删除边
4.注意
1.工程可以从入度为0的顶点开始
2.一个顶点有多个直接后继,结果通常不唯一
3.邻接矩阵为三角矩阵,存在拓扑排序,反之不一定.可按照排序结果重新安排顶点序号,此时邻接矩阵为三角矩阵
4.关键路径
1.用边表示活动的网络(AOE网)
1.定义
顶点表示事件,有向边表示活动,权值表示开销(时间)
2.两个性质
1.顶点代表的事件发生后,从顶点出发的各有向边代表的活动才能开始
2.只有进去某一顶点的所有有向边代表的活动都结束,顶点代表的事件才发生
2.几个概念
1.开始顶点(源点): 仅有一个入度为0的顶点,整个工程的开始
2.结束顶点(汇点): 仅有一个出度为0的顶点,整个工程的结束
3.关键路径: 具有最大路径长度的路径
4.关键活动: 关键路径上的活动
5.最短时间: 关键路径的长度
3.几个参量
1.事件vk的最早发生时间Ve(k)
1.定义: 顶点V到Vk的最长路径长度,决定所有从Vk开始的活动最早开工时间
2.求法: 从源点开始往后加上权值,取不同路径的最大值
所有活动完成,事件才能开始,取最大值
2.事件vk的最迟发生时间Vl(k)
1.定义: 不推迟整个工程完成的情况下,该时间最迟发生时间
2.求法: Vl(汇点)=Ve(汇点),从汇点往前依次减去权值,取不同路径最小值
取最小值才能保证不会拖延整个工程的时间
3.活动ai的最早发生时间e(i)
1.定义: 该活动的起点所表示事件最早发生时间
2.求法: <Vk,Vj>表示活动ai,则e(i)=Ve(k)
4.活动ai的最迟发生时间l(i)
1.定义: 该活动的终点所表示的事件的最迟发生时间与该活动所需要时间之差
2.求法: <Vk,Vj>表示活动ai,l(i)=Vl(j)-Weight(Vk,Vj)
5.活动的差额d(i)=l(i)-e(i)
4.关键路径
所有活动的差额d()=0的活动构成关键路径
第六章 查找
1.查找的基本概念
1.查找表(查找结构): 用于查找的数据集合
2.适合静态查找表: 顺序查找,折半查找,散列查找
3.适合动态查找表: 二叉排序树,散列查找,二叉平衡树和B树都是二叉排序树的改进
4.平均查找长度(ASL)
2.顺序查找和折半查找
1.顺序查找(线性查找)
1.一般线性表的顺序查找
1.算法特点
1.引入哨兵(数组第一个元素),从后往前查找,不必判断数组是否会越界,提高程序效率
2.优缺点
1.缺点: n较大时,效率低
2.优点: 对数据元素的存储没有要求,对有序性也没有要求
3.性能
1.ASL成功=(n+1)/2
2.ASL失败=n+1
加一个哨兵
2.有序表的顺序查找
1.判定树: 圆形结点为存在结点,矩形结点为失败结点(区间),n个成功必有n+1个失败结点
2.到达失败结点的查找长度=它上面的一个圆形结点所在层数
3.仅ASL失败不一样=(1+2+...+n+n)/n+1
最后两个失败结点在同一层次上,都为n
2.折半查找(二分查找)
1.算法特点
1.循环条件: low≤high 确保最终都指向同一个值,否则会少查找一个数
2.mid=(low+high)/2 相当于取下界
2.性能
1.时间复杂度: O(log₂n)
2.ASL: 每层层数*每层结点数/总结点数,n层有2ⁿ﹣¹个结点
3.分块查找(索引顺序查找)
1.算法特点
1.吸收顺序查找和折半查找各自优点,有动态结构,适于快速查找
2.思想
1.分为若干子块,块内可以无序,块之间有序
2.第一块中最大关键字<第二块中所有记录,以此类推
3.建立一个索引表,含有各块最大关键字和各块第一个元素的地址,按关键字有序排列
3.查找过程
1.在索引表确定所在的块,可顺序/折半查找
2.在块内顺序查找
4.性能
ASL=索引表ASL+块内ASL
题目总结
1.易错
1.折半查找的快体现在一般情况下,特殊情况,顺序查找可能更快
2.折半查找和二叉排序树的时间性能
1.折半查找用二叉树判定树衡量,ASL始终为O(log₂n)
2.二叉排序树与数据的输入顺序有关,最坏为O(n)
3.折半查找时,中间值取下界
2.公式
1.二叉判定树的高度: ┎log₂(n+1)┒或┕log₂n┙+1
1.是一棵平衡二叉树,高度最多相差为1,还是二叉排序树
2.不成功结点的比较次数(相差不超过1)/最多比较次数
3.结点总数n=2^h-1
2.n个记录的索引顺序表最理想的块长:
都顺序查找,块长为b,索引表ASL=(n/b+1)/2,块内ASL=(b+1)/2,相加用基本不等式
3.顺序查找ASL=(n+1)/2,索引查找ASL=索引表ASL+块内ASL
3.题型
1.判断一棵树是否为折半查找判定树
取最后进行比较的结点(树的中间位置),判断取上下界是否一致(也可先从根结点判断上下界)
2.直接在有序表中采用类似分块查找的思想:W252
块内的查找长度每段都不同
4.知识点
1.k分查找法: 成功与失败的时间复杂度O(logk(n))
n个结点的k叉树的深度为┕logk(n)┙+1
2.查找概率不同的情况下,采用顺序查找的最有效方式
按查找概率的降序排列
3.B树和B+树
1.B树及其基本操作
1.定义
0.B树(所有结点平衡因子为0的多路平衡查找树),孩子结点数最大值为B树的阶(m)
1.每个结点最多m棵子树(最多m-1个关键字)
2.若根结点不是终端结点,至少有两棵子树,1个关键字
3.除根结点外所有非叶结点最少┎m/2┒棵子树,最少┎m/2┒-1个关键字
4.所有非叶结点结构
1.关键字递增排列
2.左子树所有数<对应关键字,右子树所有数>对应关键字
5.所有叶结点在同一层次上,不带信息(外部结点/失败结点)
2.B树的高度
1.最小高度
每个结点最多m棵子树,m-1个关键字
h≥logm(n+1) n≤(m-1)(1+m+m²+...+m^(h-1))=m^h-1
2.最大高度
第一层最少一个结点,第二层最少2个结点,第三层最少2┎m/2┒,..,第h+1层最少2┎m/2┒^(h-1)个结点
第h+1层为叶结点(失败结点),个数为n+1(区间个数),n个关键字有n-1个失败结点
n+1≥2┎m/2┒^(h-1)
3.B树的查找
与二叉查找树类似
4.B树的插入
1.定位: 一定插入在最低层的某个非叶结点内
2.插入
1.每个非失败结点的关键字个数在[┎m/2┒-1,m-1]内
2.插入后关键字个数<m,直接插入; >m-1,对结点分裂
3.分裂方法
1.将插入key后的原结点从中间位置┎m/2┒分为两部分
2.中间位置┎m/2┒的结点插入到父结点中,左右两部分作为左右子树
3.若导致父结点也超过上限,继续分裂,直至到根结点为止,B树高度+1
5.B树的删除
1.在终端结点
1.直接删除关键字
关键字个数>┎m/2┒-1
2.兄弟够借
1.关键字个数=┎m/2┒-1,且相邻的右(左)兄弟结点的关键字>┎m/2┒
2.父子换位法: 父结点中的一个进入被删结点,兄弟结点中的一个进入父结点
3.兄弟不够借(合并法)
1.关键字个数=┎m/2┒-1,且相邻的右(左)兄弟结点的关键字=┎m/2┒-1
2.合并法: 将父结点中的一个与兄弟结点中的一个合并代替被删结点,父结点关键字少一个
3.若父结点为根结点且减少到0,直接删除根结点,合并后的新结点成为根
4.父结点不是根结点且减少到┎m/2┒-2,再与它的兄弟进行调整或合并(够借先借)
2.不在终端结点
1.若左子树关键字个数>┎m/2┒-1,用k的前驱结点(左子树最右侧结点)代替k,再递归删除k
2.若右子树关键字个数>┎m/2┒-1,用k的后继结点(右子树最左侧结点)代替k,再递归删除k
3.若左右子树关键字个数=┎m/2┒-1,直接将两个子树合并,直接删除k
2.B+树的基本概念
1.定义
1.每个分支结点最多m棵子树(子结点)
2.非叶根节点最少有两个子树,除根结点外所有非叶结点最少┎m/2┒棵子树
3.结点的子树个数=关键字个数
B树中: 结点的子树个数=关键字个数+1
4.所有叶结点包含全部关键字(顺序排列)及相应记录的指针,相邻叶结点按大小相互链接起来
5.所有分支结点(可视为索引的索引)仅包含它的各个子结点中关键字的最大值及指向子结点的指针
2.特点
1.两个头指针: 一个指向根结点,一个指向关键字最小的叶结点
2.两种查找运算: 从最小关键字顺序查找/从根结点多路查找
3.注意: 查找时,非叶结点等于给定值并不终止,继续向下查找,直到叶结点为止 无论查找成功与否,都是一条从根结点到叶结点的路径
题目总结
1.易错
1.当结点中关键字数≠子树数目,必然不是B+树
2.除根结点外所有非叶结点最少┎m/2┒棵子树,最少┎m/2┒-1个关键字
特别注意根结点: 至少有两棵子树,1个关键字
3.B树插入后分裂时,只要根结点不分裂,高度就不会+1
2.公式
1.最小高度: h≥logm(n+1)
2.最大高度: n+1≥2┎m/2┒^(h-1)
3.知识点
1.对于3阶B树: 结点数最少时类似于满二叉树,结点数最多时类似于满三叉树
总结点数=m^h-1
2.B+树用于文件索引/数据库索引
4.散列表
1.散列表的基本概念
1.散列函数
把关键字映射为对应的地址的函数,记为Hash(key)=addr(可为数组下标/索引/内存地址)
2.冲突
两个或以上的不同关键字映射到同一地址
3.同义词
发生碰撞的不同的关键字
4.散列表
根据关键字直接进行访问的数据结构,理想情况为O(1)
2.散列函数的构造方法
0.注意点
1.定义域必须包含全部的关键字,值域依赖于散列表的大小/地址范围
2.地址应等概率,均匀分布
3.函数尽量简单,在较短时间内计算出
1.直接定址法
1.函数: H(key)=a*key+b
2.特点: 不会产生冲突,适合关键字分布基本连续
2.除留余数法
1.函数: H(key)=key%p
2.P的选取: 不大于m(散列表长)但最接近或等于m的质数p
3.数字分析法
1.选取数码分布较为均匀的若干位作为散列地址
2.特点: 适用于已知关键字的集合
4.平方取中法
1.平方值的中间几位作为散列地址
2.适用于每位取值都不够均匀/均小于散列地址所需要的位数
5.折叠法
1.关键字分割成位数相同的几部分,取叠加和作为散列地址
2.适用于位数很多且每位上数字分布大致均匀
3.处理冲突的方法
1.开放地址法
0.定义
1.空闲地址既向同义词开放,又向非同义词开放
2.递推公式:Hi=[H(key)+di]%m ,di:增量序列
1.线性探测法
1.定义: di=0,1,2,...,m-1
2.特点: 造成大量元素在相邻的散列地址上聚集,降低查找效率
2.平方探测法(二次探测法)
1.定义: di=0²,1²,-1²,2²,-2²,...,k²,-k²
2.特点
1.优点: 可以避免出现堆积问题
2.缺点: 只能探测一半单元
3.再散列法(双散列法)
1.定义: di=Hash₂(key), Hi=[H(key)+i*Hash₂(key)]%m
i是冲突次数
2.特点
1.利用第二个散列函数计算地址增量
2.最多m-1次能探测所有位置
4.伪随机序列法
1.定义: di=伪随机序列
5.注意
1.不能随便物理删除已有元素,会截断其他相同散列地址元素的查找地址
2.可做删除标记,逻辑删除
3.副作用: 多次删除后,表面上散列表很满,其实还有很多位置未用,需定期维护
2.拉链法(链接法)
1.定义: 所有同义词存储在一个线性链表中,由散列地址唯一标识
2.适用于经常插入和删除的情况,可直接物理删除
4.散列查找及性能分析
1.查找过程
0.初始化: Addr=Hash(key)
1.检测Addr上是否有记录
1.无记录,查找失败
2.有记录,相等查找成功;不等执行2
2.用给定的处理冲突方法计算"下一个散列地址",把Addr置为此地址,转入1
2.查找效率
1.取决于: 散列函数,处理冲突的方法,装填因子
2.装填因子(α): 定义一个表的装满程度
α=表中记录数n/散列表长度m
3.平均查找长度依赖于α,不直接依赖于n或m
题目总结
1.易错
1.K个同义词采用线性探测填入散列表,需要探测K(K+1)/2次
1+2+...+K
2.冲突产生的概率与装填因子的大小成正比
越满越容易冲突
3.不能用随机数函数构造散列函数,无法进行正常的查找
2.知识点
1.堆积产生的原因
同义词冲突的探查序列和非同义词之间不同的探查序列交织在一起
2.平均探测次数=平均查找长度
3.题型
1.ASL成功
查找次数=冲突次数+1
2.ASL失败
根据散列函数确定一共需要的查找的位置,对每个位置查找直到为空时结束,不为空时用相应的冲突处理方法再进行查找,为空时也需要比较一次
5.串
1.串的定义
1.空格串: 一个或多个空格组成,不是空串
2.线性表以单个元素作为操作对象,串以子串作为操作对象
2.串的存储结构
1.定长顺序存储表示
1.类似于线性表顺序存储,分配定长数组
2.截断: 超过预定义长度的串值会被舍去
2.堆分配存储表示
1.用malloc()和free()动态分配和删除
3.块链存储表示
1.类似线性表的链式存储,每个结点可放一个或多个字符
3.串的基本操作
1.最小操作子集(5个): 不可利用其它串操作实现
1.串赋值: StrAssigh
2.串比较: StrCompare
3.串连接: Concat
4.求串长: StrLength
5.求子串: SubString
4.串的匹配模式
1.定义: 子串的定位操作
2.思想
1.从主串的第pos个字符起,与模式串第一个字符比较
2.若相等,继续逐个比较后序字符
3.若不等,从主串的下一个字符起重新比较
3.效率
最坏时间复杂度: O(mn)
5.改进的模式匹配算法--KMP算法
1.字符串的前后缀和部分匹配值
1.前缀: 除最后一个字符外,所有头部子串(只能从第一个位置开始)
2.后缀: 除第一个字符外,所有尾部子串(只能从最后一个位置开始)
3.部分匹配值: 前缀和后缀最长相等的前后缀长度
2.效率
1.时间复杂度: O(m+n)
3.求解next数组(手动)
1.next数组值=最长相同前后缀长度+1
2.串本身不能作为前后缀
3.通常next[1]=0(视具体题目而定,若为-1,还是用0计算,最后所有数-1)
4.next[i]中第i个不匹配时,串长为i-1,不包括第i个元素
5.字符串较长时,可以只算前面几个,能得到答案即可
题目总结
1.知识点
1.KMP算法最大优点
主串不回溯,i指针不动,j=next[j]
2.题型
1.求解next[]的快速方式,设当前求next[n],next[n-1]=m
0.默认next[1]=0,next[2]=1
下标也可从0开始,数值也可从-1开始
1.串有n-1个字符,若前m个字符与后m个字符相同,则next[n]=m+1,转3
2.前m个与后m个不同时,若m=1,则next[n]=1,转3. 否则,令m=m-1,再比较前m-1个与后m-1个,相同转1,不同继续2
3.结束操作
2.KMP的匹配过程
当next[]的值从0开始时,下标编号从1开始,不匹配时,i指针不动,j=next[j]
3.易错
1.考试时一定分清next[]值从0开始,还是从1
第七章 排序
1.排序的基本概念
1.排序的定义
1.算法的稳定性不能衡量一个算法的优劣
2.内部排序: 元素全部放在内存中
3.外部排序: 不断地在内存,外存之间移动
题目总结
1.易错
1.在顺序表上实现的排序算法在链表上有可能不能实现
2.对同一线性表使用不同的排序方法进行排序,得到的排序结果可能不同
2.公式
1.对任意n个关键字排序的比较次数最少为┍log₂(n!)┑
2.插入排序
1.直接插入排序
1.思想
1.假定第一个元素已经排序好
2.从第二个元素开始,依次与前面进行比较,不满足立即交换,就地排序,反复把已经排好的向后移
2.特点
1.将A[0]复制为哨兵,可避免下标越界,便于赋值,不用申请临时变量
2.边比较边移动
3.性能分析
1.时间效率
1.最好情况: O(n)
每次只需要比较一次,不用移动
2.最坏情况: O(n²)
2.适用性
顺序,链式都适合,大部分算法只适合顺序
4.算法实现
2.折半插入排序
1.思想
1.先折半查找出元素的待插入位置
2.统一移动待插入位置之后的所有元素
2.特点
1.仅减少了比较元素的次数,移动的次数并未改变
2.比较次数与初始状态无关,只与n有关
3.性能分析
1.时间复杂度: O(n²)
只与移动的次数有关(两层for循环),与比较的次数无关,比较只是在for循环中完成的操作
2.稳定
4.算法实现
3.希尔排序(缩小增量排序)
1.思想
1.先取步长为n/2,划分为若干组,在每组内用直接插入排序
2.再将步长缩小一半,继续操作,直至步长为1
2.特点
1.目前尚未求得最好的增量序列,无法计算时间复杂度
3.性能分析
1.时间效率
最坏情况: O(n²)
2.不稳定
相同的关键字可能被划分到不同的子表中
4.算法实现
题目总结
1.易错
1.折半插入排序时间复杂度为O(n²)
3.交换排序
1.冒泡排序
1.思想
1.从最后一个元素开始,两两相邻进行比较,若为逆序,则交换它们
2.一趟冒泡,结果将最小的元素交换到第一个位置
3.下一趟冒泡,前一趟确定的最小元素不再参与,待排序列减少一个元素
4.每趟冒泡的结果是序列中最小元素放到最终位置,最多n-1此完成
2.特点
1.冒泡排序产生的有序子序列一定是全局有序的,不同于直接插入排序
3.性能分析
1.时间效率
1.最好情况: O(n)
冒泡后,标志仍然为Flase,没有元素交换,直接跳出循环
4.算法实现
2.快速排序(分治法)
1.思想
1.每次取当前表中第一个元素作为基准pivot(枢轴值)对表进行划分
2.i指向第一个元素(基准),j指向最后一个元素
3.先从j开始,从后往前找到第一个比基准小的元素,j指向此元素位置,用此元素替换掉i所指元素
4.再从i开始,从前往后找到第一个比基准大的元素,i指向此元素位置,用此元素替换掉j所指元素
5.再次从j开始,循环往复,直到i与j接触停止,将基准值放到接触位置,将序列划分为两块,前面小于基准值,后面大于基准值
6.分别取两个子序列的第一个元素作为基准值,重复操作
2.特点
1.不产生有序子序列,但每趟排序后会将一个元素放到最终位置上
2.越有序算法效率越低,越无序算法效率越高
3.性能分析
1.空间效率
平均情况: O(㏒₂n)
算法是递归的,需要用一个递归工作栈,大小为递归树的深度
最坏情况: O(n)
2.时间效率
1.最坏情况: O(n²)
序列基本有序或逆序
2.最好情况(平均情况): O(n㏒₂n)
4.不稳定
存在交换关键字
4.提高效率的方法
1.递归划分得到的子序列较小时,不再递归,改用直接插入排序进行后续工作
2.尽量选取可以将数据中分的基准
1.头,尾,中间,选取三个元素,再取中间值
2.随机选取基准,确保最坏情况不会发生
5.算法实现
题目总结
1.易错
1.一组数采用快速排序时,速度最快的情形
每次选择的基准都把表等分为长度相近的两个子表
2.在求可能的序列时,一定要两种次序都考虑(从大到小,从小到大)
2.知识点
1.快速排序最适宜采用顺序存储
3.算法思想
1.把所有奇数移动到所有偶数前边的算法(时间/空间最少)
1.先从前往后找到一个偶数L(i),再从后往前找到一个奇数L(j),将二者交换,重复到i>j
2.基于快排,一次遍历,时间O(n),空间O(1)
2.荷兰国旗问题: 仅由红,白,蓝组成的条块序列,使得条块按红,白,蓝顺序排列,时间为O(n)
1.顺序扫描,将红色交换到最前面,蓝色交换到最后面
2.三个指针,一个工作指针,一个指向头,一个指向尾,switch语句
注: 正数,负数,0排序同样方法
3.在数组L[1...n]中找到第k小的元素
0.可利用直接排序取k个元素O(nlog₂n)以上/采用小顶堆O(n+klog₂n)
1.更精彩,基于快排,时间为O(n)
2.选择一个基准,和快排一样的划分操作,分为L[1...m-1]和L[m+1...n],L(m)为基准
3.讨论m与k关系
1.m=k,基准就是要找的元素
2.m<k,所找元素在后半部分,继续递归地在后半部分找第k-m小的元素
3.m>k,所找元素在前半部分,继续递归地在前半部分找第k小的元素
4.n个数构成集合A,分为两个不相交子集A1,A2,个数为n1,n2,元素之和为s1,s2, 满足|n1-n2|最小且|s1-s2|最大
1.将最小的n/2个元素放在A1中,其余放在A2中,仿照快排,划分后对基准位置i分别处理
2.若i=n/2,分组完成
3.若i<n/2,基准及之前所有元素放A1,继续对i之后的元素划分
4.若i>n/2,基准及之后所有元素放A2,继续对i之前的元素划分
5.无须对全部元素排序,平均时间O(n),空间O(1)
4.选择排序
1.简单选择排序
1.思想
1.第一趟找到最小的元素,将此元素与第一个元素交换
1.第二趟找到最小的元素,将此元素与第二个元素交换,重复n-1次
2.特点
1.每一趟排序可以确定一个元素的最终位置
3.性能分析
1.时间复杂度始终O(n²)
元素移动次数很少为O(n),但比较次数与初始状态无关,始终为n(n-1)/2
2.不稳定
找到最小元素后直接交换,会破坏原有的顺序
4.算法实现
2.堆排序
1.思想
1.堆的定义
大根堆(完全二叉树): 最大元素为根结点,任一非根节点的值小于等于其双亲节点的值
1.1 堆的操作
1.删除堆顶元素
先将最后一个元素与堆顶元素交换,删除后,将堆顶元素向下调整成为堆
2.插入操作
先将新结点放在堆末端,再向上调整为堆
2.构造初始堆(大根堆)
1.从倒数第二层的最后一个结点依次往前进行判断
2.只看该结点的子树(不看父结点),若子树中有结点大于根结点,找到较大的,与根结点交换
3.若交换后破坏了下一级的堆,继续用上述方法调整下一级的堆,直到根结点为止
3.将堆顶元素(最大值)输出,同时将最后一个元素放入堆顶,将堆顶向下调整成为大顶堆
4.重复操作,直到堆剩下一个元素为止
2.性能分析
1.时间复杂度始终为O(n㏒₂n)
建堆时间为O(n),之后有n-1次向下调整,每次为O(h)
2.不稳定
建堆时会打乱原有顺序
3.空间复杂度: O(1)
仅使用常数个辅助单元
3.算法实现
选择排序都不稳定
题目总结
1.经典题目
1.每个元素有两个数据项k1,k2,排序:先看k1,小的在前;k1值相同,再看k2,小的在前
1.首先确定排序顺序,必然先对k2先排序,后排k1,保证先看k1
2.对k2排序无稳定性要求,尽量选效率高的算法
3.对k1排序必须用稳定的算法,否则可能会打乱已排好的k2
2.题型
1.堆插入/删除元素时的比较次数
2.只想得到第k(k≥5)个最小元素之前的部分排序序列
1.可用冒泡/简单选择/堆排序
2.前两个时间为kn
3.堆排序,建初始堆不超过4n,取k个元素时间为klog₂n,共4n+klog₂n,k≥5时,最优
3.判断一个数据序列是否为小根堆
1.需要分两种情况,序列为奇数和偶数
2.为奇数时: 没有单分支结点,可直接用父结点与两个孩子结点比较
3.为偶数时: 有一个单分支结点,单独判断,其他结点正常
5.归并排序和基数排序
1.归并排序
1.思想
1.先划分为n个长度为1的子表,两两归并
2.得到长度为2的子表再次两两归并,重复下去
2.性能分析
1.空间复杂度: O(n)
需要将归并的数据复制到辅助数组中,长度为n
2.时间复杂度: O(n㏒₂n)
每趟归并为O(n),共进行㏒₂n趟,分割子序列与初始状态无关
3.算法实现
2.基数排序
1.思想
1.最低位优先(LSD)
1.先根据个位数的大小依次将序列放入10个队列(0~9 上进下出)中
2.从第一个队列依次将其中所有元素出队,直到第10个队列
3.再根据十位数重复操作入队,出队,百位数也是同样操作
4.当最高位也出队时,序列就有序了
2.最高位优先(MSD)
1.先根据最高位的大小依次将序列放入10个队列(0~9 上进下出)中
2.将其中个数不为1的队列递归排序,按照次高位的大小再次放入10个队列中
3.直到所有队列中只有1个数,递归结束,收集各队列返回上一层
2.特点
1.不基于比较,采用多关键字排序思想
3.性能分析(LSD)
1.空间复杂度: O(r)
r为数的基(多少进制)
2.时间复杂度: O(d(n+r))
进行d趟分配和收集,一趟分配为O(n),一趟收集为O(r),与初始状态无关
3.稳定
分配和收集都按照顺序进行
题目总结
1.易错
1.对10TB的数据文件进行排序,使用什么方法
归并排序,文件太大,不能用内部排序,只能用外部排序,通常采用归并排序
2.知识点
1.将两个各有n个元素的有序表合并为一个有序表
1.最少比较次数为: n
2.最多比较次数为: 2n-1
3.题型
1.基数排序做了多少次排序码比较
做了几次分配和收集
6.各种内部排序算法的比较及应用
1.内部排序算法的比较
2.内部排序算法的应用(小结)
1.算法的选取
1.n较小
1.记录本身小
直接插入(比较次数更少)/简单选择(交换次数更少)
2.记录本身大
简单选择
1.1 中等规模(n<1000)
希尔排序 是很好的选择
2.n很大(选时间少的)
1.不稳定
1.快速排序: 最好的方法,随机分布时,平均时间最短
2.堆排序: 需要的辅助空间少于快速排序
2.稳定
归并排序: 但空间复杂度最高
3.n很大,关键字位数较少且可分解
基数排序较好
4.序列基本有序
直接插入排序(效率最高/比较次数最少)/冒泡排序
最好情况时间复杂度为O(n)
5.若干次排序后的结果
1.每次将一个元素放在最终位置
简单选择/堆排序,冒泡排序/快速排序(交换)
只有快速排序的元素不是最值元素,其他3个都是最值(最前/最后)
2.前几个元素有序,但不是最终位置
直接插入
3.可能最后一趟开始之前,所有元素都不在最终位置
直接插入
4.不能保证一定有元素在最终位置
直接插入/希尔排序/归并排序
6.几个最
1.就平均性能而言,目前最好的内部排序算法
快速排序
2.占用空间最多的算法
归并排序O(n)
快速排序在最坏情况也为O(n)
3.基本有序时最快的是
直接插入排序
4.最好情况可达到线性时间
直接插入/冒泡排序
7.0 算法时间与初始序列无关
选择排序(简单选择/堆排序)/归并排序/基数排序
7.1 排序趟数与初始序列无关
直接插入/简单选择都为n-1趟,基数排序固定为d趟
7.2 移动次数与初始序列无关
基数排序
基数排序什么都与初始序列无关
8.查找效率最低的数据结构
堆: 主要为排序设计,查找时是无序的
9.若将顺序存储更换为链式存储,时间效率会降低
希尔排序/堆排序(利用了顺序表的随机访问特性)
2.对归并排序的改进
和直接插入排序结合: 先利用直接插入求得较长的有序子序列,然后两两归并,仍然稳定
3.基于比较的算法
可以用二叉树描述比较判定过程,因此至少需要O(n㏒₂n)的时间
4.记录本身信息量较大
利用链表作为存储结构,可避免耗费大量时间移动记录
7.外部排序
1.外部排序的基本概念
1.减少外存读写次数
增大归并路数/减少归并段个数
2.增大归并路数(m)
败者树
使用后,比较次数与m无关,可以增大m来减少归并树的高度
3.减少归并段个数
置换-选择排序
增大归并段长度来减少归并段个数
4.组织长度不等的归并段的归并顺序
最佳归并树
哈夫曼树推广到m叉树
2.外部排序的方法(归并排序)
1.两个相对独立阶段
1.得到归并段/顺串
根据内存缓冲区大小,将n个记录分为若干记录,依次读入内存用内部排序排序,再写回外存
2.对归并段进行逐趟归并,使归并段由小到大,直至完成
2.归并趟数S=树的高度=┌㏒mⁿ┐
n-初始归并段个数 m-归并路数 ┌┐-向上取整
3.多路平衡归并与败者树
1.内部归并时间随m的增长而增长
1.抵消了因增大m而减少外存访问次数所得的效益
2.不能使用普通的内部归并排序
2.败者树(完全二叉树)
1.叶结点
当前参加比较的记录
2.内部结点
记忆左右子树中失败者的序号,让胜者继续向上比较,直到根结点
3.根结点
当前的最小数/最大数的序号,不是数值本身(胜者)
3.利用败者树得到最小值序号后,取出最小值数,在其位置加入下一个关键字,继续比较,构造败者树
4.使用败者树后,比较次数与m无关,可以增大m来减少归并树的高度
5.m并不是越大越好
m增大,输入缓冲区增加,其容量减少,内外存交换数据的次数增大
4.置换-选择排序(生成最长初始归并段)
1.思想
1.先取工作区最小的数a
2.再取大于a的数中最小的归入本归并段,比a小的归入下一归并段
5.最佳归并树
1.定义(推广的m叉哈夫曼树)
1.叶结点
参加归并的一个初始归并段
2.叶结点的权值
初始归并段中的记录数
3.叶结点到根结点的路径长度
归并趟数
4.非叶结点
归并生成的新归并段
5.归并树的带权路径长度
总读记录数
所有叶结点经过的边数*权值
2.思想
让记录少的归并段最先归并,记录多的最晚归并
3.最佳归并树是严格m叉树
1.若最后缺项,不足以构成严格m叉树,添加长度为0的"虚段"最先归并
2.空归并段个数=m-u-1
u=(n0-1)%(m-1)
n0-度为0的结点数(初始归并段个数) m-m叉树
题目总结
1.题型
1.共有n个记录,工作区能容纳a个记录,做m路平衡归并
1.初始归并段个数r=n/a, 归并趟数s=┌㏒m(r)┐
2.5个初始归并段,每个有20个记录,用5路平衡归并, 不用败者树和使用败者树的比较次数
1.不用败者树: 5个记录选出最小的要比较4次,共100个记录,要做99次选最小的操作,4*99=396
2.使用败者树: 败者树高度h=3,每次选一个最小的,比较次数不超过h,共100次,不超过300次
3.做m路平衡归并,输入输出缓冲区的个数
1.正常情况(串行操作): 需要m个输入缓冲区,1个输出缓冲区
2.输入/输出并行操作: 2m个输入缓冲区,2个输出缓冲区
4.同时可用的输入/输出文件的总数不超过15个
最多可做14路归并
主题