数据结构09章.pptVIP

② 叠加可以有移位叠加和间界叠加两种方法。移位叠加：将每一部分的最低位对齐，然后相加；间界叠加：从一端向另一端沿分割界来回折迭，然后对齐相加。 ③ 将每一部分的最后一位对齐，然后相加 ，若相加产生进位，则舍弃之。 ④ 相加后的结果可直接作为Hash函数值(Hash地址)，或再用平方取中法、或除留余数法处理后作为Hash函数值。 key = 储地址为3位，即：000～999之间。 ① 移位叠加：划分得 872 834 32 872 834 + 32 1738 H(key)=738 例： 从右往左划分： 划分得 872 438 32 872 438 + 32 1342 H(key)=342 或 ② 间界叠加： 278 834 + 23 1135 H(key)=135 划分得 278 834 23 ① 移位叠加：划分得 328 348 72 328 348 + 72 748 H(key)=748 也可从左往右划分： 划分得 328 843 72 或 ② 间界叠加： 划分得 823 348 27 328 843 + 72 1243 H(key)=243 823 348 + 27 1198 H(key)=198 注：每一组关键字在求Hash地址时，只能采取同一种叠加法。 5) 随机数法： 选择一个随机函数，取关键字的随机函数值为它的Hash地址，即H(key) = random(key)，其中random为随机函数。 注：一般来说，当关键字长度不等时采用此法构造Hash函数。 Hash函数构造小结： 构造Hash函数时，通常考虑的因素有： ① 计算Hash函数所需时间； ② 关键字的长度； ③ Hash表的大小； ④ 关键字的分布情况； ⑤ 记录的查找频率。 3. 处理冲突的方法： 假设Hash表的地址集为0～(n－1)，所谓冲突是指由关键字得到的Hash地址为j(0≤j≤n－1)的位置上已存有记录，则“处理冲突”就是为该关键字的记录找到另一个“空”的Hash地址。 1) 开放定址法：Hi = (H(key)+di)mod m 此种解决冲突的办法是：若对记录Ri的关键字ki求得H(ki) = j，而哈希表中V[j]已被记录Ri–l占用，则找下一个空的位置 j+1，或 j+2，或……j+l，直到把Ri存放在所找到的下一个空位置上为止。这种寻找下一空位置的试探称为探测。其探测方法有三种： 其中：H(key) = key MOD p为Hash函数；m为表长；di为增量序列。(i=1,2,…,k; k≤m－1) (1) 线性探测再散列 (2) 二次探测再散列 (3) 伪随机探测再散列 di =1，2，3，4，…，m－1 di =12, ?12, 22, ?22, 32, ?32, …, ?k2 (k≤m/2) di =伪随机序列。 例：Hash表长m=16，设表中已填有3个记录，其关键字为19，70，33。Hash函数H(key)=key mod 13。现要将关键字为18的第四个记录填入表中，由Hash函数得Hash地址为5，产生冲突。 a) 线性探测：Hi= (H(key)+di) MOD m (di=1,2,3,…,m－1) H1= 6 H2= 7 H3= 8 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 70 19 33 18 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 70 19 33 Status CreatBST(BiTree T) { // 输入一组关键字值序列，建立一棵二叉排序树，根结点 // 指针为T，mend为常量标识符，其值标志序列输入完毕 T = NULL; Scanf(key); while (key ! = mend) { if ( ! (T = (BiTree) malloc (sizeof(BiTNode)))) } // CreatBST } // while exit(OVERFLOW); p—lchild = NULL; p—data = key; p—rchild = NULL; BST_Insert(T, p); 3) 算法实现： Status BST_Insert (BiTree T, Bitree p) { // 将指针p所指结点插入二叉排序树T中