[关闭]
@shaobaobaoer 2019-03-17T07:22:10.000000Z 字数 12753 阅读 1324

数据结构复习笔记(二)

数据结构 SHU


作者 0          ShaoBaoBaoEr
个人网站    shaobaobaoer.cn
QQ            2454225341

  1. 参考书目:
  2. # 数据结构高分笔记
  3. # 数据结构————C++s实现
  4. 上取整
  5. 下取整

0x02 森林与并查集

关于树,森林,二叉树的一些结论

把研讨的表格贴上来了。

QQ截图20180530203926.png-102.5kB
QQ截图20180530203915.png-114.8kB
QQ截图20180530203857.png-15.3kB

0x01 图论

1. 概念梳理

图的存储结构
pass

DFS与BFS

普利姆算法
关键思想:
从图中任意取出一个顶点,把它当成一棵树。从这棵相接的边中选取一个权值最小的边,把这个边与连着的点加入树中。

算法分析:

克鲁斯卡尔算法
关键思想:
每次找出侯选边中权值最小的边,将该边并入树中。重复直到所有边检测完。

算法分析:

克鲁斯卡尔和普利姆都适用于无向图

迪杰斯特拉算法
关键思想:
设有有两个顶点集合S&T,S存放图中已经找到的最短路径的顶点

这看上去有点难。
实现步骤:

  1. GET j
  2. for i in range(len(dist)):
  3. if dist[i] > dist[j] + g[j][i]:
  4. path[i] = j
  5. dist[i] = dist[i] + g[i][j]

核心代码就是如此,这边附上完整的py代码。

  1. NaN = 0xFFFF
  2. def Dist(G):
  3. '''
  4. :param G: 邻接矩阵
  5. :return:dist & path
  6. '''
  7. dist = []
  8. path = []
  9. set = []
  10. for i in range(len(G)):
  11. path.append(-1)
  12. set.append(0)
  13. dist.append(NaN)
  14. set[0] = 1
  15. for i in range(len(G)):
  16. if G[0][i] == NaN:
  17. pass
  18. else:
  19. path[i] = 0
  20. dist[i] = G[0][i]
  21. i = 0
  22. while (i < len(G)):
  23. min = NaN
  24. for j in range(0, len(G)):
  25. if set[j] == 0 and dist[j] < min:
  26. u = j
  27. min = dist[j]
  28. set[u] = 1
  29. for j in range(0, len(G)):
  30. if dist[j] > dist[u] + G[u][j] and set[j] == 0:
  31. path[j] = u
  32. dist[j] = dist[u] + G[u][j]
  33. i += 1
  34. return dist,path
  35. if __name__ == '__main__':
  36. Graph = [
  37. # 0 1 2 3 4 5 6
  38. [NaN, 4, 6, 6, NaN, NaN, NaN],
  39. [NaN, NaN, 1, NaN, 7, NaN, NaN],
  40. [NaN, NaN, NaN, NaN, 6, 4, NaN],
  41. [NaN, NaN, 2, NaN, NaN, 5, NaN],
  42. [NaN, NaN, NaN, NaN, NaN,NaN, 6],
  43. [NaN, NaN, NaN, NaN, 1, NaN, 8],
  44. [NaN, NaN, NaN, NaN, NaN, NaN, NaN]
  45. ]
  46. print(Graph[0][0] == NaN)
  47. Dist(Graph)

返回的数组为

  1. dist = [0, 4, 5, 6, 10, 9, 16]
  2. # dist 放得是0的点到其余顶点最短路径的长度
  3. path = [-1, 0, 1, 0, 5, 2, 4]
  4. # path 放得是0的点到其余各顶点的最短路径
  5. # 比如 6 。其路径为 4 , 4需要通过 5到达,5需要通过2到达,2需要通过1到达,1需要通过0到达
  6. # 综上就是 0 -> 1 -> 2 -> 5 -> 4 -> 6

附上该题目的图片:

QQ截图20180523220600.png-102.4kB

性能分析:

弗洛伊德算法

如果求途中任意一对顶点间的最短路径,那就要用弗洛伊德算法

弗洛伊算法很麻烦,但是程序却很简单。主要思想就是
监测 k = ,如果 A[i][j] > A[i][] + A[][j] 则将A[][j] 改为这个值,并将PATH[i][j] 置为

实现步骤

