数据结构导论 第6章 查找表.ppt

第6章查找表
查找(Search)的相关概念
查找:就是在数据集合中寻找满足某种条件的数据对象。
查找表:是由同一类型的数据元素(或记录)组成的数据集合。
查找的结果通常有两种可能:
查找成功,即找到满足条件的数据对象。
查找不成功,或查找失败。作为结果,
报告一些信息,如失败标志、失败位置等。
对查找表经常进行的操作:
1)查询某个“特定的”数据元素是否在查找表中;
2)检索某个“特定的”数据元素的各种属性;
3)在查找表中插入一个数据元素;
4)从查找表中删去某个数据元素。
静态查找表仅作查询和检索操作的查找表。
动态查找表有时在查询之后,还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中;或者,从查找表中删除其“查询”结果为“在查找表中”的数据元素。表结构本身可以在查找过程中动态生成。
关键字(Key):数据元素(记录)中某个数据项的值,用以标识一个数据元素。
主关键字:可唯一地标识一个数据元素的关键字。
次关键字:用以识别若干记录的关键字。
使用基于主关键字的查找,查找结果应是唯一的。
如何进行查找?
查找的方法取决于查找表的结构。
由于查找表中的数据元素之间不存在明显的组织规律,因此不便于查找。
为了提高查找的效率,需要在查找表中的元素之间人为地附加某种确定的关系,换句话说, 用另外一种结构来表示查找表
静态查找表
动态查找树表
哈希表(散列表)
衡量一个查找算法的时间效率的标准是:
在查找过程中关键字的平均比较次数或平均读写磁盘次数(只适合于外部查找),这个标准也称为平均查找长度ASL(Average Search Length),通常它是查找结构中对象总数 n 或文件结构中物理块总数 n 的函数。
算法所需要的存储量和算法的复杂性等问题。

静态查找表用顺序表作为存储结构
在静态查找表中,数据对象存放于数组中,利用数组元素的下标作为数据对象的存放地址。查找算法根据给定值x,在数组中进行查找。直到找到x在数组中的存放位置或可确定在数组中找不到x为止。
(Sequential Search)
静态查找表的顺序存储结构为:
#define maxsize 静态查找表的表长
typedef struct {
ElemType item[maxsize+1];
// 存储数据元素的数组空间,0号单元留空
int n; // 表的长度
} sqtable;
数据元素类型ElemType的定义为:
typedef struct {
keyType key; // 关键字域
……// 其它属性域
} ElemType ;
int Search_sqtable(sqtable R, KeyType k){ //顺序查找的算法,0号元素为监视哨 int i; [0].key=k; for (i=; [i].key!=K ; --i); return i;}
查找过程:从表中最后一个元素开始,顺序用各元素的关键字与给定值K进行比较,若找到与其值相等的元素,则查找成功,给出该元素在表中的位置;否则,若直到第一个记录仍未找到关键字与x相等的对象,则查找失败。
顺序查找的时间性能
设查找第 i 个元素的概率为 pi,查找到第 i 个元素所需比较次数为 ci,则查找成功的平均查找长度:
在顺序查找情形,ci = n-i +1, i = 1, , n,因此
在等概率情形,pi = 1/n, 。