1、n 线性表的查找线性表的查找n 树表的查找树表的查找n 哈希哈希 表的查找表的查找1查找的基本概念查找的基本概念查找 (Search)又称检索 ,是数据处理中最常用的运算 .查找表 由同一类型的数据元素构成的集合。其存储方式： 顺序方式、链式方式、索引方式及哈希方式关键字 每个数据元素必有一个数据项，它可以标识（识别）该数据元素。如：通讯录中的姓名等等。查找 给定一个值 k,在查找表中找出其关键字与给定值相等的数据元素的过程，称查找。若找到，称查找成功，否则 , 称查找失败。2平均查找长度 (Average Search Length) 其中 : pi 查找第 i个元素的概率ci 查找第 i个
2、元素需要比较的次数3线性表查找线性表查找一、顺序查找基本思想： 从表的一端开始，顺序扫描线性表，依次将扫描到的结点的关键字与给定值 k进行比较 ,若相等，则查找成功；若扫描到表的另一端仍没有找到与关键字 k相等的结点，则查找失败。L=（ a1 , a2 , a3 , a4 , a5 , , an-1 , an）k =查找成功 查找失败也可以从后向前扫描40顺序查找图示25 34 57 16 48 09 1 2 3 4 5 6table查找 16查找成功i i itypedef struct keytype key;InfoType data;NodeType;NodeType Rn+1;ii=
3、1;while(Ri.key!=k)i+;25 34 57 16 48 09 1 2 3 4 5 6table查找 50i i 查找失败i=1;while(i0 查找成功 */*i=0 查找失败 */顺序查找算法：6在等概率情形，在等概率情形， pi = 1/n, i = 1, 2, , n。 不成功情形不成功情形 : ASLunsucc = n+1. 性能分析：成功情形 :优点：算法简单。即适用于顺序存储方式 ,有适用于链式存储方式。缺点：效率低。O(n)7二、二分查找（折半查找）查找表要求： 以顺序方式存储，并按关键字有序排列 。基本思想：1、在查找表 R1- Rn确定中间元素 Rmid。
4、2、 若 k=Rmid.key,则查找成功。3、若 kRmid.key,则在 Rmid+1-Rn中继续查找。 05 13 19 21 37 56 64 75 80 88 921 2 3 4 5 6 7 8 9 10 11tablemidk=Rmid.key查找成功KRmid.key上半区在区间 low,high中进行二分查找8mid05 13 19 21 37 56 64 75 80 88 921 2 3 4 5 6 7 8 9 10 11tablelow highmid以顺序方式存储，并按关键字有序排列查找 k=21开始mid=(low+high)/2K=Rmid.key 查找成功yNKRmid.key)k=Rmid.key 成功905 13 19 21 37 56 64 75 80 88 921 2 3 4 5 6 7 8 9 10 11tablehighmid查找 k=78查找失败highlow开始mid=(low+high)/2K=Rmid.key 查找成功yNKRmid.key) mid(kRmid.key)(kRmid.key)?lowhigh(失败）Low=highyN查找 k=15 比较： 56、19、05、1310
