记录的存储位置 = f(关键字)
散列技术是在存储位置和它的关键字之间建立一个确定的对应关系f,使得每个关键字key对应一个存储位置f(key)
对应关系函数f称为散列函数(哈希函数)
采用三列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表(哈希表)

查找步骤

当存储记录时，通过散列函数计算出记录的散列地址
当查找记录时，通过散列函数计算记录的散列地址，并按此散列地址访问该记录
各记录之间没有任何关系
散列表适合1对1查找，不适合查找范围，也不适合关键字对应多个结果的查找
散列函数通过不同的关键字，计算出了相同地址，称之为冲突

构建散列函数

散列函数原则=计算简单+分布均匀(散列地址)
直接定址法
取关键字的某个线性函数值为散列地址：f(key)=a*key+b
适合查找表小，key比较连续的情况，不常用
数字分析法
适合处理关键字位数比较大的情况
抽取关键字的某几位作为散列地址
平方取中法
平方取中法是将关键字平方之后取中间若干位数字作为散列地址
适合不知道关键字的分布，关键字位数不是很大的情况
折叠法
将关键字从左到右分割成位数相等的几部分，然后将这几部分叠加求和，并按散列表表长取后几位作为散列地址
除留余数法
f(key) = key mod p(p <= m)
m为表长
这个方法不仅可以对关键字直接取模，也可以通过折叠、平方取中后再取模
p的取值是关键，最好接近m的最小质数
随机数法
选择一个随机数，取关键字的随机函数值为它的散列地址
f(key) = random(key)
random为随机函数，适合关键字长度不等的情况
选取方法时要考虑的因素：
计算散列地址所需时间
关键字长度
散列表大小
关键字分布情况
记录查找频率

处理散列冲突的方法

开放定址法
一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入
1.线性探测法
fi(key) = (f(key)+di) mod m
其中di = 1,2,…,m-1
意思是，散列函数计算的地址已经被其他记录占据，就将散列函数计算的地址每次次加1到m-1的一个数,
再mod表长，将每次计算的结果当做新地址去探测有没有记录，如果没有就将该地址做为记录的地址
2.二次探测法
修改一次探测法di的取值
另di = 1^2,-1^2,2^2,-2^2,q^2,-q^2,其中q<=m/2
3.随机探测法
对di采用随机函数计算得到
再散列函数法
fi(key) = RHi(key)(i=1,2,3,…k)
就是用第一个散列函数计算的地址发生冲突就换第二个散列函数，如果第二个也发生冲突，则换第三个，以此类推
链地址法
地址处不存放单一记录，而是存放记录的链表，记录1指向记录2，计算得到地址相同，就继续指下去
公共溢出区法
不发生冲突的关键字放在基本表，将发生冲突的记录依次存放在溢出表，
查找时基本表找不到时就去查溢出表，溢出表找不到再宣告失败

特点：
每个结点的孩子可以多于两个，且每一个结点处可以存储多个元素
所有元素之间存在某种特定的排序关系
2-3树：每一个结点都具有两个或者三个孩子的多路查找树，所有叶子结点都在同一层次上
2结点：拥有两个孩子和一个元素，左子树包含元素小于结点元素，右子树则大于，要么有两个孩子，要么一个孩子也没有
3结点：拥有三个孩子两个元素，孩子和结点元素呈一定顺序，要么有三个孩子，要么一个孩子也没有
2-3-4树：每一个结点都具有两个或者三个孩子或四个孩子的多路查找树，所有叶子结点都在同一层次上
4结点：拥有四个个孩子三个元素，孩子和结点元素呈一定顺序，要么有四个孩子，要么一个孩子也没有

2-3树插入原理

1.如果是一个空树，直接插入形成一个2结点，即根结点
2.插入到一个结构为2结点的叶子上，直接将该2结点转为3结点
3.插入到一个结构为3结点的叶子结点，而该叶子结点双亲为2结点，则将该双亲2结点扩展为3结点，将元素插进去
4.插入到一个结构为3结点的叶子结点，而其双亲也为3结点，则继续往上找其双亲的双亲是否为2结点，若是，则将该2结点扩展为3结点，将双亲的一个元素挪上去，将3结点的元素挪到双亲，然后插入元素
5.插入到一个结构为3结点的叶子结点，往上追溯到根结点也为3结点，则说明该子树已满，需要增加树的高度，即将树每个结点拆都分成2结点，从而保证，所有叶结点在统一层次

2-3树删除原理