程序代码
这个我们还做了研讨来着。弗洛伊德算法的python程序如下:

  1. class MGragph:
  2. def __init__(self, edges):
  3. self.edge = edges
  4. self.n = len(edges)
  5. self.e = 0
  6. def __str__(self):
  7. return str(self.edge)
  8. def fuluoyide(self):
  9. Path = full((self.n, self.n), -1)
  10. # print(Path)
  11. A = self.edge
  12. print("A = \n", mat(A))
  13. print("PATH = \n", Path)
  14. for k in range(0, self.n):
  15. print("##################")
  16. print("目前监测 k = %s,如果 A[i][j] > A[i][%s] + A[%s][j] 则将A[i][j] 改为这个值,并将PATH[i][j] 置为 %s" % (k, k, k, k))
  17. for i in range(0, self.n):
  18. for j in range(0, self.n):
  19. if A[i][j] > A[i][k] + A[k][j]:
  20. A[i][j] = A[i][k] + A[k][j]
  21. Path[i][j] = k
  22. print("A = \n", mat(A))
  23. print("PATH = \n", Path)
  24. return A, Path
  25. state2 = [[0, 5, inf, 7],
  26. [inf, 0, 4, 2],
  27. [3, 3, 0, 2],
  28. [inf, inf, 1, 0]]
  29. G = MGragph(state2)
  30. A, Path = G.fuluoyide()

最后返回的数组是

  1. A =
  2. [[0 5 8 7]
  3. [6 0 3 2]
  4. [3 3 0 2]
  5. [4 4 1 0]]
  6. PATH =
  7. [[-1 -1 3 -1]
  8. [ 3 -1 3 -1]
  9. [-1 -1 -1 -1]
  10. [ 2 2 -1 -1]]
  11. # 矩阵A 代表 任意两点的最短路径长度
  12. # 矩阵PATH 代表 任意两点之间最短路径
  13. # 比如求 1 到 3 的路径与长度
  14. # 查表 A[1][5] = 2
  15. # 查表path的 PATH[1][6] = -1 表示直接相连
  16. # 比如求 1 到 0 的路径与长度
  17. # 查表 A[1][0] = 6
  18. # 查表path的 PATH[1][0] = 3 则3作为下一步起点
  19. # PATH[3][0] = 2 则2作为下一步的起点
  20. # PATH[2][0] = -1 查找结束 最终路径为 1 -> 3 -> 2 -> 0

附上该题目的图片
QQ截图20180523220802.png-306kB

性能分析

贝尔曼福特算法

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]中。

核心算法就是

算法实现

  1. G = {1: {1: 0, 2: -3, 5: 5},
  2. 2: {2: 0, 3: 2},
  3. 3: {3: 0, 4: 3},
  4. 4: {4: 0, 5: 2},
  5. 5: {5: 0}}
  6. def getEdges(G):
  7. """ 输入图G,返回其边与端点的列表 """
  8. v1 = [] # 出发点
  9. v2 = [] # 对应的相邻到达点
  10. w = [] # 顶点v1到顶点v2的边的权值
  11. for i in G:
  12. for j in G[i]:
  13. if G[i][j] != 0:
  14. w.append(G[i][j])
  15. v1.append(i)
  16. v2.append(j)
  17. return v1, v2, w
  18. class CycleError(Exception):
  19. pass
  20. def Bellman_Ford(G, v0, INF=999):
  21. v1, v2, w = getEdges(G)
  22. # 初始化源点与所有点之间的最短距离
  23. dis = dict((k, INF) for k in G.keys())
  24. dis[v0] = 0
  25. # 核心算法
  26. for k in range(len(G) - 1): # 循环 n-1轮
  27. check = 0 # 用于标记本轮松弛中dis是否发生更新
  28. for i in range(len(w)): # 对每条边进行一次松弛操作
  29. if dis[v1[i]] + w[i] < dis[v2[i]]:
  30. dis[v2[i]] = dis[v1[i]] + w[i]
  31. check = 1
  32. if check == 0: break
  33. # 检测负权回路
  34. # 如果在 n-1 次松弛之后,最短路径依然发生变化,则该图必然存在负权回路
  35. flag = 0
  36. for i in range(len(w)): # 对每条边再尝试进行一次松弛操作
  37. if dis[v1[i]] + w[i] < dis[v2[i]]:
  38. flag = 1
  39. break
  40. if flag == 1:
  41. # raise CycleError()
  42. return False
  43. return dis
  44. v0 = 1
  45. dis = Bellman_Ford(G, v0)
  46. print(dis.values())

拓扑排序与AOV
算法思想:
AOV网是一种以顶点表示活动,以边表示先后次序且没有回路的有向图。

算法流程:

算法分析:

  1. 拓扑排序结果可能不止一个
  2. 当有向图无环的时候,还可以用DFS进出栈的过程模拟拓扑排序。 这个很有意思
  3. 时间复杂度

关键路径与AOE
与AOV的对比

对于一个工程的AOE网,只存在一个入度为0的点,成为源点。也只存在一个出度为0的点,表示汇点

2. 错题摘录

