第九章 查找

9.1查找的概念9.2静态查找表顺序查找性能分析（ASL） 折半查找性能分析（ASL） 分块查找

9.1查找的概念

?查找表：由同一类型的数据元素（或记录）构成的集合，数据元素之间存在着松散的关系。操作：查询（是否存在表中），检索（属性），插入，删除。查找表分类：静态查找表（仅查询，检索），动态查找表（可插入，删除）。?关键字：是数据元素中某个数据项的值，用于标识（识别）数据元素（或记录）。分为主关键字（可识别唯一一个记录），次关键字（可识别若干记录）。?查找：查找成功（给出记录信息或返回位置），查找不成功（给出空记录或空指针）。为了提高查找效率，可以人为地附加某种确定关系，用另一种结构来表示查找表。查找方法评价：查找速度，占用存储空间，算法本身复杂程度，平均查找长度ASL（ASL越大，时间性能越差）。

9.2静态查找表

静态查找表的顺序存储结构 typedef int KeyType; typedef struct { KeyType key; }ElemType; typedef struct { ElemType *elem; // 数据元素存储空间基址 int length; } SSTable;

顺序查找

无序查找从表的一端逐个进行比较。 int Search_Seq(SSTable ST,KeyType key) { int i; ST.elem[0].key = key; // 设置“哨兵” for (i=ST.length; ST.elem[i].key!=key; --i); return i; } // Search_Seq

性能分析（ASL）

查找成功（等概率）： 查找失败（等概率）：

折半查找

有序表的查找 int Search_Bin(SSTable ST,KeyType key){ int low,mid,high; low = 1; high = ST.length; //置区间初值 while(low <= high) { mid = (low + high) / 2; if (key == ST.elem[mid].key) return mid; else if (key < ST.elem[mid].key) high = mid - 1; else low = mid + 1; } return 0;//不存在待查元素 }

性能分析（ASL）

判定树：描述查找过程的二叉树。有n个结点的判定树的深度为下取整（log2n）+1，折半查找比较次数最多不超过深度。

顺序表和有序表的比较

分块查找

索引顺序表 = 索引（关键字项+指针项） + 顺序表