数据结构入门模板

server/2025/1/21 18:09:57/

一、栈（Stack）

定义

栈是一种**后进先出（LIFO，Last In First Out）**的数据结构。插入和删除操作只能在栈顶进行。

特点

  1. 只能从栈顶操作数据。
  2. 操作简单，时间复杂度为 O ( 1 ) O(1) O(1)。

应用场景

  • 表达式求值（如括号匹配）。
  • 深度优先搜索（DFS）。

时间复杂度

操作时间复杂度
入栈（push） O ( 1 ) O(1) O(1)
出栈（pop） O ( 1 ) O(1) O(1)
访问栈顶元素 O ( 1 ) O(1) O(1)

案例：括号匹配

问题描述：给定一个只包含 ( 和 ) 的字符串，判断括号是否匹配。

C++实现：

#include <iostream>
#include <stack>
using namespace std;bool isValid(string s) {stack<char> stk;for (char c : s) {if (c == '(') {stk.push(c);} else {if (stk.empty() || stk.top() != '(') {return false;}stk.pop();}}return stk.empty();
}int main() {string s = "(())";cout << (isValid(s) ? "Valid" : "Invalid") << endl;return 0;
}

Python实现：

def is_valid(s):stack = []for c in s:if c == '(':stack.append(c)else:if not stack or stack[-1] != '(':return Falsestack.pop()return len(stack) == 0s = "(())"
print("Valid" if is_valid(s) else "Invalid")

Java实现：

import java.util.Stack;public class Main {public static boolean isValid(String s) {Stack<Character> stack = new Stack<>();for (char c : s.toCharArray()) {if (c == '(') {stack.push(c);} else {if (stack.isEmpty() || stack.peek() != '(') {return false;}stack.pop();}}return stack.isEmpty();}public static void main(String[] args) {String s = "(())";System.out.println(isValid(s) ? "Valid" : "Invalid");}
}

二、队列（Queue）

定义

队列是一种**先进先出（FIFO，First In First Out）**的数据结构，插入操作在队尾，删除操作在队首。

特点

  1. 操作受限。
  2. 时间复杂度为 O ( 1 ) O(1) O(1)。

应用场景

  • 任务调度。
  • 宽度优先搜索（BFS）。

时间复杂度

操作时间复杂度
入队 O ( 1 ) O(1) O(1)
出队 O ( 1 ) O(1) O(1)

案例：二叉树的层序遍历

问题描述：按层序输出二叉树的节点值。

C++实现：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> result;if (!root) return result;queue<TreeNode*> q;q.push(root);while (!q.empty()) {int size = q.size();vector<int> level;for (int i = 0; i < size; ++i) {TreeNode* node = q.front(); q.pop();level.push_back(node->val);if (node->left) q.push(node->left);if (node->right) q.push(node->right);}result.push_back(level);}return result;
}int main() {TreeNode* root = new TreeNode(1);root->left = new TreeNode(2);root->right = new TreeNode(3);vector<vector<int>> result = levelOrder(root);for (const auto& level : result) {for (int val : level) {cout << val << " ";}cout << endl;}return 0;
}

Python实现：

from collections import dequedef level_order(root):if not root:return []result, queue = [], deque([root])while queue:level = []for _ in range(len(queue)):node = queue.popleft()level.append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)result.append(level)return result# TreeNode class definition
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightroot = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(level_order(root))

Java实现：

import java.util.*;class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }
}public class Main {public static List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> result = new ArrayList<>();if (root == null) return result;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int size = queue.size();List<Integer> level = new ArrayList<>();for (int i = 0; i < size; i++) {TreeNode node = queue.poll();level.add(node.val);if (node.left != null) queue.offer(node.left);if (node.right != null) queue.offer(node.right);}result.add(level);}return result;}public static void main(String[] args) {TreeNode root = new TreeNode(1);root.left = new TreeNode(2);root.right = new TreeNode(3);System.out.println(levelOrder(root));}
}

三、堆（Heap）

定义

堆是一种基于树的数据结构，分为最大堆和最小堆：

  • 最大堆：根节点值大于给定树中所有子节点的值。
  • 最小堆：根节点值小于给定树中所有子节点的值。

