什么是数据结构

前言

数据结构，简单说，就是研究数据的存储方式。数据在计算机存储空间的存放，决不是胡乱的，研究一种好的方式来存储数据，这也是数据结构的核心内容。

数据结构

数据结构大致包含以下几种存储结构：

1. 线性表，还可细分为顺序表、链表、栈和队列；

线性表结构存储的数据往往是可以依次排列的，就像一群人手拉手，每人的前面和后面都仅有一人和他拉手，具备这种“一对一”关系的数据就可以使用线性表来存储。

例如，存储类似 {1,2,3,4,5} 这样的数据时，各元素依次排列，每个元素的前面和后边有且仅有一个元素与之相邻（除首元素和尾元素），因此可以使用线性表存储。

线性表并不是一种具体的存储结构，它包含顺序存储结构和链式存储结构，是顺序表和链表的统称。

顺序表，简单地理解，就是常用的数组，只是换了个名字而已，例如使用顺序表存储 {1,3,5,7,9}，如下图所示：

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

链表存储数据时，是随用随申请，因此数据的存储位置是相互分离的，换句话说，数据的存储位置是随机的。

链表给各数据块增设一个指针来给数据块建立“依次排列”的关系，每个数据块的指针都指向下一个数据块（最后一个数据块的指针指向 NULL），看似毫无关系的数据块就建立了“依次排列”的关系，也就形成了链表，如下图所示：

栈和队列隶属于线性表，是特殊的线性表，因为它们对线性表中元素的进出做了明确的要求。

栈中的元素只能从线性表的一端进出（另一端封死），且要遵循“先入后出”的原则，即先进栈的元素后出栈。

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

2. 树结构，包括普通树，二叉树，线索二叉树等；
树存储结构适合存储具有“一对多”关系的数据 。如下图：

根节点是唯一的，不可能存在多个根节点。数据结构中的树只有一个根节点。

3. 图存储结构；

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