【Python】进阶 - 数据结构与算法

arr = [10, 20, 30, 40, 50]
print(arr[2])  # 直接访问索引为 2 的元素

count = 0
i = 1
while i<100:
    i *= 2
    count += 1
    
print(count)    # 7 （2的7次方大于100）

n = 100    # 这里 n 不是固定值，可以换成任意数
i = 0
while i < n:
    i += 1

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

# 测试
arr = [38, 27, 43, 3, 9, 82, 10]
print(quick_sort(arr))  # 输出: [3, 9, 10, 27, 38, 43, 82]

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

# 测试
arr = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(arr))  # 输出: [11, 12, 22, 25, 34, 64, 90]

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   │   ├── fib(1) = 1
│   │   │   └── fib(0) = 0
│   │   └── fib(1) = 1
│   └── fib(2)
│       ├── fib(1) = 1
│       └── fib(0) = 0
└── fib(3)
    ├── fib(2)
    │   ├── fib(1) = 1
    │   └── fib(0) = 0
    └── fib(1) = 1

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

# 测试
print(fib(5))  # 输出: 5
print(fib(10)) # 输出: 55

def swap(a, b):
    a, b = b, a
    return a, b

def create_array(n):
    return [0] * n

def create_2d_table(n):
# 下划线 _ 只是一个约定俗成的写法，表示这个循环变量在后续代码中不会被使用。
    return [[0] * n for _ in range(n)]    

print(create_2d_table(3))   # [[0, 0, 0], [0, 0, 0], [0, 0, 0]]

def hanoi(n, source, target, auxiliary):
    """
    汉诺塔游戏规则：使用三根柱子，将叠放的圆盘从一根柱子移动到另一根柱子，每次只能移动一个圆盘，且小圆盘不能放在大圆盘下方。
    :param n:         当前要移动的圆盘数量
    :param source:    当前圆盘所在的柱子
    :param target:    希望把圆盘移动到的目标柱子
    :param auxiliary: 辅助用的第三根柱
    :return:
    """
    if n == 1:
        print(f"Move disk from {source} to {target}")
        return
    hanoi(n - 1, source, auxiliary, target)
    print(f"Move disk from {source} to {target}")
    hanoi(n - 1, auxiliary, target, source)

arr = [1, 2, 3, 'a', True]  # 创建列表
arr.append(4)               # 添加元素
print(arr[0])               # 访问元素

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# 创建链表
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)

# 遍历
current = head
while current:
    print(current.data)
    current = current.next

class Node:
    """节点类：表示双向链表中的一个节点"""
    def __init__(self, data):
        self.data = data      # 节点存储的数据
        self.prev = None      # 指向前一个节点的指针
        self.next = None      # 指向下一个节点的指针


class DoublyLinkedList:
    """双向链表类：支持头尾插入、删除指定值节点以及正反向遍历"""
    def __init__(self):
        self.head = None      # 链表的头节点指针
        self.tail = None      # 链表的尾节点指针

    def append(self, data):
        """在链表尾部插入一个新节点"""
        new_node = Node(data)  # 创建新节点
        if self.head is None:  # 如果链表为空
            self.head = new_node
            self.tail = new_node
        else:
            new_node.prev = self.tail  # 新节点前驱指向当前尾节点
            self.tail.next = new_node  # 当前尾节点后继指向新节点
            self.tail = new_node       # 更新尾节点为新节点

    def prepend(self, data):
        """在链表头部插入一个新节点"""
        new_node = Node(data)  # 创建新节点
        if self.head is None:  # 如果链表为空
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head  # 新节点后继指向当前头节点
            self.head.prev = new_node  # 当前头节点前驱指向新节点
            self.head = new_node       # 更新头节点为新节点

    def delete(self, data):
        """删除第一个匹配指定数据的节点（若存在）"""
        current = self.head
        while current:
            if current.data == data:  # 找到要删除的节点
                if current.prev:
                    current.prev.next = current.next  # 前驱节点连接后继节点
                else:
                    self.head = current.next  # 如果是头节点，更新头指针
                if current.next:
                    current.next.prev = current.prev  # 后继节点连接前驱节点
                else:
                    self.tail = current.prev  # 如果是尾节点，更新尾指针
                return
            current = current.next  # 继续遍历下一个节点

    def traverse_forward(self):
        """从头到尾遍历链表并打印节点数据"""
        current = self.head
        while current:
            print(current.data, end=" ")  # 打印当前节点数据
            current = current.next        # 移动到下一个节点
        print()

    def traverse_backward(self):
        """从尾到头遍历链表并打印节点数据"""
        current = self.tail
        while current:
            print(current.data, end=" ")  # 打印当前节点数据
            current = current.prev        # 移动到前一个节点
        print()

# 测试双向链表
dll = DoublyLinkedList()
dll.append(10)
dll.append(20)
dll.prepend(5)
print("正向遍历:")
dll.traverse_forward()  # 输出: 5 10 20
print("反向遍历:")
dll.traverse_backward()  # 输出: 20 10 5

dll.delete(10)
print("删除后正向遍历:")
dll.traverse_forward()  # 输出: 5 20

stack = []
stack.append(1)  # push
stack.append(2)
print(stack.pop())  # pop -> 2

from collections import deque
q = deque()
q.append(1)
q.append(2)
print(q.popleft())  # 出队 -> 1

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.middle = None
        self.right = None

