python 算法-二叉搜索树
文章目录
python 算法-二叉搜索树
1、实现
2、二叉搜索树-Coding

1、实现
2、二叉搜索树-Coding

算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。算法是Python开发中重要知识技能，不可避免的要使用到该技能，那么，Python算法有什么特点呢？
一个Python算法应该具有以下七个重要的特征：
1. 有穷性（Finiteness）：算法的有穷性是指算法必须能在执行有限个步骤之后终止；
2. 确切性(Definiteness)：算法的每一步骤必须有确切的定义；
3. 输入项(Input)：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输    入是指算法本身定出了初始条件；
4. 输出项(Output)：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没       有输出的算法是毫无意义的；
5. 可行性(Effectiveness)：算法中执行的任何计算步骤都是可以被分解为基本的可执行       的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）；
6. 高效性(High efficiency)：执行速度快，占用资源少；
7. 健壮性(Robustness)：对数据响应正确。
Python算法除了具有以上特征，还和时间和空间有关系，不同的算法可能用不同的时间、空间或效率来完成同样的任务，因此，一个Python算法的优劣可以用空间复杂度与时间复杂度来衡量。

Python算法分析与设计：最大流算法
一、实验目的

1、掌握最大流问题的定义，了解流量、容量以及他们之间的关系。

2、掌握通过增广路径求最大流问题的Forder-Fulkerson和Edmond-Karp算法，理解这两个算法之间的异同

3、了解将计算问题转换为最大流问题的基本流程。掌握通过最大流算法求解二向图最大匹配和文件传输中的不重合边等问题的方法。
二、实验工具

Win10操作系统、python3.7编译环境、IDLE编译器
三、实验内容

已知一个容量（流量）网络，要求应用Edmond-Karp算法，求出该容量网络的最大流，容量网络各边的容量值可以由用户设置。
四、实验调试过程

实验代码如下所示：
# -*- encoding:gbk -*-
from queue import Queue

#n #边的个数
m = 6#点的个数

residual = [[0 for i in range(m)] for j in range(m)]
#残余图的剩余流量
maxflowgraph = [[0 for i in range(m)] for j in range(m)]
#记录最大流图，初始都为0
flow = [0 for i in range(m)]
#记录增广路径前进过程记录的最小流量
pre = [float('inf') for i in range(m)]
#记录增广路径每个节点的前驱
q = Queue()
#队列，用于BFS地寻找增广路径

#设置初始图的流量走向
residual[0][1]=3
residual[0][2]=2
residual[1][2]=1
residual[1][3]=3
residual[1][4]=4
residual[2][4]=2
residual[3][5]=2
residual[4][5]=3

def BFS(source,sink):
    q.empty()#清空队列

    for i in range(m):
        pre[i] = float('inf')

    flow[source] = float('inf')#这里要是不改，那么找到的路径的流量永远是0
    #不用将flow的其他清零
    q.put(source)
    while(not q.empty()):
        index = q.get()
        if(index == sink):
            break
        for i in range(m):
            if( (i!=source) & (residual[index][i]>0) & (pre[i]==float('inf')) ):
                #i!=source，从source到source不用分析了
                #residual[index][i]>0，边上有流量可以走
                #pre[i]==float('inf')，代表BFS还没有延伸到这个点上
                pre[i] = index
                flow[i] = min(flow[index],residual[index][i]) 
                q.put(i)
    if(pre[sink] == float('inf')):
        #汇点的前驱还是初始值，说明已无增广路径
        return -1
    else:
        return flow[sink]

def maxflow(source,sink):
    sumflow = 0#记录最大流，一直累加
    augmentflow = 0#当前寻找到的增广路径的最小通过流量
    while(True):
        augmentflow = BFS(source,sink)
        if(augmentflow == -1):
            break#返回-1说明已没有增广路径
        k = sink
        while(k!=source):#k回溯到起点，停止
            prev = pre[k]#走的方向是从prev到k
            maxflowgraph[prev][k] += augmentflow
            residual[prev][k] -= augmentflow#前进方向消耗掉了
            residual[k][prev] += augmentflow#反向边
            k = prev
        sumflow += augmentflow
    return sumflow