DFS好像有点糊涂,到时候问问室友

  1. 图中有关路径的定义: 由相邻顶点序偶所形成的序列。
  2. DFS和BFS对于所有图都使用
  3. 当各边的权值均相等的时候,可以用BFS算法来解决最短路径问题(可以自己想一下为啥)
  4. 有向图G拓扑序列。如果顶点之前,那么G中不可能有一条从的回路。
  5. 如果一个图从任意一个顶点出发,用DFS可以遍历所有节点,那么这个图一定是连通图。
  6. 尽管对于一个图而言,可能DFS的访问序列有多个,但是如果是用邻接表表示这个图的话,DFS的遍历序列只可能有一个。(邻接表访问是有顺序的)
  7. 利用DFS或者拓扑排序可以判断出一个有向图是不是有环。
    • 为啥?
    • 对于拓扑排序,如果最后删得剩下的不止一个顶点,那么就有环了。
    • 对于DFS,如果从某个顶点v出发,在dfs(v)结束前出现了一条从j指向v的路径,那么就必然存在环
  8. 若路径中除了开始点和结束点可以相同外,其他的顶点均不相同,则称这条路径为简单路径。很明显的是,回路和简单路径的概念完全不同
  9. 在用邻接矩阵代表无向图的时候,各顶点纵向与横向非零元素和尾顶点的度。不要傻不拉几的画个图
  10. ...

3. 总结

到时候需要做的事情

0x02 查找

1. 概念梳理

直接插入排序

每一趟将待排序的关键字插入已经排好的部分序列上的合适位置上

折半插入排序

和直接插排相比,插入的时候按照折半查找的方法进行。(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个元素的次小值。如此反复执行,便能得到一个有序序列了


  堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。
堆的定义

【升序大顶堆,降序小顶堆】

堆还是上个学习学的东西,总之,调整是从第一个非叶子节点开始,从左到右,从下到上调整。第一趟调整完后,将第一个元素和最后一个元素互换,并将最后一个元素弹出并压栈,第一趟堆排完成。
之后将剩余元素继续重复上述步骤,直到就剩下一个元素的时候,排序结束。最后把栈中元素弹出。得到升序序列。

总结来说,就是这样的:

  1.   a.将无需序列构建成一个堆,根据升序降序需求选择大顶堆或小顶堆;
  2.   b.将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端;
  3.   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

QQ截图20180528095601.png-401kB

相当重要[1]

2. 错题摘录

  1. 选择排序和插入排序的区别。
    • 插入排序和选择排序都有两层循环,外循环遍历整个数组,内循环稍有区别:
    • 选择排序 的内循环是遍历一组未排过序的数组,
    • 插入排序 的内循环是遍历一组已排过序的数组,
  2. 希尔排序与归并排序的区别:
    • 主要体现在切割方法上
      • 希尔排序 是按照增量来切割序列,然后会这些子序列进行排序,然后再把排序号的子序列合并成朱序列。接着,按照来切割序列,对这些子序列排序
      • 二路归并排序 是按照2,4,6,...,n的顺序把主序列分成若干组,然后对这些组排序。
  3. 冒泡儿和直接选择排序,在序列完全有序的时候时间复杂度为 但是,当序列完全有序的时候,快排的空间复杂度最高,为
  4. 希尔排序不能保证每趟排序至少能够将一个关键字放到其最终位置上。
  5. 在堆排序插入的时候,当问及关键字的比价次数,那么只要数被影响的部分的比较次数就行。
    • e.g. 已知大顶堆 25,13,19,12,9 插入18,再次调整为大顶堆,调整过程中关键字之间的比较次数为 2 次。
  6. 快排的递归次数与每次划分后得到的分区的处理顺序无关,这意味着快排的最下面两个递归的位置可以互换,不会影响结果。

3. 总结

To be continue

0x03 排序

1. 概念梳理

概念,顺序与折半

顺序查找 && 折半查找

折半查找树

二叉排序树与平衡二叉树

二叉排序树

平衡二叉树

B+ 与 B- 树

B+树似乎不考

B-树

具体看书吧,我这边写的不是很全,动手画一画,把删除,插入,建立的操作都画一遍,会有新的感悟!

B+树

B+ 树n个关键字有n个分支,比B-T少一个

散列表

哈希表查找不成功和成功的ASL 如何计算?
https://blog.csdn.net/u013806583/article/details/52643541

概念
根据给定关键字来计算出关键字的地址。(python的字典2333)

装填因子与确定表长

常见的Hash函数构造方法

常见冲突的解决方法

2. 错题摘录

  1. Hash函数有一个共同的性质:函数值应当以同等概率取其值域的每一个值
  2. 平衡二叉树的最少节点类似菲波那切数列,也就是:

    • 这就意味着,在平衡二叉树,如果给定了节点数,那就可以确定平衡二叉树的高度
  3. 哈希查找的时间复杂度为 因为这个是散列表

0x04 考卷陌生题解析

并查集

上学期的一些比较有用的结论

含有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) QQ截图20180530193659.png-77.3kB

