第的6章 查找.pdfVIP

数据结构与算法 主讲人：陈安龙 电子科技大学信息与软件工程学院 2015年5月19 日8时35分 Design By Chen Anlong 1 第六章 查找 现实生活中，有许多查找的例子： 如到某学校找某个同学， 邮递员按信件收信人地址确定收信人的位置； 在字典中查询某个单词； 从海量信息中找到自己需要的信息等等。 要查询这些信息，涉及到两个主要问题： 一是数据如何组织——查找表， 二是在查找表上如何查找——查找方法 。 2015年5月19 日8时35分 Design By Chen Anlong 2 对查找表基本操作 1）查询某个数据元素是否在查找表中； 2 ）检索某个数据元素的各种属性； 3 ）在查找表中插入一个数据元素； 4 ）从查找表中删去某个数据元素。 2015年5月19 日8时35分 Design By Chen Anlong 3 查找表分类 静态查找表 仅作查询和检索操作的查找表。 动态查找表 有时在查询之后，将“查询”结果“不在查找表 中”的数据元素插入到查找表中；或者，从查找表 中删除其“查询”结果为“在查找表中”的数据元 素。 2015年5月19 日8时35分 Design By Chen Anlong 4 查找过程中，往往是依据数据元素的某个数据项 进行查找，这个数据项通常是数据的关键字。 关键字：是数据元素中某个数据项的值，用以标 识一个数据元素。 若关键字能标识唯一的一个数据元素， 则称谓主关键字。 若关键字能标识若干个数据元素， 则称谓次关键字。 2015年5月19 日8时35分 Design By Chen Anlong 5 查找 根据给定的某个值，在查找表中确定一个其关键字等于 给定值的数据元素。 若查找表中存在这样一个记录，则称“查找成功”。查找 结果给出整个数据元素的信息，或指示该数据元素在查找表中 的位置； 否则称“查找不成功”。 2015年5月19 日8时35分 Design By Chen Anlong 6  查找方法评价  查找速度  占用存储空间多少  算法本身复杂程度  平均查找长度ASL(Average Search Length) ：为确定记 录在表中的位置，需和给定值进行比较的关键字的个数 的期望值叫查找算法的~ n 对含有 n个记录的表， ASL p c i i i 1 n 其中：p 为查找表中第 i个元素的概率，p 1 i i