数据的四种存储结构

数据的存储结构：1.顺序存储、2.链接存储、3.索引存储、4.散列存储。

1.顺序存储

此存储方式就是将逻辑相邻的元素存储在物理位置也是相邻的存储单元。常见的实现方式是数组来表示。
优点:可以随机访问存储单元，时间复杂度为O(1)
缺点:增加或者删除元素需要移动元素

2.链接存储

这种存储方式不需要将逻辑相邻的元素也存储在物理位置也相邻，物理位置可以不是连续。节点间的逻辑关系通过指针字段链接
优点:增加或者删除节点方便
缺点:存储结构的存储密度小，每个节点都有指针域
不能随机访问存储单元。

3.索引存储

该方式是在存储节点信息的同时，还建立附加的索引表。
稠密索引（Dense Index):每个节点都在索引表中有个一个索引
存储形式：（关键字，每个节点的存储位置）
稀疏索引（Spare Index): 每组在索引表中有个一个索引
存储形式：（关键字，每组节点的起始存储位置）
关键字是能够唯一标识一个节点的哪些数据项
优点:利用节点索引号来检索速度快
缺点:增加了索引表，会占用较多的存储空间

4.散列存储

此方式根据节点的关键字直接计算出该节点的存储地址

存储结构

数据元素之间的关系在计算机的存储有四种表示方法，分别是顺序存储、链式存储、索引存储、哈希存储。

特点

顺序存储

数据元素顺序存放，每个结点只有一个元素。存储位置反映数据元素间的逻辑关系。存储密度大，但是插入、删除操作效率较差。

链式存储

每个结点除了包含数据元素信息外还包含一组指针，指针反映数据元素间的逻辑关系。这种存储方式不要求存储空间连续，便于进行插入和删除操作，但是存储空间利用率较低。另外，由于逻辑上相邻的数据元素在存储空间上不一定相邻，所以不能对其进行随机存取。

索引存储

除了数据元素存储在一地址连续的内存空间外，尚需建立一个索引表。索引表中的索引指示结点的存储位置，兼有动态和静态的特性。

哈希（散列）存储

通过哈希函数解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将哈希函数的值座位该数据元素的存储地址，其特点是存取速度快，只能按关键字随机存取，不能顺序窜出，也不能折半存取。

数据的存储结构（物理结构）：顺序存储、链接存储（多了指针）、索引存储（多了索引表）、散列存储（散列表）。

存取方式：

随机存取、顺序存取、随机存储和顺序存储这四个概念是完全不一样的，切不可将之混淆

很多人包括我可能认为随机存取就是随机存储，顺序存取就是顺序存取，其实不是这样。

下面完整的介绍一下这4个概念

存取结构：分为随机存取和非随机存取（又称顺序存取）

　　1、随机存取就是直接存取，可以通过下标直接访问的那种数据结构，与存储位置无关，例如数组。非随机存取

就是顺序存取了，不能通过下标访问了，只能按照存储顺序存取，与存储位置有关，例如链表。

　　2、顺序存取就是存取第N个数据时，必须先访问前（N-1）个数据 （list），随机存取就是存取第N个数据时，

不需要访问前（N-1）个数据，直接就可以对第N个数据操作 （array）。

存储结构：分为顺序存储和随机存储

1.顺序存储结构

　　在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素，称作线性表的顺序存储结构。

顺序存储结构是存储结构类型中的一种，该结构是把逻辑上相邻的节点存储在物理位置上相邻的存储单元中，

结点之间的逻辑关系由存储单元的邻接关系来体现。由此得到的储结构为顺序存储结构，通常顺序存储结构是

借助于计算机程序设计语言（例如c/c++）的数组来描述的。

　　顺序存储结构的主要优点是节省存储空间，因为分配给数据的存储单元全用存放结点的数据（不考虑c/c++语言中数组需指定大小的情况），

结点之间的逻辑关系没有占用额外的存储空间。采用这种方法时，可实现对结点的随机存取，即每一个结点对应一个序号，

由该序号可以直接计算出来结点的存储地址。但顺序存储方法的主要缺点是不便于修改，对结点的插入、删除运算时，

可能要移动一系列的结点。

　　2、随机存储结构

　　在计算机中用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。

　　它不要求逻辑上相邻的元素在物理位置上也相邻。因此它没有顺序存储结构所具有的弱点，但也同时失去了顺序表可随机存取的优点。

　　随机存储最典型的代表为链式存储：

　　链式存储结构特点

　　1、比顺序存储结构的存储密度小 （每个节点都由数据域和指针域组成，所以相同空间内假设全存满的话顺序比链式存储更多）。

　　2、逻辑上相邻的节点物理上不必相邻。

　　3、插入、删除灵活 （不必移动节点，只要改变节点中的指针）。

　　4、查找结点时链式存储要比顺序存储慢。

　　5、每个结点是由数据域和指针域组成。