查找本章的主要内容是: 查找的基本概念 线性表的查找技术

概述查找的基本概念查找 ：在具有相同类型的记录构成的集合中找出满足 给定条件的记录。 查找的结果 ：若在查找集合中找到了与给定值相匹配 的记录，则称查找成功；否则，称查找失败。职工号 0001 0002 0003 姓名 王刚 张亮 刘楠 性别 男 男 女 年龄 38 25 47 参加工作 1990年4月 2003年7月 1979年9月

00040005

齐梅李爽

女女

2550

2003年7月1972年9月

概述查找的基本概念静态查找 ：不涉及插入和删除操作的查找 。 动态查找 ：涉及插入和删除操作的查找。

静态查找适用于：查找集合一经生成，便只对其进行 查找，而不进行插入和删除操作，或经过一段时间的 查找之后，集中地进行插入和删除等修改操作； 动态查找适用于：查找与插入和删除操作在同一个阶 段进行，例如当查找成功时，要删除查找到的记录， 当查找不成功时，要插入被查找的记录。

概述查找的基本概念查找结构 ：面向查找操作的数据结构 ，即查找基于的 数据结构。 查找结构 查找方法

集合中元素之间不存在明显的组织规律，不便查找。

线性表集合 树 表

散列表

概述查找的基本概念本章讨论的查找结构 ：

线性表：适用于静态查找，主要采用 顺序查找技术、折半(二分)查找技术。

线性表的查找技术顺序查找 (线性查找)基本思想：从线性表的一端向另一端逐个将关键码与 给定值进行比较，若相等，则查找成功，给出该记录 在表中的位置；若整个表检测完仍未找到与给定值相 等的关键码，则查找失败，给出失败信息。例：查找k=35 0 1 2 3 4 5 6 7 8 9

10 15 24 6 12 35 40 98 55i i i i

线性表的查找技术顺序查找 (线性查找)int SeqSearch1(int r[ ], int n, int k) //数组r[1] ~ r[n]存放查找集合 { i=n; while (i>0 && r[i]!=k) i--; return i; }

线性表的查找技术改进的顺序查找基本思想：设置“哨兵”。哨兵就是待查值，将它放 在查找方向的尽头处，免去了在查找过程中每一次比 较后都要判断查找位置是否越界，从而提高查找速度 。 例：查找k=35 0 1 2 3 4 5 6 7 8 9

35 10 15 24 6 12 35 40 98 55哨兵

i 查找方向

i

i

i

线性表的查找技术改进的顺序查找基本思想：设置“哨兵”。哨兵就是待查值，将它放 在查找方向的尽头处，免去了在查找过程中每一次比 较后都要判断查找位置是否越界，从而提高查找速度 。 例：查找k=25 0 1 2 3 4 5 6 7 8 9

25 10 15 24 6 12 35 40 98 55i i i i i i i 查找方向 i i i

线性表的查找技术改进的顺序查找int SeqSearch2(int r[ ], int n, int k) //数组r[1] ~ r[n]存放查找集合 { r[0]=k; i=n; while (r[i]!=k) i --; return i;

}

课堂练习 编写一程序在顺序表{4,6,3,2,5,8,10}中,通 过顺序查找法查找关键字5的过程。

线性表的查找技术顺序查找的缺点：平均查找长度较大，特别是当待查找集合中元素较多 时，查找效率较低。

顺序查找的优点：算法简单而且使用面广。

对表中记录的存储没有任何要求，顺序存储和链接 存储均可； 对表中记录的有序性也没有要求，无论记录是否按 关键码有序均可。

线性表的查找技术折半查找使用条件： 线性表中的记录必须有序(非递减); 必须采用顺序存储。 基本思想：在有序表中，取中间记录作为比较对象， 若给定值与中间记录的值相等，则查找成功；若给定 值小于中间记录的值，则在中间记录的左半区继续查 找；若给定值大于中间记录的值，则在中间记录的右 半区继续查找。不断重复上述过程，直到查找成功， 或所查找的区域无记录，查找失败。

线性表的查找技术折半查找的基本思想(mid=(1+n)/2)k

[ r1 … … … rmid-1 ] rmid [ rmid+1 … … … rn ]如果k<rmid 查找左半区 如果k>rmid 查找右半区

线性表的查找技术例：查找值为14的记录的过程： 0 1 2 3 4 5 6 7 8 9 10 11 12 13

7 14 18 21 23 29 31 35 38 42 46 49 52 low=1 18>14 high=6 mid=3 mid=7 31>14 high=13

high=2 mid=1

7<14

low=2 mid=2 14=14

线性表的查找技术例：查找值为22的记录的过程： 0 1 2 3 4 5 6 7 8 9 10 11 12 13

7 14 18 21 23 29 31 35 38 42 46 49 52 low=1 mid=7 31>22 18<22 high=6 mid=3 low=4 mid=5 23>22 high=4 21<22 mid=4 low=5 low>high high=13