数据结构－查找.pptVIP

基本概念 查找表（Search Table）：是由同一类型的数据元素（或记录）构 成的集合。静态查找表（Static Search Table）：对表只做查找 的操作。动态查找表（Dynamic Search Table）：在查找过程 中同时插入查找表中不存在的数据元素，或者从查找表中删除 已存在的某个数据元素。 关键字（Key）：是数据元素（或记录）中某个数据项的值，用它 可以标识（识别）一个数据元素（或记录）。主关键字 （Primary key） ：可以唯一地标识一个记录。次关键字：用以 识别若干记录的关键字。 查找（Searching）：根据给定的某个值，在查找表中确定一个其关 键字等于给定值的记录或数据元素。若表中存在这样的一个记 录，则称查找是成功的，此时查找的结果为给出整个记录的信 息，或指示该记录在查找表中的位置；否则称查找不成功。 顺序表的查找 静态查找表的顺序存储结构定义 typedef struct { ElemType * elem; // 数据元素存储空间基址，建表时按实际长度分配， // 0号单元留空。 int length; }SSTable; 顺序查找的查找过程 从表中最后一个记录开始，逐个进行记录的关键字和给定值的 比较，若某个记录的关键字个给定值比较相等，则查找成功，找到 所查记录；反之，若直至第一个记录，其关键字和给定值比较都不 相等，则表明表中没有所查记录，查找不成功。 查找算法 int Search_Seq( SSTable ST, KeyType key) { // 在顺序表ST中顺序查找其关键字等于key的数据元素。若找到， // 则函数值为该元素在表中的位置，否则为0。 ST.elem[0].key = key; // “哨兵” for ( i= ST.length; !EQ( ST.elem[i].key, key); --i ); // 从后往前找 return i; // 找不到时， i为0 }// Search_Seq 查找操作的性能分析 衡量查找算法好坏的依据是：其关键字和给定值进行过比较的记录 个数的平均值。这个平均值又称为平均查找长度（ASL）。 定义：为确定记录在查找表中的位置，需和给定值进行比较的关键 字个数的期望值称为查找算法在查找成功时的平均查找长度 （Average Search Length)。 对于含有n个记录的表，查找成功时的平均查找长度为 其中：Pi 为查找表中第I个记录的概率，且 Ci为找到表中其关键字与给定值相等的第I个记录时，和给定值已进 行过比较的关键字个数。 假设 n = ST.length, 则顺序查找的平均查找长度为 ASL = nP1 + (n-1) P2+ … + 2Pn-1 + Pn 假设每个记录的查找概率相等，即Pi = 1/n 则在等概率情况下顺序查找的平均查找长度为 另：P218　式9－4 有序表的查找 以有序表表示静态查找表时，Search函数可用折半查找来实现。 折半查找(Binary Search）的查找过程是：先确定待查记录所在的范 围（区间），然后逐步缩小范围直到找到或找不到给记录为止。 例：已知如下11个数据元素的有序表（关键字即为数据元素的 值）： （05，13，19，21，37，56，64，75，80，88，92） 现要查找关键字为 21 和 85 的数据元素。 假设指针low 和high 分别指示待查元素所在范围的下界和上界，指 针mid 指示区间的中间位置，即mid = 其初值分别为1 和11，即[1，11]为待查范围。 给定值key = 21的查找过程是： （1） 05 13 19 21 37 56 64 75 80 88 92 给定值key = 85的查找过程是： （1） 05 13 19 21 37 56 64 75 80 88 92 折半查找算法