Python中的数据结构

一.堆

堆的建立可以通过导入heapq库来实现

在Python中建立的是最小堆 即heap[k]<=heap[2*k+1]and heap[k]<=heap[2*k+2]

下面是一些堆使用的方法

heapq.heappush([],加入的元素)   
heapq.heappop(heap)弹出最小的元素  
heapq.nlargest(3,heap)返回最大的三个元素 
heapq.nsmallest(3,heap)返回最小的三个元素  
heapq.heapify(my)  #自动将列表装换成堆

例子:

import heapq ,randomdata=list(range(10))
random.shuffle(data)
print(data)
#建堆
heap=[]
for i in data:heapq.heappush(heap,i)
heapq.heappush(heap,99)#添加元素99
print(heap)print(heapq.heappop(heap))  #弹出最小的元素heapq.heapreplace(heap,3)#替换堆中最小的元素值,并自动重新建堆print(heapq.nlargest(3,heap)) #返回最大的三个元素
print(heapq.nsmallest(3,heap)) #返回最小的三个元素my=[2,0,4,3,12,15,5]
heapq.heapify(my)  #自动将列表装换成堆
print(my)

二.队列

通过导入queue模块实现

下面是一些队列使用的方法

q=queue.Queue(6) #实例化队列   
q.put(1)  #元素入队  
q.get()出队 
q.empty()判断队列是否为空
q.full()判断队列是否为满

import queueq=queue.Queue(6) #实例化队列q.put(1)  #元素入队
q.put(3)
q.put(10)print(q.full())print(q.get())

3.链表

可以通过列表来模拟.不过多讲解

4.二叉树

自己实现

class TreeNode:def __init__(self, key):self.key = keyself.left = Noneself.right = Noneclass BinaryTree:def __init__(self):self.root = Nonedef insert(self, key):if self.root is None:self.root = TreeNode(key)else:self._insert_recursive(self.root, key)def _insert_recursive(self, current_node, key):if key < current_node.key:if current_node.left is None:current_node.left = TreeNode(key)else:self._insert_recursive(current_node.left, key)else:if current_node.right is None:current_node.right = TreeNode(key)else:self._insert_recursive(current_node.right, key)def search(self, key):return self._search_recursive(self.root, key)def _search_recursive(self, current_node, key):if current_node is None or current_node.key == key:return current_nodeelif key < current_node.key:return self._search_recursive(current_node.left, key)else:return self._search_recursive(current_node.right, key)def inorder_traversal(self):return self._inorder_recursive(self.root)def _inorder_recursive(self, current_node):result = []if current_node:result.extend(self._inorder_recursive(current_node.left))result.append(current_node.key)result.extend(self._inorder_recursive(current_node.right))return result# 使用示例
tree = BinaryTree()
tree.insert(5)
tree.insert(3)
tree.insert(7)
tree.insert(2)
tree.insert(4)
tree.insert(6)
tree.insert(8)print(tree.inorder_traversal())  # 输出：[2, 3, 4, 5, 6, 7, 8]# 搜索示例
result = tree.search(4)
if result:print(f"Key 4 found: {result.key}")
else:print("Key 4 not found")

实现说明：

TreeNode类：
- 表示二叉树中的每个节点，具有一个 key 属性存储节点的值，以及 left 和 right 属性分别指向左子节点和右子节点。
BinaryTree类：
- 使用 root 属性表示树的根节点。
- insert(key) 方法用于插入新的节点到二叉树中。
- _insert_recursive(current_node, key) 是递归插入方法，根据节点值大小决定向左子树或右子树插入新节点。
- search(key) 方法用于搜索特定值的节点。
- _search_recursive(current_node, key) 是递归搜索方法，根据节点值大小在左子树或右子树中搜索目标节点。
- inorder_traversal() 方法实现中序遍历，返回一个按升序排列的节点值列表。
- _inorder_recursive(current_node) 是递归实现的中序遍历方法。
使用示例：
- 创建一个二叉搜索树（BST），插入一些节点并进行搜索和遍历操作。
- 输出示例展示了中序遍历的结果，以及如何搜索特定的节点。

这是一个基本的二叉树实现，可以根据需要扩展添加其他操作如删除节点、前序遍历、后序遍历等。

当我们对一个简单的二叉搜索树进行中序遍历时，可以通过以下步骤演示 _inorder_recursive() 方法的执行过程

初始调用

首先，我们从根节点 5 开始调用 _inorder_recursive() 方法：

调用 _inorder_recursive(5)
- current_node 是 5。
- result 初始化为空列表 []。
处理左子树 _inorder_recursive(3)
- current_node 是 3。
- 调用 _inorder_recursive(3)。
处理左子树 _inorder_recursive(2)
- current_node 是 2。
- 调用 _inorder_recursive(2)。
返回空列表 [2] 到 _inorder_recursive(3)
- 现在 result 是 [2]。
- 添加 3，返回 [2, 3] 到 _inorder_recursive(5)。
处理根节点 5
- 现在 result 是 [2, 3]。
- 添加 5，成为 [2, 3, 5]。
处理右子树 _inorder_recursive(7)
- current_node 是 7。
- 调用 _inorder_recursive(7)。
处理左子树 _inorder_recursive(6)
- current_node 是 6。
- 调用 _inorder_recursive(6)。
返回空列表 [6] 到 _inorder_recursive(7)
- 现在 result 是 [6]。
- 添加 7，返回 [6, 7] 到 _inorder_recursive(5)。
处理根节点 5
- 现在 result 是 [2, 3, 5, 6, 7]。
处理右子树 8
- current_node 是 8。
- 调用 _inorder_recursive(8)。
返回空列表 [8] 到 _inorder_recursive(7)
- 现在 result 是 [6, 7, 8]。
- 返回 [2, 3, 5, 6, 7, 8] 到 _inorder_recursive(5)。
最终结果
- 最终返回 [2, 3, 4, 5, 6, 7, 8]，这是二叉搜索树中序遍历的结果。

5.有向图

from collections import defaultdictclass WeightedGraph:def __init__(self):self.graph = defaultdict(list)def add_edge(self, u, v, weight):self.graph[u].append((v, weight))# Uncomment below for undirected graph# self.graph[v].append((u, weight))def print_graph(self):for node in self.graph:print(f"{node} -> {self.graph[node]}")# 创建一个新的带权图实例
graph = WeightedGraph()# 添加带权边
graph.add_edge(0, 1, 4)
graph.add_edge(0, 2, 2)
graph.add_edge(1, 3, 1)
graph.add_edge(2, 3, 3)# 打印邻接表表示的带权图
graph.print_graph()