@shaobaobaoer
2019-03-17T07:22:10.000000Z
字数 12753
阅读 1324
数据结构
SHU
作者 0 ShaoBaoBaoEr
个人网站 shaobaobaoer.cn
QQ 2454225341
参考书目:
# 数据结构高分笔记
# 数据结构————C++s实现
⌈ ⌉ 上取整
⌊ ⌋ 下取整
关于树,森林,二叉树的一些结论
把研讨的表格贴上来了。
图的存储结构
pass
DFS与BFS
普利姆算法
关键思想:
从图中任意取出一个顶点,把它当成一棵树。从这棵树
相接的边中选取一个权值最小的边,把这个边与连着的点加入树中。
算法分析:
克鲁斯卡尔算法
关键思想:
每次找出侯选边中权值最小的边,将该边并入树中。重复直到所有边检测完。
算法分析:
克鲁斯卡尔和普利姆都适用于无向图
迪杰斯特拉算法
关键思想:
设有有两个顶点集合S&T,S存放图中已经找到的最短路径的顶点
这看上去有点难。
实现步骤:
GET j
for i in range(len(dist)):
if dist[i] > dist[j] + g[j][i]:
path[i] = j
dist[i] = dist[i] + g[i][j]
核心代码就是如此,这边附上完整的py代码。
NaN = 0xFFFF
def Dist(G):
'''
:param G: 邻接矩阵
:return:dist & path
'''
dist = []
path = []
set = []
for i in range(len(G)):
path.append(-1)
set.append(0)
dist.append(NaN)
set[0] = 1
for i in range(len(G)):
if G[0][i] == NaN:
pass
else:
path[i] = 0
dist[i] = G[0][i]
i = 0
while (i < len(G)):
min = NaN
for j in range(0, len(G)):
if set[j] == 0 and dist[j] < min:
u = j
min = dist[j]
set[u] = 1
for j in range(0, len(G)):
if dist[j] > dist[u] + G[u][j] and set[j] == 0:
path[j] = u
dist[j] = dist[u] + G[u][j]
i += 1
return dist,path
if __name__ == '__main__':
Graph = [
# 0 1 2 3 4 5 6
[NaN, 4, 6, 6, NaN, NaN, NaN],
[NaN, NaN, 1, NaN, 7, NaN, NaN],
[NaN, NaN, NaN, NaN, 6, 4, NaN],
[NaN, NaN, 2, NaN, NaN, 5, NaN],
[NaN, NaN, NaN, NaN, NaN,NaN, 6],
[NaN, NaN, NaN, NaN, 1, NaN, 8],
[NaN, NaN, NaN, NaN, NaN, NaN, NaN]
]
print(Graph[0][0] == NaN)
Dist(Graph)
返回的数组为
dist = [0, 4, 5, 6, 10, 9, 16]
# dist 放得是0的点到其余顶点最短路径的长度
path = [-1, 0, 1, 0, 5, 2, 4]
# path 放得是0的点到其余各顶点的最短路径
# 比如 6 。其路径为 4 , 4需要通过 5到达,5需要通过2到达,2需要通过1到达,1需要通过0到达
# 综上就是 0 -> 1 -> 2 -> 5 -> 4 -> 6
附上该题目的图片:
性能分析:
弗洛伊德算法
如果求途中任意一对顶点间的最短路径,那就要用弗洛伊德算法
弗洛伊算法很麻烦,但是程序却很简单。主要思想就是
监测 k = ,如果 A[i][j] > A[i][] + A[][j] 则将A[][j] 改为这个值,并将PATH[i][j] 置为
实现步骤
程序代码
这个我们还做了研讨来着。弗洛伊德算法的python程序如下:
class MGragph:
def __init__(self, edges):
self.edge = edges
self.n = len(edges)
self.e = 0
def __str__(self):
return str(self.edge)
def fuluoyide(self):
Path = full((self.n, self.n), -1)
# print(Path)
A = self.edge
print("A = \n", mat(A))
print("PATH = \n", Path)
for k in range(0, self.n):
print("##################")
print("目前监测 k = %s,如果 A[i][j] > A[i][%s] + A[%s][j] 则将A[i][j] 改为这个值,并将PATH[i][j] 置为 %s" % (k, k, k, k))
for i in range(0, self.n):
for j in range(0, self.n):
if A[i][j] > A[i][k] + A[k][j]:
A[i][j] = A[i][k] + A[k][j]
Path[i][j] = k
print("A = \n", mat(A))
print("PATH = \n", Path)
return A, Path
state2 = [[0, 5, inf, 7],
[inf, 0, 4, 2],
[3, 3, 0, 2],
[inf, inf, 1, 0]]
G = MGragph(state2)
A, Path = G.fuluoyide()
最后返回的数组是
A =
[[0 5 8 7]
[6 0 3 2]
[3 3 0 2]
[4 4 1 0]]
PATH =
[[-1 -1 3 -1]
[ 3 -1 3 -1]
[-1 -1 -1 -1]
[ 2 2 -1 -1]]
# 矩阵A 代表 任意两点的最短路径长度
# 矩阵PATH 代表 任意两点之间最短路径
# 比如求 1 到 3 的路径与长度
# 查表 A[1][5] = 2
# 查表path的 PATH[1][6] = -1 表示直接相连
# 比如求 1 到 0 的路径与长度
# 查表 A[1][0] = 6
# 查表path的 PATH[1][0] = 3 则3作为下一步起点
# PATH[3][0] = 2 则2作为下一步的起点
# PATH[2][0] = -1 查找结束 最终路径为 1 -> 3 -> 2 -> 0
附上该题目的图片
性能分析
贝尔曼福特算法
http://www.cnblogs.com/gaochundong/p/bellman_ford_algorithm.html
http://www.wutianqi.com/?p=1912
算法思想:
Bellman-Ford算法能在更普遍的情况下(存在负权边)解决单源点最短路径问题。对于给定的带权(有向或无向)图 G=(V,E),其源点为s,加权函数 w是 边集 E 的映射。对图G运行Bellman-Ford算法的结果是一个布尔值,表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路,算法将给出从源点s到 图G的任意顶点v的最短路径d[v]。
算法流程:
1. 初始化:将除源点外的所有顶点的最短距离估计值 d[v] ←+∞, d[s] ←0;
2. 迭代求解:反复对边集E中的每条边进行松弛操作,使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离;(运行|v|-1次)
3. 检验负权回路:判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点,则算法返回false,表明问题无解;否则算法返回true,并且从源点可达的顶点v的最短距离保存在 d[v]中。
核心算法就是
算法实现
G = {1: {1: 0, 2: -3, 5: 5},
2: {2: 0, 3: 2},
3: {3: 0, 4: 3},
4: {4: 0, 5: 2},
5: {5: 0}}
def getEdges(G):
""" 输入图G,返回其边与端点的列表 """
v1 = [] # 出发点
v2 = [] # 对应的相邻到达点
w = [] # 顶点v1到顶点v2的边的权值
for i in G:
for j in G[i]:
if G[i][j] != 0:
w.append(G[i][j])
v1.append(i)
v2.append(j)
return v1, v2, w
class CycleError(Exception):
pass
def Bellman_Ford(G, v0, INF=999):
v1, v2, w = getEdges(G)
# 初始化源点与所有点之间的最短距离
dis = dict((k, INF) for k in G.keys())
dis[v0] = 0
# 核心算法
for k in range(len(G) - 1): # 循环 n-1轮
check = 0 # 用于标记本轮松弛中dis是否发生更新
for i in range(len(w)): # 对每条边进行一次松弛操作
if dis[v1[i]] + w[i] < dis[v2[i]]:
dis[v2[i]] = dis[v1[i]] + w[i]
check = 1
if check == 0: break
# 检测负权回路
# 如果在 n-1 次松弛之后,最短路径依然发生变化,则该图必然存在负权回路
flag = 0
for i in range(len(w)): # 对每条边再尝试进行一次松弛操作
if dis[v1[i]] + w[i] < dis[v2[i]]:
flag = 1
break
if flag == 1:
# raise CycleError()
return False
return dis
v0 = 1
dis = Bellman_Ford(G, v0)
print(dis.values())
拓扑排序与AOV
算法思想:
AOV网是一种以顶点表示活动,以边表示先后次序且没有回路的有向图。
算法流程:
算法分析:
关键路径与AOE
与AOV的对比
对于一个工程的AOE网,只存在一个入度为0的点,成为源点。也只存在一个出度为0的点,表示汇点
DFS好像有点糊涂,到时候问问室友
到时候需要做的事情
直接插入排序
每一趟将待排序的关键字插入已经排好的部分序列上的合适位置上
折半插入排序
和直接插排相比,插入的时候按照折半查找的方法进行。(mid为low+high除以2向下取整),要修改high则为high=m-1,要修改low则为low=m+1
希尔排序
将待排序序列切成若干个子序列,并设定增量。比如说d = 5,则将下标为的分为一组,的分为一组,如此类推。然后对各个子序列进行排序。然后再缩小增量进行排序,以此类推。
冒泡儿排序
快速排序
以前写过一个,不过方法和书上不太一样。我还是按照课本上说的来,具体如何实现的,这边不赘述了。
https://www.zybuluo.com/shaobaobaoer/note/1151376
简单选择排序
将序列切割成有序和无序两个部分,从无序的部分中选择出一个最小的(最大的)
堆排序
参考 https://www.cnblogs.com/chengxiao/p/6129630.html
堆排序的基本思想是:将待排序序列构造成一个大顶堆,此时,整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换,此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行,便能得到一个有序序列了
堆
堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。
堆的定义
【升序大顶堆,降序小顶堆】
堆还是上个学习学的东西,总之,调整是从第一个非叶子节点开始,从左到右,从下到上调整。第一趟调整完后,将第一个元素和最后一个元素互换,并将最后一个元素弹出并压栈,第一趟堆排完成。
之后将剩余元素继续重复上述步骤,直到就剩下一个元素的时候,排序结束。最后把栈中元素弹出。得到升序序列。
总结来说,就是这样的:
a.将无需序列构建成一个堆,根据升序降序需求选择大顶堆或小顶堆;
b.将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端;
c.重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复执行调整+交换步骤,直到整个序列有序。
二路归并排序
基数排序
这个玩意儿比较魔幻,稍微多写点。
基数排序的思想是多关键字排序,又称为桶排序,通过使用对多关键字进行排序的分配与收集。将无序序列排列成有序序列。
e.g
初始序列:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
278 | 109 | 063 | 930 | 589 | 184 | 505 | 269 | 008 | 083 |
对于数字而言,需要十个桶,代表关键字0-9,第一趟排序,将序列按照最低位入桶。
注意
数字要有序放入,放入方式就像是入栈一样,这也是为啥109在最下面,269在最上面
出桶的顺序和出栈顺序相反,按照桶的次序从桶下方依次取出。桶是一个队列
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
930 | 083 063 |
184 | 505 | 008 278 |
269 589 109 |
得到序列如下:
930 063 083 184 505 278 008 109 589 269
然后对上述序列按照中间位入桶,得到的序列如下:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
109 008 505 |
930 | 269 063 |
278 | 589 184 083 |
出桶得序列如下:
505 008 109 930 063 269 278 083 184 589
最后对上述序列按照最高位入桶,得到的序列如下:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
083 063 008 |
184 109 |
278 269 |
589 505 |
930 |
出桶得序列如下:排序完成
008 083 063 109 184 269 278 505 589 930
--*--
关于时间与空间复杂度的问题
先附上PPT
相当重要[1]
<快排>
些<希尔>
以的速度归<归并>
队<堆排>
<快排>
些<希尔>
选<选择>
一堆<堆排>
好友聊天To be continue
顺序查找 && 折半查找
折半查找树
二叉排序树
平衡二叉树
B+树似乎不考
B-树
具体看书吧,我这边写的不是很全,动手画一画,把删除,插入,建立的操作都画一遍,会有新的感悟!
B+树
B+ 树n个关键字有n个分支,比B-T少一个
哈希表查找不成功和成功的ASL 如何计算?
https://blog.csdn.net/u013806583/article/details/52643541
概念
根据给定关键字来计算出关键字的地址。(python的字典2333)
装填因子与确定表长
常见的Hash函数构造方法
常见冲突的解决方法
并查集
上学期的一些比较有用的结论
含有n个节点的二叉树的高度范围在 之间
在插入排序的时候,元素是从后往前比较,而不是从前往后比较
https://www.nowcoder.com/questionTerminal/22576bafa4d64135a5ace210bfad2c92
(12-13.三.10) 对一组记录(54,38,106,21,15,72,60,45,83)进行直接插入排序时,当把第7个记录60插入到有序表时,为寻找插入位置需比较(3)次
在插入第7个数,说明前面的数字已经有序了。
即数字为[15--- 21---38---54----72---106--]--60---45---83
现在对第7个数字60进行插入,需要向前找到插入点。依次比较,96,72,54.最后插入在54后面。
所以比较3次。
(12-13.一.1) 不是每一棵二叉树都可以转化成树表示
(12-13.一.4) B-树删除某一关键字值时候,不会引起节点的分裂
(12-13.二.1) 分块查找,既能较快查找,又能适应动态变化
(15-16.一.9) 了解一下临接多重表的画法等,之前没有复习到
(15-16.一.2) 带权连通图G,权值最小的边一定包含在最小生成树中
(15-16.一.4)
(15-16.三.2) 希尔排序的时间复杂度与增量的选取有关。希尔提出的增量复杂度为,增量选取公式为 后俩又有两个大大提出了一种的增量序列,其十几件时间复杂度为。希尔排序的时间复杂度算起来很麻烦,不要求掌握,知道即可。
(15-16.三.5) 无论是DFS还是BFS,都不能完全遍历无向图中的所有顶点。很简单,如果这个无向图的连通分量大于等于2的话,就只能遍历一部分了。
(15-16.四) 已知Hash = key mod 9 ;二次探测(平方)探测。求 成功和失败的ASL
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|
2 | 1 | 2 | 1 | 3 | 4 | 10 | 4 | 2 |
5 mod 10 = 5 ;a[5]!=NULL;value=1;
5 + 1^2 = 6 ;a[6]!=NULL;value=2;
5 - 1^2 = 4 ;a[4]!=NULL;value=3;
(5 + 4) mod 10 = 9;a[9]==NULL;
OUTPUT value=4;
我一个搞信安的。做算法填空设计啥的真是头大。这里给菜鸡的自己记录一些小技巧。ACM大佬们不要喷我。以下模板基本上都是我YY出来的,有啥错的还请指正。
邻接矩阵,邻接表,邻接多重表
> 自己看书
这边说一个很恐怖的事情,根据SJ的模板,他对这三个词语的英文称呼如下;严版的英文称呼在后头
邻接矩阵封装的方法
我乖乖看sj的书还不行么...
vertexes | tag | arcs | vexNum | vexMaxNum | arcNum |
---|---|---|---|---|---|
图中顶点信息<Array[]> | 访问情况<Array[]> | 二维矩阵 <Array[ ][ ]> |
//
邻接表封装的方法
我乖乖看sj的书还不行么...
data | firstarc |
---|---|
顶点的值 | 指向边节点 |
adjvex | (weight) | nextarc |
---|---|---|
顶点 | 权 | 指向下一个边节点 |
二叉树先序遍历模板
为啥写这个呢?因为把二叉树的遍历延伸出去,就是DFS(先序),也可以是二叉排序树的遍历
void preorder(btnode *p){
if(p!=NULL){
visit(p);
preorder(p->left);
preorder(p->right);
}
}
DFS
\\ 强行按照sj的封装函数魔改了一波
void DFS(AGraph &g, int v){
visit(v);
g.SetTag(v, VISITED);
for (int w = g.FirstAdjVex(v); w != -1; w = g.NextAdjVex(v, w))
if (g.GetTag(w) == UNVISITED) DFS(g, w);
}
扩展DFS检测环
能够检测出一个有向图是否存在环,除却利用拓扑排序(最后删得剩下两个入度为0的顶点且无关联)外,还可以用魔改的DFS算法,在该DFS中,需要对回边进行检测,如果回边为VISITED,那么就检测到环。
\\ 我按照自己的想法写的,如果有问题还请大神指正。
bool Cycle_DFS(AGraph &g, int v,int pre){
// visit(v);
// if
g.SetTag(v, VISITED);
for (int w = g.FirstAdjVex(v); w != -1; w = g.NextAdjVex(v, w))
if (g.GetTag(w) == UNVISITED) Cycle_DFS(g, w);
}
二叉树层序遍历模板
为啥要写这个呢? BFS的思路就是层序遍历。延伸出去,也可能是B-树或者B+树的遍历。
void layorder(btnode *p){
if (p==NULL) return ;
Queue<Type> Q;
btnode *m;
Q.enqueue(p);
while(!Q.empty()){
m=Q.dequeue();
visit(m);
if(m->left!=NULL)
Q.enqueue(m->left);
if(m->right!=NULL)
Q.enqueue(m->right);
}
}
BFS
\\ 强行按照sj的封装函数魔改了一波;行...一切按大哥的来
void BFS(AGraph &g, int v){
Queue<Type> Q;
int m;
g.SetTag(v, VISITED);
visit(v->data);
Q.enqueue(v);
While(!Q.empty()){
m = Q.dequeue();
for (w = g.FirstAdjVex(m); w != -1; w = g.NextAdjVex(m, w)){
g.SetTag(w, VISITED);
g.GetElem(w, e);
Visit(e);
Q.EnQueue(w);
}
}
}