7-25作业

**第7 周至第25 周作业**

**题目描述**

在本周的作业中，我们将学习如何使用 Python 来实现一些常见的数据结构和算法。我们将重点讨论以下几个方面：

1. **栈和队列**: 我们将学习如何使用 Python 来实现栈和队列这两个基本的线性表。
2. **链表**: 我们将学习如何使用 Python 来实现链表，这是一个非常重要的数据结构。
3. **二叉树**: 我们将学习如何使用 Python 来实现二叉树，这是一个非常重要的非线性表。
4. **图**: 我们将学习如何使用 Python 来实现图，这是一个非常重要的非线性表。

**栈和队列**

###1. 栈栈是一种后进先出的数据结构。它遵循 LIFO（Last In First Out）原则，即最后添加的元素最先被移除。

#### 实现栈的 Python代码

class Stack:
 def __init__(self):
 self.items = []

 def push(self, item):
 # 将 item 添加到栈顶 self.items.append(item)

 def pop(self):
 # 移除栈顶元素并返回 if not self.is_empty():
 return self.items.pop()
 else:
 raise IndexError("Stack is empty")

 def peek(self):
 # 返回栈顶元素但不移除 if not self.is_empty():
 return self.items[-1]
 else:
 raise IndexError("Stack is empty")

 def is_empty(self):
 # 检查栈是否为空 return len(self.items) ==0# 示例使用stack = Stack()
stack.push(1)
stack.push(2)
print(stack.pop()) # 输出:2print(stack.peek()) # 输出:1

class Queue:
 def __init__(self):
 self.items = []

 def enqueue(self, item):
 # 将 item 添加到队尾 self.items.append(item)

 def dequeue(self):
 # 移除队首元素并返回 if not self.is_empty():
 return self.items.pop(0)
 else:
 raise IndexError("Queue is empty")

 def peek(self):
 # 返回队首元素但不移除 if not self.is_empty():
 return self.items[0]
 else:
 raise IndexError("Queue is empty")

 def is_empty(self):
 # 检查队列是否为空 return len(self.items) ==0# 示例使用queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
print(queue.dequeue()) # 输出:1print(queue.peek()) # 输出:2

class Node:
 def __init__(self, data=None):
 self.data = data self.next = Noneclass LinkedList:
 def __init__(self):
 self.head = None def append(self, data):
 # 将数据添加到链表尾部 if not self.head:
 self.head = Node(data)
 else:
 current = self.head while current.next:
 current = current.next current.next = Node(data)

 def traverse(self):
 # 遍历链表并输出元素 current = self.head while current:
 print(current.data, end=" ")
 current = current.next# 示例使用linked_list = LinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)
linked_list.traverse() # 输出:123

class Node:
 def __init__(self, data=None):
 self.data = data self.left = None self.right = Noneclass BinaryTree:
 def __init__(self):
 self.root = None def insert(self, data):
 # 将数据添加到二叉树中 if not self.root:
 self.root = Node(data)
 else:
 current = self.root while True:
 if data < current.data:
 if not current.left:
 current.left = Node(data)
 break current = current.left else:
 if not current.right:
 current.right = Node(data)
 break current = current.right def traverse(self):
 # 遍历二叉树并输出元素 self._traverse(self.root)

 def _traverse(self, node):
 if node:
 print(node.data, end=" ")
 self._traverse(node.left)
 self._traverse(node.right)

# 示例使用binary_tree = BinaryTree()
binary_tree.insert(5)
binary_tree.insert(3)
binary_tree.insert(7)
binary_tree.traverse() # 输出:537

class Node:
 def __init__(self, data=None):
 self.data = data self.edges = []

class Graph:
 def __init__(self):
 self.nodes = {}

 def add_node(self, data):
 # 将数据添加到图中 if not data in self.nodes:
 self.nodes[data] = Node(data)

 def add_edge(self, from_data, to_data):
 # 将两个节点连接起来 if from_data in self.nodes and to_data in self.nodes:
 self.nodes[from_data].edges.append(to_data)
 self.nodes[to_data].edges.append(from_data)

 def traverse(self):
 # 遍历图并输出元素 for node in self.nodes.values():
 print(node.data, end=" ")
 for edge in node.edges:
 print(edge, end=" ")
 print()

# 示例使用graph = Graph()
graph.add_node(1)
graph.add_node(2)
graph.add_node(3)
graph.add_edge(1,2)
graph.add_edge(2,3)
graph.traverse() # 输出:123231