Python算法——使用算法解决数据结构问题
Python数据结构与算法实战：从基础到应用的代码解析
在Python编程学习中，数据结构和算法是进阶的必经之路。今天，我将通过几个实际的数据结构实现案例，带大家深入理解这些基础但重要的概念。
一、大整数加法：链表思维的数组实现
import time
L1="111111111111111111"
L2="222222222222222222"
startTime=time.time()
# 长度强行扭转到一致 不够前面补0
max_len= len(L1) if len(L1)>len(L2) else len(L2)
l1=L1.zfill(max_len)
l2=L2.zfill(max_len)
a1=list(l1)
a2=list(l2)
# 长度一致 每个对应的位置的相加的和 %10 前一位补1 如果>10 否则0 99+99最大3位所以多一位
a3=[0]*(max_len+1)
for index in range(max_len-1,-1,-1):
index_sum=a3[index+1]+int(a1[index])+int(a2[index])
less=index_sum-10
a3[index+1]=index_sum%10
a3[index]=1 if less>=0 else 0
if(a3[0]==0):
a3.pop(0)
a33=[str(i) for i in a3]
print(''.join(a33))
print('耗时{0}ms'.format(time.time()-startTime))
算法解析： 这个代码模拟了竖式加法的过程，从最低位开始逐位相加，处理进位。虽然处理的是字符串表示的数字，但思路可以扩展到链表表示的大整数加法。时间复杂度O(n)，空间复杂度O(n)。
二、约瑟夫环问题：循环链表的经典应用
class Node():
def __init__(self,value,next=None):
self.value=value
self.next=next
def createLink(n):
if n<=0:
return False
if n==1:
return Node(1)
else:
root=Node(1)
tmp=root
for i in range(2,n+1):
tmp.next=Node(i)
tmp=tmp.next
tmp.next=root
return root
def josephus(n,k):
if k==1:
print('幸存者:',n)
return
root=createLink(n)
tmp=root
while True:
for i in range(k-2):
tmp=tmp.next
print('杀掉:',tmp.next.value)
tmp.next=tmp.next.next
tmp=tmp.next
if tmp.next==tmp:
break
print('survive:',tmp.value)
算法解析： 约瑟夫环问题完美展示了循环链表的价值。每次数到k的人出局，通过链表删除操作模拟这个过程。时间复杂度O(n*k)，但通过数学优化可以达到O(n)。
三、二叉树的遍历：广度优先与深度优先
class Node:
def __init__(self, data, left, right):
self._data = data
self._left = left
self._right = right
def breadth_tree(tree):
lst = []
def traverse(node, p):
if node._left is not None:
lst.append(node._left)
if node._right is not None:
lst.append(node._right)
if p > (len(lst) -2):
return
else:
traverse(lst[p+1], p+1)
lst.append(tree._root)
traverse(tree._root, 0)
for node in lst:
print(node._data)
def depth_tree(tree):
lst = []
lst.append(tree._root)
while len(lst) > 0:
node = lst.pop()
print(node._data)
if node._right is not None:
lst.append(node._right)
if node._left is not None:
lst.append(node._left)
算法解析：
- 广度优先(BFS)：使用队列思想，逐层访问节点
- 深度优先(DFS)：使用栈思想，先访问子节点再回溯
两种遍历方式各有应用场景：BFS适合寻找最短路径，DFS适合深度搜索和回溯问题。
四、图的邻接矩阵表示与DFS遍历
class Graph_Matrix:
def __init__(self, vertices=[], matrix=[]):
self.matrix = matrix
self.vertices = vertices
self.num_vertices = len(self.matrix)
def DepthFirstSearch(self):
def DFS(self, i, queue):
queue.append(i)
self.to_do_vertex(i)
visited[i] = 1
if len(queue) != 0:
w = queue.pop()
for k in range(self.num_vertices):
if self.matrix[w][k] is 1 and visited[k] is 0:
self.to_do_edge(w, k)
DFS(self, k, queue)
visited = [0] * self.num_vertices
queue = []
for i in range(self.num_vertices):
if visited[i] is 0:
DFS(self, i, queue)
算法解析： 图的DFS与树的DFS原理相似，但需要处理环路和未访问节点的检测。visited数组确保每个节点只访问一次。
五、AVL平衡二叉树：自平衡的二叉搜索树
class AVLTree(object):
def singleLeftRotate(self, node):
k1 = node.left
node.left = k1.right
k1.right = node
node.height = max(self.height(node.right), self.height(node.left)) + 1
k1.height = max(self.height(k1.left), node.height) + 1
return k1
def put(self, key):
if not self.root:
self.root = Node(key)
else:
self.root = self._put(key, self.root)
def _put(self, key, node):
if node is None:
node = Node(key)
elif key < node.key:
node.left = self._put(key, node.left)
if (self.height(node.left) - self.height(node.right)) == 2:
if key < node.left.key:
node = self.singleLeftRotate(node)
else:
node = self.doubleLeftRotate(node)
elif key > node.key:
node.right = self._put(key, node.right)
if (self.height(node.right) - self.height(node.left)) == 2:
if key < node.right.key:
node = self.doubleRightRotate(node)
else:
node = self.singleRightRotate(node)
node.height = max(self.height(node.right), self.height(node.left)) + 1
return node
算法解析： AVL树通过四种旋转操作（LL、RR、LR、RL）保持平衡，确保任何节点的左右子树高度差不超过1。插入和删除后的平衡调整保证了O(log n)的查找效率。
六、树中两节点的最短路径
def deep_first_search(cur,val,path=[]):
path.append(cur.value)
if cur.value == val:
return path
if cur.child_list == []:
return 'no'
for node in cur.child_list:
t_path = copy.deepcopy(path)
res = deep_first_search(node,val,t_path)
if res == 'no':
continue
else:
return res
return 'no'
def get_shortest_path(start,end):
path1 = deep_first_search(root, start, [])
path2 = deep_first_search(root, end, [])
# 对两个路径 从尾巴开始向头 找到最近的公共根节点
len1,len2 = len(path1),len(path2)
for i in range(len1-1,-1,-1):
if path1[i] in path2:
index = path2.index(path1[i])
path2 = path2[index:]
path1 = path1[-1:i:-1]
break
res = path1+path2
return '->'.join(res)
算法解析： 这个算法先分别找到根节点到两个目标节点的路径，然后找到最近的公共祖先，合并两条路径得到最短路径。时间复杂度O(n)。
七、队列的多种实现：链表与循环数组
# 链表实现队列
class LQueue(object):
def enqueue(self, elem):
p = Node(elem)
if self.is_empty():
self._head = p
self._rear = p
else:
self._rear.next = p
self._rear =p
def dequeue(self):
if self.is_empty():
raise QueueUnderflow
result = self._head.elem
self._head = self._head.next
return result
# 循环顺序表实现队列
class SQueue(object):
def enqueue(self, elem):
if self._num == self._len:
self.__extand()
self._elems[(self._head + self._num) % self._len] = elem
self._num += 1
def dequeue(self):
if self.is_empty():
raise QueueUnderflow
result = self._elems[self._head]
self._head = (self._head + 1) % self._len
self._num -= 1
return result
算法解析：
- 链表队列：入队O(1)，出队O(1)，但节点开销大
- 循环数组队列：入队O(1)均摊，出队O(1)，空间利用率高
八、单链表的完整实现
class LList(object):
# 表首端插入元素
def prepend(self, elem):
self._head = LNode(elem, self._head)
self._num += 1
# 表末端插入元素
def append(self, elem):
if self._head is None:
self._head = LNode(elem)
else:
p = self._head
while p.next:
p = p.next
p.next = LNode(elem)
self._num += 1
# 删除第一个出现的elem
def remove(self, elem):
p = self._head
pre = None
while p:
if p.elem == elem:
if not pre:
self._head = p.next
else:
pre.next = p.next
break
else:
pre = p
p = p.next
self._num -= 1
# 运算符重载：支持索引访问
def __getitem__(self, key):
if not isinstance(key, int):
raise TypeError
if 0<=key<len(self):
p = self._head
num = -1
while p:
num += 1
if key == num:
return p.elem
p = p.next
else:
raise IndexError
算法解析： 这是一个功能完备的单链表实现，包括增删改查和运算符重载。特别注意各种边界情况的处理：空表、首节点、尾节点。
九、双向链表
class LinkedList():
def __init__(self, value=None):
self.value = value
self.before = None # 前驱
self.behind = None # 后继
def insert(linked_list, index, node):
node = LinkedList(node)
i = 0
while linked_list.behind is not None:
if i == index:
break
i += 1
linked_list = linked_list.behind
if linked_list.behind is not None:
node.behind = linked_list.behind
linked_list.behind.before = node
node.before, linked_list.behind = linked_list, node
def remove(linked_list, index):
i = 0
while linked_list.behind is not None:
if i == index:
break
i += 1
linked_list = linked_list.behind
if linked_list.behind is not None:
linked_list.behind.before = linked_list.before
if linked_list.before is not None:
linked_list.before.behind = linked_list.behind
算法解析： 双向链表每个节点有前驱和后继指针，插入删除操作需要同时更新两个方向的指针，比单链表稍微复杂但操作更灵活。
十、顺序表（数组）实现
class SeqList(object):
def __init__(self,max=10):
self.max = max
self.num = 0
self.date = [None] * self.max
# 表任意位置插入操作：
def insert(self,i,value):
if not isinstance(i,int):
raise TypeError
if i < 0 and i > self.num:
raise IndexError
for j in range(self.num,i,-1):
self.date[j] = self.date[j-1]
self.date[i] = value
self.num += 1
# 删除某一位置的操作
def remove(self,i):
if not isinstance(i,int):
raise TypeError
if i < 0 and i >=self.num:
raise IndexError
for j in range(i,self.num):
self.date[j] = self.date[j+1]
self.num -= 1
算法解析： 顺序表用连续内存存储，随机访问O(1)，但插入删除需要移动元素O(n)。适合频繁查找、较少插入删除的场景。
总结
通过以上十个数据结构实现案例，我们可以看出：
- 链表适合频繁插入删除，但查找慢
- 数组/顺序表适合频繁访问，但插入删除开销大
- 树结构在层次关系数据处理中表现出色
- 图结构能表达复杂的多对多关系
- 队列/栈在特定顺序处理中不可或缺
阅读建议
评论
匿名评论
隐私政策
你无需删除空行，直接评论以获取最佳展示效果
最新评论
A /
肖松 /
xx /