Python数据结构详细攻略
什么是数据结构?
数据结构是计算机中存储、组织数据的方式。常见的数据结构有数组、链表、栈、队列、哈希表、树和图等。不同的数据结构适用于不同的场景，通过选择合适的数据结构能够提高程序的效率和性能。
数组(Array)
数组是一种线性数据结构，它是一组连续的内存空间，用来存储同类型的数据。数组中的元素可以被通过下标访问，下标通常从0开始，用来表示元素在数组中的位置。
示例：
# 定义数组
numbers = [1, 2, 3, 4, 5]
# 访问数组元素
print(numbers[0]) # 输出1
print(numbers[2]) # 输出3
# 修改数组元素
numbers[2] = 6
print(numbers) # 输出[1, 2, 6, 4, 5]
链表(Linked List)
链表也是一种线性数据结构，不同的是它的元素不是存储在连续空间中，而是通过指针相连，形成一个链式结构，链表中的每个节点都包含数据元素和指向下一个节点的指针。
示例：
# 定义链表节点
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# 定义链表
class MyLinkedList:
def __init__(self):
"""
Initialize your data structure here.
"""
self.head = None
def get(self, index: int) -> int:
"""
Get the value of the index-th node in the linked list. If the index is invalid, return -1.
"""
if index < 0 or not self.head:
return -1
p = self.head
for i in range(index):
p = p.next
if not p:
return -1
return p.val
def addAtHead(self, val: int) -> None:
"""
Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
"""
self.head = ListNode(val, self.head)
def addAtTail(self, val: int) -> None:
"""
Append a node of value val to the last element of the linked list.
"""
if not self.head:
self.head = ListNode(val)
else:
p = self.head
while p.next:
p = p.next
p.next = ListNode(val)
def addAtIndex(self, index: int, val: int) -> None:
"""
Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
"""
if index <= 0:
self.addAtHead(val)
else:
p = self.head
for i in range(index-1):
p = p.next
if not p:
return
p.next = ListNode(val, p.next)
def deleteAtIndex(self, index: int) -> None:
"""
Delete the index-th node in the linked list, if the index is valid.
"""
if index < 0 or not self.head:
return
if index == 0:
self.head = self.head.next
return
p = self.head
for i in range(index-1):
p = p.next
if not p:
return
if p.next:
p.next = p.next.next
# 测试链表操作
obj = MyLinkedList()
obj.addAtIndex(0, 1)
obj.addAtIndex(1, 2)
obj.addAtIndex(2, 3)
print(obj.get(1)) # 输出2
obj.deleteAtIndex(1)
print(obj.get(1)) # 输出3
栈(Stack)
栈是一种先进后出(FIFO)的数据结构。它支持两个操作：入栈(push)和出栈(pop)。在栈中，只能在栈顶进行插入和删除操作。
示例：
# 使用Python的列表(list)实现栈
class Stack:
def __init__(self):
self.stack = []
def push(self, item):
self.stack.append(item)
def pop(self):
if not self.is_empty():
return self.stack.pop()
def is_empty(self):
return len(self.stack) == 0
def peek(self):
if not self.is_empty():
return self.stack[-1]
def size(self):
return len(self.stack)
# 测试栈操作
s = Stack()
s.push(1)
s.push(2)
s.push(3)
print(s.peek()) # 输出3
s.pop()
print(s.peek()) # 输出2
队列(Queue)
队列是一种先进先出(FIFO)的数据结构。它支持两个操作：入队列(enqueue)和出队列(dequeue)。在队列中，只能在队列尾进行插入操作，在队列头进行删除操作。
示例：
# 使用Python的列表(list)实现队列
class Queue:
def __init__(self):
self.queue = []
def is_empty(self):
return len(self.queue) == 0
def enqueue(self, item):
self.queue.append(item)
def dequeue(self):
if not self.is_empty():
return self.queue.pop(0)
def size(self):
return len(self.queue)
# 测试队列操作
q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.size()) # 输出3
print(q.dequeue()) # 输出1
print(q.dequeue()) # 输出2
哈希表(Hash Table)
哈希表是一种通过哈希函数将关键字映射到表中位置来实现数据的快速查找的数据结构。哈希表包含一个数组和一个哈希函数，通过哈希函数将关键字映射到数组中的位置，然后在这个位置上存储数据。
示例：
# 使用Python内置哈希表字典(dict)实现哈希表
class HashTable:
def __init__(self):
self.table = {}
def put(self, key, value):
self.table[key] = value
def get(self, key):
return self.table.get(key, -1)
def remove(self, key):
if key in self.table:
del self.table[key]
# 测试哈希表操作
ht = HashTable()
ht.put(1, 'A')
ht.put(2, 'B')
ht.put(3, 'C')
print(ht.get(2)) # 输出B
ht.remove(2)
print(ht.get(2)) # 输出-1
树(Tree)
树是一种非线性的数据结构，它由节点和边组成。每个节点包含一个数据元素和指向其子节点的指针。根节点是整个树的唯一入口。
示例：
# 定义树节点
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 定义二叉搜索树(Binary Search Tree, BST)
class BST:
def __init__(self):
self.root = None
def insert(self, val):
if not self.root:
self.root = TreeNode(val)
else:
current_node = self.root
while True:
if val < current_node.val:
if not current_node.left:
current_node.left = TreeNode(val)
break
else:
current_node = current_node.left
else:
if not current_node.right:
current_node.right = TreeNode(val)
break
else:
current_node = current_node.right
def search(self, val):
current_node = self.root
while current_node:
if current_node.val == val:
return True
elif val < current_node.val:
current_node = current_node.left
else:
current_node = current_node.right
return False
# 测试树操作
bst = BST()
bst.insert(5)
bst.insert(3)
bst.insert(7)
print(bst.search(3)) # 输出True
print(bst.search(6)) # 输出False
图(Graph)
图是一种由节点和边组成的非线性数据结构。节点表示图中的元素，边表示图中元素之间的关系。图可以分为有向图和无向图，有向图表示边有方向，无向图表示边没有方向。
示例：
# 定义有向图
graph = {
'A': ['B', 'C'],
'B': ['C', 'D'],
'C': ['D'],
'D': ['C'],
'E': ['F'],
'F': ['C']
}
# 实现深度优先搜索(DFS)
visited = set() # 用set来记录已经遍历的节点集合
def dfs(graph, node):
if node not in visited: # 如果节点没有遍历过
visited.add(node) # 将节点加入已遍历集合
for neighbor in graph[node]: # 遍历所有邻接点
dfs(graph, neighbor)
dfs(graph, 'A') # 遍历整个图
# 实现广度优先搜索(BFS)
from queue import Queue
def bfs(graph, start):
visited = set() # 用set来记录已经遍历的节点集合
q = Queue()
q.put(start) # 将起始节点加入队列
visited.add(start) # 将起始节点加入已遍历集合
while not q.empty():
node = q.get()
print(node)
for neighbor in graph[node]: # 遍历所有邻接点
if neighbor not in visited: # 如果节点没有遍历过
visited.add(neighbor) # 将节点加入已遍历集合
q.put(neighbor) # 将节点加入队列
bfs(graph, 'A') # 遍历整个图
结论
以上就是Python中常见的基本数据结构的详细介绍和示例代码，希望能够对大家编程学习有所帮助。根据不同的场景需要，选择合适的数据结构能够提高程序的效率和性能。
本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：Python数据结构详细 - Python技术站
微信扫一扫 
支付宝扫一扫 