图
图是由顶点的有穷非空集合和顶点之间边的集合组成的，通常表示为 G(V,E)。其中 G 表示一个图、V 是图G中顶点的集合、E是图G中边的集合。
深度优先遍历
也称为深度优先搜索、简称 DFS
它从图中某个顶点 v 出发、访问此顶点、然后从 v 的未被访问的邻接点出发深度优先遍历图、直至图中所有和 v 有路径相同的顶点都被访问到。
广度优先遍历
又称为广度优先搜索、简称 BFS
类似于树的层序遍历。
最小生成树
我们把构造连通网的最小代价生成树称为最小生成树。
- Prim 普里姆算法
- Kruskal 克鲁斯卡尔算法
最短路径
对于网图来说、最短路径、是指两顶点之间经过的边上权值之和最少的路径、并且我们称路径上的第一个顶点时源点、最后一个顶点是终点。
- Dijkstra 算法
- Flody 算法
查找
查找就是根据给定的某个值、在查找表中确定一个其关键字等于给定值的元素。
顺序查找
又叫线性查找、是最基本的查找技术、它的查找过程是：从表中的第一个记录开始、逐个进行记录关键字和给定值比较、若某个记录的关键字和给定值相等、则查找成功、找到所查找的记录、如果直到最后一个记录、其关键字和给定值比较都不等时、则代表表中没有所查找的记录。
有序表查找
折半查找
折半查找又称为二分查找、它的前提是线性表中的记录必须是关键码有序的、线性表必须采用顺序存储。折半查找的基本思想是：在有序表中、取中间记录作为比较对象、若给定值与中间记录的关键字相等、则查找成功、若给定值小于中间记录的关键字、则在中间记录的左半区继续查找、若给定值大于中间记录的关键字、则在中间记录的右半区继续查找。不断重复上诉过程、直到查找成功或者查找区域无记录。
插值查找
插值查找是根据要查找的关键字 key 与查找表中最大最小记录的关键字比较后的查找方法、其核心在于插值的计算公式 key-a[low] / a[high]-a[low]
斐波那契查找
线性索引查找
数据结构的最终目的是提高数据的处理速度、索引是为了加快查找速度而设计的一种数据结构。索引就是把一个关键字与它对应的记录相关联的过程。
索引按照结构可以分为线性索引、树形索引和多级索引。
所谓的线性索引就是将索引项集合组织为线性结构、也称为索引表。
线性索引可以分为稠密索引、分块索引、倒排索引。
稠密索引
稠密索引是指在线性索引中、将数据集中的每个记录对应一个索引项。
对于稠密索引这个索引表来说、索引项一定是按照关键码有序排列的
稠密索引的个数等于数据集记录的个数
分块索引
是把数据集的记录分成若干块、并且这些块需要满足两个条件
- 块内无序
- 块间有序
倒排索引
将单词或记录作为索引、将文档id作为记录、这样便可以方便地通过单词或记录查找到其所在的文档。
二叉查找树
- 若它的左子树不空、则左子树上所有结点的值均小于它的根结点的值
- 若它的右子树不空、则右子树上所有结点的值均大于它的根结点的值
- 它的左右子树也分别为二叉排序树
构造一棵二叉排序树的目的、并不是为了排序、而是为了提高查找和插入删除关键字的速度
平衡二叉树
平衡二叉树是一种二叉排序树、其中每个结点的左子树和右子树的高度差至多等于 1。
将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子。值只有-1、0、1
多路查找树
多路查找树其每一个结点的孩子数可以躲雨两个、且每个结点处可以存储多个元素。
B树
B 树是一种平衡的多路查找树
左侧灰色方块表示当前结点的元素个数。
B+树
哈希表
散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f、使得每个关键字 key 对应一个存储位置 f
解决哈希冲突
- 开放定址法
- 再散列函数法
- 链地址法
- 公共溢出区法
排序
- 交换排序
- 冒泡排序
- 快速排序
- 插入排序
- 直接插入排序
- 希尔排序
- 选择排序
- 简单选择排序
- 堆排序
- 归并排序
- 基数排序
