数据结构与算法——数据结构(python)

事实上，入门算法最好是从C/C++入手，对于一些数据结构可以有更深刻的理解，这篇笔记只是由于博主参加蓝桥杯报名的python组而去进行的粗浅学习，放在这里仅仅是作为”撑场面”的存在，如果让我现在再学习我会推荐https://labuladong.online/algo/home/

• 数据结构是指相互间存在一种或多种关系的数据元素的集合和该集合元素之间的关系组成

• 简单来说，数据结构就是数据以什么方式存储于计算机中

• 列表，集合，字典及元组都是一种数据结构

• 数据结构的分类：

  • 线性结构：结构中元素存在一对一的相互关系
  • 树结构：一对多
  • 图结构：多对多

线性结构

1.列表

• 列表与数组的区别

​ 数组元素类型固定，且声明后长度固定(因为数组是申请的是连续内存地址)

​ 列表元素类型不固定，长度可变(列表申请的是离散的内存地址)

• 列表的python内置方法

​ append O(1)

​ insert、remove O(n)

2.栈

栈的特点：后进先出LIFO

栈的基本操作：

• 压栈 push
• 出栈 pop
• 取栈顶 gettop

栈的python实现：

• push li.append
• pop li.pop
• gettop li[-1]

class stack:
    def __init__(self):
        self.stack = []
   	def push(self, element):
        self.stack.append(element)
   	def pop(self):
        return self.stack.pop()
    def get_top(self):
        if len(self.stack) > 0:
        	return self.stack[-1]
    	else:
			return None
   	def is_empty(self):
        return len(self.stack) == 0

栈的应用——括号匹配问题

def brace_match(str):
   	stack = Stack()
    for ch in str:
        if ch in {'(','[','{'}:
            stack.push(ch)
        elif ch == ')':
            if stack.get_top == '(':
                stack.pop()
            else:
                return "不匹配"
     	elif  ch == ']':
            if stack.get_eop == '[':
                stack.pop()
            else:
                return "不匹配"
       	elif ch == '}':
            if stack.get_eop == '{':
                stack.pop()
           	else:
                return "不匹配"
   	if stack.get_top == None:
        return "匹配"
#或者我们可以使用字典简化工作：
def brace_match(str):
    match = {')':'(', ']':'[', '}':'{'}
   	for ch in str:
        if ch in {'(','[','{'}:
            stack.push(ch)
        else:
            if stack.is_empty():
                return False
            elif stack.get_top() == match[ch]:
                stack.pop()
            else:
                return False
  	if stack.is_empty():
        return True
    else:
        return False

3.队列

队列的性质：先进先出 FIFO

队列的python实现：

• 线性队列：

  • 入队简单，但是出队时pop方法时间复杂度太高
  • 如果使用下标界定队列而不pop，会导致多次进行队列操作后列表过长，吃内存

• 环形队列：

  • 尽管仍然是用列表实现的，环形队列规定了队列的长度，类似C的数组操作，先申请一块确定的空间

  • 这样一来就可以用下标的增减来表示队列的出入

• 环形队列的实现：

class Queue:
    def __init__(self, size): #传入的size表示队列的长度
        self.queue = [0 for _ in range(size+1)]
        self.rear = 0 #队尾指针，永远指向最后一个数
        self.front = 0 #队首指针，永远指向队首前一个的地址
        self.size = size+1	#self.size表示申请的空间长度
   	def push(self,element):
        if not self.is_filled():
	        self.rear = (self.rear+1) % self.size
    	    self.queue[self.rear] = element
        else:
            raise IndexError("Queue is filled!")
    def pop(self):
        if not self,is_empty():
        	self.front = (self.front+1) % self.size
        	return self.queue[self.front]
        else:
            raise IndexError("Queue is empty!")
    def is_empty(self):
        return self.front == self.rear
    def is_filled(self):
        return (self.rear+1) % self.size == self.front

队列的python内置模块

from collections import deque
#单向队列
q = deque()
q.append(element)	#队尾进队
q.popleft() #队首出列

#双向队列
q.qppendleft(element)	#队首进队
q,pop()	#队尾出列

#deque(param1,param2)
#param1传入列表，作为初始的队列
#param2传入队列最大长度，如果列表长度大于param2，则出队知道满足即可
#由此我们可以完成比如Linux的tail命令

