Python語言版的數據結構與算法
數碼 6
這篇文章將從Python語言的角度，對數據結構與算法做詳細的闡述，並且給出對應的代碼實現。
線性結構是數據結構中最基本、最常用的結構之一，它是一種一對一、一對多的關係。其中，數組是最基本的線性結構，Python中提供的List就是一種典型的數組結構。
1、List
在Python中，列表(List)是一種高效、靈活、強大的數據類型。通過索引的方式，我們可以非常方便地訪問、添加、插入、刪除和修改元素。下面是對應代碼：
# 定義一個列表 list1 = [1, 2, 3, 4, 5] # 訪問列表中的元素 print(list1[0]) # 輸出1 # 添加元素 list1.append(6) print(list1) # 輸出[1, 2, 3, 4, 5, 6] # 插入元素 list1.insert(0, 0) print(list1) # 輸出[0, 1, 2, 3, 4, 5, 6] # 刪除元素 del list1[0] print(list1) # 輸出[1, 2, 3, 4, 5, 6] # 修改元素 list1[0] = 0 print(list1) # 輸出[0, 2, 3, 4, 5, 6]
2、Stack
棧(Stack)是一種後進先出（LIFO）的數據結構，通過push()和pop()方法，實現對棧中元素的添加和刪除。下面是對應代碼：
class Stack:
def __init__(self):
self.items = []
# 判斷棧空
def isEmpty(self):
return self.items == []
# 添加元素
def push(self, item):
self.items.append(item)
# 刪除元素
def pop(self):
return self.items.pop()
# 返回棧頂元素
def peek(self):
return self.items[len(self.items)-1]
# 返回棧中元素數量
def size(self):
return len(self.items)
s = Stack()
s.push('hello')
s.push('world')
print(s.pop()) # 輸出world
樹形結構是一種非線性結構，適合存儲具有層次關係的數據結構。常見的樹形結構有二叉樹、二叉搜索樹、AVL樹、紅黑樹等。
1、二叉搜索樹
二叉搜索樹(Binary Search Tree)是一種樹形結構，每個節點最多有兩個子節點。其中，每個節點的值都大於其左子樹中的所有節點的值，且小於其右子樹中的所有節點的值。下面是對應的代碼實現：
# 定義一個節點類
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# 定義一個二叉搜索樹類
class BST:
def __init__(self):
self.root = None
# 插入節點
def insert(self, val):
node = TreeNode(val)
if not self.root:
self.root = node
else:
current = self.root
while True:
if current.val > val:
if not current.left:
current.left = node
break
else:
current = current.left
else:
if not current.right:
current.right = node
break
else:
current = current.right
# 搜索節點
def search(self, val):
current = self.root
while True:
if not current:
break
elif current.val == val:
return True
elif current.val > val:
current = current.left
else:
current = current.right
return False
bst = BST()
bst.insert(3)
bst.insert(1)
bst.insert(5)
print(bst.search(3)) # 輸出True
print(bst.search(4)) # 輸出False
2、AVL樹
AVL樹是一種自平衡二叉搜索樹，它通過旋轉操作來保持樹的平衡。其中，旋轉操作主要分為四種：左旋、右旋、左右旋和右左旋。下面是對應的代碼實現：
# 定義一個AVL節點類
class AVLNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.height = 1
# 定義一個AVL樹類
class AVLTree:
def __init__(self):
self.root = None
# 獲取節點高度
def getHeight(self, node):
if not node:
return 0
else:
return node.height
# 獲取節點平衡因子
def getBalanceFactor(self, node):
if not node:
return 0
else:
return self.getHeight(node.left) - self.getHeight(node.right)
# 右旋
def rightRotate(self, y):
x = y.left
T2 = x.right
x.right = y
y.left = T2
y.height = max(self.getHeight(y.left), self.getHeight(y.right)) + 1
x.height = max(self.getHeight(x.left), self.getHeight(x.right)) + 1
return x
# 左旋
def leftRotate(self, x):
y = x.right
T2 = y.left
y.left = x
x.right = T2
x.height = max(self.getHeight(x.left), self.getHeight(x.right)) + 1
y.height = max(self.getHeight(y.left), self.getHeight(y.right)) + 1
return y
# 插入節點
def insert(self, val):
node = AVLNode(val)
if not self.root:
self.root = node
else:
self.root = self.insertNode(self.root, node)
def insertNode(self, root, node):
if not root:
return node
elif node.val 1 and node.val < root.left.val:
return self.rightRotate(root)
elif balanceFactor root.right.val:
return self.leftRotate(root)
elif balanceFactor > 1 and node.val > root.left.val:
root.left = self.leftRotate(root.left)
return self.rightRotate(root)
elif balanceFactor < -1 and node.val < root.right.val:
root.right = self.rightRotate(root.right)
return self.leftRotate(root)
return root
avl = AVLTree()
avl.insert(3)
avl.insert(1)
avl.insert(5)
print(avl.root.val) # 輸出3
圖是一種非線性結構，它由頂點(Vertex)和邊(Edge)組成，是描述對象之間關係的一種數據結構。常見的圖有有向圖、無向圖、加權圖等。
1、無向圖BFS
無向圖是一種節點之間沒有方向的圖，它可通過廣度優先搜索算法(BFS)來進行遍歷。下面是對應的代碼實現：
from collections import defaultdict
# 定義一個圖類
class Graph:
def __init__(self):
self.graph = defaultdict(list)
# 添加邊
def addEdge(self, u, v):
self.graph[u].append(v)
self.graph[v].append(u)
# BFS遍歷
def BFS(self, s):
visited = [False] * (max(self.graph) + 1)
queue = []
queue.append(s)
visited[s] = True
while queue:
s = queue.pop(0)
print(s, end=" ")
for i in self.graph[s]:
if visited[i] == False:
queue.append(i)
visited[i] = True
# 定義一個無向圖
g = Graph()
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)
g.BFS(2) # 輸出2 0 3 1
2、有向圖DFS
有向圖是一種節點之間有方向的圖，它可通過深度優先搜索算法(DFS)來進行遍歷。下面是對應的代碼實現：
# 定義一個有向圖類
class DiGraph:
def __init__(self, V):
self.V = V
self.graph = defaultdict(list)
# 添加邊
def addEdge(self, u, v):
self.graph[u].append(v)
# DFS遍歷
def DFS(self, v, visited):
visited[v] = True
print(v, end=" ")
for i in self.graph[v]:
if visited[i] == False:
self.DFS(i, visited)
# 定義一個有向圖
g = DiGraph(4)
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)
# 調用DFS算法
visited = [False] * (g.V)
for i in range(g.V):
if visited[i] == False:
g.DFS(i, visited)
排序算法是對無序數據進行排序的一種算法。常見的排序算法有冒泡排序、選擇排序、插入排序、歸併排序和快速排序等。
1、冒泡排序
冒泡排序(Bubble Sort)是一種通過交換相鄰元素的位置來實現排序的算法。下面是對應的代碼實現：
def bubbleSort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
arr = [64, 34, 25, 12, 22, 11, 90]
bubbleSort(arr)
print("冒泡排序結果：")
for i in range(len(arr)):
print(arr[i], end=" ")
2、快速排序
快速排序(Quick Sort)是一種比冒泡排序略快的排序算法。它通過遞歸對數據進行排序，利用分治思想來提高排序的效率。下面是對應的代碼實現：
def partition(arr, low, high):
i = low - 1
pivot = arr[high]
for j in range(low, high):
if arr[j] <= pivot:
i = i + 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[high] = arr[high], arr[i+1]
return i+1
def quickSort(arr, low, high):
if low < high:
pi = partition(arr, low, high)
quickSort(arr, low, pi-1)
quickSort(arr, pi+1, high)
arr = [64, 34, 25, 12, 22, 11, 90]
quickSort(arr, 0, len(arr)-1)
print("快速排序結果：")
for i in range(len(arr)):
print(arr[i], end=" ")
本文從不同方面對Python語言下的數據結構與算法進行了詳細的闡述，其中對線性結構、樹形結構、圖結構和排序算法進行了詳細的介紹，並給出了對應的Python代碼實現。希望本文能夠幫助讀者了解數據結構與算法的基本知識，並通過Python語言實現這些算法。