数据结构汇总学习(ing)

本文主要是介绍数据结构汇总学习(ing)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

背景：
数据结构是计算机科学中的一个重要主题，不同的数据结构适用于不同的应用场景。除了线性表和单链表，常见的数据结构还有许多其他类型。下面简要介绍几种常见的数据结构：

栈 (Stack)

特点

后进先出 (LIFO)：最后一个被插入的元素最先被删除。
基本操作：
- push：将元素压入栈顶。
- pop：将栈顶元素弹出。
- peek：查看栈顶元素但不弹出。

应用场景

递归
表达式求值
浏览器历史记录

示例代码

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) == 0def size(self):return len(self.items)

队列 (Queue)

特点

先进先出 (FIFO)：第一个被插入的元素最先被删除。
基本操作：
- enqueue：将元素插入队尾。
- dequeue：将队头元素移出。

应用场景

操作系统的任务调度
打印队列
宽度优先搜索 (BFS)

示例代码

class Queue:def __init__(self):self.items = []def enqueue(self, item):self.items.insert(0, item)def dequeue(self):if not self.is_empty():return self.items.pop()def is_empty(self):return len(self.items) == 0def size(self):return len(self.items)

树 (Tree)

特点

层次结构：树是一种非线性数据结构，由节点和边组成。
基本术语：
- 根节点 (Root)：树的顶端节点。
- 叶子节点 (Leaf)：没有子节点的节点。
- 内部节点 (Internal Node)：有子节点的节点。
- 高度 (Height)：树的最大深度。

常见种类

二叉树 (Binary Tree)：每个节点最多有两个子节点。
二叉搜索树 (BST)：左子树的所有节点小于根节点，右子树的所有节点大于根节点。
平衡树：如 AVL 树、红黑树，保证树的高度较低，提高操作效率。
堆 (Heap)：特殊的完全二叉树，用于实现优先队列。
字典树 (Trie)：用于高效存储和查找字符串集合。

应用场景

数据检索
表达式解析
路径查找

二叉搜索树示例代码

class TreeNode:def __init__(self, key):self.left = Noneself.right = Noneself.value = keyclass BinarySearchTree:def __init__(self):self.root = Nonedef insert(self, key):if self.root is None:self.root = TreeNode(key)else:self._insert(self.root, key)def _insert(self, root, key):if key < root.value:if root.left is None:root.left = TreeNode(key)else:self._insert(root.left, key)else:if root.right is None:root.right = TreeNode(key)else:self._insert(root.right, key)def inorder_traversal(self, root):if root:self.inorder_traversal(root.left)print(root.value, end=" ")self.inorder_traversal(root.right)# 示例使用
bst = BinarySearchTree()
bst.insert(50)
bst.insert(30)
bst.insert(20)
bst.insert(40)
bst.insert(70)
bst.insert(60)
bst.insert(80)bst.inorder_traversal(bst.root)  # 输出: 20 30 40 50 60 70 80

图 (Graph)

特点

顶点和边：图由顶点 (Vertex) 和边 (Edge) 组成，可以表示对象及其关系。
类型：
- 有向图 (Directed Graph)：边有方向。
- 无向图 (Undirected Graph)：边无方向。
- 带权图 (Weighted Graph)：边有权重。

应用场景

社交网络
地图和导航
网络路由

表示方法

邻接矩阵
邻接表

邻接表示例代码

from collections import defaultdictclass Graph:def __init__(self):self.graph = defaultdict(list)def add_edge(self, u, v):self.graph[u].append(v)def bfs(self, start):visited = set()queue = [start]while queue:vertex = queue.pop(0)if vertex not in visited:print(vertex, end=" ")visited.add(vertex)queue.extend([neighbor for neighbor in self.graph[vertex] if neighbor not in visited])def dfs(self, start):visited = set()self._dfs_util(start, visited)def _dfs_util(self, vertex, visited):if vertex not in visited:print(vertex, end=" ")visited.add(vertex)for neighbor in self.graph[vertex]:self._dfs_util(neighbor, visited)# 示例使用
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)print("BFS Traversal:")
g.bfs(2)  # 输出: 2 0 3 1print("\nDFS Traversal:")
g.dfs(2)  # 输出: 2 0 1 3

哈希表 (Hash Table)

特点

快速查找：通过哈希函数将键映射到数组中的位置，从而实现常数时间复杂度的查找、插入和删除操作。
冲突解决：常用的冲突解决方法有链地址法和开放地址法。

应用场景

数据库索引
缓存实现
唯一标识符存储

示例代码

class HashTable:def __init__(self):self.size = 10self.table = [[] for _ in range(self.size)]def _hash(self, key):return hash(key) % self.sizedef insert(self, key, value):index = self._hash(key)for pair in self.table[index]:if pair[0] == key:pair[1] = valuereturnself.table[index].append([key, value])def get(self, key):index = self._hash(key)for pair in self.table[index]:if pair[0] == key:return pair[1]return Nonedef delete(self, key):index = self._hash(key)for i, pair in enumerate(self.table[index]):if pair[0] == key:self.table[index].pop(i)return# 示例使用
hash_table = HashTable()
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)print(hash_table.get("banana"))  # 输出: 2
hash_table.delete("banana")
print(hash_table.get("banana"))  # 输出: None