4.栈与队列的应用——迷宫问题

栈——深度优先搜索

• 回溯法：从一个节点中任意找下一个能走的点，当找不到能走的点时，退回上一个节点，直到有一个节点能找到下一个且不重复的方向
• 可以使用栈结构储存路径

def maze_patch(maze,start,end):
    rows,cols = len(maze), len(maze[0])
    dirs = [(-1,0),(0,1),(1,0),(0,-1)]
    stack = [start]
    
    while stack:
        Node = stack[-1] #取到当前位置节点
        
        if Node == end:
            return stack
        
        maze[Node[0]][Node[1]] = 2
        for x,y in dirs:
            Node[0] += x	#这里开始的Node是NextNode
            Node[1] += y
            if 0<=Node[0]<=rows and 0<=Node[1]<=cols and maze[Node[0]][Node[1]]==0:
                stack.append(Node)
            else:
                stack.pop()  #这里pop出去的是原来的Node
   	return False

队列——广度优先搜索

def bfs_maze_path(maze, start, end):
    rows, cols = len(maze), len(maze[0])
    directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]  # 上、下、左、右
    queue = deque([start])  # BFS 使用队列
    parent = {start: None}  # 记录路径

    while queue:
        x, y = queue.popleft()  # 取队首元素

        if (x, y) == end:  # 找到出口
            path = []
            while parent[(x, y)] is not None:  # 回溯路径
                path.append((x, y))
                (x, y) = parent[(x, y)]
            return path[::-1]  # 逆序返回路径

        maze[x][y] = 2  # 标记已访问

        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < rows and 0 <= ny < cols and maze[nx][ny] == 0:
                queue.append((nx, ny))
                parent[(nx, ny)] = (x, y)  # 记录父节点
                maze[nx][ny] = 2  # 避免重复入队     
				#注意这里并没有break，会找到该节点所有可能的地方，并且将该节点出队，也就是说按照出队的节点算会依次查看可能的节点的可能节点

    return None  # 无解

5.链表

链表操作(以单链表为例)

1. 定义节点

class ListNode:
    def __init__(self,val):
        self.val = val
        self.next = None
#节点的定义与C语言很相似，只不过省去了申请内存空间的操作

2. 定义链表

class LinkedList:
    def __init__(self):
        self.head = None

3. 插入节点

#头插法
def insert_at_head(self,val):
    new_node = ListNode(val)
   	new_node.next = self.head
    self.head = new_node
#尾插法
def insert_at_tail(self,val):
    new_node = ListNode(val)
    
    if not self.head:	#if self.head == None
        self.head = new_node
    	return
    
    temp = self.head
    
    while temp.next:
        temp = temp.next
  	temp.next = new_node
#这里头插法与尾插法不同的原因是，头插法可以保持head节点永远是头节点，但是尾插法类似头插法写的话会导致head节点永远是尾节点，在链表中我们需要head节点来进行链表的锚定

#特定位置的插入
def insert_at_position(self,val,pos): #链表仍然是从0开始数
    new_node = ListNode(val)
    if not self.head:
        self.head = new_node
        return 
    
    temp = self.head
    
    for _ in range(pos-1):	
        if not temp:
            return None
        temp = temp.next
   	new_node.next = temp.next
    temp.next = new_node

4. 删除节点

#删除头节点
def delete_head(self):
    if self.head:
    	self.head = self.head.next
    else:
        return None
#删除尾节点
def delete_tail(self):
    if not self.head:
        return 
    
    temp = self.head
    
    while temp.next:
        temp = temp.next
   	temp = None
#删除指定值的节点
def delete_by_value(self,val):
    if not self.head:
        return 
   	if self.head.val == val:
        self.head = self.head.next
        return 
    
    cur = self.head
    
    while temp.next:
        if cur.next.val == val:
            cur.next = cur.next.next
            return 

5. 查找节点

#按值查找
def search_by_value(self,val):
    if not self.head:
        return False
    if self.head.val == val:
        return {"position":0,"value":val}
    
    cnt = 0
    temp = self.head.next
    
    while temp:
        cnt += 1
        if temp.next.val == val:
            return {"position":cnt,"value":val}
  		temp = temp.next
  	return False
