根据某个关键字查找某个数据元素
1.线性查找
遍历所有元素,优化策略是减少比较次数,复杂度O(n)
2.有序表查找
1).二分查找O(logn)
public static int binarySearch(int k, int[] arr) { int high = arr.length - 1; int low = 0; int mid; while (low <= high) { mid = (low + high) / 2; if (k == arr[mid]) { return mid; } else if (k > arr[mid]) { low = mid + 1; } else { high = mid - 1; } } return -1; }
3.线性索引查找
稠密索引:将数据集中的每一个记录对应一个索引项,索引按关键码有序排列
分块索引:快内无序、块间有序,块中最大关键字,块中的记录数,块的首地址
倒排索引:次关键码、记录号
4.二叉排序树
left-child < parent < right-child
二叉树的删除,删除叶子或只有右子树或只有左子树的情况补上就行,但是既有左子树又有右子树的情况,找到被删除节点的直接前驱或直接后继替还被删除节点。
中序遍历,复杂度O(logn),考虑树变成了链表的情况O(n)
5.平衡二叉树:二叉排序树但是左子树和右子树高度差1
找出最小不平衡子树,计算每个节点的平衡因子BL,> 1进行右旋, < -1进行左旋
6.多路查找树(B树)
每一个节点的孩子可以多于2个,每个节点可以存储多个元素
2-3:每个节点2个孩子或3个孩子
2节点:一个元素2个(或没有)孩子
3节点:一大一小2个元素3个(或没有)孩子
2-3-4:对2-3树的扩展,多了4节点3元素
BTree:平衡多路查找树,节点最大的孩子为BTree的阶
B的阶数与硬盘大小相匹配,与磁盘页面进行多次访问
B+Tree:分支出现该元素则作为该分支下的叶子节点,每一个叶子节点保存的后一个叶子节点指针
7.散列表O(1)
适合查找和给定值相等问题
要求:简单、均匀、存储利用率高
直接定址、数字分析、平方取中、折叠法、取模、随机数
处理冲突的方法:
开放定址:寻找下一个 fi(k) = (f(k) + di) % m,线性探测,二次探测:di^2,随机探测:random(di)
再次散列:还一种散列方式
链地址方:构建链表,存储头指针
公共溢出区:为冲突关键字建立的顺序表
相关推荐
数据结构与算法--面向对象的C++设计 数据结构与算法--面向对象的C++设计 数据结构与算法--面向对象的C++设计 数据结构与算法--面向对象的C++设计 数据结构与算法--面向对象的C++设计 数据结构与算法--面向对象的C++...
算法-数据结构和算法-15-二分查找.rar
数据结构及算法-查找.ppt该文档详细且完整,值得借鉴下载使用,欢迎下载使用,有问题可以第一时间联系作者~
Python版数据结构与算法-查找算法源代码,含顺序搜索、二分查找、哈希表搜索、树(图)数据查找源代码
数据结构与算法-学生成绩管理系统(以顺序表来实现)
数据结构实验七-查找 数据结构实验七-查找全文共15页,当前为第1页。数据结构实验七-查找全文共15页,当前为第1页。实验七 查找 数据结构实验七-查找全文共15页,当前为第1页。 数据结构实验七-查找全文共15页,当前...
主要内容包括:面向对象编程的基本原理,判定算法效率的方法,堆栈、队列及其应用,对于多种递归的详细讨论,二叉树、B树、2-4树等的查找和遍历等,分析排序、散列等数据结构的应用,图、NP完整性,数据压缩算法、...
数据结构与算法》以基本数据结构和算法设计策略为知识单元,系统地介绍了数据结构的知识与应用、计算机算法的设计与分析方法,主要内容包括线性表、树、图和广义表、算法设计策略以及查找与排序算法等。《数据结构与...
数据结构与算法-散列表查找操作实验.pdf
国外经典教材 数据结构与算法----面向对象的C++模式 ...8 散列,哈希表与分散表 9树 10查找树, 11堆和优先队列 12集合,多重集和分区 13动态存储分配 14 算法模式和问题求解 15 排序算法和排序器 16 图和图算法
用数据结构的经典算法-查找折半,直接。排序有冒泡,希尔,快速,堆排序等都是必须知道的。本程序将上面所有的算法都结合在一起。并且以成绩查询系统将其全部实现。本程序全部以C++编写。
算法与数据结构它们分别涵盖了以下主要内容: 数据结构(Data Structures): ...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
(1)掌握顺序查找,二分法查找和索引查找的算法思想及程序实现方法。 (2)掌握二叉排序树、AVL树的查找、插入、删除、建立算法的思想及程序实现方法。 (3)掌握散列存储结构的思想,能选择合适散列函数,实现...
数据结构-查找算法(代码+报告)
1)数据结构的基本概念 2)线性表、栈与队列的定义,存储表示 3)树和二叉树的定义、二叉树的遍历 4)图的定义、存储结构、图的遍历 5)排序与查找
数据结构与算法-java版 ...以基本数据结构和算法设计策略为知识单元,系统地介绍了数据结构的知识与应用、计算机算法的设计与分析方法,主要内容包括线性表、树、图和广义表、算法设计策略以及查找与排序算法等。
数据结构实验报告-查找与排序算法17.doc
数据结构实验报告-查找与排序算法18.doc
数据结构实验报告-查找与排序算法22.doc
《数据结构与算法》-李春葆 实验报告-典型查找算法实践-二叉查找树实现查找