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语言实现这些算法。