#按位置查找
def search_by_position(self,pos):
    if not self.head:
        return False
    
    temp = self.head
    
    for _ in range(pos):
        if not temp:
            return None
        temp = temp.next
  	return {"position":pos,"value":temp.val}

6.哈希表

哈希表（hash table），又称散列表，它通过建立键 key 与值 value 之间的映射，实现高效的元素查询。具体而言，我们向哈希表中输入一个键 key ，则可以在 O(1) 时间内获取对应的值 value 。

1.哈希表的基础实现

事实上，python的字典结构就是基于哈希表实现的一种散列表，但这并不是说在python中只有字典可以实现哈希表操作，为了加深理解，以下根据列表这种最基本的数据结构实现哈希表：

在哈希表中，每一个列表的空位称为一个**”哈希桶“**，构建哈希表就是将键值对的键key映射到哈希桶的下标，将值value映射到哈希桶中的过程，列表的长度，也就是哈希桶的个数称为哈希容量n

class Hash:
    
    def __init__(self,size=100):	#以100个哈希桶为例
       	self.hash_buckets = [None for _ in range(100)]
    
    def insert(key,val):	
        self.hash_buckets[key] = val

这样一来会出现一些问题，比如一个键值对1000000000000：1，当key过大时，这个哈希桶集需要申请的内存空间过大，针对这个问题，我们可以对其进行**“取模”**，模数为哈希桶集的长度，这样就可以保证每一个key一定可以找到对应的哈希桶下标与之对应

但是这样一来又会出现新的问题，比如1003：1和12303：3这样的两个不同键值对会存在同一个哈希桶，像这样的问题，我们称之为**”哈希冲突“**。

容易想到，哈希容量n越大，越不容易出现哈希冲突，增加哈希容量的过程称为**“扩容”，由此引申出“负载因子”**的概念，负载因子=哈希表元素数量/哈希桶数量，用于表述哈希冲突的大小，一般来说当负载因子>0.75时，哈希表进行扩容

2.哈希冲突的解决

1.链地址法

在原始哈希表中，一个哈希桶仅能存一个键值对，在链地址法中我们将哈希桶的元素转换为链表，将冲突的键值对储存在链表里即可

from typing import Optional

class ListNode:
    """链表节点类"""
    def __init__(self, key: int, val: str, next: Optional["ListNode"] = None):
        self.key = key
        self.val = val
        self.next = next  # 指向下一个节点

class HashMapChaining:
    """基于链表的链式地址哈希表"""

    def __init__(self):
        """构造方法"""
        self.size = 0  # 当前存储的键值对数量
        self.capacity = 4  # 哈希表初始容量
        self.load_thres = 2.0 / 3.0  # 负载因子阈值
        self.extend_ratio = 2  # 扩容倍数
        self.buckets = [None] * self.capacity  # 使用 None 代表空桶

    def hash_func(self, key: int) -> int:
        """哈希函数"""
        return key % self.capacity

    def load_factor(self) -> float:
        """计算负载因子"""
        return self.size / self.capacity

    def get(self, key: int) -> Optional[str]:
        """查询操作"""
        index = self.hash_func(key)
        node = self.buckets[index]
        while node:
            if node.key == key:
                return node.val  # 找到 key，返回 value
            node = node.next
        return None  # 未找到 key，返回 None

    def put(self, key: int, val: str):
        """添加或更新操作"""
        if self.load_factor() > self.load_thres:
            self.extend()
        index = self.hash_func(key)
        node = self.buckets[index]

        # 遍历链表，若 key 存在则更新
        while node:
            if node.key == key:
                node.val = val
                return
            node = node.next

        # 头插法插入新键值对
        new_node = ListNode(key, val, self.buckets[index])
        self.buckets[index] = new_node
        self.size += 1

    def remove(self, key: int):
        """删除操作"""
        index = self.hash_func(key)
        node = self.buckets[index]
        prev = None  # 记录前驱节点

        while node:
            if node.key == key:
                if prev:
                    prev.next = node.next  # 断链
                else:
                    self.buckets[index] = node.next  # 头节点被删除
                self.size -= 1
                return
            prev, node = node, node.next  # 继续向后查找

    def extend(self):
        """扩容哈希表"""
        old_buckets = self.buckets
        self.capacity *= self.extend_ratio
        self.buckets = [None] * self.capacity
        self.size = 0

        for node in old_buckets:
            while node:
                self.put(node.key, node.val)  # 重新哈希并插入新桶
                node = node.next

    def print(self):
        """打印哈希表"""
        for i, node in enumerate(self.buckets):
            res = []
            while node:
                res.append(f"{node.key} -> {node.val}")
                node = node.next
            print(f"Bucket {i}: {', '.join(res)}" if res else f"Bucket {i}: Empty")


