【数据结构】数据结构整体大纲

发表于 2024-12-22 09:08:18

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？立即注册

×

数据结构用来干什么的？很简单，存数据用的。 （这篇文章仅先容数据结构的大纲，具体解说放在后面的每一个章节中，逐个击破）
那为什么不直接使用数组、聚集来存储呢 ——> 如果有成千上亿条数据呢？如果说：有一块连续的40w个字节大小的数据被存储在内存空间当中，请问，这个时候我必要提取出其中的某一条数据，不方便举行操作。
数组有个问题，数据一旦太大，如果想在内存中找到特定的空间很难，而我们将数据零散的到处分配在不同的空间中，所以我们采用了数据结构的方式举行数据的存储，然后中心通过指针的方式将这些数据串起来。创建之后，从此以后，这些数据形成了一个链条，所以，当我们知道一个链条的起始点，一个一个链接中的节点往下找，便可以找到这个链条其中的每一个数据，这便是数据结构的本质，这个链条被称为 链表。

根据上图的逻辑，我们现在要存储 10 20 30 40 50 60 六个数据使它们形成一个链表，该怎么写呢？

struct node
{
int d;
struct node *next;
};
struct node *p1 = (struct node *)malloc(sizeof(struct node));
p1->d = 10;
struct node *p2 = (struct node *)malloc(sizeof(struct node));
p2->d = 20;
p1->next = p2;
struct node *p3 = (struct node *)malloc(sizeof(struct node));
p3->d = 30;
p2->next = p3;
p1->next->next->d; // 30
//如此以往，环环相扣，首位相连

复制代码

这便是数据结构的本质与基础，很简单吧。数据结构一点都不难，只要能够理解数据之间串联方式的内涵逻辑，再看数据结构的各种方式不过是根据以上图基础的变种而已。它们的目的都是 链接零散在内存空间中数据 而存在的，用一些具有规则、规律的方式大概结构，对数据举行存储、插入、删除、查找、更新的过程。
什么是数据？

广义：你在计算机里看到的统统 —— 现实生活中的统统事物皆是数据。
狭义：代码产生的一系列数据：int a = 10; ——> a是数据，10也是数据。

什么是结构？

指的是关系 ——> 存储关系，逻辑关系，算法关系等。

什么是数据结构？

研究数据与数据之间的关系。例如：

关系：

研究分析数据与数据之间的关系 ----------------------------> 逻辑关系（结构）：表示数据运算之间的抽象关系（如毗邻关系、从属关系等），按每个数据元素大概具有的 直接前驱数 和 直接后继数 将逻辑结构分为“线性结构”和非线性结构两大类。
1.1 聚集
数据元素除了“同属于一个聚集”外，无其他关系。例子：鸡，鸭，鹅属于 —> 禽类
1.2 线性结构
指数据元素之间存在 一个对一个 的关系，形成有序的聚集。如许结构中，每个数据元素都有一个明确的前驱和后继，除了第一个元素没有前驱，最后一个元素没有后继，就像一辆火车一样一节节车厢链接在一起。
1.3 树状结构
出现一个对多个的关系（自上而下）。
1.4 图形结构
出现多对多的关系（人工智能）。
例如：脑神经，数据元素出现多对多的关系。
将这种关系保存在计算机中 -------------------------------------> 存储关系（结构）：存储结构是数据的逻辑结构在计算机存储器中的映射。存储结构是通过计算机语言所编制的步调来实现的。
2.1 次序存储
将这些数据依次存储在一块连续的空间中（数组）
2.2 链式存储
给每一个数据单独申请一个独立的空间，使用指针建立它们之间的关系。（构造数据用结构体形式去实现）
通过某种本事，修改在计算机中保存的关系 ----------------> 算法（狭义:增删改查）
3.1 插入删除修改替换排序（增删改查操作）

数据结构是计算机科学的核心内容，主要研究如何高效地组织、存储和操作数据。不同的数据结构适用于不同的应用场景，可以显著提高步调的性能和算法的服从。这篇文章是数据结构的完整学习大纲，涵盖了基础概念、常用数据结构及其相干算法、应用场景等内容。学习数据结构时，发起按照从简单到复杂的次序，由浅入深逐步深入理解每种结构的实现和应用。
数据结构的作用：

提高步调的可维护性和扩展性：数据结构通过抽象化数据的存储和操作，使步调更易维护和扩展。

