第八章查找wl1.ppt

8.1、静态查找表 8.1.2 折半查找 目标：每次将待查记录所在区间缩小一半 前题：采用顺序存储结构的有序表 一.算法描述 (1)设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值 (2)初始时，low=1,high=n,mid=?(low+high)/2 (3)让k与mid指向的记录比较 i)若k==r[mid].key，查找成功 ii)若kr[mid].key，则high=mid-1 iii)若kr[mid].key，则low=mid+1 (4)重复(3)操作，直至lowhigh时，查找失败 二、算法演示 8.1.5 索引顺序的查找 查找过程：将表分成几块，块内无序，块间有序；先确定待查记录所在块，再在块内查 适用条件：分块有序表 算法实现 (1) 用数组存放待查记录,每个数据元素至少含有关键字域 (2)建立索引表，每个索引表结点含有最大关键字域和指向本块第一个结点的指针 分块查找方法评价 8.2、动态查找表 找结点q前驱和后继的方法： 1、如何求A的后继： （1）刚开始，让p指到q的右子树 （2）循环，让p沿左指针一直往下，直到p-lchild为空 8.2.3 B树 8.3 散列查找 8.3.1 散列的概念 1、基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法 2、定义 哈希（散列）函数——在记录的关键字与记录的存储地址之间建立的一种对应关系叫~ 散列函数是一种映象，是从关键字空间到存储地址空间的一种映象。 散列函数可写成：addr(ai)=H(ki) 》ai是表中的一个元素 》addr(ai)是ai的存储地址（可能是地址或序号） 》ki是ai的关键字 散列表——应用散列函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫~ 散列查找——利用散列函数进行查找的过程叫~ (2)散列查找算法实现 用线性探测再散列法处理冲突 实现 查找过程：同前 删除：只能作标记，不能真正删除 插入：遇到空位置或有删除标记的位置就可以插入 算法描述： 用外链表处理冲突算法 （见教材） 关键字 集合 存储地址 集合 hash 例 30个地区的各民族人口统计表 编号 地区别 总人口 汉族 回族…... 1 北京 2 上海 …... …... 以编号作关键字， 构造散列函数：H(key)=key H(1)=1 H(2)=2 以地区别作关键字，取地区 名称第一个拼音字母的序号 作哈希函数：H(Beijing)=2 H(Shanghai)=19 H(Shenyang)=19 从例子可见： 散列函数只是一种映象，所以散列函数的设定很灵活，只要使任何关键字的散列函数值都落在表长允许的范围之内即可 冲突：key1key2，但H(key1)=H(key2)的现象叫~ 同义词：具有相同函数值的两个关键字，叫该散列函数的~ 散列函数通常是一种压缩映象，所以冲突不可避免，只能尽量减少；同时，冲突发生后，应该有处理冲突的方法 8.3.2 散列函数的构造方法 (1)直接定址法 构造：取关键字或关键字的某个线性函数作散列地址，即H(key)=key 或 H(key)=a.key+b 特点: 直接定址法所得地址集合与关键字集合大小相等，不会发生冲突 实际中能用这种哈希函数的情况很少 例 有80个记录，关键字为8位十进制数，哈希地址为2位十进制数 8 1 3 4 6 5 3 2 8 1 3 7 2 2 4 2 8 1 3 8 7 4 2 2 8 1 3 0 1 3 6 7 8 1 3 2 2 8 1 7 8 1 3 3 8 9 6 7 8 1 3 6 8 5 3 7 8 1 4 1 9 3 5 5 ….. ….. ?? ? ??? ?? 分析： ?只取8 ?只取1 ?只取3、4 ?只取2、7、5