数据结构第九章 查找.pptxVIP

何谓查找表 ？;对查找表经常进行的操作:;仅作查询和检索操作的查找表。;是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。; 根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）。 ; 由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。 为了提高查找的效率， 需要在查找表中的元素之间人为地 附加某种确定的关系，换句话说， 用另外一种结构来表示查找表。;9.1 静态查找表;9.1 静 态 查 找 表;typedef struct { // 数据元素存储空间基址，建表时 // 按实际长度分配，0号单元留空 int length; // 表的长度 } SSTable;;数据元素类型的定义为:;一、顺序查找表; 以顺序表或线性链表表示静态查找表;int location( SqList L, ElemType e, Status (*compare)(ElemType, ElemType)) { k = 1; p = L.elem; while ( k=L.length !(*compare)(*++p, e))) k++; if ( k= L.length) return k; else return 0; };ST.elem;int Search_Seq(SSTable ST, KeyType key) { // 在顺序表ST中顺序查找其关键字等于 // key的数据元素。若找到，则函数值为 // 该元素在表中的位置，否则为0。 ST.elem[0].key = key; // “哨兵” for (i=ST.length; ST.elem[i].key!=key; --i); // 从后往前找 return i; // 找不到时，i为0 }; 定义： 查找算法的平均查找长度 (Average Search Length) 为确定记录在查找表中的位置，需和给定值 进行比较的关键字个数的期望值 其中: n 为表长，Pi 为查找表中第i个记录的概率， 且 　 ， Ci为找到该记录时，曾和给定 值比较过的关键字的个数。; 在等概率查找的情况下， 顺序表查找的平均查找长度为： ; 上述顺序查找表的查找算法简单， 但平均查找长度较大，特别不适用于表长较大的查找表。;ST.elem;int Search_Bin ( SSTable ST, KeyType key ) { low = 1; high = ST.length; // 置区间初值 while (low = high) { mid = (low + high) / 2; if （EQ (key , ST.elem[mid].key) ) return mid; // 找???待查元素 else if ( LT (key , ST.elem[mid].key) ) high = mid - 1; // 继续在前半区间进行查找 else low = mid + 1; // 继续在后半区间进行查找 } return 0; // 顺序表中不存在待查元素 } // Search_Bin;21;折半查找优劣： 折半查找的效率比顺序查找高，但只适用于有序表，而且限于顺序存储结构，对线性链表无法进行折半查找。;在n50时，可得近似结果 ;索引顺序表的查找过程：;例如：;索引顺序查找的平均查找长度ASLbs = 查找“索引”的平均查找长度Lb + 查找“顺序表”的平均查找长度Lw;9.2 动 态 查 找 表;一、二叉排序树（二叉查找树）;一、二叉排序树 （二叉查找树）;（1）若它的左子树不空，则左子树上 所有结点的值均小于根结点的值；;50; 通常，取二叉链表作为 二叉排序树的存储结构;2．二叉排序树的查找算法：;50;从上述查找过程可见，;Status SearchBST (BiTree T, KeyType key,