03-查找与排序.ppt

江苏大学多媒体教学课件计算机软件技术基础 2. 二叉排序树 3. 二叉排序树的生成 4.删除二叉排序树上的结点 2）数字分析法: 该法适用于较大的静态数据，在已知所有关键字键值的情况下，分析每一位的数字分布是否均匀，删除不均匀分配的数字位，根据存储空间的大小来确定所取地址的位数。 542 42 2241 542 81 3678 542 22 8171 542 38 9671 542 54 1577 542 88 6376 542 19 3552 422 836 281 396 515 853 135 存储空间从0-1000 3）平方取中法: 若一组关键字的值在每一位上对某些数字的重复频度都很高，就不宜采用数字分析法，取关键字平方后的中间几位为哈希函数。 H(Key) = Key2 = an an-1 … a2 a1 0100,1100,1200,1160,2060,2061,2163,2261,2262 设存储空间 0-1000 平方后，取2、3、4位构成哈希地址如下： 010,210,440,345,243,247,678,112,116 4）除留余数法： 取关键字被不大于散列表表长 m 的数p除后所得的余数为哈希函数。 即 H（K）=K MOD p （p?m） p一般选取小于等于表长的质数。 H（K）= K MOD p + C （p?m） C 的作用可以调节最终的地址范围，为小于表长的某一整型常数 。 5）折叠法：将关键字的值分为几段，尔后叠加求和。 A、移位折叠，将各段左对齐后相加； B、边界折叠，将奇数段、偶数段倒排后相加。 1）开放定址法(线性探测再散列) 设散列函数 H（k）=k MOD m m为表长 若发生冲突，设发生冲突的地址为 p , 则沿着一个探查序列逐个探查，那么，探查的地址序列为P+1, P+2, P+3 ,…, m-1 , 0, 1, …, P-1. 即：Hi=（H（Key）+di） MOD m di为增量序列，为1，2，…，m-1 29 17 60 0 1 2 3 4 5 6 7 8 9 10 例如 : 在长度为11的散列表中，已填有关键字分别为60、17、29的记录，现填入第四个记录，其关键字为38。 38 3、解决冲突的方法 //按开放定址法所建的散列表的散列查找算法： # define M 100 int h(int k) { return (k%97); } /* 哈希函数 */ int SearchHash(int t[ ],int K) { int i, j=0; i=h(K); /* 求得哈希地址 */ while((( jM) (t[(i+j)%M]!=0)) (t[(i+j)%M]!=K))) j++; /* 该地址有数据且与待查关键字不等时， 求下一地址*/ i=(i+j)%M; if (t[i]= =K) return (i); /*查找成功 */ else return (-1); /*查找不成功*/ } 缺点：探测次数多，删除运算难，溢出处理复杂。 为了改变线性探测再散列的缺点，避免相近的关键字值聚集在一起。当发生冲突时，求另一地址的公式是： H2j =(H1+j2) mod m H1=H（Key） H2j+1 =(H1-j2) mod m ( j = 1,2, …, s, s-1 ) 2）平方探测再散列（二次探测法） 47，7，29，11，16，92，22，8，3 8 29 7 16 92 47 22 11 0 1 2 3 4 5 6 7 8 9 10 3 用一组预先给定的随机数来求发生冲突时“另一个”地址，公式为： H2j =(H1 + Rj ) mod m ( j = 1,2, …, s, s-1 ) 其中，Rj为一组随机数列。 3）随机探测再散列 仅仅是对线性探测再散列的一种改进 链地址法：把具有相同散列地址的键值存放在同一个链表中，称为同义词链表。 优点：插入、删除方便，缺点：占用存储空间多。 例 一组关键字为: (21，14，19，58， 65，32，72） H(K)=K MOD 11 21 65 ∧ 32 ∧ 19 ∧ 72 14 ∧ 58 0 1 2 3 4 5 6 7 8 9 10 4）链地址