软件技术基础课件5——数据结构与算法4剖析.ppt

* * * * * * * * * * * * * * * * * * * * Shanghai Jiao Tong University Shanghai Jiao Tong University 第一部分 数据结构与算法 查找算法 与排序一样，是最基本的算法，其他复杂算法的基础 举例：3D打印的数据准备——STL模型切层 主要内容： 基本概念 顺序查找 二分查找（折半查找） 分块查找 哈希表查找 查找算法的选择与所采用的数据结构（尤其是存储结构）有关 * 第一部分 数据结构与算法 查找算法 基本概念与术语： 查找表：由一些具有相同可辨认特性的数据元素（或记录）构成的集合 查找表的基本操作： 查询某个“特定数据元素”是否在查找表中 查询某个“特定数据元素”的各种属性 在查找表中插入一个数据元素 删除查找表中的某个数据元素 静态查找表：仅作“查询”（检索）操作的查找表 动态查找表：作“插入”和“删除”操作的查找表 * 第一部分 数据结构与算法 查找算法 基本概念与术语： 关键字（key）：数据元素中某个数据项的值，用它可以识别一个数据元素 主关键字：可以惟一地标示一个数据元素的关键字。 不同记录的主关键字不同，如零件号、零件编码 次关键字：可以标示若干个数据元素的关键字，如：零件材料 查找（检索）：根据给定的某个值，在查找表中确定一个关键字等于给定值的记录或数据元素 查找成功：即找到满足条件的记录。此时可返回记录位置，也可返回记录的全部内容。 查找不成功：即未找到满足条件的记录。返回空记录或空指针。 为提高查找效率，在构造查找表时，可在集合中的数据元素之间人为地加上某种确定的约束关系 * 第一部分 数据结构与算法 查找算法 基本概念与术语： 查找算法评价：通常以关键字同给定值进行过比较的记录的个数的平均值作为衡量查找算法好坏的依据 平均查找长度， ASL (Average Search Length)：为确定记录在表中的位置，需要与给定值进行比较的关键字的个数的期望值叫做查找算法的平均查找长度。 找到第 i 个记录 需比较的次数。 对含有 n 个记录的表，查找成功时： 第 i 个记录被 查找的概率。 * 第一部分 数据结构与算法 查找算法 顺序查找： 对应的查找表为静态查找表 常用的顺序表、链表均可表达静态查找表 顺序查找指的是顺序表中的查找操作，从表的一端开始，逐个进行记录的关键字和给定值的比较 优点：算法简单，适应面广 缺点：平均查找长度大，不适用于表长大的查找表 平均查找长度： 找64 5 37 19 21 13 56 64 92 88 80 75 64 0 1 2 3 4 5 6 7 8 9 10 11 第一部分 数据结构与算法 查找算法 顺序查找： 对应的查找表为静态查找表 常用的顺序表、链表均可表达静态查找表 顺序查找指的是顺序表中的查找操作，从表的一端开始，逐个进行记录的关键字和给定值的比较 优点：算法简单，适应面广 缺点：平均查找长度大，不适用于表长大的查找表 平均查找长度： 查找成功时： 查找不成功时，比较次数总是 n + 1 次 假定查找成功与不成功概率相等，每个元素被查找的概率相等，则 第一部分 数据结构与算法 查找算法 有序表的查找——二分查找（折半查找）： 每次将待查记录所在区间缩小一半 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 找21 low high mid high mid 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 low high mid low mid high mid high High low 第一部分 数据结构与算法 查找算法 有序表的查找——二分查找（折半查找）： 二分查找的性能： 平均查找长度： 优点：查找效率