非常实用的数据结构知识点总结

数据结构知识点概括第一章概论数据就是指能够被计算机识别、存储和加工处理的信息的载体数据元素是数据的基本单位，可以由若干个数据项组成数据项是具有独立含义的最小标识单位数据结构的定义逻辑结构从逻辑结构上描述数据，独立于计算机线性结构一对一关系••线性结构多对多关系•存储结构是逻辑结构用计算机语言的实现顺序存储结构如数组••链式存储结构如链表索引存储结构:稠密索引每个结点都有索引项••稀疏索引每组结点都有索引项•散列存储结构如散列表•・数据运算对数据的操作定义在逻辑结构上，每种逻辑结构都有一个运算集合•常用的有检索、插入、删除、更新、排序•数据类型是一个值的集合以及在这些值上定义的一组操作的总称结构类型由用户借助于描述机制定义，是导出类型•抽象数据类型ADT:是抽象数据的组织和与之的操作相当于在概念层上描述问题•优点是将数据和操作封装在一起实现了信息隐藏•程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法算法取决于数据结构算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出评价算法的好坏的因素:算法是正确的；•・执行算法的时间；执行算法的存储空间主要是辅助存储空间；•・算法易于理解、编码、调试时间复杂度是某个算法的时间耗费，它是该算法所求解问题规模n的函数渐近时间复杂度是指当问题规模趋向无穷大时，该算法时间复杂度的数量级评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关时间复杂度按数量级递增排列依次为常数阶对数阶0Iog2n\线性阶0n［线性对数阶0nlog2n\平方阶0n八21立方阶0n八31……k次方阶指数阶02八空间复杂度是某个算法的空间耗费，它是该算法所求解问题规模n的函数■除余法:表长为m,hash=x%m相乘取整法:hash=intm*x*A-intx*A;A=

0.618•随机数法hash=randomx\•处理冲突的方法:开放定址法一般形式为hi=h key+di%mlim-l,开放定址法要求散列表的装填因子aw

1.••・开放定址法类型线性探查法address=hashx+i%m;,二次探查法:address=hashx+iA2%m;,双重散列法address=hashx+i*hashy%m;拉链法是将所有关键字为同义词的结点链接在同一个单链表中••・拉链法的优点・拉链法处理冲突简单，且无堆积现象；链表上的结点空间是动态申请的适于无法确定表长的情况；•・拉链法中c可以大于1,结点较大时其指针域可忽略，因此节省空间；拉链法构造的散列表删除结点易实现♦・拉链法也有缺点当结点规模较小时，用拉链法中的指针域也要占用额外空间，还是开放定址法省空间第十章排序

10.1排序的基本概念

10.2插入排序

10.3选择排序

10.4交换排序本章主要知识点排序的基本概念和衡量排序算法优劣的标准，其中衡量标准有算法的时间复杂度、空间复杂度和稳定性直接插入排序，希尔排序直接选择排序，堆排序冒泡排序，快速排序

10.1排序的基本概念

1.排序是对数据元素序列建立某种有序排列的过程

2.排序的目的便于查找

3.关键字是要排序的数据元素集合中的一个域，排序是以关键字为基准进行的关键字分主关键字和次关键字两种对要排序的数据元素集合来说如果关键字满足数据元素值不同时该关键字的值也一定不同，这样的关键字称为主关键字不满足主关键字定义的关键字称为次关键字

4.排序的种类分为内部排序和外部排序两大类若待排序记录都在内存中，称为内部排序；若待排序记录一部分在内存，一部分在外存，则称为外部排序注外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂得多

5.排序算法好坏的衡量标准⑴时间复杂度——它主要是分析记录关键字的比较次数和记录的移动次数⑵空间复杂度——算法中使用的内存辅助空间的多少3稳定性——若两个记录A和B的关键字值相等，但排序后A、B的先后次序保持不变，则称这种排序算法是稳定的

10.2插入排序插入排序的基本思想是每步将一个待排序的对象，按其关键字大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止简言之，边插入边排序，保证子序列中随时都是排好序的常用的插入排序有直接插入排序和希尔排序两种

10.

