Python数据结构与算法

Python数据结构与算法详解

1. 数据结构基础

1.1 线性表

1.1.1 数组(Array)

Python中没有原生的数组类型，通常使用列表(list)来模拟数组：

# 创建数组
arr = [1, 2, 3, 4, 5]# 访问元素
print(arr[0])  # 输出: 1# 修改元素
arr[2] = 10
print(arr)  # 输出: [1, 2, 10, 4, 5]# 数组长度
print(len(arr))  # 输出: 5

1.1.2 链表(Linked List)

class Node:def __init__(self, data):self.data = dataself.next = Noneclass LinkedList:def __init__(self):self.head = Nonedef append(self, data):new_node = Node(data)if not self.head:self.head = new_nodereturnlast_node = self.headwhile last_node.next:last_node = last_node.nextlast_node.next = new_nodedef print_list(self):current = self.headwhile current:print(current.data, end=" -> ")current = current.nextprint("None")# 使用示例
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.print_list()  # 输出: 1 -> 2 -> 3 -> None

1.1.3 栈(Stack)

class Stack:def __init__(self):self.items = []def push(self, item):self.items.append(item)def pop(self):if not self.is_empty():return self.items.pop()return Nonedef peek(self):if not self.is_empty():return self.items[-1]return Nonedef is_empty(self):return len(self.items) == 0def size(self):return len(self.items)# 使用示例
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())  # 输出: 3
print(stack.peek())  # 输出: 2

1.1.4 队列(Queue)

from collections import dequeclass Queue:def __init__(self):self.items = deque()def enqueue(self, item):self.items.append(item)def dequeue(self):if not self.is_empty():return self.items.popleft()return Nonedef is_empty(self):return len(self.items) == 0def size(self):return len(self.items)# 使用示例
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(queue.dequeue())  # 输出: 1
print(queue.size())  # 输出: 2

1.2 非线性表

1.2.1 树(Tree)

class TreeNode:def __init__(self, value):self.value = valueself.children = []def add_child(self, child_node):self.children.append(child_node)def display(self, level=0):print("  " * level + str(self.value))for child in self.children:child.display(level + 1)# 使用示例
root = TreeNode("A")
child1 = TreeNode("B")
child2 = TreeNode("C")
root.add_child(child1)
root.add_child(child2)
child1.add_child(TreeNode("D"))
child1.add_child(TreeNode("E"))
root.display()
"""
输出:
ABDEC
"""

1.2.2 二叉树(Binary Tree)

class BinaryTreeNode:def __init__(self, value):self.value = valueself.left = Noneself.right = Noneclass BinaryTree:def __init__(self):self.root = Nonedef insert(self, value):if not self.root:self.root = BinaryTreeNode(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 = BinaryTreeNode(value)else:self._insert_recursive(node.left, value)else:if node.right is None:node.right = BinaryTreeNode(value)else:self._insert_recursive(node.right