《算法与数据结构》第7章 检索及基本算法ppt

《《算法与数据结构》第7章 检索及基本算法ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法与数据结构第7章检索及基本算法第7章检索及基本算法7.1检索的概念7.2线性表的检索7.3树表的检索7.4哈希检索检索的概念检索（searching）也称作查找，是一种常用的基本运算。人们几乎每天都要做检索的工作，如在电话号码薄中查找某单位或某个人的电话号码，在字典中查找某个词的含义或读法，在图书馆查找某本书刊的编号，上网在各种数据库中查找某些需要的文献资料等等。在语言翻译的编译程序中要对符号表查找，在数据库系统中要用SQL语言为各种应用设计查找程序，如此等等。检索的概念(续)简言之，检索就是在“大量信息”中查找一个“特定的”信息。这

2、里的大量信息是检索所依赖的数据结构，称之为检索表（searchtable）；检索表是由同一类型的数据元素（或记录）组成的集合。由于集合是一种松散型数据结构，数据元素除了同属于一个集合外再无别的关系，所以检索表是一种非常灵活的数据结构。检索的概念(续)对检索表常做的运算和操作有：查找某个特定的数据元素是否在检索表中；检索某个特定的数据元素的各种属性；在检索表中插入一个数据元素；从检索表中删去某个数据元素。若对查找表只作前两种统称为“检索”的操作，称此类检索表为静态检索表（staticsearchtable）；若在检索的过程中同时插入表中不存

3、在的数据元素，或者从检索表中删除已存在的某个数据元素，称此类检索表为动态检索表（dynamicsearchtable）。检索的概念(续)所谓特定的信息，是指关键字值等于给定值的信息，信息的单位是数据元素或记录。关键字（key）是数据元素（或记录）中某个数据项的值，用它可以标识一个数据元素（或记录）。显然，在一个记录中的每个数据项都可以作为标识该记录的关键字。如人事档案记录结构为：它含有五个关键字，其中性别这个关键字标识了一个职工的性别情况。检索的概念(续)主关键字（primarykey）是指能惟一标识一个数据元素（或记录）的关键字。如上述

4、记录中身份证号码是主关键字，可以惟一标识一条记录；而姓名、性别、年龄、工资级别不能惟一标识一条记录，它们都不是主关键字。辅关键字（secondarykey）是用以标识若干数据元素（或记录）的关键字，也称作次关键字或从关键字。如上述记录中的姓名、性别、年龄、工资级别都是辅关键字。检索的概念(续)检索，就是根据给定的某个值，在检索表中查找一个关键字等于给定值的记录的运算或操作。若在检索表中存在这样的记录，则称检索成功，检索的结果是找到记录的全部信息（或找到记录在检索表中的位置）；若检索表中不存在关键字值等于给定值的记录，则称检索失败，给出在检

5、索表中无要查找的记录的信息提示，并在动态检索时插入关键字等于给定值的记录于检索表中。检索的概念(续)在检索表中查找某个数据元表（或记录）的过程，依赖于这个数据元表（或记录）在查找表中所处的位置；对检索表的检索方法取决于检索表中数据元表（或记录）的组织策略。如在字典中查找一个英文单词，由于字典是按字母顺序编排的，所以不需从第一个单词顺序查找，而只是按待查单词中每个字母在字母表中的位置快速找到该单词；而在数据元素（或记录）之间无任何关系组织起来的集合中查找，则需要从第一个元素（或记录）开始依次顺序查找。检索的概念(续)在计算机中进行检索是对已

6、存入计算机中的数据进行检索，取决于采用何种数据结构来组织检索表；往往需要在数据元素（或记录）之间人为地加上一些关系，即用非集合结构如数组、文件、二叉树、散列表等结构来组织检索表，以便按某种规律来进行检索。依数据组织方式不同，检索分为线性表检索、树表检索和散列表检索等。衡量一个检索算法的优劣，主要依据在检索过程中给定值和关键字的比较操作次数。为此，我们引入平均检索长度的概念。平均检索长度检索算法的平均检索长度（averagesearchlength），即在检索过程中用给定值和关键字进行比较的平均比较次数，或者说是为找到具有给定值关键字的记录

7、所需要的比较次数的平均值。它是为确定记录在检索表中的位置，需要和给定值进行比较的关键字个数的期望值。平均检索长度（续）对于含有n个记录的检索表，检索成功时的平均检索长度为其中，Pi为检索第i个记录的概率，且；一般在不特殊说明的情况下均认为是等概率，即检索每个记录的概率相等，。Ci为找到第i个记录需要和给定值比较的关键字的个数，它随检索方法的不同而不同。第7章检索及基本算法7.1检索的概念7.2线性表的检索7.3树表的检索7.4哈希检索线性表的检索在检索表的数据组织方式中，线性表是最基本的，也是最常用的一种组织方式。本节主要讨论在顺序存储结

8、构实现的线性表上的检索算法，其类型定义描述为typedefstruct{keytypekey;/*关键字类型*/elemtypeother;/*其它域*/}sqlist;sqlistR[n+1