【精品数据结构】查找2

1、,在此幻灯片插入公司的徽标 从“插入”菜单 选择图片 找到徽标文件 单击“确定” 重新设置徽标大小 单击徽标内任意位置。徽标外部出现的方框是“调整控点” 使用这些重新设置对象大小 如果在使用尺寸调整控点前按下 shift 键，则对象改变大小但维持原比例。,DATA,10,65,865,姓名 学号 成绩 班级 李红 9761059 95 机97.6,数据结构,第二章数据结构与算法,(续),2.7 查找,查找：查找是在一个给定的数据结构中，根据给定的条件查找满足条件的结点。不同的数据结构采用不同的查找方法。查找的效率直接影响数据处理的效率。 查找的结果： 查找成功：找到满足条件的结点 查找失败：找

2、不到满足条件的结点。, 可以采用从前向后查，也可采用从后向前查的方法。 在平均情况下，大约要与表中一半以上元素进行比较，效率较低。平均查找长度较大。 在下面两种情况下只能采取顺序查找： a. 线性表为无序表（元素排列是无序的）； b. 即使是有序线性表，但采用的是链式存储结构。,271 顺序查找（线性查找） 查找过程： 对给定的一关键字K，从线性表的一端开始，逐个进行记录的关键字和K的比较，直到找到关键字等于K的记录或到达表的另一端。,1 . 顺序查找 (线性表在顺序存储结构下的顺序查找） 数据结构： typedef struct int key; float info; SSTable;,每

3、个结点包含两部分内容：Key 和info,其他信息,顺序查找的算法： int Search_seq(SSTable ST , int n, int key) int i=n; ST0.key=key; while(STi.key!=key) i- -; /*从表尾往前查*/ return i; ,监视哨,使用了监视哨，在查找过程中，不用每一步都去判断是否查找结束。 找到：返回元素在线性表中的存储位置； 未找到：返回0。,根据上述算法可知： 查找成功时的平均查找次数为： ASL=(1+2+3+4+n)/n=(n+1)/2 查找不成功时的比较次数为： n+1 则顺序查找的平均查找长度为： ASL=

4、(n+1)/2+n+1)/2=(n+1)3/4 顺序查找的优点：算法简单，无需排序，采用顺序和链式存储均可。 缺点：平均查找长度较大。,2. 线性表在链式存储结构下的顺序查找 struct node int data; struct node *next; ; int searlb(struct node *h,int x) struct node *m; m=h; while (m-next!=NULL ,2.7.2 折半查找（二分法查找） 思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。 前提：必须在具有顺序存储结构的有序表中进行。,分三种情况： 1）若

5、中间项的值等于x,则说明已查到。 2）若x小于中间项的值，则在线性表的前半部分查找； 3）若x大于中间项的值，则在线性表的后半部分查找。 特点：比顺序查找方法效率高。最坏的情况下，需要比较 log2n次。,查找23和79的过程如下图：,mid=(low+high)/2不进位取整,( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),( 08

6、, 14, 23, 37, 46, 55, 68, 79, 91 ),( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),折半查找的c语言算法程序： int Search_Bin( SSTable ST , int n, int key) int low, high,mid; low=1; high=n; while(low=high) mid=(low+high)/2; if(STmid.key= = key) return (mid); /*查找成功*/ else if( key STm

7、id.key) high=mid-1; /*在前半区间继续查找*/ else low=mid+1; /*在后半区间继续查找*/ return (0); /*查找不成功*/ ,是顺序查找的一种改进方法，就是把被查找的表分成若干块，每块中记录的存放顺序是无序的，但块与块之间必须按关键字有序。即第一块中任一记录的关键字都小于第二块中任一记录的关键字，而第二块中任一记录的关键字都小于第三块中任一记录的关键字，依此类推。 该法要为被查找的表建立一个索引表，索引表中的一项对应于表中的一块，索引表中含有这一块中的最大关键字和指向块内第一个记录位置的指针，索引表中各项关键字有序。,2.7.3分块查找（索引顺序

8、查找）,索引表,块中的最大关键字,块内第一个记录位置的指针,分块查找步骤：,查索引表，确定要找的记录在哪一块。 在相应的块中查找。,例如，要找关键字为22的记录。 由索引的第一项可知，要找的记录要么在第二块中，要么不存在。并获取第二块中第一个记录的位置。,2.7.2-1 利用二叉排序树进行查找 （1）二叉排序树的概念及构造,一棵二叉排序树,在二叉排序树中，若按中序遍历就可以得到由小到大的有序序列，即 2，3，3，7，8，10，12，18 , 10、18、3、8、12、2、7、3 ,10,10,18,3,8,12,2,7,3,（2） 在指针t 所指向的二叉排序树中查找关键字值为K的结点 #def

9、ine M 100 typedef struct node int key; struct node L, R;JD JD pxscz(JD t, int K) JD p; if(t!=NULL) p=t; while(p!=NULL) printf(“key= %dn”,p-key); if(p-key=k) return (p); else if(p-keyk) p=p-L; else p=p-R; return(NULL); ,10,2,7,3,8,18,12,3,1、 基本概念哈希函数，冲突,2.7.3 散列（HSAE）查找,哈希表技术的主要目标是提高查找效率，即缩短查表 和填表的时间

10、。,根据关键字直接计算出元素所在位置的函数。 例如：设哈希函数为： int(K/3)+1 则构造 01、02、05、09、11、13、16、19、21、26、27、31、的散列表(哈希表）为：,哈希函数：,冲突：两个不同的关键字具有相同的存储位置。,为了有效地使用散列技术，需要解决两方面的问题： 构造好的哈希函数，使冲突的现象尽可能的少； 设计有效的解决冲突的方法。,2、 构造哈希函数的方法 （1） 直接定址法取关键字或关键字的某个线性函数值为散列地址，即 H（K）=K 或 H（K）=A*K+B；（其中A、B为常数） 直接定址哈希函数示例：某公司一险种投保费交纳表（20年）， 将年份作关键字，

11、哈希函数取关键字本身，若查找第3年应交纳的保费，只要查找表的第3项即可。,（2）平方取中法取关键字平方后的中间几位为哈希函数。 如：K=308，K2=94864，H（K）=486,（3） 除后余数法取关键字被不大于散列表表长m的数p除后所得的余数为哈希函数。 即 H（K）=K MOD p （pm）,3、 处理冲突的方法 （1） 开放定址法,设散列函数 H（k）=k MOD m （m为表长, 设m=11) 若发生冲突，设发生冲突的地址为 p , 则沿着一个探查序列逐个探查，那么，探查的地址序列为 P+1, P+2, P+3 , m-1 , 0, 1, , P-1.,3、 处理冲突的方法 （1）

12、开放定址法,设散列函数 H（K）=K MOD m （m为表长） 若发生冲突，则沿着一个探查序列逐个探查，那么，第i次计算冲突的散列地址为： Hi=(H(K)+di)MOD m (di=1,2,m-1，i=1,2,F(F=m-1),0 1 2 3 4 5 6 7 8 9 10,设散列函数 H(k)=k MOD 11 求： 60、17、29、38在散列表中的位置。,H(60)= 60 mod 11 = 5 H(17)= 17 mod 11 = 6 H(29)= 29 mod 11 = 7 H(38)= 38 mod 11 = 5，H(38+1) mod 11 = 6 H(38+2) mod 11 = 7 H(38+3) mod 11 = 8,按开放地址法所建的散列表的散列查找算法： # difine M 100 int h(int k) return (k%97); int SearchHase(int t ,int k) int i