图解算法使用python笔记

admin 2022年1月6日01:33:43安全博客评论9 views46478字阅读154分55秒阅读模式

比较简略的算法书,适合初学者入门。 以下是做的一些简记。

0x1算法

0x1.1算法的定义
为了解决某项工作或某个问题,所需要有限数量的机械性或重复性指令与计算步骤。
这个算法应用相当广泛,如快排序法、递归算法、大整数乘法。

1
2
3
4
5
6
7
num1=int(input('输入第一个数:'))
num2=int(input('输入第二个数:'))
while num2!=0:
temp=num1%num2
num1=num2
num2=temp
print('最大公约数:',num1)

0x1.2算法条件
输入、输出、明确性、有限性、有效性
0x1.3时间复杂度O(f(n))

1
0(1)<0(log2n)<0(n)<O(nlog2n)<O(n2)<O(2n)

0x2常见算法

0x2.1分治法
核心思想就是将一个难以直接解决的大问题依照相同的概念,分割长两个或更多子问题,以便各个击破,即“分而治之”。
0x2.2递归法
定义: 一个函数或子程序,是由自身所定义或调用的,就成为递归。
至少满足的两个条件:
一个可以反复执行的递归过程
一个可以离开递归执行过程的出口
范例:
阶乘函数

1
2
3
4
5
6
def factorial(i):
if i==0:
return 1
else:
ans=i*factorial(i-1)
return ans

斐波那契数列

1
2
3
4
5
6
7
def fib(n):
if n==0:
return 0
elif n==1 or n==2:
return 1
else:
return (fib(n-1)+fib(n-2))

0x2.3 贪心算法
方法是从某一七点开始,在每一个解决问题步骤中使用贪心原则,即采用在当前状态下最有利或最优化选择,不断地改进该解答,持续在每一步骤中选择最佳的方法,并且逐步逼近给定的目标,当达到某一步骤不能再继续前进时,算法就停止,就是尽可能快地求得更好的解。
经常用于找出图的最小生成树,最短路径与哈弗曼编码等。
0x2.4动态规划法
主要做法:如果一个问题答案与子问题相关的话,就能将大问题拆解成各个小问题,其中与分治法最大不同的地方是可以让每一个子问题的答案被存储起来,以供下次求解时直接取用。这样的做法不但能减少再次计算的时间,并将这些解组合成大问题的解答,故而使用动态规划可以解决重复计算问题。
范例:
斐波那契数列

1
2
3
4
5
6
7
8
9
10
11
12
output=[None]*1000
def Fibonacci(n):
result=output[n]
if result==None:
if n==0:
result=0
elif n==1:
result=1
else:
result=Fibonacci(n-1) + Fibonacci(n-2)
output[n]=result
return result

0x2.5迭代法
是指无法使用公式一次求解,而需要使用迭代,例如用循环去重复执行程序代码的某些部分来得到答案。
范例:
使用for循环来设计一个计算1!~n!阶乘的递归程序

1
2
3
4
5
6
7
sum=1
n=int(input('请输入n='))
for i in range(0,n+1):
for j in range(i,0,-1):
sum *=j
print('%d!=%3d'%(i,sum))
sum=1

0x2.6枚举法
又称穷举法,核心思想就是列举所有的可能。
范例:
当某数1000依次减去1,2,3……直到哪一个数,相减得结果开始为负数。

1
2
3
4
5
6
x=1
num=1000
while num>=0:
num=num-x
x=x+1
print(x-1)

0x2.7回溯法
也算是枚举中的一种。
特点主要是在搜索过程中寻找问题的解,当发现不满足求解条件时,就回溯,尝试别的路径,避免无效搜索。
常见的迷宫问题

0x3数据结构类型

0x3.1数组
数组结构其实就是一排紧密相邻的可数内存,并提供一个能够直接访问单一数据内容的计算方法。

0x3.2链表
是由许多相同数据项按特定顺序排列而成的线性表。

0x3.3 堆栈
是一组相同数据类型的组合,具有后进先出的特性,所有操作均在堆栈结构的顶端进行。

0x3.4队列
是一种先进先出的数据结构,和堆栈一样都是一种有序线性表的抽象数据类型。

0x3.5树形结构
基本观念:
树是由一个或一个以上的节点所组成的,存在一个特殊的节点,称为树根,每个节点可代表一些数据和指针组合而成的记录。
一些专有名词:
度数:每个节点所有子树的个数
层数:树的层数
高度: 树的最大层数
树叶或终端节点: 度数为零节点就是树叶
父节点:每个节点有连接的上一层节点
子节点:每个节点有连接的下一层节点
祖先和子孙:所谓祖先,是指从树根到该节点路径上所包含的几点,而子孙则是在该节点往下追溯子树中的任意节点
兄弟节点:有共同父亲节点的节点为兄弟节点
非终端节点:树叶以外的节点
同代: 在同一棵中具有相同层数的节点
森林:n棵(n>=0)互斥树的集合
二叉树:
一般树形结构在计算机内存中的存储方式是以链表为主

0x3.6图形结构
图是由定点和边组成的集合,通常用G=(V,E)来表示,其中V是所有顶点所组成的集合,而E代表所有边所组成的集合。 图的种类有两种;一种是无向图,一种是有向图,无向图以(V1,V2)表示其边,有向图以<V1,V2>表示其边。

0x3.7哈希表
哈希表是一种存储记录的连续内存,通过哈希函数的应用,可以快速存取与查找数据。
相关名词
bucket(桶): 哈希表总存储数据的位置,每一个位置对应到唯一的一个地址,桶就好比一个记录。
solt(槽):每个记录中可能包含好几个字段,而solt就是桶中的字段。
collision(碰撞): 两项不同的数据,经过哈希函数运算后,对应到相同的地址。
溢出:如果数据经过哈希函数运算后,所对应的bucket已满,就会使bucket发生溢出。
哈希表: 存储记录的连续内存。
同义词:两个标识符I1和I2经哈希函数运算后所得的数值相同。
加载密度: 是指标识符的使用数量除以哈希表内槽的总数。
完美哈希: 没有碰撞也没有溢出的哈希函数。

0x4排序算法

在排序过程中,根据数据的移动方式,可将排序方式分为:
直接移动和逻辑移动两种方式。
直接移动:是指直接交换存储数据的位置;缺点是:直接移动会浪费许多时间进行数据的移动。
而逻辑移动并不会移动数据存储的位置,仅仅改变指向这些数据的辅助功能指针的值;优点是:只要改变辅助指针指向的位置就能达到排序的目的。

排序可以按照执行时所使用的内存种类区分为以下两种方式:
1)内部排序:排序数量小,可以全部加载到内存中进行排序。
2)外部排序:数据量大,无法全部一次性加载到内存中进行排序,而必须借助辅助存储器(如硬盘)进行排序。

排序算法的分析
1)算法稳定与否?
稳定的排序是指在经过排序后,两个相同键值的记录仍然保持原来的次序。即同一数字在排序前后的相对位置不会发生改变。

2)时间复杂度?Time Complexity
当数据量较大时,排序算法所花费的时间就显得尤为重要。排序算法的时间复杂度分为:最好情况(Best Case)、平均情况(Average Case)和最差情况(Worst Case).
最好情况就是值原本的数列已经是经过排序之后的结果;最差结果是数列中的每一个值都需要重新排列。
3)空间复杂度?Space Complexity
空间复杂度是指算法在执行过程中所需要占用的额外内存空间。任何排序算法都有数据的对调操作,数据对调就会暂时用到一个额外的空间,这也是排序中空间复杂度要考虑的问题。排序算法占用的额外空间越小,空间复杂度就越低

0x4.1冒泡排序法
原理:是从第一个元素开始比较相邻元素的大小,若大小顺序有误,则对调后再进行下一个元素的比较,就仿佛气泡逐渐从水底逐渐冒升到水面上一样。如此扫面一次之后,就可以确保最后一个元素位于正确的顺序。接着再逐步进行第二次扫描,直到完成所有元素的排序关系为止。
范例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
data=[16,25,39,27,12,8,45,63]
print('冒泡排序法:原始数据为:')
for i in range(len(data)):
print('%3d'%data[i],end='')
print()
for i in range(len(data)-1,0,-1): #扫描次数
for j in range(i):
if data[j]>data[j+1]:
data[j],data[j+1]=data[j+1],data[j]
print('第%d次排序后的结果是:'%(8-i),end='')
for j in range(len(data)):
print('%3d'%data[j],end='')
print()
print('排序后的结果为:')
for j in range(len(data)):
print('%3d'%data[j],end='')
print()

0x4.2选择排序法
也算是枚举法的一种应用,就是反复从未排序的数列中取出最小的元素,加入到另一个数列中,最后的结果即为已排序的数列。
范例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def showdata(data):
for i in range(len(data)):
print('%3d'%data[i],end='')
print()
def select(data):
for i in range(len(data)-1):
for j in range(i+1,8):
if data[i]>data[j]:
data[i],data[j]=data[j],data[i]
print()
data=[16,25,39,27,12,8,45,63]
print('原始数据为:')
showdata(data)
select(data)
print('排序后的数据为:')
showdata(data)

0x4.3插入排序法
是将数组中的元素,逐一与已排序好的数据进行比较,前两个元素先排好,再将第三个元素插入适当的位置,所以这三个元素仍然是已排序好的,接着讲第四个元素加入,重复此步骤,直到排序完成为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def showdata(data):
for i in range(len(data)):
print('%3d'%data[i],end='')
print()
def insert(data):
for i in range(1,len(data)):
tmp=data[i]#tmp用来暂存数据
no=i-1
while no >=0 and tmp <data[no]:
data[no+1]=data[no] #就把所有元素往后推一个元素
no-=1
data[no+1]=tmp #最小的元素放到第一个位置
def main():
data = [16, 25, 39, 27, 12, 8, 45, 63]
print('原始数据为:')
showdata(data)
insert(data)
print('排序后的数据为:')
showdata(data)
main()

0x4.4希尔排序
排序的原则是将数据区分成特定间隔的几个小区块,以插入排序法排完区块内的数据后再渐渐减少间隔的距离。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def showdata(data):
for i in range(len(data)):
print('%3d' % data[i], end='')
print()
def shell(data):
k = 1 # 打印计数
j=0
jmp = len(data) // 2
while jmp >= 1:
for i in range(jmp, len(data)):
tmp = data[i]
j = i - jmp
while j >= 0 and tmp < data[j]:
data[j + jmp] = data[j]
j = j - jmp
data[jmp + j] = tmp
print('第%d次排序过程:' % k, end='')
k += 1
showdata(data)
print('--------------------------------')
jmp = jmp // 2
def main():
data = [16, 25, 39, 27, 12, 8, 45, 63]
print('原始数据为:')
showdata(data)
shell(data)
main()

