文档介绍：第八章查找
查找的基本概念
基于线性表的查找法
基于树的查找法
计算式查找法-哈希法
总结与提高
第八章查找
查找的基本概念
列表:由同一类型的数据元素(或记录)构成的集合,可利用任意数据结构实现。
关键字:数据元素的某个数据项的值,用它可以标识列表中的一个或一组数据元素。
主关键字:如果一个关键字可以唯一标识列表中的一个数据元素,则称其为主关键字,否则为次关键字。当数据元素仅有一个数据项时,数据元素的值就是关键字。
查找:根据给定的关键字值,在特定的列表中确定一个其关键字与给定值相同的数据元素,并返回该数据元素在列表中的位置。
在查找算法中要用到三类参量,即:
①查找对象K(找什么)
②查找范围L(在哪找)
③查找的结果(K在L中的位置)
其中①、②为输入参量,在函数中不可缺少。
③为输出参量,可用函数返回值表示。
平均查找长度:为确定数据元素在列表中的位置,需和给定值进行比较的关键字个数的期望值,称为查找算法在查找成功时的平均查找长度。
对于长度为n的列表,查找成功时的平均查找长度为:
ASL=P1C1+ P2C2+…+ =
i=1
n
PiCi
其中Pi为查找列表中第i个数据元素的概率,Ci为找到列表中第i个数据元素时,已经进行过的关键字比较次数。
查找的基本方法:
比较式查找法
计算式查找法-HASH(哈希)查找法
基于线性表的查找法
基于树的查找法
基于线性表的查找法
具有顺序查找法、折半查找法和分块查找法三种
顺序查找法
顺序查找法的特点是:用所给关键字与线性表中各元素的关键字逐个比较,直到成功或失败。
存储结构:
顺序结构
链式结构
顺序结构有关数据类型的定义:
#define LIST_SIZE 20
typedef struct {
KeyType key;
OtherType other_data;
} RecordType;
typedef struct {
RecordType r[LIST_SIZE+1]; /* r[0]为工作单元*/
int length;
} RecordList;
设置监视哨的顺序查找算法
int SeqSearch(RecordList l, KeyType k)
/*在顺序表l中顺序查找其关键字等于k的元素,若找到,则函数值为该元素在表中的位置,否则为0*/
{
[0].key=k; i=;
while ([i].key!=k) i--;
return(i);
}
[0]为监视哨,可以起到防止越界的作用。
不设置监视哨的顺序查找算法
int SeqSearch(RecordList l, KeyType k)
/*不用监视哨法,在顺序表中查找关键字等于k的元素*/
{
[0].key=k; i=;
while (i>=1&&[i].key!=k) i--;
if (i>=1) return(i)else return (0);
}
循环条件i>=1判断查找是否越界。
用平均查找长度分析顺序查找算法的性能。
假设列表长度为n,那么查找第i个数据元素时需进行n-i+1次比较,即Ci=n-i+1。又假设查找每个数据元素的概率相等,即Pi=1/n,则顺序查找算法的平均查找长度为:
ASL=
i=1
n
PiCi
=
n
1
i=1
n
Ci
=
n
1
i=1
n
(n-i+1)=
2
1
(n+1)