Posts

栈和队列有哪些特殊的操作？栈和队列能解决什么样的问题？用栈和队列这种数据结构，来解决与“先进先出”、“先进后出”有关的实际问题了，如宽度优先搜索、表达式求值等。 类比 - 日常生活普遍规律 如果桌上有一叠盘子，大家都只会拿最上面的那一个。食堂排队的时候，你总是先找到队尾加入，而排在队首的同学打完饭之后就会离开。 类比计算机，也许只需要在线性序列的一端或两端进行操作，对应的就是栈和队列这两种受限的线性表，他们是最简单的基础数据结构，应用也最广泛。 重点：栈的 LIFO（后进先出） 特性，深度优先搜索，理解递归中栈的作用；队列的 FIFO（先进先出）特性，宽度优先搜索。 难点：机械的递归转非递归，简单理解就可以了，不需要掌握；顺序队列的实现假溢出处理。 栈 在C++程序中，栈（Stack） 是一种非常重要的线性数据结构，它遵循 LIFO（Last In, First Out） 原则，即 后进先出。 一、栈的核心特点 后进先出（LIFO）：最后被添加到栈中的元素，会最先被移除。 只能在一端操作：所有的插入（入栈/Push）和删除（出栈/Pop）操作都发生在栈的同一端，这一端被称为 栈顶（Top）。 另一端是固定的：栈的另一端称为 栈底（Bottom）。 📌 类比： 想象一个放羽毛球的筒： 你只能从筒的开口（栈顶）放入或取出羽毛球。 最后放进去的球，会最先被拿出来。 二、栈的基本操作 操作 描述 push(x) 将元素 x 压入栈顶 pop() 移除并返回栈顶元素 top() / peek() 返回栈顶元素，但不移除 empty() 判断栈是否为空 size() 返回栈中元素的个数 三、C++ 中如何实现栈？ C++ 提供了两种主要方式来使用栈： 1. 使用 STL 容器适配器 std::stack 这是最常用、最推荐的方式。std::stack 是一个容器适配器，默认基于 std::deque 实现。 #include <iostream> #include <stack> int main() { std::stack<int> s; // 创建一个存储 int 类型的栈 s.push(10); // 入栈 s.push(20); s.push(30); std::cout << "栈顶元素: " << s.top() << std::endl; // 输出: 30 s.pop(); // 出栈 std::cout << "新的栈顶元素: " << s.top() << std::endl; // 输出: 20 std::cout << "栈的大小: " << s.size() << std::endl; // 输出: 2 if (!s.empty()) { std::cout << "栈非空" << std::endl; } return 0; } std::stack 的特点： 使用简单，接口清晰。 默认底层容器是 std::deque，也可以指定为 std::vector 或 std::list： std::stack<int, std::vector<int>> s_vec; // 基于 vector std::stack<int, std::list<int>> s_list; // 基于 list 2. 自己用数组或链表实现 虽然不常用，但理解其原理很重要。 ...

单元2 下面是一个简洁的 C++ 程序示例，展示了**顺序表（使用 vector）和链表（使用自定义单向链表）**的基本操作对比，包括插入、删除和访问元素： 🧪 顺序表 vs 链表：C++ 示例对比 ✅ 顺序表（使用 std::vector） #include <iostream> #include <vector> using namespace std; int main() { vector<int> seqList; // 插入元素 seqList.push_back(10); seqList.push_back(20); seqList.push_back(30); // 删除元素（删除第二个） seqList.erase(seqList.begin() + 1); // 访问元素 for (int i = 0; i < seqList.size(); ++i) { cout << "顺序表元素[" << i << "] = " << seqList[i] << endl; } return 0; } ✅ 链表（自定义单向链表） #include <iostream> using namespace std; struct Node { int data; Node* next; Node(int val) : data(val), next(nullptr) {} }; void insert(Node*& head, int val) { Node* newNode = new Node(val); newNode->next = head; head = newNode; } void deleteNode(Node*& head, int val) { Node* curr = head; Node* prev = nullptr; while (curr) { if (curr->data == val) { if (prev) prev->next = curr->next; else head = curr->next; delete curr; return; } prev = curr; curr = curr->next; } } void printList(Node* head) { int index = 0; while (head) { cout << "链表元素[" << index++ << "] = " << head->data << endl; head = head->next; } } int main() { Node* head = nullptr; // 插入元素（头插法） insert(head, 30); insert(head, 20); insert(head, 10); // 删除元素（删除值为 20 的节点） deleteNode(head, 20); // 打印链表 printList(head); return 0; } 📊 对比总结 特性 顺序表（vector） 链表（自定义） 插入效率 中间插入需移动元素，较慢 修改指针即可，效率高 删除效率 删除需移动元素 修改指针即可 随机访问 支持 O(1) 下标访问 需遍历，O(n) 内存结构 连续内存，缓存友好 分散内存，灵活扩展 实现复杂度 简单（STL支持） 需手动管理指针 单链表中，做插入数据的操作时，是否需要同时做两处数据的操作？ 也就是修改前一个数据的后置链接指向，并增加新数据，例如在数据A和B之间插入C，首先要生成新的数据C，其后驱指针指向B，再修改前一个数据A的后驱指针，删除其与B的链接，建立与C的链接。 此外删除操作也是类似的的需要修改两处，该规则适用于双链表和循环链表。 ...

单元1 C++补充知识，关于 C语言与C++编程范式 以及 模板函数与模板类——融合整理为一份清晰系统的总结文章，完整展现 C/C++ 编程思想与核心机制 👇 🧠 C / C++ 编程范式与模板机制详解 一、C语言：典型的面向过程编程 C语言是计算机科学中广泛使用的一种底层语言，其编程范式是 面向过程（Procedure-Oriented Programming, POP）。 📌 面向过程核心理念 程序以“函数”为基本单位，强调从上到下的执行过程 问题被逐步拆解为多个函数，每个函数处理一个子任务 数据结构与操作行为分离，函数通过参数操控数据 🧪 C语言特征简述 特征 描述 模块化设计 使用函数实现各子过程 程序从 main() 执行 顺序调用各个逻辑步骤 struct 仅用于封装数据 不支持行为或方法定义 无类与对象机制 不具备封装、继承、多态 🧱 示例比较：冰箱装大象（C语言方式） openFridge(); putElephant(); closeFridge(); 强调函数的调用流程，数据通过参数传递，不具备对象概念。 二、C++：融合面向过程与面向对象 C++ 是基于 C 语言发展而来的一种多范式语言，既支持面向过程，又强调 面向对象（OOP） 和 泛型编程。 🔍 面向对象编程思想 程序以“对象”为单位组织，强调数据与行为的封装 引入类、对象、继承、多态等高级机制 更接近现实世界建模，适用于复杂系统开发 ⚙️ OOP 核心特性 特性 描述 封装 将数据和操作行为打包成一个对象 继承 子类继承父类属性和行为 多态 同一种操作可作用于不同类型对象 🧱 示例比较：冰箱装大象（C++ 面向对象方式） Fridge fridge; Elephant elephant; fridge.open(); fridge.put(elephant); fridge.close(); 对象封装行为，语义清晰，可扩展性强。 ...

单元1 算法+数据结构 = 程序 算法：如何让计算机分析这些数据？ 数据结构：如何把这些数据表示给计算机？ 程序：如何让计算机明白我要做什么？ 网课地址：数据结构基础 🧠 数据结构与算法效率总览 一、📦 抽象数据类型（ADT：Abstract Data Type） 抽象数据类型定义了一类数据的逻辑结构和操作方式，它不依赖具体的实现方式，是算法设计的基础。 ✨ ADT 特点： 封装性：隐藏内部存储与操作细节，只暴露接口 独立性：实现方式灵活（可用数组、链表等） 通用性：跨语言、跨平台适用 📚 常见 ADT 与实现方式及应用 ADT名称 描述 常见实现方式 应用场景举例 数组 固定大小，顺序排列 顺序存储 图像处理、表格数据 链表 节点动态链接 单/双向链表 内存分配、编辑器缓冲区 栈 后进先出（LIFO） 数组、链表 函数调用、撤销操作 队列 先进先出（FIFO） 链表、循环数组 消息调度、打印系统 集合 无序不重复元素集合 哈希表、树结构 数据去重、元素管理 映射（Map） 键值对集合 哈希表、搜索树 参数配置、缓存索引 堆（Heap） 特殊优先队列结构 完全二叉树 优先任务调度、TOP-k问题 树（Tree） 分层父子关系结构 二叉树、AVL树等 文件系统、数据库索引 图（Graph） 顶点与边构成关系网 邻接表、邻接矩阵 地图导航、社交关系网络 二、📊 数据结构逻辑组织层级关系 根据元素之间的逻辑关系，可分为线性与非线性结构： 🧩 线性结构 元素一对一排列 包括：线性表、栈、队列、串（字符串） 🌲 非线性结构 元素存在一对多或多对多关系 包括： 类型 示例 树 二叉树、搜索树、Huffman 树等 图 有向图、无向图、加权图等 ✅ 层级包含关系：图 ⊇ 树 ⊇ 二叉树 ⊇ 线性表 ...

以下从市场需求、技术趋势、安全挑战及行业应对四个维度综合分析C++的前景，特别聚焦网络安全与基础设施领域的最新动态： 🔧 一、C++的当前市场地位与核心需求 高薪刚需领域 薪资竞争力：2025年C++岗位年薪中位数达24-60万，北京67%岗位月薪20-50K，显著高于多数语言。 行业集中度：通信（华为5G协议栈）、半导体（中芯国际芯片设计）、金融科技（中信证券高频交易系统）三大领域贡献超60%的高端岗位，依赖C++的硬件级控制与低延迟性能。 不可替代的技术场景 游戏开发：UE5引擎渲染管线优化、分布式服务器架构（40-80K薪资）仍以C++为核心。 嵌入式系统：车载娱乐系统、工业PLC控制需直接操作硬件，C++占比超80%。 AI基础设施：TensorFlow/PyTorch底层、CUDA加速库依赖C++实现极致性能优化。 🔒 二、网络安全与基础设施领域的新挑战 美国政府强制去C/C++政策 安全风险定性：CISA与FBI联合报告指出，C/C++的内存安全问题（如缓冲区溢出、释放后使用）对关键基础设施（能源、交通、金融）构成“异常风险”，威胁国家安全。 政策时间表：2026年1月1日前，所有支持关键基础设施的软件必须制定“内存安全迁移路线图”，否则将承担法律责任。 内存安全漏洞的行业影响 历史教训：70%的严重漏洞源于内存安全问题，如SQL注入、默认密码滥用等，在C/C++代码中高发。 开源生态压力：要求维护软件物料清单（SBOM）、缓存依赖项，并对开源贡献实施安全审计。 ⚙️ 三、C++的技术演进与安全升级路径 语言自身进化 现代C++标准：C++20/23引入模块、协程、概念，提升开发效率；智能指针（std::unique_ptr）部分缓解内存泄漏。 Safe C++ Extension提案：借鉴Rust所有权模型，设计编译时借用检查器，目标实现“零成本内存安全”（如Circle编译器实验）。 增量替代与混合方案 Rust协同：Linux内核自6.8版起支持Rust驱动，但C++核心模块因重构成本暂保留。 硬件辅助安全：Intel CET（控制流强制技术）、ARM MTE（内存标记扩展）在芯片层补强C++缺陷。 工具链强化 静态分析工具：Clang-Tidy、Coverity可检测80%内存错误；Visual Studio 2022 LTSC版本支持至2032年，提供长期安全更新。 下表总结了C++在各领域的现状及安全升级路径： 应用领域 现状 安全升级路径 挑战 关键基础设施 C++主导，但面临政策压力 Rust混合开发/硬件安全扩展 遗留系统重构成本高 游戏/嵌入式 不可替代，性能刚需 现代C++标准+静态分析工具 安全特性引入性能损耗 AI/高性能计算 底层优化依赖C++ Safe C++扩展提案 新标准落地周期长 🔭 四、未来十年前景与开发者建议 生命周期预测 短期（2026-2030）：传统领域（游戏、嵌入式）需求稳定，但关键基础设施份额将被Rust/Go侵蚀。 长期（2030+）：C++仍主导性能敏感场景，预计20-30年内维持“系统层基石”地位，但应用层占比下降。 开发者应对策略 转型学习： 深耕现代C++特性（模块、协程）并掌握Rust，适应混合开发现实。 补充硬件安全知识（如ARM MTE）。 领域选择： 优先进入：游戏引擎、AI芯片优化、工业控制（政策影响小）。 谨慎评估：政府/金融基础设施新项目（政策合规风险高）。 💎 结论 C++不会消失，但必须进化：在性能至上的领域（游戏、嵌入式、AI底层）仍是“硬核首选”；在网络安全敏感场景（关键基础设施）则需通过安全扩展或混合编程满足合规。开发者应拥抱现代C++与Rust双技能栈，以应对2026年后行业剧变。