第九章查找PPT课件

1、第九章第九章 查找查找知识点知识点2：静态查找表：静态查找表一、一、 顺序查找顺序查找 查找过程查找过程：对给定的一关键字对给定的一关键字K K，从线性表的一端开始，逐个，从线性表的一端开始，逐个进行记录的关键字和进行记录的关键字和K K的比较，直到找到关键字等于的比较，直到找到关键字等于K K的记录或的记录或到达表的另一端到达表的另一端v查找方向查找方向：从前向后、从后向前：从前向后、从后向前 v在下面两种情况下在下面两种情况下只能采取顺序查找只能采取顺序查找： a. a. 线性表为无序表（元素排列是无序的）；线性表为无序表（元素排列是无序的）； b. b. 即使是有序线性表，但采用的是链式

2、存储结构。即使是有序线性表，但采用的是链式存储结构。 顺序表的结构：顺序表的结构：typedef struct ElemType *elem; int length ; SSTable;SSTable ST;每个结点均包含每个结点均包含关键字内容：关键字内容：Key 顺序表的结点结构顺序表的结点结构：typedef struct KeyType key; ; ElemType;ST.elem0 1 2 3 4 5 6 7（a） 初态初态40803060102025(return i=4)(b) K=8080408030601020250 1 2 3 4 5 6 7(c) K=90(return

3、 i=0 )0 1 2 3 4 5 6 79040803060102025 顺序查找的算法：顺序查找的算法：int Search_seq(SSTable ST , KeyType key) int i=ST.length; ST0.key=key; while(STi.key!=key) i- -; /*从表尾往前查从表尾往前查*/ return i;监视哨监视哨使用了监视哨，在使用了监视哨，在查找过程中，不用查找过程中，不用每一步都去判断是每一步都去判断是否查找结束。否查找结束。找到：返回元素在找到：返回元素在线性表中的存储位线性表中的存储位置；置；未找到：返回未找到：返回0 0。比较次数：

4、比较次数：查找第查找第n n个元素：个元素： 1 1查找第查找第n-1n-1个元素：个元素：2 2. .查找第查找第1 1个元素：个元素： n n查找第查找第i i个元素：个元素： n+1-i n+1-i查找失败：查找失败： n+1 n+1顺序查找方法的顺序查找方法的平均查找长度平均查找长度ASLASL是指为是指为确定数据元素在表中的位置确定数据元素在表中的位置所进行的关键字比较次数的期望值所进行的关键字比较次数的期望值。niiicpASLn1个记录的表，对含有 其中：其中：P Pi i为表中第为表中第i i个数据元素的查找概率个数据元素的查找概率 C Ci i为表中第为表中第i i个数据元素

