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 ,random
 
data=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 queue
 
q=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 = key
        self.left = None
        self.right = None
 
class BinaryTree:
    def __init__(self):
        self.root = None
 
    def 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_node
        elif 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")

实现说明：

1. TreeNode类：

   • 表示二叉树中的每个节点，具有一个 key 属性存储节点的值，以及 left 和 right 属性分别指向左子节点和右子节点。

2. BinaryTree类：

   • 使用 root 属性表示树的根节点。
   • insert(key) 方法用于插入新的节点到二叉树中。
   • _insert_recursive(current_node, key) 是递归插入方法，根据节点值大小决定向左子树或右子树插入新节点。
   • search(key) 方法用于搜索特定值的节点。
   • _search_recursive(current_node, key) 是递归搜索方法，根据节点值大小在左子树或右子树中搜索目标节点。
   • inorder_traversal() 方法实现中序遍历，返回一个按升序排列的节点值列表。
   • _inorder_recursive(current_node) 是递归实现的中序遍历方法。

3. 使用示例：

   • 创建一个二叉搜索树（BST），插入一些节点并进行搜索和遍历操作。
   • 输出示例展示了中序遍历的结果，以及如何搜索特定的节点。

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

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

初始调用

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

1. 调用 _inorder_recursive(5)

   • current_node 是 5。
   • result 初始化为空列表 []。

2. 处理左子树 _inorder_recursive(3)

   • current_node 是 3。
   • 调用 _inorder_recursive(3)。

3. 处理左子树 _inorder_recursive(2)

   • current_node 是 2。
   • 调用 _inorder_recursive(2)。

4. 返回空列表 [2] 到 _inorder_recursive(3)

   • 现在 result 是 [2]。
   • 添加 3，返回 [2, 3] 到 _inorder_recursive(5)。

5. 处理根节点 5

   • 现在 result 是 [2, 3]。
   • 添加 5，成为 [2, 3, 5]。

6. 处理右子树 _inorder_recursive(7)

   • current_node 是 7。
   • 调用 _inorder_recursive(7)。

7. 处理左子树 _inorder_recursive(6)

   • current_node 是 6。
   • 调用 _inorder_recursive(6)。

8. 返回空列表 [6] 到 _inorder_recursive(7)

   • 现在 result 是 [6]。
   • 添加 7，返回 [6, 7] 到 _inorder_recursive(5)。

9. 处理根节点 5

   • 现在 result 是 [2, 3, 5, 6, 7]。

10. 处理右子树 8

    • current_node 是 8。
    • 调用 _inorder_recursive(8)。

11. 返回空列表 [8] 到 _inorder_recursive(7)

    • 现在 result 是 [6, 7, 8]。
    • 返回 [2, 3, 5, 6, 7, 8] 到 _inorder_recursive(5)。

12. 最终结果

    • 最终返回 [2, 3, 4, 5, 6, 7, 8]，这是二叉搜索树中序遍历的结果。

5.有向图

from collections import defaultdict
 
 
class 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()