数据结构概念（0）

数据结构

数据结构，就是研究数据的存储方式,如何存储具有复杂关系的数据更有助于后期对数据的再利用

数据存储的几种结构

• 线性表：还可细分为顺序表，链表，栈和队列
• 树结构：普通树，二叉树，线索二叉树
• 图存储结构

线性表

线性表结构存储的数据往往是可以依次排列的，具备这种关系的数据就可以使用线性表来存储，线性表并不是一种具体的存储结构，它包含[顺序存储结构]和[链式存储结构]，是顺序表和链表的统称

顺序表（数组）

顺序表，简单地理解，就是常用的数组，顺序表结构的底层实现借助的就是数组，因此对于初学者来说，可以把顺序表完全等价为数组，但实则不是这样。数据结构是研究数据存储方式的一门学科，它囊括的都是各种存储结构，而数组只是各种编程语言中的基本数据类型，并不属于数据结构的范畴。

image.png

链表

链表和顺序表不同，使用链表存储数据时，是随用随申请，因此数据的存储位置是相互分离的

image.png

栈

栈和队列隶属于线性表，是特殊的线性表，因为它们对线性表中元素的进出做了明确的要求。
栈中的元素只能从线性表的一端进出（另一端封死），且要遵循“先入后出”的原则，即先进栈的元素后出栈。

image.png

像一个木桶，栈中含有 3 个元素，分别是 A、B 和 C，从在栈中的状态可以看出 A 最先进的栈，然后 B 进栈，最后 C 进栈。根据“先进后出”的原则，3 个元素出栈的顺序应该是：C 最先出栈，然后 B 出栈，最后才是 A 出栈。

队列

队列中的元素只能从线性表的一端进，从另一端出，且要遵循“先入先出”的特点，即先进队列的元素也要先出队列

image.png

队列结构如图 4 所示，队列中有 3 个元素，分别是 A、B 和 C，从在队列中的状态可以看出是 A 先进队列，然后 B 进，最后 C 进。根据“先进先出”的原则，3 个元素出队列的顺序应该是 A 最先出队列，然后 B 出，最后 C 出。

树存储结构

树存储结构适合存储具有“一对多”关系的数据。

image.png

图存储结构

图存储结构适合存储具有“多对多”关系的数据

image.png