在编程的世界里，数据结构是构建高效算法的基石。掌握数据结构不仅能够提升你的编程能力，还能让你在面对复杂问题时游刃有余。本篇文章将为你提供50个实战习题，通过这些习题，你将能够深入理解各种数据结构的原理和应用。
1. 数组
习题1： 实现一个数组，支持在O(1)时间复杂度内插入和删除元素。
class MyArray:
def __init__(self):
self.data = []
def insert(self, index, value):
self.data.insert(index, value)
def delete(self, index):
return self.data.pop(index)
习题2： 实现一个有序数组，支持二分查找。
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
2. 链表
习题3： 实现一个单链表，支持插入、删除和查找操作。
class ListNode:
def __init__(self, value=0, next=None):
self.value = value
self.next = next
class LinkedList:
def __init__(self):
self.head = None
def insert(self, value):
new_node = ListNode(value)
if not self.head:
self.head = new_node
return
current = self.head
while current.next:
current = current.next
current.next = new_node
def delete(self, value):
if not self.head:
return
if self.head.value == value:
self.head = self.head.next
return
current = self.head
while current.next and current.next.value != value:
current = current.next
if current.next:
current.next = current.next.next
def search(self, value):
current = self.head
while current:
if current.value == value:
return True
current = current.next
return False
3. 栈
习题4： 实现一个栈，支持入栈、出栈和判断栈空操作。
class Stack:
def __init__(self):
self.data = []
def push(self, value):
self.data.append(value)
def pop(self):
if not self.data:
return None
return self.data.pop()
def is_empty(self):
return len(self.data) == 0
4. 队列
习题5： 实现一个队列，支持入队、出队和判断队列空操作。
class Queue:
def __init__(self):
self.data = []
def enqueue(self, value):
self.data.append(value)
def dequeue(self):
if not self.data:
return None
return self.data.pop(0)
def is_empty(self):
return len(self.data) == 0
5. 树
习题6： 实现一个二叉树，支持插入、删除和查找操作。
class TreeNode:
def __init__(self, value=0, left=None, right=None):
self.value = value
self.left = left
self.right = right
class BinaryTree:
def __init__(self):
self.root = None
def insert(self, value):
if not self.root:
self.root = TreeNode(value)
return
current = self.root
while current:
if value < current.value:
if not current.left:
current.left = TreeNode(value)
return
current = current.left
else:
if not current.right:
current.right = TreeNode(value)
return
current = current.right
def delete(self, value):
self.root = self._delete(self.root, value)
def _delete(self, node, value):
if not node:
return None
if value < node.value:
node.left = self._delete(node.left, value)
elif value > node.value:
node.right = self._delete(node.right, value)
else:
if not node.left:
return node.right
elif not node.right:
return node.left
else:
min_node = self._find_min(node.right)
node.value = min_node.value
node.right = self._delete(node.right, min_node.value)
return node
def _find_min(self, node):
while node.left:
node = node.left
return node
6. 图
习题7： 实现一个图，支持添加边、删除边、查找路径和判断图中是否存在环操作。
class Graph:
def __init__(self):
self.adjacency_list = {}
def add_edge(self, u, v):
if u not in self.adjacency_list:
self.adjacency_list[u] = []
if v not in self.adjacency_list:
self.adjacency_list[v] = []
self.adjacency_list[u].append(v)
self.adjacency_list[v].append(u)
def delete_edge(self, u, v):
if u in self.adjacency_list and v in self.adjacency_list[u]:
self.adjacency_list[u].remove(v)
if v in self.adjacency_list and u in self.adjacency_list[v]:
self.adjacency_list[v].remove(u)
def find_path(self, start, end):
visited = set()
return self._find_path_recursive(start, end, visited)
def _find_path_recursive(self, current, end, visited):
if current == end:
return [current]
visited.add(current)
for neighbor in self.adjacency_list[current]:
if neighbor not in visited:
path = self._find_path_recursive(neighbor, end, visited)
if path:
return [current] + path
return None
def has_cycle(self):
visited = set()
return self._has_cycle_recursive(self.root, visited)
def _has_cycle_recursive(self, node, visited):
if not node:
return False
if node in visited:
return True
visited.add(node)
for neighbor in self.adjacency_list[node]:
if self._has_cycle_recursive(neighbor, visited):
return True
return False
总结
通过以上50个实战习题，相信你已经对数据结构有了更深入的理解。在实际编程过程中，灵活运用这些数据结构，将帮助你解决各种复杂问题。不断练习，你将逐渐成为一名优秀的程序员。