数据结构基础精讲讲义

数据结构基础阶段第一章

绪论数据结构的基本概念2

算法和算法评价1目

录CONTENTS本节思维导图概览一、数据结构的基本概念绪论二、算法和算法评价本节考点题型：选择题、应用题选择题考点：算法相关知识点、时空复杂度应用题考点：计算时间复杂度数据数据结构的基本概念数据元素、数据项数据对象、数据类型(1)

数据是什么？数据信息的载体，是描述客观事物属性的数、字符以及所有能够输入到计算机中并被计算机程序识别和处理的符号的集合。(2)

数据元素、数据项(3)

数据对象、数据类型原子类型结构类型数据数据类型数据对象抽象数据类型(4)

数据结构及其三要素●

数据结构相互之间存在一种或多种特定关系的数据元素的集合逻辑结构存储结构数据结构数据结构三要素数据的运算(5)

逻辑结构与存储结构数据的逻辑结构是指数据元素之间的逻辑关系数据的存储结构是指数据结构在计算机中的表示顺序存储线性结构逻辑结构存储结构链式存储索引存储散列存储非线性结构练习题1、以下数据结构中，（）是非线性数据结构A.树B.字符串C.队列D.栈2、在存储数据时，不仅要存储各数据的值，还要存储（）A.数据的操作方法B.数据元素的类型D.数据的存取方法C.数据元素之间的关系3、链式存储设计时，结点内的存储单元地址（）A.一定连续B.一定不连续C.不一定连续D.部分连续，部分不连续(6)

算法●

算法对特定问题求解步骤的一种描述，是指令的有限序列，其中的每条指令表示一个或多个操作有穷性确定性算法特征可行性输入、输出语句的频度：在算法中被重复执行的次数时间复杂度算法效率的度量算法所耗费的存储空间空间复杂度注：算法原地工作是指算法所需的辅助空间为常量，及O(1)(7)

时间复杂度的计算练习题1、有右图算法，则时间复杂度是（）A.O(n)B.O(nlogn)C.O(³√n)D.O(√n)2、有右图算法，则时间复杂度是（）A.O(n)B.O(n2)D.O(log2n)C.O(nlog2n)3、下列说法，错误的是（）I.算法原地工作的含义是指不需要任何额外的辅助空间II.在相同规模下，复杂度为O(n)的算法在时间上总是优于复杂度为O(n2)

的算法III.同一个算法，实现的语言级别越高，执行效率越低A.IB.I,IIC.IID.III本章小结1、算法的时间复杂度计算---->找准基本语句以及找准循环次数数据结构基础阶段第二章

线性表线性表的定义和基本操作2

线性表的顺序表示1目

录CONTENTS3线性表的链式表示本节思维导图概览一、线性表的定义和基本操作二、线性表的顺序表示三、线性表的链式表示线性表本节考点题型：选择题、编程题选择题考点：线性表的特点、线性表的存储以及基本操作编程题考点：线性表的基本操作(1)

线性表的定义L=（a1,a2,a3,a4,a5,a6）注：线性表是一种逻辑结构，表示元素一对一的相邻关系。顺序表和链表是指存储结构。创建表求表长按值查找按位查找插入元素线性表的基本操作删除元素输出判空销毁练习题1、线性表是n个具有（）的有限序列A.数据表B.字符C.数据元素D.数据项2、以下（）是一个线性表A.由n个实数组成的集合C.所有整数组成的序列B.由100个字符组成的序列D.邻接表3、在线性表中，除开始元素之外，每个元素（），最后一个元素（）A.只有唯一的一个前驱元素C.有多个前驱元素B.只有唯一的一个后继元素D.有多个后继元素F.没有前驱元素E.没有后继元素(2)

线性表的顺序表示顺序表（A1~A5均是整型）地址A1A2A2A4A510001004100810121016申请表空间插入元素顺序表的基本操作删除元素按值查找元素练习题1、下列（）是顺序存储结构的优点A.存储密度大B.插入运算方便D.方便用于各种逻辑结构的存储表示C.删除运算方便2、在n个元素的线性表的数组表示中，时间复杂度为O(1)的操作是（）I.访问第i(1<=i<=n)个结点和求第i(2<=i<=n)个结点的直接前驱II.在最后一个结点后插入一个新的结点III.删除第一个结点Ⅳ.在第i(1<=i<=n)个结点后插入一个结点A.I