# 测试代码
hmap = HashMapChaining()
hmap.put(1, "A")
hmap.put(5, "B")
hmap.put(9, "C")
hmap.print()
print("Get key 5:", hmap.get(5))  # 输出 "B"
hmap.remove(5)
hmap.print()

值得注意的是，当链表很长时，查询效率 O(n) 很差。此时可以将链表转换为“AVL 树”或“红黑树”，从而将查询操作的时间复杂度优化至 O(log⁡n) 。

2.开放寻址(不推荐)

1. 线性探测

线性探测采用固定步长的线性搜索来进行探测，其操作方法与普通哈希表有所不同。

• 插入元素：通过哈希函数计算桶索引，若发现桶内已有元素，则从冲突位置向后线性遍历（步长通常为 1 ），直至找到空桶，将元素插入其中。
• 查找元素：若发现哈希冲突，则使用相同步长向后进行线性遍历，直到找到对应元素，返回 value 即可；如果遇到空桶，说明目标元素不在哈希表中，返回 None 。

然而，线性探测容易产生“聚集现象”。具体来说，数组中连续被占用的位置越长，这些连续位置发生哈希冲突的可能性越大，从而进一步促使该位置的聚堆生长，形成恶性循环，最终导致增删查改操作效率劣化。

值得注意的是，我们不能在开放寻址哈希表中直接删除元素。这是因为删除元素会在数组内产生一个空桶 None ，而当查询元素时，线性探测到该空桶就会返回，因此在该空桶之下的元素都无法再被访问到，程序可能误判这些元素不存在

为了解决该问题，我们可以采用懒删除（lazy deletion）机制：它不直接从哈希表中移除元素，而是利用一个常量 TOMBSTONE 来标记这个桶。在该机制下，None 和 TOMBSTONE 都代表空桶，都可以放置键值对。但不同的是，线性探测到 TOMBSTONE 时应该继续遍历，因为其之下可能还存在键值对。

然而，懒删除可能会加速哈希表的性能退化。这是因为每次删除操作都会产生一个删除标记，随着 TOMBSTONE 的增加，搜索时间也会增加，因为线性探测可能需要跳过多个 TOMBSTONE 才能找到目标元素。

为此，考虑在线性探测中记录遇到的首个 TOMBSTONE 的索引，并将搜索到的目标元素与该 TOMBSTONE 交换位置。这样做的好处是当每次查询或添加元素时，元素会被移动至距离理想位置（探测起始点）更近的桶，从而优化查询效率。

以下代码实现了一个包含懒删除的开放寻址（线性探测）哈希表。为了更加充分地使用哈希表的空间，我们将哈希表看作一个“环形数组”，当越过数组尾部时，回到头部继续遍历。

2. 平方探测

平方探测与线性探测类似，都是开放寻址的常见策略之一。当发生冲突时，平方探测不是简单地跳过一个固定的步数，而是跳过“探测次数的平方”的步数，即 1,4,9,… 步。

平方探测主要具有以下优势。

• 平方探测通过跳过探测次数平方的距离，试图缓解线性探测的聚集效应。
• 平方探测会跳过更大的距离来寻找空位置，有助于数据分布得更加均匀。

然而，平方探测并不是完美的。

• 仍然存在聚集现象，即某些位置比其他位置更容易被占用。
• 由于平方的增长，平方探测可能不会探测整个哈希表，这意味着即使哈希表中有空桶，平方探测也可能无法访问到它。

3. 多次哈希

顾名思义，多次哈希方法使用多个哈希函数 f1(x)、f2(x)、f3(x)、… 进行探测。

