數據結構和算法是計算機科學的核心基礎，它們在軟件開發、系統設計、數據處理等領域中扮演著至關重要的角色。本文將通過一系列示例，詳細分析常見數據結構和算法的應用場景及其實現方式，幫助讀者更好地理解和掌握這些基礎知識。
數組是一種線性數據結構，它由一組相同類型的元素組成，這些元素在內存中是連續存儲的。數組的訪問速度非?？?，因為可以通過索引直接訪問任意元素。
示例1：統計數組中元素的頻率
def count_frequency(arr):
frequency = {}
for num in arr:
if num in frequency:
frequency[num] += 1
else:
frequency[num] = 1
return frequency
arr = [1, 2, 2, 3, 3, 3, 4]
print(count_frequency(arr))
示例2：尋找數組中的最大值和最小值
def find_max_min(arr):
if not arr:
return None, None
max_val = min_val = arr[0]
for num in arr:
if num > max_val:
max_val = num
if num < min_val:
min_val = num
return max_val, min_val
arr = [1, 2, 3, 4, 5]
print(find_max_min(arr))
鏈表是一種線性數據結構，它由一系列節點組成，每個節點包含數據和指向下一個節點的指針。鏈表可以分為單向鏈表、雙向鏈表和循環鏈表。
示例1：反轉鏈表
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list(head):
prev = None
current = head
while current:
next_node = current.next
current.next = prev
prev = current
current = next_node
return prev
# 示例鏈表: 1 -> 2 -> 3 -> 4 -> 5
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
reversed_head = reverse_list(head)
while reversed_head:
print(reversed_head.val, end=" -> ")
reversed_head = reversed_head.next
示例2：檢測鏈表中的環
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
# 示例鏈表: 1 -> 2 -> 3 -> 4 -> 5 -> 2 (形成環)
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
head.next.next.next.next.next = head.next
print(has_cycle(head))
棧是一種后進先出（LIFO）的數據結構，只允許在一端進行插入和刪除操作。棧常用于實現遞歸、表達式求值、括號匹配等場景。
示例1：括號匹配
def is_valid_parentheses(s):
stack = []
mapping = {')': '(', '}': '{', ']': '['}
for char in s:
if char in mapping:
top_element = stack.pop() if stack else '#'
if mapping[char] != top_element:
return False
else:
stack.append(char)
return not stack
s = "()[]{}"
print(is_valid_parentheses(s))
示例2：逆波蘭表達式求值
def eval_rpn(tokens):
stack = []
for token in tokens:
if token in "+-*/":
b = stack.pop()
a = stack.pop()
if token == '+':
stack.append(a + b)
elif token == '-':
stack.append(a - b)
elif token == '*':
stack.append(a * b)
elif token == '/':
stack.append(int(a / b))
else:
stack.append(int(token))
return stack[0]
tokens = ["2", "1", "+", "3", "*"]
print(eval_rpn(tokens))
隊列是一種先進先出（FIFO）的數據結構，只允許在一端進行插入操作，在另一端進行刪除操作。隊列常用于任務調度、緩沖區管理等場景。
示例1：使用隊列實現棧
from collections import deque
class MyStack:
def __init__(self):
self.queue = deque()
def push(self, x):
self.queue.append(x)
for _ in range(len(self.queue) - 1):
self.queue.append(self.queue.popleft())
def pop(self):
return self.queue.popleft()
def top(self):
return self.queue[0]
def empty(self):
return not self.queue
stack = MyStack()
stack.push(1)
stack.push(2)
print(stack.pop()) # 輸出 2
print(stack.top()) # 輸出 1
示例2：使用隊列實現廣度優先搜索（BFS）
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
node = queue.popleft()
if node not in visited:
print(node)
visited.add(node)
queue.extend(graph[node] - visited)
graph = {
'A': {'B', 'C'},
'B': {'A', 'D', 'E'},
'C': {'A', 'F'},
'D': {'B'},
'E': {'B', 'F'},
'F': {'C', 'E'}
}
bfs(graph, 'A')
樹是一種非線性數據結構，它由節點和邊組成，每個節點可以有零個或多個子節點。樹常用于表示層次結構，如文件系統、組織結構等。
示例1：二叉樹的遍歷
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def inorder_traversal(root):
result = []
def traverse(node):
if node:
traverse(node.left)
result.append(node.val)
traverse(node.right)
traverse(root)
return result
# 示例二叉樹:
# 1
# / \
# 2 3
# / \
# 4 5
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(inorder_traversal(root))
示例2：二叉搜索樹的插入
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def insert_into_bst(root, val):
if not root:
return TreeNode(val)
if val < root.val:
root.left = insert_into_bst(root.left, val)
else:
root.right = insert_into_bst(root.right, val)
return root
# 示例二叉搜索樹:
# 4
# / \
# 2 7
# / \
# 1 3
root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(7))
root = insert_into_bst(root, 5)
print(inorder_traversal(root))
圖是一種非線性數據結構，它由節點（頂點）和邊組成，邊可以是有向的或無向的。圖常用于表示網絡、社交關系等復雜結構。
示例1：深度優先搜索（DFS）
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start)
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
graph = {
'A': {'B', 'C'},
'B': {'A', 'D', 'E'},
'C': {'A', 'F'},
'D': {'B'},
'E': {'B', 'F'},
'F': {'C', 'E'}
}
dfs(graph, 'A')
示例2：Dijkstra算法求最短路徑
import heapq
def dijkstra(graph, start):
distances = {node: float('inf') for node in graph}
distances[start] = 0
heap = [(0, start)]
while heap:
current_distance, current_node = heapq.heappop(heap)
if current_distance > distances[current_node]:
continue
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(heap, (distance, neighbor))
return distances
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
}
print(dijkstra(graph, 'A'))
哈希表是一種通過哈希函數將鍵映射到值的數據結構，它支持快速的插入、刪除和查找操作。哈希表常用于實現字典、緩存等。
示例1：統計字符串中字符的頻率
def count_char_frequency(s):
frequency = {}
for char in s:
if char in frequency:
frequency[char] += 1
else:
frequency[char] = 1
return frequency
s = "hello world"
print(count_char_frequency(s))
示例2：實現LRU緩存
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key):
if key not in self.cache:
return -1
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key, value):
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False)
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1)) # 輸出 1
cache.put(3, 3)
print(cache.get(2)) # 輸出 -1
排序算法是將一組數據按照特定順序進行排列的算法。常見的排序算法包括冒泡排序、選擇排序、插入排序、歸并排序、快速排序等。
示例1：快速排序
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)
arr = [3, 6, 8, 10, 1, 2, 1]
print(quicksort(arr))
示例2：歸并排序
def mergesort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = mergesort(arr[:mid])
right = mergesort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
arr = [3, 6, 8, 10, 1, 2, 1]
print(mergesort(arr))
搜索算法是在數據集中查找特定元素的算法。常見的搜索算法包括線性搜索、二分搜索、深度優先搜索、廣度優先搜索等。
示例1：二分搜索
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
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(binary_search(arr, 5))
示例2：廣度優先搜索（BFS）
from collections import deque
def bfs(graph, start, target):
visited = set()
queue = deque([(start, [start])])
while queue:
node, path = queue.popleft()
if node == target:
return path
if node not in visited:
visited.add(node)
for neighbor in graph[node]:
queue.append((neighbor, path + [neighbor]))
return None
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
print(bfs(graph, 'A', 'F'))
動態規劃是一種通過將問題分解為子問題來求解復雜問題的方法。它通常用于優化問題，如最短路徑、最長公共子序列等。
示例1：斐波那契數列
def fibonacci(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
print(fibonacci(10))
示例2：最長公共子序列（LCS）
def lcs(X, Y):
m, n = len(X), len(Y)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
for j in range(n + 1):
if i == 0 or j == 0:
dp[i][j] = 0
elif X[i - 1] == Y[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
X = "ABCBDAB"
Y = "BDCAB"
print(lcs(X, Y))
貪心算法是一種在每一步選擇中都采取當前狀態下最優的選擇，從而希望導致全局最優解的算法。貪心算法常用于解決最優化問題，如最小生成樹、最短路徑等。
示例1：活動選擇問題
def activity_selection(activities):
activities.sort(key=lambda x: x[1])
selected = []
last_end = 0
for start, end in activities:
if start >= last_end:
selected.append((start, end))
last_end = end
return selected
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 13), (12, 14)]
print(activity_selection(activities))
示例2：霍夫曼編碼
”`python import heapq
class HuffmanNode: def init(self, char, freq): self.char = char self.freq = freq self.left = None self.right = None
def __lt__(self, other
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