解决特定领域的问题：

数据结构广泛应用于操作体系、数据库、网络、人工智能、大数据等领域，解决特定问题。好比说：B+树 用于数据库索引，图结构 用于建模网络。

数据结构的界说和分类：高效的存储与操作数据
1.1 数据结构提供了一种合理的方式来组织和存储数据，以支持各种数据操作（如插入、删除、查询、排序等）。
1.2 例如：使用数组可以快速按索引访问数据。使用 哈希表 实现快速查找。
数据结构与算法的关系
时间复杂度与空间复杂度
3.1 大 O 表示法
3.2 最优、最坏、平均复杂度分析；合理选择数据结构可以显著降低算法的时间复杂度。
3.3 例如，使用堆实现优先队列，使插入和删除的时间复杂度从 O(n) 降为 O(log n)。
根本操作：插入、删除、查找、更新。

数据结构整体大纲

数据结构的分类

（1）线性数据结构

数据元素按线性次序分列。
数据元素之间存在 一个对一个 的关系，形成有序的聚集。如许结构中，每个数据元素都有一个明确的前驱和后继，除了第一个元素没有前驱，最后一个元素没有后继，就像一辆火车一样一节节车厢链接在一起。
常见例子：
- 数组（Array）
- 链表（Linked List）：单向链表、单向循环链表、双向链表、双向循环链表、内核链表。
- 栈（Stack）
- 队列（Queue）
- 双端队列（Deque）

（2）非线性数据结构

数据元素之间不一定是线性关系，可以是层次关系或网状关系。
常见例子：
- 树（Tree）
- 图（Graph）

（3）哈希结构

通过哈希函数将数据映射到特定位置，支持快速查找和插入。
常见例子：
- 哈希表（Hash Table）

（4）高级数据结构

基于基础数据结构的抽象或优化。
常见例子：
- 堆（Heap）
- 并查集（Union-Find）
- 字典树（Trie）
- 跳表（Skip List）
- B 树与 B+ 树

各数据结构的具体先容

1. 数组（Array）
作用：存储固定大小的连续数据，支持随机访问。
解决的问题：快速按索引访问数据。
应用场景：

实现栈、队列。
存储二维或多维矩阵数据（如图像处置惩罚）。
动态数组（如 C++ 的 std::vector 和 Python 的 list）。

2. 链表（Linked List）
作用：通过节点链式存储数据，支持动态插入和删除。
解决的问题：在不知道数据大小或必要频繁插入/删除时提供灵活的存储方式。
种类：

单向链表、单向循环链表、双向链表、双向循环链表、内核链表。

应用场景：

内存管理（如空闲内存块管理）。
LRU 缓存（使用双向链表和哈希表实现）。
实现队列和其他数据结构。

3. 栈（Stack）
作用：后进先出（LIFO）的数据结构。
解决的问题：用于处置惩罚具有递归或嵌套结构的数据。
常见操作：push（入栈），pop（出栈），peek（查察栈顶元素）。
应用场景：

函数调用栈（保存函数调用上下文）。
括号匹配问题（如验证表达式正当性）。
表达式求值（如中缀转后缀表达式）。

4. 队列（Queue）
作用：先进先出（FIFO）的数据结构。
解决的问题：适用于必要按次序处置惩罚任务的场景。
种类：

普通队列、双端队列（Deque）、优先队列。

应用场景：

任务调度（如操作体系中的进程调度）。
广度优先搜索（BFS）。
实现消息队列（如 RabbitMQ）。

5. 树（Tree）
根本概念：节点、根、叶子、子树、高度、深度。
作用：层次化存储数据，便于快速查找、插入和删除。
解决的问题：高效存储和操作有层次关系的数据。
种类：

二叉树、二叉搜索树（BST）、平衡二叉树（如 AVL 树、红黑树）、堆。

应用场景：

文件体系（如目次结构）。
数据检索（如表达式树）。
数据库索引（如 B+ 树）。

6. 图（Graph）
根本概念：存极点、边、权重、度。
作用：存储网状关系的数据。
解决的问题：建模网络、路径规划等问题。
常见表示：

毗邻矩阵、毗邻表。
有向图 vs 无向图。

应用场景：

网络路由（如最短路径算法：Dijkstra）。
交际网络分析。
电路设计、推荐体系。

