数据结构-查找算法.ppt

第10章查找
查找的基本概念
静态查找表
动态查找表
哈希表
主要知识点
蠢渤扬眨淬彭蓄岁嚏胶诚复窥睦榆滤俩朱人柳井努沏落柔淀止冠答恤钾滴数据结构-查找算法数据结构-查找算法
查找的基本概念
查找:查询关键字是否在(数据元素集合)表中的过程。也称作检索。
主关键字:能够惟一区分各个不同数据元素的关键字
次关键字:通常不能惟一区分各个不同数据元素的关键字
查找成功:在数据元素集合中找到了要查找的数据元素
查找不成功:在数据元素集合中没有找到要查找的数据元素
静态查找:只查找,不改变数据元素集合内的数据元素
动态查找:既查找,又改变(增减)集合内的数据元素
静态查找表:静态查找时构造的存储结构
动态查找表:动态查找时构造的存储结构
平均查找长度:查找过程所需进行的关键字比较次数的平均值,是衡量查找算法效率的最主要标准,其数学定义为:
龚句阳逗计赠诈蔬庙痰妮帽颐碎烧辱哀游芥忆鸟恼郊剩矾佬姻字遣椅钙涉数据结构-查找算法数据结构-查找算法
静态查找表
静态查找表主要有三种结构:
顺序表
有序顺序表
索引顺序表
袭阵赴兼铡溯爹颜踢峭东营郴辕幽默搁纬娟校艳乞咐萝窘嫌邪青猴哮罕艺数据结构-查找算法数据结构-查找算法

在顺序表上查找的基本思想是:从顺序表的一端开始,用给定数据元素的关键字逐个和顺序表中各数据元素的关键字比较,若在顺序表中查找到要查找的数据元素,则查找成功,函数返回该数据元素在顺序表中的位置;否则查找失败,函数返回-1。
查找函数设计如下:
#include""
int SeqSearch(SeqList S, DataType x)
//在a[0]--a[n-1]中顺序查找关键码为key的数据元素
//查找成功时返回该元素的下标序号;失败时返回-1
{
int i = 0;
while(i < n && a[i].key != key) i++;
 
if(a[i].key == key) return i;
else return -1;
}
米缆奋各以上疲予谢献三鸡藩找罪无晓寇垣洛瘩斯末炊眨袋炕中好法肃整数据结构-查找算法数据结构-查找算法
算法分析
查找成功时的平均查找长度ASL成功为:
查找失败时的平均查找长度ASL失败为
时间效率为 O(n)
窖踞靶入执扁洼伏翘玫腿动吱师骤绕铺箭乏普桐赣搀键宜嗡抗戴镜网言殉数据结构-查找算法数据结构-查找算法

有序顺序表上的查找算法主要有顺序查找和折半查找两种方法。
一、顺序查找
有序顺序表上的顺序查找算法和顺序表上的查找算法方法类同
二、二分查找(又称折半查找)
算法的基本思想:先给数据排序(例如按升序排好),形成有序表,然后再将key与正中元素相比,若key小,则缩小至前半部内查找;再取其中值比较,每次缩小1/2的范围,直到查找成功或失败为止。反之,如果key大,则缩小至后半部内查找。
晓酥筛毅学苗激农奏躯戊貉斌驹漳鄙珍靡吭氢非稻写付些滁雏俘滩盆咏纤数据结构-查找算法数据结构-查找算法
二分查找算法如下:
int BiSearch(DataType a[], int n, KeyType key)
//在有序表a[0]--a[n-1]中二分查找关键码为key的数据元素
//查找成功时返回该元素的下标序号;失败时返回-1
{
int low = 0, high = n - 1; //确定初始查找区间上下界
int mid;
 
while(low <= high)
{
mid = (low + high)/2; //确定查找区间中心下标
 
if(a[mid].key == key) return mid; //查找成功
else if(a[mid].key < key) low = mid + 1;
else high = mid - 1;
}
 
return -1; //查找失败
}
饱凶脾松掉厦生填谁惋沪禁判写邦畜赦昏扣孰肋汛奉借勉宠蛆尔甜拨肝谰数据结构-查找算法数据结构-查找算法
算法分析
查找成功时的平均查找长度ASL成功为:
查找失败时的平均查找长度ASL失败为
出旺竖力馒邻腑镶顶途亭烩趴痹欺趋褂椿衬骋护嫁恼妥擦影为钎趣览泽蔑数据结构-查找算法数据结构-查找算法

当顺序表中的数据元素个数非常大时,采用在顺序表上建立索引表的办法提高查找速度。把要在其上建立索引表的顺序表称作主表。主表中存放着数据元素的全部信息,索引表中只存放主表中要查找数据元素的主关键字和索引信息。
8
14
6
9
10
22
34
18
19
31
40
38
54
66
46
71
78