第9章查找 9.1 静态查找表《算法与数据结构（C＆Java）（第2版）》 同步教学（电子工业出版社）

9.1 基本概念 9.2 静态查找表 9.3 动态查找表 9.4 哈希表 第9章 查找 9.1 基本概念 ——若表中存在特定元素，称查找成功，应输出该记录； ——否则，称查找不成功（也应输出失败标志或失败位置） 查找表 查 找 查找成功 查找不成功 静态查找 动态查找 关键字 主关键字 次关键字 ——由同一类型的数据元素（或记录）构成的集合。 ——查询(Searching)特定元素是否在表中。 ——只查找，不改变集合内的数据元素。 ——既查找，又改变（增减）集合内的数据元素。 ——记录中某个数据项的值，可用来识别一个记录 ( 预先确定的记录的某种标志 ) ——可以唯一标识一个记录的关键字 例如“学号” 例如“女” 是一种数据结构 ——识别若干记录的关键字 （2）对查找表常用的操作有哪些？ 查询某个“特定的”数据元素是否在表中； 查询某个“特定的”数据元素的各种属性； 在查找表中插入一元素； 从查找表中删除一元素。 （3) 有哪些查找方法？ 查找方法取决于表中数据的排列方式; 讨论： （1）查找的过程是怎样的？ 给定一个值K，在含有n个记录的文件中进行搜索，寻找一个关键字值等于K的记录，如找到则输出该记录，否则输出查找不成功的信息。 例如查字典 针对静态查找表和动态查找表的查找方法也有所不同。 “特定的”=关键字 明确：查找的过程就是将给定的K值与文件中各记录的关键字项进行比较的过程。所以用比较次数的平均值来评估算法的优劣。称为平均查找长度（ASL：average search length）。 其中： n是文件记录个数； Pi是查找第i个记录的查找概率（通常取等概率,即Pi =1/n）; Ci是找到第i个记录时所经历的比较次数。 统计意义上的数学期望值 物理意义：假设每一元素被查找的概率相同，则查找每一元素所需的比较次数之总和再取平均，即为ASL。 显然，ASL值越小，时间效率越高。 （4）如何评估查找方法的优劣？ 静态查找：只查找，不修改： 针对静态查找表的查找算法主要有： 9.2 静态查找表 一、顺序查找（线性查找） 二、折半查找（二分或对分查找） 三、静态树表的查找 四、分块查找（索引顺序查找） 一、顺序查找（ Linear search，又称线性查找 ） （1）顺序表的机内存储结构： typedef struct { ElemType *elem; //表基址，0号单元留空。表容量为全部元素 int length; //表长，即表中数据元素个数 }SSTable; 顺序查找：即用逐一比较的办法顺序查找关键字，这显然是最直接的办法。 对顺序结构如何线性查找？见下页之例； 对单链表结构如何线性查找？函数虽未给出，但也很容易编写；只要知道头指针head就可以“顺藤摸瓜”； 对非线性树结构如何顺序查找?可借助各种遍历操作！ （2）算法的实现： 技巧：把待查关键字key存入表头或表尾（俗称“哨兵”），这样可以加快执行速度。 例： 若将待查找的特定值key存入顺序表的首部（如0号单元），则顺序查找的实现方案为：从后向前逐个比较！ int Search_Seq( SSTable ST , KeyType key ){ //在顺序表ST中，查找关键字与key相同的元素；若成功，返回其位置信息，否则返回0 ST.elem[0].key =key; //设立哨兵，可免去查找过程中每一步都要检测是否查找完毕。当n>1000时，查找时间将减少一半。 for( i=ST.length; ST.elem[ i ].key!=key; - - i ); //不要用for(i=n; i>0; - -i) 或 for(i=1; i<=n; i++) return i; //若到达0号单元才结束循环，说明不成功，返回0值(i=0)。成功时则返回找到的那个元素的位置i。 } // Search_Seq ——返回特殊标志，例如返回空记录或空指针。前例中设立了“哨兵”，就是将关键字送入末地址ST.elem[0].key使之结束并返回 i=0。 讨论② 查找效率怎样计算？ ——用平均查找长度ASL衡量。 讨论① 查不到怎么办？ 讨论③ 如何计算ASL？ 分析： 查找第1个元素所需的比较次数为1； 查找第2个元素所需的比较次数为2； …… 查找第n个元素所需的比较次数为n； 总计全部比较次数为：1＋2＋…＋n = (1+n)n/2 未考虑查找不成功的情况：查找哨兵所需的比较次数为n+1 这是查找成功