7. 哈希表（Hash Table）
根本概念：哈希函数，键值对存储。
作用：通过哈希函数支持快速插入和查找。
解决的问题：快速检索键值对。
冲突解决方法：

链地址法、开放地址法。

应用场景：

缓存（如 LRU 缓存）。
数据去重。
实现字典（如 Python 的 dict）。

8. 堆（Heap）
作用：动态维护最大值或最小值。
解决的问题：快速找到优先级最高的元素。
种类：

大顶堆、小顶堆。
完全二叉树。

应用场景：

优先队列。
Top-K 问题（如实时流数据分析）。
堆排序。

高级数据结构

9. 并查集（Union-Find）
作用：解决连通性问题。
解决的问题：动态合并聚集并查询聚集所属。
优化：

路径压缩、按秩合并。

应用场景：

网络连通性。
Kruskal 最小天生树算法。

10. 字典树（Trie）
作用：高效存储和检索字符串聚集。
解决的问题：快速搜索前缀匹配数据。
应用场景：

搜索引擎的自动补全。
拼写检查。
字符串去重。

11. 平衡树
作用：插入、删除、旋转操作，性子与平衡维护数据。
解决的问题：性子与平衡维护；应用：STL 的 map 和 set。
应用场景：

AVL 树。
红黑树。

12. 跳表（Skip List）
作用：通过引入多级索引（多层链表）以提高操作服从，是平衡树（如 AVL 树、红黑树）的高效替代方案，能够在有序数据聚集中快速举行查找、插入和删除操作。
解决的问题：时间复杂度分析：O(log n)。
应用场景：

数据库索引。
有序聚集操作。

13. B 树与 B+ 树
作用：平衡多路查找树，恰当磁盘存储。
解决的问题：高效管理和检索大规模数据。
应用场景：

数据库索引（如 MySQL）。
文件体系（如 NTFS）。

数据结构解决的问题及对应应用场景

问题范例解决问题的数据结构应用场景快速查找和插入哈希表、平衡树（红黑树、AVL 树）数据检索、缓存、字典实现动态优先级管理堆（大顶堆、小顶堆）优先队列、任务调度、实时流数据的 Top-K 问题快速存储和检索字符串字典树（Trie）拼写检查、搜索引擎自动补全路径或连通性问题图（毗邻表、毗邻矩阵）、并查集网络路由、交际网络分析、最小天生树数据的层次化存储与操作树（BST、B+ 树）文件体系、数据库索引处置惩罚动态长度的数据链表（单链表、双向链表）内存管理、链式存储任务调度或次序问题队列、双端队列（Deque）操作体系进程调度、消息队列递归或嵌套问题栈函数调用栈、表达式求值、括号匹配搜索和路径规划问题图（DFS、BFS）、堆（用于 Dijkstra）地图导航、最短路径算法大规模数据的排序与检索堆、平衡树（红黑树）、B+ 树外部排序、数据库查询、文件体系常用算法与数据结构结合

排序算法
- 冒泡排序、选择排序、插入排序
- 快速排序、归并排序、堆排序
- 桶排序、计数排序、基数排序
- 时间复杂度及适用场景
搜索算法
- 线性搜索
- 二分搜索
- 深度优先搜索（DFS）、广度优先搜索（BFS）
- A* 搜索算法（启发式搜索）
字符串匹配算法
- 暴力匹配
- KMP 算法
- Rabin-Karp 算法
- Trie 树（前缀树）

综上。
数据结构的作用：通过合理组织和存储数据，解决服从、存储和操作问题。
学习把握的过程由浅入深：先把握基础数据结构（数组、链表、栈、队列），再逐步学习复杂的数据结构（树、图、哈希）。
结合算法：理解排序、搜索、字符串匹配等算法中使用的数据结构。
解决的问题：快速查找、动态优先级管理、路径规划、大规模数据检索等。
应用场景：从操作体系、数据库、网络路由到人工智能、大数据分析，数据结构是解决实际问题的重要工具。
每种数据结构都有其独特的特性和适用场景，学习时需结合理论与应用，理解其实现原理和使用方法，以便在实际开发中合理选用。
以上。仅供学习与分享交流，请勿用于贸易用途！转载需提前说明。
我是一个十分热爱技术的步调员，希望这篇文章能够对您有资助，也希望认识更多热爱步调开发的小同伴。
感谢！

【数据结构】数据结构整体大纲

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

浏览过的版块

雁过留声