数据结构 - 计算机基础

01. 数组与链表

数组是最基础的数据结构，使用连续内存存储相同类型的元素。支持 O(1) 随机访问，但插入和删除需要移动元素，时间复杂度为 O(n)。链表使用节点存储数据，每个节点包含数据和指向下一个节点的指针。插入和删除只需修改指针，时间复杂度为 O(1)，但不支持随机访问。选择建议： - 需要频繁随机访问：选择数组 - 需要频繁插入删除：选择链表 - 需要两端操作：选择双端队列

python

# 数组（Python 列表）
arr = [1, 2, 3, 4, 5]
arr.append(6)        # O(1) 均摊
arr.insert(0, 0)     # O(n)
arr.pop()            # O(1)
print(arr[2])        # O(1) 随机访问

# 链表节点定义
class ListNode:
def __init__(self, val=0, next=None):
    self.val = val
    self.next = next

# 创建链表: 1 -> 2 -> 3
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)

# 遍历链表
current = head
while current:
print(current.val, end=" -> ")
current = current.next
print("None")

02. 栈与队列

栈（Stack）是后进先出（LIFO）的数据结构。只能在栈顶进行插入和删除操作。应用：函数调用栈、表达式求值、括号匹配。队列（Queue）是先进先出（FIFO）的数据结构。从队尾插入，从队头删除。应用：任务调度、广度优先搜索、消息队列。双端队列（Deque）两端都可以进行插入和删除操作。

python

# 栈的实现
class Stack:
def __init__(self):
    self.items = []

def push(self, item):
    self.items.append(item)

def pop(self):
    if not self.is_empty():
        return self.items.pop()

def peek(self):
    if not self.is_empty():
        return self.items[-1]

def is_empty(self):
    return len(self.items) == 0

# 使用栈判断括号匹配
def is_valid_parentheses(s):
stack = Stack()
mapping = {')': '(', ']': '[', '}': '{'}

for char in s:
    if char in mapping:
        if stack.is_empty() or stack.pop() != mapping[char]:
            return False
    else:
        stack.push(char)

return stack.is_empty()

print(is_valid_parentheses("()[]{}"))  # True
print(is_valid_parentheses("(]"))      # False

Python 的 list 可以直接当栈使用：append() 入栈，pop() 出栈。

03. 哈希表

哈希表（Hash Table）通过哈希函数将键映射到数组索引，实现近乎 O(1) 的查找、插入和删除。哈希冲突的解决方法： - 链地址法：冲突的元素存储在链表中 - 开放寻址法：冲突时探测下一个空位哈希表广泛应用于：缓存、字典、数据库索引、去重。

python

# Python 字典就是哈希表的实现
hash_map = {}

# 插入 O(1)
hash_map["name"] = "张三"
hash_map["age"] = 25
hash_map["city"] = "北京"

# 查找 O(1)
print(hash_map["name"])  # 张三

# 判断键是否存在
if "age" in hash_map:
print("存在年龄字段")

# 遍历
for key, value in hash_map.items():
print(f"{key}: {value}")

# 简单哈希函数实现
def simple_hash(key, table_size):
hash_value = 0
for char in str(key):
    hash_value += ord(char)
return hash_value % table_size

print(simple_hash("hello", 10))  # 哈希值

知识测验

第 1/5 题正确 0

数组和链表的主要区别是什么？

算法基础