3.1 数据操作：插入、删除、查找
插入 (Insert):
在数据结构中添加新元素的操作。插入可以发生在数据结构的开头、结尾或任意位置。
删除 (Delete):
从数据结构中删除元素的操作。删除可以根据元素的值、索引或在数据结构中的位置发生。
查找 (Search):
在数据结构中找到元素的操作。查找可以根据值或其他标准进行。
操作示例：
- 数组: 插入和删除需要移动元素，这可能是耗时的 —
O(n)。 - 链表: 如果已知节点位置，插入和删除可以在
O(1)时间内完成。 - 哈希表: 查找、插入和删除通常在平均情况下是
O(1)。 - 树: 在平衡树中，查找、插入和删除操作可以在
O(log n)时间内完成。
3.2 基本概念：数组、列表、栈、队列
数组
数组是一种元素相同类型的序列，可以通过索引访问。
操作复杂度：索引访问 — O(1)，插入和删除 — O(n)。
示例：创建数组，修改元素并输出结果
# 创建一个数字数组
arr = [1, 2, 3, 4, 5]
# 修改索引为2（第三个元素，因为索引从0开始）的元素
arr[2] = 10
# 输出修改后的数组
print(arr) # 输出: [1, 2, 10, 4, 5]
# 在数组末尾添加新元素
arr.append(6)
print(arr) # 输出: [1, 2, 10, 4, 5, 6]
# 根据索引删除元素
del arr[1]
print(arr) # 输出: [1, 10, 4, 5, 6]
列表
列表是由元素组成的集合，其中每个元素包含对下一个（单链表）或对下一个和上一个（双链表）元素的引用。
操作复杂度：已知位置的插入和删除 — O(1)，查找 — O(n)。
示例：创建简单的单链表并遍历
# 定义链表节点结构
class Node:
def __init__(self, data):
self.data = data
self.next = None
# 创建单链表
node1 = Node("101")
node2 = Node("102")
node3 = Node("103")
# 连接节点
node1.next = node2
node2.next = node3
# 设置链表头部
list_head = node1
# 遍历链表并输出数据
current = list_head
while current:
print(current.data)
current = current.next
# 输出:
# 101
# 102
# 103
栈 (Stack)
栈是一种元素集合，遵循LIFO（后进先出）原则：最后添加的最先删除。
操作复杂度：插入（push）和删除（pop） — O(1)。
示例：实现和使用栈来检查括号的平衡
def is_balanced(expression):
stack = []
opening = "({["
closing = ")}]"
pairs = {")": "(", "}": "{", "]": "["}
for char in expression:
if char in opening:
stack.append(char)
elif char in closing:
if not stack or stack.pop() != pairs[char]:
return False
return len(stack) == 0
# 检查不同的表达式
print(is_balanced("({[]})")) # 输出: True
print(is_balanced("([)]")) # 输出: False
print(is_balanced("((")) # 输出: False
队列 (Queue)
队列是一个元素的集合，遵循FIFO（先进先出）原则：最先添加的最先删除。
操作复杂度：插入（enqueue）和删除（dequeue） — O(1)。
示例：实现和使用队列来模拟任务处理
from collections import deque
class TaskQueue:
def __init__(self):
self.queue = deque()
def add_task(self, task):
self.queue.append(task)
print(f"任务 '{task}' 已添加到队列")
def process_task(self):
if self.queue:
task = self.queue.popleft()
print(f"处理任务: '{task}'")
else:
print("队列为空")
def display_queue(self):
print("当前任务队列:", list(self.queue))
# 创建和使用任务队列
task_queue = TaskQueue()
task_queue.add_task("发送邮件")
task_queue.add_task("更新数据库")
task_queue.add_task("创建报告")
task_queue.display_queue()
task_queue.process_task()
task_queue.process_task()
task_queue.display_queue()
# 输出:
# 任务 '发送邮件' 已添加到队列
# 任务 '更新数据库' 已添加到队列
# 任务 '创建报告' 已添加到队列
# 当前任务队列: ['发送邮件', '更新数据库', '创建报告']
# 处理任务: '发送邮件'
# 处理任务: '更新数据库'
# 当前任务队列: ['创建报告']
3.3 不同数据结构类型的区别
以下是不同类型数据结构的关键区别：
数组:
- 访问: 快速的索引访问 —
O(1)。 - 改变大小: 固定大小，增加需要复制所有元素 —
O(n)。 - 适用于: 随机访问元素，当数据大小是预先已知的。
链表:
- 访问: 慢速索引访问 —
O(n)。 - 改变大小: 易于更改大小，插入和删除只需
O(1)。 - 适用于: 经常添加和删除元素。
栈:
- 工作原理:
LIFO。 - 操作: 仅在一端进行插入和删除 —
O(1)。 - 适用于: 任务的反向顺序执行，函数调用管理。
队列:
- 工作原理:
FIFO。 - 操作: 在不同的两端进行插入和删除 —
O(1)。 - 适用于: 按任务到达顺序进行管理。
3.4 不同数据结构的应用
不同数据结构在实际中的应用示例：
数组
存储固定长度的数据，例如一周中的天或一年中的月份。
示例：使用数组处理一周中的天
# 创建一个星期数组
days = ["星期一", "星期二", "星期三", "星期四", "星期五", "星期六", "星期天"]
# 按索引获取星期几（例如第三天）
print(days[2]) # 输出: 星期三
# 修改一天的名称
days[0] = "星期一 (一周的开始)"
print(days[0]) # 输出: 星期一 (一周的开始)
# 遍历一周中的所有天
for day in days:
print(day)
# 输出:
# 星期一 (一周的开始)
# 星期二
# 星期三
# 星期四
# 星期五
# 星期六
# 星期天
链表
实现动态集合，其中可以从集合的中间添加和删除元素。
示例：实现和使用链表存储待办事项
class TodoItem:
def __init__(self, task):
self.task = task
self.next = None
class TodoList:
def __init__(self):
self.head = None
def add_task(self, task):
new_item = TodoItem(task)
if not self.head:
self.head = new_item
else:
current = self.head
while current.next:
current = current.next
current.next = new_item
def display_tasks(self):
current = self.head
if not current:
print("待办事项列表为空")
else:
while current:
print(f"- {current.task}")
current = current.next
# 创建和使用待办事项列表
todo = TodoList()
todo.add_task("买菜")
todo.add_task("打电话给妈妈")
todo.add_task("准备演示文稿")
print("我的待办事项列表:")
todo.display_tasks()
# 输出:
# 我的待办事项列表:
# - 买菜
# - 打电话给妈妈
# - 准备演示文稿
栈
任务的反向顺序执行，例如递归中的函数调用处理、撤销操作。
示例：使用栈反转字符串
def reverse_string(s):
stack = []
# 将字符串中的每个字符放入栈中
for char in s:
stack.append(char)
reversed_s = ''
# 从栈中取出字符，形成反转字符串
while stack:
reversed_s += stack.pop()
return reversed_s
# 示例使用
original = "Hello, World!"
reversed_str = reverse_string(original)
print(f"原始字符串: {original}")
print(f"反转的字符串: {reversed_str}")
# 输出:
# 原始字符串: Hello, World!
# 反转的字符串: !dlroW ,olleH
队列
按顺序处理任务，例如打印机任务、客户服务队列。
示例：模拟文档打印队列
from collections import deque
class PrinterQueue:
def __init__(self):
self.queue = deque()
def add_document(self, document):
self.queue.append(document)
print(f"文档 '{document}' 已加入打印队列")
def print_document(self):
if self.queue:
document = self.queue.popleft()
print(f"打印文档: '{document}'")
else:
print("打印队列为空")
def display_queue(self):
print("当前打印队列:", list(self.queue))
# 创建和使用打印队列
printer = PrinterQueue()
printer.add_document("报告")
printer.add_document("演示文稿")
printer.add_document("合同")
printer.display_queue()
printer.print_document()
printer.print_document()
printer.display_queue()
# 输出:
# 文档 '报告' 已加入打印队列
# 文档 '演示文稿' 已加入打印队列
# 文档 '合同' 已加入打印队列
# 当前打印队列: ['报告', '演示文稿', '合同']
# 打印文档: '报告'
# 打印文档: '演示文稿'
# 当前打印队列: ['合同']
在这个例子中，我们创建了一个简单的打印队列模拟。文件按到达顺序加入队列并打印，展示了FIFO（先进先出）原则。
GO TO FULL VERSION