算法与数据结构 索引查找的实现

发布网友 发布时间：2022-04-21 03:19

我来回答

共1个回答

热心网友 时间：2022-05-10 11:16

二分查找法、哈希查找法、二叉排序树查找法等各种查找算法。1.线性表上的查找： 主要分为三种线性结构：顺序表，有序顺序表，索引顺序表。对于第一种，我们采用传统查找方法，逐个比较。对于及有序顺序表我们采用二分查找法。对于第三种索引结构，我们采用索引查找算法。其中，二分查找还要特别注意适用条件以及其递归实现方法。 2.树表上的查找： 树表主要分为以下几种：二叉排序树，平衡二叉树，B树，键树。由于二叉排序树与平衡二叉树是一种特殊的二叉树，所以与二叉树的联系就更为紧密。 二叉排序树，它的中序遍历结果是一个递增的有序序列。平衡二叉树是二叉排序树的优化，其本质也是一种二叉排序树，只不过，平衡二叉树对左右子树的深度有了限定。 B树是二叉排序树的进一步改进，也可以把B树理解为三叉、四叉....排序树。因为这两种算法涉及到B树结点的*和合并，是一个难点。键树也称字符树，特别适用于查找英文单词的场合。一般不要求能完整描述算法源码，多是根据算法思想建立键树及描述其大致查找过程。 3.基本哈希表的查找算法： 哈希表查找的基本思想是：根据当前待查找数据的特征，以记录关键字为自变量，设计一个function，该函数对关键字进行转换后，其解释结果为待查的地址。堆排序属于选择排序类型的排序，是一树形选择排序。堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。 堆排序的最坏时间复杂度为O(nlgn)。堆排序的平均性能较接近于最坏性能。 由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。 堆排序是就地排序，辅助空间为O(1)， 它是不稳定的排序方法。堆排序，是利用堆这种数据结构的性质，通过堆元素的删除、调整等一系列操作将最小数选出放在堆顶。堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大(或最小)的记录。堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。
vae.la