数据的结构与存储

逻辑结构与物理结构

逻辑结构是指数据对象中元素之间的相互关系。

集合结构中的数据元素除了同属于一个集合之外，无任何其他关系。

线性结构中的数据元素之间是一对一的关系。

常用的线性结构有：线性表，栈，队列，双队列，数组，串。关于广义表，是一种非线性的数据结构。常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)，图。

1．集合中必存在唯一的一个"第一个元素"； 2．集合中必存在唯一的一个"最后的元素"； 3．除最后元素之外，其它数据元素均有唯一的"后继"； 4．除第一元素之外，其它数据元素均有唯一的"前驱"。

数据结构中线性结构指的是数据元素之间存在着“一对一”的线性关系的数据结构。如(a0,a1,a2,…..,an),a0 为第一个元素，an 为最后一个元素，此集合即为一个线性结构的集合。相对应于线性结构，非线性结构的逻辑特征是一个结点元素可能对应多个直接前驱和多个后继。

树形结构中的数据元素之间存在一种一对多的层次关系。

图形结构中的数据元素是多对多的关系。

数据的逻辑结构在计算机中的存储形式,也叫存储结构。

把数据元素放在地址连续的存储单元里,其数据间的逻辑关系和物理关系是一致的。

把数据元素存放在任意的存储单元里,这组存储单元可以是连续的,也可以是不连续的。其存储关系不能反映逻辑关系,需要用一个指针存放数据元素的地址。

数据类型指一组性质相同的值得集合及定义在此集合上的一些操作的总称，数据类型又分为原子类型与结构类型：

抽象数据类型指一个数学模型以及定义在该模型上的一组操作，抽象的意义在于数据类型的数学抽象特性，抽象数据类型体现了程序设计中问题分解，抽象和信息隐藏的特性。为了便于在之后的讲解中对抽象数据类型进行规范的描述，我们给出了描述抽象数据类型的标准格式：

ADT 抽象数据类型名
Data
    数据元素之间逻辑关系的定义

Operation
    操作 1

        初始条件

        操作结果描述

    操作 2

        ...
  操作 n

        ...

数据结构的存储方式只有两种：数组（顺序存储）和链表（链式存储）。

比如说队列、栈这两种数据结构既可以使用链表也可以使用数组实现。用数组实现，就要处理扩容缩容的问题；用链表实现，没有这个问题，但需要更多的内存空间存储节点指针。
图的两种表示方法，邻接表就是链表，邻接矩阵就是二维数组。邻接矩阵判断连通性迅速，并可以进行矩阵运算解决一些问题，但是如果图比较稀疏的话很耗费空间。邻接表比较节省空间，但是很多操作的效率上肯定比不过邻接矩阵。
哈希表就是通过哈希函数把键映射到一个大数组里。而且对于解决哈希冲突的方法，拉链法需要链表特性，操作简单，但需要额外的空间存储指针；线性探查法就需要数组特性，以便连续寻址，不需要指针的存储空间，但操作稍微复杂些。
树，用数组实现就是堆，因为堆是一个完全二叉树，用数组存储不需要节点指针，操作也比较简单；用链表实现就是很常见的那种树，因为不一定是完全二叉树，所以不适合用数组存储。为此，在这种链表树结构之上，又衍生出各种巧妙的设计，比如二叉搜索树、AVL 树、红黑树、区间树、B 树等等，以应对不同的问题。

综上，数据结构种类很多，甚至你也可以发明自己的数据结构，但是底层存储无非数组或者链表，二者的优缺点如下：

数组由于是紧凑连续存储,可以随机访问，通过索引快速找到对应元素，而且相对节约存储空间。但正因为连续存储，内存空间必须一次性分配够，所以说数组如果要扩容，需要重新分配一块更大的空间，再把数据全部复制过去，时间复杂度 O(N)；而且你如果想在数组中间进行插入和删除，每次必须搬移后面的所有数据以保持连续，时间复杂度 O(N)。
链表因为元素不连续，而是靠指针指向下一个元素的位置，所以不存在数组的扩容问题；如果知道某一元素的前驱和后驱，操作指针即可删除该元素或者插入新元素，时间复杂度 O(1)。但是正因为存储空间不连续，你无法根据一个索引算出对应元素的地址，所以不能随机访问；而且由于每个元素必须存储指向前后元素位置的指针，会消耗相对更多的储存空间。

最近更新于 0001-01-01