B.I、III

C.I、IID.II、III(3)

线性表的链式表示datanext单链表结点结构L={3、4、5}316045NULL12408200816头插法建立链表查找元素插入元素删除元素求表长尾插法按值查找链表的基本操作按位查找(4)

双链表插入元素priordatanext双链表的操作双链表结点结构删除元素NULL345NULL(5)

循环链表34455NULLNULLNULL3(6)

静态链表034512345NULL12-1(7)

顺序表和链表的比较本章小结1、算法的时间复杂度计算---->找准基本语句以及找准循环次数数据结构基础阶段第三章

栈、队列和数组栈1目

录CONTENTS2

队列3数组和特殊矩阵本节思维导图概览一、栈栈队列和数组二、队列三、数组和特殊矩阵本节考点题型：选择题、编程题选择题考点：栈和队列的特点、栈和队列的基本操作、栈和队列的区别编程题考点：栈和队列的基本操作、栈和队列的应用、压缩矩阵的存储(1)栈L={A1,A2,A3,A4,A5}A1A2A3A4A5初始化空栈判断栈是否为空进栈（入栈）出栈（弹栈）取栈顶元素销毁栈栈的基本操作(2)

栈的顺序表示初始化顺序栈的基本操作判空进栈出栈取栈顶元素(3)

共享栈以及栈的链式存储结构0Maxsize-11号栈栈底1号栈顶2号栈顶2号栈栈底00A1041616A2206060A3648080A484^top练习题1、某栈的输入序列为a,b,c,d,下面的4种序列中，不可能为其输出序列的是（）A.a,b,c,dC.d,c,a,bB.c,b,d,aD.a,c,b,d2、3个不同元素依次进栈，有多少种不同的出栈方式（）A.4

B.5

C.6D.73、一个栈的入栈序列为1，2，3，4……n，出栈序列是P

，P

，P

，……P

。若P

=3，则P123n23可能取值的个数是（）A.n-3

B.n-2C.n-1D.无法确定(4)

队列L={A1,A2,A3,A4,A5}A1A2A3A4A5初始化队列判断队是否为空入队Front1Rear5队列的基本操作3出队取队头元素销毁队(5)

队列的顺序存储结构Front1Rear53(6)

循环队列RearFront初始化判队空入队循环队列的操作出队(7)

队列的链式存储结构FrontRearA1A2A3A4初始化判队空入队链式队列的基本操作出队(8)

双端队列FrontRearA1A2A3A4A5FrontRearA1A2A2A3A3A4A4A5FrontRearA1A5练习题1、栈和队列的主要区别在于（）A、它们的逻辑结构不一样C、所包含的元素不一样B、它们的存储结构不一样D、插入、删除操作的限定不一样2、一个队列的入队顺序是1，2，3，4。则出队顺序是（）A、4，3，2，1B、1，2，3，4C、1，4，3，2D、3，2，4，13、一个链队列中，队头指针为Front，队尾指针为Rear，x所指向的元素需要入队，则需要执行的操作是（）A、front=x，front=front->nextB、x->next=front->next，front=xC、rear->next=x，rear=xD、rear->next=x，x->next=NULL,rear=x括号匹配递归栈应用表达式求值前缀表达式（波兰表达式）中缀表达式三种表达式后缀表达式（逆波兰表达式）表达式求值三种表达式之间转换前、后缀表达式求值常见的算数表达式（（

15/（

7-2））*2）-（

