内查找和外查找:都在内存中查找即内查找,外查找还涉及外存,比如硬盘等。
分类包括:
1、线性表的查找
又分顺序查找、二分查找和分块查找。
1)二分查找又叫折半查找
- 折半查找要求线性表有序。
- 有序是指存在某个关键字的序列。
- 基本思想是拆半。
- 二分查找可以用二叉树来描述,按照二分查找的思想建立一棵二叉树,此树称为二分查找的“判定树”。
- 二分查找的最坏性能和平均性能相近。
2)分块查找
线性表分成块,每块内部不要求有序,但块块之间应有序
2、树表查找
1)二叉排序树
- 左子树非空,则左树上所有节点均小于根。
- 右子树非空,则右树上的所有节点均大于根。
- 左右子树分别仍是二叉排序树
- 二叉排序树中的“中序遍历”是递增序列。
- 同一序列,构成的二叉排序树可能不同。
2)平衡的二叉排序树
- 要求二叉排序树的左子树和右子树的高度最多相差1
- 这个差被成为平衡因子
- 平衡二叉树避免了顺序查找行为的出现。
3)B树
前面方法都只适用于内查找,B树则适合外查找。
B-树是平衡二叉树的一种。
定义一个m阶的B树
- 每个节点至多有m个孩子
- 根节点有两个孩子或者为空
- 每个节点至少有(m/2的上限)个孩子(除了根和叶)。
- 叶在同一层,且叶中没有关键信息。
- 有K个孩子的非叶节点恰好有k-1个关键字。
查找B树时,给定关键字的查找首先从根开始,一定能确定要找的K在Ki和Ki+1之间。在这之间重复寻找,直到成功或者返回指针为空。
文件系统NTFS对目录索引的管理使用B树。
分享到:
相关推荐
一、填空 ...试在0~19的散列地址空间中对关键字序列(19,01,23,14,55,20,84,27,68,11,10,77)造哈希表,并求等概率下查找成功时的平均查找长度。 .......
数据结构-查找算法(代码+报告)
数据结构课程设计 航班检索程序 包括对于各类航班信息的查找,用记事本作为简易数据库
数据结构 查找实验报告 1、在顺序表中查找某个数据,若查找成功输出其位置及查找次数,若查找失败输出失败信息。 2、在有n个元素的有序顺序表上进行二分查找。 (1)建立有n个元素的有序顺序表,数据元素为整型。 ...
数据结构课程设计,索引顺序查找,用c++做的~有源代码,任务书,报告,超全~~~
数据结构实践教程:内含17个经典数据结构实例 根据五个不同数据结构,对每个结构都有2~4个经典实例。每个实例都有项目简介、设计思路、数据结构、完整程序、运行结果五个部分,可以直接拿来做一篇课程设计。实例名称...
数据结构往往同 高效的检索算法和索引技术有关。 数据结构还包含数的操作,排序和查找等一系列问题。其中,排序的功能是将一个数 据元素(或记录)的任意序列,重新排列成一个按关键字有序的排列。数据结构的排序 有5...
数据结构课程设计,内容: 一篇英文文章存储在一个文本文件中,然后分别基于线性表、二叉排序树和哈希表不同的存储结构,完成单词词频的统计和单词的检索功能。同时计算不同检索策略下的平均查找长度ASL,通过比较...
对于本设计,可采用基数排序法对一组具有结构特点的飞机航班号进行排序,利用二分查找法对排好序的航班记录按航班号实现快速查找,按其他次关键字的查找可采用最简单的顺序查找方法进行,因此他们用得较少。...
山东大学《数据结构》实验指导06查找或检索.docx
1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象 以及它们之间的 关系 和运算等的学科。 2. 数据结构被形式地定义为(D, R),其中D是 数据元素 的有限集合,R是D上的 关系 有限集合。 3. 数据...
1)查询某个“特定的”数据元素是否在查找表中; 2)检索某个“特定的”数据元素的各种属性; 3)在查找表中插入一个数据元素; 4)从查找表中删去某个数据元素
数据结构课程设计例题,约瑟夫环问题,职工信息检索系统(查找的应用—哈希法),排序算法的比较与分析(排序的应用
所谓查找(Search)又称检索,就是在一个数据元素集合中寻找满足某种条件的数据元素。关于有序表的查找,有折半查找、插值查找、斐波那契查找等,它们的原理和实现方法各有不同,对不同数据的处理也各有优劣。 查找在...
算法是解决问题的一系列步骤。...查找算法:用于在数据结构中查找特定元素的算法,如线性查找、二分查找等。在C#中,可以使用List<T>.Contains()方法或Dictionary, TValue>.ContainsKey()方法来查找元素。
1、设计合适的数据结构存储朋友、分组信息,将以上文件内容导入其中(如果你觉得以上文件中的信息不合适,可以自行处理,删除某列、增加属性、规范化数据均可,如果你认为有必要,甚至去掉“编号”都可以)。...
个人根据各自的理解的不同而有不同 的表述方法: Sartaj Sahni在他的《数据结构、算法与应用》一书中称:"数据结构是数据对象,以与存在于该 对象的实例和组成实 例的数据元素之间的各种联系。这些联系可以通过定义...
在计算机科学中,AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1,所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者...
本项目要求词典检索系统实现变位 词的查找功能 2。基本要求 (1)用文件 diction.txt存储词典 (2)尽力改进算法效率 1.构造Pair类 struct Pair {String stampCode; //特征码 LinkList<String> words; //词链表 ...
一、 实验目的和要求 掌握不同的检索方法,并能用高级语言实现检索算法; 熟练掌握顺序表和有序表的检索方法,以及静态检索树的构造方法和检索算法... 熟悉各种存储结构的特征以及如何应用树结构解决具体问题;