数据结构（全）_heyuchang666的博客-CSDN博客_数据结构
https://zhuanlan.zhihu.com/p/138523723
| 定义 | 数据结构是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，并确保经过这些运算以后所得到的新结构仍保持原来的结构类型 |
|---|---|
| 数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合（结构就是指数据元素之间存在的关系，分为逻辑结构和存储结构。） | |
| 理解 | 计算机存储、组织数据的方式 |
| 相互之间存在一种或多种特定关系的数据元素的集合 | |
| 补充 | 数据结构往往同高效的检索算法和索引技术有关。 |
| 数据是存储在计算机的内存里的，在存储时，决定了数据顺序和位置关系的便是“数据结构” |
| 数据结构分类 | ||||
| 逻辑结构 | 指数据元素之间逻辑关系的数据结构。 这里的逻辑关系是指数据元素之间的前后间关系，与数据在计算机中的存储位置无关。 | 线性结构 | 数据结构的元素之间存在一对一线性关系，所有结点都最多只有一个直接前趋结点和一个直接后继结点 | 数组、队列、链表、栈 |
| 非线性结构 | 各个结点之间具有多个对应关系，一个结点可能有多个直接前趋结点和多个直接后继结点 | 多维数组、广义表、树结构和图结构等 | ||
| 物理结构 | 指数据的逻辑结构在计算机存储空间中的存放形式称为数据的物理结构，也叫做存储结构。 | 顺序存储 | 是连续的，在内存中用一组地址连续的存储单元依次存储线性表的各个数据元素。 | |
| 链式存储 | 在内存中的存储元素不一定是连续的，用任意地址的存储单元存储元素，元素节点存放数据元素以及通过指针指向相邻元素的地址信息 | |||
| 索引存储 | 除建立存储结点信息外，还建立附加的索引表来标识节点的地址。索引表由若干索引项组成。 | |||
| 散列存储 | 又称Hash存储，由节点的关键码值决定节点的存储地址。 | |||
| 1数组 （Array） | 一个数组可以分解为多个数组元素，这些数组元素可以是基本数据类型或是构造类型。 |
|
数据是按照顺序存储在内存的连续空间内，arr后面的[]代表下标，由于数据是存储在连续空间内的，所以每个数据的内存地址(在内存上的位置)都可以通过数组下标计算出来，从而可以直接访问目标数据，达到随机访问的目的。 | |
| 2链表 （Linked List） | 一种物理存储单元上非连续，非顺序的存储结构 |
| 既可以表示线性结构，也可以用于表示非线性结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 | |
| 链表数据一般都是分散存储于内存中 的，无须存储在连续空间内 | |
|
| |
| 链表基础知识 https://www.bilibili.com/video/BV11L411T7XP/?spm_id_from=333.788.recommend_more_video.0&vd_source=6f20b4f7e632409d144977c0199c707b | |
| 链表到底是为了解决什么问题而发明的https://www.bilibili.com/video/BV1kS4y1e7Wj?spm_id_from=333.337.search-card.all.click&vd_source=6f20b4f7e632409d144977c0199c707b | |
| 【动画】如何轻松手写链表??????? | |
| 提高链表的查找速度 跳跃表 2-3: 跳跃列表 Skip List_哔哩哔哩_bilibili | |
| 3栈 （Stack） | 只能在某一端插入和删除的特殊线性表 |
| 按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。 | |
| (12条消息) 数据结构—栈_heyuchang666的博客-CSDN博客 https://blog.csdn.net/heyuchang666/article/details/49451099 | |
|
| |
| 栈解释 https://www.bilibili.com/video/BV1P44y1q7uL?spm_id_from=333.337.search-card.all.click&vd_source=6f20b4f7e632409d144977c0199c707b | |
| 栈的原理与实现（Python） https://www.bilibili.com/video/BV1DK4y1S795?spm_id_from=333.999.0.0&vd_source=6f20b4f7e632409d144977c0199c707b | |
| 4队列（Queue） | 队列是一种先进先出（FIFO）的线性表，它只允许在表的一端插入元素，而在表的另一端删除元素。 |
| 在队列中，允许插入的一端称为队尾（rear），允许删除元素的一端称为队头（front）。 | |
| 和栈不同的是，队列只允许在表的一端进行插入操作，而在另一端进行删除操作。 | |
| (12条消息) 数据结构—队列_heyuchang666的博客-CSDN博客https://blog.csdn.net/heyuchang666/article/details/49364747 | |
| Python实现队列 https://www.bilibili.com/video/BV11Z4y1A7Vz?spm_id_from=333.337.search-card.all.click&vd_source=6f20b4f7e632409d144977c0199c707b | |
| 循环队列 https://www.bilibili.com/video/BV1CE411w7AF?spm_id_from=333.337.search-card.all.click&vd_source=6f20b4f7e632409d144977c0199c707b | |
| 5树（Tree） | 是包含n（n>0）个结点的有穷集合K，且在K中定义了一个关系N，N满足 以下条件： （1）有且仅有一个结点 K0，他对于关系N来说没有前驱，称K0为树的根结点。简称为根（root）。 （2）除K0外，K中的每个结点，对于关系N来说有且仅有一个前驱。 （3）K中各结点，对关系N来说可以有m个后继（m>=0）。 |
| 一种层级式的数据结构，由顶点（节点）和连接它们的边组成 数的结构特点是： 每个节点有零个或多个子节点； 没有父节点的节点称为根节点； 每一个非根节点有且只有一个父节点； 除了根节点外，每个子节点可以分为多个不相交的子树。 | |
| 树的基础知识 | |
| 文字 | |
|
| |
| 树、二叉树、二叉堆、二叉搜索树、字典树 | |
| 红黑树、二分搜索、BST 2021年最好懂的红黑树_哔哩哔哩_bilibili | |
| 6图（Graph） | 是由结点的有穷集合V和边的集合E组成。 其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。 |
| 数据元素之间的多对多的关系 | |
| 图的基础知识：视频 | |
| 文字： | |
| 7堆（Heap） | 是一种图的树形结构（非线性数据结构），每个结点都有一个值， |
| 堆是一个完全二叉树（所谓完全二叉树就是除了最后一层其他层的节点个数都是满的）。 堆中每一个节点的值都必须大于等于或者小于其子树中每一个节点的值。 | |
|
| |
| 最大堆，最小堆 | |
| 散列表 （Hash table） 哈希表 | 一种数据结构，它提供了快速的插入操作和查找操作 |
| 无论哈希表总中有多少条数据，插入和查找的时间复杂度都是为O(1)， 因为哈希表的查找速度非常快 | |
| 图文并茂详解数据结构之哈希表 - 知乎 (zhihu.com) https://zhuanlan.zhihu.com/p/144296454 | |