2+3）前缀、中缀、后缀表达式前缀表达式+ab中缀表达式后缀表达式a+bab+a+b-cab+c--+abca+b-c*dab+cd*--+ab*cd后缀表达式中缀表达式（手算）后缀表达式的计算（手算）后缀表达式的计算（机算）中缀表达式前缀表达式（手算）前缀表达式的计算（机算）后缀表达式中缀表达式（机算）中缀表达式的求值（机算）练习题1、已知程序如右，程序运行时使用栈来保存调用过程的信息，则栈底到栈顶保存的信息依次对应的是（）A、main()->S(1)->S(0)C、main()->S(0)->S(1)B、S(0)->S(1)->main()D、S(1)->S(0)-main()2、假设栈初始为空，将中缀表达式a/b+(c*d-e*f)/g转换为等价的后缀表达式过程中，当扫描到f时，栈中的元素依次是（）A、+(*-B、+(-*C、/+(*-*D、/+-*(9)

数组以及特殊矩阵的存储inta[5]={1,2,3,4,5}一维数组二维数组数组inta[2][3]={1,2,3,4,5,6}对称矩阵三角矩阵三对角矩阵稀疏矩阵特殊矩阵对称矩阵的压缩存储a11a21a31a12a22a32a13a23a33a14a24a34a41a42a43a44三角矩阵的压缩存储a11a21a31ccccca22a32ca33a41a42a43a44三对角矩阵的压缩存储a11a210a12a22a3200a23a330a3400a43a44稀疏矩阵的压缩存储a110000a220a23000a340000练习题1、对n阶对称矩阵压缩存储时，需要表长为（）的顺序表A、n/2B、n*n/2C、n*(n+1)/2D、n*(n-1)/22、二维数组A按行优先存放方式存储，每个元素占1个存储单元。若A[0][0]的存储地址是100，A[3][3]的存储地址是220，则元素A[5][5]的存储地址是（）A、295B、300C、301D、3063、将一个12*12的对角矩阵M的上三角部分元素Mij（1<=i<=j<=10）按行优先存放在C语言的一维数组N中，元素M6，6在N中的下标是（）A、50B、51C、55D、66本章小结1、栈和队列的特性：给出入栈或入队序列，得出出栈或出队序列2、循环队列的队空和队满条件3、表达式求值以及括号匹配4、特殊矩阵的压缩存储（下标计算）数据结构基础阶段第四章

串串的定义和实现2

模式匹配1目

录CONTENTS本节思维导图概览一、串的定义和实现栈队列和数组二、模式匹配本节考点题型：选择题、应用题选择题考点：next数组、nextval数组的计算、模式匹配中元素的比对应用题考点：next数组、nextval数组的计算、模式匹配过程(1)

串的定义s=’helloworld’赋值复制将

赋值为StrAssign(&T,hello)//

ThelloStrCopy(&T,s)//

T把串

的值复制给串sStrEmpty(s)//判断s是否为空串，是则返回true，否则false判空StrLength(s)//求s串的长度（不包含\0）求串长串的基本操作清空操作销毁串ClearString(&s)//将s清为空串DestoryString(&s)//回收s的内存空间串连接a

b返回

和

连接之后的新串Concat(&T,a,b)//T求子串位置比较操作求子串

在主串

中的位置Index(S,T)//TSStpare(S,T)//S

T比较串

和顺序存储表示串的存储结构链式存储表示(2)

简单模式匹配i主串S：a1b2ca4cdab8cbac3567910111212b345a模式串T：

acbj(3)

KMP算法i123456789101112

1314

15主串S1a23456模式串Tbaabcj(4)

求next数组(5)

next数组的优化(6)

求nextval数组练习题1、已知串’aaab’，其next数组为（）A、0123C、0231B、0112D、12112、串‘ababaaababaa’的nextval数组为（）A、0，1，0，1，1，2，0，1，0，1，0，2B、0，1，0，1，1，4，1，1，0，1，0，2C、0，1，0，1，0，4，2，1，0，1，0，4D、0，1，1，1，0，2，1，1，0，1，0，43、设主串为‘abaabaabcabaabc’,模式串‘abaabc’，采用kmp算法进行模式匹配，直到匹配成功时，字符间的比较次数是（）A、9B、10C、12D、15本章小结1、next数组的求法（next[1]=0、next[2]=1）数据结构基础阶段第五章

树与二叉树树的基本概念12

二叉树的概念3

二叉树的遍历和线索二叉树目

录CONTENTS4树、森林5

树与二叉树的应用本节思维导图概览一、树的基本概念二、二叉树的概念树与二叉树三、二叉树的遍历与线索二叉树四、树、森林五、树和二叉树的应用本节考点题型：选择题、应用题选择题考点：树和二叉树的性质、二叉树的构建、二叉树的遍历应用题考点：树、森林与二叉树的转换、哈夫曼编码的计算、树和二叉树的性质、二叉树的构建、二叉树的遍历(1)

树的基本概念树的特性任何一颗非空树应该满足：1、有且仅有一个特定的根节点2、当n>1时，其余节点分为m（m>0）个互不相交的有限集T

T

，T

……T

，其中每个集合1，

23N本身又是一棵树，称为根子树(2)

森林(3)

常考的性质极的小知识度为m的树m叉树任意结点的度<=m任意结点的度<=m至少有一个结点的度为m一定是非空树，至少有m+1个结点可以所有结点的度都小于m可以是空树(4)

二叉树二叉树是n（n>=0）个结点的有限集合。满足以下要求：1、或者为空二叉树（n=0时）2、或者由两颗互不相交左右子树构成（左右子树又是一颗二叉树）(5)

满二叉树与完全二叉树●

满二叉树●

完全二叉树高为h时，含有2h-1个结点的二叉树的与所对应的满二叉树的结点编号完全一致(6)

二叉排序树和平衡二叉树●

二叉排序树●

完全二叉树左子树所有的关键字都小于跟结点的关键字右子树所有的关键字都大于根节点的关键字左右子树又是一颗二叉排序树树上任意一个结点的高度之差小于1(7)

二叉树的性质1、n

=n

+1（n

：度为0的结点个数；n

：度为1的结点个数；n

：度为2的结点个数）0

20122、非空二叉树第k层最多有2k-1个结点3、高为h的二叉树最多有2h-1个结点（h>=1）4、具有n个结点的完全二叉树的高度为log

（n+1）向上取整或log

（n）向下取整+1；结点i所在的22层次为log2i向上取整+1顺序存储结构二叉树的存储链式存储结构(8)

二叉树的顺序存储(9)

二叉树的链式存储先序遍历中序遍历后序遍历顺序遍历二叉树的遍历层次遍历顺序遍历AFBCE

G层次遍历AFBCE

G(10)

由遍历序列构建二叉树1、先序和中序序列构造相应二叉树先序：ABCDEFGHIJ中序：CDBFEAIHGJ2、中序和后序序列构造相应二叉树中序：BDCEAFHG后序：DECBHGFA3、层次序列和中序序列构造相应二叉树层次序列：ABCDEFG中序：DBEAFCG前序线索二叉树中序线索二叉树后序线索二叉树线索二叉树(11)

线索二叉树(12)

中序线索二叉树的构造（手动模拟）(13)中序线索二叉树的构造（代码实现）(14)前序线索二叉树的构造（代码实现）(15)中序线索二叉树找前驱和后继1点后继为该结点rchild指向结rtag0后继为右子树的最左下结点前驱为该结点lchild指向结1点ltag0前驱为左子树的最右下结点(16)先序线索二叉树找后继1点后继为该结点rchild指向结rtag0(17)后序线索二叉树找前驱和后继1点后继为该结点rchild指向结rtagltag01点前驱为该结点lchild指向结0双亲表示法树的存储结构孩子表示法孩子兄弟表示法一、双亲表示法AFBCE

GI二、孩子表示法AFBCE

GI三、孩子兄弟表示法AFBCE

GI树转二叉树树森林和二叉树的转换森林转二叉树二叉树转树二叉树转森林一、树转二叉树二、森林转二叉树三、二叉树转树四、二叉树转森林先根遍历后根遍历层次遍历树的遍历先序遍历中序遍历森林的遍历(18)哈夫曼树结点的权？结点的带权路径长度？树的带权路径长度（WPL）？哈夫曼树的构造a1eb62cd32哈夫曼编码数据结构基础阶段第六章

图图的基本概念12

图的存储及基本操作3

图的遍历目

录CONTENTS4图的应用本节思维导图概览一、图的基本概念二、图的存储及基本操作三、图的遍历图四、图的应用本节考点题型：选择题、应用题选择题考点：图的性质、图的生成树、图的存储、图的遍历等应用题考点：图的生成树、图的存储、图的遍历、拓扑序列、关键路径等(1)

图的基本概念有向图VS无向图简单图VS多重图顶点的度、入度和出度(2)

一些基础概念连通图、强连通图子图和生成子图连通分量无向图中的极大连通子图称为连通分量强连通分量有向图中的极大连通子图称为强连通分量生成树连通图的生成树是包含图中全部顶点的一个极小连通子图若图中顶点数量为n，则它的生成树包含n-1条边生成森林在非连通图中，连通分量的生成树构成森林边的权、带权图(网)边的权：在一个图中，给每条边赋予有含义的数值，该数值称为该边的权值带权图(网)：边上带权值的图带权路径长度：在一个带权图中，一条路径上所有权值之和，称为该路径的带权路径长度完全图任意两个顶点之间都存在边的图称为完全图稀疏图VS稠密图稀疏图：边很少的图稠密图：边很多的图特殊的图--树练习题1、一个有n个顶点和n条边的无向图一定是（）A、连通的B、无环的D、有环的C、不连通的2、设有无向图G=(V,E)和G1=(V1,E1),若G1是G的生成树，则下列不正确的是（）Ⅰ.G1为G的连通分量Ⅱ.G1为G的无环子图Ⅲ.G1为G的极小连通子图且V1=VA、Ⅰ、ⅡB、只有ⅢC、Ⅱ、ⅢD、只有Ⅰ3、下列关于图的叙述正确的是（）Ⅰ.回路是简单路径Ⅱ.存储稀疏图，用邻接矩阵比邻某省市空间Ⅲ.若有向图存在拓扑序，则该图不存在回路A、仅ⅡB、仅Ⅰ、ⅡC、仅ⅢD、仅Ⅰ、Ⅲ邻接矩阵邻接表图的存储十字链表邻接多重表邻接矩阵邻接矩阵的特殊性质AF1G1H0A

0F

1G

1H

0011100100An的元素An[i][j]等于顶点i到顶点j的长度为n的路径的数目邻接表邻接表VS邻接矩阵十字链表-->有向图邻接多重表-->无向图十字链表VS邻接多重表练习题1、以下关于图的存储，正确的是（）A、邻接矩阵和邻接表表示都唯一B、邻接矩阵表示唯一，邻接表表示不唯一C、邻接矩阵表示不唯一，邻接表表示唯一D、邻接矩阵和邻接表表示都不唯一2、邻接多重表是（）的表示结构，十字链表是（）的表示结构A、无向图不是B、有向图C、无向图和有向图D、都判断是否存在边找出与结点x邻接的边在图中插入顶点x在图中删除顶点x在图中添加边图的基本操作基于邻接表和邻接矩阵在图中删除边找结点x的第一个邻接点找下一个邻接点有向图的操作A0B0CB0

A20^ABC110ABC2^121000C^无向图的操作A0B1CB0

A100221^^^ABC110ABC121101C广度优先搜索(BFS)利用队列图的遍历深度优先搜索(DFS)利用栈广度优先搜索(BFS)手动模拟广度优先搜索(BFS)代码实现成树/森林深度优先搜索(DFS)手动模拟深度优先搜索(DFS)代码实现成树/森林广度优先VS深度优先练习题1、如右图所示，符合深度优先遍历的序列个数是（）1、aebfdc

2、acfdeb

3、aedfcb4、aefdbc

5、aecfdbA、5B、4C、3D、22、对右图进行广度优先遍历，不是广度优先遍历序列的是A、h,c,a,b,d,e,g,fC、d,b,c,a,h,e,f,gB、e,a,f,g,b,h,c,dD、a,b,c,d,h,e,f,gPrim(普里姆)算法“选点”最小生成树Kruskal(克鲁斯卡尔)算法“选边”Prim算法对于一个带权连通无向图G=(V,E)，生成树不同，每棵树的权可能也不同。假设R为G的所有生成树的集合，若T为R中边的权值之和最小的生成树，则称T为G的最小生成树Kruskal算法BFS算法(无权图)单源最短路径Dijkstra算法(带权/无权图)最短路径各顶点最短路径Floyd算法(带权/无权图)BFS算法Dijkstra算法Floyd算法AOV网和拓扑排序AOV网：使用有向无环图(DAG图)表示活动之间的先后关系。顶点表示活动，边表示活动之间活动间的先后关系AOE网和关键路径AOE网：使用有向无环图(DAG图)表示活动之间的先后关系。边表示活动，顶点表示事件，边上的权值表示表示该活动的开销练习题1、对下列所示的无向图，按照Dijkstra算法，写出从顶点1到其他各个顶点的最短路径和最短路径长度数据结构基础阶段第七章

查找查找的基本概念12

顺序查找和折半查找3

树型查找目

录CONTENTS45B树和B+树散列表本节思维导图概览一、查找的基本概念二、顺序查找和折半查找三、树型查找查找四、B树和B+树五、散列表本节考点题型：选择题、应用题选择题考点：查找的次数、散列表相关知识点等应用题考点：计算平均查找长度、处理冲突、查找判定树等基础知识●

查找：在数据集合中寻找满足某种条件的数据元素的过程●

查找表：用于查找的数据集合，由同种类型的数据元素组成●

静态查找表：查找表的操作只涉及数据元素是否在查找表中或只查找满足条件的元素的属性，不涉及插入或删除操作●

关键字：数据元素中唯一标志某个元素的值基础知识●

平均查找长度：在查找过程中，一次查找长度是指需要比较的关键字次数，平均查找长度是所有查找过程中比较关键字次数的平均值平均查找长度：ASL

=∑

PiCin1n：查找表长

Pi：查找到第i个的概率Ci：查找到第i个数据需要比较的关键字次数(1)

顺序查找顺序查找：从头到尾依次查找4565-9130664371顺序查找的平均查找长度4565-9130664371有序表的顺序查找-23-651318224371有序表的顺序查找判定树-23-651318224371(2)

折半查找(二分查找)折半查找：将给定的值k与表中中间元素mid进行比较，若相等，则返回；若k不等于mid则往mid的左边或者右边继续进行比较。折半查找仅适用于有序的顺序表-45

-23-91322667896折半查找的平均查找长度-45

-23-91322667896有序表的折半查找判定树-45

-23-91322667896(3)

分块查找(索引顺序查找)分块查找：将查找表分为若干子块，块内的元素无序，但块间有序。再建立一个索引表索引表中的各个元素含有各块最大的关键字和各块第一个元素的地址，索引表按关键字有序排列example：关键字集合为{87，23，71，60，20，5，31，10，7，30，21，82，77，53}按关键字码分为4个块和索引表索引查找平均长度example：设索引查找和块内查找平均长度为分块查找的平均查找长度L

L和

。则ASL

=LI+LSIS将长度为n的查找表分为b块，每块有s个记录，等概率情况下：索引表采取顺序查找ASL=L

+L

=(b+1)/2+(s+1)/2=(s2+2s+n)/2sIS索引表采取折半查找块内查找平均长度向上取整+(s+1)/2ASL=L

+L

=log

(b+1)IS2练习题1、已知一个长度为16的顺序表L，其元素按关键字有序排列，若采用折半查找法查找L中不存在的元素，则关键字的比较次数最多是（）A、4C、6B、5D、72、下列选项中，不能构成折半查找中关键字比较序列的是（）A、500，200，450，180B、500，450，200，180C、180，500，200，450D、180，200，500，450(3)

树型查找-->二叉排序树(BST)●

二叉排序树50左子树所有的关键字都小于跟结点的关键字右子树所有的关键字都大于根节点的关键字左右子树又是一颗二叉排序树32661375457080二叉排序树的插入5032661345二叉排序树的构造设关键字序列为{44，23，52，11，23}二叉排序树的删除删除叶子结点：直接删除即可50删除结点a有左子树或右子树：则找a子树称为a父节点的子树3266删除结点a有左子树和右子树：则找a的直接后继或直接前驱替代a1375457080二叉排序树的效率设关键字序列为{44，23，52，11，23}(4)

平衡二叉树(L)●

平衡二叉树树上任意一个结点的高度之差小于1●

结点平衡因子结点左子树的高度-结点右子树的高度假设给定关键字序列{15，3，7，10，9，8}构建一颗二叉排序树LL型右单旋转左单旋转RR型平衡调整LR型先左后右双旋转先右后左双旋转RL型练习题1、含有20个结点的平衡二叉树的最大深度为（）A、4B、5C、6D、72、对下列关键字序列，不可能构成某种二叉排序树中一条查找路径的是A、95，22，91，24，94，71B、92，20，91，34，88，35C、21，89，77，29，36，38D、12，25，71，68，33，34(5)

B树(B-树)●

B树又称为多路平衡查找树，B树中所有孩子结点的个数的最大值称为B树的阶，用m表示。一棵m阶B树或为空树或满足以下特性：①树中每个结点至多有m棵子树，至多有m-1个关键字②若根节点不是终端结点，则至少有两棵子树③除根节点之外的所有非叶结点至少有m/2向上取整棵子树，至少有m/2向上取整-1个关键字P0K：为结点i到n的关键字，且K1<K2<K3……<KnP：指向子树的根节点P

所指子树的所有结点的关键字都小于K

P

所指子树中所有关键字都大K1P1K2KnPn④所有非叶结点的结构：n……i-1i，

i于Ki⑤所有的叶子结点都在同一层次上且不带信息查找元素插入元素删除元素B树的操作B树插入结点B树要求：①对m阶B树-->除根节点外，结点的关键字个数n=[⌈

m/2⌉

-1,m-1]②子树0<关键字1<子树1<关键字2<子树2<关键字3……注：新元素一定是插入到最底层的终端节点若在加入关键字后导致结点的关键字个数超过上限，则会从中间位置分裂，中间位置的关键字插入为原来的父节点中，若此时父节点关键字个数也超过上限，则又继续进行分裂操作B树删除结点直接删除删除叶子结点删除关键字找直接前驱/后继删除非叶子结点(6)

B+树●

B+树一棵m阶的B+树需要满足以下条件：①每个分支最多有m棵子树②非叶根结点至少有两颗子树，其他每个分支结点至少有⌈

m/2⌉

棵子树③结点的子树个数与关键字相等④所有叶结点包含全部关键字和指向相应记录的指针，叶结点的关键字按顺序排列且相邻叶节点按大小顺序用指针连接⑤所有的分支结点仅包含它的各个子结点中关键字的最大值和指向其子节点的指针B树VSB+树(7)

散列表(哈希表)●

散列函数把查找表中关键字映射成为关键字对应的地址的函数，记为Hash(key)=Add●

冲突散列函数可能会把不同的关键字映射成为同一个地址，这种情况称为冲突，这些起冲突的关键字称为同义词●

散列表根据关键字而直接进行访问的数据结构，散列表建立了关键字和存储地址的映射关系直接定址法除留余数法数字分析法平方取中法散列函数的构造方法m：散列表长度di：增量序列线性探测法平方探测法双散列法H

=(H(key)+d

)%mii处理冲突方法开放定址法拉链法H

=(H(key)+i*Hash

(key))%mi2i：冲突次数，初值为0把所有同义词存储在一个线性链表中序列{19，14，23，01，68，20，84，27，55，11，10，79}散列函数为：H(key)=key%13散列查找的性能分析序列{19，14，23，01，68，20，84，27，55，11，10，79}散列函数为：H(key)=key%13①通过线性探测发处理冲突②通过拉链法处理冲突数据结构基础阶段第八章

排序排序的基本概念12

插入排序3

交换排序目

录CONTENTS45选择排序归并和基数排序本节思维导图概览一、排序的基本概念二、插入排序排序三、交换排序四、选择排序五、归并和基数排序本节考点题型：选择题、应用题选择题考点：八大排序的模拟、各种排序的比较次数、各种排序的优点等应用题考点：利用各种排序的优势对数据进行操作(1)

排序的基本概念●

排序重新排列表中的元素，使表中的元素按关键字有序的过程●

算法的稳定性若在一个表中，两个元素a,b的关键字相同，在排序之前a排在b之前，若在排序之后a还在b之前，说明这个算法是稳定的；否则说明算法不是稳定的直接插入排序插入排序希尔排序直接插入排序78

2