数据结构考研知识点,完全贴合大纲.docx

数据结构知识点基本概念1 .数据能被计算机识别、存储和加工处理的信息的载体。2 .数据元素数据的基本单位，可由若干个数据项组成。例如，一 本书的书目信息为一个数据元素，而书目信息的每一 项（如书名，作者名等）为一个数据项。3 .数据结构数据之间的相互关系，即数据的组织形式。它包括三 个要素：数据的逻辑结构（数据之间的逻辑关系）、 数据的存储结构（数据在计算机中的存储方式）和数 据的运算。4 .数据的逻辑结构线性结构：若结构是非空集，则有且仅有一个开始 结点和一个终端结点，并且所有结点都最多只有一个 直接前趋和一个直接后继。栈、队列等都是线性结构。 非线性结构：一个结点可能有多个直接前趋和直接 后继。数组、广义表、树和图等数据结构都是非线性 结构。5 .数据的存储结构顺序存储借助数据在连续的存储空间中的相对位置表示元素 关系，通常用数组描述。链接存储借助数据元素的存储地址的指针表示元素关系。索引存储储存结点信息的同时，建立附加索引表，。索引表由 若干索引项组成。索引项的一般形式是：（关键字、地 址）。有稠密索引和稀疏索引。散列存储按结点的关键字直接计算出存储地址第一章栈、队列和数组一、栈和队列的基本概念1 .栈(Stack)1.1 概念栈是仅在表的一端进行插入和删除运算的线性表， 又称栈为LIFO表(Last In First Out)。栈的修改是按 后进先出的原则进行的。称插入、删除这一端为栈顶，另一端称为栈底。表 中无元素时为空栈。通常栈有顺序栈和链栈两种存储 结构。1.2 栈的基本运算构造空栈：InitStack(S)判栈空：StackEmpty(S)判栈满：StackFull(S)进栈：Push(S,x)退栈：Pop(S)取栈顶元素：StackTop(S)2 队列(Queue)2.1 概念队列是一种运算受限的线性表，又称作FIFO表 (First In First Out),插入在表的一端进行，而删除在 表的另一端进行，队列的操作原则是先进先出的。允许删除的一端称为队头(front),允许插入的一端 称为队尾(rear),队列也有顺序存储和链式存储两种存 储结构。2.2 队列的基本运算置空队：InitQueue(Q)判队空：QueueEmpty(Q)判队满：QueueFull(Q)入队：EnQueue(Q,x)出队：DeQueue(Q)取队头元素：QueueFront (Q)二、栈和队列的顺序存储结构L栈的顺序存储结构L1概念开辟一组地址连续的存储单元，依次存放自栈底到 栈顶的数据元素。设top指针指示栈顶元素的当前位置。基本操作栈示意图:topbase新元素入栈顶时：先入栈, 再移指针top=top+l 删除元素时：先移指针top=topT, 后删栈顶元素栈的长度：top-base当栈满时，做进栈运算必定产生空间溢出，称“上 溢”。当栈空时，做退栈运算必定产生空间溢出，称 “下溢”。上溢是一种错误应设法避免，下溢常用作 程序控制转移的条件。1.2基本运算新元素入栈顶时：先入栈，再移指针top=top+l 删除元素时：先移指针top=top-l,后删栈顶元素 栈的长度：top-base2 .队列的顺序存储结构2.1 概念用一组地址连续的存储单元依次存放从队头到队尾的元素。设队头指针为front,指向队头元素。队尾指针为rear,指向队尾元素的下一个位。当front=rear=0,表示空队列。顺序队列中存在“假上溢”现象，由于入队和出队 操作使头尾指针只增不减导致被删元素的空间无法 利用，队尾指针超过向量空间的上界而不能入队。将队列的头、尾相连形成一个环，构成循环队列。并引 入数学中的模运算计算队头和队尾指针。rearfront2.2 基本运算 入队操作:Q.baseQ.rear=x;Q.rear=(Q.rear+l)%MAXQSIZE;出队操作：x=Q.baseQ.front;Q.front=(Q.front+l)%MAXQSIZE;三、栈和队列的链式存储结构L栈的链式存储结构1.1 概念采用链式存储结构称链栈，并由其栈顶指针惟一确 定。alA设1s为栈顶指针,栈=(al,a2,an), al为栈底元素, an为栈顶元素。an最迟入栈元最早入栈元1.2 基本运算建栈。Void initstack(linkstack *s) s->top=NULL;判栈空。Int stackempty (linkstack *s) return s->top=NULL;)进栈。Void push(linkstack *s,datatype x) (stacknode *p=(stacknode *)malloc(sizeof(stacknode);p->data=x;p->next=s->top;s->top=p;)退栈。Datatype pop(linksatck *s)|datatype x;stacknode *p=s->top;if(stackempty(s)error( "stack underflow");x=p->data;s->top=p->next;free(p);return x;)取栈顶元素。Datatype stacktop(linkstack *s)(if(stackempty(s)error( astack is empty w );return s->top->data;2 .队的链式存储结构2.1 概念用链表示的队列简称为链队列。设两个指针front、 rear分别指示队头和队尾。为了链队列的操作方便， 增加一个头结点，front指向头结点，rear指向队尾元素。如图所示：front - al* -* an a - rear头结点队头元素队尾元素2.2 基本运算建空队Void initqueue(linkqueue *q)(q->front=q->rear=NULL;)判队空。Int queueempty(linkqueue *q)(return q->front=NULL&&q->rear=NULL;)入队。Void enqueue(linkqueue *q,datatype x)(queuenode *p=(queuenode*)malloc(sizeof(queuenode);p->data=x;p->next=NULL;if(queueempty(q)q-front=q->rear=p;elseq->rear->next=p;q->rear=p; 出队。Datatype dequeue(linkqueue *q)(datatype x;queuenode *p;if(queueempty(q)error( aqueue is underflow w );p=q->front;x=p->data;q->front=p->next;if(q->rear=p) q->rear=NULL;free(p);return x;)取队头元素。Datatype queuefront(linkqueue *q) if(queueempty(q)error( "queue is empty");return q->front->data;第二章树与二叉树一、树的基本概念1 .树是n个结点的有限集合，非空时必须满足：只有 一个称为根的结点；其余结点形成m个不相交的子 集，并称根的子树。2 .树的表示方法：树形表示法；嵌套集合表示法; 凹入表表示法；广义表表示法；3 .一个结点拥有的子树数称为该结点的度；一棵树的 度是指树中结点最大的度数。4 .度为零的结点称叶子或终端结点；度不为零的结点 称分支结点或非终端结点5 .根结点称开始结点，根结点外的分支结点称内部结 点；6 .树中某结点的子树根称该结点的孩子；该结点称为 孩子的双亲；7 .树中存在一个结点序列KI, K2,Kn,使Ki为 Ki+1的双亲，则称该结点序列为K1到Kn的路径或 道路；8,树中结点K到Ks间存在一条路径，则称K是Ks 的祖先，Ks是K的子孙；9 .结点的层数从根算起，若根的层数为1,则其余结 点层数是其双亲结点层数加1;双亲在同一层的结点 互为堂兄弟；树中结点最大层数称为树的高度或深 度；10 .树中每个结点的各个子树从左到右有次序的称有 序树，否则称无序树；1L森林是m棵互不相交的树的集合。二、二叉树1 .二叉树的定义及其主要特性1.1 定义树中每个结点至多有两棵子树，且子树有序。满二叉树是一棵深度为k,结点数为2k-l的二叉树; 完全二叉树是至多在最下两层上结点的度数可以 小于2,并且最下层的结点集中在该层最左的位置的 二叉树。1.2 二叉树的五种基本形态0 O(1)空二叉树(2)只有一个根结点（3）有根结点和（4）有根结点和（5）有根结点和左，右左子树右子树子树1.3 二叉树的主要特性二叉树第i层上的结点数最多为深度为k的二叉树至多有2k-l个结点；在任意二叉树中，叶子数为n（）,度为2的结点数为n2,则 n（）=ii2+l;1.4 满二叉树与完全二叉树满二叉树深度为k,且有2k-l个结点。（对满二叉树中的结点约 定编号：自根起，从上到下，从左到右）完全二叉树仅允许最下层右侧分支不满，若按从上到下，从左到 右为树中结点编号，则与满二叉树相同。二者关系：满二叉树是完全二叉树。完全二叉树不一定是满二叉树。1.5 完全二叉树性质n个结点，深度为K的完全二叉树，其K=log2N+l 对一棵n个结点深度为K的完全二叉树上的结点按 层次编码（从第一层到第K层，从左到右），则树中编 号为i的结点（Iv=iv=n）有：a:当i=l时，此点是根；b:当i>l时，i的双亲是i/2 ；c:当2i>n时，i是叶点（无左孩子）；当2iv=n时，2i 是i的左孩子；d:当2i+l>n时,i结点无右孩子；当2i+lv=n时，2i+l 是i的右孩子。2 .二叉树的顺序存储结构和链式存储结构2.1 顺序存储结构用一维数组A作为二叉树的存储结构，Ai表示编号 为i的结点。各个结点编号间的关系：i=l是根结点；i>l则双亲结点是i/2取整；左孩子是方，右孩子是2i+l；（要小于n）i> （n/2取整）的结点是叶子；奇数没有右兄弟，左兄弟是i-1;偶数没有左兄弟， 右兄弟是i+1。0123 4ABC特点：浪费存储空间深度为K,只有K个结点的单支树 需要2K-1个存储单元。（由二叉 树的性质2知，深度为K的二叉树 至多有2K-1个结点）。而真正有 用的只有K个空间，其它绝大多 数空间是空闲的。造成了存储空 间的极大浪费。但顺序存储结构适用于完全二叉树。特点：即不浪费空间，又可以快速确定其结点的位置；对已 知的结点i,其左孩子为2i,右孩子为2i+L双亲为 i/2o结点在存储空间中的相对位置，分好表现出了完全二叉树中结完全二叉树点之间的关系。2.2 链式存储结构链表中每个结点至少含有三个域：数据域、左指针域 和右指针域。Ichild Data rchild指向左孩子指向右孩子t3 .二叉树的遍历根据访问结点的次序不同可分为：先序遍历（前序 遍历或先根遍历），中序遍历（或中根遍历）、后序遍 历（或后根遍历）。遍历线索二叉树。时间复杂度为 0（n） o先序：先访问根结点，然后访问左子树，再访问右子树。中序： 子树。后序： 结点。例1：先访问左子树,先访问左子树,然后访问根结点然后访问右子树,再访问右，再访问根先中后ABCDEFGHIJK CEDFBGAIKJH EFDCGBKJIHA例2：已知先序、中序可以惟一确定一棵二叉树已知：中序：GDHBAECIF先序：ABDGHCEFIGDHB JECIFGDH例3：已知中序、后序可以惟一确定一棵二叉树已知：中序：DBGEAHFIC后序：DGEBHIFCA4 .线索二叉树的基本概念和构造4. 1概念利用二叉链表中的n+1个空指针域存放指向某种遍历 次序下的前趋和后继结点的指针，这种指针称线索。 加线索的二叉链表称线索链表。相应二叉树称线索二 叉树。4. 2构造(D增加两个标志位每个标志位仅占1个存储位(bit)结点结构：IchildLTagdataRTagrchild若LTag=O(Link),则Ichi Id指向左孩子；RTag=O(Link),则rchild指向右孩子；若LTag=l (Thread),则Ichi Id指向线索前趋;RTag=l (Thread),则rchiId指向线索后继。带头结点的中序线索链表：二叉树的头指针Head三、树和森林L树的存储结构双亲表示法（顺序存储结构）：开辟一组连续空间 存储树的结点，每个结点中附设一个指示双亲结点的 双亲域。Data:Parent:特点：找结点双亲容易，但找孩子不容易孩子表示法（链式存储结构）：A.按树的度设结点指针域。特点：每个结点的结构一致，操作简单，但浪费存储空间。树的度=3B.按结点的度设结点指针域特点：每个结点的结构不一致，操作复杂，但节省存储空间。C.按孩子结点排成线性表特点：节省空间，操作也较容易;问题：这种结构不能 反映出树的层 次性特征。每个结点的孩子链表孩子兄弟表示法（二叉树表示法）：在这种表示法 中，树中每个结点有三个域。数据域：存放结点数据左指针域：指向该结点的第一个孩子结点 右指针域：指向该结点的右兄弟结点/data7fchnsib特点：便于实现树的各种操作，节省空间，并且能够描述树的层次结构。2.森林与二叉树的转换二叉树和树都可以用二叉链表作为其存储结构。因 此，以二叉链表作为中间介，可以导出树与二叉树之 间存在对应关系。一棵树与惟一的一棵二叉树一一对 应。举例:二叉树表示注二叉链表二叉树2. 1树转换成二叉树保持双亲和第一个孩子连线，其他连线去掉；兄弟之间连线；使右兄弟结点成为右孩子，使第一个孩子成为左孩 子。2. 2森林转换为二叉树将每棵树转化为二叉树；将各棵二叉树的根相连；使二叉树的根成为右孩子。2. 3二叉树转换成森林若某结点是其父结点的左孩子，则把该结点的右孩 子、右孩子的右孩子、 ，都与该结点的父结 点用线线连；去掉树中所有父结点到其右孩子的连线，生成森 林。3.树和森林的遍历3. 1树的遍历先根遍历先访问树根，再依次先根遍历根的每棵子树。后根遍历先依次后根遍历根的每棵子树，再访问树根。例：先根：ABCEFD后根：BEFCDA二叉树（续上例）先序：ABCEFD 中后：BEFCDA结论:树的先根遍历相当于其转化的二叉树的先序遍历:树的后根遍历相当于其转化的二叉树的中序遍历;3. 2森林的遍历先序（先根）遍历森林A.访问第-一棵树的树根；B.先序遍历第一棵树根的子树森林：C.先序遍历除第一棵树之后,剩余的树构成的森林。先序：ABCDEF中序（后根）遍历森林A.中序遍历森林中第-一棵树的根结点的子树森林;B.访问第一棵树的根结点：C.中序遍历除第一棵树之后剩余的树构成的森林。中序：BCDAFE例:先根:ABCDEFGHJIK （二叉树的先序）后根:BADEFCJHKIG （二叉树的中加森林转化的二叉树:四、树与二叉树的应用1 .概念：树的路径长度是从树根到每一结点的路径长度之 和。将树中的结点赋予实数称为结点的权。结点的带权路径是该结点的路径长度与权的乘积。 树的带权路径长度又称树的代价，是所有叶子的带权 路径长度之和。带权路径长度最小的二叉树称最优二 叉树（哈夫曼树）。具有2n-1个结点其中有n个叶子，并且没有度为1 的分支结点的树称为严格二叉树。对字符集编码时，要求字符集中任一字符的编码都 不是其它字符的编码前缀，这种编码称前缀码。字符出现频度与码长乘积之和称文件总长；字符出 现概率与码长乘积之和称平均码长；使文件总长或平均码长最小的前缀码称最优前缀 码利用哈夫曼树求最优前缀码，左为0,右为1。编码 平均码长最小；没有叶子是其它叶子的祖先，不可能 出现重复前缀。例：给定四个叶子结点a、b、c、d,分别带权0.1、0.1、0.4、0.4, 由它们构成不同的带权二叉树，分别求WPL。0.1 0.1 0.4 0.4WPL=2WPL=1.8WPL=2.12 .哈夫曼树构造算法）根据给定的n个权值wl, w2,wn）构成n棵二叉树 的集合F二Tl, T2,Tn,其中每棵二叉树Ti中只有 一个带权为wi的根结点，其左右子树为空。在F中选取两棵根结点的权值最小的树作为左右子 树构造一棵新的二叉树，且置新的二叉树的根结点的 权值为左右子树上根结点的权值之和。在F中删除这两棵树，同时将新得到的二叉树加入F 中。重复和，直到F只含一棵树为止。这棵树便是 哈夫曼树。3 .前缀码给定一个码的集合序列，若没有一个序列是另一个序列的前缀，则称这个集合中的码为前缀码。例：000, 001, 01, 10, 11前缀码0, 1, 10, 11)不是前缀码特点：前缀码是码长不等的编码，既可以缩短报文的长度，又容易翻译。第四章图一、图的基本概念1 .图：图G是由顶点集V和边集E组成，顶点集是有 穷非空集，边集是有穷集；2 .G中每条边都有方向称有向图；有向边称弧；边的 始点称弧尾；边的终点称弧头；G中每条边都没有方 向的称无向图。3 .顶点n与边数e的关系：无向图的边数e介于 0n(nl)/2之间，有n(n-l)/2条边的称无向完全图； 有向图的边数e介于0n(n-l)之间，有n(n-l)条边的 称有向完全图；4 .无向图中顶点的度是关联与顶点的边数；有向图中 顶点的度是入度与出度的和。所有图均满足：所有顶点的度数和的一半为边数。5 .图G (V, E),如V，是V的子集，是E的子集， 且E，中关联的顶点均在V，中，则G，(V，E，)是G的子 图。6 .在有向图中，从顶点出发都有路径到达其它顶点的 图称有根图；7 .在无向图中，任意两个顶点都有路径连通称连通图; 极大连通子图称连通分量；8 .在有向图中，任意顺序两个顶点都有路径连通称强连通图；极大连通子图称强连通分量；9 .将图中每条边赋上权，则称带权图为网络。二、图的存储及基本操作1 .邻接矩阵表示法用一维数组存储图中顶点的信息；用矩阵(二维数组)表示图中各顶点之间的相邻关系。(1)邻接矩阵的定义图G=(V, E), n个顶点，邻接矩阵用AL . n, 1. n存放：Ai j= "1 若vi, vj或(vi, vj) e E, iwj 0 否则对带权的图：Ai j= rwij 若丫工 vj或(vi, vj) eE, iwj,且权为wijY 0 否则2 .邻接表法（1）无向图的邻接表头结点:表结点:vexdata Firstarcadjvex nextarc顶点构造方法:指向与该顶点 邻接的第一个 邻接点在点的 接中置 邻图位指向下一个 邻接点与同一顶点邻接的所有邻接点构成一个单链表，用表 结点描述；各链表设置表头结点，由头结点描述；各表头结点构成一个顺序表。有向图的邻接表及其逆邻接表邻接表（出度表）：结点结构同无向图。以Vi为顶点的邻接点单链表上的结点都是以vi为弧尾的邻接点。顺序表部分定义同无向图的邻接表。逆邻接表（入度表）：结点结构同无向图。以Vi为顶点的邻接点单链表上的结点都是以vi为弧头的邻接点。顺序表部分定义同无向图的邻接表。3 .邻接矩阵表示法与邻接表表示法的比较邻接矩阵是唯一的，邻接表不唯一；存储稀疏图用邻接表，存储稠密图用邻接矩阵；求无向图顶点的度都容易，求有向图顶点的度邻接 矩阵较方便；判断是否是图中的边，邻接矩阵容易，邻接表最坏 时间为O(n)；求边数e,邻接矩阵耗时为0(1?),与e无关,邻 接表的耗时为O(e+n)；三、图的遍历1 .深度优先搜索(DFS)搜索策略：访问当前顶点vi,寻找与vi相邻且未被访问顶点 Vj,若存在，将其作为当前点，访问，并重复上述搜 寻过程。否则(所有邻接点都被访问过)，退回一步，寻找 与前一个顶点相邻的未被访问顶点，访问，并重复上 述过程。若上述过程无法访问图中的所有顶点，则另选一个 新顶点重新开始。深度优先搜索是一种纵向搜索的过程。2 .广度优先搜索(BFS)访问出发点vO,依次访问vO的各个未曾访问过的邻 接点，然后分别从这些邻接点出发重复上述过程。若上述过程无法访问图中的所有顶点，则另选一个 新顶点重新开始。广度优先搜索是一种横向搜索的过程。使用队列结构。四、图的基本应用1 .概念将没有回路的连通图定义为树称自由树。生成树：连通图G的一个子图若是一棵包含G中 所有顶点的树，该子图称生成树。有DFS生成树和 BFS生成树，BFS生成树的高度最小。非连通图生成 的是森林。最小生成树：连通网G=(V,E),边是带权的，因而 G的生成树的各边也是带权的。将生成树的各边的权 值总和称为生成树的权，并把权最小的生成树称为G 的最小生成树。例：用Prim算法求最小生成树连通图如下所示：例：用克鲁斯卡尔算法求最小生成树连通图如下所示:给定带权有向图,2 .最短路径路径的开始顶点称源点，路径的最后一个顶点称终 点。单源最短路径问题源点中间顶点终点路径长度121014301435014,3560uO到其余各顶点的最短路径求从指定源点到图中其余各点的最短路径。3 .拓扑排序3.1 概念AOV网：顶点表示活动，弧表示活动间的优先关系 的有向图。在无回路的AOV网中，所有的活动可以排成一个 线性序列，使得每个活动的所有前驱活动都排在该活 动的前边，称此序列为拓扑序列，由AOV网构成拓 扑序列的过程称为拓扑排序。3.2 拓扑排序算法思想选择有向图中入度为0的顶点输出，并从图中删去 该点相邻弧；重复上述操作，直到图中全部顶点均被输出或图中 已不存在入度为0的顶点（有回路）。第五章动态查找一、平衡二叉树（AVL树）L基本概念查找的同时对表做修改操作（如插入或删除）则相应 的表称之为动态查找表，否则称之为静态查找表。衡量一个查找算法次序优劣的标准是在查找过程 中对关键字需要执行的平均比较次数（即平均查找长 度 ASL）.平衡二叉树（AVL树），或为空树，或为如下性质的二 叉排序树:左右子树深度之差的绝对值不超过1；左右 子树仍然为平衡二叉树.平衡因子BF=左子树深度一右子树深度.平衡二叉树每个结点的平衡因子只能是1, 0,-1。若其绝对值超过1,则该二叉排序树就是不平衡的。如图所示为平衡树和非平衡树示意图：2 .平衡二叉树的算法思想若向平衡二叉树中插入一个新结点后破坏了平衡 二叉树的平衡性。首先要找出插入新结点后失去平衡 的最小子树根结点的指针。然后再调整这个子树中有 关结点之间的链接关系，使之成为新的平衡子树。当 失去平衡的最小子树被调整为平衡子树后，原有其他 所有不平衡子树无需调整，整个二叉排序树就又成为 一棵平衡二叉树。失去平衡的最小子树是指以离插入结点最近，且平 衡因子绝对值大于1的结点作为根的子树。假设用A 表示失去平衡的最小子树的根结点，则调整该子树的 操作可归纳为下列四种情况。2.1 LL型平衡旋转法由于在A的左孩子B的左子树上插入结点F,使A 的平衡因子由1增至2而失去平衡。故需进行一次顺 时针旋转操作。即将A的左孩子B向右上旋转代替 A作为根结点，A向右下旋转成为B的右子树的根结 点。而原来B的右子树则变成A的左子树。2.2 RR型平衡旋转法由于在A的右孩子C的右子树上插入结点F,使A 的平衡因子由-1减至-2而失去平衡。故需进行一次逆 时针旋转操作。即将A的右孩子C向左上旋转代替A 作为根结点,A向左下旋转成为C的左子树的根结点。 而原来C的左子树则变成A的右子树。2.3 LR型平衡旋转法由于在A的左孩子B的右子数上插入结点F,使A 的平衡因子由1增至2而失去平衡。故需进行两次旋 转操作（先逆时针，后顺时针）。即先将A结点的左 孩子B的右子树的根结点D向左上旋转提升到B结点的位置,然后再把该D结点向右上旋转提升到A结 点的位置。即先使之成为LL型，再按LL型处理。如图中所示，即先将圆圈部分先调整为平衡树，然后 将其以根结点接到A的左子树上，此时成为LL型， 再按LL型处理成平衡型。2.4 RL型平衡旋转法由于在A的右孩子C的左子树上插入结点F,使A 的平衡因子由-1减至-2而失去平衡。故需进行两次旋 转操作（先顺时针，后逆时针），即先将A结点的右 孩子C的左子树的根结点D向右上旋转提升到C结 点的位置,然后再把该D结点向左上旋转提升到A结 点的位置。即先使之成为RR型，再按RR型处理。二、B树及其基本操作、B+树的基本概念1.B树的概念一棵m阶B树，或为空树，或为满足下列条件的m叉树：1、所有叶子结点都出现在同一层上。叶子不带 信息。叶子的父亲称为终端结点。既非叶子又非终 端结点的结点称为内结点；%母个非叶子结点，除根外,子树个数在lm/2倒m 之间。若根结点不是终端结点(根结点肯定不是叶 结点)，则其子树个数可以少到2；这里形为x的 式子表示不小于x的最小整数。3、每个非叶子结点，除子树个数等信息外，还要包 含下列形式的内容：(PpKpPKrKn l,Pn)这里，n为结点中实际具有的子树个数，%为关键字 (i=l,n-1),且KjVKj+i (i=l,n-2) Pj(i=l, n)为指向子树根结点的指针，且指针Pj所指子树中 所有结点的关键字值，均小于Kj(i=l,nl),而均 大于K,|(i=2,，n)；以后，我们为了说话方便，称 忠为Kj的左子树，席|为Kj的右子树。2. B树的基本操作2.1 检索B树的检索与二叉排序树类似。在某棵子树 （包括根）中检索关键字key时，首先，在子树 的根（记为r）中搜索，若与某关键字Kj相等，则 表示已找到，结束，否则，在r的子树耳中，按 类似方法继续检索。这里，j满足Kjl<key<Kj为了应用于插入操作，在检索不成功时， 应返回关键字范围包括key的结点的指针，该结 点是叶子。B树的插入与删除都比较复杂，涉及到保持结构和保持语义问题。为了处理方便，B的插入，只在终端结点中插 入。假定要在m阶B树中插入关键字key。设 n=m-l,即n为结点中关键字数目的最大值。首 先，要查找插入位置（定位），由于是在终端结 点中插入，所以要确定它属于那个终端结点，其 方法与上面介绍的检索方法相同。定位的结果是返回了 key所属叶结点的指针p。 定位后，就可以在p结点中插入key。但由于B树结 点的子树个数受限（不超过阶数m）,所以，若p 中的关键字个数小于n,则直接插入适当位置（同 线性结构的插入），否则，插入点的关键字个数溢 出，此时，我们将该结点p 一分为二（称为“分 裂”），设其前后部分分别是pl和p2,然后，将中 点关键字“上抽”至Up的父亲，并令中点关键字的 右指针指向p2,其左指针pl。与插入操作类似，删除操作也是将删除归结到终端 结点中进行。设在m阶B树中删除关键字key。首先需要查找 key的位置，其方法与上面介绍的检索方法相同。找 到key的位置后，即返回了key所属结点的指针q,假 定key是q中第i个关键字叫。若q不是终端结点，则直 接删除key,然后，用R所指子树中的最小键值x代替 %的位置。这里，该x所在结点必为终端结点。这样， 问题就归结为在终端中删除关键字。如果在终端结点p中删除后，关键字数目为不足 m/212 ,则不符合m阶B树的要求，这需要借关键 字，或合并结点。由B树定义的第2条，除根外，子树个数在m/21到 m之间，关键字的数目等于子树个数减2,因此，在 删除关键字时会影响子树的个数，从而破坏B树定义, 所以，需要进行平借、上推、下拉、合并等操作。删除引起的“借”和“合并”过程的图示如图25-3o图25-3一个5阶B树的删除引起的“合并”5阶B树的非终结点的关键字个数，不能低于2,不能大于4三、散列（Hash）表一、哈希表查找的基本概念1、基本思想不直接比较，通过哈希函数建立关键字到哈希表的映射关系（可 能多对一）。建立哈希表时。在哈希表中杳找记录时。keyHash函数Hash地址二、解决冲突的方法1、开放定址法：当冲突发生时，使用某种方法在Hash表中形成一个探查序列，然 后沿着此探查序列逐个单元地查找，直到找到给定关键字或碰到一个 开放的地址(即地址单元为空)为止。插入时：碰到开放的地址，则将待查关键字插入。查找时：碰到开放的地址，则说明查找失败。(1)、线性探测再散列di = (d+i) mod mi=l, 2,m-1m为Hash表表长d为冲突产生时的Hash地址通过i取值的线性变化构造探查序列特点：线性(2)二次探测再散列d2i-1 = (d + i2) mod md2i = (d - i2) mod m K=i<=(m-l)/2特点：将同义词来回散列在第一次产生冲突时的Hash地址的两端探测序列是跳跃似的减少堆积(二次聚集)的发生缺点：不易探测到整个Hash表空间(3)伪随机探测再散列di = (d + Ri) mod mm为Hash表长d为冲突产生时的Hash地址Ri： RI, R2, . , RmT是一个伪随机数序列2、再哈希法当冲突产生时，通过再计算另一个哈希函数地址解决冲突。即为 构造不同的哈希函数。di = RHi(K)i=l, 2,k其中：RHi (K) w RHj(K),即RHi均是不同的Hash函数。优点：不易产生堆积或聚集。缺点：计算量大。3、链地址法将所有关键字为同义词的记录存储在同一单链表中。假设Hash函数产生的哈希地址在区间0mT上，则将Hash表定义 为一个由m个头指针组成的指针数组chainHashm,凡Hash地址为i 的记录都插入到以数组元素chainHashli为头指针的链表中，并保持 同义词在同一线性链表中按关键字有序。优缺点优点：不会产生堆积：空间是动态申请的，适用于造表前无法确 定表长的情况。缺点：空间开销大。三、哈希表的算法分析 哈希表的装填因子_表中填入的记录数_ _n_。一哈希表的长度一 ma体现哈希表的装满程度哈希表的查找效率的决定因素哈希函数解决冲突的方法哈希表的装填因子假设Hash函数均匀的前提下，不同的解决冲突的方法得到的Hash 表的ASL不同，且不是表中关键字个数n的函数，而是装填因子a的函 数。如下表所示：解决冲突的方法平均查找长度ASL成功查找不成功查找线性探测法(l+l/(l-a)/2(1+1/(1 -a)2)/2二次探测、随机探测 、再哈希法-ln(l-a)/a1/( 1-a)链地址法1+ a/2a + exp(-a )ASLa越小，发生冲突的可能性越小。a越大，发生冲突的可能性越大。因此只要a选择合适，不管n多大，哈希表的平均查找长度就会限 定在一个范围之内。第六章排序一、希尔排序(Shell Sort)又称缩小增量排序，是直接插入排序的改进。基本思想：将待排记录序列按增量dh值分成若干 子表进行直接插入排序；然后缩小增量值，再分割， 再排序，直至整个序列“基本有序”时，再对整个序 列做一次直接插入排序。实现过程：将直接插入排序的间隔变为do d的取 值要注意：最后一次必为1;避免d值互为倍数； 关键字比较次数最大为n125；记录移动次数最大为 1.6n125；算法的平均时间是0(/25)；是一种就地的不 稳定的排序。二、快速排序基本思想：每趟让待排表中的第一元素作支点，排 序后入终位k,将原表一分为二，使得rl中 元素小于等于rk,而rk+lrn中元素都大于等于 rk,递归进行，直到表长为1时，排序结束。实现过程：将第一个值作为基准，设置ij指针交替 从两头与基准比较，有交换后，交换j, io i=j时确定 基准，并以其为界限将序列分为两段。重复以上步骤。算法的最好时间是O(nlog2n)；最坏时间是0(，)； 平均时间是O(nlog2n)；辅助空间为O(log2n)；是 种不稳定排序； 三、堆排序实现过程：把序列按层次填入完全二叉树，调整位 置使双亲大于或小于孩子，建立初始大根或小根堆， 调整树根与最