数据结构中常用的逻辑结构和存储结构

数据结构中常用的逻辑结构和存储结构 数据结构是一门研究数据的逻辑结构和存储结构，以及对数据的各种操作的学科。数据结构可以分为逻辑上的数据结构和物理上的数据结构两部分。逻辑上的数据结构反映数据之间的逻辑关系，即逻辑结构，而物理上的数据结构反映数据在计算机内部的存储安排，即存储结构。 逻辑结构是指数据元素之间的逻辑关系，分为线性结构和非线性结构两种。线性结构的特征是有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前驱和一个直接后继。线性表是一个典型的线性结构，它有四个基本特征：集合中必存在唯一的一个"第一个元素"；集合中必存在唯一的一个"最后的元素"；除最后元素之外，其它数据元素均有唯一的"后继"；除第一元素之外，其它数据元素均有唯一的"前驱"。非线性结构的逻辑特征是一个结点元素可能对应多个直接前驱和多个直接后继。常见的非线性结构有树（二叉树等）、图（网等）。 逻辑结构有四种基本类型：集合结构、线性结构、树形结构和图形结构。集合结构的数据元素之间没有其他关系。线性结构的数据元素之间是一对一的关系。树形结构的数据元素之间存在一种一对多的层次关系。网形结构的数据元素是多对多的关系。 存储结构是指数据的逻辑结构在计算机中的存储形式。数据元素的存储结构形式有两种：顺序存储和链式存储。顺序存储结构把逻辑上相邻的节点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现。顺序存储结构的优点是节省存储空间，因为分配给数据的存储单元全用存放结点的数据，结点之间的逻辑关系没有占用额外的存储空间。采用这种方法时，可实现对结点的随机存取，即每一个结点对应一个序号，由该序号可以直接计算出来结点的存储地址。但顺序存储方法的主要缺点是不便于修改，对结点的插入、删除运算时，可能要移动一系列的结点。 链式存储结构在计算机中用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。链式存储结构的特点是：逻辑上相邻的节点物理上不必相邻；插入、删除灵活（不必移动节点，只要改变节点中的指针）；查找结点时链式存储要比顺序存储慢；每个结点是由数据域和指针域组成。 数据结构的研究主要集中在三个方面：数据的逻辑结构、数据的物理存储结构和对数据的操作（或算法）。算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。因而研究数据结构的逻辑结构与存储结构显得十分重要。 在实际应用中，数据结构的选择取决于具体的问题和要求。例如，在编译器的设计中，通常使用树形结构来表示语法树。在数据库的设计中，通常使用图形结构来表示数据之间的关系。在操作系统的设计中，通常使用链式存储结构来管理内存空间。 数据结构中常用的逻辑结构和存储结构是研究数据的逻辑关系和物理存储形式的基础。只有深入理解了数据结构的逻辑结构和存储结构，才能设计出高效的算法和数据结构，使得计算机系统运行更快、更高效。