数据结构作为六七年前甚至小学就有接触过的知识，如今再次与其狭路相逢。不同于之前所有数据结构知识的学习，考研的数据结构会明显偏向于理论知识而非实践应用，故特此另开一篇用以记录学习历程。
【20210924】虽然基本上是按照王道的复习指导来复习的，但实际专业科目并非408，所以目录和408是有出入的，但大体而言的知识点覆盖是一致的。随着2022年408考纲的修订，会有如下知识点不会提及：串、并查集、平衡树、红黑树、外部排序等。
目录
第一章绪论
第二章线性表
第三章数组
第四章栈和队列
串
第七章树与二叉树
第八章图
第九章文件及查找
第十章内排序
数据结构考研笔记
1.1数据结构的基本概念
1.1.1基本概念和术语
数据是信息的载体；
数据元素是数据的基本单位，由若干个数据项（最小单位）组成；
数据对象是具有相同性质的数据元素的集合；
数据类型分为原子类型、结构类型、抽象数据类型；
数据结构是存在某种关系的数据元素的集合，包括逻辑结构、存储结构与数据的运算。
1.1.2数据结构三要素
①逻辑结构
逻辑结构指数据元素之间存在的逻辑关系，是固有的客观联系；
逻辑结构分为线性结构与非线性结构，比如：线性表、树、图等；
②存储结构
存储结构又称为物理结构，指数据结构在计算机中的表示（映像），是计算机内部的存储方法；
存储结构主要有顺序存储、链式存储、索引存储和散列存储；
一种逻辑结构通过映像便可以得到它的存储结构；
诸如顺序表、哈希表、链表这样的表述，它们既体现了逻辑结构（均为线性），又体现了存储结构（顺序、散列、链式）；
而这样的表述我们往往就直接称之为数据结构；
诸如有序表，它只体现了逻辑结构（线性），而存储结构是未知的（可以是顺序、链式……）；
不存在只体现存储结构而不体现逻辑结构的表述；
所以，我们认为：逻辑结构独立于存储结构。
③数据的运算（算法）
算法包括运算的定义（取决于逻辑结构，体现算法功能）与实现（取决于存储结构，体现于操作步骤）。
1.2算法的基本概念
算法的5个重要特性：有穷性、确定性、有效性（可行性）、输入与输出；
一个好的算法的目标：正确性、可读性、鲁棒性、效率与低存储量需求。
1.3算法分析
O(1) (log表示以2为底的对数) 空间复杂度指算法耗费存储空间的数量级。 1.4题目与总结 ①循环条件包含主体变量，将执行次数t代入该条件再计算，如： inti=1;while(i<=n)i=i*2;每次i*=2，执行次数t+=1，即2^t<=n，得t<=logn，则T(n)=O(logn)。再如： inti=3;while((i+1)*(i+1) ②循环条件与主体变量无关，采用数学归纳法或直接循环计数。如： intfact(intn){if(n<=1)return1;returnn*fact(n-1);}对于递归函数，直接得T(n)=1+T(n-1)=k+T(n-k)=n-1+T(1)=n，即T(n)=O(n)。 2.1线性表的基本概念 2.1.1线性表的定义 线性表是具有相同数据类型的n个数据元素的有限序列。 线性表的特点： ①表中元素具有逻辑上的顺序性，有先后次序； ②表中元素都是数据元素，每个元素都是单个元素； ③表中元素的数据类型都相同，占有相同大小的存储空间； ④表中元素具有抽象性，即仅讨论元素间的逻辑关系，不考虑具体内容。 线性表是逻辑结构，表示元素一对一的相邻关系； 顺序表、链表是存储结构，表示在计算机中数据的存储方式。 2.1.2线性表的基本操作 略 2.2线性表的顺序存储结构 2.2.1顺序表的定义 顺序表指线性表的顺序存储，用一组地址连续的存储单元存储； 顺序表是一种随机存取的存储结构，存储密度大； 一般用数组表示顺序表，线性表从1开始，数组下标从0开始； 顺序表最主要特点是随机访问，通过首地址与元素序号在O(1)找到指定元素。 2.2.2顺序表上基本操作的实现 >插入结点O(n)1<=i<=Length >删除结点O(n)1<=i<=Length >按值查找O(n)1<=i<=Length *2.2.3关于静态分配与动态分配 静态分配代码： #defineMaxSize50typedefstruct{ElemTypedata[MaxSize];intlength;}SeqList;动态分配代码： #defineInitSize20typedefstruct{ElemType*data;intMaxSize,length;}SeqList;L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);//CL.data=newElemType[InitSize];//C++对于动态分配，如果空间占满，则开辟一块更大的存储空间。即如果原有n个元素，现申请增加m个连续的存储空间，则需要寻找一块n+m个连续的存储空间，再将原有的n个元素复制到新空间的前n个存储空间。 2.3线性链表及其操作 2.3.1单链表的定义 单链表指线性表的链式存储，用一组任意的存储单元来存储数据元素； 而为了建立元素之间的线性关系，对每个链表结点，还要存放一个指向后继的指针； 头指针用以标识单链表，如果其值为NULL，说明为一个空表； 在第一个结点前附加一个结点，成为头结点，可以不记录信息，也可以记录表长。 设置头结点，便于空表与非空表的统一处理。 2.3.2单链表上基本操作的实现 >建表O(n) ①头插法：将存有读入数据的新结点插入到当前链表表头； 使用头插法会导致读入数据与生成链表顺序相反； ②尾插法：增加一个尾指针，以使新结点直接插入到表尾。 >查找O(n) ①按序号查找 ②按值查找 >插入结点O(n) 一般指在某结点的后面插入新结点，即后插操作。 >删除结点O(n) >求表长O(n) 2.3.3双链表 在单链表基础上增加前驱指针。 2.3.4循环链表 对于循环单链表，尾结点指针不是指向NULL，而是头结点； 对于循环双链表，在循环单链表基础上，头结点的前驱指针指向尾结点。 2.3.5静态链表 静态链表借助数组来描述链式存储结构，结点的指针域的值是下一结点的相对地址（数组下标），最后以-1或其他值域外的值表示结束。 静态链表操作起来明显不够方便，其存在的意义在于适用于不支持指针的语言。 2.3.6顺序表与链表的比较 2.4题目与总结 真题的算法题还是很有意思的，给出一个很简单的需求，可以用比较常规的方法做，但往往会有很巧妙的做法，和面试试题的风格接近。比如： 【王道2.2应用第12题】【2013408真题】求长度为n，值域为n的整数序列中出现次数大于n/2的元素的值。 奇妙的满分方法。 3.1数组的定义 数组是由n个相同类型的数据元素构成的有限序列。 数组是线性表的推广。一维数组可视为一个线性表，二维数组可视为其元素均为定长线性表的线性表，以此类推。 3.2数组的存储结构 对于多维数组有两种映射方法：按行优先与按列优先。一般默认按行优先。 3.3特殊矩阵的压缩存储 压缩存储：多个值相同的元素只分配一个存储空间，0元素不分配； 特殊矩阵：如对称矩阵、上三角矩阵、对角矩阵。 3.4稀疏矩阵的三元组表示 稀疏矩阵指非零元素个数远小于零个数的矩阵。 用三元组（行，列，值）来存储，或者十字链表法。 3.5数组的应用举例 第四章堆栈和队列 4.1堆栈的基本概念 栈是一种运算受限的线性表，只允许在一端进行插入或删除操作。 数学性质：n个不同元素进栈，出栈元素不同排列的个数为C(2n,n)/(n+1)，这就是卡特兰数。 栈的基本操作： >InitStack(&S)初始化空栈S >StackEmpty(S)判断栈是否为空 >Push(&S,x)进栈 >Pop(&S,&x)出栈，弹出栈顶元素x并返回 >GetTop(S,&x)读栈顶元素x并返回 >DestroyStack(&S)销毁栈，释放空间 4.2堆栈的顺序存储结构 顺序栈的实现：略 顺序栈的基本运算：略 共享栈：两个顺序栈共享一个一维数组，栈底分别设在两端，栈顶向中间延伸。 4.3堆栈的链式存储结构 采用链式存储的栈称为链栈。 优点：便于多个栈共享存储空间，提高效率，且不存在栈溢出的情况。 链栈没有头结点，直接指向栈顶元素。 4.4队列的基本概念 队列是一种只允许在表的一端插入，另一端删除的线性表。 队列的操作： >InitQueue(&Q)初始化空队列Q >QueueEmpty(Q)判断队列是否为空 >EnQueue(&Q,x)入队 >DeQueue(&Q,&x)出队，删除队头元素x并返回 >GetHead(Q,&x)读队头元素x并返回 4.5队列的顺序存储结构 队列的顺序存储：略 循环队列：普通队列会出现假溢出情况，故引用循环队列，将队列从逻辑上视为一个环，利用取余运算实现。 由于循环队列在队空与队满的判断条件是等价的，故需要一些处理方式来区分： >牺牲一个单元来区分，约定“队头在队尾下一位置作为队满的标志”； >增设表示元素个数的数据成员。 循环队列的操作：略 4.6队列的链式存储结构 队列的链式存储：采用链式存储的队列称为链队列。 链队列往往设计成带头结点的单链表。 链式队列的基本操作：略 双端队列 双端队列指两端都可以入队出队操作的队列，两端称为前端和后端。 栈和队列的应用 栈在括号匹配中的应用 栈在表达式求值中的应用 后缀表达式可以轻松获得运算符关系，且不用处理括号。用栈处理。 栈在递归中的应用 可以用栈来模拟递归过程，以消除递归。 对于同一个问题，非递归算法效率通常比递归算法更高。 队列在层次遍历中的应用 比如BFS。 队列在计算机系统中的应用 比如页面替换算法。 4.7题目与总结 【王道3.2选择第8题】【2011408真题】循环队列存储在数组A[0..n-1]中，队列非空时front和rear分别指向队头与队尾。初始时队列为空，且第一个进入队列的元素存储在A[0]，则front和rear的初值为？ 反向思考。首先插入后的队首与队尾指向的位置均为0，且插入元素只会更改rear的值，则front在插入前仍为0，而rear需要-1，对于循环队列，0的前一个位置为n-1。故答案分别为0,n-1。 【王道3.3选择第11题】【2012408真题】将中缀表达式a+b-a*((c+d)/e-f)+g转换为等价的后缀表达式ab+acd+e/f-*-g+时，用栈存放暂时不能确定运算次序的操作符，转换过程中栈的操作符个数最大为？ 看了下解析，实在是太麻烦了点吧。不过自己做的时候没想太多，前后两道题也做对了。 无括号时正常乘除在先加减在后。有括号时，遇到右括号，完成对应的左括号之后范围内所有运算。 比如本题，+直接运算，可弹出；-不动，因为后面是个*；加上第一个(；遇到第一个)时，第二个(及里面的+弹出；遇到第二个)时，第一个(及里面的/与-弹出；*运算完成，-*先后弹出；+直接运算，弹出。 整个过程中，操作符最大的时刻在：-*(/-，即遇到第二个)之前。 串的定义和实现 串的定义 串是由零个或多个字符组成的有限序列，为字符串的简称。 串的存储结构 串有三种存储方式： >定长顺序存储表示：分配一个固定长度 >堆分配存储表示：按串长动态分配，使用指针指向串的起始地址 >块链存储表示：类似于线性表链式存储结构，具体实现时可以使每个结点存放一个或多个字符 串的基本操作 >StrAssign(&T,chars)将串T赋值为chars >StrCopy(&T,S)将串S复制得到串T >StrEmpty(S)判断串S是否为空 >StrCompare(S,T)比较串S与T的大小（S>T返回值>0；=/=； >StrLength(S)返回串S的长度 >SubString(&Sub,S,pos,len)返回串S的第pos个字符起长度为len的子串Sub >Concat(&T,S1,S2)返回串S1和串S2连接而成的串T >Index(S,T)返回主串S中与串T相同的子串第一次出现的位置（不存在则为0） >ClearString(&S)清空串S >DestroyString(&S)销毁串S，释放空间 串的模式匹配 简单的模式匹配算法 子串的定位操作通常称为串的模式匹配，求的是子串（模式串）在主串中的位置。 具体算法略。 改进的模式匹配算法——KMP算法 部分匹配值：字符串的最长公共前后缀长度； 比如字符串'ababa'，其部分匹配值为3，对应的前缀与后缀为'aba'； 在算法竞赛中，通常我们会将模式串的所有前缀的部分匹配值后移一位再依次存入一个数组，一般称为fail数组或next数组；第一位填充-1； 还是'ababa'，其fail数组为：[-1,0,0,1,2]； 求得fail数组后，每次匹配失败，则将模式串当前指针前移到fail[匹配失败的位置]，主串指针不动，同时再次对齐两个指针。这样思考更适用于笔试考场。 注意题目可能给出的fail数组所有值+1，以适应首位序号不为0而为1的标号方式。 KMP算法的进一步优化 优化构建fail数组的过程。假设模式串为a，且匹配失败恰好发生在第i位，则下次匹配必然是与第fail[i]位，但如果a[i]=a[fail[i]]，则必然再次匹配失败，以此类推。所以为了避免多余的匹配，我们将这种情况下的fail[i]=j优化为fail[i]=fail[j]，相当于再递归一次。 优化后的数组一般命名为nextval数组。 7.1树的基本概念 7.1.1树的定义 树是n个结点的有限集。对于任意一棵空树，满足： ①有且仅有一个特定的根结点； ②n>1时，除去根结点外的其他结点又可分为若干个互不相交的子树。 7.1.2树逻辑上的特点 7.1.3树的逻辑表示方法 文氏图表示法；凹入表示法；嵌套括号（广义表）表示法；树形表示法。 【可能需要补充】 7.1.4基本名词术语 >祖先/子孙/双亲（父）/孩子（子）/兄弟 >度：结点的子结点个数为结点的度；最大结点的度为树的度 >分支结点/叶子结点 >深度（自顶向下）/高度（自底向上）/层次 >有序树/无序树 >路径/路径长度 >森林：m棵互不相交的树集合，加上一个共同根结点后即可认为是一棵树 7.1.5树的性质 ①树的结点数=所有结点度数之和+1； ②度为m的树第i层至多m^(i-1)个结点； ③高度为h的m叉树至多(m^h-1)/(m-1)个结点； ④具有n个结点的m叉树最小高度为log_m[n(m-1)+1]向上取整。 7.2树的存储结构 7.2.1多重链表结构 将每个结点的子结点用单链表链接起来形成线性结构，即孩子表示法； 找子结点时操作简单，而找父结点则相当麻烦，同时很浪费空间。 7.2.2三重链表结构 每个结点包含结点值、指向父结点的指针、指向结点第一个子结点的指针、指向结点下一个兄弟结点的指针，即孩子兄弟表示法（二叉树表示法）与双亲表示法的结合。 由于存储内容多，对于各类操作都容易实现，又不浪费空间。 【注：这一节的说法区别较大】 7.3二叉树 7.3.1二叉树的定义 二叉树是度不大于2的有序树，即每个结点至多2棵子树，且有左右之分； 空树与只有根结点的情况都是二叉树； 即使某个结点只有一棵子树，也需要明确其是左子树还是右子树。 7.3.2两种特殊形态的二叉树 ①满二叉树：高度为h且含有2^h-1个结点的二叉树； 每层都含有最多的结点，故可以按层序编号； 对于编号为i的结点，左孩子为2i，后孩子为2i+1。 ②完全二叉树：最后一层可以不含有最多结点的满二叉树； 特征很多，都容易推出，略。 还有二叉排序树与平衡二叉树也是特殊的二叉树。 7.3.3二叉树的性质 >非空二叉树叶子结点数=度为2的结点数+1（常用结论） 其他略。 7.3.4二叉树的基本操作 7.3.5二叉树与树、树林之间的转换 遵循左孩子右兄弟原则； 树的前根序列、森林的先序遍历、二叉树的先序遍历相对应； 树的后根序列、森林的中序遍历、二叉树的中序遍历相对应。 7.4二叉树的存储结构 7.4.1二叉树的顺序存储结构 一般只用于满二叉树与完全二叉树，否则太浪费空间； 数组下标从1开始更恰当，以满足父子结点之间的编号关系。 7.4.2二叉树的链式存储结构 每个结点包含结点值、指向左孩子结点的指针、指向右孩子结点的指针。 7.5二叉树的遍历 7.5.1什么是二叉树的遍历 二叉树的遍历指按某条搜索路径访问每个结点有且仅有一次。 7.5.2前序遍历 先根结点，再左子树，再右子树。 7.5.3中序遍历 先左子树，再根结点，再右子树。 7.5.4后序遍历 先左子树，再右子树，再根结点。 7.5.5按层次遍历 以满二叉树/完全二叉树按层次编号的顺序进行遍历。 7.5.6递归问题的非递归算法的设计 即用栈来模拟递归的过程； 效率更高，但编写起来更麻烦。 7.5.7由遍历序列恢复二叉树 由前序/后序遍历加上中序遍历，可唯一确定一棵二叉树。 7.5.8树和树林的遍历 暂略 7.6线索二叉树 7.6.1基本概念 线索二叉树将结点的前驱或后继的指针存放到叶子结点的空指针中，以更为方便地遍历二叉树； 为此我们需要额外增加两个标志域以表示其左右指针是指向子结点还是前驱/后继。 7.6.2什么是线索二叉树 7.6.3线索二叉树的构造 为方便，可以在二叉树的线索链表中添加一个头结点； 头结点的左指针指向二叉树根结点，右指针指向最后一个结点。 7.6.4线索二叉树的利用 7.6.5线索二叉树的建立 唯有后序线索树的遍历需要利用栈。 7.7二叉排序树 7.7.1二叉排序树的定义 二叉排序树的左子树所有结点小于根结点，右子树所有结点大于根结点； 二叉排序树的中序遍历必然严格单调递增。 7.7.2二叉排序树的建立 7.7.3二叉排序树的删除 删除结点如果： >右子树空，则用左儿子结点填补； >左子树空，则用右儿子结点填补； >左右子树均非空，则用右子树的中序序列的第一个结点填补。 7.7.4二叉排序树的查找 查找效率取决于树的高度： >如果左右子树高度差不超过1（即平衡二叉树），则平均查找长度为O(log2n) >如果是一棵单支树（即类似于单链表），则为O(n) 7.8哈夫曼树及其应用 7.8.1哈夫曼树的基本概念 WPL：树中所有叶结点带权路径长度（路径长度*结点权值）之和； 对于n个带权叶结点构成的所有二叉树中，WPL值最小的为哈夫曼树。 7.8.2哈夫曼树的构造 每次选取两棵根结点权值最小的树作为新结点的左右子树，以此反复； 哈夫曼树没有度为1的结点。 7.8.3哈夫曼编码 7.9题目与总结 【王道5.1选择第7题】【2010408真题】在一棵度为4的树中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树的叶结点个数是？ 根据树的性质，树的结点数=树的分支数+1=树的度数+1，即： 叶结点个数+20+10+1+10=20*4+10*3+1*2+10*1+1 可得：叶结点个数=82 【王道5.3选择第29题】二叉树在线索化后，仍不能有效求解的问题是？A.前序线索二叉树求前序后继B.中序线索二叉树求中序后继C.中序线索二叉树求中序前驱D.后续线索二叉树求后序后继 线索二叉树不能有效求解，意味着在遍历过程中线索无法指向实际存在的前驱/后继。 对于前序/中序的遍历过程，它们的共同点在于一定会在叶子结点遍历到与该结点不直接相连的结点上，那么线索也就必定存在；而后序遍历是可能有非叶子结点遍历过去的，而非叶子结点不能建立线索，故无法继续遍历到它的实际后继。 故只能选D。 【王道5.4选择第27题】若度为m的哈夫曼树中，叶子结点个数为n，则非叶子结点的个数为？ 初看这道题觉得很古怪，以往我们都将哈夫曼树既定地认为是二叉树，而这里突然问一个度未知的哈夫曼树，所以也只能将计就计地类比一下了。 度为m的哈夫曼树，根据其建立过程，每次选择根结点度数最小的m棵树进行合并，意味着其所有结点的度数只有0和m两种可能。 已知总结点个数=分支数-1=非叶子结点个数y*m-1=n+y，解得：y=(n-1)/(m-1)，最后向上取整。 8.1图的基本概念 8.1.1图的定义 图不可以为空图，点集不得为空，但边集可以。 8.1.2图的分类 8.1.3名词术语 ①有向图：边集由有向边（弧）构成； ②无向图：边集由无向边（边）构成； 弧一般用<>表示，边一般用()表示； ③简单图：没有重边，没有自环；否则为多重图； ④完全图：任意两点之间都存在边（或者两条方向相反的弧）； ⑤子图：边集与点集均为另一个图的子集； 当边集等价时，则称为生成子图； ⑥无向图的连通、连通图、连通分量： 极大连通子图：又称为连通分量，对于连通图，极大连通子图即其自身；对于非连通图，有多个极大连通子图； 极小连通子图：即生成树，对于非连通图没有意义； ⑦有向图的强连通、强连通图、强连通分量： 极大强连通子图：又称为强连通分量，类比于连通分量； 不存在极小强连通子图； ⑧生成树：包含全部顶点的极小连通子图； ⑨度、入度、出度：略； ⑩网：带权图的别称； 稠密图、稀疏图：均为模糊而相对的概念； 路径、路径长度、回路：略； 简单路径、简单回路：结点不重复出现； 距离：最短路径； 有向树：形如树的有向图。 8.2图的存储方法 8.2.1邻接矩阵存储方法 设邻接矩阵为A，A^n的元素A^n[i][j]表示点i到点j长度为n的路径数目。 8.2.2邻接表存储方法 邻接表顶点数n决定顶点表个数，边数e决定边表个数； 两种存储方法对于不同操作各有优势。 8.3图的遍历 8.3.1深度优先遍历 8.3.2广度优先遍历 BFS树的高度总会小于等于DFS树。 8.4最小生成树 8.4.1什么是最小生成树 8.4.2求最小生成树 8.5最短路径问题 8.5.1路径长度的定义 8.5.2问题的提出 8.5.3解决问题所需要确定的数据结构 8.5.4算法（用自然语言表达） 8.6AOV网与拓扑排序 8.6.1AOV网的定义 AOV网，ActivityOnVertexNetwork，建立在DAG（有向无环图）上的用点表示活动、用弧表示活动优先级的网。弧是无权的。 8.6.2拓扑排序 8.6.3拓扑排序的方法 8.7AOE网与关键路径 8.7.1AOE网的定义 AOE网，ActivityOnEdgeNetwork，建立在DAG（有向无环图）上的用点表示事件、用弧表示活动（开销）的网。弧是带权的。 8.7.2AOE网的存储方法 8.7.3关键路径 这个最大路径长度即完成整个工程所需的最短工期，只有加快关键活动进度才能缩短工期。 8.7.4求关键路径 所有e=l的活动为关键活动，构成关键路径。 第九章文件与查找 9.1文件的基本概念 9.1.1名次术语 属性：记录：文件：关键字： 9.1.2文件的逻辑结构 9.1.3文件的物理结构 顺序（连续）链接索引散列（随机） 9.1.4文件的基本操作 查找插入删除修改排序 9.2顺序文件 9.2.1顺序文件的基本概念 顺序文件：物理结构与逻辑结构记录排列先后次序一致的文件； 从逻辑结构上划分，按关键字有序的顺序文件成为排序顺序文件，否则为一般顺序文件； 从存储结构上划分，在存储介质上采用连续组织方式的顺序文件称为连续顺序文件，采用链接组织方式的顺序文件称为链接顺序文件。 两种划分方式的名称可叠加使用，比如排序连续顺序文件。 9.2.2连续顺序文件的查找 顺序查找法；二分查找法（前提是有序，根据教材默认为向下取整，边界不取中间值）； 关于二分查找的判定树： ① ②判断是否可以作为二分查找判定树，将序列按中序遍历填入树中，观察取整方式是否一致。 9.2.3链接顺序文件的查找 9.3索引文件 9.3.1索引文件的基本概念 索引：记录关键字值与记录的存储位置之间的对应关系； 索引文件：由基本数据与索引表两部分组成的数据文件。 9.3.2稠密索引文件 每一个记录在索引表中都占有一项。 9.3.3非稠密索引分块文件 将记录分成若干块，索引表只记录每一块的首地址； 块内数据不用有序，块间则必须有序。 9.3.4多级索引文件 9.4B-树和B+树 【这一部分应该是之前搞竞赛时唯一完全没接触过的部分】 9.4.1B-树的定义 B-树（Balance-Tree），即多路平衡查找树，又称为B树。它是在二叉排序树上的优化，带有一定的分块思想。 B-树每一个（内部）结点包含如下有序信息： 关键字个数，子结点指针0，关键字值1，子结点指针1，关键字值2，子结点指针2，... 对于子结点指针x指向的子结点，其关键字值的值域为：（关键字值x-1，关键字值x） 对于m阶的B-树，满足： ①是一棵m叉树，即任意结点最多有m个子结点，即最多有m-1个关键字； ②根结点最少有2个子结点，其他非叶子结点最少有m/2个子结点； ③叶子结点都位于同一层，不包含任何关键字信息，所以一般又称其为外部结点。 随便丢个图理解下： B-树的高度：对于有n个关键字的m阶B-树，其高度范围为log_m(n+1)<=h<=(log_(m/2)((n+1)/2))+1。 9.4.2B-树的查找 9.4.3B-树的插入 插入位置一定是最底层中的某个非叶子结点； 插入过程可能会导致溢出，使得关键字个数超过m-1，此时需要进行结点分裂； 从溢出结点开始将其关键字从中间位置分成两部分，一部分放在原结点，一部分放在新结点，并使其依旧满足B-树的性质，依次递归直到不出现溢出或者到根结点为止，具体操作举例如下： 特别提及B-树的删除。相对应地，在删除时涉及到结点合并； 如果被删结点非叶子结点，则用被删关键字的前驱或后继替代，并对应地在原位置删除即可； 如果被删结点为叶子结点： >所在结点关键字个数>=m/2，则可直接删除； >否则，如果该结点的兄弟结点（左或右）关键字个数>=m/2，则可轮替其父结点、兄弟结点中的关键字，具体操作举例如下： >否则，将其父结点中关键字下放到兄弟结点中，依次递归直到所有结点中关键字个数满足B-树性质或者到根结点为止，具体操作举例如下： 9.4.4B+树的定义 B+树是应数据库所需而出现的一种B-树的变形树。和B-树相比，B+树： >分支结点不记录关键字值个数，即有n个关键字的结点只有n个子结点； >非叶子结点只起到索引作用，也就是说其包含的值在叶子结点部分均会出现，即叶子结点数=记录数； >叶结点被链接成一个不等长链表，故多出一个指向最左边的叶结点的入口，即有两种查找方式；不论哪种方式，必然需要查找到叶子结点所在层。 9.5散列文件 9.5.1散列文件的基本概念 散列函数：把关键字映射成该关键字对应的地址的函数，记为H(k)=Addr，Addr可以使数组下标、索引或内存地址； 同义词：被映射到同一地址的不同关键字互为同义词，这种现象为冲突； ASL平均查找长度只依赖于装填因子（记录数n/表长m）； 查找效率取决于散列函数的定义、冲突的处理方法和装填因子大小。 9.5.2散列函数的构造 >直接定址法：H(k)=ak+b； >除留余数法：H(k)=kMODp，p为小于等于地址范围的素数； >其他：数字分析法；平方取中法；叠加法；基数转换法；随机数法。 9.5.3冲突的处理方法 >开放定址法：H'(key)=(H(key)+d_i)/m； ①线性探测再散列：d_i=i，即顺序查找下一空闲单元； 这种方法容易造成元素的聚集（堆积），从而降低查找效率。 ②二次探测再散列：d_i=i^2，表长必须为4k+3形式的素数； ③伪随机探测再散列； >再散列法：多个散列函数； >链地址法：将所有同义词存储到同一条链表中。 9.6题目与总结 【王道7.3选择第9题】【2013408真题】在一棵高度为2的5阶B树中，所含关键字的个数至少是？ 首先对于根结点，至少有2个子结点，即至少有1个关键字； 然后对于深度为2的一层非叶子结点，至少有5/2=3（向上取整）个子结点，即至少有2个关键字； 故关键字至少有1*1+2*2=5个。 这类型的问题的分析方式全部统一如此，切记，m阶B树是m叉树，但m叉树不代表一定存在结点有m个子结点！ 比如这道题，就不要去考虑哪一个结点必须得安排上4个子结点。 【王道7.4选择第18题】【2019408真题】现有长度为11且初始为空的散列表HT，散列函数是H(key)=key%7，采用线性探查法解决冲突，将关键字序列87,40,30,6,11,22,98,20依次插入HT后，HT查找失败的平均查找长度是？ 哈希值范围为0~6，故查找失败对应的地址有7个。关键字序列哈希后对应的散列地址分别为0~7；故对于需要查找的对应地址为0的关键字，需要从0到8依次查找一次，共计9次；地址为1的关键字，需要从1到8查找8次，以此类推。 故ASL=(9+8+...+3)/7=6。 10.1排序的基本概念 10.1.1排序的定义 10.1.2排序的功能 对任意n个关键字排序的比较次数至少为log(n!)向上取整。 10.1.3排序的分类 稳定性：对于相等的两个元素，如果排序后先后顺序依旧不变，则该排序算法是稳定的。 10.2插入排序法 10.2.1核心思想 从第i位开始，每次循环将第1到i-1位视作已排序部分，第i到n位为未排序部分，在已排序部分中将第i位的元素插入到合适的位置，以此类推，共需要循环n-1次； 10.2.2算法 10.3选择排序法 10.3.1核心思想 每次从第i个数到第n个数中找到最小的元素，将这个元素和第i个位置上的元素交换。 10.3.2算法 10.4冒泡排序法 10.4.1核心思想 从第1位开始扫描，检查相邻的两个元素，如果前一个元素大于后一个元素，则交换两个元素的位置，一直扫描到第n位； 扫描完后，能且仅能确定第n个元素为整个序列的最大值，则下一轮扫描为从第1位到第n-1位，并确定第n-1位为倒数第二大元素，以此类推，扫描n-1次后，完成排序。 10.4.2算法 10.5Shell排序法 10.5.1核心思想 希尔（Shell）排序是插入排序的一种，相当于分治进行多次直接插入排序，每次只对间距为固定长度的几个元素排序； 目前希尔提出的第一段排序间距为d_1=n/2，递推公式d_i+1=d_i/2，最后一段等于1； 仅适用于顺序存储。 10.5.2算法 10.6快速排序法 10.6.1核心思想 快速排序是交换排序的一种。上述《排序十讲》已经有详细介绍，不过似乎不仅划分方式没有明确，如何移动也是有不同的做法的； 从结果而言，这些做法是无异的，并且也都属于O(nlogn)的范畴内，但效率上存在一定差异，更重要的是目前涉及到各种理论操作的题目，比如求问使用快速排序第一趟结果如何，或者反而求之，就会因不同做法而不同。目前看到的三种做法在下面提到。 10.6.2算法步骤 对于如何移动元素，有三种做法： ①来自之前的做法是，直接平移元素，即保留所有小于或大于基准数的元素的相对顺序；这样常数肯定是较高的，以为需要进行多次循环； ②来自某校课件的做法是，从左到右找大于基准数的数，从右到左找小于基准数的数，并交换，直到两个指针重叠，再继续向左找下一个小于基准数的数，将其与基准数交换。 ③来自王道教材（严蔚敏《数据结构》）的做法和第二种差不多，只是它会把基准数一开始就单独列出并空缺出一个位置，然后左右指针依次找大于/小于基准数的数并将其移动到空缺位，直到两个指针重叠，将基准数填入即可（我觉得我讲得都比王道清楚，不太理解王道为什么一没文字描述二图也画得一般）。 在已经基本有序的数据中，快速排序算法难以发挥长处。 10.7堆积排序法 10.7.1堆积的定义 10.7.2排序的核心思想 10.7.3排序步骤 10.7.4调整子算法 10.7.5建初始堆积 10.7.6堆积排序算法 10.8二路归并排序法 10.8.1什么是二路归并 10.8.2核心思想 将数列平均划分为两个子序列，分别递归，再次划分为两个子序列，并进行排序，最后逐层回溯将划分的两个子序列合并。 *10.9排序算法总结 在m趟排序后， >冒泡排序、选择排序至少最后（最前）m个数是最终位置； >快速排序、堆排序至少有m个数是最终位置； >插入排序前m个数有序； 插入排序、归并排序在最后一趟排序前，可以所有数都不在最终位置； 在数据基本有序时，快速排序效率最低； 插入排序、选择排序、基数排序的排序趟数与序列初始状态无关； 希尔排序、堆排序在采用链式存储后效率会下降； 冒泡排序是唯一可以提前终止（当本轮排序已经有序时）的排序。 10.10题目 【王道8.3选择第17题】【2019408真题】下列序列中，不可能是快速排序第二趟结果的是？ A.5,2,16,12,28,60,32,72 B.2,16,5,28,12,60,32,72 C.2,12,16,5,28,32,72,60 D.5,2,12,28,16,32,72,60 根据快速排序特性，完成第一趟后必有至少1个数满足其左侧数均小于而右侧数均大于的情况；完成第二趟后必有至少2个数，以此类推。但如果这两个数均不在序列最左/右侧，那么则必须要有至少3个数（这一点在这道题前面2014年408真题里的解析却不是这么写的，可以认为是存在漏洞的解释）。 以此，A选项有28,72满足，其中72在最右侧，故满足； B选项有2,72满足，分别在最左、右侧，故满足； C选项有2,32,28满足，故满足； D选项有12,32满足，而均在序列中间，故不满足。 所以选D。 【王道8.4选择第3题】设线性表中每个元素有两个数据项k1,k2，先按照k1从小到大排序，k1相等时按k2从小到大排序，满足这种要求的排序方法是？ A.先按k1进行直接插入排序，再按k2进行简单选择排序 B.先按k2进行直接插入排序，再按k1进行简单选择排序 C.先按k1进行简单选择排序，再按k2进行直接插入排序 D.先按k2进行简单选择排序，再按k1进行直接插入排序 不论是第一轮还是第二轮排序，都是以整体为范围来排序。所以后进行的排序会成为最终关键字，也就是第一关键字，故k1后排序，排除A,C； 直接插入排序是稳定排序，简单选择排序是不稳定排序。第一轮排序是无所谓的，但如果第二轮排序使用不稳定排序，会导致第一轮确定好的k2的大小关系被破坏，故只能选择D。