10.3索引查找表 例.查找表为: 22,12,13,8,9,2033,42,44,38,24,48,60,58,74,49,86,53 索引表为: 关键字项 22 48 86 指针项 7 13
例. 查找表为: 22, 12, 13, 8, 9, 20, 33, 42, 44, 38, 24, 48, 60, 58, 74, 49, 86, 53 索引表为: 关键字项 指针项 22 48 86 1 7 13 10.3 索引查找表
10.3索引查找表 查找分为两步: 1.确定待查记录所在块;(可以用顺序或折半查找 2.在块内顺序查找.(只能用顺序查找) 例如:k=38 第1步:k=38的记录只可能在块2中; 第2步:从r7]开始,直到k= rli. key或诊12为止 关键字项 22 48 指针项 7 13 22,12,13,8,9,20.33,42,44,38,24,4860,58,74,49,86,53
查找分为两步: 1. 确定待查记录所在块; (可以用顺序或折半查找) 2. 在块内顺序查找. (只能用顺序查找) 关键字项 指针项 22 48 86 1 7 13 22, 12, 13, 8, 9, 20, 33, 42, 44, 38, 24, 48, 60, 58, 74, 49, 86, 53 例如: k=38 第1步: k=38 的记录只可能在块2中; 第2步: 从r[7]开始, 直到k=r[i].key 或i>12为止. 10.3 索引查找表
10.3索引查找表 分块查找表的平均查找长度ASL=Lb+Lw 其中:Lb为查索引表确定所在块的平均查找长度; L为在块内查找记录的平均查找长度; 三种查找方法比较 顺序查找 折半查找 分块查找 ASL 大 小 中 表结构要求 无 有序表 分段有序 (块之间有序)
分块查找表的平均查找长度ASL=Lb+Lw 其中: Lb为查索引表确定所在块的平均查找长度; Lw为在块内查找记录的平均查找长度; 三种查找方法比较 顺序查找 折半查找 分块查找 ASL 大 小 中 表结构要求 无 有序表 分段有序 （块之间有序） 10.3 索引查找表
10.4树表查找(动态查找表) 动态查找表的特点是:表结构本身是在查找过程中动态生成的。 即查找不成功时,将该记录插入在动态查找表中。 一、二叉排序树( Binary Sort Tree)(又称为二叉查找树) 1、BST定义: BST或者是一棵空树;或者是具有如下性质的BT: 若左子树非空,则左子树上所有结点的值均小于根结点的值 若右子树非空,则右子树上所有结点的值均大于根结点的值; 左、右子树也为BST
10.4 树表查找（动态查找表） 动态查找表的特点是: 表结构本身是在查找过程中动态生成的。 即查找不成功时，将该记录插入在动态查找表中。 一、二叉排序树（Binary Sort Tree)（又称为二叉查找树） 1、BST定义： BST或者是一棵空树；或者是具有如下性质的BT: • 若左子树非空，则左子树上所有结点的值均小于根结点的值； • 若右子树非空，则右子树上所有结点的值均大于根结点的值； • 左、右子树也为BST
10.4树表查找(动态查找表) 例如: 24 通常,取二叉链表作为二叉排序树的存储结构。中序遍历的结果的序 列是有序的,即(8,12,24,37,45,53,61,78,90,100)。所以 叉排序树本身可以看成是个有序表,但是这棵树不是有序表构成的, 可以由一个无序序列,构造完以后是个有序表 二叉排序树的特点,是用非线形结构来表示一个线形有序表
78 100 61 90 12 37 24 8 45 53 例如： 通常，取二叉链表作为二叉排序树的存储结构。中序遍历的结果的序 列是有序的，即（8，12，24，37，45，53，61，78，90，100）。所以 二叉排序树本身可以看成是个有序表，但是这棵树不是有序表构成的， 可以由一个无序序列，构造完以后是个有序表 。 二叉排序树的特点，是用非线形结构来表示一个线形有序表 。 10.4 树表查找（动态查找表）