result = maxflow(0,m-1)    
print(result)
print(maxflowgraph)#最大流图

五、实验结果分析

python算法-双指针问题
一、数组合并
1. 使用模拟指针和并两个有序数组
2.模拟指针说明：
二、二分法（折半查找法）
1.有序数组的二分法查找
2. 二分法说明
三、链表（双链表和单链表区别）

一、数组合并
1. 使用模拟指针和并两个有序数组
# 使用指针合并两个数组
arr1 = [1,3,4,6,7] 
arr2 = [2,5,8,9,10]
#定义两个有序数组，并初始化赋值
ind = 0
# ans比较时的角标
ans = arr1.copy()
#ans 排序结果初始化为arr1

for i in range(0,len(arr2)):
	while ind < len(arr1):
		if arr2[i]<= arr1[ind]: #范围小于数组的元素下标的最大值
			ans.insert(ind + i ,arr2[i]) #向第一非数组中插入第二个数组中的数字
			break #跳出当前循环
		else:
			ind +=1  #ind指向的数字小于i指向的数字，ind向后移动一位

	else:
		ans =ans +arr2[i:] #ans加上arr2中剩余的元素
		break
print(ans,type(ans))
#输出结果： [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] <class 'list'>

2.模拟指针说明：
- 指针：内存空间变量，可以通过一个数组中的没个元素的下标找出它的值，
即存储这个元素位置的变量可以看作一个指针，即python中模拟指针问题
- 实例中 ind是存储数组中数值的下角标的变量，ans用于存储排序完成后数组中的变量
- 使用for循环是因为同一个数字前面可能插入两个及以上的数字，
- python中的数组和列表时一个概念，我们这里不区分，

二、二分法（折半查找法）
1.有序数组的二分法查找
# 有序数组的二分法查找
number = [1,2,3,4,5,6,7,8,9,10,11,12]
#初始化定义一个数组
head = 0  #定义指针头
tail =len(number) #定义指针的尾
#数组的长度是最大下标数加1
search = int(input('请输入要搜索的数字：'))
while  tail - head >1:
	mid = (head + tail ) // 2  #通过整除，找出中间角标 
	if search < number[mid]:
		tail =mid
	if  search > number[mid]:
		head= mid 
	if search == number[mid]:
		ans =mid 
		break
else :
	if search == number[head-1]:
		ans = head
	else :
		ans = -1 	#数组不存在搜索的数字
if ans == -1:
	print(search,'不在数组中')
else:
	print(search,'在数组中的索引位置为：',ans)	



2. 二分法说明
二分法又叫折半查找法，每次查找后，查找范围都折半，这样查找到最后，查找范围只剩一个数字时判断是否是查找的数字，如果是记录位置，如果不是，则要查找的数字不在这个数组中，
三、链表（双链表和单链表区别）
链表：是用指针连接的用于存储数据的数组，它最大的优点是在于可以有效地利用零碎的内存空间。在很多语言中，数组的大小要提前定义，定义后不能随便更改，而数组中只能存储同一类型的变量。如果使用了链表，则可以改变数组长度，并且可以在同一数组中存储不同类型的元素。

这和python的列表很像，实际上列表的工作原理就是链表，于是Python语言没有指针，我们使用么你指针的办法实现链表。

单链表：链表的每个元素不仅仅存储各个元素的值。还要存储这个元素的指针值。这样链表才能被连接起来。单链表的每个元素包含本身值和一个指向下一个数的指针，因为链表的最后一个数没有。下一个数，所以它的指针为空。



双链表：双链表中的元素由两个指针和元素值组成，一个指针指向下一个元素，一个指针上一个元素双链表可以双向遍历，无论遍历到第几个数都可以通过索引返回。我们也可以实现双向输出，



注意:指针是存储下一个元素位置的变量，

python中没有指针，链表我们不使用python模拟，这里我们了解单链表和双链表的区别就可以了，这里我们主要介绍概念性东西，让我们整个算法知识体系完整。