第九章查找 静态查找表 动态查找表 哈希查找表 91基本概念Pae214 >查找表:是由同一类型数据元素构成的集合 构 静态查找表:只做“查询”或“检索”操作 动态查找表:查询、检索、插入、删除。 关键字:是数据元素中某个数据相的值,用 它可以标识一个数据元素。 主关键字、次关键字 查找:根据给定值,在查找表中确定一个其 关键字等于给定值的数据元素。 查找成功返回位置序号、查找不成功返回0
1 第九章 查找 • 静态查找表 • 动态查找表 • 哈希查找表 数 据 结 构 之 查 找 2 9.1 基本概念(Page 214) ¾ 查找表：是由同一类型数据元素构成的集合。 ¾ 静态查找表：只做“查询”或“检索”操作。 ¾ 动态查找表：查询、检索、插入、删除。 ¾ 关键字：是数据元素中某个数据相的值，用 它可以标识一个数据元素。 主关键字、次关键字 ¾ 查找：根据给定值，在查找表中确定一个其 关键字等于给定值的数据元素。 查找成功返回位置序号、查找不成功返回 0
注意 据结构 比较各种查找算法时间 复杂度和空间复杂度, 查找算法的主要时间用 于“关键字的比较”。 92静态查找表 据>顺序表的查找 构 typedef int KT; typedef struct(KT key ;.ET typedef struct{ ET*elem;数据元素存储空间基址 0为空单元 int length;SsT 查 int Search_ Sq(SST ST, Kt key)i St elem0Jkey=key;/设置哨兵 for(i-STlength; key!=STelem(ikey; i--); return 1;
2 数 据 结 构 之 查 找 3 注意 比较各种查找算法时间 复杂度和空间复杂度， 查找算法的主要时间用 于“关键字的比较”。 数 据 结 构 之 查 找 4 9.2 静态查找表 ¾ 顺序表的查找 typedef int KT ; typedef struct{KT key ; ... }ET; typedef struct{ET *elem; //数据元素存储空间基址， 0为空单元 int length;}SST; int Search_Sq(SST ST, KT key){ St.elem[0].key=key;//设置哨兵 for(i=ST.length ; key!=ST.elem[i].key; i--) ; return i; }
>顺序表的查找算法性能分析 据结构 在等概率的情况下:Pi=1/n >查找成功时的平均查找长度:(n+1)/2 查找不成功时的比较次数:n+1 假设查找成功与不成功的可能性相同, 在等概率的情况下:Pi=1/2n,则顺序 查找的平均查找长度为 ASLsS=(n+1)+(n+1)2)/2=3(n+1)/4 有序表的查找折半查找 数据结构 >折半查找(二分查找):经过一次比较将 表分割成两部分,然后只在表的一部分中 继续进行查找的方法。 mid=(low+high)/2 513192158798088 查 ow= /Lmid= high=8
3 数 据 结 构 之 查 找 5 ¾ 顺序表的查找算法性能分析 在等概率的情况下：Pi=1/n ¾查找成功时的平均查找长度： (n+1)/2 ¾查找不成功时的比较次数： n+1 ¾假设查找成功与不成功的可能性相同， 在等概率的情况下：Pi=1/2n , 则顺序 查找的平均查找长度为： ASLss=((n+1)+(n+1)/2)/2=3(n+1)/4 数 据 结 构 之 查 找 6 ¾ 有序表的查找——折半查找 ¾ 折半查找（二分查找）：经过一次比较将 表分割成两部分，然后只在表的一部分中 继续进行查找的方法。 mid=(low+high)/2 key =13
二分算法描述 s int Search_Bin(SST ST, KT key)t 结 low=l: high-ST length; 构 while(ow=1); 站2、深度为k的二叉树至多有2-1个结点(k>=1); 构3、对任何一棵二叉树T,如果其终端结点数为 n0,度为2的结点数为n,则n=n2+1。 4、具有n个结点的完全二叉树的深度为 t Llog:n+
4 数 据 结 构 之 查 找 7 ¾ 二分算法描述 int Search_Bin(SST ST, KT key){ low=1 ; high=ST. length; while(low=1); 2、深度为k的二叉树至多有2 -1个结点(k>=1); 3、对任何一棵二叉树T，如果其终端结点数为 n0，度为2的结点数为n2，则n0=n2+1。 4、具有n个结点的完全二叉树的深度为: log2 n +1 k i-1
二叉判定树 查找过程可用二 据结构 叉树来描述。树 中每个结点表示 记录,结点 中的值为该记录 在表中的位置 通常这个描述查 找过程的二叉树 为判定树。 6的的國 在该树中,和给 定值进行比较的 次数恰为该结点 在判定树中的层 次 性能分析 比较次数最多: 数据结构 Llog,n 1 不超过判定树的深度 时间复杂度: O(og,n) 此方法只能适用 于有序表,且限 66 于顺序存储结构
5 数 据 结 构 之 查 找 9 ¾ 二叉判定树 ¾查找过程可用二 叉树来描述。树 中每个结点表示 一个记录，结点 中的值为该记录 在表中的位置， 通常这个描述查 找过程的二叉树 为判定树。 ¾在该树中，和给 定值进行比较的 次数恰为该结点 在判定树中的层 次。 数 据 结 构 之 查 找 10 ¾ 性能分析 比较次数最多： log2 n+1 不超过判定树的深度 时间复杂度： O(log2 n) ¾ 此方法只能适用 于有序表，且限 于顺序存储结构
索引顺序表的查找(分块查找)要求 索引表 结 按表中记录的关键字分块,R1,R2…,R1 第R块中所有关键字确定待查记录所在块;(可以用顺序或折半查 数据结构 找) 在块内顺序查找.(块内查找只能用顺序查找) 查找数据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(keydata) 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(keydata 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 (keydata) 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(keydata)){ 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(keydata)) 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 (keydata) ) f->lchild=p; else f->rchild=p; return OK; } return ERROR ; } 数 据 结 构 之 查 找 20 例：将序列（45，24，53，12，24，90） 构造成为二叉排序树