答是要 8.1查找的基本概念 8.2静态查找表 无序表查找 有序表查找 ●分块查找 ★8.3动态查找表 B树 B·树 8.4哈表
内容提要 8.1 查找的基本概念 8.2 静态查找表 • 无序表查找 • 有序表查找 • 分块查找 8.3 动态查找表 • B树 • B+树 8.4 哈希表
:表示数据元素的数据项 :寻找关键字满足待定条件的数据元素的过 程 查找表:用于查找的数据结构,可能是线性结构 ,也可能是非线性结构 静态查找:查找过程中,不会修改查找表的查找 操作 动态查找:查找的目的是为了修改查找表,通常 是查找成功则删除结点,查找失败则插入结 平均查找长度:查找过程中的平均比较次数, 是比较查找算法优劣的依据
8.1 查找的基本概念 关键字：表示数据元素的数据项 查找：寻找关键字满足特定条件的数据元素的过 程 查找表：用于查找的数据结构，可能是线性结构 ，也可能是非线性结构 静态查找：查找过程中，不会修改查找表的查找 操作 动态查找：查找的目的是为了修改查找表，通常 是查找成功则删除结点，查找失败则插入结 点 平均查找长度：查找过程中的平均比较次数，它 是比较查找算法优劣的依据
石中本的查找 int sqsearch(SQL/ST L, int aidkey dint j, for=O j<L. len, ++ 静态查找表基本 if(L elem]. key==aidkey return j 不作插入和删除操 return -1 作,一般采用顺序 存储结构 (2)有序表的查找 .线性查找算法 int sqsearch(sQLIST L, int aidkey dint ji for=O, <L. len&&L elem. key<=aidkey; j++) if(Lelem key==aidkey return j, return -1
2、静态查找表 (1)无序表的查找 int sqsearch(SQLIST L, int aidkey) {int j; for(j=0;j<L.len;j++) if(L.elem[j].key==aidkey) return j; return -1; } (2)有序表的查找 I.线性查找算法： int sqsearch(SQLIST L, int aidkey) {int j; for(j=0;j<L.len&&L.elem[j].key<=aidkey;j++) if(L.elem[j].key==aidkey) return j; return -1; } 静态查找表基本上 不作插入和删除操 作，一般采用顺序 存储结构
2345678910 int binsearch(SQLIST L, int aidkey) t int low, high, mid, low=0: high=L/en- ( while(lowaidkey high=mid-1; e/se ow=mid+1 return
2、静态查找表(cont’d) (2)有序表的查找 II.折半查找算法： int binsearch(SQLIST L, int aidkey) { int low,high, mid; low=0; high=L.len-1; while(lowaidkey) high=mid-1; else low=mid+1; } return -1; } 1 2 2 3 3 3 3 4 4 4 1+2*2+4*3+3*4=29 O(29/10) 1 2 3 4 5 6 7 8 9 10
农的 根据菱波那契序列的特点对有序表分制 0.618法 菱波那契序列 1235813213455……f(m f(n+2)=f(m)+(n+1) 从20个数的数表中查找一个纪录 先找比较第13个,如果小,再比较第8个, 如果大比较后几个数的第5个 每次都比较位于这个数列的黄金分割点0.618处 比如123456789101112131415 16 查找15的位置
2、静态查找表(cont’d) (2)有序表的查找 III.斐波那契查找： 根据斐波那契序列的特点对有序表分割 0.618法 斐波那契序列 1 2 3 5 8 13 21 34 55······f(n)······ f(n+2)=f(n)+f(n+1) 从20个数的数表中查找一个纪录 先找比较第13个，如果小，再比较第8个，···· 如果大 比较后几个数的第5个······ 每次都比较位于这个数列的黄金分割点0.618处 比如 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 查找15的位置
应用条件:查找表中关键字分布均匀 查找失败时,确定下一个比较对象的方法
2、静态查找表(cont’d) (2)有序表的查找 IV.插值查找： 应用条件：查找表中关键字分布均匀 查找失败时，确定下一个比较对象的方法： high low low L elem high key L elem low key aidkey L elem low key i − + − − = *( ) . [ ]. . [ ]. . [ ]
分块找 将查找表分成若干块,块的大小可以不等,块内可 以是无序的,但块问是有序的。比如,前面块内的所有 关键字都比后面的小 利用索引表记录每个块的起点和终点和块内的最大 关键字。查找时先在索引表中搜索确定,需要在哪个块 内查找,然后,在到查找表特定区间内去搜索 最大关键字5494154 块起始地址0612 36544328492558746365769410138146 01234567891011121314
2、静态查找表(cont’d) (3)分块查找 将查找表分成若干块，块的大小可以不等，块内可 以是无序的，但块间是有序的。比如，前面块内的所有 关键字都比后面的小。 利用索引表记录每个块的起点和终点和块内的最大 关键字。查找时先在索引表中搜索确定，需要在哪个块 内查找，然后，在到查找表特定区间内去搜索。 36 54 43 28 49 25 58 74 63 65 76 94 101138146 ... 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 最大关键字 54 94 154 …….. 块起始地址 0 6 12 ……
3动在查传表 AVL树、B树和B+树都是常用的动态查找 表 (1)B树(B树 的定义:一梯m或称mB树,或者是空树,或者是满足下 面特性的m又排序树ch= parenteral) ①每个结点至多有m棵子树, ②如根结点不是叶,至少有两棵子树, ③除根之外,所有拍终端结点至少有「m1m2向上取整棵 子树,以后记为m2 ④所有的非终端结点含有信息 最m/21个关键字 n所 K k结点
3、动态查找表 (1)B树(B-树) I. B树的定义：一棵m叉(或称m阶)B树，或者是空树，或者是满足下 面特性的m叉排序树(lchild<parent<rchild)： ①每个结点至多有m棵子树， ②如根结点不是叶，至少有两棵子树， ③除根之外，所有非终端结点至少有┌m/2 ┐(m/2向上取整)棵 子树 ,以后记为[m/2] ④所有的非终端结点含有信息 最多[m/2]-1个关键字 Ai是子树指针，Ki是关键字，结点内部关键字有序 ⑤所有叶结点都在同一层次，叫做失败结点。 AVL树、B树和B+树都是常用的动态查找 表 ····· Kn An · n A0 K1 A1 K2
3动在查传表c B Fs冂 18 2 43 78 血4咧 F F
3、动态查找表(cont’d) (1)B树(B-树) II. B树的查找： 过程演示 1 · 35 · 1 · 18 · 2 · 43 · 78 · 1 · 11 · 1 · 27 · 1 · 39 · 2 · 47 · 53 · 1 · 99 · F F F F F F F F F F F 53
3动在查传表c I B 先查找插入的位置,必然在最低一层结点有序插入 但结点的插入可能会导致结点被撑破,需要分两种情况处理: 1)如果插入关键字后叶子结点中的关键字数量=m-1,则插入操 作完毕 (2)如果插入后,叶子结点中的关键字数量是m,则需要将叶子结点 分为2,成为2个听子,中间的关键字携带着新叶子结点的指针上 升到双亲结点中。这就转化为在双亲结点中插入一个关键字的问题
3、动态查找表(cont’d) (1)B树(B-树) III. B树的插入：先查找插入的位置，必然在最低一层结点有序插入 ！但结点的插入可能会导致结点被撑破，需要分两种情况处理： (1)如果插入关键字后,叶子结点中的关键字数量<=m-1，则插入操 作完毕。 (2)如果插入后，叶子结点中的关键字数量是m，则需要将叶子结点 一分为2，成为2个叶子，中间的关键字携带着新叶子结点的指针上 升到双亲结点中。这就转化为在双亲结点中插入一个关键字的问题 了。 这个问题的处理仍需要按照(1)(2)两种情况处理，一直到增加关键字 的结点未满或者新生成根结点为止