算法与数据结构C语言描述第2版ppt课件

第6章集合 集合 是 种逻辑结构 其特点是元素之间没有什么联系 其逻辑关系集合为空集 只是共处于一个集合当中 查找 也叫检索 是根据给定的某个值 在表中确定一个关键字等于给定值的记录或数据元素关键字 是数据元素中某个数据项的值 它可以标识一个数据元素查找方法评价查找速度占用存储空间多少算法本身复杂程度平均查找长度ASL AverageSearchLength ASL P1C1 P2C2 PnCnPi 查找第i个元素的概率P1 Pi Pn 1Ci 找到第i个元素需比较次数 1 typedefintKeyType typedefintDataType typedefstruct KeyTypekey 字典元素的关键码字段 DataTypevalue 字典元素的属性字段 DicElement typedefstruct intMAXNUM 字典中元素的个数上界 intn 为字典中实际元素的个数 DicElement element 存放字典中的元素 SeqDictionary 2 顺序查找查找过程 从表的一端开始逐个进行记录的关键字和给定值的比较 如果某个记录的关键字等于k 则查找成功 否则查找失败 算法描述 例 1234567891011 513192137566475808892 找37 比较次数 5 比较次数 查找第1个元素 1查找第2个元素 2 查找第n个元素 n查找第i个元素 i查找失败 n 3 顺序表查找程序实现 intseqSearch SeqDictionary pdic KeyTypekey int position inti for i 0 in i 从头开始向后扫描 if pdic element i key key position i return 1 检索成功 position pdic n return 0 检索失败 4 顺序查找方法的ASL 优点 算法简单且适用面广 它对表的结构无任何要求 无论记录是否按关键字有序均可应用 而且上述所有讨论对线性链表也同样适用 缺点 平均查找长度较大 特别是当n很大时 查找效率低 猜字游戏 47 这是一个1 100之间的一个整数 最多要猜多少次一定能猜出 6 折半查找查找过程 每次将待查记录所在区间缩小一半适用条件 采用顺序存储结构的有序表算法实现设表长为n low high和mid分别指向待查元素所在区间的上界 下界和中点 k为给定值初始时 令low 1 high n mid low high 2 让k与mid指向的记录比较若k r mid key 已查到若kr mid key 则low mid 1 在表的后半部分继续查找重复上述操作 直至low high时 查找失败 7 算法描述 8 9 10 折半查找非递归算法 intbinarySearch SeqDictionary pdic KeyTypekey int position intlow mid high low 0 high pdic n 1 while lowelement mid key key position mid return 1 检索成功 elseif pdic element mid key key high mid 1 要检索的元素在左半区 elselow mid 1 要检索的元素在右半区 position low return 0 检索失败 11 分析二分法检索每经过一次比较就将检索范围缩小一半 第i次比较可能比较的元素个数如下表 比较次数可能比较的元素个数11 2022 2134 22 j2j 1若字典元素个数n刚好为20 21 2j 1 2j 1则最大检索长度为j 若2j 1 n 2j 1 1 则最大检索长度为j 1 所以 二分法检索的最大检索长度为 12 设检索每个元素的概率相同 则平均检索长度为 设字典元素个数n 2j 1 散列查找基本思想 在记录的存储地址和它的关键字之间建立一个确定的对应关系 这样 不经过比较 一次存取就能得到所查元素的查找方法定义散列函数 在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数散列函数是一种映象 是从关键字空间到存储地址空间的一种映象散列函数可写成 addr ai H ki ai是表中的一个元素addr ai 是ai的存储地址ki是ai的关键字 14 散列表 应用散列函数 由记录的关键字确定记录在表中的地址 并将记录放入此地址 这样构成的表叫散列表散列查找 又叫哈希查找 利用散列函数进行查找的过程叫哈希查找 以编号作关键字 构造哈希函数 H key keyH 1 1H 2 2 以地区别作关键字 取地区名称第一个拼音字母的序号作哈希函数 H Beijing 2H Shanghai 19H Shenyang 19 15 从例子可见 散列函数只是一种映象 所以散列函数的设定很灵活 只要使任何关键字的哈希函数值都落在表长允许的范围之内即可冲突 key1 key2 但H key1 H key2 的现象叫冲突同义词 具有相同函数值的两个关键字 叫该散列函数的同义词散列函数通常是一种压缩映象 所以冲突不可避免 只能尽量减少 同时 冲突发生后 应该有处理冲突的方法散列函数的构造方法直接定址法构造 取关键字或关键字的某个线性函数作散列地址 即H key key或H key a key b特点直接定址法所得地址集合与关键字集合大小相等 不会发生冲突实际中能用这种散列函数的情况很少 16 数字分析法构造 对关键字进行分析 取关键字的若干位或其组合作散列地址适于关键字位数比散列地址位数大 且可能出现的关键字事先知道的情况 例有80个记录 关键字为8位十进制数 散列地址为2位十进制数 分析 只取8 只取1 只取3 4 只取2 7 5 数字分布近乎随机所以 取 任意两位或两位与另两位的叠加作散列地址 17 平方取中法构造 取关键字平方后中间几位作散列地址适于不知道全部关键字情况key 4731 47312 22382361 如果地址长度为3位 则可以取第三位到第五位作为散列地址 即有h1 4731 382 折叠法构造 将关键字分割成位数相同的几部分 然后取这几部分的叠加和 舍去进位 做散列地址种类移位叠加 将分割后的几部分低位对齐相加间界叠加 从一端沿分割界来回折送 然后对齐相加适于关键字位数很多 且每一位上数字分布大致均匀情况 例关键字为 0442205864 散列地址位数为4 18 除留余数法构造 取关键字被某个不大于哈希表表长m的数p除后所得余数作散列地址 即H key keyMODp p m特点简单 常用 可与上述几种方法结合使用p的选取很重要 p选的不好 容易产生同义词随机数法构造 取关键字的随机函数值作散列地址 即H key random key 适于关键字长度不等的情况选取散列函数 考虑以下因素 计算散列函数所需时间关键字长度散列表长度 散列地址范围 关键字分布情况记录的查找频率 19 处理冲突的方法开放定址法方法 当冲突发生时 形成一个探查序列 沿此序列逐个地址探查 直到找到一个空位置 开放的地址 将发生冲突的记录放到该地址中 即Hi H key di MODm i 1 2 k k m 1 其中 H key 散列函数m 散列表表长di 增量序列分类线性探测再散列 di 1 2 3 m 1二次探测再散列 di 1 1 2 2 3 k k m 2 伪随机探测再散列 di 伪随机数序列 20 例表长为11的散列表中已填有关键字为17 60 29的记录 H key keyMOD11 现有第4个记录 其关键字为38 按三种处理冲突的方法 将它填入表中 1 H 38 38MOD11 5冲突H1 5 1 MOD11 6冲突H2 5 2 MOD11 7冲突H3 5 3 MOD11 8不冲突 38 2 H 38 38MOD11 5冲突H1 5 1 MOD11 6冲突H2 5 1 MOD11 4不冲突 38 3 H 38 38MOD11 5冲突设伪随机数序列为9 则 H1 5 9 MOD11 3不冲突 38 21 双重散列法方法 构造若干个散列函数 当发生冲突时 计算下一个哈希地址 即 Hi Rhi key i 1 2 k其中 Rhi 不同的散列函数特点 计算时间增加链地址法方法 将所有关键字为同义词的记录存储在一个单链表中 并用一维数组存放头指针 22 例已知一组关键字 19 14 23 1 68 20 84 27 55 11 10 79 散列函数为 H key keyMOD13 哈希表长为m 16 设每个记录的查找概率相等 1 用线性探测再散列处理冲突 即Hi H key di MODm H 55 3冲突 H1 3 1 MOD16 4冲突 H2 3 2 MOD16 5 H 79 1冲突 H1 1 1 MOD16 2冲突 H2 1 2 MOD16 3冲突 H3 1 3 MOD16 4冲突 H4 1 4 MOD16 5冲突 H5 1 5 MOD16 6冲突 H6 1 6 MOD16 7冲突 H7 1 7 MOD16 8冲突 H8 1 8 MOD16 9 ASL 1 6 2 3 3 4 9 12 2 5 14 1 68 27 55 19 20 84 79 23 11 10 H 19 6 H 14 1 H 23 10 H 1 1冲突 H1 1 1 MOD16 2 H 68 3 H 20 7 H 84 6冲突 H1 6 1 MOD16 7冲突 H2 6 2 MOD16 8 H 27 1冲突 H1 1 1 MOD16 2冲突 H2 1 2 MOD16 3冲突 H3 1 3 MOD16 4 H 11 11 H 10 10冲突 H1 10 1 MOD16 11冲突 H2 10 2 MOD16 12 2 用链地址法处理冲突 ASL 1 6 2 4 3 4 12 1 75 关键字 19 14 23 1 68 20 84 27 55 11 10 79 散列查找算法实现用线性探测再散列法处理冲突数据结构实现检索算法 程序实现插入算法 程序实现 typedefintKeyType typedefintDataType typedefstruct KeyTypekey 字典元素的关键码字段 DataTypevalue 字典元素的属性字段 DicElement typedefstruct intm m为基本区域长度 DicElement element HashDictionary DicElement是字典中元素类型 25 散列查找过程及分析散列查找过程 26 哈希查找分析哈希查找过程仍是一个给定值与关键字进行比较的过程评价哈希查找效率仍要用ASL哈希查找过程与给定值进行比较的关键字的个数取决于 哈希函数处理冲突的方法哈希表的负载因子负载因子 表中填入的记录数哈希表长度 27 作业 1设有一散列函数为H1 key key 11 该散列表使用双重散列法解决冲突 其再散列函数为 H2 key key 7 5关键字序列依次为 25 48 10 29 71 47 36 1 请在散列表中填入上述各关键字 2 要查找关键字47需进行几次比较 写出比较顺序 012345678910 28