索引顺序表的查找(分块查找)要求 索引表 结 按表中记录的关键字分块,R1,R2…,R1 第R块中所有关键字<Rk+1块中的所有关键字 k=1,2,,L-1,称为“分块有序” 对每块建立一个索引项,包含有两项内 容 关键字项:为该块中最大关键字值; 指针项:为该块第一个记录在表中位置 所有索引项组成索引表 查找过程 >确定待查记录所在块;(可以用顺序或折半查 数据结构 找) 在块内顺序查找.(块内查找只能用顺序查找) 查找数据24 A[2147国索引表 找 2189232424刘S 123456789101l12131415161718
6 数 据 结 构 之 查 找 11 ¾ 索引顺序表的查找（分块查找）要求： ¾ 索引表 ¾ 按表中记录的关键字分块, R1,R2,…,RL 第Rk 块中所有关键字< Rk+1块中的所有关键字 k=1,2,…,L-1, 称为“分块有序” ¾ 对每块建立一个索引项, 包含有两项内 容: ¾ 关键字项 : 为该块中最大关键字值; ¾ 指针项 : 为该块第一个记录在表中位置. ¾所有索引项组成索引表 数 据 结 构 之 查 找 12 ¾ 查找过程 ¾确定待查记录所在块; (可以用顺序或折半查 找) ¾在块内顺序查找. (块内查找只能用顺序查找) 22 1 48 7 86 13 22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 53 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 索引表 查找数据 24
性能分析 ASLL=LL+L 据L为确定块的平均查找长度;L为块内查找次数。 结 若顺序查找:ASLb=Lb+Lw=(n/s+s)2+1 若折半查找:ASLb=Lb+Lv=log2(n/s+1)+s/2 三种查找方法比较 顺序查找 折半查找 分块查找 ASI 大 中 表结构要求 无 有序变 块之间有序 93动态查找表 >二又排序树BST >二叉排序树的定义:page227 构 查找过程 之>二又排序树的插入和删除 二叉排序树的查找分析 含有n个结点的二叉排序树的平均查找长度 和树的形态有关:最差的形态是:单支树 ((n+1)2);最好的形态是:判定树(log2n) 在随机情况下,二叉排序树的平均查找长度 和ogn是等数量级的
7 数 据 结 构 之 查 找 13 ¾ 性能分析 ASLbs=Lb+Lw， Lb为确定块的平均查找长度；Lw为块内查找次数。 若顺序查找： ASLbs=Lb+Lw =(n/s+s)/2+1 若折半查找： ASLbs=Lb+Lw = log2(n/s+1)+s/2 三种查找方法比较 顺序查找 折半查找 分块查找 ASL 大 小 中 表结构要求 无 有序表 块之间有序 数 据 结 构 之 查 找 14 9.3 动态查找表 ¾ 二叉排序树(BST) ¾ 二叉排序树的定义：page 227 ¾ 查找过程 ¾ 二叉排序树的插入和删除 ¾ 二叉排序树的查找分析 含有n个结点的二叉排序树的平均查找长度 和树的形态有关：最差的形态是：单支树 ( (n+1)/2 )；最好的形态是：判定树( log2 n )。 在随机情况下，二叉排序树的平均查找长度 和 log n是等数量级的
据结构 43 53 3 ①OO 7 (6O 24 (9O 78) >查找算法 数据结构 当前BST非空时,将给定值k与当前根结 点的关键字比较 若相等,查找成功,结束;若k小于当前根 结点的关键字,则将左子树作为当前BST 若k大于当前根结点的关键字,则将右子 树作为当前BST; 查 >重复(1)
8 数 据 结 构 之 查 找 15 数 据 结 构 之 查 找 16 ¾查找算法 ¾当前BST非空时，将给定值k与当前根结 点的关键字比较: ¾若相等，查找成功，结束; 若k小于当前根 结点的关键字，则将左子树作为当前BST; 若k大于当前根结点的关键字，则将右子 树作为当前BST; ¾重复(1)
BT SearchBST(BT T, int key 据结构 if((!T) key ==T->data)) return(T); else if(key<T->data) return( SearchBST(T->lchild, key )) else return( SearchBST(T->rchild, key )) Status Search Bit(BT T, BtN &f, btn &p, in 数key){ 菇∥f是p的双亲结点指针 构 p-T; fT; while(p)i if(p->data==key) return TRUE 查 找 else if(key<(p->data f=p; p=p->lchild se f=p; p=p->rchild 3 return FALSE;
9 数 据 结 构 之 查 找 17 BT SearchBST ( BT T,int key ) { if ( ( !T ) || key = =T->data) ) return ( T ); else if (key<T->data) return ( SearchBST ( T->lchild, key ) ); else return ( SearchBST ( T->rchild, key ) ); } 数 据 结 构 之 查 找 18 Status Search_Bit(BT T,BTN &f ,BTN &p, int key){ // f 是 p 的双亲结点指针 p=T; f=T ; while(p){ if(p->data==key) return TRUE; else if(key<(p->data)){ f = p ; p=p->lchild; } else {f = p ; p=p->rchild ; } } return FALSE; }
在二叉排序树中插入关键字为key的结点 * Status Insert Bit(BT T int key )0 s if( Search_Bit(T, f, p, key )) p=(BTN"malloc(sizeof(BTN); p->lchild=p->rchild= NULL; p->data= key if(f)T=p; else if(key<(f->data)) f->lchild=p: else f->rchild=p: return OK; j return ERROR 例:将序列(45,24,53,12,24,90) 数据结构 构造成为二叉排序树 5 查
10 数 据 结 构 之 查 找 19 ¾ 在二叉排序树中插入关键字为 key 的结点 Status Insert_Bit(BT T ,int key ){ if( !Search_Bit(T , f , p , key )){ p=(BTN *)malloc(sizeof(BTN)); p->lchild=p->rchild= NULL; p->data = key ; if(!f ) T= p; else if (key<(f->data) ) f->lchild=p; else f->rchild=p; return OK; } return ERROR ; } 数 据 结 构 之 查 找 20 例：将序列（45，24，53，12，24，90） 构造成为二叉排序树