QQ截图20180530195830.png-48.3kB

(15-16.三.2) 希尔排序的时间复杂度与增量的选取有关。希尔提出的增量复杂度为,增量选取公式为 后俩又有两个大大提出了一种的增量序列,其十几件时间复杂度为。希尔排序的时间复杂度算起来很麻烦,不要求掌握,知道即可。
(15-16.三.5) 无论是DFS还是BFS,都不能完全遍历无向图中的所有顶点。很简单,如果这个无向图的连通分量大于等于2的话,就只能遍历一部分了。

(15-16.四) 已知Hash = key mod 9 ;二次探测(平方)探测。求 成功和失败的ASL
QQ截图20180602212233.png-4.4kB

0 1 2 3 4 5 6 7 8
2 1 2 1 3 4 10 4 2
  1. 5 mod 10 = 5 ;a[5]!=NULL;value=1;
  2. 5 + 1^2 = 6 ;a[6]!=NULL;value=2;
  3. 5 - 1^2 = 4 ;a[4]!=NULL;value=3;
  4. (5 + 4) mod 10 = 9;a[9]==NULL;
  5. OUTPUT value=4;

0x05 算法设计题

我一个搞信安的。做算法填空设计啥的真是头大。这里给菜鸡的自己记录一些小技巧。ACM大佬们不要喷我。以下模板基本上都是我YY出来的,有啥错的还请指正。

邻接矩阵,邻接表,邻接多重表
> 自己看书

这边说一个很恐怖的事情,根据SJ的模板,他对这三个词语的英文称呼如下;严版的英文称呼在后头

邻接矩阵封装的方法

我乖乖看sj的书还不行么...

vertexes tag arcs vexNum vexMaxNum arcNum
图中顶点信息<Array[]> 访问情况<Array[]> 二维矩阵 <Array[ ][ ]>
  1. //

邻接表封装的方法

我乖乖看sj的书还不行么...

data firstarc
顶点的值 指向边节点
adjvex (weight) nextarc
顶点 指向下一个边节点

二叉树先序遍历模板

为啥写这个呢?因为把二叉树的遍历延伸出去,就是DFS(先序),也可以是二叉排序树的遍历

  1. void preorder(btnode *p){
  2. if(p!=NULL){
  3. visit(p);
  4. preorder(p->left);
  5. preorder(p->right);
  6. }
  7. }

DFS

  1. \\ 强行按照sj的封装函数魔改了一波
  2. void DFS(AGraph &g, int v){
  3. visit(v);
  4. g.SetTag(v, VISITED);
  5. for (int w = g.FirstAdjVex(v); w != -1; w = g.NextAdjVex(v, w))
  6. if (g.GetTag(w) == UNVISITED) DFS(g, w);
  7. }

扩展DFS检测环

能够检测出一个有向图是否存在环,除却利用拓扑排序(最后删得剩下两个入度为0的顶点且无关联)外,还可以用魔改的DFS算法,在该DFS中,需要对回边进行检测,如果回边为VISITED,那么就检测到环。

  1. \\ 我按照自己的想法写的,如果有问题还请大神指正。
  2. bool Cycle_DFS(AGraph &g, int v,int pre){
  3. // visit(v);
  4. // if
  5. g.SetTag(v, VISITED);
  6. for (int w = g.FirstAdjVex(v); w != -1; w = g.NextAdjVex(v, w))
  7. if (g.GetTag(w) == UNVISITED) Cycle_DFS(g, w);
  8. }

二叉树层序遍历模板

为啥要写这个呢? BFS的思路就是层序遍历。延伸出去,也可能是B-树或者B+树的遍历。

  1. void layorder(btnode *p){
  2. if (p==NULL) return ;
  3. Queue<Type> Q;
  4. btnode *m;
  5. Q.enqueue(p);
  6. while(!Q.empty()){
  7. m=Q.dequeue();
  8. visit(m);
  9. if(m->left!=NULL)
  10. Q.enqueue(m->left);
  11. if(m->right!=NULL)
  12. Q.enqueue(m->right);
  13. }
  14. }

BFS

  1. \\ 强行按照sj的封装函数魔改了一波;行...一切按大哥的来
  2. void BFS(AGraph &g, int v){
  3. Queue<Type> Q;
  4. int m;
  5. g.SetTag(v, VISITED);
  6. visit(v->data);
  7. Q.enqueue(v);
  8. While(!Q.empty()){
  9. m = Q.dequeue();
  10. for (w = g.FirstAdjVex(m); w != -1; w = g.NextAdjVex(m, w)){
  11. g.SetTag(w, VISITED);
  12. g.GetElem(w, e);
  13. Visit(e);
  14. Q.EnQueue(w);
  15. }
  16. }
  17. }



[1] 快速返回排序时间,空间复杂度与稳定度结论
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注