前言：自用，参考王道数据结构。过期末考试的别看了，我看完了才发现没用。（图太大发不出来，懒得发了）
数据结构
第一章绪论第二章线性表01定义值得注意的特性eg：L=（a1,a2,a3...,ai,ai+1,....an）都要是同种元素，例如全都是int类型数量要有限，数的完有先后次序ai的意思就是ai是线序表中的第i个元素（也叫位序）
?数据元素同类型
?有限
?有序
重要术语?表长、空表
?表头、表位
?前驱、后继
?数据元素的位序（从1开始）
02基本操作创销、增删改查（所有数据结构适用的记忆思路）判空、判长、打印输出（还可根据自己的实际需求增加其他基本操作）判断是否是空表求表长书P12
其他值得注意的点?理解什么时候要传入参数的应用“”
就是需要将数据带回来的时候使用的
?
?函数命名要有可读性
别整个a啥的名字到后面自己都看不懂
03存储/物理结构顺序表（顺序存储）用顺序存储方式来实现的线性表
?存储结构
?逻辑上相邻的而数据元素物理上也相邻
?实现方式
?静态分配
?使用静态数组实现
代码02Project1
?
?大小一旦确定就无法改变
?动态分配
代码02Project1
?使用动态数组实现
?L.data=(ElemType*)malloc(sizeof(ElemType)*size);
sizeof()判断元素有多少字节ElemType是什么类型的元素size顺序表最大长度
?
?顺序表存满时，可再用malloc动态拓展顺序表的最大容量
?需要将数据元素复制到新的存储区域，并用free函数释放原区域
?特点
?随机访问
?能在O（1）时间内找到第i个元素
?存储密度高
?拓展容量不方便
?插入、删除数据元素不方便
?基本操作
?插入
?Listlnsert(L,i,e)
?将元素e插入到L的第i个位置
?插入位置之后的元素都要后移
?
?时间复杂度
?最好O(1)、最坏O(n)、平均O(n)
?删除
?ListDlete(L,i,e)
?将L的第i元素删除，并用e返回
?删除位置之后的元素都要前移
?
?时间复杂度
?最好O(1)、最坏O(n)、平均O(n)
?代码要点
?代码中注意位序i和数组下表的区别
位序i=数组i-1
?算法要有健壮性，注意判断i的合法性
?跨考同学注意:移动元素时,从靠前的元素开始?还是从表尾元素开始?
删除是元素靠前的先开始移动，插入是表尾元素先开始移动
?分析代码，理解为什么有的参数需要加“”引用
?按位查找
?GetElem(L,i)
ElemTypeGetElem(SeqListL,inti){returnL.data[i-1];}
?获取表L中第i个位置的元素的值
?用数组下表即可得到第i个元素L.data[i-1]
?时间复杂度
?最好/最坏/平均时间复杂度都是O(1)
?按值查找
intLocateElem(SeqListL,ElemTypee){for(inti=0;iL.length;i++)if(L.data==e)returni+1;return0;}
?LocateElem(L,e)
?在顺序表L中查找第一个元素值等于e的元素，并返回其位序
?从第一个元素开始依次往后检索
?时间复杂度
?最好O(1):目标元素在第一个位置
?最坏O(n):目标元素在最后一个位置
?平均O(n):目标元素在每个位置的概率相同
链表（链式存储）?单链表
?用“链式存储（存储结构）实现了“线性结构”（逻辑结构）”
?一个结点储存一个数据元素
?各结点间的先后关系用一个指针表示
?用代码定义一个单链表
?
?两种实现
?不带头节点
?空表判断：L==NULL。写代码不方便
?带头节点
?空表判断：L-next==NULL。写代码不方便
?其他值得注意的点
?typedef关键字的用法
?“LinkList”等价于"LNode"前者强调这是链表，后者强调这是结点合适的地方使用合适的名字，代码可读性更高
?单链表的插入删除
参考06Project的代码
?插入
?按位序插入
?带头节点
?不带头节点
?指定节点的后插操作
?指定结点的前插操作
?删除
?按位序删除
?指定节点的删除
?单链表的查找
代码参考07Project
?按位查找
?注意与"顺序表"对比
?单链表不具备“随机访问”
?按值查找
?求单链表长度
?Key
?三种基本操作的时间复杂度都是O(n)
?如何写循环扫描各个节点的代码逻辑
?注意边界条件的处理
?单链表的建立
代码参考08Project
?尾插法
?带头节点
?不带头节点
?头插法
?带头节点
?不带头节点
?双链表
?初始化
?头结点的prior、next都指向NULL
?插入（后插）
?注意新插入结点、前驱节点、后驱结点的指针修改
?边界情况：新插入结点在最后一个位置，需特殊处理
?删除（后删）
?注意删除结点的前驱节点、后驱结点的指针修改
?边界情况：如果被删除结点是最后一个位置，需特殊处理
?遍历
?从一个给定结点开始，后向遍历、前向遍历的实现（循环的终止条件）
?链表不具备随机存储特性，查找操作只能通过顺序遍历实现
?循环链表
?循环单链表
?空表
?
?非空表
?
?循环双链表
?空表
?
?非空表
?
?代码问题
?如何判空
?如何判断结点p食肉是表尾/表头结点
?如何在表头、表中、表尾插入/删除一个结点
?静态链表
?什么是静态链表
?如何定义一个静态链表
?简述基本操作的实现
栈和队列栈定义?一种操作受限的线性表，只能在栈顶插入、删除
?特性：后进先出（LIFO）
?术语：栈顶、栈底、空栈
基本操作?创、销
?增、删（元素进栈、出栈，只能在栈顶操作）
?查（获得栈顶元素，但不删除）
?判空
顺序栈03Project1代码
顺序存储，用静态数组实现，并需要记录栈顶指针基本操作?创、增、删、查（都是O(1)时间复杂度）
两种实现?初始化时top=-1
?入栈
?S.data[++S.top]=x;
?出栈
?x=S.data[S.top--];
?获得栈顶元素
?x=S.data[S.top]
?栈空/栈满条件是？
?初始化时top=0
?入栈
?S.data[S.top++]=x;
?出栈
?x=S.data[--S.top];
?栈空/栈满条件是？
?获得栈顶元素
?x=S.data[S.top-1]
共享栈?两个栈共享同一片内存空间，两个栈从两边往中间增长
?初始化
?0号栈栈顶指针初始时top0=-1；1号栈栈顶指针初始时top1=MaxSize；
?栈满条件
?top0+1=top1；
链栈用链式存储方式实现的栈两种实现方式?带头结点
?不带头结点（推荐）
重要基本操作?创（初始化）
?增（进栈）
?删（出栈）
?查（获取栈顶元素）
?如何判空、判满？
队列定义?一种操作受限的线性表，只能在队尾插入、在队头删除
?特性：先进先出（FIFO）
?术语：队头、队尾、空队列、队头元素、队尾元素
用链式存储实现队列?带头节点
?不带头结点
基本操作?创、销
?增、删（入队、出队，只能在规定的一端进行）
?查（获得队头元素，但不删除）
?判空
?判满（不存在的情况）
顺序实现?实现思想
?用静态数组存放数据元素，设置队头/队尾（front/rear）指针
?循环队列：用模运算（取余）将存储空间在逻辑上变为“环状”
?Q.rear=(Q.real+1)%MaxSize;
?重要考点
?如何初始化、入队、出队
?如何判空、判满
?如何计算队列的长度
?分析思路
?确定front、rear指针的指向
?1.rear指向队尾元素后一个位置
?2.rear指向队尾元素
?确定判空判满的方法
?a.牺牲一个存储单元
?b.增加size变量记录队列长度
?c.增加tag=0/1用于标记最近的一次操作是出队/入队
?...
队列变种?双端队列
?允许从两端插入、两端删除的队列
?
?输出受限的双端队列
?允许从两端删除、从一端插入的队列
?
?输出受限的双端队列
?允许从两端插入、从一端删除的队列
?
?考点：队输出序列合法性的判断
栈的应用——表达式求值概念?运算符、操作数、界限符
三种表达式?中缀表达式
?运算符在操作数中间
?后缀表达式（逆波兰式）
?运算符在操作数后面
?前缀表达式（波兰式）
?运算符在操作数前面
后缀表达式考点（重点）?中缀转后缀
?1.按“左优先”原则确定运算符的运算次序
?2.根据1中确定的次序，依次将各个运算符和与之相邻的两个操作数按左操作数的规则合体
?后缀转中缀
?从左往右扫描，每遇到一个运算符，就将左操作数变为（左操作数运算符右操作数）的形式
?计算
?从左往右扫描，遇到操作数入栈，遇到运算符则弹出两个栈顶元素运算后入栈（先弹出的元素是“右操作数”）
前缀表达式?中缀转前缀
?1.按“右优先”原则确定运算符的运算次序
?2.根据1中确定的次序，依次将各个运算符和与之相邻的两个操作数按运算符的规则合体
?计算
?从右往左扫描，遇到操作数入栈，遇到运算符则弹出两个栈顶元素运算后入栈（先弹出的元素是“左操作数”）
表达式求值?
栈的应用——递归特殊矩阵压缩储存对称矩阵?特点：对方阵中任意一个元素，有ai,j=aj,i
?压缩：只储存主对角线+下三角区（或主对角线+上三角区）
三角矩阵?特点：上三角区全为常量（下三角矩阵）；或下三角区全为常量（上三角矩阵）
?压缩：按行优先/列优先规则依次存储非常量区域，并在最后一个位置存放常量c
三对角矩阵(带状矩阵）?特点：当
i-j
1时，有ai,j=0（1≤i，j≤n）
?压缩：按行优先/列优先规则依次存储带状区域
稀疏矩阵?特点：非零元素个数远小于零元素个数
?压缩：只存储非零元素
?顺序存储：顺序存储三元组行，列，值
?链式存储：十字链表法
串定义串，即字符串（String），是由零个或多个字符组成的有限序列术语：串长、空串、空格串、子串、主串、字符在主串中的位置、子串在主串中的位置串V.S线性表串的数据对象限定为字符集串的基本操作大多以“子串”为操作对象基本操作Index（S,T），定位操作、找到串T在主串S中的位置StrCompare(S,T):比较操作。若ST，则返回值0;若S=T,则返回值=0；若St，则返回值0。span=""/t，则返回值0。其他...字符集编码每个字符在计算机中对应一个二进制数，比较字符的大小其实就是比较二进制数的大小串的存储结构顺序存储?静态数组
?
?动态数组
?malloc、free
链式存储?可让每个结点存多个字符，没有字符的位置用“#”或‘\0’补足
王道教材采用——静态数组?
重点
基本操作的实现?求子串：boolSubString(SStringSub,SSringS,intpos,intlen)
?串的比较：intStrCompare(SStringS,SStringT)
?求串在主串中的位置：intIndex(SStringS,SStringT)
朴素模式匹配算法?算法思想
?主串长度n，模式串长度m
?将主串中所有长度为m的子串与模式串对比
?找到第一个与模式串匹配的子串，并返回子串起始位置
?若所有子串都不匹配，则返回0
?复杂度
?最坏时间复杂度=O（nm）
?最好时间复杂度=O（n）
KMP算法了解怎么做即可
?复杂度
?最坏时间复杂度=O（m+n）
?最好时间复杂度=O（n）
?求next数组
?next都无脑写0
?next都无脑写1
?其他next：在不匹配的位置前，划一根美丽的分界线模式串一步一步往后退，直到分界线之前“能对上”，或模式串完全跨过分界线为止，此时j指向哪儿，next数组值就是多少
树与二叉树基本概念结点、边、根节点、叶子节点、分支节点、子树基本术语结点之间的关系?父节点（双亲结点）、孩子节点
?祖父结点、子孙结点
?兄弟节点、堂兄弟结点
?节点之间的路径——只能从上往下
?路径长度——路径上经过多少条边
结点、树的属性?结点的层次（深度）、结点的高度
?树的深度（高度）
?结点的度
重点
?结点的分支数
?树的度
重点
?树中各结点的度的最大值
有序树VS无序树?逻辑上看，各子树是否有序，位置是否可换
森林?由m（m0）个互不相交的树组成森林
常考性质考点1?结点数=总度数+1
考点2考察点
?度为m的树
?至少有一个结点度=m
?一定是非空树
?m叉树
?允许所有结点的度都mspan=""/m
?可以是空树
考点3?度为m的树第i层至多有几个结点？
考点4?高度为h的m叉树至多有几个结点？
考点5考察点
?高度为h的m叉树至少有多少个结点？
?高度为h、度为m的树至少有多少个结点？
考点6?具有n个结点的m叉树的最小高度为？
二叉树基本概念?可为空二叉树
?任意结点的度≤2
?是有序树、左子树、右子树不可颠倒
?思考：二叉树V.S度为2的有序树
特殊二叉树?满二叉树
?高度为h，含有2^h-1个结点的二叉树
?完全二叉树
?在满二叉树的基础上可去掉若干个编号更大的结点
?二叉排序树
?左子树关键字根节点关键字右子树关键字span=""
?平衡二叉树
?左右子树深度差不超过1
常考性质?二叉树
?考点1
?设非空二叉树中度为0、1、2的结点个数分别n0、n1和n2，则n0=n2+1
?考点2
?二叉树第i层至多有2^（i-1）个结点（i≥1）m叉树第i层至多有m^（i-1）个结点（i≥1）
?考点3
?高度为h的二叉树至多有2^h-1个结点高度为h的m叉树至多有（m^h-1）/（m-1）个结点
?完全二叉树
?考点1
?具有n个（n0）结点的完全二叉树的高度h为?log2（n+1）?或?log2n+1?
?考点2
?对于完全二叉树，可以由结点数n推出为0、1、2的节点个数n0、n1和n2
?
二叉树储存结构?
?
二叉树先/中/后序遍历参考第五章6
二叉树层序遍历?树的层次遍历算法思想
?1.初始化一个辅助队列
?2.根节点入队
?3.若队列非空，则队头结点出队，访问该节点，并将其左、右孩子插入队尾（如果有的话）
?4.重复3直至队列为空
由二叉树遍历序列构造二叉树?前序+中序遍历序列
?后序+中序遍历系列
?层序+中序遍历系列
?
线索二叉树?作用：方便从一个指定节点触发，找到其前驱、后继；方便遍历
?储存结构
?在普通二叉树结点的基础上，增加两个标志位ltag和rtag
?ltag==1时，表示lchild指向前驱；ltag==0时，表示lchild指向左孩子
?rtag==1时，表示lchild指向后继；rtag==0时，表示rchild指向右孩子
?三种线索二叉树
?中序线索二叉树
?以中序遍历序列为依据进行“线索化”
?先序线索二叉树
?以先序遍历序列为依据进行“线索化”
?后序线索二叉树
?以后序遍历序列为依据进行“线索化”
?几个概念
?线索
?指向前驱/后继的指针称为线索
?中序前驱/中序后继；先序前驱/先序后继；后序前驱/后序后继
?手算画出线索二叉树
?确定线索二叉树类型——中序、先序、or后序？
?按照对应遍历规则，确定各个节点的访问顺序，并写上编号
?将n+1个空链域连上前驱、后继
?找前驱后继
?
二叉树线索化?中序线索化
?得到中序线索二叉树
?先序线索化
?得到先序线索二叉树
?后序线索化
?得到后序线索二叉树
?核心
?中序/先序/后序遍历算法的改造，当访问一个结点时，连接该结点与前驱结点的线索信息
?用一个指针pre记录当前访问节点的前驱节点
?易错点
?最后一个结点的rchild、rtag的处理
?先序线索化中，注意处理无限循环问题，当ltag==0时，才能对左子树先序线索化
树的存储结构?双亲表示法
?顺序存储结点数据，结点中保存父节点在数组中的下标
?优点：找父节点方便；缺点：找孩子不方便
?孩子表示法
?顺序存储结点数据，结点保存孩子链表头指针（顺序+链式存储）
?优点：找孩子方便；缺点：找父节点不方便
?孩子兄弟表示法
?用二叉链表存储树——左孩子右兄弟
?孩子兄弟表示法存储的树，从储存视角来看形态上和二叉树类似
?考点：树与二叉树的相互转换。本质就是用孩子兄弟表示法储存树
?森林与二叉树的转换
?本质：用二叉链表储存森林——左孩子右兄弟
?森林中各个树根节点之间视为兄弟关系
二叉排序树?二叉排序树的定义
?左子树节点值根节点值右子树节点值span=""
重点
?默认不允许两个节点的关键字相同
?查找操作
?从根节点开始，目标值更小往左找，目标值更大往右找
?插入操作
?找到应该插入的位置（一定是叶子结点），一定要注意修改其父结点指针
?删除操作
重点
?被删结点为叶子，直接删除
?被删除结点只有左或只有右子树，用其子树顶替其位置
?被删结点有左、右子树
?可用其后继节点顶替，再删除后继节点
?或用其前驱节点顶替，再删除前驱节点
?前驱：左子树最后下的结点
?后继：右子树最左下的结点
?查找效率分析
?取决于树的高度，最好O（logn），最坏O(n)
?平均查找长度的计算
重要
?查找成功的情况
?查找失败的情况（需补充失败节点）
平衡二叉树?定义
?树上任一结点的左子树和右子树的高度之差不超过1
?结点的平衡因子=左子树高-右子树高
?插入操作
?和二叉排序树一样，找到合适的位置插入
?新插入的结点可能导致其祖先的平衡因子改变，导致失衡
?调整“不平衡”
?找到最小不平衡子树进行调整，记最小不平衡子树的根为A
?LL
?在A的左孩子的左子树插入导致A不平衡，将A的左孩子右上旋
?RR
?在A的右孩子的右子树插入导致A不平衡，将A的右孩子左上旋
?LR
?在A的左孩子的右子树插入导致A不平衡，将A的左孩子的右孩子先左上旋再右上旋
?RL
?在A的右孩子的左子树插入导致A不平衡，将A的右孩子的左孩子先右上旋再左上旋
?查找效率分析
?考点：高为h的平衡二叉树最少有几个节点——递推求解
?平衡二叉树最大深度为O(logn)，平均长度/查找的时间复杂度为O(logn)
哈夫曼树?概念
?结点的权：某种特定含义的数值
?结点的带权路径长度=根到结点路径长度*结点的权值
?树的带权路径长度（WPL）=树中所有叶子节点的带权路径长度之和
?哈夫曼树（最优二叉树）：在含有给定的n个带权结点的二叉树，WPL最小的二叉树
?构造哈夫曼树
?每次选两个根节点权值最小的树合并，并将二者权值之和作为新的根节点的权值
?哈夫曼树不唯一，但WPL必然都是最小值
?哈夫曼编码
?将字符频次作为字符节点权值，构造哈夫曼树，即可得哈夫曼树，可用于数据压缩
?前缀代码——没有一个编码是另一个编码的前缀
?固定的长度编码——每个字符用相等长度的二进制位表示
?可变长度编码——允许对不同字符用不等长的二进制位表示
图图的基本概念定义：G=(V,E),顶点集V，边集E无向图（无向边/边）、有向图（有向边/弧）顶点的度、出度、入度（无向图？有向图？）边的权、带权图/网点到点的关系?路径、回路、简单路径、简单回路
?路径长度
?点到点的距离（最短路径）
?无向图顶点的连通性、连通图
?有向图顶点的强连通性、强连通图
图的局部?子图
?连通分量——极大连通子图
?强连通分量——极大强连通子图
?连通无向图的生成树——包含全部顶点的极小连通子图
?非连通无向图的生成森林——各连通分量的生成树
几种特殊形态的图?完全图
?稠密图、稀疏图
?树、森林、有向树
图的存储邻接矩阵?如何计算指定顶点的度、入度、出度（分无向图、有向图来考虑）？时间复杂度如何？
?如何找到与顶点相邻的边（入边、出边）？时间复杂度如何
?如何存储带权图？
?空间复杂度——O（
V
^2），适合存储稠密图
?无向图的邻接矩阵为对称矩阵，如何压缩存储？
?设图G的邻接矩阵为A（矩阵元素为0/1），则An的元素An[j]等于由顶点i到顶点j的长度为n的路径的数目
邻接表十字链表邻接多重表图基本操作Adjacent(G,x,y):判断图G是否存在边或（x，y）Neighbors(G,x):列出图G中与结点x邻接的边InsertVertex(G,x):在图G中插入顶点xDeleteVertex(G,x):从图G中删除顶点xAddEdge(G,x,y):若无向边(x,y)或有向边不存在，则向图G中添加该边RemoveEdge(G,x,y):若无向边(x,y)或有向边存在，则从图G中删除该边FristNeighbor(G,x):求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有临界点或图中不存在x，则返回-1。NextNeighbor(G,x,y):假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1Get_edge_value(G,x,y):获取图G中边(x,y)或对应的权值Set_edge_value(G,x,y,v):设置图G中边(x,y)或对应的权值为v考点图的BFS类似于树的层序遍历（广度优先遍历）算法要点?需要一个辅助队列
?如何从一个结点找到与之邻接的其他顶点
?visited数组防止重复访问
?如何处理非连通图
复杂度?空间复杂度：O(
V
)——辅助队列
?时间复杂度
?访问结点的时间+访问所有边的时间
?邻接矩阵:O(
V
^2)
?邻接表：(
O
+
E
)
广度优先生成树?由广度优先遍历确定的树
?邻接表存储的图表示方式不唯一，遍历序列、生成树也不唯一
?遍历非连通图可得广度优先生成森林
图的DFS算法要点?递归的深入探索未被访问过的邻接点（类似于树的先根遍历的实现）
?如何从一个结点找到与之邻接的其他顶点
?visited数组防止重复访问
?如何处理非连通图
复杂度分析?空间复杂度：O(
V
)——来自递归工作栈
?时间复杂度
?访问结点的时间+访问所有边的时间
?邻接矩阵：O(
V
^2)
?邻接表：O(
V
+
E
)
深度优先生成树?由深度优先遍历确定的树
?邻接表存储的图表示方式不唯一，深度优先遍历序列、生成树也不唯一
?深度优先遍历非连通图可得深度优先生成森林
图的遍历和图的连通性?无向图
?DFS/BFS函数调用次数=连通分量数
?有向图
?若从起始顶点到其他顶点都有路径，则只需调用1次DFS/BFS
?对于强连通图，从任一顶点出发都只需调用1次DFS/BFS
最小生成树基本不会考察代码
Prim算法（普里姆）?从某一个i的那个点开始构建生成树；每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。
Kruskal算法（克鲁斯卡尔）?每次选择一条权值最小的边，使这两条边的两头连通（原本已经连通的就不选），直到所有结点都连通
最短路径问题单源最短路径单个顶点连接各个顶点
?BFS算法（无权图）
?Dijkstra算法（带权图、无权图）
各顶点间的最短路径?Floyd算法（带权图、无权图）
查找基本概念查找?找到符合条件的数据元素（记录）
查找表?由同一类型的数据元素（记录）组成
?静态查找表
?只需要查找操作
?动态查找表
?除了查找，还需要增/删数据元素
关键字?唯一标识数据元素的数据项
查找算法的效率评价平均查找长度ASL通常考虑查找成功、查找失败两种情况下的ASL顺序查找算法实现?从头到尾（或者从尾到头）挨个找
?适用于顺序表、链表、表中元素有序无序都OK
?可在0号位置存“哨兵”，从尾部向头部挨个查找优点：循环时无需判断下标是否越界
优化?若表中元素有序
?当前关键字大于（或小于）目标关键字时，查找失败
?优点：查找失败时ASL更少
?查找判定树
考点
?成功结点的关键字对比次数=结点所在层数
?失败节点的关键字对比次数=其父节点所在层数
?若各个关键字被查概率不同
?可按被查概率降序排列
?优点：查找成功时ASL更少
时间复杂度?O(n)
折半查找适用范围?只适用于有序的顺序表
算法思想?在[low,high]之间找到目标关键字，每次检查mid=（low+high）/2
?根据mid所指元素与目标关键字的大小调整low或high，不断缩小low和high的范围
?若lowhigh则查找失败
判定树?构造
?由mid所指元素将原有元素分割到左右子树中
?Key：右子树结点数-左子树结点数=0或1
?特性
?折半查找的判定树是平衡的二叉排序树（左中右）span=""
?折半查找判定树，只有最下面一层是不满的
?若查找表有n个关键字，则失败结点有n+1个
?树高h=?log2（n+1）?（不包含失败结点）
时间复杂度?O(log2n)
分块查找又称“索引顺序查找”，数据分块储存，块内无序、块间有序算法思想?索引表中记录每个分块的最大关键字、分块区间
?先查索引表（顺序或折半）、再对分块内进行顺序查找
ASL?ASL=查索引表的平均查找长度+查分块的平均查找长度
?设n个记录均匀分成B块，每块s个记录
?顺序查找索引表
?
?
?折半查找索引表
?
易错点?对索引表进行折半查找时，若索引表中不包含目标关键字，则折半查找最终停在lowhigh，要在low所指分块中查找
B树插入?通过“查找”确定插入位置（一定是在终端结点）
?若插入后结点关键字个数未超过上限，则无需做其他处理
?若插入后关键字个数超过上限，则需要将当前结点的中间元素放到父节点中，当前结点分裂为两个部分;该操作会导致父节点关键字个数+1,若父节点关键字个数也超过了上限，则需要再向上分裂;根节点的分裂会导致B树高度+1。
删除?非终端结点关键字
?用其直接前驱或直接后继代替其位置，转化为对“终端结点”的删除
?直接前驱：当前关键字左边指针所指子树中“最右下”的元素
?直接后继：当前关键字右边指针所指子树中“最左下”的元素
?终端结点关键字
?删除后节点关键字个数未低于下限，无需任何处理
?低于下限
?右兄弟够借，则用当前结点的后继、后继的后继依次顶替空缺
?左兄弟够借，则用当前结点的前驱、前驱的前驱依次顶替空缺
?左（右）兄弟都不够借，则需要与父结点内的关键字、左（右）兄弟进行合并。合并后导致父节点的关键字数量-1，可能需要继续合并。
B+树B树VSB+树散列查找概念?散列表、散列函数H（key）、同义词、冲突
?填装因子α=表中记录个数/散列表表长
常见散列函数?除留余数法
?H（key）=key%p，p是不大于表长的质数
?直接定址法
?H（key）=key或H（key）=a*key+b
?数字分析法
?选取数码分布较为均匀的若干位作为散列地址
?平方取中法
?取关键字的平方值得中间几位作为散列地址
冲突的处理?拉链法（链地址法）
?同义词串成一个链表
?开放定址法
?线性探测法
?di=0，1，2，3,...,i-1
?平方探测法
?di=0^2,1^2,-1^2,-2^2...
?伪随机序列法
?di=一个伪随机序列
?再散列法
?准备多个散列函数，一个发生冲突了就用下一个
查找效率?取决于散列函数、处理冲突得方法、填装因子α
排序将各元素按关键字递增/或递减顺序重新排列评价指标稳定性?关键字相同的元素经过排序后相对顺序是否会改变
时间复杂度、空间复杂度分类内部排序?数据都在内存中
外部排序?数据太多，无法全部放入内存
插入排序算法思想：每次将一个待排序的记录按其关键字大小插入到前面已排好的子序列中，直到全部记录插入完成。直接插入排序?顺序查找找到插入的位置，适用于顺序表、链表
折半插入排序?折半查找找到应插入的位置，仅适用于顺序表
?注意：一直到lowhigh时才停止折半查找。当mid所指元素等于当前元素时，应继续令low=mid+1，以保证“稳定性”。最终应将当前元素插入到low所指位置（即high+1）
性能?空间复杂度
?O(1)
?时间复杂度
?最好
?原本有序O(n)
?最坏
?原本逆序O(n^2)
?平均
?O(n^2)
?稳定性
?稳定
希尔排序先将待排序表分割成若干形如L[i，i+d,i+2d,...,i+kd]的“特殊”子表，对各个子表分别进行直接插入排序。缩小增量d，重复上述过程，直到d=1为止。性能?空间复杂度
?O(1)
?时间复杂度
?未知，但优先于直接插入排序
?稳定性
?不稳定
?适应性
?仅可用于顺序表
高频体型：给出增量序列，分析每一趟排序后的状态冒泡排序算法原理?从后往前（或从前往后）两两比较相邻元素的值，若为逆序，则交换它们，直到序列比较完。称这样的过程为“一趟”冒泡排序。最多只需n-1趟排序
?每一趟排序都可以使一个元素移动到最终位置，已经确定最终位置的元素在之后的处理中无需再对比
?如果某一趟排序过程中未发生“交换”，则算法可提前结束
性能?空间复杂度
?O(1)
?时间复杂度
?最好O(n)
?有序
?最差O(n^2)
?逆序
?平均O(n^2)
?稳定性
?稳定
?适用性
?顺序表、链表都可以
快速排序算法表现主要取决于递归深度，若每次“划分”越均匀，则递归深度越低。“划分”越不均匀，则递归深度越深性能?空间复杂度
?最好
?O(n)
?最坏
?O(logn)
?时间复杂度
?最坏
?O(nlogn)
?每次划分很平均
?最好
?O(n^2)
?原本正序或逆序
?平均
?O(nlogn)
?稳定性
?不稳定
简单选择排序算法原理?每一趟在待排序元素中选取关键字最小的元素加入有序子序列
?必须进行总共n-1趟处理
性能?空间复杂度
?O(1)
?时间复杂度
?O(n^2)
?稳定性
?不稳定
?适用性
?顺序表、链表都可以
堆排序堆?顺序存储的“完全二叉树”
?结点i的左孩子是2i；右孩子是2i+1；父节点是i/2
?编号≤n/2的结点都是分支结点
?大根堆(根≥左、右)；小根堆(根≤左、右)
算法思想（以大根堆为例）?建堆
?编号≤n/2的所有结点依次“下坠”调整（自底向上处理各分支节点）
?调整规则：小元素逐层“下坠”（与关键字更大的孩子交换）
?排序
?将堆顶元素加入有序子序列（堆顶元素与堆底元素交换）
?堆底元素换到堆顶后，需要进行“下坠”调整，恢复“大根堆“的特性
?上述过程重复n-1趟
特性?时间复杂度
?O(1)
?空间复杂度
?建堆O(n)、排序O(nlogn)；总的时间复杂度=O(nlogn)
?稳定性
?不稳定
?基于大根堆的堆排序得到”递增序列“，基于小根堆的堆排序得到”递减序列“
堆的插入与删除?插入
?新元素放到表尾(堆底)
?根据大/小根堆的要求，新元素不断”上升“，直到无法继续上升为止
?删除
?被删除元素用表尾(堆底)元素替代
?根据大/小根堆的要求，代替元素不断”下坠“，直到无法继续下坠为止
?关键字对比次数
?每次”上升“调整只需对比关键字1次
?每次”下坠“调整可能需要对比关键字2次，也可能只需对比1次
?基本操作
?i的左孩子——2ii的右孩子——2i+1i的父节点——?i/2?
归并排序Merge（归并）?把两个或多个有序的子序列合并为一个
?2路归并——二合一
?k路归并——k合一
归并排序算法?若lowhigh，则将序列分成从中间mid=(low+high)/2分开
?对左半部分[low，mid]递归地进行归并排序
?对右半部分[mid+1，high]递归地进行归并排序
?将左右两个有序子序列Merge为一个
性能?空间复杂度
?O(n)
?时间复杂度
?O(nlogn)
?稳定性
?稳定的
基数排序算法思想?将整个关键字拆分为d位(或”组“)
?按照各个关键字位权重递增的次序(如：个、十、百)，做d趟”分配“和”收集“，若当前处理的关键字位可能取得r个值，则需要建立r个队列
?分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应队列。一趟分配耗时O(n)
?收集：把各个队列中的结点依次出队并链接。一趟收集耗时O(r)
性能?时间复杂度
?O(r)
?空间复杂度
?O(d(n+r))
?稳定性
?稳
擅长处理?数据元素的关键字可以方便地拆分为d组，且d较小
?每组关键字的取值范围不大，即r较小
?数据元素个数n较大
外部排序若要进行k路归并并排序，则需要在内存中分配k个输入缓冲区和1个输出缓冲区步骤?生成r个初始归并段(对L个记录进行内部排序，组成一个有序的初始归并段)
?进行S趟k路归并，S=[log(k)(r)]
如何进行k路归并?把k个归并段的块读入k个输入缓冲区
?用”归并排序“的方法从k个归并段中选出几个最小记录暂存到输出缓冲区中
?当输出缓冲区满时，写出外存
外部排序时间开销?读写外存的时间+内部排序所需时间+内部归并所需时间
优化?增加归并路数k，进行多路平衡归并
?代价1：需要增加相应的输入缓冲区
?代价2：每次从k个归并段中选一个最小元素需要(k-1)次关键字对比
?减少初始归并段数量r
最佳归并树基础理论?每个初始归并段对应一个叶子结点，把归并段的块数作为叶子的权值
?归并树的WPL=树中所有叶结点的带权路径长度之和
?归并过程中的磁盘I/O次数=归并树的WPL*2
注意：k叉归并的最佳归并树一定是严格k叉树，即树中只有度为k、度为0的结点如何构造?补充虚段
?若(初始归并段数量-1)%(k-1)=0，说明刚好可以构成严格k叉树，此时不需要添加虚段
?若(初始归并段数量-1)%(k-1)=u≠0，则需要补充(k-1)-u个虚段
?构造k叉哈夫曼树
?每次选择k个根节点权值最小的树合并，并将k个根节点的权值之和作为新的根节点的权值
预览时标签不可点收录于话题#个上一篇下一篇