通常使用堆实现一些需要自动索引的场景，如优先队列。

特点

  1. 深度为 ⌊ log ⁡ n ⌋ \lfloor \log n \rfloor ⌊logn⌋，操作时间复杂度为 O ( log ⁡ n ) O(\log n) O(logn)。
  2. 通常用数组表示，父节点、左子节点和右子节点与索引关系为：
    • 父节点： parent ( i ) = ⌊ ( i − 1 ) / 2 ⌋ \text{parent}(i) = \lfloor (i-1)/2 \rfloor parent(i)=⌊(i−1)/2⌋
    • 左子节点： left ( i ) = 2 i + 1 \text{left}(i) = 2i + 1 left(i)=2i+1
    • 右子节点： right ( i ) = 2 i + 2 \text{right}(i) = 2i + 2 right(i)=2i+2

应用场景

  • 优先队列（Priority Queue）
  • 最大/最小 K 问题

时间复杂度

操作时间复杂度
插入（insert） O ( log ⁡ n ) O(\log n) O(logn)
删除（delete） O ( log ⁡ n ) O(\log n) O(logn)
取最大/最小值 O ( 1 ) O(1) O(1)

案例：前 K 个最大元素

问题描述：给定一个数组，找到其中前 K 个最大元素。

C++实现：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;vector<int> topKElements(vector<int>& nums, int k) {priority_queue<int, vector<int>, greater<int>> minHeap;for (int num : nums) {minHeap.push(num);if (minHeap.size() > k) {minHeap.pop();}}vector<int> result;while (!minHeap.empty()) {result.push_back(minHeap.top());minHeap.pop();}return result;
}int main() {vector<int> nums = {3, 2, 1, 5, 6, 4};int k = 2;vector<int> result = topKElements(nums, k);for (int val : result) {cout << val << " ";}cout << endl;return 0;
}

Python实现：

import heapqdef top_k_elements(nums, k):return heapq.nlargest(k, nums)nums = [3, 2, 1, 5, 6, 4]
k = 2
print(top_k_elements(nums, k))

Java实现：

import java.util.*;public class Main {public static List<Integer> topKElements(int[] nums, int k) {PriorityQueue<Integer> minHeap = new PriorityQueue<>();for (int num : nums) {minHeap.offer(num);if (minHeap.size() > k) {minHeap.poll();}}List<Integer> result = new ArrayList<>(minHeap);Collections.sort(result, Collections.reverseOrder());return result;}public static void main(String[] args) {int[] nums = {3, 2, 1, 5, 6, 4};int k = 2;System.out.println(topKElements(nums, k));}
}

下面是并查集和树状数组的内容，整合到现有文档中：

四、并查集（Union-Find）

定义

并查集是一种用于处理动态连通性问题的数据结构，主要支持以下两种操作：

  1. **合并：将两个元素所在的集合合并。
  2. 查找：查询某个元素属于哪个集合。

特点

  1. 常用于解决连通性问题（如网络连通、图的连通分量）。
  2. 通过路径压缩和按秩合并优化，时间复杂度接近 O ( 1 ) O(1) O(1)。

应用场景

  • 判断无向图是否有环。
  • 网络连通性问题。
  • 最小生成树（Kruskal算法）。

时间复杂度

操作时间复杂度
查找 O ( l o g ( n ) ) O(log(n)) O(log(n))
合并 O ( l o g ( n ) ) O(log(n)) O(log(n))

案例：判断图是否连通

问题描述：给定包含 n 个节点的无向图，以及一些边，判断图是否是连通的。

C++实现：

