《软件技术基础课件5——数据结构与算法4讲义》由会员分享，可在线阅读，更多相关《软件技术基础课件5——数据结构与算法4讲义（27页珍藏版）》请在金锄头文库上搜索。
1、Shanghai Jiao Tong University 1 第一部分 数据结构与算法 查找算法 p与排序一样，是最基本的算法，其他复杂算法的基础 举例：3D打印的数据准备STL模型切层 p主要内容： 基本概念 顺序查找 二分查找（折半查找） 分块查找 哈希表查找 p查找算法的选择与所采用的数据结构（尤其是存储结 构）有关 Shanghai Jiao Tong University 2 第一部分 数据结构与算法 查找算法 p基本概念与术语： 查找表：由一些具有相同可辨认特性的数据元素（或记录）构 成的集合 查找表的基本操作： 查询查询某个“特定数据元素”是否在查找表中 查询查询某个“特定数据
2、元素”的各种属性 在查找表中插入插入一个数据元素 删除删除查找表中的某个数据元素 静态查找表：仅作“查询查询”（检索）操作的查找表 动态查找表：作“插入插入”和“删除删除”操作的查找表 Shanghai Jiao Tong University 3 第一部分 数据结构与算法 查找算法 p基本概念与术语： 关键字（key）：数据元素中某个数据项的值，用它可以识别 一个数据元素 主关键字：可以惟一地惟一地标示一个数据元素的关键字。 不同记录的主关键字不同，如零件号、零件编码 次关键字：可以标示若干个数据元素的关键字，如：零件材料 查找（检索）：根据给定的某个值，在查找表中确定一个关键 字等于给定值
3、的记录或数据元素 查找成功：即找到满足条件的记录。此时可返回记录位置，也 可返回记录的全部内容。 查找不成功：即未找到满足条件的记录。返回空记录或空指针 。 为提高查找效率，在构造查找表时，可在集合中的数 据元素之间人为地加上某种确定的约束关系 Shanghai Jiao Tong University 4 第一部分 数据结构与算法 查找算法 p基本概念与术语： 查找算法评价：通常以关键字同给定值进行过比较的记录的个 数的平均值作为衡量查找算法好坏的依据 平均查找长度， ASL (Average Search Length)：为确定记录 在表中的位置，需要与给定值进行比较的关键字的个数的期望
4、值叫做查找算法的平均查找长度。 找到第 i 个记录 需比较的次数。 对含有 n 个记录的表，查找成功时： 第 i 个记录被 查找的概率。 Shanghai Jiao Tong University 5 第一部分 数据结构与算法 查找算法 p顺序查找： 对应的查找表为静态查找表 常用的顺序表、链表均可表达静态查找表 顺序查找指的是顺序表中的查找操作，从表的一端开始 ，逐个进行记录的关键字和给定值的比较 优点：算法简单，适应面广 缺点：平均查找长度大，不适用于表长大的查找表 平均查找长度： 找64 5 37 19 21 13 56 64 92 88 80 75 64 0 1 2 3 4 5 6 7
5、 8 9 10 11 Shanghai Jiao Tong University 第一部分 数据结构与算法 查找算法 p顺序查找： 对应的查找表为静态查找表 常用的顺序表、链表均可表达静态查找表 顺序查找指的是顺序表中的查找操作，从表的一端开始 ，逐个进行记录的关键字和给定值的比较 优点：算法简单，适应面广 缺点：平均查找长度大，不适用于表长大的查找表 平均查找长度： 查找成功时： 查找不成功时，比较次数总是 n + 1 次 假定查找成功与不成功概率相等，每个元素被查找的概率相等，则 Shanghai Jiao Tong University 第一部分 数据结构与算法 查找算法 p有序表的查找
6、二分查找（折半查找）： 每次将待查记录所在区间缩小一半 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 找21 lowhighmidhighmid low mid 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 找60 lowhighmid lowmidhigh mid high High low Shanghai Jiao Tong University 第一部分 数据结构与算法 查找算法 p有序表的查找二分查找（折半查找）： 二分查找的性能： 平均查找长度： 优点
7、：查找效率高 缺点：只能适用于有序表、且存储结构只能是顺序表。有 序表的存储结构为线性链表时，此方法也无效。 可以设计某种二叉树结构(二叉排序树)来构造有序表，然后基 于二叉树来实现二分查找（此时不属于顺序表查找） Shanghai Jiao Tong University 第一部分 数据结构与算法 查找算法 p索引顺序表的查找（分块查找）： 需要先建立索引顺序表： 1、将表分成几块，且表或者块间有序，或者分块有序分块有序 2、建立“索引表”（每个结点含有最大关键字域和指向本块 第一个结点的指针，且按关键字有序） ： 查找过程： 先确定待查记录所在块（顺序或折半查找） 再在内查找（顺序查找）
8、查38 1 7 13 22 48 86 索引表 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 53 22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 53 Shanghai Jiao Tong University 第一部分 数据结构与算法 查找算法 p分块查找： 分块查找的性能： 平均查找长度： 长度为 n 的表均分成 b 块，每块含 s 个记录 (b = n/s)，等 概率查找（每块查找的概率为 1/b
9、， 块中每个记录的查找概 率为 1/s ） 两部分组成：确定所在块，在块内顺序查找 顺序查找： 折半查找： Shanghai Jiao Tong University 第一部分 数据结构与算法 查找算法 p哈希表查找： 一般顺序表： 记录在表中位置和它的关键字之间不存在一个确定的关系 ；查找时给定值依次和关键字集合中各关键字进行比较。 效率取决于和给定值进行比较的关键字个数 平均查找长度不可能为0 哈希表： 若记录的关键字关键字与记录在表中的存储位置存储位置之间存在一种对 应（函数）关系。则： 记录的关键字为 key 记录在表中的位置（称为哈希地址哈希地址）为 f (key)，则称 此函数 f
10、 (key) 为哈希函数（散列函数）哈希函数（散列函数） 哈希函数哈希函数是一个映像映像，即：将关键字的集合映射到某个 地址集合上。它的设置很灵活，只要使得关键字的哈希 函数值都落在表长允许的范围之内即可 Shanghai Jiao Tong University 第一部分 数据结构与算法 查找算法 p哈希表查找： 哈希表： 冲突：由于哈希函数是一个压缩映像压缩映像，因此，在一般情况 下，很容易产生“冲突冲突”现象，即：key1 key2，而 f (key1) = f (key2)。这种具有相同函数值的关键字称为同义词同义词 Z Zhao, QQian, S Sun, L Li, WWu, C
11、 Chen, H Han, Y Ye, D Dai 设哈希函数 f (key) = (Ord(关键字首字母) - Ord(A) + 1) / 2 若添加关键字 Zhou，其存储位置是？ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 Dai Chen Zhao Qian Sun Li Wu Han Ye Zhou Zhou Zhou Zhou Shanghai Jiao Tong University 第一部分 数据结构与算法 查找算法 p哈希表查找： 哈希表： 根据设定的哈希函数H(key)和所选中的处理冲突的方法建 立的查找表查找表即为“哈希表哈希表” 该映射过程称为哈希造
12、表哈希造表或散列散列 基本思想：以记录的关键字为自变量，根据哈希函数，计 算出对应的哈希地址，并在此存储该记录的内容 哈希表哈希表既是一种存储方法，又是一种查找方法 当对记录进行查找时，再根据给定的关键字，用同一个哈 希函数计算出给定关键字对应的存储地址，随后进行访问 Shanghai Jiao Tong University 第一部分 数据结构与算法 采用何种构造哈希函数的方法取决于建表的关键字集合的情况（包括 关键字的范围和形态）： 基本原则基本原则是使产生冲突的可能性尽可能小 哈希函数的构造方法： 对数字类型关键字，常用下列构造方法： 若是非数字类型关键字，则需先对其进行数字化处理。 1
13、. 直接定址法 3. 平方取中法 5. 除留余数法 4. 折叠法 6. 随机数法 2. 数字分析法 Shanghai Jiao Tong University 第一部分 数据结构与算法 选取哈希函数，考虑以下因素： 1）计算哈希函数所需时间 2）关键字长度 3）哈希表长度（哈希地址范围） 4）关键字分布情况 5）记录的查找频率 哈希函数为关键字的线性函数 H(key) = key 或者 H(key) = a key + b 1. 直接定址法 特点：地址集合的大小 = 关键字集合的大小。 不同的关键字（调整 a 与 b 的值）不发生冲突。 实际中能使用这种哈希函数的情况很少。 Shanghai
14、Jiao Tong University 第一部分 数据结构与算法 2. 数字分析法（数字选择法） 构造：取关键字的若干位或其组合作哈希地址。 适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况。 例：有 80 个记录，关键字为 8 位十进制数，哈希表长为 100。则哈希地址可取 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 只
15、取 3、4 只取 2、7、5 数字分布近乎随机 所以：取 任意两位或两位 与另两位的叠加作哈希地址 Shanghai Jiao Tong University 第一部分 数据结构与算法 构造：以关键字的平方值的中间几位作为哈希地址。 求“关键字的平方值”的目的是“扩大差别”，同时平方值的中 间各位又能受到整个关键字中各位的影响。 3. 平方取中法（较常用） 此方法适合于关键字中的每一位都有某些数字重复出现频度很高重复出现频度很高的现象。 4. 折叠法 构造：将关键字分割成位数相同的几部分，然后取这几部分的叠加和叠加和 （舍去进位）做哈希地址。 移位叠加：移位叠加：将分割后的几部分低位对齐相加。 间界叠加：间界叠加：从一端沿分割界来回折叠，然后对齐相加。 适于关键字位数很多，且每一位上数字分布