1.删除的元素位于结构为3结点的叶子上，直接删掉就好，3结点变2结点
2.删除元素位于结构为2结点的叶子上，
若双亲也为2结点结构，且双亲另一个孩子为3结点，则将元素删除后，左旋或右旋，将原来双亲移下来做孩子，将原来3结点一个元素移上去做双亲，另一个不动继续做孩子
若双亲为2结点结构，且双亲另一个孩子也为2结点,假设删除的是左子树的元素，则寻找双亲的双亲的直接后继元素来填充双亲的双亲的元素位置，将双亲的双亲的元素做双亲元素的孩子，将双亲元素移下来做孩子，将双亲原来的孩子移上去做双亲
若双亲是一个3结点结构，则将双亲一个元素移下来，3结点变2结点
若删除时，整颗树是一个满2叉树状态，则将树的深度变小，2结点变3结点
3.删除元素位于结构为2结点的双亲位置，若其右孩子为3结点则将其直接后继结点顶上去，3结点孩子变2结点
4.删除元素位于结构为3结点的双亲位置，若其直接前驱位于3结点结构，则将前驱顶上去，3结点变2结点
若其直接前驱位于2结点结构，则将前驱与直接后继合并为3结点，双亲变2结点

B树

一种平衡的多路查找树，2-3树和2-3-4树都是B树的特例
把结点最大的孩子树数目称为B树的阶，因此2-3树是3阶B树，2-3-4树是4阶B树
一个m阶的B树有如下属性
如果根结点不是叶结点，则其至少有两颗子树
每一个非根的分支节点都有K-1个元素和K个孩子，其中K满足：m/2向上取整 <= K <= m
所有叶子结点都位于同一层次
每个分支结点包含元素个数，该结点各元素及其孩子的信息

特征

首先得是一颗二叉排序树
左子树与右子树都是平衡二叉树
每个结点左子树与右子树的深度差的绝对值不能大于1
结点左子树深度减右子树深度的差叫做平衡因子BF，即|BF|<=1，BF=-1/1/0
平衡二叉树就是一颗二叉树上所有结点的平衡因子的绝对值小于等于1 的树

关键操作

左子树bf大于右子树bf，右旋
左子树bf小于右子树bf，左旋
左旋的子树的右子树若存在左子树，将该左子树做左旋子树根结点的右子树，左旋子树根结点做其右子树的左子树
右旋的子树的左子树若存在右子树，将该右子树做右旋子树根结点的左结点，右旋子树根结点做其左子树的右子树

构建

现用以下数据构建平衡二叉树
3,2,1,4,5,6,7,10,9,8

按照大于父节点做右子树小于父结点做左子树原则,将3,2,1构建树，当1进入树之后3的左子树深度2减右子树深度0大于1，以2为中心进行右旋，如图1
继续添加4和5，当5进入树之后，3的左右子树深度差为-2，断开2,3链接，将3,4,5,以4为中心左旋，再与2相连，如图2
继续添加6，当6进入树之后,这时2的bf为-2，以2的右子树根结点为中心左旋，此时1,2和3均为4的左子树，则将4的原左子树做新左子树的右子树，如图3
添加7,当7进入树之后,5的bf为-2，断开4,5链接，以6为中心左旋，再与4相连，如图4
添加10、9,当9进入树之后,6的bf为-2,断开6、7，因为10有左结点，先将9、10关系转换，让10做9孩子结点，然后以9为中心左旋，再与6相连,如图5
添加8,4、6的bf又变为-2,断开4、6,9的bf为1，因为将来要对6左旋，所以先将9右旋，使9的bf变成0或负值，再对6以7为中心左旋，如图6
最终结果如图7
代码链接

将无序的数组，把首项当做根结点开始，按照比双亲结点小的做左子树，比双亲结点大的做右子树的规则
建立一颗二叉树，对二叉树进行中序遍历，即得到无序数组从小到大的排序
二叉排序树特点
—- 若它的左子树不为空，则左子树上所有结点的值均小于它的根结构的值
—- 若它的右子树不为空，则右子树上所有结点的值均大于它的根结构的值
—- 它的左右子树也分别为二叉排序树(递归)
代码链接

稠密索引

索引表与数据表一对一，索引表的关键码是对应目标数据的提取，索引表有序，数据表无序

分块索引

将整个数据表分块，取每块数据中最大值建立索引表，块间有序，块内无序

静态查找: 数据集合稳定，不需要添加，删除元素的查找操作
– 组织数据宜用线性表结构
– 如果要对关键字排序，折半查找算法或斐波那契查找算法
动态查找：数据集合在查找过程中需要同时添加或删除元素的查找操作
– 二叉排序树，散列表结构

顺序查找

顺序查找/线性查找:从第一个(或者最后一个)记录开始，逐个进行记录的关键字和给定值进行比较，若某个记录的关键字和给定值相等，则查找成功。
—如果查找了所有的记录仍然找不到与给定值相等的关键字，则查找不成功

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

