6数据结构-查找课件.ppt

第九章 查找表;何谓查找表 ？;对查找表经常进行的操作:;仅作查询和检索操作的查找表。;是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。; 根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录） ; 由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。 为了提高查找的效率， 需要在查找表中的元素之间人为地 附加某种确定的关系，换句话说， 用另外一种结构来表示查找表。;9.1 静态查找表;9.1 静 态 查 找 表;数据对象D：; Create(ST, n);;假设静态查找表的顺序存储结构为;一、顺序查找表;一、顺序查找表;int location( SqList L, ElemType e, Status (*compare)(ElemType, ElemType)) { i = L.length; p = L.elem+L.length; while ( i=1 !(*compare)(*p--,e))) i--; if ( i=1) return i; else return 0; } //location;ST.elem;int Search_Seq(SSTable ST, KeyType kval) { // 在顺序表ST中顺序查找其关键字等于 // key的数据元素。若找到，则函数值为 // 该元素在表中的位置，否则为0。 ST.elem[0].key = kval; // 设置“哨兵” for (i=ST.length; --i); // 从后往前找 return i; // 找不到时，i为0 } // Search_Seq;分析顺序查找的时间性能。;顺序表查找的平均查找长度为： ; 若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上。; 顺序查找表的查找算法简单， 但平均查找长度较大，特别不适用于表长较大的查找表。;ST.elem;折半查找算法： 假设有一序列存在数组 r 中，指针low和high分别指示查找范围的下界和上界，mid指示区间的中间位置，即 mid = (low + high) / 2 首先令r[mid].key与给定值k相比较， 如果 (1) r[mid].key = k，则查找成功。（退出） (2) k r[mid].key， 则在[low, mid-1]范围内查找。 (3) k r[mid].key， 则在[mid+1, high]范围内查找;int Search_Bin ( SSTable ST, KeyType kval ) { low = 1; high = ST.length; // 置区间初值 while (low = high) { mid = (low + high) / 2; if （kval == ST.elem[mid].key ) return mid; // 找到待查元素 else if ( kval ST.elem[mid].key) ) high = mid - 1; // 继续在前半区间进行查找 else low = mid + 1; // 继续在后半区间进行查找 } return 0; // 顺序表中不存在待查元素 } // Search_Bin; 先看一个具体的情况，假设：n=11;假设 n=2h-1 并且查找概率相等 则 ;*;n — 表长 (18) s — 块长 (6) b — 块数 (3); ASLbs = Lb + LS 索引表的平均查找长度 块内的平均查找长度; 若都采用顺序查找，则 ASLbs = Lb + Ls = + = (b+1)/2 + (s+1)/2 =(b+s)/2 +1 = ;9.2 动 态 查 找 树 表;?(n) ?(1) ?(n) ?(1);1）从查找性能看，最好情况能达