2.1直接插入排序L其基本思想是顺序地把待排序的数据元素按其关键字值的大小插入到已排序数据元素子集合的适当位置例1关键字序列T=13,6,3,31,9,27,5,11,请写出直接插入排序的中间过程序列初始关键字序列:初始,6,3,31,9,27,5,11第一次排序:【6,13]，3,31,9,27,5,11第二次排序:[3,6,13】，31,9,27,5,11第三次排序:[3,6,13,31】，9,27,5,11，第四次排序:[3,6,9,13,31]27,5,11第五次排序:[3,6,9,13,27,31】，5,11第六次排序:[3,5,6,9,13,27,31】，11第七次排序:[3,5,6,9,11,13,27,31]注方括号［］中为已排序记录的关键字，下划横线的关键字表示它对应的记录后移一个位置

2.直接插入排序算法public staticvoid insertSortint[]a{int i,j,temp;int n=a.Length;fori=0;in-1;i++{whilej-1tempa[j]{a[j+1]=a[j];j}a[j+1]=temp;初始关键字序列:【13】，6,3,31,9,27,5,11第一次排序【6,13]，3,31,9,27,5,11第二次排序[3,6,13]，31,9,27,5,

113、直接插入排序算法分析⑴时间效率当数据有序时，执行效率最好,此时的时间复杂度为0n;当数据基本反序时，执行效率最差，此时的时间复杂度为On2所以当数据o越接近有序，直接插入排序算法的性能越好2空间效率仅占用1个缓冲单元——01⑶算法的稳定性稳定希尔shell排序又称缩小增量排序

1、基本思想把整个待排序的数据元素分成若干个小组，对同一小组内的数据元素用直接插入法排序；小组的个数逐次缩小，当完成了所有数据元素都在一个组内的排序后排序过程结束

2、技巧小组的构成不是简单地〃逐段分割〃，而是将相隔某个增量d的记录组成一个小组，让增量d逐趟缩短例如依次取5,3,1，直到d=1为止

3、优点让关键字值小的元素能很快前移，且序列若基本有序时，再用直接插入排序处理，时间效率会高很多例2:设待排序的序列中有12个记录,它们的关键字序列T=65,34,25,87,12,38,56,46,14,77,92,23,请写出希尔排序的具体实现过程public staticvoid shellSortint[]a,int[]d,int numOfD{int i,j,k,m,span;int temp;int n=a.Length;form=0;mnumOfD;m++{〃共numOfD次循环span=d[m];〃取本次的增量值fork=0;kspan;k++{〃共span个小组fori=k;in-span;i=i+span{算法的时间复杂度和空间复杂度合称算法复杂度第二章线性表线性表是由nNO个数据元素组成的有限序列n=0是空表；非空表，只能有一个开始结点，有且只能有一个终端结点线性表上定义的基本运算构造空表InitlistL•,求表长:ListlengthL取结点GetNodeL,i•查找:LocateNodeL,x•,插入:InsertListL,x,i删除:DeleteL,i•顺序表是按线性表的逻辑结构次序依次存放在一组地址连续的存储单元中在存储单元中的各元素的物理位置和逻辑结构中各结点相邻关系是一致的地址计算LOCa i=LOCa1+i-1*d;首地址为1在顺序表中实现的基本运算插入平均移动结点次数为n/2;平均时间复杂度均为0n1•删除平均移动结点次数为n-1/2;平均时间复杂度均为0n%•线性表的链式存储结构中结点的逻辑次序和物理次序不一定相同，为了能正确表示结点间的逻辑关系，在存储每个结点值的同时,还存储了其后继结点的地址信息即指针或链X这两部分信息组成链表中的结点结构一个单链表由头指针的名字来命名单链表运算・建立单链表•头插法s-next=head;head=s;生成的顺序与输入顺序相反平均时间复杂度均为OnX・尾插法head=rear=null;ifhead=null head=s;else r-next=s;r=s;平均时间复杂度均为0n・加头结点的算法对开始结点的操作无需特殊处理，统一了空表和非空表查找按序号与查找位置有关，平均时间复杂度均为0n1••寸安值与输入实例有关，平均时间复杂度均为0n I,插入运算:p=GetNodeL,i-1;s-next=p-next;p-next=s;平均时间复杂度均为0n,删除运算p=GetNodeL,i-1;r=p-next;p-next=r-next;free r;平均时间复杂度均为0n单循环链表是一种首尾相接的单链表，终端结点的指针域指向开始结点或头结点链表终止条件是以指针等于头指针或尾指针采用单循环链表在实用中多采用尾指针表示单循环链表优点是查找头指针和尾指针的时间都是01,不用遍历整个链表双链表就是双向链表，就是在单链表的每个结点里再增加一个指向其直接前趋的指针域prior,形成两条不同方向的链由头指针head惟一确定双链表也可以头尾相链接构成双向循环链表双链表上的插入和删除时间复杂度均为

01、顺序表和链表的比较・基于空间顺序表的存储空间是静态分配，存储密度为1；适于线性表事先确定其大小时采用•■链表的存储空间是动态分配，存储密度＜1；适于线性表长度变化大时采用基于时间•顺序表是随机存储结构，当线性表的操作主要是查找时，宜采用•以插入和删除操作为主的线性表宜采用链表做存储结构•若插入和删除主要发生在表的首尾两端，则宜采用尾指针表示的单循环链表•第三章栈和队列栈Stack是仅限制在表的一端进行插入和删除运算的线性表，称插入、删除这一端为栈顶，另一端称为栈底表中无元素时为空栈栈的修改是按后进先出的原则进行的，我们又称栈为LIF0表Last InFirst Out\通常栈有顺序栈和链栈两种存储结构栈的基本运算有六种构造空栈InitStackS•・判栈空StackEmptyS,判栈满StackFullS进栈:PushS,x退栈PopS,取栈顶元素StackTopS在顺序栈中有〃上溢〃和〃下溢〃的现象〃上溢〃是栈顶指针指出栈的外面是出错状态•〃下溢〃可以表示栈为空栈，因此用来作为控制转移的条件•顺序栈中的基本操作有六种:•构造空栈•判栈空•判栈满•进栈・退栈・取栈顶元素链栈则没有上溢的限制，因此进栈不要判栈满链栈不需要在头部附加头结点，只要有链表的头指针就可以了链栈中的基本操作有五种:•构造空栈•判栈空・进栈・退栈・取栈顶元素队列Queue是一种运算受限的线性表，插入在表的一端进行，而删除在表的另一端进行，允许删除的一端称为队头front,允许插入的一端称为队尾rear,队列的操作原则是先进先出的,又称作FIFO表First InFirst Out.队列也有顺序存储和链式存储两种存储结构队列的基本运算有六种置空队InitQueueQ•判队空QueueEmptyQ•判队满QueueFullQ•・入队EnQueueQ,x,出队DeQueueQ取队头元素QueueFrontQ•顺序队列的〃假上溢〃现象由于头尾指针不断前移，超出向量空间这时整个向量空间及队列是空的却产生了〃上溢〃现象为了克服〃假上溢现象引入循环向量的概念，是把向量空间形成一个头尾相接的环形，这时队列称循环队列判定循环队列是空还是满，方法有三种一种是另设一个布尔变量来判断；•第二种是少用一个元素空间，入队时先测试rear+1%m=front满空；第三种就是用一个计数器记录队列中的元素的总数•队列的链式存储结构称为链队列，一个链队列就是一个操作受限的单链表为了便于在表尾进行插入入队的操作，在表尾增加一个尾指针，一个链队列就由一个头指针和一个尾指针唯一地确定链队列不存在队满和上溢的问题在链队列的出队算法中，要注意当原队中只有一个结点时，出队后要同进修改头尾指针并使队列变空第四章串串是零个或多个字符组成的有限序列空串是指长度为零的串，也就是串中不包含田可字符结点X•空白串指串中包含一个或多个空格字符的串•.在一个串中任意个连续字符组成的子序列称为该串的子串，包含子串的串就称为主串子串在主串中的序号就是指子串在主串中首次出现的位置•空串是任意串的子串，任意串是自身的子串•串分为两种串常量在程序中只能引用不能改变；•串变量的值可以改变•串的基本运算有求串长strlencharts•串复制strcpychar*to,char*from•串联接strcatchar*to,char*from•串比较charcmpchar*sl,char*s2•字符定位strchrchar*s,chare•串是特殊的线性表结点是字符，所以串的存储结构与线性表的存储结构类似串的顺序存储结构简称为顺序串顺序串又可按存储分配的不同分为・静态存储分配直接用定长的字符数组来定义优点是涉及串长的操作速度快，但不适合插入、链接操作动态存储分配是在定义串时不分配存储空间，需要使用时按所需串的长度分配存储单元•串的链式存储就是用单链表的方式存储串值，串的这种链式存储结构简称为链串链串与单链表的差异只是它的结点数据域为单个字符为了解决〃存储密度〃低的状况，可以让一个结点存储多个字符，即结点的大小顺序串上子串定位的运算又称串的〃模式匹配〃或〃串匹配〃，是在主串中查找出子串出现的位置在串匹配中，将主串称为目标串，子串称为模式串x这是比较容易理解的，串匹配问题就是找出给定模式串P在给定目标串T中首次出现的有效位移或者是全部有效位移最坏的情况下时间复杂度是0n-m+1m,假如m与n同阶的话则它是0n八2%链串上的子串定位运算位移是结点地址而不是整数第五章多维数组数组一般用顺序存储的方式表示存储的方式有行优先顺序，也就是把数组逐行依次排列PASCAL.C列优先顺序,就是把数组逐列依次排列FORTRAN♦地址的计算方法:,按行优先顺序排列的数组LOCa ij=LOCa11+i-1*n+j-1*d.・按列优先顺序排列的数组LOCa ij=LOCa11+j-1*n+i-1*d.矩阵的压缩存储为多个相同的非零元素分配一个存储空间；对零元素不分配空间特殊矩阵的概念所谓特殊矩阵是指非零元素或零元素分布有一定规律的矩阵稀疏矩阵的概念一个矩阵中若其非零元素的个数远远小于零元素的个数，则该矩阵称为稀疏矩阵特殊矩阵的类型:对称矩阵:满足a ij=a ji1元素总数nn+l/

2.I=max i,j,J=min i,j,LOCa ij=LOC sa

[0]+I*I+l/2+J•*d.・三角矩阵:•上三角阵:k=i*2n-i+l/2+j-i,LOCa ij=LOCsa

[0]+k*d.下三角阵k=i*i+1/2+j,LOCa ij=LOCsa

[0]+k*d.•对角矩阵k=2i+j,LOCa ij=LOCsa

[0]+k*d.•稀疏矩阵的压缩存储方式用三元组表把非零元素的值和它所在的行号列号做为一个结点存放在一起，用这些结点组成的一个线性表来表示但这种压缩存储方式将失去随机存储功能加入行表记录每行的非零元素在三元组表中的起始位置，即带行表的三元组表第六章树树是n个结点的有限集合，非空时必须满足只有一个称为根的结点；其余结点形成m个不相交的子集，并称根的子树根是开始结点；结点的子树数称度；度为0的结点称叶子终端结点；度不为0的结点称分支结点非终端结点；除根外的分支结点称内部结点；有序树是子树有左，右之分的树；无序树是子树没有左，右之分的树；森林是m个互不相交的树的集合;树的四种不同表示方法:,树形表示法;嵌套集合表示法;凹入表示法广义表表示法♦••二叉树的定义是n0个结点的有限集，它是空集（n=0）或由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成二叉树不是树的特殊情形，与度数为2的有序树不同二叉树的4个重要性质二叉树上第i层上的结点数目最多为2A（i-l）（ilX;•深度为k的二叉树至多有（2人k）-1个结点（kl）;•在任意一棵二叉树中，若终端结点的个数为nO,度为2的结点数为n2,则n0=n2+l;•具有n个结点的完全二叉树的深度为int（Iog2n）+

1.•满二叉树是一棵深度为k,结点数为（2八k）-1的二叉树；完全二叉树是满二叉树在最下层自右向左去处部分结点；二叉树的顺序存储结构就是把二叉树的所有结点按照层次顺序存储到连续的存储单元中（存储前先将其画成完全二叉树）树的存储结构多用的是链式存储BinTNode的结构为lchild|data|rchild，把所有BinTNode类型的结点，加上一个指向根结点的BinTree型头指针就构成了二叉树的链式存储结构，称为二叉链表它就是由根指针root唯一确定的共有2n个指针域,n+1个空指针根据访问结点的次序不同可得三种遍历先序遍历（前序遍历或先根遍历），中序遍历（或中根遍历1后序遍历（或后根遍历X时间复杂度为0（n1利用二叉链表中的n+1个空指针域来存放指向某种遍历次序下的前趋结点和后继结点的指针，这些附加的指针就称为〃线索〃，加上线索的二叉链表就称为线索链表线索使得查找中序前趋和中序后继变得简单有效，但对于查找指定结点的前序前趋和后序后继并没有什么作用树和森林及二叉树的转换是唯一对应的转换方法树变二叉树兄弟相连，保留长子的连线•・二叉树变树结点的右孩子与其双亲连森林变二叉树树变二叉树，各个树的根相连•树的存储结构:有双亲链表表示法结点data|parent,对于求指定结点的双亲或祖先十分方便，但不适于求指定结•点的孩子及后代孩子链表表示法为树中每个结点data|next设置一个孩子链表firstchild,并将data|firstchild存放在一个向量中•双亲孩子链表表示法将双亲链表和孩子链表结合•孩子兄弟链表表示法结点结构leftmostchild|data|rightsibing,附加两个分别指向该结点的最左孩子和右邻兄弟的•指针域树的前序遍历与相对应的二叉树的前序遍历一致；树的后序遍历与相对应的二叉树的中序遍历一致树的带权路径长度是树中所有叶结点的带权路径长度之和树的带权路径长度最小的二叉树就称为最优二叉树（即哈夫曼树\在叶子的权值相同的二叉树中，完全二叉树的路径长度最短哈夫曼树有n个叶结点，共有2n-l个结点，没有度为1的结点，这类树又称为严格二叉树变长编码技术可以使频度高的字符编码短，而频度低的字符编码长，但是变长编码可能使解码产生二义性如

00、0L0001这三个码无法在解码时确定是哪一个，所以要求在字符编码时任一字符的编码都不是其他字符编码的前缀，这种码称为前缀码其实是非前缀码\哈夫曼树的应用最广泛地是在编码技术上，它能够容易地求出给定字符集及其概率分布的最优前缀码哈夫曼编码的构造很容易，只要画好了哈夫曼树，按分支情况在左路径上写代码0,右路径上写代码1,然后从上到下到叶结点的相应路径上的代码的序列就是该结点的最优前缀码第七章图图的逻辑结构特征就是其结点顶点的前趋和后继的个数都是没有限制的，即任意两个结点之间之间都可能相关图GraphG=V,E,V是顶点的有穷非空集合，E是顶点偶对的有穷集有向图Digraph:每条边有方向；无向图Undigraph:每条边没有方向有向完全图具有n*n-1条边的有向图；无向完全图具有n*n-1/2条边的无向图；有根图有一个顶点有路径到达其它顶点的有向图；简单路径是经过顶点不同的路径；简单回路是开始和终端重的简单路径；网络是带权的图图的存储结构邻接矩阵表示法用一个n阶方阵来表示图的结构是唯一的，适合稠密图•无向图邻接矩阵是对称的•有向图行是出度，列是入度•建立邻接矩阵算法的时间是On+n八2+e,其时间复杂度为On人2邻接表表示法用顶点表和邻接表构成不是唯一的，适合稀疏图•・顶点表结构vertex|firstedge,指针域存放邻接表头指针邻接表用头指针确定,无向图称边表；•有向图又分出边表和逆邻接表；•邻接表结点结构为adjvex|next,时间复杂度为n+e1,空间复杂度为n+e图的遍历深度优先遍历借助于邻接矩阵的列使用栈保存已访问结点•・广度优先遍历借助于邻接矩阵的行使用队列保存已访问结点生成树的定义若从图的某个顶点出发，可以系统地访问到图中所有顶点，则遍历时经过的边和图的所有顶点构成的子图称作该图的生成树最小生成树图的生成树不唯一，从不同的顶点出发可得到不同的生成树，把权值最小的生成树称为最小生成树MSTX构造最小生成树的算法・Prim算法的时间复杂度为0n^2与边数无关适于稠密图-Kruskal算法的时间复杂度为0Ige,主要取决于边数，较适合于稀疏图最短路径的算法/Dijkstra算法,时间复杂度为0n八2类似于prim算法拓扑排序是将有向无环图G中所有顶点排成一个线性序列，若u,v£EG,则在线性序列u在v之前，这种线性序列称为拓扑序列拓扑排序也有两种方法无前趋的顶点优先，每次输出一个无前趋的结点并删去此结点及其出边，最后得到的序列即拓扑序列•无后继的结点优先每次输出一个无后继的结点并删去此结点及其入边，最后得到的序列是逆拓扑序列•第八章排序记录中可用某一项来标识一个记录，则称为关键字项，该数据项的值称为关键字排序是使文件中的记录按关键字递增或递减次序排列起来基本操作比较关键字大小；改变指向记录的指针或移动记录•存储结构顺序结构、链表结构、索引结构•经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是稳定的，否则排序算法是不稳定的排序过程中不涉及数据的内、外存交换则称之为〃内部排序〃内排序，反之，若存在数据的内外存交换，则称之为外排序内部排序方法可分五类插入排序、选择排序、交换排序、归并排序和分配排序评价排序算法好坏的标准主要有两条执行时间和所需的辅助空间，另外算法的复杂程序也是要考虑的一个因素插入排序:直接插入排序逐个向前插入到合适位置••哨兵监视哨有两个作用作为临变量存放R[i]••是在查找循环中用来监视下标变量j是否越界•直接插入排序是就地的稳定排序时间复杂度为022,比较次数为n+2n-l/2;移动次数为n+4n-1/2;•・希尔排序•等间隔的数据比较并按要求顺序排列，最后间隔为

1.希尔排序是就地的不稳定排序时间复杂度为n八

1.25,比较次数为n八

1.25;移动次数为l.6n

2.25;•交换排序:冒泡排序:自下向上确定最轻的一个自上向下确定最重的一个自下向上确定最轻的一个，后自上向下确定最重的一个••••冒泡排序是就地的稳定排序时间复杂度为n八2,比较次数为nn-1/2;移动次数为3nn-1/2;•快速排序:以第一个元素为参考基准，设定、动两个指针，发生交换后指针交换位置，直到指针重合重复直到排序完成••快速排序是非就地的不稳定排序时间复杂度为0nlog2n，比较次数为nn-1/2;•选择排序:直接选择排序选择最小的放在比较区前••直接选择排序就地的不稳定排序时间复杂度为0n八2I比较次数为nn-1/2;•.堆排序,建堆按层次将数据填入完全二叉树，从int（n/2）处向前逐个调整位置然后将树根与最后一个叶子交换值并断开与树的连接并重建堆，直到全断开•堆排序是就地不稳定的排序，时间复杂度为0（nlog2n）,不适宜于记录数较少的文件•归并排序先两个一组排序，形成（n+1）/2组，再将两组并一组，直到剩下一组为止•归并排序是非就地稳定排序，时间复杂度是0（nlog2n）,•分配排序:箱排序按关键字的取值范围确定箱子数，按关键字投入箱子，链接所有非空箱••箱排序的平均时间复杂度是线性的（n1•・基数排序:•从低位到高位依次对关键字进行箱排序・基数排序是非就稳定的排序，时间复杂度是（d*n+d*rd\各种排序方法的比较和选择彳寺排序的记录数目n;n较大的要用时间复杂度为0（nlog2n）的排序方法；记录的大小（规模）；记录大最好用链表作为存储结构，而快速排序和堆排序在链表上难于实现；•关键字的结构及其初始状态；对稳定性的要求；••语言工具的条件；,存储结构；时间和辅助空间复杂度••第九章查找查找的同时对表做修改操作（如插入或删除）则相应的表称之为动态查找表，否则称之为静态查找表衡量查找算法效率优劣的标准是在查找过程中对关键字需要执行的平均比较次数（即平均查找长度ASL I线性表查找的方法顺序查找逐个查找,ASL=（n+1）/2;二分查找取中点int（n/2）比较,若小就比左区间,大就比右区间用二叉判定树表示ASL=（J（每层结点数*层数））/N.•分块查找要求〃分块有序〃，将表分成若干块内部不一定有序，并抽取各块中的最大关键字及其位置建立有序索引表•二叉排序树（BST）定义是二叉排序树是空树或者满足如下性质的二叉树若它的左子树非空，则左子树上所有结点的值均小于•根结点的值；若它的右子树非空，则右子树上所有结点的值均大于根结点的值；•・左、右子树本身又是一棵二叉排序树二叉排序树的插入、建立、删除的算法平均时间性能是O（nlog2n1二叉排序树的删除操作可分三种情况进行处理・*P是叶子，则直接删除*P,即将*P的双亲*parent中指向*P的指针域置空即可・*P只有一个孩子*child,此时只需将*child和*p的双亲直接连接就可删去*p.•*p有两个孩子，则先将*p结点的中序后继结点的数据到*p,删除中序后继结点关于B-树（多路平衡查找树\它适合在磁盘等直接存取设备上组织动态的查找表，是一种外查找算法建立的方式是从下向上拱起散列技术将结点按其关键字的散列地址存储到散列表的过程称为散列散列函数的选择有两条标准简单和均匀常见的散列函数构的造方法平方取中法:hash=int xA2%100•。