//方式一
function search(array,key){
	var i;
	for(var i = 0;i<= array.length;i++){
		if(a[i] == key){
			return i;
		}
  }
  return 0;
}
//方式二
function search(array,key){
	var i= array.length;
	a[0] = key;
	while(a[i] != key){
	  i--
  }
  return i;
}

插值查找(按比例查找)

查找方法类似于折半查找，只不过mid的值不再取low和high的中间值，
而是根据查找值在low和hight中间的大概位置确定mid
var mid = low +(high-low)*(num-list[low])/(list[high]-list[low]);
因此插值查找适用于有一定顺序规律的数组
代码链接

斐波那契查找(黄金查找)

同样适用于有一定顺序规律的数组
在折半查找的基础上根据斐波那契数列进行分割。
在斐波那契数列找一个等于略大于查找表中元素个数的数F[k]，
将原查找表扩展为长度为F[k]-1(如果要补充元素，则补充重复最后一个元素，直到满足F[k]-1个元素)
进行斐波那契分割，即F[k]-1个元素分割为前半部分F[k-1]-1个元素，后半部分F[n-2]-1个元素，剩一个做mid
找出要查找的元素在那一部分并递归，直到找到。

代码链接

关键路径

AOE网：在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，
这种有向图的边表示活动的网，我们称之为AOE网(Activity On Edge Network)
始点/源点:AOE网中没有入边的顶点
终点/汇点:AOE网中没有出边的顶点

etv:时间最早发生时间,顶点的最早发生时间
ltv:事件最晚发生时间，每个顶点对应事件最晚需要开始的时间，如果超出此时间将会延误着整个工期
ete:活动最早开工时间，弧的最早发生时间
lte:活动最晚发生时间，不推迟工期的最晚开工时间
关键路径的目的是在规划工程各项活动执行的顺序时，找出关键的活动，保证工程不延期


代码链接

背景

DAG(Directed Acyclic)图/无环图：无环的有向图
‘活动’：所有的工程或者某种流程都可以分为的若干个小的工程或者阶段
AOV(Active On Vertex Network)网：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系
这样的有向图为顶点表示活动的网即AOV网
拓扑序列：设G=(V,E)是一个具有n个顶点的有向图，V中的顶点序列V1，V2，……Vn满足若从顶点Vi到Vj有一条路径，则在顶点序列中顶点Vi必在顶点Vj之前,我们称这样的顶点序列为一个拓扑序列,
拓扑排序：所谓的拓扑排序，其实就是对一个有向图构造拓扑序列的过程,保证活动是按一定顺序进行

对AOV网进行拓扑排序的方法和步骤

——从AOV网中选择一个没有前驱的顶点(入度为0的顶点),并且输出它；
——从网中删去该顶点，并且删去从该顶点发出的全部有向边(将有向边终点入度减一)
——重复上述两步，直到剩余网中不再没有前驱的顶点为止。
代码链接

算法时间复杂度

对一个具有n个顶点，e条边的网来说，初始建立入度为0的顶点栈，要检查所有顶点一次，执行时间为O(n);
排序中，若AOV网无回路，则每个顶点入、出栈各一次，每个表结点被检查一次，因而执行时间是O(n+e);
因此整个算法时间复杂度是O(n+e)

网图：两个顶点经过的边上权值之和最少的路径
非网图：两个顶点之间经过的边数最少的路径
源点：路径起始的第一个顶点
终点：最后一个顶点

迪杰斯特拉(Dijkstra)算法

一个顶点到所有顶点的最短路径
主要思路：一步步求出它们之间顶点的最短路径，过程中都是基于已经求出的最短路径的基础上，求得更远顶点的最短路径
编程思路：类似于最小生成树普里姆算法
代码链接

佛洛依德(Floyd)算法

扩展版迪杰斯特拉(Dijkstra)算法，求图中所有结点到所有结点的最大路径，结果由二维数组展现
代码链接

图的各结点连线间存在权值，寻找一种访问路径,使得访问各结点最终的路径的权值和最小，
最终访问路径和结点形成树的结构，即最小生成树

普里姆算法

主要思路：研究对象为结点，以某顶点为起点，逐步找各个顶点上最小权值的边来构建最小生成树
编程思路：新建一数组，初始化为起点(最小生成树的根结点)在邻接矩阵所在行的权值
找到该组权值最小值,最小权值下标即要选择路径的终点，同时也是接下来要比较的邻接矩阵权值行的行号，
将该最小权值置0，然后将新建数组与矩阵权值行比较，
相同位置，矩阵行若小于新建数组值，就将新建数组值替换为矩阵行的值，
再次寻找新建数组中的最小权值，重复以上步骤
代码链接

克鲁斯卡尔算法

主要思路：研究对象为边，将边集数组从小到大排序，依次取边集数组的元素，判断边与边是否形成环路，不会形成则选择该边构建最小树
代码链接