顺序存储结构的随机存取_数据结构分为哪三类

一、存取结构：随机存取和顺序存

1.1随机存取

随机存取（直接存取,Random Access）指的是当存储器中的数据被读取或写入时，所需要的时间与该数据所在的物理地址无关。

随机存取就是直接存取，可以通过下标直接访问到元素的位置，与存储位置无关，时间复杂度永远为O(1)，例如数组。存取第N个数据时，不需要访问前（N-1）个数据，直接就可以对第N个数据操作 （array）。

随机存取的微观现实例子就是编程语言中的数组。

随机存取的宏观现实例子就是我们的随机存取存储器(RAM:Random Access Memory)，通俗的说也就是我们电脑的内存条。因为RAM利用电容存储电荷的原理保存信息，所以RAM可以高速存取，且与物理地址无关。

1.2顺序存取

顺序存取(Sequential Access)是一种按记录的逻辑顺序进行读、写操作的存取方法，所需要的时间与该数据所在的物理地址有关。顺序存取表现为：在存取第N个数据时，必须先访问前（N-1）个数据。

非随机存取也叫顺序存取，不能通过下标访问。

顺序存取的微观现实例子就是数据结构中的链表。

顺序存取的现实例子就是我们的录音磁带、光盘、机械硬盘里面的磁盘。磁带、光盘、磁盘上的数据分别存储在不同扇区、不同磁道上，磁盘的读写磁头通过切换不同扇区和磁道来读取物理地址不连续的数据时，该过程中要经过不同扇区和不同磁道上的无关数据，磁盘的读写磁头在切换不同扇区和磁道所需时间也不同，故为顺序存取。

1.3 存取与插入删除的区别

存取只是将数组或链表的数据取出来或存入，不改变表的长度，而插入删除则会改变表的长度。

二、存储结构：顺序存储、随机存储

2.1 顺序存储

顺序存储是把逻辑上相邻的数据元素存储在物理位置上相邻的存储单元中，数据元素之间的逻辑关系由存储单元的邻接关系来体现。

顺序存储的主要优点：

    节省存储空间。因为分配给数据的存储单元全用存放数据元素（不考虑c/c++语言中数组需指定大小的情况），数据元素之间的逻辑关系没有占用额外的存储空间。
    可实现对数据元素的随机存取(直接存取)。即每一个数据元素对应一个元素下标，由该元素下标可以直接计算出来数据元素的物理存储地址。

顺序存储的主要缺点：

    不便于数据修改。对数据元素的插入、删除运算时，可能要移动一系列的数据元素。
    产生磁盘碎片。因为顺序存储只能使用相邻的一整块存储单元，因此会产生较多的磁盘碎片。

顺序存储的典型实例就是编程语言中的数组。例如，使用顺序表存储集合 {1,2,3,4,5}，数据最终的存储状态如下图所示：

数组中的所有元素存储在一个连续性的内存块中，并通过数组的首地址和元素下标来访问。因此一个数组就是由1个数组首地址和N个数组元素构成，数组不需要像链表一样，链表的每个节点必须存储下一个结点的物理地址，在存储同样多的数据下，数组比链表节省空间。

数组可通过数组的首地址和元素下标来直接存取数组中的没每一个元素，而不需要像链表一样，在存取第N个链表结点的数据时，必须先访问前（N-1）个链表结点。

但对数组的数据元素的插入、删除运算时，可能要移动一系列的数据元素，特别的麻烦，因此顺序存储结构的数组不便于修改。

2.2 随机存储

在计算机中用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。它不要求逻辑上相邻的元素在物理位置上也相邻，而是借助指示元素存储地址的指针来表示元素之间的逻辑关系。

顺序存储的主要优点：

1. 不会产生磁盘碎片。因为随机存储不要求逻辑上相邻的元素在物理位置上也相邻，而是借助指示元素存储地址的指针来表示元素之间的逻辑关系，因此不会产生磁盘碎片。
2. 数据修改方便。对数据元素的插入、删除运算时，随机存储不必移动结点，只要改变结点中的指针。

顺序存储的主要缺点：
3. 占用空间大。随机存储的每个结点都由数据域和指针域组成，所以相同空间内假设全存满，顺序存储比随机存储可存更多数据。
4. 查找结点时链式存储要比顺序存储慢，且只能实现顺序存取。 

2.2.1 随机存储——链式存储

链式存储是随机存储最典型的代表，因此链式存储的定义、优点和缺点就是 2.2随机存储 中的定义、优点和缺点。

2.2.2 随机存储——索引存储

除建立存储结点信息外，还建立附加的索引表来标识结点的地址，索引表由若干索引项组成，索引项的一般形式是(关键字，地址)。

索引存储的主要优点：检索速度快。
索引存储的主要缺点：增加了附加的索引表,会占用较多的存储空间。

2.2.3 随机存储——散列存储

散列存储，又称Hash存储，是一种将数据元素的存储位置与关键码之间建立确定对应关系的查找技术，即根据元素的关键字直接计算出该元素的存储地址。

散列存储的主要优点：检索、增加和删除节点的操作更快。
散列存储的主要缺点：若散列函数不好，则可能出现元素存储单元的冲突。
 

参考原文出处：

数据结构考研:随机存取、顺序存取、随机存储和顺序存储的区别/详细解释(计算机/软件工程/王道论坛)_快乐李同学(李俊德-大连理工大学)的博客-CSDN博客_数据结构随机存取是什么意思

今天的文章
顺序存储结构的随机存取_数据结构分为哪三类分享到此就结束了，感谢您的阅读。