数据结构及其变化-创新互联
集合
散列表
定义：
散列表：通过将元素映射到该表中的某一位置，来提高访问速度
装填因子：元素的个数/表的长度
碰撞： 多个关键字映射到同一位置的现象
碰撞检测方案：直接寻址法和链接法
简单一致散列：每个元素散列时是独立的，与其他元素无关
一致散列：假设每个关键字的探察序列`<0,1,2,…,m-1>的m!中排列的每一种可能性是相同的
关键字集合静态：关键字集合存入表中后不再变化创新互联建站主营米林网站建设的网络公司,主营网站建设方案,App定制开发,米林h5微信平台小程序开发搭建,米林网站营销推广欢迎米林等地区企业咨询
散列函数的设计
即映射函数 。
好的映射函数应该满足简单一致散列
通常利用关键字分布的限制性信息来设计，称为启发式
乘法散列
hk = ka
除法散列
hk = k mod a
全域散列及设计
作用在大小为m的表上的一组映射函数H，其能够保证任意两个元素，最多只有|H|/m个映射函数会发生碰撞。
这个设计的平均性能比较好
选则一个大质数p p> max(e)
ha,b(k)=((ak+b)mod p)mod m
Hp,m={ha,b:a∈Zp* ,b∈Zp}
Hp,m中共有p(p-1)个散列函数
设计证明：
即证明选择不同的值发生碰撞的概率不大于1/m
1 对于任意两个元素k,l(k!=l) r=(ak+b)mod p s=(al+b)mod p 可证明r!=s
2 可用r s 来表示a,b a=((r-s)((k-l)-1 mod p)) mod p, b=(r-ak)mod p 重要的是可以证明对和对一一对应。
3 可证明 给定r,p的选择数目为p-1个， 碰撞概率 r== s mod m 的数目最多为 (p-1)/m,所以碰撞概率最多为1/m
完全散列
定义：在静态集合上最坏查找是O(1)的散列技术
1 最外围函数为h(k)=((ak+b)mod p)mod m (是全域散列)
2 散列表S的大小为mj 相关的散列函数为hj(k)=((ajk+bj)mod p)mod mj
3 mj为落在该pos下的元素个数的平方
E(x)=Cn2 * 1n2 = n2n2*1n2 < 1/2
开放地址法
所有的元素都放在表中。依据探查序列算法解决发生碰撞时下一个探查的位置
该结构在删除元素时，不能将对应的位置设置为空，而是设置一个deleted的标记
线性探查 h(k,i)=(h(k)+ci)mod m
二次探查 h(k,i)=(h(k)+c1i+c2i2)mod m
双重散列 h(k,i)=(h(k)+h2(k)i)mod m
线
栈
后进先出的数据结构
队列
先进先出的数据结构
树
二叉树
完全二叉树:只有最下面的两层结点度能够小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树
满二叉树:除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树
平衡二叉树:其左右高度相差不超过1，并且都是平衡二叉树，
各基本操作的运行时间都是O(h) h为树的高度
avl树=二叉搜索树+平衡
红黑书
根节点和叶子节点是黑色的，两者之间黑色节点的个数是相同的。另外一种树是红树，其子节点都是黑树 此为红黑树
最坏情况下操作时间为O(lgn)
每个节点 (color,key,left,right和p)
左旋
长子的次子是自己的长子
自己是长子的次子
右旋
次子的长子是自己的次子
自己是次子的长子
增
根据二叉树找到挂靠的父节点，直接插入，颜色为红
增调：（红黑颠倒简称倒）
伯红 => 伯父爷倒 我=我爷 命名为(上窜)
伯黑 => （我是长子 => 我=父 左旋）父爷倒 爷右旋
删
确定实际要删的节点y（当前节点(双子不全)或者其继任）所以y一定不是双子
确定y的替代节点x（唯一的孩子或空 ）
x向上取代y
若y黑，则删调
删调：比较麻烦，后续再提炼
B树
定义 B树是平衡(t+)叉树 t>=2 是最小度数
曾
B-TREE-SPLIT-CHILD ：当前节点中间关键字放到上面，左右分拆为两个
B-TREE-INSERT-CHILD：
1 当跟节点为2t-1时，拆
2 插入元素到指定node位置，如果node满了，拆；（如果父节点满了，拆）
删
1 删掉指定元素k 如果该元素位于内节点中。如果其有合适的前继或后继e，则删掉e;否则删掉k,合并左右子节点，
2 若合并 则进行合并后调整: 检查该节点元素个数，如果不满足，则从左右兄弟拉元素或者合并
二叉堆
父元素大于（或小于）子元素的满二叉树
二项堆
可合并堆
支持create、insert、min、pop、union五种操作（建增查删合）的数据结构
二项树
一种递归定义的有序树。二项树B0只包含一个节点。二项树Bk 由两棵Bk-1连接而成，其中一颗树是另一棵树的左孩子。
最小堆有序:结点的关键字大于或等于其父节点的关键字。
二项堆
最坏情况下时间复杂度为lgn
是具有最小堆有序性质的二项树的一个集合，其中不存在根度数重复的元素
容易证明m个元素 二项树的个数为<=lg2m+1
斐波那契堆
除删除外其余操作时间为O(1)
由一组最小堆有序树构成，但不一定是二项树
树根之间是无序的，树根之间和各个树内部都是双链。
图
先序、中序、后序
最小生成树
无向加权连通图
<G,E>,选择一组E1 ,E1 ∈E,能连接所有顶点，求min(E1)
kruskal算法（OElgE）
优先收集全图最小边（除非该边的两个顶点都在已知的顶点中）
Prim算法（OElgV）
收集已知顶点外围的最小边
单源最短路径
最短路径估计：对每个顶点
v∈V,都设置一个属性d[v],用来描述从源点到v的最短路径的上界。
松弛技术：
1 初始化每个顶点v与原点u间的最短路径估计为无穷
2 针对
bellman-ford算法（OEV）
用每个顶点松弛每条边 ,可以处理边为负数的情况
dijkstra算法（Ov2）
1 顶点集合S，将S边上最短路径的顶点u加入S
2 使用u松弛u周围的边
不可以处理边为负数的情况
多源最短路径
定义：计算每对顶点间的最短路径
闭包：任何顶点之间都存在路径的有向图
floyd-warshall算法(OV3)
用任意顶点k松弛任意两个顶点
<u,v>间的边
johnson算法
依次执行Dijkstra算法
大流
流守恒：进入某顶点的速度等于离开该顶点的速度
问题描述：在不违背容量限制的条件下，把物质从源点传输到汇点的大速率是多少？
ford-fulkerson方法依赖三种重要思想:残留网络，增广路径、割。
残留流量
Cf(u,v)=c(u,v)-f(u,v)
残留网络
给定一流网络G=(V,E)和流f，由f压得的G的残留网络是Gf=(V,Ef)
增广路径
增广路径为残留网络中的一条从源点到汇点的简单路径
流网络的割
将网络切成两部分的一种割法
最小割 就是最小容量的割
大流最小割 最小割就是大流
基本的ford-fulkerson算法
1 全置0
2 依次寻找一个增广路径p,计算其最小容量c
3 依次对该路径上的每段子路径的流加上c，每段子路径的容量减去c
所以算法的关键是如何寻找到一个增广路径（寻增算法）
edmonds-karp算法
使用广度优先算法找增广路径
压入与重标记算法
定义 依次检查残留网络的每个顶点的相邻顶点
两种基本操作：1 把流的余量从一个顶点压向另一个顶点 2重标记
压入：把当前节点的余流沿着边压向邻点
重标记：当前边为最低邻点的高度+1
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
分享名称：数据结构及其变化-创新互联
文章转载：http://cdiso.cn/article/copihs.html
