作者主页: 知孤云出岫
目录
- 数据结构实操代码题
- 题目一：实现栈（Stack）
- 题目二：实现队列（Queue）
- 题目三：实现二叉搜索树（BST）
- 题目四：实现链表（Linked List）
- 题目五：实现图的深度优先搜索（DFS）和广度优先搜索（BFS）
数据结构实操代码题
题目一：实现栈（Stack）
请实现一个栈的数据结构，支持以下操作：
push(x)：将元素x压入栈中。pop()：移除并返回栈顶元素。top()：返回栈顶元素。is_empty()：判断栈是否为空。
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 None
def top(self):
if not self.is_empty():
return self.items[-1]
else:
return None
def 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()：判断队列是否为空。
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 None
def front(self):
if not self.is_empty():
return self.items[0]
else:
return None
def 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()：中序遍历二叉树。
class TreeNode:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
class BinarySearchTree:
def __init__(self):
self.root = None
def 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 None
if 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)：获取指定位置的元素。
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def append(self, x):
if not self.head:
self.head = ListNode(x)
else:
current = self.head
while current.next:
current = current.next
current.next = ListNode(x)
def insert(self, index, x):
if index == 0:
new_node = ListNode(x)
new_node.next = self.head
self.head = new_node
else:
current = self.head
for _ in range(index - 1):
if current is None:
return
current = current.next
if current is None:
return
new_node = ListNode(x)
new_node.next = current.next
current.next = new_node
def delete(self, index):
if self.head is None:
return
if index == 0:
self.head = self.head.next
else:
current = self.head
for _ in range(index - 1):
if current is None:
return
current = current.next
if current is None or current.next is None:
return
current.next = current.next.next
def get(self, index):
current = self.head
for _ in range(index):
if current is None:
return None
current = current.next
return 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节点开始进行广度优先搜索。
from collections import defaultdict, deque
class 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 visited
def _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}
这些题目涵盖了栈、队列、二叉搜索树、链表和图的基本操作，通过编写这些代码，你可以很好地练习和巩固数据结构的基本概念和应用。
