编程与数学 02-017 Python 面向对象编程 17课题、数据结构

编程与数学 02-017 Python 面向对象编程 17课题、数据结构

• 一、基本数据结构实现
• • （一）链表(Linked List)
  • （二）栈(Stack)
  • （三）队列(Queue)
• 二、树形数据结构
• • （二）二叉树(Binary Tree)
  • （二）二叉搜索树(BST)
• 三、图结构(Graph)
• • （一）邻接表表示法
• 四、哈希表(Hash Table)
• 五、堆(Heap)
• 六、高级数据结构
• • （一）字典树(Trie)
• 七、数据结构设计原则
• 八、Python内置数据结构与OOP
• 全文总结

摘要：本文介绍了Python面向对象编程中常见的数据结构实现，包括链表、栈、队列、树形结构（如二叉树和二叉搜索树）、图结构、哈希表、堆以及高级数据结构如字典树。每个数据结构都通过类的形式实现，具有封装性、单一职责和清晰的接口。同时，文章还探讨了数据结构设计原则以及Python内置数据结构与面向对象编程的结合，强调了合理设计类、选择合适的数据结构、提供清晰接口、考虑性能和代码可维护性的重要性。

关键词：Python，面向对象编程，数据结构，链表，栈，队列，树，图，哈希表，堆，字典树

人工智能助手：Kimi

一、基本数据结构实现

（一）链表(Linked List)

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

