数据结构与算法——第2章-存储结构、存取结构(2.5)

发表于 分类于 ， ， 阅读时长 ≈ 1 分钟

一 概述

1
2
1.线性表的顺序存储结构是随机存取结构（而不是顺序存取结构）
2.线性表的链式存储结构称为顺序存取结构（而不是随机存取结构）

二 存储结构、存取结构

1
2
存储结构：数据在内存中真实的存储状态可分为顺序存储结构和链式存储结构。
存取结构：存取数据的方式可分为顺序存取结构和随机存取结构

三 线性表的顺序存储结构是随机存取结构

3.1 概念

1
2
3
4
5
6
线性表的顺序存储结构是随机存取结构（而不是顺序存取结构）

线性表的顺序存储结构本质就是采用一块连续的存储空间将所有数据集中存储起来。
很多种编程语言中，都使用数组这种数据类型来表示顺序存储结构。

顺序存储结构最大的特点：可以随机存或取数据。

3.2 示例

1
2
3
4
5
6
例如，数组 a 初始存储状态为（int a[4]={0,1,2,3};）：

如果想取出元素 1，由于其位于数组下标为 1 的位置，因此借助a[1]就可以轻松实现；
如果想将元素 2 改存为元素 5，可这样实现：a[2] = 5;

顺序存储结构可以随机存或取各个元素，因此“线性表的顺序存储结构称为随机存取结构”

图示

四 线性表的链式存储结构称为顺序存取结构

1
2
3
4
5
6
7
链表存储数据时，物理空间并不紧挨着，而是分散在内存中的各个位置。
仍以存储 0、1、2、3 元素为例，如果采用链式存储结构，则各个元素的存储状态可能为：

如果想在链表中存或取数据，就只能从链表头 H 开始，逐个遍历链表中的每个元素，直至找到目标元素。
从链表中存和取数据必须从遵循各个元素在链表中存储的逻辑顺序，无法随机存取。

因此，线性表的链式存储结构（栈和队列），又称为顺序存取结构

图示

五 参考

  • CSDN—存储结构、存取结构