数据结构实操代码题~考研

作者主页: 知孤云出岫在这里插入图片描述

数据结构实操代码题

题目一：实现栈（Stack）

请实现一个栈的数据结构，支持以下操作：

push(x)：将元素x压入栈中。
pop()：移除并返回栈顶元素。
top()：返回栈顶元素。
is_empty()：判断栈是否为空。

python">class Stack:def __init__(self):self.items = []def push(self, x):self.items.append(x)def pop(self):if not self.is_empty():return self.items.pop()else:return Nonedef top(self):if not self.is_empty():return self.items[-1]else:return Nonedef is_empty(self):return len(self.items) == 0# 测试代码
stack = Stack()
stack.push(1)
stack.push(2)
print(stack.top())    # 输出: 2
print(stack.pop())    # 输出: 2
print(stack.is_empty()) # 输出: False
print(stack.pop())    # 输出: 1
print(stack.is_empty()) # 输出: True

题目二：实现队列（Queue）

请实现一个队列的数据结构，支持以下操作：

enqueue(x)：将元素x加入队列。
dequeue()：移除并返回队列头部元素。
front()：返回队列头部元素。
is_empty()：判断队列是否为空。

python">class Queue:def __init__(self):self.items = []def enqueue(self, x):self.items.append(x)def dequeue(self):if not self.is_empty():return self.items.pop(0)else:return Nonedef front(self):if not self.is_empty():return self.items[0]else:return Nonedef is_empty(self):return len(self.items) == 0# 测试代码
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
print(queue.front())    # 输出: 1
print(queue.dequeue())  # 输出: 1
print(queue.is_empty()) # 输出: False
print(queue.dequeue())  # 输出: 2
print(queue.is_empty()) # 输出: True

题目三：实现二叉搜索树（BST）

请实现一个二叉搜索树的数据结构，支持以下操作：

insert(x)：插入元素x。
search(x)：查找元素x，返回True或False。
inorder()：中序遍历二叉树。

python">class TreeNode:def __init__(self, key):self.left = Noneself.right = Noneself.val = keyclass BinarySearchTree:def __init__(self):self.root = Nonedef insert(self, key):if self.root is None:self.root = TreeNode(key)else:self._insert(self.root, key)def _insert(self, root, key):if key < root.val:if root.left is None:root.left = TreeNode(key)else:self._insert(root.left, key)else:if root.right is None:root.right = TreeNode(key)else:self._insert(root.right, key)def search(self, key):return self._search(self.root, key)def _search(self, root, key):if root is None or root.val == key:return root is not Noneif key < root.val:return self._search(root.left, key)else:return self._search(root.right, key)def inorder(self):return self._inorder(self.root, [])def _inorder(self, root, result):if root:self._inorder(root.left, result)result.append(root.val)self._inorder(root.right, result)return result# 测试代码
bst = BinarySearchTree()
bst.insert(3)
bst.insert(1)
bst.insert(2)
bst.insert(5)
print(bst.search(3))    # 输出: True
print(bst.search(4))    # 输出: False
print(bst.inorder())    # 输出: [1, 2, 3, 5]

题目四：实现链表（Linked List）

请实现一个单向链表的数据结构，支持以下操作：

append(x)：在链表末尾添加元素x。
insert(index, x)：在指定位置插入元素x。
delete(index)：删除指定位置的元素。
get(index)：获取指定位置的元素。

python">class ListNode:def __init__(self, x):self.val = xself.next = Noneclass LinkedList:def __init__(self):self.head = Nonedef append(self, x):if not self.head:self.head = ListNode(x)else:current = self.headwhile current.next:current = current.nextcurrent.next = ListNode(x)def insert(self, index, x):if index == 0:new_node = ListNode(x)new_node.next = self.headself.head = new_nodeelse:current = self.headfor _ in range(index - 1):if current is None:returncurrent = current.nextif current is None:returnnew_node = ListNode(x)new_node.next = current.nextcurrent.next = new_nodedef delete(self, index):if self.head is None:returnif index == 0:self.head = self.head.nextelse:current = self.headfor _ in range(index - 1):if current is None:returncurrent = current.nextif current is None or current.next is None:returncurrent.next = current.next.nextdef get(self, index):current = self.headfor _ in range(index):if current is None:return Nonecurrent = current.nextreturn current.val if current else None# 测试代码
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
print(ll.get(1))     # 输出: 2
ll.insert(1, 4)
print(ll.get(1))     # 输出: 4
ll.delete(2)
print(ll.get(2))     # 输出: 3

题目五：实现图的深度优先搜索（DFS）和广度优先搜索（BFS）

请实现一个无向图的数据结构，支持以下操作：

add_edge(u, v)：添加边u-v。
dfs(start)：从start节点开始进行深度优先搜索。
bfs(start)：从start节点开始进行广度优先搜索。

python">from collections import defaultdict, dequeclass Graph:def __init__(self):self.graph = defaultdict(list)def add_edge(self, u, v):self.graph[u].append(v)self.graph[v].append(u)def dfs(self, start):visited = set()self._dfs(start, visited)return visiteddef _dfs(self, node, visited):if node not in visited:visited.add(node)for neighbor in self.graph[node]:self._dfs(neighbor, visited)def bfs(self, start):visited = set()queue = deque([start])visited.add(start)while queue:node = queue.popleft()for neighbor in self.graph[node]:if neighbor not in visited:visited.add(neighbor)queue.append(neighbor)return visited# 测试代码
g = Graph()
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 4)
g.add_edge(3, 4)
g.add_edge(4, 5)
print(g.dfs(1))  # 输出: {1, 2, 3, 4, 5}
print(g.bfs(1))  # 输出: {1, 2, 3, 4, 5}