• 插入元素：若哈希函数 f1(x) 出现冲突，则尝试 f2(x) ，以此类推，直到找到空位后插入元素。
• 查找元素：在相同的哈希函数顺序下进行查找，直到找到目标元素时返回；若遇到空位或已尝试所有哈希函数，说明哈希表中不存在该元素，则返回 None 。

与线性探测相比，多次哈希方法不易产生聚集，但多个哈希函数会带来额外的计算量。

Tip

请注意，开放寻址（线性探测、平方探测和多次哈希）哈希表都存在“不能直接删除元素”的问题。

3.哈希函数

在上述的代码中，当我们计算桶下标index时并不是直接模桶的长度，而是先对key进行哈希算法的变换得到hash(key)，这是因为，我们倾向于将不同的key均匀分布于哈希桶，也就是让哈希冲突尽可能少，只有这样，我们在哈希表中的搜索，删除，添加操作的时间复杂度才会趋近于O(1)，在极端情况下，也就是所有的键值对存在于同一个哈希桶中，此时，搜索删除添加操作的时间复杂度会达到O(n)。

因此，我们使用哈希算法对key的值进行一个混淆与扩散，常用的哈希算法如下：

表 6-2 常见的哈希算法

	MD5	SHA-1	SHA-2	SHA-3
推出时间	1992	1995	2002	2008
输出长度	128 bit	160 bit	256/512 bit	224/256/384/512 bit
哈希冲突	较多	较多	很少	很少
安全等级	低，已被成功攻击	低，已被成功攻击	高	高
应用	已被弃用，仍用于数据完整性检查	已被弃用	加密货币交易验证、数字签名等	可用于替代 SHA-2

7.树

1.二叉树

1.二叉树基本概念

二叉树（binary tree）是一种非线性数据结构，代表“祖先”与“后代”之间的派生关系，体现了“一分为二”的分治逻辑。与链表类似，二叉树的基本单元是节点，每个节点包含值、左子节点引用和右子节点引用。

每个节点都有两个引用（指针），分别指向左子节点（left-child node）和右子节点（right-child node），该节点被称为这两个子节点的父节点（parent node）。当给定一个二叉树的节点时，我们将该节点的左子节点及其以下节点形成的树称为该节点的左子树（left subtree），同理可得右子树（right subtree）

在二叉树中，除叶节点外，其他所有节点都包含子节点和非空子树。

• 根节点（root node）：位于二叉树顶层的节点，没有父节点。
• 叶节点（leaf node）：没有子节点的节点，其两个指针均指向 None 。
• 边（edge）：连接两个节点的线段，即节点引用（指针）。
• 节点所在的层（level）：从顶至底递增，根节点所在层为 1 。
• 节点的度（degree）：节点的子节点的数量。在二叉树中，度的取值范围是 0、1、2 。
• 二叉树的高度（height）：从根节点到最远叶节点所经过的边的数量。
• 节点的深度（depth）：从根节点到该节点所经过的边的数量。
• 节点的高度（height）：从距离该节点最远的叶节点到该节点所经过的边的数量。

2.二叉树基本操作

#定义二叉树类
class TreeNode:
    def __init__(self,val: int):
        self.val: int = val
        self.left: TreeNode | None = None 
        self.right: TreeNode | None = None
#初始化
# 初始化二叉树
# 初始化节点
n1 = TreeNode(val=1)
n2 = TreeNode(val=2)
n3 = TreeNode(val=3)
n4 = TreeNode(val=4)
n5 = TreeNode(val=5)
# 构建节点之间的引用（指针）
n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5

#插入与删除
# 插入与删除节点
p = TreeNode(0)
# 在 n1 -> n2 中间插入节点 P
n1.left = p
p.left = n2
# 删除节点 P
n1.left = n2
#需要注意的是，插入与删除一般是一起的，因为删除会导致删除该节点的同时删除其子树

3.二叉树类型

1. 满二叉树

2. 完全二叉树

3. 完满二叉树

4. 平衡二叉树

4.二叉树的退化

二叉树的最佳结构与最差结构

	完美二叉树	链表
第 i 层的节点数量	2i−1	1
高度为 h 的树的叶节点数量	2h	1
高度为 h 的树的节点总数	2h+1−1	h+1
节点总数为 n 的树的高度	log2⁡(n+1)−1	n−1