# 构建树
def build_tree():
    # 创建节点
    A = TreeNode('A')
    B = TreeNode('B')
    C = TreeNode('C')
    D = TreeNode('D')
    F = TreeNode('F')
    G = TreeNode('G')
    H = TreeNode('H')
    I = TreeNode('I')
    J = TreeNode('J')
    K = TreeNode('K')
    L = TreeNode('L')
    M = TreeNode('M')

    # 构建树结构
    A.left = B
    A.middle = C
    A.right = D
    B.left = F
    B.right = G
    G.left = L
    C.left = H
    D.left = I
    D.middle = J
    D.right = K
    I.left = M

    return A

# 前序遍历
def preorder_traversal(node):
    if node:
        print(node.val, end=' ')
        preorder_traversal(node.left)
        preorder_traversal(node.middle)
        preorder_traversal(node.right)

# 中序遍历
def inorder_traversal(node):
    if node:
        inorder_traversal(node.left)
        print(node.val, end=' ')
        inorder_traversal(node.middle)
        inorder_traversal(node.right)

# 后序遍历
def postorder_traversal(node):
    if node:
        postorder_traversal(node.left)
        postorder_traversal(node.middle)
        postorder_traversal(node.right)
        print(node.val, end=' ')

# 使用
root = build_tree()

print("Pre-order traversal:")
preorder_traversal(root)
print("\nIn-order traversal:")
inorder_traversal(root)
print("\nPost-order traversal:")
postorder_traversal(root)

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# 创建二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

# 前序遍历
def preorder_traversal(node):
    if node:
        print(node.value, end=' ')
        preorder_traversal(node.left)
        preorder_traversal(node.right)

print("前序遍历:")
preorder_traversal(root)  # 输出: 1 2 4 5 3

class BSTNode:
    # 定义二叉搜索树节点类
    def __init__(self, value):
        self.value = value  # 节点值
        self.left = None    # 指向左子节点
        self.right = None   # 指向右子节点

class BinarySearchTree:
    # 定义二叉搜索树类
    def __init__(self):
        self.root = None  # 初始化根节点为空
    
    # 插入新值到二叉搜索树中
    def insert(self, value):
        if not self.root:  # 如果树为空，则创建根节点
            self.root = BSTNode(value)
        else:
            self._insert_recursive(self.root, value)  # 否则，使用递归方法插入
    
    # 递归实现插入操作
    def _insert_recursive(self, node, value):
        if value < node.value:  # 如果新值小于当前节点值
            if node.left is None:  # 若左子节点为空，则插入为左子节点
                node.left = BSTNode(value)
            else:
                self._insert_recursive(node.left, value)  # 否则，继续在左子树中查找位置
        else:  # 如果新值大于或等于当前节点值
            if node.right is None:  # 若右子节点为空，则插入为右子节点
                node.right = BSTNode(value)
            else:
                self._insert_recursive(node.right, value)  # 否则，继续在右子树中查找位置
    
    # 在二叉搜索树中搜索指定值
    def search(self, value):
        return self._search_recursive(self.root, value)  # 使用递归方法进行搜索
    
    # 递归实现搜索操作
    def _search_recursive(self, node, value):
        if node is None or node.value == value:  # 如果节点为空或找到了目标值，则返回该节点
            return node
        if value < node.value:  # 如果目标值小于当前节点值，则在左子树中继续搜索
            return self._search_recursive(node.left, value)
        return self._search_recursive(node.right, value)  # 否则，在右子树中继续搜索

# 使用示例
bst = BinarySearchTree()  # 创建一个二叉搜索树实例
bst.insert(50); bst.insert(30); bst.insert(20); bst.insert(40); bst.insert(70); bst.insert(60); bst.insert(80)

print("\n查找40:", bst.search(40) is not None)  # 输出: True
print("查找100:", bst.search(100) is not None)  # 输出: False

class CompleteBinaryTree:
    def __init__(self):
        self.tree = []  # 使用列表存储完全二叉树的节点值

    def insert(self, value):
        """向完全二叉树中插入一个节点"""
        self.tree.append(value)

    def get_parent_index(self, index):
        """获取父节点的索引"""
        if index == 0:
            return None
        return (index - 1) // 2

    def get_left_child_index(self, index):
        """获取左子节点的索引"""
        left_index = 2 * index + 1
        if left_index >= len(self.tree):
            return None
        return left_index

    def get_right_child_index(self, index):
        """获取右子节点的索引"""
        right_index = 2 * index + 2
        if right_index >= len(self.tree):
            return None
        return right_index

    def display(self):
        """显示完全二叉树的结构"""
        print("完全二叉树的层次遍历:")
        for i in range(len(self.tree)):
            print(f"节点 {self.tree[i]} | 父节点索引: {self.get_parent_index(i)} | 左子节点索引: {self.get_left_child_index(i)} | 右子节点索引: {self.get_right_child_index(i)}")

# 使用示例
cbt = CompleteBinaryTree()
cbt.insert(1)
cbt.insert(2)
cbt.insert(3)
cbt.insert(4)
cbt.insert(5)
cbt.insert(6)

cbt.display()

完全二叉树的层次遍历:
节点 1 | 父节点索引: None | 左子节点索引: 1 | 右子节点索引: 2
节点 2 | 父节点索引: 0 | 左子节点索引: 3 | 右子节点索引: 4
节点 3 | 父节点索引: 0 | 左子节点索引: 5 | 右子节点索引: None
节点 4 | 父节点索引: 1 | 左子节点索引: None | 右子节点索引: None
节点 5 | 父节点索引: 1 | 左子节点索引: None | 右子节点索引: None
节点 6 | 父节点索引: 2 | 左子节点索引: None | 右子节点索引: None

import heapq

# 创建一个最小堆
min_heap = []
heapq.heappush(min_heap, 3)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 2)
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 4)

print("最小堆的内容:", min_heap)
print("弹出最小值:", heapq.heappop(min_heap))
print("更新后的最小堆:", min_heap)

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C']
}