逻辑结构与存储结构

什么是逻辑结构？

是指数据之间的关系。分为：线性结构和非线性结构（集合、树、网）。

1. 线性结构：

有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前驱和一个直接后继，一对一关系。

形如：A-B-C-D

例如：线性表【 顺序表、链表、栈（顺序栈、链栈）和队列（顺序队列、链队列）】。

2. 非线性结构：

非线性结构也就是每个结点可以有不止一个直接前驱和直接后继，一对多关系。

常见的非线性结构包括：树（二叉树）、图（网）等。

什么是存储结构？

是指逻辑结构的存储映像。在物理内存中存储的方式。

常见的存储结构有顺序存储、链式存储、索引存储以及散列存储（哈希表）。

1. 顺序存储：

把逻辑上相邻的节点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储结构为顺序存储结构，通常顺序存储结构是借助于数组来描述的。

优点：节省空间，可以实现随机存取。

缺点：插入、删除时需要移动元素，效率低。

2. 链式存储：

在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。特点是元素在物理上可以不相邻，所以每个数据元素包括了一个数据域和一个指针域，数据域用来存放数据，而指针域用来指向其后继结点的位置。

优点：插入、删除灵活。

缺点：不能随机存取，查找速度慢。

判断

一个指的是数据之间的关系，而另一个指这种关系在计算机中的表现形式。比如，线性表中的栈，数据元素之间的关系是一对一的，除头和尾结点之外的每个结点都有唯一的前驱和唯一的后继，这体现的是逻辑结构；而对于栈中的结点来说，它们可以顺序存储（也就是顺序栈），取一段连续的存储空间，将栈结点按顺序存入，每个结点和其前驱和后继在物理上都是相邻的。同时，栈结点也可以链式存储（链栈），每个结点中包括数据域和指针域，而指针域就是用来指向其后继的，在访问时就可以通过指针来找到其后继进行访问，每个结点之间物理上可以相邻也可以不相邻。