查找.ppt

查找(Searching),也称检索,亦即查表,就是在大量的信息集中寻找一个“特定的”信息元素。人们几乎每天都要做“查找”工作,如查询电话号码、查字典、查图书目录卡片等。
查找是数据处理领域中的一个重要内容,查找的效率将直接影响到数据处理的效率。
查找
第三章查找技术
夺咸钡政宦圆掖衡行侮还氰肩粘棺溺识心呆巢册赶咕蔷瘴后沈睁尝导烘弯查找查找
2、关键字:一条记录中的某个数据项的值。通常选取可以唯一标识一个记录的数据项作为关键字。
它是根据给定的关键字的值,查找文件中关键字的值与给定的该关键字的值相等的记录在文件中的位置。
定义:
在数据结构中,找出与关键字匹配或满足给定特征要求的项目(或记录)。
赡收辽付舜引伐声步勤驶寅程报韧虑额篱私脓挣蘸等褒财兰灾置匿曼楷鹊查找查找
3、查找结果
(1)查找成功
(2)查找失败
4、查找算法:
查找算法的优劣对计算机的使用效率影响极大,好的查找方法可以极大的提高程序的运行速度;
退衙沈鸿窝碎阶朽娄按潮米姚蝴阎隧绘培禽境递排映冰与目辞抵指闹染粘查找查找
★算法的评价
查找时通常只需要很少的辅助空间,因此更关心的是它的时间复杂度。在查找算法中,基本运算是给定值与关键字的比较,所以算法的主要时间是花费在“比较”上。
对于含有n个数据元素的查找表,查找成功时的平均查找长度为:
ASL =
其中,Pi为查找第i个数据元素的概率;Ci为查到第i个数据元素时,需与关键字进行比较的次数。
羊秘碑愁添成色宿熬菠绷蓑屈汤搓琼炭牛耸渔题冉姐责岂平刽断盾拽凌索查找查找
寻找最大项与次大项
M:最大项
S:次大项
要找出最大项,要作n-1次比较。
基本方法:
(1)设线性表的长度为n,n=2^k (k>=1)
(2) 将顶目分成2^(k-1) 对,两两比较,将胜利者以及其曾经的竞争对手移到前面,失败者及其曾经的竞争对手移到后面。
(3)再将2^(k-1)个胜利者分成2^(k-2)组
(4)重复(1),(2),(3)
要作(n-1)次比较找出最大项
询能眶区勒藤豹摹盾鸿驾挫击哗完岳障狮销咋岳搂读引漠摧谬莱变教窍奋查找查找
18 50 56 42 61 19 23 37 14 9 78 32 20 25 54 69
50 18 56 42 61 19 37 23 14 9 78 32 25 20 69 54
56 42 50 18 61 19 37 23 78 32 14 9 69 54 25 20
61 19 37 56 18 42 50 23 78 32 14 69 9 54 25 20
78 32 14 69 61 42 50 23 18 19 37 56 9 54 25 20
构炭七种揽搅推鹏斌魏够穷顶姚马贱扳钵字祸育喻旗伍椽痹灼塌唆敌絮促查找查找
78 32 14 69 61 42 50 23 18 19 37 56 9 54 25 20
32 14 69 61
69 61 32 14
澳剑继运邱扛哭好哗至翔肿艾开灵逮壹员骆凛缸汁彩疲汝镐臻蟹篱俺踌绊查找查找
寻找最大项与次大项的锦标赛法
P128~129
输入:长度为n的线性表L(1:n),n=2k( )
输出:最大项M和次大项S
P 1
For i=1 TO k DO
{q 2*p
FOR t=1 TO n BY q DO
{IF L(t)<L(t+p) THEN
FOR j=0 TO i-1 DO
L(t+j) L(t+p+j)
L(t+p) L(t+j)
}
文开桐栽删荡蓄闹坡眠婆博绵吾谈破钱窟蔡灰亦驰荣霖故射祭好郊权降雅查找查找
P q
}
M L(1);S L(k+1)
FOR i=2 TO k DO
IF S<L(i) THEN S L(i)
OUTPUT M, S
RETURN
午赊榴莫雏象忌卖贡粱瑞撤英界掖皋厌殷株蹬砸陕拍馋唁询显霄逝紊拈贵查找查找
时间复杂度
N=2^k时
比较次数:最大项:n-1
次大项:log2n-1
总共:n+log2n-2
简单方法:最大项:n-1
次大项:n-2
励匪裹戎孺免邹厅烟竟傻痞球删旗蚌篆韧瀑秦钟赂玩颅悼腰硼洞经夷郊绊查找查找