数据结构

数据是存储在计算机的内存里的，在存储时，决定了数据顺序和位置关系的便是“数据结构”，分为逻辑结构和物理结构。

逻辑结构

指数据元素之间逻辑关系的数据结构，这里的逻辑关系是指数据元素之间的前后间关系。一种数据结构的逻辑结构根据需要可以表示成多种存储结构。

• 线性结构：数据结构的元素之间存在一对一线性关系，所有结点都最多只有一个直接前趋结点和一个直接后继结点。常见的有数组、队列、链表、栈。
• 非线性结构：各个结点之间具有多个对应关系，一个结点可能有多个直接前趋结点和多个直接后继结点。常见的有多维数组、广义表、树结构和图结构等。

物理结构

指数据的逻辑结构在计算机存储空间中的存放形式称为数据的物理结构，也叫做存储结构。

• 顺序存储：存储顺序是连续的，在内存中用一组地址连续的存储单元依次存储线性表的各个数据元素。
• 链式存储：在内存中的存储元素不一定是连续的，用任意地址的存储单元存储元素，元素节点存放数据元素以及通过指针指向相邻元素的地址信息。
• 索引存储：除建立存储结点信息外，还建立附加的索引表来标识节点的地址。索引表由若干索引项组成。
• 散列存储：又称Hash存储，由节点的关键码值决定节点的存储地址。

常用的数据结构

• 数组(Array): 线性表数据结构，用一组连续的内存空间来存储一组相同类型的数据
• 链表(Linked List): 物理存储单元上非连续，非顺序的存储结构。链表有一系列节点(元素)组成。每个节点包含两个数据，一个是存储元素的数据域（值），另一个是存储下一个节点地址的指针域(还可以增加一个数据存储上一个节点地址的指针域)
• 队列(Queue): 线性排列的数据结构，FIFO(First in First Out)，操作数据从两端进行
• 栈(Stack): 线性排列的数据结构，LIFO(Last in First Out)，操作数据从顶端进行
• 散列表(Hash): 又称哈希表。存储的由键(key)和值(value)组成的数据，根据键直接访问存储在内存存储位置
• 树(Tree): 层级式的数据结构，由顶点(节点)和连接它们的边组成，非根节点有且只有一个父节点
• 堆(Heap): 完全二叉树(除了最后一层其他层的节点个数都是满的)。
• 图(Graph): 相对复杂的一种数据结构，由顶点(结点，Vertex)和连接每对顶点的边(Edge)所构成的图形