61线性查找62折半查找63分快查找64二元查找树65散列

61线性查找62折半查找63分快查找64二元查找树65散列内容摘要：

delete( k, frchild )。 else if ( Frchild == NULL ) F = Flchild。 else if( Flchild == NULL ) F = Frchild。 else Fdata =deletemin(Frchild) } 在二元查找树中删除结点 Records deletemin( F ) { records tmp。 BST p。 if ( Flchild == NULL ) { p = F。 tmp = Fdata。 F = Frchild。 delete p。 return tmp。 } else return ( deletemin( Flchild )。 } 数据结构与算法 . 第六章 查 找 国家示范性软件学院 2020 秋 Slide. 6 14 例：二元树用二元链表表示，且每个结点的键值互不相同， 编写算法判别该二元树是否为二元排序树。 int judge(BTree *bt) { BTree *s[100],*p=bt。 int top=0,preval=min。 do{ while(p){ s[top++]=p。 p=plchild。 } if(top0){ p=s[top]。 if(pdatapreval) return 0。 //不是二元排序树 preval=pdata。 p=prchild。 } }while (p||top0)。 return(1) ； //是二元排序树 } 数据结构与算法 . 第六章 查 找 国家示范性软件学院 2020 秋 Slide. 6 15 散列法 —— 哈希（ Hash）查找 散列法 —— 地址散列法 被查找元素的存储 地址 = Hash ( Key ) Key BEIJING （北京 ) TIANJIN (天津 ) HEBEI (河北 ) SHANXI (山西 ) SHANGHAI (上海 ) SHANGDONG (山东 ) HENAN (河南 ) SICHUAN (四川 ) f1(key) 02 20 08 19 19 19 08 19 f2(key) 09 04 17 28 28 26 22 03 f3(key) 04 26 02 13 23 17 16 16 例：全国 30个地区的人口统计，每个地区为一个记录，内容如下： 编号 地区名 总人口 汉族 回族 … f1(key): 取关键字第一个字母在字母表中的序号 f2(key): 求第一和最后字母在字母表中序号之和，然后取 30的余数 f3(key): 将第一个字母的八进制看成十进制，再取 30的余数 数据结构与算法 . 第六章 查 找 国家示范性软件学院 2020 秋 Slide. 6 16 Hash查找的关键问题 ① 构造 Hash函数 ②制订解决冲突的方法 散列（ Hash）函数（表）分类 内散列表（数组） 外散列表（链表） 构造散列函数（ Hash）的几种方法 ：  直接定址法： Hash( key ) = key。 或 Hash( key ) = akey+b。  质数除余法  平方取中法  折叠法  数字分析法  随机数法 解决冲突的方法 ： 开放定址法 再散列法 链地址法 建立一个公共溢出区 数据结构与算法 . 第六章 查 找 国家示范性软件学院 2020 秋 Slide. 6 17 地址 01 02 03 04 05 … 25 26 27 … 100 年龄 1 2 3 4 5 … 25 26 27 … 100 人数 3000 2020 5000 … 6000 … … ： 地址 01 02 03 04 05 … 25 26 27 … 100 年份 1949 1950 1951 … 1973 … 人数 3000 2020 5000 … 6000 … … ： 直接定址法： Hash( key ) = key。 或 Hash( key ) = akey+b。 例一： Hash( key ) = key 例二： Hash( key ) = key + （ 1949） + 1 数据结。