第8章查找.ppt

基本概念与术语
静态查找表
动态查找表
哈希表查找
小结与习题
第八章查找
1
本章主要内容
本章主要学习静态查找和动态查找方法。静态查找包括顺序查找、二分查找和分块索引查找等,动态查找包括二叉排序树、B树等。作为重点内容本章还介绍了哈希查找及相关知识。
查找是数据结构中的重要操作,好的查找方法会大大提高执行效率。通过本章学习,应掌握以下内容:
        查找的有关概念;
        静态查找;
        动态查找;
哈希查找。
2
查找就是指在给定的一组数据中对某个数值进行查询的过程。
关键字是数据元素(或记录)中某个项或组合项的数值,它可以标识一个数据元素或记录。
主关键字将能唯一确定一个数据元素(或记录)的关键字。
查找表是由具有相同类型的数据元素(或记录)组成的集合。分为静态查找表和动态查找表两大类。
如果查找表中能够找到满足条件的记录,称为查找成功,否则称为查找不成功。
基本概念与术语
3
静态查找表:在对查找表进行操作时,不改变表的结构,只进行查找操作;
动态查找表:在对查找表进行操作时,可以改变该查找表的结构,既可以进行查找操作,又可以进行插入、删除等操作。
静态查找表
静态查找表结构
静态查找表是由数据元素组成的线性表。其存储结构分为顺序存储和链式存储两种。可以用顺序表或线性链表来表示静态查找表。
4
静态查找表结构
typedef int KeyType;
typedef struct{
KeyType key;
………
} ElemType;
typedef struct{
ElemType elem[MAXSIZE+1];
int length;
}SST;
typedef struct NODE{
ElemType data;/* 结点的数据域*/
struct NODE *next;/*指针域*/
}NodeType;
静态查找表的顺序存储结构定义
静态查找表的链式存储结构定义
5
顺序查找
顺序查找又称线性查找,它思路简单、容易实现,是一种最基本的查找方法。
其查找过程为:从查找表的一端开始,逐个进行关键字与查找值的比较,若某个记录的关键字值与给定值相等,则查找成功,给出数据元素在查找表中的位置;若将整个表查找完,仍未找到与给定值相同的关键字,则查找失败,给出提示信息。
6
【】顺序查找
int Search_Seq(SST ST,KeyType x){
[0].key=x; /*设置监护哨*/
i=;
while([i].key!=x)
i--; /*返回找到记录的下标或者0(查找不成功) */
return i;
}/*Search_Seq*/
将查找过程中给定值和关键字比较的次数称为查找长度。通常用平均查找长度ASL来衡量查找算法的优劣。
算法分析:
7
平均查找长度:在查找成功时,平均查找长度ASL是指为确定数据元素在表中位置所进行关键字比较次数的期望值。对一个含n个数据元素的表,查找成功时
ASL=
Pi*Ci
n
∑
i=1
Pi为表中第i个数据元素的查找概率,Ci为表中第i个数据元素的关键字与给定值x相等时,需要比较的次数。
设查找表长度为n,查找元素x和表中第i个元素关键字相等时,需要比较的次数为n-i+1,则平均查找长度为:
ASL=
Pi*(n-i+1)
n
∑
i=1
8
设查找表中各元素的查找概率相等,即 Pi=1/n,则上面的式子表示为:
n
∑
i=1
ASL=
(n-i+1)=
1
─
n
n+1
───
2
当查找成功时,顺序查找的时间复杂度就是O(n)。
当查找失败时,关键字与给定值的比较次数总是n+1次。

二分查找,也称为折半查找,是对有序表进行的一种高效率的线性查找。有序表是指数据元素按给定的关键字已经是升序(或者是降序)的查找表。
9
假设各记录的关键字是由小到大排序的,算法的实现过程为:在待查找的有序表中,将中间元素首先与给定值进行比较,若相等,则表示查找成功;若给定值小于中间元素的关键字,则在左边的区域中继续查找;若给定值大于中间元素的关键字,则在右边的区域中继续查找。重复上述过程,直到查找成功或者查找失败,查找的过程随之结束。
例在给定的序列A={6,13,17,20,24,28,30,36,39,44,48,51,55}中查找给定值13和52这两个数据。
⑴查找关键字为13的过程
10