数据结构第九章查找(与“查找”有关的文档共124张).pptx

数据结构第九章查找 数据结构第九章查找是指在数据集合中搜索特定元素的过程。查找表是由同一类型的数据元素或记录组成的集合，每个数据元素或记录都有一个唯一的关键字。查找的目的是在表中找到特定的元素，输出该记录，否则输出失败标志或失败位置。 查找表的操作有四种：查询某个特定的数据元素是否在表中；查询某个特定的数据元素的各种属性；在查找表中插入一元素；从查找表中删除一元素。 查找方法可以分为两大类：比较式查找法和计算式查找法。比较式查找法又可以分为静态查找表和动态查找表。静态查找表只作前两种操作，而动态查找表是查找过程中同时插入不存在或删除已存在的某个元素。计算式查找法也称为哈希（HASH）查找法。 评估查找方法的优劣可以用平均查找长度（ASL）来衡量。ASL是指比较次数的平均值，它是评估算法优劣的重要指标。ASL值越小，时间效率越高。 静态查找表是指查找表的抽象数据类型，具有Create、Destroy、Search和Traverse四种操作。Create操作用于构造一个含n个数据元素的静态查找表，Destroy操作用于销毁表，Search操作用于查找表中其关键字等于key的数据元素，Traverse操作用于按某种次序对表的每个元素调用函数Visit()。 静态查找表的查找算法有顺序查找、折半查找、静态树表的查找和分块查找等。顺序查找是指用逐一比较的方法顺序查找关键字，这显然是最直接的方法。折半查找是指将查找表分成两半，然后比较中间元素的关键字与要查找的关键字，如果中间元素的关键字小于要查找的关键字，则在右半部分继续查找，否则在左半部分继续查找。静态树表的查找是指使用树形结构来存储数据元素，然后使用树的遍历操作来实现查找。分块查找是指将查找表分成多个块，然后使用索引来快速查找要查找的元素。 静态查找表的顺序查找可以用顺序表表示静态查找表，那么Search函数可用顺序查找来实现。顺序查找的顺序存储结构可以使用数组来实现。顺序查找的时间复杂度为O(n)，空间复杂度为O(1)。 数据结构第九章查找是指在数据集合中搜索特定元素的过程，查找表的操作有四种，查找方法可以分为比较式查找法和计算式查找法，静态查找表的查找算法有顺序查找、折半查找、静态树表的查找和分块查找等。