（二）栈(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 None def peek(self): if not self.is_empty(): return self.items[-1] return None def is_empty(self): return len(self.items) == 0 def size(self): return len(self.items)# 使用示例s = Stack()s.push(1)s.push(2)print(s.pop()) # 输出: 2print(s.peek()) # 输出: 1

（三）队列(Queue)

class Queue: def __init__(self): self.items = [] def enqueue(self, item): self.items.insert(0, item) def dequeue(self): if not self.is_empty(): return self.items.pop() return None def is_empty(self): return len(self.items) == 0 def size(self): return len(self.items)# 使用示例q = Queue()q.enqueue(1)q.enqueue(2)print(q.dequeue()) # 输出: 1

二、树形数据结构

（二）二叉树(Binary Tree)

class TreeNode: def __init__(self, value): self.value = value self.left = None self.right = Noneclass BinaryTree: def __init__(self, root_value): self.root = TreeNode(root_value) def insert_left(self, parent, value): if parent.left is None: parent.left = TreeNode(value) else: new_node = TreeNode(value) new_node.left = parent.left parent.left = new_node def insert_right(self, parent, value): if parent.right is None: parent.right = TreeNode(value) else: new_node = TreeNode(value) new_node.right = parent.right parent.right = new_node def preorder(self, node): if node: print(node.value, end=\" \") self.preorder(node.left) self.preorder(node.right)# 使用示例bt = BinaryTree(1)bt.insert_left(bt.root, 2)bt.insert_right(bt.root, 3)bt.insert_left(bt.root.left, 4)bt.preorder(bt.root) # 输出: 1 2 4 3

（二）二叉搜索树(BST)

class BSTNode: def __init__(self, value): self.value = value self.left = None self.right = Noneclass BinarySearchTree: def __init__(self): self.root = None def insert(self, value): if self.root is None: self.root = BSTNode(value) else: self._insert(value, self.root) def _insert(self, value, current_node): if value < current_node.value: if current_node.left is None: current_node.left = BSTNode(value) else: self._insert(value, current_node.left) elif value > current_node.value: if current_node.right is None: current_node.right = BSTNode(value) else: self._insert(value, current_node.right) else: print(\"值已存在\") def search(self, value): return self._search(value, self.root) if self.root else False def _search(self, value, current_node): if current_node is None: return False elif value == current_node.value: return True elif value < current_node.value: return self._search(value, current_node.left) else: return self._search(value, current_node.right)# 使用示例bst = BinarySearchTree()bst.insert(5)bst.insert(3)bst.insert(7)print(bst.search(3)) # 输出: Trueprint(bst.search(9)) # 输出: False

三、图结构(Graph)

（一）邻接表表示法

class Graph: def __init__(self): self.adj_list = {} def add_vertex(self, vertex): if vertex not in self.adj_list: self.adj_list[vertex] = [] def add_edge(self, v1, v2): if v1 in self.adj_list and v2 in self.adj_list: self.adj_list[v1].append(v2) self.adj_list[v2].append(v1) def dfs(self, start): visited = set() self._dfs(start, visited) def _dfs(self, vertex, visited): visited.add(vertex) print(vertex, end=\" \") for neighbor in self.adj_list[vertex]: if neighbor not in visited: self._dfs(neighbor, visited)# 使用示例g = Graph()g.add_vertex(\'A\')g.add_vertex(\'B\')g.add_vertex(\'C\')g.add_edge(\'A\', \'B\')g.add_edge(\'B\', \'C\')g.dfs(\'A\') # 输出: A B C

四、哈希表(Hash Table)

class HashTable: def __init__(self, size=10): self.size = size self.table = [[] for _ in range(size)] def _hash(self, key): return hash(key) % self.size def insert(self, key, value): hash_key = self._hash(key) bucket = self.table[hash_key] for i, (k, v) in enumerate(bucket): if k == key: bucket[i] = (key, value) return bucket.append((key, value)) def get(self, key): hash_key = self._hash(key) bucket = self.table[hash_key] for k, v in bucket: if k == key: return v return None def delete(self, key): hash_key = self._hash(key) bucket = self.table[hash_key] for i, (k, v) in enumerate(bucket): if k == key: del bucket[i] return# 使用示例ht = HashTable()ht.insert(\"name\", \"Alice\")ht.insert(\"age\", 25)print(ht.get(\"name\")) # 输出: Aliceht.delete(\"age\")print(ht.get(\"age\")) # 输出: None

五、堆(Heap)

class MinHeap: def __init__(self): self.heap = [] def parent(self, i): return (i - 1) // 2 def left_child(self, i): return 2 * i + 1 def right_child(self, i): return 2 * i + 2 def insert(self, key): self.heap.append(key) self._heapify_up(len(self.heap) - 1) def _heapify_up(self, i): while i > 0 and self.heap[self.parent(i)] > self.heap[i]: self.heap[self.parent(i)], self.heap[i] = self.heap[i], self.heap[self.parent(i)] i = self.parent(i) def extract_min(self): if not self.heap: return None root = self.heap[0] last = self.heap.pop() if self.heap: self.heap[0] = last self._heapify_down(0) return root def _heapify_down(self, i): smallest = i left = self.left_child(i) right = self.right_child(i) if left < len(self.heap) and self.heap[left] < self.heap[smallest]: smallest = left if right < len(self.heap) and self.heap[right] < self.heap[smallest]: smallest = right if smallest != i: self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i] self._heapify_down(smallest)# 使用示例h = MinHeap()h.insert(3)h.insert(1)h.insert(4)print(h.extract_min()) # 输出: 1print(h.extract_min()) # 输出: 3

六、高级数据结构

（一）字典树(Trie)

class TrieNode: def __init__(self): self.children = {} self.is_end = Falseclass Trie: def __init__(self): self.root = TrieNode() def insert(self, word): current = self.root for char in word: if char not in current.children: current.children[char] = TrieNode() current = current.children[char] current.is_end = True def search(self, word): current = self.root for char in word: if char not in current.children: return False current = current.children[char] return current.is_end def starts_with(self, prefix): current = self.root for char in prefix: if char not in current.children: return False current = current.children[char] return True# 使用示例t = Trie()t.insert(\"apple\")print(t.search(\"apple\")) # 输出: Trueprint(t.search(\"app\")) # 输出: Falseprint(t.starts_with(\"app\")) # 输出: True

七、数据结构设计原则

1. 封装性：将数据结构的实现细节隐藏在类内部
2. 单一职责：每个数据结构类只负责一种数据组织方式
3. 接口清晰：提供明确的方法签名和文档说明
4. 性能考虑：根据操作频率选择合适实现方式
5. 可扩展性：设计时考虑未来可能的扩展需求

八、Python内置数据结构与OOP

Python内置数据结构(list, dict, set等)也可以与OOP结合使用：

class ShoppingCart: def __init__(self): self.items = {} # 使用字典存储商品和数量 def add_item(self, item, quantity=1): if item in self.items: self.items[item] += quantity else: self.items[item] = quantity def remove_item(self, item, quantity=1): if item in self.items: if self.items[item] <= quantity: del self.items[item] else: self.items[item] -= quantity def total_items(self): return sum(self.items.values()) def clear(self): self.items.clear()# 使用示例cart = ShoppingCart()cart.add_item(\"Apple\", 3)cart.add_item(\"Banana\")print(cart.total_items()) # 输出: 4

全文总结

本文全面介绍了Python面向对象编程中多种数据结构的实现方式。首先，通过类的形式实现了链表、栈、队列等基本数据结构，展示了如何通过节点和指针管理数据。接着，文章深入探讨了树形结构，包括二叉树和二叉搜索树的插入、搜索等操作。图结构通过邻接表实现，并提供了深度优先搜索的示例。哈希表的实现则展示了如何处理键值对的存储和检索。堆结构的实现重点在于维护最小堆的性质。此外，高级数据结构如字典树的实现展示了如何高效处理字符串前缀匹配问题。文章还强调了数据结构设计的原则，如封装性、单一职责和接口清晰性，并结合Python内置数据结构展示了面向对象编程的强大功能。通过这些内容，读者可以更好地理解如何在Python中实现和使用各种数据结构，以及如何通过面向对象的方式提高代码的复用性和可维护性。

在Python面向对象编程中实现数据结构时，关键在于：

1. 合理设计类和类之间的关系
2. 选择合适的数据结构作为内部实现
3. 提供清晰的接口方法
4. 考虑时间复杂度和空间复杂度
5. 保持代码的可读性和可维护性

通过面向对象的方式实现数据结构，可以更好地组织代码，提高复用性，并使数据操作更加安全和直观。