#include <iostream>
#include <vector>
using namespace std;class UnionFind {
public:UnionFind(int n) : parent(n), rank(n, 1) {for (int i = 0; i < n; ++i) parent[i] = i;}int find(int x) {if (x != parent[x]) {parent[x] = find(parent[x]); // 路径压缩}return parent[x];}void unionSet(int x, int y) {int rootX = find(x);int rootY = find(y);if (rootX != rootY) {if (rank[rootX] > rank[rootY]) {parent[rootY] = rootX;} else if (rank[rootX] < rank[rootY]) {parent[rootX] = rootY;} else {parent[rootY] = rootX;rank[rootX]++;}}}private:vector<int> parent, rank;
};int main() {UnionFind uf(5);uf.unionSet(0, 1);uf.unionSet(1, 2);cout << (uf.find(0) == uf.find(2) ? "Connected" : "Not Connected") << endl;return 0;
}

Python实现：

class UnionFind:def __init__(self, n):self.parent = list(range(n))self.rank = [1] * ndef find(self, x):if x != self.parent[x]:self.parent[x] = self.find(self.parent[x])  # 路径压缩return self.parent[x]def union(self, x, y):rootX = self.find(x)rootY = self.find(y)if rootX != rootY:if self.rank[rootX] > self.rank[rootY]:self.parent[rootY] = rootXelif self.rank[rootX] < self.rank[rootY]:self.parent[rootX] = rootYelse:self.parent[rootY] = rootXself.rank[rootX] += 1uf = UnionFind(5)
uf.union(0, 1)
uf.union(1, 2)
print("Connected" if uf.find(0) == uf.find(2) else "Not Connected")

Java实现：

class UnionFind {private int[] parent;private int[] rank;public UnionFind(int n) {parent = new int[n];rank = new int[n];for (int i = 0; i < n; i++) {parent[i] = i;rank[i] = 1;}}public int find(int x) {if (x != parent[x]) {parent[x] = find(parent[x]); // 路径压缩}return parent[x];}public void union(int x, int y) {int rootX = find(x);int rootY = find(y);if (rootX != rootY) {if (rank[rootX] > rank[rootY]) {parent[rootY] = rootX;} else if (rank[rootX] < rank[rootY]) {parent[rootX] = rootY;} else {parent[rootY] = rootX;rank[rootX]++;}}}
}public class Main {public static void main(String[] args) {UnionFind uf = new UnionFind(5);uf.union(0, 1);uf.union(1, 2);System.out.println(uf.find(0) == uf.find(2) ? "Connected" : "Not Connected");}
}

五、树状数组（Fenwick Tree）

定义

树状数组是一种用于高效维护数组前缀和的数据结构，支持快速更新和查询操作。

特点

  1. 时间复杂度为 O ( log ⁡ n ) O(\log n) O(logn)。
  2. 适用于动态数组。

应用场景

  • 区间查询和更新。
  • 逆序对计数。

时间复杂度

操作时间复杂度
单点更新 O ( log ⁡ n ) O(\log n) O(logn)
前缀查询 O ( log ⁡ n ) O(\log n) O(logn)

案例：计算数组前缀和

问题描述：支持动态更新和快速前缀和查询。

C++实现：

#include <iostream>
#include <vector>
using namespace std;class FenwickTree {
public:FenwickTree(int n) : tree(n + 1, 0) {}void update(int i, int delta) {while (i < tree.size()) {tree[i] += delta;i += i & -i;}}int query(int i) {int sum = 0;while (i > 0) {sum += tree[i];i -= i & -i;}return sum;}private:vector<int> tree;
};int main() {FenwickTree ft(5);ft.update(1, 5);ft.update(2, 3);cout << ft.query(2) << endl; // 输出8return 0;
}

Python实现：

class FenwickTree:def __init__(self, n):self.tree = [0] * (n + 1)def update(self, i, delta):while i < len(self.tree):self.tree[i] += deltai += i & -idef query(self, i):sum_ = 0while i > 0:sum_ += self.tree[i]i -= i & -ireturn sum_ft = FenwickTree(5)
ft.update(1, 5)
ft.update(2, 3)
print(ft.query(2))  # 输出8

Java实现：

class FenwickTree {private int[] tree;public FenwickTree(int n) {tree = new int[n + 1];}public void update(int i, int delta) {while (i < tree.length) {tree[i] += delta;i += i & -i;}}public int query(int i) {int sum = 0;while (i > 0) {sum += tree[i];i -= i & -i;}return sum;}public static void main(String[] args) {FenwickTree ft = new FenwickTree(5);ft.update(1, 5);ft.update(2, 3);System.out.println(ft.query(2)); // 输出8}
}

http://www.ppmy.cn/server/160253.html

相关文章

网络安全（渗透）

网络安全（渗透）

目录 名词解释 2、相互关系 3. 安全影响 名词解释 1、poc、exp、payload与shellcode POC&#xff08;Proof of Concept&#xff09;&#xff1a; 是一种概念验证代码或演示程序&#xff0c;用于证明漏洞的存在。 主要目的是通过简单的代码或操作向安全研究人员、开发人员…
阅读更多...
WPS生成文件清单，超链接到工作簿文件-Excel易用宝

WPS生成文件清单，超链接到工作簿文件-Excel易用宝

今天一大早&#xff0c;我们老板就心急火燎的来找到我&#xff0c;说这个文件夹中有很多工作簿&#xff0c;每次要打开一个文件都要打开这个文件夹&#xff0c;在密密麻麻的文件中查找&#xff0c;能不能在表格中做一个带超链接的列表&#xff0c;可以点击列表中的工作簿名称就…
阅读更多...
[Bug]libGL.so.1: cannot open shared object file: No such file or directory

[Bug]libGL.so.1: cannot open shared object file: No such file or directory

问题描述&#xff1a; 在服务器环境配置尝试导入 opencv (cv2) 模块时&#xff0c;系统找不到 libGL.so.1 这个共享库文件。这个问题通常出现在 Linux 系统中&#xff0c;特别是当系统缺少必要的图形库时。 (yolov11) python ./configs/yolov11/train.py Traceback (most rec…
阅读更多...
OpenAI秘密重塑机器人军团: 实体AGI的崛起!

OpenAI秘密重塑机器人军团: 实体AGI的崛起!

在人工智能的浪潮中&#xff0c;OpenAI一直是引领者的角色。这家以推进通用人工智能&#xff08;AGI&#xff09;为己任的公司&#xff0c;最近宣布了一项重大战略调整&#xff1a;重组其机器人部门&#xff0c;并计划推出实体AGI智能。这不仅是一次简单的组织架构变动&#xf…
阅读更多...
如何在Mac上使用Brew更新Cursor应用程序

如何在Mac上使用Brew更新Cursor应用程序

在这篇博文中&#xff0c;我们将介绍如何在Mac上更新Cursor应用程序&#xff0c;以及一些相关的使用技巧和功能。 什么是Cursor&#xff1f; Cursor是一款强大的工具&#xff0c;旨在帮助用户更好地编写、编辑和讨论代码。它结合了AI技术&#xff0c;使得编程过程更加高效和便…
阅读更多...
抖音ip属地不准是什么原因？可以改吗

抖音ip属地不准是什么原因？可以改吗

在数字化时代&#xff0c;社交媒体平台如抖音已成为人们日常生活的重要组成部分。随着各大平台对用户隐私和数据安全的日益重视&#xff0c;IP属地的显示功能应运而生。然而&#xff0c;不少抖音用户在使用过程中发现&#xff0c;显示的IP属地与实际位置存在偏差&#xff0c;这…
阅读更多...
Linux初识：【版本控制器Git】【调试器gdb/cgdb使用】

Linux初识：【版本控制器Git】【调试器gdb/cgdb使用】

目录 一.版本控制器Git 1.1版本控制器 1.2Git的操作 1.2.1从远端仓库到本地 1.2.2工作区到本地暂存区 1.2.3本地暂存区到本地仓库 1.2.4本地仓库到远程仓库 1.2.5 .gitignore 1.2.6Windows上操作&#xff08;需要安装Tortoisegit&#xff09; 1.2.7同步远端和当地 二调…
阅读更多...
神经网络：什么是交叉熵？

神经网络：什么是交叉熵？

在机器学习和深度学习中&#xff0c;交叉熵&#xff08;Cross Entropy&#xff09; 是一种常见的损失函数&#xff0c;特别适用于分类问题。尽管这个术语听起来可能有点复杂&#xff0c;但通过一个类比&#xff0c;我们可以更直观地理解它的含义和作用。 类比场景&#xff1a;…
阅读更多...
最新文章

Copyright @ 2022~2023