0x4.5合并排序法
工作原理针对已排序好的两个或两个以上的数列通过合并的方式,将其组合成一个大的且已排序好序的数列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
list3 = []
list1 = [20, 45, 51, 88, 99999]
list2 = [98, 10, 23, 15, 99999]
def select_sort(data): #选择排序法
for i in range(len(data)-1):
small=i
for j in range(i+1,len(data)-1):
if data[j]<data[small]:
small=j
data[small],data[i]=data[i],data[small]
def Merge(list1,list2):
index1=0
index2=0
for index3 in range(len(list1)+len(list2)-1):
if list1[index1]<list2[index2]:
list3.append(list1[index1])
index1 +=1
print('此数字%d来自于第1个数列'%list3[index3])
else:
list3.append(list2[index2])
index2 +=1
print('此数字%d来自于第2个数列'%list3[index3])
print('目前的合并排序结果为:',end='')
for i in range(index3+1):
print(list3[i],' ',end='')
print('\n')
def showdata(data):
for i in range(len(data)):
print('%3d' % data[i], end='')
print()
def main():
select_sort(list1)
showdata(list1)
select_sort(list2)
showdata(list2)
Merge(list1,list2)
if __name__ == '__main__':
main()

0x4.6 快速排序法
又称为分割交换排序法,是目前工人最佳的排序法,也是使用分而治之的方式,先在数据中找到一个虚拟的中间值,并按此中间值将所有打算排序的数据分为两部分。其中,小于中间值的数据值的数据放在左边,大于中间值的数据放在右边,再以同样的方式处理左右两边的数据,直到排序完为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import random

def inputarr(data, size):
for i in range(size):
data[i] = random.randint(1, 100)


def showdata(data, size):
for i in range(size):
print('%3d' % data[i], end='')
print()

def quick(d, size, lf, rg):
# 第一项键值为d[lf]
if lf < rg: # 排序数列的左边与右边
lf_idx = lf + 1
while d[lf_idx] < d[lf]:
if lf_idx + 1 > size:
break
lf_idx += 1
rg_idx = rg
while d[rg_idx] > d[lf]:
rg_idx -= 1
while lf_idx < rg_idx:
d[lf_idx], d[rg_idx] = d[rg_idx], d[lf_idx]
lf_idx += 1
while d[lf_idx] < d[lf]:
lf_idx += 1
rg_idx -= 1
while d[rg_idx] > d[lf]:
rg_idx -= 1
d[lf], d[rg_idx] = d[rg_idx], d[lf]
for i in range(size):
print('%3d' % d[i], end='')
print()
quick(d, size, lf, rg_idx - 1) # 以rg_idx为基准点分成左右两半以递归方式
quick(d, size, rg_idx + 1, rg) # 分别为左右两半进行排序直至完成排序


def main():
data = [0] * 100
size = int(input('请输入数组大小(100以下):'))
inputarr(data, size)
print('您输入的原始数据是:')
showdata(data, size)
print('排序过程如下:')
quick(data, size, 0, size - 1)
print('最终的排序结果为:')
showdata(data, size)
main()

0x4.7基数排序法
基数排序法和之前的冒泡、选择、插入、希尔、合并、快速、堆积排序算法都不相同,它并不需要进行元素之间的比较操作。而是属于一种分配模式的排序方式。
基数排序方法按照比较的方向可分为最高位优先(Most Significant Digit First,MSD)和最低位优先(Least Significant Digit First,LSD)两种。MSD算法是从最左边的位数开始比较,而LSD是从最右边的位数开始比较。以LSD对三位数的整数数据来加以排序,它是按照个位、十位数、百位数这样的次序进行排序的。

1)首先每个整数按照个位数字放到列表中 + 从左到右合并后成为:……
2)按照十位数字,将其放到列表中: + 从左到右合并后成为 ……
3)按照百位数字,按序放到列表中 + 最后合并即可完成最后的排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import random
def inputarr(data, size):
for i in range(size):
data[i] = random.randint(0, 999) # 设置 data 值最大为 3 位数

def showdata(data, size):
for i in range(size):
print('%5d' % data[i], end='')
print()

def radix(data, size):
n = 1 # n为基数,从个位数开始排序
while n <= 100:
tmp = [[0] * 100 for row in range(10)] # 设置暂存数组,[0~9位数][数据个数],所有内容均为0
for i in range(size): # 对比所有数据
m = (data[i] // n) % 10 # m为 n 位数的值,如 36 取十位数(36/10)%10=3
tmp[m][i] = data[i] # 把 data[i] 的值暂存在 tmp 中
k = 0
for i in range(10):
for j in range(size):
if tmp[i][j] != 0: # 因为一开始设置 tmp ={0},故不为 0 者即为
data[k] = tmp[i][j] # data 暂存在 tmp 中的值,把 tmp 中的值放
k += 1 # 回 data[ ]里
print('经过%3d位数排序后:' % n, end='')
showdata(data, size)
n = 10 * n

def main():
data = [0] * 100
size = int(input('请输入数组大小(100以下):'))
print('您输入的原始数据是:')
inputarr(data, size)
showdata(data, size)
radix(data, size)
main()

0x4.8堆积排序法
堆积排序算法是选择排序算法的改进版本,他可以减少在选择排序中的比较次数,进而减少排序时间。堆积排序用到了二叉树的技巧,它是利用堆积树来完成排序的。堆积树是一种特殊的二叉树,可分为最大堆积树和最小堆积树。

最大堆积树满足如下三个条件:

1)它是一个完全二叉树

2)所有节点都大于或等于它左右子节点的值

3)树根是堆积树中最大的值

最小堆积树满足如下三个条件:

1)它是一个二叉树

2)所有节点都小于或等于它左右子节点的值

3)树根是对堆积树中最小的值

QQ:二叉树转换为最大堆积树:

从树根往下进行比较,大的值就往上排列,知道到达了树叶节点即可。(从二叉树的树根开始从上往下逐一按堆积树建立原则来改变各节点的值,最终得到一棵最大堆积树)

然后根据建立的最大堆积树,从大到小进行提取数据。

首先提取树根作为排好序数组的第一个值,然后在删除了树根的基础上,重新针对剩下的节点建立最大堆积树,然后再将树根放入数组作为第二个值,……

堆积排序法的分析:

1)在所有情况下,时间复杂度均为o(nlogn)

2)堆积排序不是稳定的排序算法

