导图社区 数据结构
- 44
- 0
- 0
- 举报
数据结构
关于考研408数据结构的思维导图，主要内容有c语言、chap1绪论、chap2线性表、chap3栈和队列、chap4串等。
编辑于2022-12-25 01:24:45 北京市- 考研数据结构
- 相似推荐
- 大纲
数据结构
c语言
malloc
# include <stdib.h> void *malloc(size_t size)
功能
size -- 内存块的大小，以字节为单位
该函数返回一个指针 ，指向已分配大小的内存。如果请求失败，则返回 NULL
memset
# include <string.h> void *memset(void *str, int c, size_t n)
功能
复制字符 c（一个无符号字符）到参数 str 所指向的字符串的前 n 个字符
回一个指向存储区 str 的指针
memcpy
# include <string.h> void *memcpy(void *str1, const void *str2, size_t n)
功能
从存储区 str2 复制 n 个字节到存储区 str1
返回一个指向目标存储区 str1 的指针
c++
输入输出流
输入
char name[50]; cin >> name;
输出
char str[] = "Hello C++"; cout << "Value of str is : " << str << endl;
endl：换行
执行结果
引用类型可作为函数参数
void A(LinkList &L)
与指针传入类似，可直接改变传入参数原本的值
static
隐藏与隔离的作用
全局变量仅限于在本源文件中使用，在其他源文件中不能引用，也就是说限制其作用域只在定义该变量的源文件内有效，而在同一源程序的其他源文件中不能使用。这时，就可以通过在全局变量之前加上关键字 static 来实现，使全局变量被定义成为一个静态全局变量
减少全局变量(有风险)的使用
static修饰局部变量,改变了该变量的生命周期,使该变量的生命周期与整个程序(而不是局部子程序的代码块)的生命周期相同,程序结束时才销毁.
静态局部变量与全局变量的主要区别就在于可见性，静态局部变量只在其被声明的代码块中是可见的
chap1 绪论
数据
能输入到计算机并被计算机程序处理的符号的总称。
数据对象(文件)
相同性质数据元素的集合
数据元素(记录)
数据的基本单位
可由若干数据项组成
数据项
不可分割的最小单位
数据结构
数据元素+关系
概念
相互之间存在一种或多种特定关系的数据元素的集合。
三要素
逻辑结构
独立于存储结构
非线性结构
集合
树型结构
图状结构或网状结构
线性结构
线性表
栈
易错点：栈是一种抽象数据类型，是一种运算受限的线性表，并非存储结构
队列
存储结构（物理结构）
顺序存储
链式存储
结点内存储单元地址连续
索引存储
元素信息+索引表
例：文件目录项=文件名+inode
散列存储(哈希Hash存储)
根据元素关键字直接计算出该元素存储地址
若散列函数不好，则可能出现存储单元冲突
数据的运算
定义
针对逻辑结构，指出运算的功能
实现
数据类型
例：int\char\bool\float\double等
概念
分类
原子类型
其值不可再分的数据类型
结构类型
其值可分解为若干成分（分量）的数据类型
抽象数据类型
概念
Abstract Data Type(ADT)是指一个数学模型以及定义在该模型上的一组操作
分类
固定聚合类型
值由确定的数目的成分按某种结构组成
可变聚合类型
值成分数目不确定
多形数据类型
值的成分不确定
定义四要素
定义格式类似于C语言结构体
ADT类型名
数据对象
数据关系
基本操作
算法(数据的运算)
算法设计取决于逻辑结构，实现依赖于存储结构
概念
五个特性
效率的度量
时间复杂度
T(n)=O(f(n))
表示执行时间与f(n)成正比
加法规则
O(f(n))+O(g(n))=O(max(f(n),g(n)))
乘法规则
O(f(n))*O(g(n))=O(f(n),g(n))
空间复杂度
S(n)=O(f(n))
原地工作
额外空间相对于输入数据量来说是常数
额外空间：程序除需要存储空间寄存本身所用的指令、常数、变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些为实现计算机所需信息的辅助空间。
chap2 线性表
算法题
定义
具有相同数据类型的n(n>=0，有限)个数据元素的有限序列
顺序存储
顺序表
用一组地址连续的存储单元依次存储线性表的数据元素
特点
随机存取
逻辑顺序与物理顺序相同
例：数组
动态分配
malloc
（指针类型）malloc(size)
动态分配是在堆上开辟一片空间用以存储数据，使用过后需释放(free)
引申概念：内存泄露
malloc后没有free导致堆空间被占满
静态分配
函数内
在栈中存放，函数运行完自动释放
静态局部变量
静态全局变量
全局变量
静态存储区
数据类型描述：data[],length
基本操作实现
插入
时间复杂度
删除
时间复杂度
按值查找
时间复杂度
有序查找
二分法
常见问题算法
数组元素循环左移
reverse(0,i-1);rever(i,n-1);reverse(0,n-1);
两有序数列A,B合并求中位数
二分法分别求A,B中位数a,b;若a=b，a=b=mid;若a>b或a<b，舍弃两边保留中间部分继续循环求中位数。
数组A[n]中未出现的最小正整数
Nmin=1~n+1;Tag数组B记录出现过的值
链式存储
概念
结点、数据域、指针域
头指针
链表有头结点时指向头结点，无头结点时指向第一结点
头结点
第一个结点前附设的结点，指针域指向第一个结点
注意区分
特点
非随机存储
单链表
结点中只有指向后继节点的指针
基本操作实现
建立
头插法
头结点
尾插法
尾指针
时间复杂度
按序号查找结点值
时间复杂度
按值查找结点
时间复杂度
插入结点
时间复杂度
删除结点
时间复杂度
法一
查找删除位置的前驱结点再删除
先让指针p指向待删除结点，断链后free掉
法二
查找待删除位置的结点，将其后继结点的值赋予其自身，再删除其后继节点
不保证待删结点p一定有后继结点，如：p为尾结点
求表长
时间复杂度
数据类型描述：data,*next
注意：结构体中可以定义指向自身结构体类型的指针，但必须在typedef struct后加上结构体名
常见问题算法
双链表
数据类型描述：data,*next,*prior
基本操作实现
插入结点
删除结点
循环链表
最后一个结点的指针域指向头结点
循环单链表
判空条件
头结点指针是否等于头指针
循环双链表
判空条件
头结点的prior域和next域相等且等于头指针
静态链表
用数组描述的链表
常用算法
头插、尾插、逆置法、归并法、双指针法
存储结构的选取
存储
难以估计线性表的长度或存储规模时，宜采用链表
运算
频繁插入、删除，宜采用链表；按序号访问，宜顺序表
环境
顺序表更宜实现，任何高级语言中都有数组类型
chap3 栈和队列
栈
定义
只允许在一端进行插入和删除的线性表
特点
LIFO
数学性质
n个不同元素进栈，出栈元素不同排列个数为
分类
顺序栈
栈顶指针指向栈顶元素，栈空时S.top=-1
数据类型描述：data[],top
链栈
单链表，无头结点，插入删除都在链表表头进行
数据类型描述：data,*next
选用情况
数据元素变动较大
多个队列
避免出现存储分配不合理的“溢出”问题(如银行窗口排队)
共享栈
判满：top1-top0=1
判空：top0=-1;top1=maxsize
应用
数制转换
原理
例子
括号匹配
左括号入栈，遇到右括号弹出左括号或非法
表达式求值(树)
一般数学表达式=中缀表达式，转化为后缀表达式(已包含运算符优先级信息)后，遇到操作数则入栈，遇到运算符则弹出栈顶两个操作数并将运算结果入栈，循环该过程
后缀表达式
中缀表达式手动转换为后缀表达式方法
画树(操作数不要重复)
1.按运算符优先级对所有运算单位加括号。2.把运算符移动到对应的括号后面。3.去除所有括号
手算
左优先原则:只要左边的运算符能先计算，就优先算左边的
步骤
1| 确定中缀表达式中各个运算符的运算顺序
2| 选择下一个运算符，按照 「左操作数右操作数运算符」的方式组合成一个新的操作数
3| 如果还有运算符没被处理，就继续②
机算
1| 遇到操作数。直接加入后缀表达式。
2| 遇到界限符。遇到“(”直接入栈;遇到“)”则依次弹出栈内运算符并加入后缀表达式，直到弹出“(”为止。注意:“(”不加入后缀表达式。
3| 遇到运算符。依次弹出栈中"("之后的优先级高于或等于当前运算符的所有运算符(没有则不弹)，并加入后缀表达式，若碰到“(”或栈空则停止。之后再把当前运算符入栈。
先弹出的运算符先生效
后缀表达式的计算(机算)
步骤
1| 从左往右扫描下一个元素，直到处理完所有元素
2| 若扫描到操作数则压入栈，并回到①;否则执行③
3| 若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到①
先出栈的是右操作数
前缀表达式
中缀表达式手动转换为前缀表达式方法
手算
右优先
前缀表达式的计算
从右往左扫描
先出栈的是左操作数
递归调用
递归模型要素
递归表达式(递归体)
边界条件(递归出口)
用栈将递归算法转换成非递归算法
时间复杂度
队列
定义
只允许在一端进行插入(队头)，另一端进行删除(队尾)的线性表
数据类型描述：data[],front,rear
特点
FIFO
分类
循环队列
顺序存储
出队
入队
队空条件
队满条件
队列中元素个数
链式队列
选用情况
数据元素变动较大
多个队列
避免出现存储分配不合理的“溢出”问题
双端队列
输入受限的双端队列(仅一端输入)
注意输出序列是否有夹在中间的数被输出的情况
限入队列4先出表明1，2，3已全入，所以输出前队列起始状态为4，3，2，1 输出4后变为3，2，1，此时不可能输出2
输出受限的双端队列(仅一端输出)
不管输入从哪边进，输出序列较小的数一定在中间
应用
逐行或逐层的问题
例：层序遍历二叉树
主机与外部设备之间速度不匹配的问题
例：缓冲区
打印机打印，缓冲区先进先出
多用户引起的资源竞争问题
例：进程的就绪队列、银行排队窗口
数组
一维
多维
二维数组下标与一维数组下标的映射
压缩存储、稀疏矩阵
对称矩阵
只存放主对角线和下三角区的元素
下标映射当i>=j时与下三角矩阵一致，否则将表达式中i,j对调
三角矩阵
下三角
上三角
计算出从第一个元素到A[x][y]共有多少个元素，注意数组下标都是从0开始的
存储方式
三元组(三元数组)
(行标，列标，值)
十字链表
三对角矩阵
chap4 串
大纲中属于查找算法中的一个小节
概念
主串、子串、串长
前缀、后缀、部分匹配值
{ababa}
前缀A={a,ab,aba,abab}
除最后一个字符外，字符串的所有头部子串
后缀B={a,ba,aba,baba}
除第一个字符外，字符串的所有尾部子串
部分匹配值(Partial Match)表=00123
字符串前n个字符的前后缀交集中最长子串的长度
'0':{a}，A∩B为空；
'0':{ab},A∩B为空；
'1':{aba},A∩B={a}；
'2':{abab},A∩B={ab}；
'3':{ababa},A∩B={aba}
存储结构
定长顺序存储
堆分配存储
块链存储
模式匹配算法
暴力匹配O(mn)
主串指针回溯
KMP算法(O(m+n))
O(m+n) 求next数组O(m) 模式匹配过程O(n)
主串指针i不回溯
next数组求解
部分匹配值右移一位，第一个元素-1填充，再将数组整体值全+1就得到了next数组
next[j]值含义：当模式串第j个字符匹配失败时，主串指针i不变，模式串指针j应该指向什么位置(从模式串的哪个位置继续匹配)
next[1]=0,next[2]=1固定
任何模式串第1个字符不匹配时，只能匹配下一子串，所以next[1]=0;(此时程序的逻辑是让j指针先等于next[j]的值，然后i++，j++)
主串字符与模式串第2个字符不匹配时，用主串当前字符(指针i指向的字符)尝试匹配模式串第1个字符，所以next[2]=1;
next[x]:第x个字符匹配失败，在匹配失败字符前画一条分界线，将模式串后移到与主串字符对应上或完全跨过分界线为止，此时j指向模式串的第几个位置，next数组值就是多少
特殊情况：j=0时,i++,j++
S：主串，T：模式串
KMP算法的进一步改进
只优化next数组变为nextval数组
当char[next[j]]=char[j]时,将nextval[j]=next[next[j]]
使用next数组时，若模式串第j个字符不匹配，则下次从模式串第next[j]个字符开始匹配
chap5 数组和广义表
chap6 树和二叉树
基本术语
性质
结点数-边数=1
二叉树
性质
ni为度为i的结点个数
特殊二叉树
满二叉树
完全二叉树
比满二叉树少了最底层、最右边的结点
性质
最后一个分支结点编号
i>1时，双亲结点编号为
叶结点个数为
叶子结点只可能在层次最大的两层出现
若有度为1的结点，则只可能有一个
层序编号，第一个叶子结点(或只有左孩子的结点)之后全为叶子结点
n为奇数，每个分支结点都有左右孩子；n为偶数，编号最大的分支结点无右孩子
n个结点的完全二叉树高度为
结点层次
2i≤n，i的左孩子编号为2i；2i+1≤n，i的右孩子编号为2i+1
存储结构
顺序
链式
结点描述：*lchild,data,*rchild
操作
遍历
算法题
先序(根)
中序(根)
后序(根)
递归
递归的过程(什么时候在哪个递归层，何时进入下一层，何时退出)看数据结构视频
层序
队列辅助
步骤
1| 若树非空，则根节点入队
2| 若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队
3| 重复②直到队列为空
要唯一确定一棵二叉树，至少需要两个序列，且必须有中序序列
先序+中序确定二叉树方法
由先序序列第一个值为根结点，在中序序列找到该值，该值左侧为左子树，右侧为右子树
先序序列第二个值为左子树根结点，在中序的左侧序列中找到该根结点，将左子树进一步划分，直至划分完毕再对中序的右侧序列继续以该方式划分
先序+后序确定祖先关系
当两结点先序序列为XY且后序序列为YX时，可以确定X是Y的祖先
线索二叉树
结点描述：*lchild,*ltag,*rtag,data,*rchild
tag==0:child指针指向孩子；tag==:child指针指向线索
中/先/后序遍历的改造
关注何时建立前驱线索，何时建立后继线索
当前结点没有左孩子时建立前驱线索 当前结点a无右孩子，在遍历下一结点时建立Pre(也就是a)的后继线索
中序线索化二叉树
后继
P的右子树中最左下结点
前驱
P的左子树中最右下结点
在中序遍历过程中的visit()函数中处理结点
先序线索化二叉树
易错点
死循环问题
后序线索化二叉树
易错点
最后一个结点的处理
应用
哈夫曼树
定义
带权路径长度最小的二叉树
带权路径长度
构造
每次从合成后存在的结点中选出两个最小的进行构造
哈夫曼编码
固定长度编码
数据通信中，对每个字符用相等长度的二进制位标志
可变长度编码
允许用不同长度二进制位表示字符
使用频率高的字符用短编码，频率低用长编码
前缀编码
没有一个编码是另一个编码的前缀
连续二进制位表示的多个字符不会译码出错
总长度最短的前缀编码——哈夫曼编码
哈夫曼树不唯一，但WPL相同且为最优
叶结点权值为该字符出现的频度
0表示转向左(或右)孩子，1表示转向右(或左)孩子
树中一定没有度为1的结点
树和森林
概念
存储结构
双亲表示法
静态链表(数组)
孩子表示法
孩子兄弟表示法
操作
树与二叉树的转换
森林与二叉树转换
第一棵树根结点作森林根结点，其他树作为其兄弟结点
特点
左子树上全为第一棵树的结点，右子树上为其他树
左孩子，右兄弟
遍历
应用
并查集
存储结构
树的双亲表示
操作
Union(S,Root1,Root2)
集合S中的子集合Root2并入子集合Root1，两子集合无交集
find(S,x)
查找S中单元素x所在的子集合，并返回该集合名字
Initial(S)
将集合S中每个元素都初始化为只有一个单元素的子集合
n个独立元素多次Union合并为一个集合
n个元素两两合并共需n-1次合并，每次合并都需要先用Find操作找到根结点(复杂度O(n)) 总时间复杂度n*(n-1)
优化
尽可能让树变矮
对Union
根结点的绝对值表示树的结点总数
小树合并到大树
构造的树高不超过
Find(S,x)时间复杂度
n个独立元素多次Union合并为一个集合
先find才能union
对find
压缩路径(使查找路径变短)
n个独立元素多次Union合并为一个集合
chap7 图
基本术语
无向图
性质
记某顶点V的度为TD(v)，(n个顶点，e条边)
某无向图为连通图，且有n个顶点，则最少有n-1条边
某无向图为非连通图，n个顶点，则边的数量最多为：
有向图
性质
记某顶点V的入度为ID(v)，出度为OD(v)(n个顶点，e条边)
某有向图为强连通图，且有n个顶点，则最少有n条边
路径--顶点v到顶点vg之间的一条路径是指顶点序列 回路一-第一个顶点和最后一个顶点相同的路径称为回路或环 简单路径--在路径序列中，顶点不重复出现的路径称为简单路径。 简单回路一-除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。 路径长度一一路径上边的数目 点到点的距离一一从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。 若从u到v根本不存在路径，则记该距离为无穷 无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的 有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的
存储结构
邻接矩阵法
数据结构类型
一维数组表示顶点信息，二维数组(邻接矩阵)存储边的信息
邻接矩阵
带权图无路径时用∞，无权图无路径时用0
有向图邻接矩阵对角线以下元素全为0->不存在回路=有拓扑序列
特点
有向图行出列入，第i行(列)非0元素个数=顶点i的出(入)度
无向图邻接矩阵为对称矩阵
确定两顶点间是否有边O(1),确定图中有多少边O(n)
邻接表法
数据结构类型
表示方式不唯一
如：可以把无向图中顶点1的边链表从1->2->5,改为1->5->2
顶点表(顺序索引)+边表(链式)
邻接多重表
无向图
十字链表
有向图
结构与邻接多重表类似
图的遍历
深度优先Depth-First-Search(类似先序遍历，增加访问标记数组)
空间复杂度
时间复杂度
分析访问顶点+边
邻接矩阵
访问顶点V，查找所有顶点的邻接点V²，V+V²~V²
邻接表
V是访问顶点，E是访问顶点的所有边
生成树/序列
邻接矩阵唯一，生成的树唯一，序列唯一；邻接表不唯一，所以生成的树不唯一，序列不唯一
广度优先Breadth-First-Search(类似层序遍历，增加访问标记数组）
时间复杂度
不要分析代码，分析访问顶点+边
邻接矩阵
访问顶点V，查找所有顶点的邻接点V²，V+V²~V²
邻接表
V是访问顶点，E是访问顶点的所有边
空间复杂度
生成树/序列
邻接矩阵唯一，生成的树唯一，序列唯一；邻接表不唯一，所以生成的树不唯一，序列不唯一
分析遍历序列，注意邻接表存储方式
按邻接表每个结点链接的链表顺序访问，不是按图访问
对无向图，BFS/DFS函数调用次数=连通分量数
对有向强连通图，BFS/DFS函数调用次数=1
应用
最小生成树(带权连通无向，可能有多个)
Prim算法
每次选择顶点，适用于边稠密图
从某顶点开始构建生成树，每次将代价最小的新顶点纳入生成树
时间复杂度
共需n-1轮，每一轮遍历两个数组即2n，总次数2n*(n-1)~n²
lowcast数组值与最小路径中path数组值不一致，path需将路径值累加，lowcast不用
Kruskal算法
每次选择边，适用于边稀疏图
每次选则一条权值最小的边，让两个顶点连通(已连通就不选)
时间复杂度
并查集
最短路径
BFS算法(单源(出发点相同)最短）
无权
基于BFS遍历，改变visit时的操作(修改最短路径长度d[]和前驱结点path[])
Dijkstra算法(单源最短)
不适用与有负权值的带权图
带负权值的图往往在实际应用中涉及能源消耗及补充的情况。 如电动车从v0到v2消耗7个电，从v0到v1消耗10个电，但在V1~V2间有充电站可以补充5个电
带权、无权
时间复杂度
处理n-1轮 邻接矩阵，访问dist=n,查找某结点邻接结点n；实际(n-1)*2n~n² 邻接表，访问dist=n,查找结点邻接结点e；实际(n-1)*n+e~n²
思想
源点v0，计算到各个顶点路径长度，每次选出一个从v0出发的最短路径连接的顶点并标记，在该顶点基础上更新路径长度，循环上述过程直至所有顶点都被标记
Floyd算法(每对顶点间的最短)
动态规划思想，不能解决带有负权回路的图
动态规划：将每个问题的求解分为多个阶段 负权回路：
带权、无权
每次新加入一个可中转的顶点Vi(按序号加入)，在计算该情况下到达全部顶点的最短路径后再加入一个新的可中转顶点，循环该过程
时间复杂度
n轮，每轮遍历两个矩阵2n²，共2n^3~n^3
空间复杂度
2个n*n矩阵=2n²~n²
path数组中-1代表无中转点，其他值则为有中转情况下的上一中转点 通过path矩阵以递归的方式找到完整路径
有向无环图
描述表达式
构造树不唯一
优先级相同的运算符可以交换运算次序，所以构造树不唯一
AOV(Activity On Vertex)网(无环)
用顶点表示活动的网，有向无权
工程图
拓扑序列
有回路的图不存在拓扑序列
每个顶点出现且只出现一次
若顶点A在序列中排在顶点B之前，则图中不存在从顶点B到顶点A的路径
拓扑排序(找到做事的先后顺序)
解决工程可按何种顺序进行
1| 从AOV网中选择一个没有前驱(入度为0)的顶点并输出
2| 删除该顶点和以它为起点的有向边
3| 重复步骤1,2直到AOV为空或网中不存在无前驱的顶点为止
4| 时间复杂度
邻接矩阵
访问顶点V，查找所有顶点的邻接点V²，V+V²~V²
邻接表
V是访问顶点，E是访问顶点的所有边
逆拓扑排序
每次选择出度为0的顶点
实现
拓扑
DFS算法
AOE(Activity On Edge)网
带活动开销的工程图
相关概念
带权有向，顶点表示事件，有向边表示活动，权值表示完成该活动开销。仅有一个入度为0(源点)和出度为0(汇点)的顶点
关键路径和关键活动
解决工程最短时间问题
所有路径中，最大长度的路径为关键路径，关键路径上的活动为关键活动
特性
关键活动耗时增加/缩短，会延长/缩短整个工期时间
缩短到一定程度，关键路径可变为非关键路径
可有多条关键路径，只缩短其中一条关键路径上关键活动的时间并不能加快整个工程工期，只有加快全部关键路径上的，或那些被包括在所有关键路径上的关键活动才能缩短工期
求解方法
1| 事件最早发生时间ve(i)
决定了所有从顶点v开始的活动能开工的最早时间
2| 事件最迟发生时间vl(i)
不推迟整个工程完成的前提下，该事件最迟必须发生的时间
3| 活动最早开始时间e(i)
活动弧的起点(弧尾)所表示事件的最早发生时间
4| 活动最迟开始时间l(i)
活动弧的终点(弧头)所表示事件的最迟发生时间与该活动所需时间之差
5| 时间余量d(i)
d(i)=e(i)-l(i)
关键活动：d(i)=0
例：
chap8 动态存储管理
chap9 查找
概念
查找表(查找结构)
查找数据的集合
关键字
基于关键字的查找，查找结果应当唯一
静态查找表
无插入删除操作
顺序查找、折半查找、散列查找
动态查找表
需插入、删除
二叉排序树查找、散列查找
查找长度
一次查找运算中需要对比关键字的次数
平均查找长度Average Search Length
分别考虑查找成功/查找失败两种情况的时间复杂度
ASL数量级反应了查找算法的时间复杂度
线性结构
顺序(线性)查找
哨兵
无需判断i值是否越界
优化
判定树(有序表，被查概率相等)
被查概率不等
概率大的放在靠前位置
折半(二分)查找
有序的顺序表(数组)
链表不具有随机存取的特性
判定树
右子树结点数-左子树结点数=0或1
一定是平衡二叉树
只有最下面一层可能不满(完全二叉)
树高
时间复杂度
失败结点：n+1个
左子树结点数-右子树结点数=0或1
分块(索引顺序)查找
块内无序，块间有序
数据类型描述
算法过程
1| 在索引表中确定待查记录所属的分块(顺序或折半)
若索引表中不包含目标关键字，则折半查找最终停在low>high，并在low所指分块中查找
原因：折半查找停止的前一状态mid=low=high,
2| 块内顺序查找
效率分析
长度为n的查找表均匀的分为b块，每块s个元素
顺序查找索引表
拓展：动态查找表的数据结构？
树形结构
二叉排序树BST(Binary Search Tree)
特点
中序遍历二叉排序树，可以得到一个递增的有序序列
二叉排序树中删除再插入同一结点，得到的二叉排序树与原来的不一定相同
查找
x<root，在左子树查找，x>root，在右子树查找，循环上述过程直到x=root
两种实现方式(递归、非递归)
时间复杂度
查找成功/查找失败（加入空结点）平均查找长度
插入
(1)空，直接插入；(2)非空，k<root，插入到左子树，k>root，插入到右子树；循环(2)
删除
叶结点直接删，只有左子树或右子树，则用左子树或右子树替代；左右子树都有，则找到右子树中最小的结点替代原结点(即右子树最左下结点)，或左子树中最大的结点(即左子树最右下结点)
平衡二叉树
左右子树的高度差不超过1
结点数据中有平衡因子balance项
插入(算法题不考)
调整对象
最小不平衡子树
LL平衡旋转(右单)
左子树的左子树最高：右旋
RR平衡旋转(左单)
右子树的右子树最高：左旋
LR平衡旋转(先左后右)
左子树的右子树最高：LR旋
RL平衡旋转(先右后左)
右子树的左子树最高：RL旋
H,H+1表示子树的高度
平均查找长度=最大深度
时间复杂度
高度为h的平衡二叉树，结点总数最少为
删除
不平衡特性向上传导
按二叉排序树删除结点的原则删除；找到最小不平衡子树；调整；循环步骤2,3
红黑树(算法题不考)
红黑树插入删除结点的开销比平衡二叉树更小
特点
数据类型描述
每个结点是红色或黑色
相当于平衡二叉树的balance
根节点、叶子结点均为黑色
根叶黑
不存在两个相邻(父子)的红结点(兄弟结点不算相邻)
黑结点可以相邻
不红红
对每个结点，从该结点到任一结点的简单路径上，所含黑结点的数目相同
每个结点的黑高唯一
黑路同
相关概念
结点的黑高
从某结点出发(不含该结点)，到达任一空叶结点的简单路径上黑结点的总数
叶结点
又称失败结点、NULL结点、外部结点、空叶结点
性质
从根结点到最远叶结点的最长路径不大于到最近叶结点的最短路径的2倍
左右子树高度差不超过两倍
有n个内部结点的红黑树树高
黑高固定，内部结点至少有多少个？
内部结点全黑时为最少，且为满二叉树的形态(否则会违反黑路同)，即结点数最少为
插入
新结点是根：染黑；新结点非根：染红
插入处理方式和二叉排序树一样，插入后不满足红黑树要求，则需调整
只可能破坏"不红红"
调整方式
看插入结点叔结点的颜色
爷变新结点——把爷结点当作新插入的结点
删除
B树(多路平衡查找树)
绝对平衡
特点
左右子树高度相同
n阶B树=n叉查找树
结点内关键字递增
所有叶结点都在同一层上并且不带信息
非叶结点结构
K:结点关键字；P:指向子树根结点的指针
n个关键字的m阶B树高度
必有n+1个叶子结点
最小(每个结点满)
最大(每个结点分叉尽可能少)
插入
每次新插入的元素一定在最底层的终端结点中，用查找来确定插入位置
插入后若导致原结点关键字数超过上限，则从中间位置将其中的关键字分为两部分，左部分关键字放在原结点中，右部分关键字放到新结点，中间位置结点插入原结点的父结点(放到指向该结点的指针的右边位置)
中间位置
向上分裂
例子：4阶B树插入过程
删除
被删关键字在非终端结点，则用直接前驱(左子树最右下元素)或直接后继(右子树最左下元素)来替代被删除关键字
对非终端结点的删除操作必然可以转化为对终端结点的删除操作
删除关键字后被删结点关键字低于下限
兄弟够借
父结点给原结点，兄弟结点给父结点
兄弟不够借
不合法情况可能会向上传导
两兄弟以及父结点的一个关键字合并
树高为3，最后一层空页结点不算树高
B+树
为解决操作系统文件索引和数据库索引而产生
m阶
非叶根结点至少有2棵子树，其他每个分支结点子树的数量至少为
结点的子树个数与关键字个数相等
所有叶结点包含全部关键字以及指向相应记录的指针，叶结点中关键字按大小排序，相邻叶结点按大小顺序相互链接
支持顺序查找
分支结点中仅包含各个子结点中关键字的最大值及指向其子结点的指针
B+树查找必须到查到最底层才能确定结点是否存在，而B树可能在中间某层就找到了
因为B树每层都保存信息，但B+树只有叶结点保存信息
B+树分支结点的功能类似于操作系统中文件的索引项
典型应用：关系型数据库的索引，如MySQL
散列结构
散列表(Hash Table哈希表)
空间换时间
散列函数合理，散列表越长，冲突的概率越低
数据元素的关键字与其存储地址有映射关系
相关概念
同义词
不同关键字通过哈希函数映射到同一值
装填因子
表中记录的个数/散列表长度
会直接影响散列表的查找效率
查找长度
查找运算中，需要对比关键字的次数(不计算索引指针)
注意
查找失败
散列函数为mod(n)，查找失败的情况只会从0~n-1开始查找，即便数组长度为m>n,也不存在从位置n~m-1直接开始查找的情况
冲突
同义词会产生冲突
冲突越多，查找效率越低
处理冲突方法
拉链法(链地址法)
实际应用较多
JAVA hashmap
同义词放在同一个链表中
优化，链表中顺序排列关键词
开放定址法
对冲突的同义词，以某种规则找到其他空位放
线性探测法
容易堆积
空位置的判断要算一次比较
平均查找长度
查找成功
查找失败
平方探测法
散列表长度m必须是一个可以表示成4j+3的素数，才能探测到所有位置
数论
伪随机序列法
di是伪随机序列
删除元素
删除结点时不能简单的将被删结点的位置置空，否则会导致后序同义词无法被找到
增加一个删除标记
造成问题：散列表中看起来很满，但实际可能很空(很多元素都被标记已删除)
再散列法
使用多个散列函数，当原始散列函数冲突时，用下一个散列函数计算一个新地址，直到不再冲突为止
常见散列函数
散列表表长为m，p应取不大于m但最接近或等于m的质数
如：关键字全为偶数时，若p取4，8....等2的倍数则会导致奇数位置一直为空 但若关键字为连续的自然数，无固定规律，则可以不取质数
适用于关键字的分布基本连续的情况，若关键字不连续，则会导致空位较多，造成存储空间的浪费
如：学号
关键字为r进制数，而r个数码在各位上出现的频率不一定相同，可能在某些为分布均匀(每个数码出现频率基本相等)，而某些位不均匀，只有其中数码经常出现。此时选择数码分布比较均匀的几位作为散列地址
这种方法得到的散列地址与关键字的每位都有关系，具体取多少位看实际情况
应用：身份证号作为关键字设计散列函数
chap10 排序
概念
稳定性
关键字相同的元素排序后相对位置保持不变
内部排序
数据都在内存中
插入排序
直接插入排序
从头开始顺序对比每个元素大小确定插入位置
空间复杂度
时间复杂度
稳定性
稳定
适用性
顺序表、链表
折半插入排序
折半查找找到应该插入的位置(第一个大于关键字的值之前的位置，当关键字与表中值相等时，为保证稳定性，则应找到可能连续的最后一个相等的元素的右边位置)，再移动元素
空间复杂度
时间复杂度
稳定性
稳定
适用性
顺序表
希尔排序
先部分有序，再全局有序
初始增量d=n/2,一般每次将增量缩小一半
空间复杂度
时间复杂度
稳定性
不稳定
适用性
顺序表
最后一趟是直接插入排序
交换排序
关键字比较后对换
冒泡排序
特点
从后往前，或从前往后两两比较，若为逆序则交换，直到整个序列比较完为一趟排序
每趟都可以使一个元素移动到最终位置
某一趟排序未发生交换则已整体有序，可停止排序
时间复杂度
空间复杂度
稳定性
稳定
适用性
顺序表、链表
快速排序
性能最优，递归
特点
选择一个基准(枢轴)，每次处理将更小的元素换到基准左边，大的换到右边，一趟排序后该基准元素会移动到最终位置。再对左右两个子表以同样方式划分。
时间复杂度
最坏情况:初始序列有序
空间复杂度
算法表现取决于递归深度，若每次划分均匀，递归深度越低
稳定性
不稳定
优化
选头中尾三个位置的元素，取中间值作为枢轴元素
在序列中随机选取一个元素作为枢轴元素
一趟排序=一层
选择排序
简单选择排序
时间复杂度
空间复杂度
稳定性
不稳定
适用性
顺序表、链表
堆排序(算法题不考)
二叉树的层序存储
相关概念
大(小)根堆
根结点比左右孩子结点的值都大(小)
是一颗完全二叉树
算法思想(大根堆)
1. 根据序列层序遍历建立堆
2. 从最后一个非终端结点开始检查一遍所有非终端结点是否满足大根堆要求，不满足则将当前结点与更大的一个孩子结点互换。若元素互换破坏了原本已调整过的下一级的堆，则采用同样方法向下调整(小元素不断下坠)
3. 确定堆顶元素后，与堆中最后一个元素交换，并将该元素从待排序序列中去掉；循环处理剩余待排序序列
n-1趟
时间复杂度
排序
建堆
空间复杂度
稳定性
不稳定
适用性
顺序表
插入
放到表尾，与其父结点对比交换(上升)，直到无法上升为止
删除
被删元素用堆底元素代替，并让该元素不断下坠，直到无法下坠为止
对比关键字多少次？
归并排序
递归
需辅助数组
二路归并
二(k)路归并树形态上就是一棵倒立的二(k)叉树
时间复杂度
空间复杂度
稳定性
稳定
两个元素相等时，优先使用更靠前的
基数排序
不是基于比较的排序算法
将所有关键字的个、十、百等位上的数字依次排序
实现
r进制数设置r个队列，先处理权重低的位
分配
顺序扫描各个元素，若当前处理关键字位=x，则将元素插入Qx队尾
收集
将Qr-1~Q0各个队列中结点依次出队并链接
时间复杂度
一趟分配O(n),一趟收集O(r),共d趟(当前数据每一个有多少位)分配收集
空间复杂度
稳定性
稳定
适用情况
外部排序
文件较大内存一次放不下，需存在外存
需要关注读写磁盘的次数
多路归并排序
步骤
生成r个初始归并段
进行s趟k路归并
r个初始归并段，k路归并,归并趟数
k路归并
k个归并段的块读入输入缓冲区
归并排序选出几个最小记录暂存到输出缓冲区
注意
每当一个输入缓冲区空时，需立即将与之对应的归并段的下一块内容读入内存，再继续归并
缓冲区满时写出外存
每次向输入缓冲区读入两个块，排序完成后(缓冲区内缓冲区间均有序)全部输出到外存，得到第一个有序的归并段，再循环继续排第二组
优化
多路归并可以减少归并趟数，从而减少访存开销
缺点
需开辟k个输入缓冲区，内存开销增加
每挑选一个关键字需要比对关键字(k-1)次，内部归并所需时间增加
败者树可以减少k路归并时关键字的对比次数
减少初始归并段数r
生成初始归并段的内存工作区越大，初始归并段越长，r越少
置换-选择排序进一步减少初始归并段数量
内存工作区可容纳l个记录，初始归并段只能包含l个记录，若文件有n个记录，则初始归并段总数量r=n/l
时间开销
读写外存时间+内部排序时间+内部归并时间
概念
k路平衡归并
最多只能有k个归并段归并为1个
每趟归并中，若有m个归并段参与归并，则经过一趟处理得到新的归并段数量:
反例
败者树
减少关键字比对次数
倒二叉树
对k路归并，败者树构建完成后，选出最大(小)值需要对比关键字次数:
实现
叶子结点：k个归并段中当前参加比较的元素
k路归并设置一个长度为k的数组(完全二叉树层序存储)，数组中(非叶子结点)存储本次比较中败者所在的归并段号(索引)
置换-选择排序
减少初始归并段个数
置换选择：每次选择最小的元素置换出外存
最佳归并树
多叉哈夫曼树应用
计算出不同长度归并段归并的最佳次序
特点
每个初始归并段对应一个叶子结点
归并时磁盘IO次数=归并树的WPL*2
WPL：带权路径长度
初始归并段数量n,k路归并若无法构成严格k叉树，则需补充虚段
chap12 文件
必须会手写！