5、的关键字与给定值个数据元素的关键字与给定值keykey相等时，按算法定位时相等时，按算法定位时关键字的比较次数。显然，不同的查找方法，关键字的比较次数。显然，不同的查找方法，C Ci i可以不同。可以不同。 ni=1Pi=1性能分析：性能分析：212)1(11111nnnnincpASLnpniniiii则概率相等设表中每个元素的查找在在不等概率查找不等概率查找时时 ，ASLASLssss 在在 P Pn nPPn-1n-1PP2 2PP1 1 时时取极小值取极小值 若查找概率无法事先测定，则查找过程采取的改进办法是，若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查找之后，将刚刚查

6、找到的记录直接移至表尾的位置上在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上。 顺序查找缺点是当顺序查找缺点是当n n很大时，平均查找长度较大，效率低；优点很大时，平均查找长度较大，效率低；优点是对表中数据元素的存储没有要求。是对表中数据元素的存储没有要求。 线性表在链式存储结构下的顺序查找线性表在链式存储结构下的顺序查找 struct node int data; struct node *next; int searlb(struct node *h,int x) int m=0; struct node *p; p=h; while (p-next!=NULL&p-dat

7、a!=x) p=p-next; m+; if(p-data=x) return m; else return 0;二、二、 有序表的查找有序表的查找有序表有序表即是表中数据元素按关键字升序或降序排列。即是表中数据元素按关键字升序或降序排列。查找过程查找过程：每次将待查记录所在区间缩小一半：每次将待查记录所在区间缩小一半顺序存储结构的有序表顺序存储结构的有序表折半查找的折半查找的基本思想基本思想：在有序表中，：在有序表中，取中取中间元素作为比较对象，若给定值与中间元素的关键字相等，则查间元素作为比较对象，若给定值与中间元素的关键字相等，则查找成功；找成功；若给定值小于中间元素的关键字，则在中间元

8、素的左半若给定值小于中间元素的关键字，则在中间元素的左半区继续查找；区继续查找；若给定值大于中间元素的关键字，则在中间元素的若给定值大于中间元素的关键字，则在中间元素的右半区继续查找。右半区继续查找。不断重复上述查找过程，直到查找成功，或所不断重复上述查找过程，直到查找成功，或所查找的区域无数据元素，查找失败。查找的区域无数据元素，查找失败。顺序查找表的查找算法简单，顺序查找表的查找算法简单， 但平均查找长度较大，特别不适用于但平均查找长度较大，特别不适用于表长较大的查找表。表长较大的查找表。顺序存储结构的有序表顺序存储结构的有序表折半查找的折半查找的基本思想基本思想：在有序表中，：在有序表中

9、，取中间元素取中间元素作为比较对象，若给定值与中间元素的关键字相等，则查找成功；作为比较对象，若给定值与中间元素的关键字相等，则查找成功；若给若给定值小于中间元素的关键字，则在中间元素的左半区继续查找；定值小于中间元素的关键字，则在中间元素的左半区继续查找；若给定若给定值大于中间元素的关键字，则在中间元素的右半区继续查找。值大于中间元素的关键字，则在中间元素的右半区继续查找。不断重复不断重复上述查找过程，直到查找成功，或所查找的区域无数据元素，查找失败。上述查找过程，直到查找成功，或所查找的区域无数据元素，查找失败。算法实现算法实现n设表长为设表长为n n，lowlow、highhigh和和m

10、idmid分别指向待查元素所在区间的分别指向待查元素所在区间的上界、下界和中点上界、下界和中点, ,k k为给定值为给定值n初始时，令初始时，令low=1,high=n,mid=low=1,high=n,mid= (low+high)/2(low+high)/2 n让让k k与与midmid指向的记录比较指向的记录比较若若k=rmid.keyk=rmid.key，查找成功，查找成功若若krmid.keykrmid.keykrmid.key，则，则low=mid+1low=mid+1n重复上述操作，直至重复上述操作，直至lowhighlowhigh时，查找失败时，查找失败lowhighmid例

11、1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92找211 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid找701 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75

12、80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92low highmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhigh1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92算法：算法：int Search_Bin(SStable ST,KeyTyp

13、e Key) low=1;high=ST.length; while(low=high) mid=(low+high)/2; if(ST.elemmid=key) return mid; else if (ST.elemmidkey) high=mid-1; else low=mid+1; return 0;先看一个具体的情况，假设：先看一个具体的情况，假设：n=11分析分析折半查找折半查找的平均查找长度的平均查找长度6391425781011判定树判定树i1234567891011C i12233334444算法评价算法评价n判定树：描述查找过程的二叉树叫判定树判定树：描述查找过程的二叉树叫

14、判定树n有有n n个结点的判定树的深度为个结点的判定树的深度为 loglog2 2n n +1+1n折半查找法在查找过程中进行的比较次数最多不超过其判定折半查找法在查找过程中进行的比较次数最多不超过其判定树的深度树的深度n折半查找的折半查找的ASLASL1)1(log1)1(log12111),1(log,122211112nnnnjncncpASLnphnhnhjjniiniiiih则：概率相等设表中每个记录的查找的满二叉树即判定树是深度为设表长折半查找的效率比顺序查找高折半查找的效率比顺序查找高前提：必须在前提：必须在具有顺序存储结构的具有顺序存储结构的有序表有序表中进行中进行三、三、索引

15、索引顺序表的查找（顺序表的查找（分块查找分块查找）查找过程查找过程：将表分成几块，块内无序，块间有序；先确定待查：将表分成几块，块内无序，块间有序；先确定待查记录所在块，再在块内查找记录所在块，再在块内查找适用条件适用条件：分块有序表：分块有序表算法实现算法实现n用用数组存放待查记录数组存放待查记录, ,每个数据元素至少含有关键字域每个数据元素至少含有关键字域n建立建立索引表索引表，每个索引表结点含有最大关键字域和指向本块，每个索引表结点含有最大关键字域和指向本块第一个结点的指针第一个结点的指针索引表索引表 20 53 89 1 6 111812852051362229538960726676

16、块中的最大关块中的最大关键字键字块内第一个记块内第一个记录位置的指针录位置的指针查29 20 53 89 1 6 111812852051362229538960726676查找步骤查找步骤1. 查索引表，确定要找的记录在哪一块。查索引表，确定要找的记录在哪一块。2. 在相应的块中查找。在相应的块中查找。分块查找方法评价分块查找方法评价2) 1(log)2(1)(21212111) 1 (211ssnASLssnsbisjbASLsbnLLLLASLbssibjbswbwbbs：用折半查找确定所在块：用顺序查找确定所在块查找概率相等，则：记录的个记录，并设表中每个块，每块含的表平均分成若将表长为均查找长度在块中查找元素的平块的平均查找长度查找索引表确定所在其中：ASL最大最大最小最小两者之间两者之间表结构表结构有序表、无序表有序表、无序表