3)只需要一个额外的空间,空间复杂度为o(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def heap(data, size):
for i in range(int(size / 2), 0, -1): # 建立堆积树节点
ad_heap(data, i, size - 1)
print()
print('堆积的内容:', end='')
for i in range(1, size): # 原始堆积树的内容
print('[%2d] ' % data[i], end='')
print('\n')
for i in range(size - 2, 0, -1): # 堆积排序
data[i + 1], data[1] = data[1], data[i + 1] # 头尾节点交换
ad_heap(data, 1, i) # 处理剩余节点
print('处理过程为:', end='')
for j in range(1, size):
print('[%2d] ' % data[j], end='')
print()

def ad_heap(data, i, size):
j = 2 * i
tmp = data[i]
post = 0
while j <= size and post == 0:
if j < size:
if data[j] < data[j + 1]: # 找出最大节点
j += 1
if tmp >= data[j]: # 若树根较大,结束比较过程
post = 1
else:
data[int(j / 2)] = data[j] # 若树根较小,则继续比较
j = 2 * j
data[int(j / 2)] = tmp # 指定树根为父节点

def main():
data = [0, 5, 6, 4, 8, 3, 2, 7, 1] # 原始数组的内容
size = 9
print('原始数组为:', end='')
for i in range(1, size):
print('[%2d] ' % data[i], end='')
heap(data, size) # 建立堆积树
print('排序结果为:', end='')
for i in range(1, size):
print('[%2d] ' % data[i], end='')

main()

0x5查找与哈希算法

通常判断一个查找算法的好坏主要由比较次数及查找所需要时间来判断。
0x5.1顺序查找
顺序查找法又称线性,是一种简单的查找。它的方法是将数据一项一项地按照顺序逐个查找,所以不管数据顺序如何,都得从头到尾遍历一次。
0x5.2二分法查找
如果要查找的数据已经事先排好序了,则可以使用二分法来进行查找。二分查找法是将数据分割成二等份,再比较键值与中间值得大小,如果键值小于中间值,可确定查找的数据在前段,否则在后半部分。如此分割数直到找到或确定不存在为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def bin_search(data,val):
low=0
high=len(data)-1
while low<=high and val!=-1:
mid=int((low+high)/2)
if val<data[mid]:
high=mid-1
elif val>data[mid]:
low=mid+1
else:
return mid
return -1
data=[1,2,5,6,8,11,14,17]
val=5
print(bin_search(data,val))

0x5.3 插值查找法
插值查找法(Interpolation Search)又叫插补查找法,是二分查找法的改进版。它是按照数据位置的分布,利用公式预测数据所在的位置,再以二分法的方式渐渐逼近。使用插值法是假设数据平均分布在数组中,而每一项数据的差距相当接近或有一定距离比例。插值法的公式为:

1
Mid=low+((key-data[low])/(data[high]-data[low]))*(high-low)

其中key是要查找的键,data[high]和data[low]是剩余待查找记录中的最大值和最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def interpolation_search(data,val):
low=0
high=len(data)-1
while low<=high and val !=-1:
mid=low+int((val-data[low])*(high-low)/(data[high]-data[low]))
if val==data[mid]:
return mid
elif val <data[mid]:
high=mid-1
else:
low=mid+1
data=[1,2,5,6,8,11,14,17]
val=3
print(interpolation_search(data,val))

0x5.4常见的哈希法简介
哈希法是使用哈希函数来计算一个键值所对应的地址,进而建立哈希表格,然后依靠哈希函数来查找到各个键值存放在表格中的地址,查找速度与数据多少无关,在没有碰撞和溢出的情况下,一次读取即可完成

常见的哈希算法有除留余数法,平方取中法,折叠法及数字分析法
0x5.4.1除留余数法
最简单的哈希函数是将数据除以某一个常数后,取余数来当索引
例子:
在一个有13个位置的数组中,只使用到7个地址,值分别是12,65,70,99,33,67,48。我们可以把数组内的值除以13,并以其余数来当数组的下标(作为索引),可以用以下式子表示:
h(key)=key mod B

0x5.4.2平方取中法
先计算数据的平方,之后再取中间的某段数字作为索引

例子说明
将数据存放在100个地址空间中,其操作步骤如下:
第一步:将12,65,70,99,33,67,51平方后如下
144,4225,4900,9801,1089,4489,2601

第二步:取百位数和十位数作为键值,分别为
14,22,90,80,08,48,60

第三步:存放数据

1
2
3
4
5
6
7
f(14) = 12
f(22) = 65
f(90) = 70
f(80) = 99
f(8) = 33
f(48) = 67
f(60) = 51

0x5.4.3折叠法
折叠法是将数据转换成一串数字后,先将这串数字拆成几个部分,再把它们加起来,就可计算出这个键值的Bucket Address(桶地址)

例子说明
有一个数据,转换成数字后为2365479125443,若以每4个数字为一个部分则可拆为2365,4791,2544,3。将这4组数字加起来后即为索引值:2365+4791+2544+3=9703—>桶地址

在折叠法中有两种做法,如上例直接将每一部分相加所得的值作为其bucket address,这种方法称为”移动折叠法”。哈希法的设计原则之一就是降低碰撞,如果希望降低碰撞的机会,就可以将上述每一部分数字中的奇数或偶数反转,再相加来取得其bucket address,这种改进的做法称为”边界折叠法”(folding at the boundaries)

0x5.4.4数字分析法
适用于数据不会更改,且为数字类型的静态表。再决定哈希函数时先追一检查数据的相对位置和分布情况,将重复性高的部分删除。
0x5.5碰撞与溢出问题的处理
在哈希法中,当标识符要放入某个通(Bucket,哈希表中存储数据的位置)时,若该桶已经满了,就会发生溢出(Overflow);另一方面哈希法的理想情况是所有数据经过哈希函数运算后都得到不同的值,但现实情况是即使所有关键字段的值都不相同,还是可能得到相同的地址,于是就发生了碰撞(Collision)问题
0x5.5.1线性探测算法
原理简介
线性探测法是当发生碰撞情况时,若该索引对应的存储位置已有数据,则以线性的方式往后寻找空的存储位置,一旦找到位置就把数据放进去。线性探测法通常把哈希的位置视为环形结构,如此一来若后面的位置已被填满而前面还有位置时,可以将数据放到前面

线性探测算法

1
2
3
4
5
6
7
def create_table(num,index):
temp = num % INDEXBOX
while True:
if index[temp]==-1:
index[temp]=num
else:
temp=(temp+1)%INDEXBOX

范例:
以除留余数法的哈希函数取得索引值,再以·线性探测法来存储数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import random

INDEXBOX = 10
MAXNUM = 7

def print_data(data,max_number):
print("\t",end="")
for i in range(max_number):
print("[%2d]" %data[i],end="")
print()

def create_table(num,index):
temp = num%INDEXBOX
while True:
if index[temp]==-1:
index[temp]=num
break
else:
temp=(temp+1)%INDEXBOX

index = [None]*INDEXBOX
data = [None]*MAXNUM

print("原始数组值:")
for i in range(MAXNUM):
data[i]=random.randint(1,20)

for i in range(INDEXBOX):
index[i]=-1

print_data(data,MAXNUM)

print("哈希表内容:")
for i in range(MAXNUM):
create_table(data[i],index)
print("%2d =>" %data[i],end="")
print_data(index,INDEXBOX)

print("完成哈希表:")
print_data(index,INDEXBOX)

0x5.5.2平方探测法
线性探测法有一个缺点,就是相类似的键值经常会聚集在一起,因此可以考虑以平方探测法来加以改进。在平方探测中,当溢出发生时,下一次查找的地址是(f(x)+i)mod B与(f(x)-i)mod B,即让数据值加或减i的平方

例子说明
数据值key,哈希函数f

1
2
3
4
5
6
7
8
9
第一次查找:f(key)
第二次查找:(f(key)+1^2)%B
第三次查找:(f(key)-1^2)%B
第四次查找:(f(key)+2^2)%B
第五次查找:(f(key)-2^2)%B
......
......
......
第n次查找:(f(key)+-((B-1)/2)^2)%B,其中,B必须为4j+3型的质数,且1<=i<=(B-1)/2

0x5.5.3再哈希法
再哈希法就是一开始就先设置一系列的哈希函数,如果使用第一种哈希函数出现溢出时就改用第二种,如果第二种也出现溢出就用第三种,一直到没有发生溢出为止

例子说明
数据:681,467,633,511,100,164,472,438,445,366,118
其中哈希函数为(此处的m=13)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
f1 = h(key) = key MOD m
f2 = h(key) = (key+2) MOD m
f3 = h(key) = (key+4) MOD m
说明如下:
第一次:使用第一种哈希函数f1 = h(key) = key MOD m,得到的哈希地址如下:

```bash
681 ---> 5
467 ---> 12
633 ---> 9
511 ---> 4
100 ---> 9
164 ---> 8
472 ---> 4
438 ---> 9
445 ---> 3
366 ---> 2
118 ---> 1

第二步:其中100,472,438都发生碰撞,再使用第二种哈希函数f2 = h(key) = (key+2) MOD m,进行数据的地址

1
2
3
100 ---> h(100+2) = 102 mod 13 = 11
472 ---> h(472+2) = 474 mod 13 = 6
438 ---> h(438+2) = 440 mod 13 = 11

第三步:438仍发生碰撞问题,使用第三种哈希函数f3 = h(key) = (key+4) MOD m,重新进行438地址的安排

1
438 ---> h(438+4) = 442 mod 13 = 0

0x6 数组与链表算法

数组与链表都是相当重要的结构化数据类型(structured data type),也都是典型线性表的应用。按照内存存储的方式,基本上可分为以下两种方式:
1.静态数据结构(static data structure)
数据类型就是一种典型的静态数据结构,它使用连续分配的内存空间(contiguous allocation)来存储有序表中的数据。静态数据结构是在编译时就给相关的变量分配好内存空间。缺点是删除或加入数据时,需要移动大量的数据

2.动态数据结构(dynamic data structure)
动态数据结构又称为”链表”(linked list),它使用不连续的内存空间存储具有线性表特性的数据。优点是数据的插入或删除都相当方便,不需要移动大量数据

0x6.1矩阵

0x6.1.1 矩阵相加
相加的两个矩阵对应的行数与列数都必须相等,而相加后的矩阵的行数与列数也是相同的

1
2
3
4
5
6
7
8
9
10
11
12
A=[[1,3,5],[7,9,11],[13,15,17]]
B=[[9,8,7],[6,5,4],[3,2,1]]
N=3
C=[[None]*N for row in range(N)]
for i in range(3):
for j in range(3):
C[i][j]=A[i][j]+B[i][j]
print('[矩阵A和矩阵B相加的结果]')
for i in range(3):
for j in range(3):
print('%d'%C[i][j],end='\t')
print()

0x6.1.2矩阵相乘
两个矩阵A与B相乘受到某些限制。首先,必须符合A为一个mn的矩阵,B为np的矩阵,对AB之后的结果为一个mp的矩阵C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
def MatrixMultiply(arrA, arrB,arrC,M,N,P):
global C
if M<=0 or N<=0 or P<=0:
print('[错误:维数M,N,P必须大于0]')
return
for i in range(M):
for j in range(P):
Temp=0
for k in range(N):
Temp = Temp + int(arrA[i*N+k])*int(arrB[k*P+j])
arrC[i*P+j] = Temp

print('请输入矩阵A的维数(M,N): ')
M=int(input('M= '))
N=int(input('N= '))
A=[None]*M*N #声明大小为MxN的列表A

print('[请输入矩阵A的各个元素]')
for i in range(M):
for j in range(N):
A[i*N+j]=input('a%d%d='%(i,j))

print('请输入矩阵B的维数(N,P): ')
N=int(input('N= '))
P=int(input('P= '))

B=[None]*N*P #声明大小为NxP的列表B

print('[请输入矩阵B的各个元素]')
for i in range(N):
for j in range(P):
B[i*P+j]=input('b%d%d='%(i,j))

C=[None]*M*P #声明大小为MxP的列表C
MatrixMultiply(A,B,C,M,N,P)
print('[AxB的结果是]')
for i in range(M):
for j in range(P):
print('%d' %C[i*P+j], end='\t')
print()

0x6.1.3转置矩阵
“转置矩阵”(A)就是把原矩阵的行坐标元素与列坐标元素互相调换,假设A为A的转置矩阵,则有A[i,j]=A[j,i]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
arrA = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]

N = 4

arrB = [[None]*N for row in range(N)]

print("原设置的矩阵内容:")
for i in range(4):
for j in range(4):
print("%d" %arrA[i][j],end="\t")
print()

for i in range(4):
for j in range(4):
arrB[i][j] = arrA[j][i]

print("转置矩阵内容:")
for i in range(4):
for j in range(4):
print("%d" % arrB[i][j], end="\t")
print()

0x6.2 链表

在python中,如果以动态分配产生链表节点的节点,可以先行定义一个类,接着在该类中定义一个指针字段,作用是指向下一个链表节点,另外该类中至少要有一个数据字段。例如,我们声明一个学生成绩链表节点的结构声明,并且包含姓名(name),成绩(score)两个数据字段与一个指针字段(next)。在python语言中可以声明如下:

1
2
3
4
5
class student:
def __init__(self):
self.name=""
self.score=0
self.next=None

完成节点类的声明后,就可以动态建立链表中的每个节点。假设现在要新增一个节点至链表的末尾,且ptr指向链表的第一个节点,在程序上必须设计4个步骤:

动态分配内存空间给新节点使用
将原链表尾部的指针(next)指向新元素所在的内存位置
将ptr指针指向新的节点的内存位置,表示这是新的链表尾部
由于新节点当前为链表的最后一个元素,因此将它的指针(next)指向None
例如:将s1的next变量指向s2,而且s2的next变量指向None

1
2
s1.next=s2
s2.next=None

python程序片段是建立学生节点的单向链表的算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class student:
def __init__(self):
self.name=""
self.score=0
self.next=None

head = student()
head.next = None
ptr = head
select = 0

while select!=2:
print("(1)添加 (2)离开=>")
try:
select = int(input("请输入一个选项:"))
except ValueError:
print("输入错误")
print("请重新输入\n")
if select==1:
new_data = student()
new_data.name = input("姓名:")
new_data.no=input("学号:")
new_data.Math=eval(input("数学成绩:"))
ptr.next = new_data
new_data.next = None
ptr = ptr.next

0x6.2.1 单向链表的连接功能
对于两个或两个以上的连接(concatenation,也称为级联),其实现方法很容易:只要将链表的首尾相连即可
范例:
将两组学生成绩的链表连接起来,并输出新的学生的成绩链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import sys
import random

def concatlist(ptr1,ptr2):
ptr=ptr1
while ptr.next!=None:
ptr=ptr.next
ptr.next=ptr2
return ptr1

class employee:
def __init__(self):
self.num=0
self.salary=0
self.name=''
self.next=None

findword=0
data=[[None]*2 for row in range(12)]

namedata1=['Allen','Scott','Marry','Jon','Mark','Ricky','Lisa','Jasica', 'Hanson','Amy','Bob','Jack']

namedata2=['May','John','Michael','Andy','Tom','Jane','Yoko','Axel','Alex','Judy','Kelly','Lucy']

for i in range(12):
data[i][0]=i+1
data[i][1]=random.randint(51,100)

head1=employee() #建立第一组链表的头部
if not head1:
print('Error!! 内存分配失败!!')
sys.exit(0)

head1.num=data[0][0]
head1.name=namedata1[0]
head1.salary=data[0][1]
head1.next=None
ptr=head1
for i in range(1,12): #建立第一组链表
newnode=employee()
newnode.num=data[i][0]
newnode.name=namedata1[i]
newnode.salary=data[i][1]
newnode.next=None
ptr.next=newnode
ptr=ptr.next

for i in range(12):
data[i][0]=i+13
data[i][1]=random.randint(51,100)

head2=employee() #建立第二组链表的头部
if not head2:
print('Error!! 内存分配失败!!')
sys.exit(0)

head2.num=data[0][0]
head2.name=namedata2[0]
head2.salary=data[0][1]
head2.next=None
ptr=head2
for i in range(1,12): #建立第二组链表
newnode=employee()
newnode.num=data[i][0]
newnode.name=namedata2[i]
newnode.salary=data[i][1]
newnode.next=None
ptr.next=newnode
ptr=ptr.next

i=0
ptr=concatlist(head1,head2) #将链表相连
print('两个链表相连的结果为:')
while ptr!=None: #打印链表的数据
print('[%2d %6s %3d] => ' %(ptr.num,ptr.name,ptr.salary),end='')
i=i+1
if i>=3:
print()
i=0
ptr=ptr.next

0x6.2.2单向链表的节点
在单向链表类型的数据结构中,若要在链表中删除一个节点,如同一列火车中拿掉原来的车厢,根据所删除节点的位置会有以下三种不同的情况:
(1)删除链表的第一个节点
只要把链表头指针指向第二个节点即可
图解算法使用python笔记
python算法如下:

1
2
top=head
head=head.next

(2)删除链表的最后一个节点
只要指向最后一个节点ptr的指针直接指向None即可
图解算法使用python笔记
python算法如下:

1
2
ptr.next=tail
ptr.next=None

(3)删除链表内的中间节点
只要将删除节点的前一个节点的指针指向将要被删除节点的下一个节点即可 !! 图解算法使用python笔记
python算法如下:

1
2
Y=ptr.next
ptr.next=Y.next

范例:
在员工数据的链表中删除节点,并且允许所删除的节点有在链表头部,链表尾部和链表中间三种不同位置的情况。最后离开时,列出此链表的最后所有节点的数据字段的内容。结构成员类型如下:

1
2
3
4
5
6
class employee:
def __init__(self):
self.num=0
self.salary=0
self.name=""
self.next=None

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
import sys
class employee:
def __init__(self):
self.num = 0
self.salary = 0
self.name = ''
self.next = None

def del_ptr(head, ptr): # 删除节点子程序
top = head
if ptr.num == head.num: # [情形1]:要删除的节点在链表头部
head = head.next
print('已删除第 %d 号员工 姓名:%s 薪资:%d' % (ptr.num, ptr.name, ptr.salary))
else:
while top.next != ptr: # 找到删除节点的前一个位置
top = top.next
if ptr.next == None: # 删除在链表末尾的节点
top.next = None
print('已删除第 %d 号员工 姓名:%s 薪资:%d' % (ptr.num, ptr.name, ptr.salary))
else:
top.next = ptr.next # 删除在串行中的任一节点
print('已删除第 %d 号员工 姓名:%s 薪资:%d' % (ptr.num, ptr.name, ptr.salary))
return head # 返回链表

def main():
findword = 0
namedata = ['Allen', 'Scott', 'Marry', 'John', 'Mark', 'Ricky', 'Lisa', 'Jasica', 'Hanson', 'Amy', 'Bob', 'Jack']
data = [[1001, 32367], [1002, 24388], [1003, 27556], [1007, 31299], [1012, 42660], [1014, 25676], [1018, 44145],
[1043, 52182], [1031, 32769], [1037, 21100], [1041, 32196], [1046, 25776]]
print('员工编号 薪水 员工编号 薪水 员工编号 薪水 员工编号 薪水')
print('-------------------------------------------------------')
for i in range(3):
for j in range(4):
print('%2d [%3d] ' % (data[j * 3 + i][0], data[j * 3 + i][1]), end='')
print()
head = employee() # 建立链表头部
if not head:
print('Error!! 内存分配失败!!')
sys.exit(0)
head.num = data[0][0]
head.name = namedata[0]
head.salary = data[0][1]
head.next = None

ptr = head
for i in range(1, 12): # 建立链表
newnode = employee()
newnode.num = data[i][0]
newnode.name = namedata[i]
newnode.salary = data[i][1]
newnode.num = data[i][0]
newnode.next = None
ptr.next = newnode
ptr = ptr.next

while (True):
findword = int(input('请输入要删除的员工编号,要结束删除过程,请输入-1:'))
if (findword == -1): # 循环中断条件
break
else:
ptr = head
find = 0
while ptr != None:
if ptr.num == findword:
ptr = del_ptr(head, ptr)
find = find + 1
head = ptr
ptr = ptr.next
if find == 0:
print('######没有找到######')

ptr = head
print('\t员工编号 姓名\t薪水') # 打印剩余链表中的数据
print('\t==============================')
while (ptr != None):
print('\t[%2d]\t[ %-10s]\t[%3d]' % (ptr.num, ptr.name, ptr.salary))
ptr = ptr.next

main()

0x6.2.3单向链表的反转
如果要将单向链表反转,则必须使用三个指针变量
图解算法使用python笔记
python算法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class employee:
def __init__(self):
self.num=0
self.salary=0
self.name=""
self.next=None

def invert(x): # x为链表的头指针
p=x # 将p指向链表的开头
q=None # q是p的前一个节点
while p!=None:
r=q # 将r接到q之后
q=p # 将q接到p之后
p=p.next # p移到下一个节点
q.next=r # q连接到之前的节点
return q

在算法invert(X)中,我们使用了p,q,r三个指针变量,它的演变过程如下:
第一步:执行while循环前

图解算法使用python笔记
第二步:执行whilex
图解算法使用python笔记
第三步:第二次执行while循环
图解算法使用python笔记
当执行到p=None时,整个单向链表就整个反转过来了
范例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class employee:
def __init__(self):
self.num=0
self.salary=0
self.name=''
self.next=None

findword=0

namedata=['Allen','Scott','Marry','Jon', \
'Mark','Ricky','Lisa','Jasica', \
'Hanson','Amy','Bob','Jack']

data=[[1001,32367],[1002,24388],[1003,27556],[1007,31299], \
[1012,42660],[1014,25676],[1018,44145],[1043,52182], \
[1031,32769],[1037,21100],[1041,32196],[1046,25776]]

head=employee() #建立链表头部
if not head:
print('Error!! 内存分配失败!!')
sys.exit(0)

head.num=data[0][0]
head.name=namedata[0]
head.salary=data[0][1]
head.next=None
ptr=head
for i in range(1,12): #建立链表
newnode=employee()
newnode.num=data[i][0]
newnode.name=namedata[i]
newnode.salary=data[i][1]
newnode.next=None
ptr.next=newnode
ptr=ptr.next

ptr=head
i=0
print('反转前的员工链表节点数据:')
while ptr !=None: #打印链表数据
print('[%2d %6s %3d] => ' %(ptr.num,ptr.name,ptr.salary), end='')
i=i+1
if i>=3: #三个元素为一行
print()
i=0
ptr=ptr.next

ptr=head
before=None
print('\n反转后的链表节点数据:')
while ptr!=None: #链表反转,利用三个指针
last=before
before=ptr
ptr=ptr.next
before.next=last

ptr=before
while ptr!=None:
print('[%2d %6s %3d] => ' %(ptr.num,ptr.name,ptr.salary), end='')
i=i+1
if i>=3:
print()
i=0
ptr=ptr.next

0x7堆栈与队列算法

堆栈结构在计算机领域中的应用相当广泛,常用于计算机程序的运行,例如递归调用、子程序调用。
队列在计算机领域中的应用也相当广泛,例如计算机的模拟、CPU的作业调度、外围设备联机并发处理系统的应用以及图形遍历的广度优先搜索法。

0x7.1堆栈

0x7.1.1数组来实现堆栈
优点:用列表实现堆栈设计非常简单
缺点:如果堆栈本身的大小是变动的,但列表的大小只能是预先规划和声明的,则列表规划太大会浪费空间,规划过小则不够用。

范例:
使用数组结构来设计一个python程序,用循环来控制元素压入堆栈或弹出堆栈,并仿真堆栈的各种操作,此堆栈的最大容量是100个元素,其中必须包括压入(push)和弹出(pop),并在最后输出堆栈内的所有元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
MAXSTACK = 100  # 定义堆栈的最大容量
global stack
stack = [None] * MAXSTACK # 堆栈的数组声明
top = -1 # 堆栈的顶端


# 判断是否为空堆栈
def isEmpty():
if top == -1:
return True
else:
return False


# 将指定的数据压入堆栈
def push(data):
global top
global MAXSTACK
global stack
if top >= MAXSTACK - 1:
print('堆栈已满,无法再加入')
else:
top += 1
stack[top] = data # 将数据压入堆栈


# 从堆栈弹出数据*/
def pop():
global top
global stack
if isEmpty():
print('堆栈是空')
else:
print('弹出的元素为: %d' % stack[top])
top = top - 1


# 主程序
i = 2
count = 0
while True:
i = int(input('要压入堆栈,请输入1,要弹出则输入0,停止操作则输入-1: '))
if i == -1:
break
elif i == 1:
value = int(input('请输入元素值:'))
push(value)
elif i == 0:
pop()

print('============================')
if top < 0:
print('\n 堆栈是空的')
else:
i = top
while i >= 0:
print('堆栈弹出的顺序为:%d' % (stack[i]))
count += 1
i = i - 1
print

print('============================')

范例:
设计一个python程序,以数组仿真扑克牌洗牌以及发牌的过程。使用随机数来生成扑克牌放入堆栈,放满52张牌后开始发牌,使用堆栈功能来给4个人发牌。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
import random
global top
top = -1
k = 0

def push(stack, MAX, val):
global top
if top >= MAX - 1:
print('[堆栈已经满了]')
else:
top = top + 1
stack[top] = val


def pop(stack):
global top
if top < 0:
print('[堆栈已经空了]')
else:
top = top - 1
return stack[top]

def shuffle(old):
result = []
while old:
p = random.randrange(0, len(old))
result.append(old

)
old.pop(p)
return result


card = [None] * 52
card_new = [None] * 52
stack = [0] * 52
for i in range(52):
card[i] = i + 1

print('[洗牌中...请稍候!]')

card_new = shuffle(card)

i = 0
while i != 52:
push(stack, 52, card_new[i]) # 将52张牌压入堆栈
i = i + 1

print('[逆时针发牌]')
print('[显示各家的牌] 东家\t 北家\t 西家\t 南家')
print('=================================')

while top >= 0:
# print(stack[top])
style = (stack[top]) % 4 # 计算牌的花色
# print('style=', style)
if style == 0: # 梅花
ascVal = 'club'
elif style == 1: # 方块
ascVal = 'diamond'
elif style == 2: # 红心
ascVal = 'heart'
elif style == 3:
ascVal = 'spade' # 黑桃
print('[%s%3d]\t' % (ascVal, stack[top] % 13 + 1), end='')
if top % 4 == 0:
print()
top -= 1

0x7.1.2 用链表实现堆栈
优点:随时可以动态改变链表的长度,能有效利用内存资源,缺点:设计的算法较为复杂。

利用链表实现堆栈时,同样需要定义链表节点,包含一个next指针。
范例:
设计一个python程序以链表来实现堆栈操作,并使用循环来控制元素的压入堆栈或弹出堆栈,其中必须包括压入(push)和弹出(pop)函数,并在最后输出堆栈内的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Node:  # 堆栈链结节点的声明
def __init__(self):
self.data = 0 # 堆栈数据的声明
self.next = None # 堆栈中用来指向下一个节点
top = None

# 判断堆栈是否为空,是空返回1,否则返回0
def isEmpty():
global top
if (top == None):
return 1
else:
return 0
# 将指定的数据压入堆栈
def push(data):
global top
new_add_node = Node()
new_add_node.data = data # 将传入的值指定为节点的内容
new_add_node.next = top # 将新节点指向堆栈的顶端
top = new_add_node # 新节点成为堆栈的顶端

# 从堆栈弹出数据
def pop():
global top
if isEmpty():
print('===目前为空堆栈===')
return -1
else:
ptr = top # 指向堆栈的顶端
top = top.next # 将堆栈顶端的指针指向下一个节点
temp = ptr.data # 弹出堆栈的数据
return temp # 将从堆栈弹出的数据返回给主程序

# 主程序
while True:
i = int(input('要压入堆栈,请输入1,要弹出则输入0,停止操作则输入-1: '))
if i == -1:
break
elif i == 1:
value = int(input('请输入元素值:'))
push(value)
elif i == 0:
print('弹出的元素为%d' % pop())

print('============================')
while (not isEmpty()): # 将数据陆续从顶端弹出
print('堆栈弹出的顺序为:%d' % pop())

0x7.1.3汉诺塔问题的求解算法
该游戏是在一块铜板装置上,有三根杆(编号A、B、C),在A杆自下而上、由大到小按顺序放置64个金盘(如下图)。游戏的目标:把A杆上的金盘全部移到C杆上,并仍保持原有顺序叠好。操作规则:每次只能移动一个盘子,并且在移动过程中三根杆上都始终保持大盘在下,小盘在上,操作过程中盘子可以置于A、B、C任一杆上
汉诺塔问题归纳成三个步骤:
1)将n-1个盘子从木杆1移动到了木杆2
2)将第n个最大盘子从木桩1移动到木桩3
3)将n-1个盘子从木桩2移动到了木桩3

1
2
3
4
5
6
7
8
9
def hanoi(n,p1,p2,p3):
if n==1:
print('盘子从%d移到%d'%(p1,p3))
else:
hanoi(n-1,p1,p3,p2)
print('盘子从%d移到%d'%(p1,p3))
hanoi(n-1,p2,p1,p3)
j=int(input('请输入要移动盘子的数量:'))
hanoi(j,1,2,3)

0x7.1.4八皇后问题
八皇后问题也是一种常见的堆栈的应用。现在要放入多个皇后到棋盘上,相互之间还不能吃到对方。后放入的皇后,放入前必须考虑所放位置的直线方向、横线方向或对角线方向是否已经被放置了旧皇后,否则就会被先放入的旧皇后吃掉。

4皇后在4x4的棋盘上,8皇后问题在8x8的棋盘上,N皇后问题就在NXN的棋盘上。

在实际过程中也会用到回朔法:如果放置新皇后的该行(列)的8个位置都没有办法放置新皇后(放入都会被之前的吃掉),此时必须从堆栈中弹出前一个皇后的位置,并在该行(列)中重新寻找另一个新的位置来放,再将该位置压入堆栈中,而这种方式就是一种回溯算法的应用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
global queen
global number
EIGHT = 8 # 定义堆栈的最大容量
queen = [None] * 8 # 存放8个皇后的行位置

number = 0 # 计算总共有几组解的总数
# 决定皇后存放的位置
# 输出所需要的结果
def print_table():
global number
x = y = 0
number += 1
print('')
print('八皇后问题的第%d组解\t' % number)
for x in range(EIGHT):
for y in range(EIGHT):
if x == queen[y]:
print('<q>', end='')
else:
print('<->', end='')
print('\t')
input('\n..按下任意键继续..\n')
# 测试在(row,col)上的皇后是否遭受攻击
# 若遭受攻击则返回值为1,否则返回0
def attack(row, col):
global queen
i = 0
atk = 0
offset_row = offset_col = 0
while (atk != 1) and i < col:
offset_col = abs(i - col)
offset_row = abs(queen[i] - row)
# 判断两皇后是否在同一行或在同一对角线上
if queen[i] == row or offset_row == offset_col:
atk = 1
i = i + 1
return atk
def decide_position(value):
global queen
i = 0
while i < EIGHT:
if attack(i, value) != 1:
queen[value] = i
if value == 7:
print_table()
else:
decide_position(value + 1)
i = i + 1

# 主程序
decide_position(0)

0x7.1.5老鼠走迷宫问题
老鼠遵守以下三个原则:

1)一次只能走一格

2)遇到墙无法往前走,退回一步找找看能否有其他的路可走

3)走过的路不会再走第二次

可以采用二维数组MAZE[row][col],并附和一下规则:

1.MAZE[i][j]=1,表示[i][j]处有墙,无法通过

2.MAZE[i][j]=0,表示[i][j]处无墙,可以通过

3.MAZE[1][1]是入口,MAZE[m][n]是出口。

可以使用链表的方式来记录已经走过的位置,并且将走过的位置对应的数组元素内容标记为2,然后阿静这个位置放入堆栈再进行下一次的选择。

该算法时每次进行移动时所执行的操作,其主要是判断当前所在位置的上、下、左、右是否还有可以前进的方格。如果找到可以前进的方格,则将该方格的编号加入记录移动路径的堆栈中,并往该方格移动;如果四周没有可走的方格时,也就是当前所在的方格无法走出迷宫,必须退回到前一格重新检查是否有其他的可走的路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
class Node:
def __init__(self, x, y):
self.x = x
self.y = y
self.next = None
class TraceRecord:
def __init__(self):
self.first = None
self.last = None

def isEmpty(self):
return self.first == None

def insert(self, x, y):
newNode = Node(x, y)
if self.first == None:
self.first = newNode
self.last = newNode
else:
self.last.next = newNode
self.last = newNode

def delete(self):
if self.first == None:
print('[队列已经空了]')
return
newNode = self.first
while newNode.next != self.last:
newNode = newNode.next
newNode.next = self.last.next
self.last = newNode

ExitX = 8 # 定义出口的X坐标在第8行
ExitY = 10 # 定义出口的Y坐标在第10列
# 声明迷宫数组
MAZE = [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], \
[1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], \
[1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1], \
[1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1], \
[1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1], \
[1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1], \
[1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1], \
[1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1], \
[1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1], \
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]


def chkExit(x, y, ex, ey):
if x == ex and y == ey:
if (MAZE[x - 1][y] == 1 or MAZE[x + 1][y] == 1 or MAZE[x][y - 1] == 1 or MAZE[x][y + 1] == 2):
return 1
if (MAZE[x - 1][y] == 1 or MAZE[x + 1][y] == 1 or MAZE[x][y - 1] == 2 or MAZE[x][y + 1] == 1):
return 1
if (MAZE[x - 1][y] == 1 or MAZE[x + 1][y] == 2 or MAZE[x][y - 1] == 1 or MAZE[x][y + 1] == 1):
return 1
if (MAZE[x - 1][y] == 2 or MAZE[x + 1][y] == 1 or MAZE[x][y - 1] == 1 or MAZE[x][y + 1] == 1):
return 1
return 0


# 主程序

path = TraceRecord()
x = 1
y = 1

print('[迷宫的路径(0标记的部分)]')
for i in range(10):
for j in range(12):
print(MAZE[i][j], end='')
print()

while x <= ExitX and y <= ExitY:
MAZE[x][y] = 2
if MAZE[x - 1][y] == 0:
x -= 1
path.insert(x, y)
elif MAZE[x + 1][y] == 0:
x += 1
path.insert(x, y)
elif MAZE[x][y - 1] == 0:
y -= 1
path.insert(x, y)
elif MAZE[x][y + 1] == 0:
y += 1
path.insert(x, y)
elif chkExit(x, y, ExitX, ExitY) == 1:
break
else:
MAZE[x][y] = 2
path.delete()
x = path.last.x
y = path.last.y
print('[老鼠走过的路径(2标记的部分)]')
for i in range(10):
for j in range(12):
print(MAZE[i][j], end='')
print()

0x7.2 队列

0x7.2.1 数组实现队列
与堆栈不同的是需要拥有两种基本操作:加入与删除,而且要使用front与rear两个指针来分别指向队列的前端与末尾,缺点是数组大小无法根据队列的实际需要来动态申请,只能说明固定的大小

1
2
3
4
MAXSIZE=4
queue=[0]*MAXSIZE
front=-1
rear=-1 # 队列为空时,front=-1,rear=-1

队列操作的过程用python语言将以数组操作队列的相关算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def enqueue(item):    # 将新数据加入Q的末尾,返回新队列
global rear
global MAX_SIZE
global queue
if rear==MAX_SIZE-1:
print("队列已满!")
else:
rear+=1
queue[rear]=item
def dequeue(item): # 删除队列前端的数据,返回新队列
global rear
global MAX_SIZE
global front
global queue
if front==rear:
print("队列为空!")
else:
front+=1
item=queue[front]
def FRONT_VALUE(Queue): #返回队列前端的值
global rear
global front
global queue
if front==rear:
print("这是空队列!")
else:
print(queue[front])

范例:
打印输出队列前端的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import sys

MAX=10 #定义队列的大小
queue=[0]*MAX
front=rear=-1
choice=''
while rear<MAX-1 and choice !='e':
choice=input('[a]表示加入一个数值,[d]表示取出一个数值,[e]表示跳出此程序: ')
if choice=='a':
val=int(input('[请输入数值]: '))
rear+=1
queue[rear]=val
elif choice=='d':
if rear>front:
front+=1
print('[取出数值为]: [%d]' %(queue[front]))
queue[front]=0
else:
print('[队列已经空了]')
sys.exit(0)
else:
print()

print('------------------------------------------')
print('[输出队列中的所有元素]:')

if rear==MAX-1:
print('[队列已满]')
elif front>=rear:
print('没有')
print('[队列已空]')
else:
while rear>front:
front+=1
print('[%d] ' %queue[front],end='')
print()
print('------------------------------------------')
print()

0x7.2.2链表实现队列

1
2
3
4
5
6
7
8
9
10
class student:
def __init__(self):
self.name=" "*20
self.score=0
self.next=None

front=student()
rear=student()
front=None
rear=None

在队列中加入新的节点,等于加到此队列的末端;在队列中删除节点,就是将此队列最前端的节点删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def enqueue(name,score):
global front
global rear
new_data=student()
new_data.name=name
new_data.score=score
if rear==None:
front=new_data
else:
rear.next=new_data

rear=new_data
new_data.next=None
def dequeue():
global front
global rear
if front==None:
print("队列已空!")
else:
print("姓名:%s\t成绩:%d...取出" %(front.name,front.score))
front=front.next

范例:
链表中元素节点仍为学生姓名及成绩的结构数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class student:
def __init__(self):
self.name=' '*20
self.score=0
self.next=None

front=student()
rear=student()
front=None
rear=None

def enqueue(name, score): # 把数据加入队列
global front
global rear
new_data=student() # 分配内存给新元素
new_data.name=name # 给新元素赋值
new_data.score = score
if rear==None: # 如果rear为None,表示这是第一个元素
front = new_data
else:
rear.next = new_data # 将新元素连接到队列末尾

rear = new_data # 将rear指向新元素,这是新的队列末尾
new_data.next = None # 新元素之后无其他元素

def dequeue(): # 取出队列中的数据
global front
global rear
if front == None:
print('队列已空!')
else:
print('姓名:%s\t成绩:%d ....取出' %(front.name, front.score))
front = front.next # 将队列前端移到下一个元素

def show(): # 显示队列中的数据
global front
global rear
ptr = front
if ptr == None:
print('队列已空!')
else:
while ptr !=None: # 从front到rear遍历队列
print('姓名:%s\t成绩:%d' %(ptr.name, ptr.score))
ptr = ptr.next

select=0
while True:
select=int(input('(1)加入 (2)取出 (3)显示 (4)离开 => '))
if select==4:
break
if select==1:
name=input('姓名: ')
score=int(input('成绩: '))
enqueue(name, score)
elif select==2:
dequeue()
else:
show()

0x 7.2.3双向队列
双向队列(Double Ended Queues,DEQue)为一个有序线性表,加入与删除可在队列的任意一端进行
图解算法使用python笔记
双向队列的应用可以区分为两种:第一种是数据只能从一端加入,但可从两端取出;;另一种则是可从两端加入,但从一端取出
范例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class Node:
def __init__(self):
self.data=0
self.next=None

front=Node()
rear=Node()
front=None
rear=None

#方法enqueue:队列数据的加入
def enqueue(value):
global front
global rear
node=Node() #建立节点
node.data=value
node.next=None
#检查是否为空队列
if rear==None:
front=node #新建立的节点成为第1个节点
else:
rear.next=node #将节点加入到队列的末尾
rear=node #将队列的末尾指针指向新加入的节点

#方法dequeue:队列数据的取出
def dequeue(action):
global front
global rear
#从队列前端取出数据
if not(front==None) and action==1:
if front==rear:
rear=None
value=front.data #将队列数据从前端取出
front=front.next #将队列的前端指针指向下一个
return value
#从队列末尾取出数据
elif not(rear==None) and action==2:
startNode=front #先记下队列前端的指针值
value=rear.data #取出队列当前末尾的数据
#查找队列末尾节点的前一个节点
tempNode=front
while front.next!=rear and front.next!=None:
front=front.next
tempNode=front
front=startNode #记录从队列末尾取出数据后的队列前端指针
rear=tempNode #记录从队列末尾取出数据后的队列末尾指针
#下一行程序是指当队列中仅剩下最后一个节点时,
#取出数据后便将front和rear指向None
if front.next==None or rear.next==None:
front=None
rear=None
return value
else:
return -1

print('用链表来实现双向队列')
print('====================================')

ch='a'
while True:
ch=input('加入请按 a,取出请按 d,结束请按 e:')
if ch =='e':
break
elif ch=='a':
item=int(input('加入的元素值:'))
enqueue(item)
elif ch=='d':
temp=dequeue(1)
print('从双向队列前端按序取出的元素数据值为:%d' %temp)
temp=dequeue(2)
print('从双向队列末尾按序取出的元素数据值为:%d' %temp)
else:
break

0x8 树形结构及其算法

树形结构是一种应用相当广泛的非线性结构。树状算法在程序中的建立与应用大多使用链表来处理,当然也可以使用数组这样的连续内存来表示二叉树

由于二叉树的应用相当广泛,因此衍生了许多特殊的二叉树结构
1.满二叉树(fully binary tree)
如果二叉树的高度为h,树的节点数为2-1,h>=0,就称此树为”满二叉树”
图解算法使用python笔记
2.完全二叉树(complete binary tree)
如果二叉树的高速为h,所含的节点数小于2-1,但其节点的编号方式如同高度为h的满二叉树一样,从左到右,从上到下的顺序一一对应
图解算法使用python笔记
对于完全二叉树而言,假设有N个节点,那么此二叉树的层数h为log(N+1)

3.斜二叉树(skewed binary tree)
当一个二叉树完全没有左节点或右节点时,就称为左斜二叉树或右斜二叉树
图解算法使用python笔记
4.严格二叉树(strictly binary tree)
二叉树中的每一个非终端节点均有非空的左右子树
图解算法使用python笔记
0x8.1数组实现二叉树
使用有序的一位数组来表示二叉树,首先可将此二叉树假想成一棵满二叉树,而且第K层具有2个节点,按序存放在一维数组中

首先来看看使用一维数组建立二叉树的表示方法以及数组索引值的设置

索引值 1 2 3 4 5 6 7
内容值 A B C D

一维数组中的索引值有以下关系:
1.左子树索引值是父节点索引值乘2
2.右子树索引值是父节点索引值乘2加1

二叉查找树具有以下特点:
1.可以是空集合,若不是空集合,则节点上一定要有一个键值
2.每一个树根的值需大于左子树的值
3.每一个树根的值需小于右子树的值
4.左右子树也是二叉查找树
5.树的每个节点值都不相同
范例:
现在示范用一组数据(32,25,16,35,27)来建立一棵二叉查找树,具体过程如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def Btree_create(btree,data,length):
for i in range(1,length):
level=1
while btree[level]!=0:
if data[i]>btree[level]: #如果数组内的值大于树根,则往右子树比较
level=level*2+1
else: #如果数组内的值小于或等于树根,则往左子树比较
level=level*2
btree[level]=data[i] #把数组值放入二叉树

length=9
data=[0,6,3,5,4,7,8,9,2] #原始数组
btree=[0]*16 #存放二叉树数组
print('原始数组内容:')
for i in range(length):
print('[%2d] ' %data[i],end='')
print('')
Btree_create(btree,data,9)
print('二叉树内容:')
for i in range(1,16):
print('[%2d] ' %btree[i],end='')
print()

0x8.2 链表实现二叉树
链表实现二叉树,就是使用功能链表来存储二叉树。使用链表来表示二叉树的好处是对于节点的增加与删除相当容易,缺点是很难找到父节点,除非在每一节点多增加一个父字段

1
2
3
4
5
class tree:
def __init__(self):
self.data=0
self.left=None
self.right=None

链表实现二叉树的示意图:

以链表方式建立二叉树的python算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def create_tree(root,val):    #建立二叉树的函数
newnode=tree()
newnode.data=val
newnode.left=None
newnode.right=None
if root==None:
root=newnode
return root
else:
current=root
while current!=None:
backup=current
if current.data > val:
current=current.left
else:
current=current.right
if backup.data >val:
backup.left=newnode
else:
backup.right=newnode
return root

范例:
按序输入一棵二叉树10个节点的数据,分别是5,6,24,8,12,3,17,1,9,并使用链表来建立二叉树。最后输出左,右子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class tree:
def __init__(self):
self.data=0
self.left=None
self.right=None

def create_tree(root,val): #建立二叉树的函数
newnode=tree()
newnode.data=val
newnode.left=None
newnode.right=None
if root==None:
root=newnode
return root
else:
current=root
while current!=None:
backup=current
if current.data > val:
current=current.left
else:
current=current.right
if backup.data >val:
backup.left=newnode
else:
backup.right=newnode
return root

data=[5,6,24,8,12,3,17,1,9]
ptr=None
root=None
for i in range(9):
ptr=create_tree(ptr,data[i]) #建立二叉树
print('左子树:')
root=ptr.left
while root!=None:
print('%d' %root.data)
root=root.left
print('--------------------------------')
print('右子树:')
root=ptr.right
while root!=None:
print('%d' %root.data)
root=root.right
print()

0x8.3二叉树遍历
所谓二叉树的遍历(Binary Tree Traversal),最简单的说法就是”访问树中所有的节点各一次”,并且在遍历后,将树中的数据转化为线性关系

简单二叉树节点而言,每个节点都可分为左右两个分支
图解算法使用python笔记
可以有ABC,ACB,BAC,BCA,CAB,CBA一共6种遍历方法。如果按照二叉树特性,一律从左到右,那么就只剩下三种遍历方式,分别是BAC,ABC,BCA三种。这三种方式的命名与规则如下:

中序遍历(BAC,Inorder):左子树—>树根—>右子树
前序遍历(ABC,Preorder):树根—>左子树—>右子树
后序遍历(BCA,Postorder):左子树—>右子树—>树根
1.中序遍历
中序遍历(Inorder Traversal)是”左中右”的遍历顺序,也就是从树的左侧逐步向下方移动,直到无法移动,再访问此节点,并向右移动一节点。如果无法再向右移动时,可以返回上层的父节点,并重复左,中,右的步骤:

遍历左子树
遍历(或访问)树根
遍历右子树
中序遍历结果:FDHGIBEAC
图解算法使用python笔记
中序遍历的递归算法如下:

1
2
3
4
5
def inorder(ptr):      #中序遍历子程序
if ptr!=None:
inorder(ptr.left)
print('[%2d] ' %ptr.data, end='')
inorder(ptr.right)

2.后序遍历
后序遍历(Postorder Traversal)是”左右中”的遍历顺序,就是先遍历左子树,在遍历右子树,最后遍历(或访问)根节点。反复执行此步骤

遍历左子树
遍历右子树
遍历树根
后序遍历结果:FHIGDEBCA

后序遍历的递归算法如下:

1
2
3
4
5
def postorder(ptr):      #后序遍历子程序
if ptr!=None:
inorder(ptr.left)
inorder(ptr.right)
print('[%2d] ' %ptr.data, end='')

3.前序遍历
前序遍历(Preorder Traversal)是”中左右”的遍历顺序,也就是先从根节点遍历,再往左方移动,当无法继续时,继续向右方移动,接着再重复执行此步骤:

遍历树根
遍历左子树
遍历右子树
前序遍历结果:ABDFGHIEC

前序遍历的递归算法:

1
2
3
4
5
def preorder(ptr):      #前序遍历子程序
if ptr!=None:
print('[%2d] ' %ptr.data, end='')
inorder(ptr.left)
inorder(ptr.right)

范例:
按序输入一棵二叉树节点的数据,分别是5,6,24,8,12,3,17,1,9,利用链表来建立二叉树,最后进行中序遍历,轻松完成从小到大的排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class tree:
def __init__(self):
self.data = 0
self.left = None
self.right = None


def inorder(ptr): # 中序遍历子程序
if ptr != None:
inorder(ptr.left)
print('[%2d] ' % ptr.data, end='')
inorder(ptr.right)


def create_tree(root, val): # 建立二叉树的函数
newnode = tree()
newnode.data = val
newnode.left = None
newnode.right = None
if root == None:
root = newnode
return root
else:
current = root
while current != None:
backup = current
if current.data > val:
current = current.left
else:
current = current.right
if backup.data > val:
backup.left = newnode
else:
backup.right = newnode
return root


# 主程序
data = [5, 6, 24, 8, 12, 3, 17, 1, 9]
ptr = None
root = None
for i in range(9):
ptr = create_tree(ptr, data[i]) # 建立二叉树
print('====================')
print('排序完成的结果:')
inorder(ptr) # 中序遍历
print('')

0x 8.4 二叉树的查找
二叉树在建立的过程中,是根据左子树<树根<右子树的原则建立的,因此只需从树根出发比较键值,如果比数根大就往右,否则往左而下,直到相等就找到了要查找的值,如果比到None,无法在前进就代表查找不到此值

二叉树查找的算法:

1
2
3
4
5
6
7
8
9
10
11
def search(ptr,val):     #查找二叉树中某个值的子程序
while True:
if ptr==None: #没找到就返回None
return None
if ptr.data==val: #节点值等于查找值
print('共查找 %3d 次' %i)
return ptr
elif ptr.data > val: #节点值大于查找值
ptr=ptr.left
else:
ptr=ptr.right

范例:
建立一个二叉树找树,并输入要查找的值。二叉树节点的数据按序依次为7,1,4,2,8,13,12,11,15,9,5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class tree:
def __init__(self):
self.data=0
self.left=None
self.right=None

def create_tree(root,val): #建立二叉树的函数
newnode=tree()
newnode.data=val
newnode.left=None
newnode.right=None
if root==None:
root=newnode
return root
else:
current=root
while current!=None:
backup=current
if current.data > val:
current=current.left
else:
current=current.right
if backup.data >val:
backup.left=newnode
else:
backup.right=newnode
return root

def search(ptr,val): #查找二叉树中某个值的子程序
i=1
while True:
if ptr==None: #没找到就返回None
return None
if ptr.data==val: #节点值等于查找值
print('共查找 %3d 次' %i)
return ptr
elif ptr.data > val: #节点值大于查找值
ptr=ptr.left
else:
ptr=ptr.right
i+=1

#主程序
arr=[7,1,4,2,8,13,12,11,15,9,5]
ptr=None
print('[原始数组内容]')
for i in range(11):
ptr=create_tree(ptr,arr[i]) #建立二叉树
print('[%2d] ' %arr[i],end='')
print()
data=int(input('请输入查找值:'))
if search(ptr,data) !=None : #在二叉树中查找
print('您要找的值 [%3d] 找到了!!' %data)
else:
print('您要找的值没找到!!')

0x8.5二叉树节点的插入
二叉树插入 的情况和查找相似,重点是插入后仍要保持二叉查找数的特性。

1
2
3
4
5
if search(ptr,data)!=None:      #在二叉树中查找
print('二叉树中有此节点了!')
else:
ptr=create_tree(ptr,data)
inorder(ptr)

范例:
二叉树的节点数据按序为7,1,4,2,8,13,12,11,15,9,然后输入一个键值,如果不在此二叉树中,就将其加入到二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class tree:
def __init__(self):
self.data=0
self.left=None
self.right=None

def create_tree(root,val): #建立二叉树的函数
newnode=tree()
newnode.data=val
newnode.left=None
newnode.right=None
if root==None:
root=newnode
return root
else:
current=root
while current!=None:
backup=current
if current.data > val:
current=current.left
else:
current=current.right
if backup.data >val:
backup.left=newnode
else:
backup.right=newnode
return root

def search(ptr,val): #在二叉树中查找某个值的子程序
while True:
if ptr==None: #没找到就返回None
return None
if ptr.data==val: #节点值等于查找值
return ptr
elif ptr.data > val: #节点值大于查找值
ptr=ptr.left
else:
ptr=ptr.right

def inorder(ptr): #中序遍历子程序
if ptr!=None:
inorder(ptr.left)
print('[%2d] ' %ptr.data, end='')
inorder(ptr.right)

#主程序
arr=[7,1,4,2,8,13,12,11,15,9,5]
ptr=None
print('[原始数组内容]')

for i in range(11):
ptr=create_tree(ptr,arr[i]) #建立二叉树
print('[%2d] ' %arr[i],end='')
print()
data=int(input('请输入要查找的键值:'))
if search(ptr,data)!=None: #在二叉树中查找
print('二叉树中有此节点了!')
else:
ptr=create_tree(ptr,data)
inorder(ptr)

0x8.6二叉树的删除
二叉树节点的删除操作则稍为复杂,可分为以下三种情况:
1.删除的节点为树叶,只要将其相连的父节点指向None即可
2.删除的节点只有一棵子树。如下图:删除节点1,就将其右指针字段放在父节点的左指针字段
3.删除的节点有两棵子树。如下图:要删除节点4,方式有两种,虽然结果不同,但都可符合二叉树特性

3.1 找出中序立即先行者(inorder immediate predecessor),就是将欲删除节点的左子树中最大者向上提,在此即为上图中的节点2。简单来说,就是在该节点的左子树,往右寻找,直到右指针为None,这节点就是中序立即先行者

3.2 找出中序立即后续者(inorder immediate successor),就是把要删除节点的右子树中最小者向上提,在此即为上图中的节点5。简单来说,就是在该节点的右子树,往左寻找,直到左指针为None,这个节点就是中序立即后续者
图解算法使用python笔记
0x8.7二叉树的删除
堆积排序法算是选择排序法的改进版,它可以减少在选择排序法中的比较次数,进而减少排序时间。堆积树是一种特殊的二叉树,可分为最大堆积树和最小堆积树两种。

最大堆积树满足以下3个条件:
它是一个完全二叉树
所有节点的值都大于或等于它左右子节点的值
树根是堆积树中最大的

最小堆积树满足以下3个条件:
它是一个完全二叉树
所有节点的值都小于或等于它左右子节点的值
树根是堆积树中最小的
假设有9项数据32,17,16,24,35,87,65,4,12,以二叉树表示:
图解算法使用python笔记
如果要将该二叉树转换堆积树(heap tree),我们可以用数组来存储二叉树所有节点的值,即:

1
2
3
A[0]=32,A[1]=17,A[2]=16,A[3]=24,A[4]=35,A[5]=87

A[6]=65,A[7]=4,A[8]=12

步骤01:A[0]=32为树根,若A[1]大于父节点,则必须互换。此处A[1]=17<A[0]=32故不交换

步骤02:A[2]=16<A[0],故不交换

步骤03:A[3]=24>A[1]=17,故交换,如下图

图解算法使用python笔记
步骤04:A[4]=35>A[1]=24,故交换,再与A[0]=32比较,A[1]=35>A[0]=32,故交换,如下图
图解算法使用python笔记
步骤05:A[5]=87>A[2]=16,故交换,再与A[0]=35比较,A[2]=87>A[0]=35,故交换,如下图
图解算法使用python笔记
步骤06:A[6]=65>A[2]=35,故交换,且A[2]=65<A[0]=87,故不交换,如下图
图解算法使用python笔记
步骤07:A[7]=4<A[3]=17,故不交换,A[8]=12<A[3]=17,故不交换
范例:
使用堆积排序法来排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
def heap(data, size):
for i in range(int(size / 2), 0, -1): # 建立堆积树节点
ad_heap(data, i, size - 1)
print()
print('堆积的内容:', end='')
for i in range(1, size): # 原始堆积树的内容
print('[%2d] ' % data[i], end='')
print('\n')
for i in range(size - 2, 0, -1): # 堆积排序
data[i + 1], data[1] = data[1], data[i + 1] # 头尾节点交换
ad_heap(data, 1, i) # 处理剩余节点
print('处理过程为:', end='')
for j in range(1, size):
print('[%2d] ' % data[j], end='')
print()


def ad_heap(data, i, size):
j = 2 * i
tmp = data[i]
post = 0
while j <= size and post == 0:
if j < size:
if data[j] < data[j + 1]: # 找出最大节点
j += 1
if tmp >= data[j]: # 若树根较大,结束比较过程
post = 1
else:
data[int(j / 2)] = data[j] # 若树根较小,则继续比较
j = 2 * j
data[int(j / 2)] = tmp # 指定树根为父节点


def main():
data = [0, 5, 6, 4, 8, 3, 2, 7, 1] # 原始数组的内容
size = 9
print('原始数组为:', end='')
for i in range(1, size):
print('[%2d] ' % data[i], end='')
heap(data, size) # 建立堆积树
print('排序结果为:', end='')
for i in range(1, size):
print('[%2d] ' % data[i], end='')


main()

0x9图的数据结构及其算法

图除了被应用在数据结构中最短路径搜索,拓扑排序外,还能应用在系统分析中以时间为评审标准的性能评审技术等。采用Dijkstra这种图形算法就能快速寻找出两个节点之间的最短路径
图的遍历,可以定义如下:
一个图G=(V,E),存在某一顶点v属于V,我们希望从v开始,通过此节点相邻的节点而去访问图G中的其他节点,这就被称为”图的遍历”。也就是从某一个顶点V1开始,遍历可以经过V1到达的顶点,接着遍历下一个顶点直到全部的顶点遍历完毕为止
0x9.1图的遍历算法
图遍历的方法有两种:即”深度优先遍历”和”广度优先遍历”,也称为”深度优先搜索”和”广度优先搜索”
1.深度优先遍历的方式有点类似于前序遍历,从图的某一顶点开始遍历,被访问过的顶点就做上已访问的记号,接着遍历此顶点所有相邻且未访问过的顶点中的任意一个顶点,并做上已访问的记号,再以该点为新的起点继续进行深度优先搜索

这种图的遍历方法结合了递归和堆栈两种数据结构的技巧,由于此方法会造成无限循环,因此必须加入一个变量,判断该点是否已经遍历完毕
深度优先函数的算法如下:

1
2
3
4
5
6
7
8
def dfs(current): #深度优先函数
run[current]=1
print('[%d] ' %current, end='')
ptr=head[current].next
while ptr!=None:
if run[ptr.val]==0: #如果顶点尚未遍历,
dfs(ptr.val) #就进行dfs的递归调用
ptr=ptr.next

范例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class list_node:
def __init__(self):
self.val = 0
self.next = None


head = [list_node()] * 9 # 声明一个节点类型的链表数组

run = [0] * 9


def dfs(current): # 深度优先函数
run[current] = 1
print('[%d] ' % current, end='')
ptr = head[current].next
while ptr != None:
if run[ptr.val] == 0: # 如果顶点尚未遍历,
dfs(ptr.val) # 就进行dfs的递归调用
ptr = ptr.next


# 声明图的边线数组
data = [[1, 2], [2, 1], [1, 3], [3, 1], \
[2, 4], [4, 2], [2, 5], [5, 2], \
[3, 6], [6, 3], [3, 7], [7, 3], \
[4, 8], [8, 4], [5, 8], [8, 5], \
[6, 8], [8, 6], [8, 7], [7, 8]]
for i in range(1, 9): # 共有八个顶点
run[i] = 0 # 把所有顶点设置成尚未遍历过
head[i] = list_node()
head[i].val = i # 设置各个链表头的初值
head[i].next = None
ptr = head[i] # 设置指针指向链表头
for j in range(20): # 二十条边线
if data[j][0] == i: # 如果起点和链表头相等,则把顶点加入链表
newnode = list_node()
newnode.val = data[j][1]
newnode.next = None
while True:
ptr.next = newnode # 加入新节点
ptr = ptr.next
if ptr.next == None:
break

print('图的邻接表内容:') # 打印图的邻接表内容
for i in range(1, 9):
ptr = head[i]
print('顶点 %d=> ' % i, end='')
ptr = ptr.next
while ptr != None:
print('[%d] ' % ptr.val, end='')
ptr = ptr.next
print()
print('深度优先遍历的顶点:') # 打印深度优先遍历的顶点
dfs(1)
print()

2.广度优先遍历法
广度优先(Breadth-FIrst Search,BFS)遍历法则是使用队列和递归技巧来遍历,也是从图的某一顶点开始遍历,被访问过的顶点就做上已访问的记号。接着遍历此顶点的所有相邻且未访问过的顶点中的任意一个顶点,并做上已访问的记号,再以该点为新的起点继续进行广度优先的遍历
广度优先函数的python函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#广度优先查找法
def bfs(current):
global front
global rear
global Head
global run
enqueue(current) #将第一个顶点存入队列
run[current]=1 #将遍历过的顶点设置为1
print('[%d]' %current, end='') #打印出该遍历过的顶点
while front!=rear: #判断当前的队伍是否为空
current=dequeue() #将顶点从队列中取出
tempnode=Head[current].first #先记录当前顶点的位置
while tempnode!=None:
if run[tempnode.x]==0:
enqueue(tempnode.x)
run[tempnode.x]=1 #记录已遍历过
print('[%d]' %tempnode.x,end='')
tempnode=tempnode.next

范例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
MAXSIZE=10  #定义队列的最大容量	

front=-1 #指向队列的前端
rear=-1 #指向队列的末尾

class Node:
def __init__(self,x):
self.x=x #顶点数据
self.next=None #指向下一个顶点的指针

class GraphLink:
def __init__(self):
self.first=None
self.last=None

def my_print(self):
current=self.first
while current!=None:
print('[%d]' %current.x,end='')
current=current.next
print()

def insert(self,x):
newNode=Node(x)
if self.first==None:
self.first=newNode
self.last=newNode
else:
self.last.next=newNode
self.last=newNode

#队列数据的存入
def enqueue(value):
global MAXSIZE
global rear
global queue
if rear>=MAXSIZE:
return
rear+=1
queue[rear]=value


#队列数据的取出
def dequeue():
global front
global queue
if front==rear:
return -1
front+=1
return queue[front]

#广度优先查找法
def bfs(current):
global front
global rear
global Head
global run
enqueue(current) #将第一个顶点存入队列
run[current]=1 #将遍历过的顶点设置为1
print('[%d]' %current, end='') #打印出该遍历过的顶点
while front!=rear: #判断当前的队伍是否为空
current=dequeue() #将顶点从队列中取出
tempnode=Head[current].first #先记录当前顶点的位置
while tempnode!=None:
if run[tempnode.x]==0:
enqueue(tempnode.x)
run[tempnode.x]=1 #记录已遍历过
print('[%d]' %tempnode.x,end='')
tempnode=tempnode.next

#声明图的边线数组
Data=[[0]*2 for row in range(20)]

Data =[[1,2],[2,1],[1,3],[3,1],[2,4], \
[4,2],[2,5],[5,2],[3,6],[6,3], \
[3,7],[7,3],[4,5],[5,4],[6,7],[7,6],[5,8],[8,5],[6,8],[8,6]]

run=[0]*9 #用来记录各顶点是否遍历过
queue=[0]*MAXSIZE
Head=[GraphLink]*9

print('图的邻接表内容:') #打印图的邻接表内容
for i in range(1,9): #共有8个顶点
run[i]=0 #把所有顶点设置成尚未遍历过
print('顶点%d=>' %i,end='')
Head[i]=GraphLink()
for j in range(20):
if Data[j][0]==i: #如果起点和链表头相等,则把顶点加入链表
DataNum = Data[j][1]
Head[i].insert(DataNum)
Head[i].my_print() #打印图的邻接标内容

print('广度优先遍历的顶点:') #打印广度优先遍历的顶点
bfs(1)
print()

后面
0x9.2最小生成树
生成树又称”花费树”,“出本树”或”值树”,一个图的生成树(spanning tree)就是以最少的边来连通图中所有的顶点,且不造成回路(cycle)的树形结构。假设在树的边加上一个权重(weight)值,这种图就成为”加权图(weighted graph)”。如果这个权重值代表两个顶点间的距离(distance)或成本(cost),这类图就被称为网络(network)
介绍以所谓”贪婪法则”(Greedy Rule)为基础来求得一个无向连通图的最小生成树的常见问题,分别是Prim算法和Kruskal算法
0x9.3 图的最短路径法
图的这章可详细看:https://blog.csdn.net/V_lq6h/article/details/86743787
参考书本:
图解算法——使用Python http://m.bookdao.com/book.aspx?bookid=3346564 数据结构–python 第八章 排序https://blog.csdn.net/Jasminexjf/article/details/89379735
查找与哈希算法 https://blog.csdn.net/V_lq6h/article/details/86743773
数组与链表算法:https://www.cnblogs.com/LQ6H/p/10346666.html
堆栈https://blog.csdn.net/jasminexjf/article/details/89295924
python算法 https://www.cnblogs.com/LQ6H/default.html?page=5
图的数据结构及其算法 https://blog.csdn.net/V_lq6h/article/details/86743787

FROM :blog.cfyqy.com | Author:cfyqy

特别标注: 本站(CN-SEC.COM)所有文章仅供技术研究,若将其信息做其他用途,由用户承担全部法律及连带责任,本站不承担任何法律及连带责任,请遵守中华人民共和国安全法.
  • 我的微信
  • 微信扫一扫
  • weinxin
  • 我的微信公众号
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2022年1月6日01:33:43
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                  图解算法使用python笔记 http://cn-sec.com/archives/721848.html

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: