数据结构与算法-要点整理
知识导图:

一、数据结构
包含:线性表(数组、队列、链表、栈)、散列表、树(二叉树、多路查找树)、图
1.线性表
数据之间就是“一对一“的逻辑关系。
线性表存储数据的实现方案有两种,分别是顺序存储结构和链式存储结构。
包含:数组、队列、链表、栈。
1.1 数组:
连续内存存储。简单,此处不多介绍。
1.2 队列:
可以通过数组+前后索引实现,也可以通过链表+前后指针实现。
queue:
1)通过数组+前后索引实现
#include <iostream>
#include <stdexcept>template <typename T, int capacity>
class Queue {
private:T arr[capacity];int front; // 队头索引int rear; // 队尾索引int size; // 当前队列中的元素数量public:Queue() : front(0), rear(0), size(0) {}// 判断队列是否为空bool isEmpty() const {return size == 0;}// 判断队列是否已满bool isFull() const {return size == capacity;}// 入队操作void enqueue(const T& value) {if (isFull()) {throw std::overflow_error("Queue is full");}arr[rear] = value;rear = (rear + 1) % capacity; // 循环更新队尾索引++size;}// 出队操作T dequeue() {if (isEmpty()) {throw std::underflow_error("Queue is empty");}T value = arr[front];front = (front + 1) % capacity; // 循环更新队头索引--size;return value;}// 获取队头元素T getFront() const {if (isEmpty()) {throw std::underflow_error("Queue is empty");}return arr[front];}// 获取队列中的元素数量int getSize() const {return size;}
};int main() {Queue<int, 5> queue;try {// 入队操作queue.enqueue(1);queue.enqueue(2);queue.enqueue(3);// 输出队头元素std::cout << "Front element: " << queue.getFront() << std::endl;// 出队操作std::cout << "Dequeued element: " << queue.dequeue() << std::endl;// 再次输出队头元素std::cout << "Front element after dequeue: " << queue.getFront() << std::endl;// 输出队列中的元素数量std::cout << "Queue size: " << queue.getSize() << std::endl;} catch (const std::exception& e) {std::cerr << "Exception: " << e.what() << std::endl;}return 0;
}
2)通过链表+前后指针实现
#include <iostream>
#include <stdexcept>// 定义链表节点结构体
template <typename T>
struct Node {T data;Node<T>* next;Node(const T& value) : data(value), next(nullptr) {}
};// 定义队列类
template <typename T>
class Queue {
private:Node<T>* front; // 队头指针Node<T>* rear; // 队尾指针int size; // 当前队列中的元素数量public:// 构造函数Queue() : front(nullptr), rear(nullptr), size(0) {}// 析构函数~Queue() {while (!isEmpty()) {dequeue();}}// 判断队列是否为空bool isEmpty() const {return size == 0;}// 获取队列中的元素数量int getSize() const {return size;}// 入队操作void enqueue(const T& value) {Node<T>* newNode = new Node<T>(value);if (isEmpty()) {front = rear = newNode;} else {rear->next = newNode;rear = newNode;}++size;}// 出队操作T dequeue() {if (isEmpty()) {throw std::underflow_error("Queue is empty");}T value = front->data;Node<T>* temp = front;front = front->next;if (front == nullptr) {rear = nullptr;}delete temp;--size;return value;}// 获取队头元素T getFront() const {if (isEmpty()) {throw std::underflow_error("Queue is empty");}return front->data;}
};int main() {Queue<int> queue;try {// 入队操作queue.enqueue(1);queue.enqueue(2);queue.enqueue(3);// 输出队头元素std::cout << "Front element: " << queue.getFront() << std::endl;// 出队操作std::cout << "Dequeued element: " << queue.dequeue() << std::endl;// 再次输出队头元素std::cout << "Front element after dequeue: " << queue.getFront() << std::endl;// 输出队列中的元素数量std::cout << "Queue size: " << queue.getSize() << std::endl;} catch (const std::exception& e) {std::cerr << "Exception: " << e.what() << std::endl;}return 0;
}
双端队列Deque:
允许你从队列的两端进行元素的插入和删除操作,既可以在头部进行操作,也可以在尾部进行操作。
1)通过数组+前后索引实现
#include <iostream>
#include <stdexcept>template <typename T, int capacity>
class ArrayDeque {
private:T arr[capacity];int front;int rear;int size;public:ArrayDeque() : front(0), rear(0), size(0) {}// 判断队列是否为空bool isEmpty() const {return size == 0;}// 判断队列是否已满bool isFull() const {return size == capacity;}// 在队头插入元素void insertFront(const T& value) {if (isFull()) {throw std::overflow_error("Deque is full");}front = (front - 1 + capacity) % capacity;arr[front] = value;++size;}// 在队尾插入元素void insertRear(const T& value) {if (isFull()) {throw std::overflow_error("Deque is full");}arr[rear] = value;rear = (rear + 1) % capacity;++size;}// 从队头删除元素T deleteFront() {if (isEmpty()) {throw std::underflow_error("Deque is empty");}T value = arr[front];front = (front + 1) % capacity;--size;return value;}// 从队尾删除元素T deleteRear() {if (isEmpty()) {throw std::underflow_error("Deque is empty");}rear = (rear - 1 + capacity) % capacity;T value = arr[rear];--size;return value;}// 获取队头元素T getFront() const {if (isEmpty()) {throw std::underflow_error("Deque is empty");}return arr[front];}// 获取队尾元素T getRear() const {if (isEmpty()) {throw std::underflow_error("Deque is empty");}return arr[(rear - 1 + capacity) % capacity];}// 获取队列中的元素数量int getSize() const {return size;}
};int main() {ArrayDeque<int, 5> deque;try {deque.insertFront(1);deque.insertRear(2);std::cout << "Front element: " << deque.getFront() << std::endl;std::cout << "Rear element: " << deque.getRear() << std::endl;deque.deleteFront();std::cout << "Front element after deleteFront: " << deque.getFront() << std::endl;deque.deleteRear();std::cout << "Is deque empty after deletions? " << (deque.isEmpty() ? "Yes" : "No") << std::endl;} catch (const std::exception& e) {std::cerr << "Exception: " << e.what() << std::endl;}return 0;
}
2)通过链表+前后指针实现
#include <iostream>
#include <stdexcept>// 定义链表节点结构体
template <typename T>
struct Node {T data;Node<T>* prev;Node<T>* next;Node(const T& value) : data(value), prev(nullptr), next(nullptr) {}
};template <typename T>
class LinkedDeque {
private:Node<T>* front;Node<T>* rear;int size;public:LinkedDeque() : front(nullptr), rear(nullptr), size(0) {}~LinkedDeque() {while (!isEmpty()) {deleteFront();}}// 判断队列是否为空bool isEmpty() const {return size == 0;}// 在队头插入元素void insertFront(const T& value) {Node<T>* newNode = new Node<T>(value);if (isEmpty()) {front = rear = newNode;} else {newNode->next = front;front->prev = newNode;front = newNode;}++size;}// 在队尾插入元素void insertRear(const T& value) {Node<T>* newNode = new Node<T>(value);if (isEmpty()) {front = rear = newNode;} else {newNode->prev = rear;rear->next = newNode;rear = newNode;}++size;}// 从队头删除元素T deleteFront() {if (isEmpty()) {throw std::underflow_error("Deque is empty");}T value = front->data;Node<T>* temp = front;front = front->next;if (front == nullptr) {rear = nullptr;} else {front->prev = nullptr;}delete temp;--size;return value;}// 从队尾删除元素T deleteRear() {if (isEmpty()) {throw std::underflow_error("Deque is empty");}T value = rear->data;Node<T>* temp = rear;rear = rear->prev;if (rear == nullptr) {front = nullptr;} else {rear->next = nullptr;}delete temp;--size;return value;}// 获取队头元素T getFront() const {if (isEmpty()) {throw std::underflow_error("Deque is empty");}return front->data;}// 获取队尾元素T getRear() const {if (isEmpty()) {throw std::underflow_error("Deque is empty");}return rear->data;}// 获取队列中的元素数量int getSize() const {return size;}
};int main() {LinkedDeque<int> deque;try {deque.insertFront(1);deque.insertRear(2);std::cout << "Front element: " << deque.getFront() << std::endl;std::cout << "Rear element: " << deque.getRear() << std::endl;deque.deleteFront();std::cout << "Front element after deleteFront: " << deque.getFront() << std::endl;deque.deleteRear();std::cout << "Is deque empty after deletions? " << (deque.isEmpty() ? "Yes" : "No") << std::endl;} catch (const std::exception& e) {std::cerr << "Exception: " << e.what() << std::endl;}return 0;
}
1.3 链表:
和顺序表不同,使用链表存储数据,不强制要求数据在内存中集中存储,各个元素可以分散存储在内存中。链表存储数据间逻辑关系的实现方案是:为每一个元素配置一个指针,每个元素的指针都指向自己的直接后继元素。
单向链表:

#include <iostream>struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(nullptr) {}
};class LinkedList {
private:ListNode* head;public:LinkedList() : head(nullptr) {}void insertAtHead(int val) {ListNode* newNode = new ListNode(val);newNode->next = head;head = newNode;}void insertAtTail(int val) {ListNode* newNode = new ListNode(val);if (head == nullptr) {head = newNode;return;}ListNode* curr = head;while (curr->next!= nullptr) {curr = curr->next;}curr->next = newNode;}void deleteAtHead() {if (head == nullptr) {std::cout << "链表为空,无法删除" << std::endl;return;}ListNode* temp = head;head = head->next;delete temp;}void deleteAtTail() {if (head == nullptr) {std::cout << "链表为空,无法删除" << std::endl;return;}if (head->next == nullptr) {delete head;head = nullptr;return;}ListNode* curr = head;while (curr->next->next!= nullptr) {curr = curr->next;}delete curr->next;curr->next = nullptr;}void printList() {ListNode* curr = head;while (curr!= nullptr) {std::cout << curr->val << " ";curr = curr->next;}std::cout << std::endl;}// 查找元素是否存在bool search(int val) {ListNode* curr = head;while (curr!= nullptr) {if (curr->val == val) {return true;}curr = curr->next;}return false;}
};int main() {LinkedList list;list.insertAtHead(3);list.insertAtHead(2);list.insertAtHead(1);std::cout << "插入头部后的链表: ";list.printList();list.insertAtTail(4);list.insertAtTail(5);std::cout << "插入尾部后的链表: ";list.printList();list.deleteAtHead();std::cout << "删除头部节点后的链表: ";list.printList();list.deleteAtTail();std::cout << "删除尾部节点后的链表: ";list.printList();if (list.search(3)) {std::cout << "元素 3 存在于链表中" << std::endl;} else {std::cout << "元素 3 不存在于链表中" << std::endl;}return 0;
}
双向链表:
“双向”指的是各节点之间的逻辑关系是双向的,头指针通常只设置一个。

#include <iostream>// 定义双向链表节点结构体
struct ListNode {int val;ListNode* prev;ListNode* next;ListNode(int x) : val(x), prev(nullptr), next(nullptr) {}
};// 双向链表类
class DoublyLinkedList {
private:ListNode* head;ListNode* tail;public:DoublyLinkedList() : head(nullptr), tail(nullptr) {}// 插入节点到链表头部void insertAtHead(int val) {ListNode* newNode = new ListNode(val);if (head == nullptr) {head = newNode;tail = newNode;} else {newNode->next = head;head->prev = newNode;head = newNode;}}// 插入节点到链表尾部void insertAtTail(int val) {ListNode* newNode = new ListNode(val);if (tail == nullptr) {head = newNode;tail = newNode;} else {newNode->prev = tail;tail->next = newNode;tail = newNode;}}// 删除头部节点void deleteAtHead() {if (head == nullptr) {std::cout << "链表为空,无法删除" << std::endl;return;}ListNode* temp = head;if (head == tail) {head = nullptr;tail = nullptr;} else {head = head->next;head->prev = nullptr;}delete temp;}// 删除尾部节点void deleteAtTail() {if (tail == nullptr) {std::cout << "链表为空,无法删除" << std::endl;return;}ListNode* temp = tail;if (head == tail) {head = nullptr;tail = nullptr;} else {tail = tail->prev;tail->next = nullptr;}delete temp;}// 打印链表元素(从头到尾)void printList() {ListNode* curr = head;while (curr!= nullptr) {std::cout << curr->val << " ";curr = curr->next;}std::cout << std::endl;}// 打印链表元素(从尾到头)void printListReverse() {ListNode* curr = tail;while (curr!= nullptr) {std::cout << curr->val << " ";curr = curr->prev;}std::cout << std::endl;}
};int main() {DoublyLinkedList list;list.insertAtHead(3);list.insertAtHead(2);list.insertAtHead(1);std::cout << "插入头部后的链表: ";list.printList();list.insertAtTail(4);list.insertAtTail(5);std::cout << "插入尾部后的链表: ";list.printList();list.deleteAtHead();std::cout << "删除头部节点后的链表: ";list.printList();list.deleteAtTail();std::cout << "删除尾部节点后的链表: ";list.printList();std::cout << "从尾到头打印链表: ";list.printListReverse();return 0;
}
单向循环链表与双向循环链表:
单链表通过首尾连接可以构成单向循环链表:

双向链表也可以进行首尾连接,构成双向循环链表:

静态链表:
用静态链表存储数据,数据全部存储在数组中(和顺序表一样),但存储位置是随机的,数据之间"一对一"的逻辑关系通过一个整形变量(称为"游标",和指针功能类似)维持(和链表类似)。
在静态链表中,数组的每个元素代表一个链表节点,每个节点通常包含两部分:
- 数据域:存储节点的数据。
- 游标域(或指针域):存储下一个节点在数组中的索引,而不是像动态链表那样存储一个物理地址。

1.4 栈
栈是一种后进先出的数据结构。
#include <iostream>
#include <vector>class ArrayStack {
private:std::vector<int> data; // 存储元素的数组
public:// 入栈操作void push(int value) {
//使用 data.push_back(value) 将元素添加到 data 的末尾,实现入栈操作。data.push_back(value);}// 出栈操作int pop() {if (isEmpty()) {throw s相关文章:
数据结构与算法-要点整理
知识导图: 一、数据结构 包含:线性表(数组、队列、链表、栈)、散列表、树(二叉树、多路查找树)、图 1.线性表 数据之间就是“一对一“的逻辑关系。 线性表存储数据的实现方案有两种,分别是顺序存储结构和链式存储结构。 包含:数组、队列、链表、栈。 1.1 数组…...
Fort Firewall:全方位守护网络安全
Fort Firewall是一款专为 Windows 操作系统设计的开源防火墙工具,旨在为用户提供全面的网络安全保护。它基于 Windows 过滤平台(WFP),能够与系统无缝集成,确保高效的网络流量管理和安全防护。该软件支持实时监控网络流…...
Nginx实战技巧(Practical Tips for nginx)
引言 简介 Nginx(发音为 "engine-x")是一个高性能的HTTP和反向代理服务器. Nginx以其高并发处理能力、低资源消耗和灵活的配置而闻名,适用于高流量的Web服务器和应用程序。 Nginx的主要功能包括: HTTP服务器…...
YOLOv8:目标检测与实时应用的前沿探索
随着深度学习和计算机视觉技术的迅速发展,目标检测(Object Detection)一直是研究热点。YOLO(You Only Look Once)系列模型作为业界广受关注的目标检测框架,凭借其高效、实时的特点,一直迭代更新…...
解锁数字经济新动能:探寻 Web3 核心价值
随着科技的快速发展,我们正迈入一个全新的数字时代,Web3作为这一时代的核心构成之一,正在为全球数字经济带来革命性的变革。本文将探讨Web3的核心价值,并如何推动数字经济的新动能。 Web3是什么? Web3,通常…...
Lua 环境的安装
1.安装Lua运行环境 本人采用的是在windows系统中使用cmd指令方式进行安装,安装指令如下: winget install "lua for windows" 也曾使用可执行程序安装过,但由于电脑是加密电脑,最后都已失败告终。使用此方式安装可以安…...
Object类(2)
大家好,今天我们继续来看看Object类中一些成员方法,这些方法在实际中有很大的用处,话不多说,来看。 注:所有类都默认继承Object类的,所以可调用Object类中的方法,如equals,也可以发生…...
汽车网络信息安全-ISO/SAE 21434解析(中)
目录 第七章-分布式网络安全活动 1. 供应商能力评估 2. 报价 3. 网络安全职责界定 第八章-持续的网络安全活动 1. 网路安全监控 2. 网络安全事件评估 3. 漏洞分析 4. 漏洞管理 第九章-概念阶段 1. 对象定义 2. 网路安全目标 3. 网络安全概念 第十章 - 产品开发 第十…...
fatal error C1083: [特殊字符]ļ: openssl/opensslv.h: No such file or directory
一、环境 1. Visual Studio 2017 2. edk2:202305 3. Python:3.11.4 二、 fatal error C1083: 򿪰ļ: openssl/opensslv.h: No such file or directory 上图出现这个警告,不用管。 出现Done,说明编译成功。 执行上…...
C#System.Threading.Timer定时器意外回收注意事项
System.Threading.Timer定时器使用时会出现意外回收的情况。具体解释如下: 只要在使用 Timer,就必须保留对它的引用。对于任何托管对象,如果没有对 Timer 的引用,计时器会被垃圾回收。即使 Timer 仍处在活动状态,也会被回收。 实例对比测试 实例 定义两个类,其中一个…...
20.Word:小谢-病毒知识的科普文章❗【38】
目录 题目 NO1.2.3文档格式 NO4.5 NO6.7目录/图表目录/书目 NO8.9.10 NO11索引 NO12.13.14 每一步操作完,确定之后记得保存最后所有操作完记得再次删除空行 题目 NO1.2.3文档格式 样式的应用 选中应用段落段落→开始→选择→→检查→应用一个一个应用ctr…...
vue3底层原理和性能优化
Vue 3 在底层原理和性能优化方面做了许多改进,以下是一些主要的优化点和原理: 1. 虚拟 DOM 的改进 静态树提升:Vue 3 能够检测到静态组件(即不依赖响应式数据的组件)并将其提升到渲染函数之外,从而减少不…...
Ubuntu介绍、与centos的区别、基于VMware安装Ubuntu Server 22.04、配置远程连接、安装jdk+Tomcat
目录 ?编辑 一、Ubuntu22.04介绍 二、Ubuntu与Centos的区别 三、基于VMware安装Ubuntu Server 22.04 下载 VMware安装 1.创建新的虚拟机 2.选择类型配置 3.虚拟机硬件兼容性 4.安装客户机操作系统 5.选择客户机操作系统 6.命名虚拟机 7.处理器配置 8.虚拟机内存…...
金融级分布式数据库如何优化?PawSQL发布OceanBase专项调优指南
前言 OceanBase数据库作为国产自主可控的分布式数据库,在金融、电商、政务等领域得到广泛应用,优化OceanBase数据库的查询性能变得愈发重要。PawSQL为OceanBase数据库提供了全方位的SQL性能优化支持,助力用户充分发挥OceanBase数据库的性能潜…...
springboot 动态线程池
在Spring Boot中,可以使用ThreadPoolTaskExecutor类来创建动态线程池。以下是一个示例: 首先,需要在配置文件中配置线程池的属性,例如最小线程数、最大线程数、线程存活时间等。可以在application.properties或application.yml中…...
【PySide6快速入门】qrc资源文件的使用
文章目录 PySide6快速入门:qrc资源文件的使用前言什么是qrc文件?qrc文件的作用: qrc文件可以干什么?如何创建qrc文件?1. 创建.qrc文件2. 使用rcc工具编译.qrc文件 如何引用qrc文件并使用资源?示例代码&…...
【creo】CREO配置快捷键方式和默认单位
了解CREO工作目录设置 设置快捷方式启动目录,就能自动加载其中的配置。 一、通过键盘快捷方式 保存配置 creo_parametric_customization.ui 文件: 二、通过映射键录制 通过这种方式可以监听鼠标的点击事件。使用键盘快捷方式无法找到需要的动作时候可…...
STM32使用VScode开发
文章目录 Makefile形式创建项目新建stm项目下载stm32cubemx新建项目IED makefile保存到本地arm gcc是编译的工具链G++配置编译Cmake +vscode +MSYS2方式bilibiliMSYS2 统一环境配置mingw32-make -> makewindows环境变量Cmake CmakeListnijia 编译输出elfCMAKE_GENERATOR查询…...
数据结构与算法再探(六)动态规划
目录 动态规划 (Dynamic Programming, DP) 动态规划的基本思想 动态规划的核心概念 动态规划的实现步骤 动态规划实例 1、爬楼梯 c 递归(超时)需要使用记忆化递归 循环 2、打家劫舍 3、最小路径和 4、完全平方数 5、最长公共子序列 6、0-1背…...
若依基本使用及改造记录
若依框架想必大家都了解得不少,不可否认这是一款及其简便易用的框架。 在某种情况下(比如私活)使用起来可谓是快得一匹。 在这里小兵结合自身实际使用情况,记录一下我对若依框架的使用和改造情况。 一、源码下载 前往码云进行…...
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以? 在 Golang 的面试中,map 类型的使用是一个常见的考点,其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...
多场景 OkHttpClient 管理器 - Android 网络通信解决方案
下面是一个完整的 Android 实现,展示如何创建和管理多个 OkHttpClient 实例,分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...
ardupilot 开发环境eclipse 中import 缺少C++
目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...
Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...
【Java学习笔记】BigInteger 和 BigDecimal 类
BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点:传参类型必须是类对象 一、BigInteger 1. 作用:适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...
VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP
编辑-虚拟网络编辑器-更改设置 选择桥接模式,然后找到相应的网卡(可以查看自己本机的网络连接) windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置,选择刚才配置的桥接模式 静态ip设置: 我用的ubuntu24桌…...
基于 TAPD 进行项目管理
起因 自己写了个小工具,仓库用的Github。之前在用markdown进行需求管理,现在随着功能的增加,感觉有点难以管理了,所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD,需要提供一个企业名新建一个项目&#…...
免费数学几何作图web平台
光锐软件免费数学工具,maths,数学制图,数学作图,几何作图,几何,AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...
数据结构:递归的种类(Types of Recursion)
目录 尾递归(Tail Recursion) 什么是 Loop(循环)? 复杂度分析 头递归(Head Recursion) 树形递归(Tree Recursion) 线性递归(Linear Recursion)…...
