沈阳农业大学信息与电气工程学院数据结构课件 第八章.ppt

第九章 查找 9.1 静态查找表 9.2 动态查找表 9.3 哈希表 内容包括：查找的基本概念、三种基本查找方法的基本思想和算法、二叉排序树查找的基本思想和算法、散列法基本思想、散列函数的常用构造方法及解决冲突方法。 查找的基本概念 查找又称为查询或检索，是在一批记录中依照某个域的指定域值，找出相应的记录的操作。 在计算机中，被查找的数据对象是由同一类型的记录构成的集合，可称之为查找表（search table）。 在实际应用问题中，每个记录一般包含有多个数据域，查找是根据其中某一个指定的域进行的，这个作为查找依据的域称为关键字（key）。 对于给定的关键字的值，如果在表中经过查找能找到相应的记录，则称查找成功，一般可输出该记录的有关信息或指示该记录在查找表中的位置。若表中不存在相应的记录，则称查找不成功，此时应该给出不成功的信息。 查找算法中的基本运算是记录的关键字与给定值所进行的比较，其执行时间通常取决于比较的次数。因此，通常以关键字与给定值进行比较的记录个数的平均值，作为衡量查找算法好坏的依据。 查找的应用 日常生活中：在电话号码簿中查阅“某单位”或“某人”的电话号码；在字典中查阅“某个词”的读音和含义等等。这里“电话号码簿”和“字典”都可看作一张查找表。 各种系统软件和应用软件中：编译程序中的符号表、信息处理系统中信息表等等。 查找表操作及分类 操作：(1)查询某个“特定的”数据元素是否在查找表中；(2)某个“特定的”数据元素的各种属性；(3)在查找表中插入一个数据元素；(4)从查找表中删去某个数据元素。 分类：若对查找表只作(1)和(2)两种操作，则称此类查找表为静态查找表。若在查找过程中同时插入查找表中簿存在的数据元素，或者从查找表中删除已存在的某个数据元素，则称此类查找表为动态查找表。 9.1 静态查找表 抽象数据类型静态查找表的定义： ADT StaticSearchTable{ 数据对象D: D是具有相同属性的数据 元素的集合。 数据关系R:数据元素同属一个集合。 基本操作P: Create(ST,n); Destroy(ST); Search(ST,key);Traverse(ST,Visit()); } ADT StaticSearchTable 顺序表的查找 顺序查找(Sequential search)也称为线性查找，是采用线性表作为数据的存储结构，对数据在表中存放的先后次序没有任何要求。 顺序查找是最简单的查找方法，它的基本思想是：查找从线性表的一端开始，顺序将各单元的关键字与给定值k进行比较，直至找到与k相等的关键字，则查找成功，返回该单元的位置序号；如果进行到表的另一端，仍未找到与k相等的关键字，则查找不成功，返回0作为查找失败的信息。 顺序查找的线性表定义如下： #define MAXITEM 100 /*最多项数*/ struct element { keytype key; Elemtype data; }; typedef struct sqlist[MAXITEM]; 这里keytype和ElemType可以是任何相应的数据类型，如int、float或char等，在算法中我们规定它们缺省是int类型。 顺序查找算法 int sequsearch (sqlist r, int k, n) { /*n为线性表r中元素个数*/ i=1 while (r[i].key!=k i=n) i++; if(in) i=0; return(i); } 顺序查找算法分析 此函数的主要运算时间是用于循环语句逐单元进行比较判断r[i].key是否等于k，因此顺序查找的速度较慢，最坏的情况查找成功需比较n次，最好的情况是比较1次，如果对每个关键字进行查找的概率相等，则查找成功所需的平均比较次数为(n+1)/2，而查找失败则需比较(n+1)次，时间复杂度为O（n）。 为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度(Average Search Length)。 顺序查找算法分析 顺序查找的平均查找长度 ASLSS=(n+1)/2 (假设每个记录的查找概率相等） 查找概率不等时,应对查找表作特殊处理. 严格说来，查找算法的平均查找长度应是查找成功时的平均查找长度与查找不成功时的平