数据结构--查找--思维导图.pdf

数据结构--查找--思维导图.pdf 本资源是关于数据结构中查找算法的详细介绍，包括顺序查找、折半查找、散列表等多种查找算法的原理、实现和应用。 顺序查找 顺序查找是最基本的查找算法，它的实现方法是从查找表的开始逐个比较关键字，直到找到目标元素或遍历整个表。顺序查找的时间复杂度为O(n)，其中n是查找表的长度。 折半查找 折半查找是对有序表的查找算法，它的实现方法是将表分为两半，然后比较关键字与中间元素的关键字，若相等则返回该元素的位置，否则在前半部分或后半部分继续查找。折半查找的时间复杂度为O(log2n)，其中n是查找表的长度。 散列表 散列表是一种基于关键字的查找数据结构，它的实现方法是将关键字映射到某个地址，然后根据该地址访问对应的数据元素。散列表的查找效率取决于散列函数、处理冲突的方法和填装因子。 散列函数 散列函数是一个把查找表中的关键字映射成该关键字对应的地址的函数。散列函数的定义域必须包含全部需要存储的关键字，而值域的范围则依赖于散列表的大小或地址范围。散列函数应尽量简单，能够在较短时间内计算出任一关键字对应的散列地址。 处理冲突 处理冲突是指散列函数可能会把多个不同的关键字映射到同一地址下的情况。常见的处理冲突方法有开放定址法、链地址法和再散列法。 开放定址法 开放定址法是指可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。其实现方法是Hi = (H(key) + di) % m，其中m为散列表表长，di为增量序列。 链地址法 链地址法是指把所有同义词存放在一个线性链表中，这个线性链表由地址唯一标识，即散列表中每个单元存放该链表头指针。链地址法适用于经常进行插入和删除的情况。 分块查找 分块查找又称索引顺序查找，它吸取了顺序查找和折半查找各自的优点，既有动态结构，又适于快速查找。其实现方法是将查找表分为若干子块，每块的元素可以无序，但块间是有序的，即对于所有块有第i块的最大关键字小于第i+1块的所有记录的关键字。建立索引表，索引表中的每个元素含有各块的最大关键字和各块中各记录的关键字。