在计算机科学中，数据结构是处理数据的一种方式，它决定了数据在计算机中的存储方式以及数据之间的关系。掌握数据结构对于编程来说至关重要，因为它不仅影响代码的效率，还能帮助我们更好地理解问题。本文将提供一系列实战任务，帮助你深入理解各种数据结构，并通过实际操作提升你的编程技能。
一、线性数据结构
1. 数组
任务描述：实现一个动态数组，支持插入、删除、查找和排序操作。
代码示例：
class DynamicArray:
def __init__(self):
self.capacity = 1
self.size = 0
self.array = [None] * self.capacity
def insert(self, index, value):
if index < 0 or index > self.size:
raise IndexError("Index out of bounds")
if self.size == self.capacity:
self._resize(2 * self.capacity)
for i in range(self.size, index, -1):
self.array[i] = self.array[i - 1]
self.array[index] = value
self.size += 1
def delete(self, index):
if index < 0 or index >= self.size:
raise IndexError("Index out of bounds")
value = self.array[index]
for i in range(index, self.size - 1):
self.array[i] = self.array[i + 1]
self.array[self.size - 1] = None
self.size -= 1
if self.size <= self.capacity // 4:
self._resize(self.capacity // 2)
return value
def _resize(self, new_capacity):
new_array = [None] * new_capacity
for i in range(self.size):
new_array[i] = self.array[i]
self.array = new_array
self.capacity = new_capacity
def find(self, value):
for i in range(self.size):
if self.array[i] == value:
return i
return -1
def sort(self):
for i in range(self.size):
for j in range(i + 1, self.size):
if self.array[i] > self.array[j]:
self.array[i], self.array[j] = self.array[j], self.array[i]
2. 链表
任务描述：实现一个双向链表，支持插入、删除、查找和排序操作。
代码示例：
class Node:
def __init__(self, value):
self.value = value
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
def insert(self, value, index=0):
new_node = Node(value)
if index == 0:
if self.head is None:
self.head = self.tail = new_node
else:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
elif index == self.size():
new_node.prev = self.tail
self.tail.next = new_node
self.tail = new_node
else:
current = self.head
for _ in range(index):
current = current.next
new_node.prev = current.prev
new_node.next = current
current.prev.next = new_node
current.prev = new_node
self.size += 1
def delete(self, index):
if index < 0 or index >= self.size():
raise IndexError("Index out of bounds")
current = self.head
for _ in range(index):
current = current.next
if current.prev:
current.prev.next = current.next
if current.next:
current.next.prev = current.prev
if current == self.head:
self.head = current.next
if current == self.tail:
self.tail = current.prev
self.size -= 1
return current.value
def find(self, value):
current = self.head
for _ in range(self.size()):
if current.value == value:
return current
current = current.next
return None
def sort(self):
sorted_list = []
current = self.head
while current:
sorted_list.append(current.value)
current = current.next
sorted_list.sort()
current = self.head
for value in sorted_list:
current.value = value
current = current.next
def size(self):
current = self.head
count = 0
while current:
count += 1
current = current.next
return count
二、非线性数据结构
1. 树
任务描述：实现一个二叉搜索树（BST），支持插入、删除、查找和排序操作。
代码示例：
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, value):
if self.root is None:
self.root = TreeNode(value)
else:
self._insert_recursive(self.root, value)
def _insert_recursive(self, current, value):
if value < current.value:
if current.left is None:
current.left = TreeNode(value)
else:
self._insert_recursive(current.left, value)
else:
if current.right is None:
current.right = TreeNode(value)
else:
self._insert_recursive(current.right, value)
def delete(self, value):
self.root = self._delete_recursive(self.root, value)
def _delete_recursive(self, current, value):
if current is None:
return None
if value < current.value:
current.left = self._delete_recursive(current.left, value)
elif value > current.value:
current.right = self._delete_recursive(current.right, value)
else:
if current.left is None:
return current.right
elif current.right is None:
return current.left
else:
min_larger_node = self._find_min(current.right)
current.value = min_larger_node.value
current.right = self._delete_recursive(current.right, min_larger_node.value)
return current
def _find_min(self, current):
while current.left is not None:
current = current.left
return current
def find(self, value):
return self._find_recursive(self.root, value)
def _find_recursive(self, current, value):
if current is None:
return None
if value < current.value:
return self._find_recursive(current.left, value)
elif value > current.value:
return self._find_recursive(current.right, value)
else:
return current
def inorder_traversal(self):
result = []
self._inorder_recursive(self.root, result)
return result
def _inorder_recursive(self, current, result):
if current:
self._inorder_recursive(current.left, result)
result.append(current.value)
self._inorder_recursive(current.right, result)
2. 图
任务描述：实现一个图数据结构，支持添加边、删除边、查找最短路径和拓扑排序操作。
代码示例：
class Graph:
def __init__(self):
self.adjacency_list = {}
def add_edge(self, vertex1, vertex2, weight=0):
if vertex1 not in self.adjacency_list:
self.adjacency_list[vertex1] = []
if vertex2 not in self.adjacency_list:
self.adjacency_list[vertex2] = []
self.adjacency_list[vertex1].append((vertex2, weight))
self.adjacency_list[vertex2].append((vertex1, weight))
def remove_edge(self, vertex1, vertex2):
if vertex1 in self.adjacency_list and vertex2 in self.adjacency_list[vertex1]:
self.adjacency_list[vertex1].remove((vertex2, 0))
if vertex2 in self.adjacency_list and vertex1 in self.adjacency_list[vertex2]:
self.adjacency_list[vertex2].remove((vertex1, 0))
def shortest_path(self, start, end):
distances = {vertex: float('infinity') for vertex in self.adjacency_list}
distances[start] = 0
priority_queue = [(0, start)]
while priority_queue:
current_distance, current_vertex = heappop(priority_queue)
if current_distance > distances[current_vertex]:
continue
for neighbor, weight in self.adjacency_list[current_vertex]:
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
priority_queue.append((distance, neighbor))
return distances[end]
def topological_sort(self):
in_degree = {vertex: 0 for vertex in self.adjacency_list}
for edges in self.adjacency_list.values():
for edge in edges:
in_degree[edge[0]] += 1
queue = [vertex for vertex in self.adjacency_list if in_degree[vertex] == 0]
sorted_list = []
while queue:
vertex = queue.pop(0)
sorted_list.append(vertex)
for neighbor, _ in self.adjacency_list[vertex]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return sorted_list if len(sorted_list) == len(self.adjacency_list) else None
通过以上实战任务，你可以深入理解各种数据结构，并通过实际操作提升你的编程技能。记住，理论知识是基础，但实践才是检验真理的唯一标准。不断练习，相信你会在数据结构领域取得优异的成绩。