存储结构和存取结构的区别

正如题目所说,本节带大家理清这样一个知识点,即存结构和存结构,虽一字之差,却天差地别!

所谓存储结构,指的是数据在内存中真实的存储状态,具体可分为 2 类,即顺序存储结构和链式存储结构。而存取结构,指的是存取数据的方式,具体也可以分为 2 类,分别为顺序存取结构和随机存取结构。

举个例子,线性表的顺序存储结构是随机存取结构,而不是顺序存取结构;线性表的链式存储结构,又可以称为顺序存取结构,而不是随机存取结构。

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

顺序存储结构最大的特点是,我们可以随机存或者取数据。例如,现有一个数组 a,其初始存储状态为:

int a[4]={0,1,2,3};
图 1 int a[4]={0,1,2,3};

在此基础上,如果想取出元素 1,由于其位于数组下标为 1 的位置(数组下标通常由 0 开始计数),因此借助 a[1],就可以轻松实现目的;反之,如果想将元素 2 改存为元素 5,可以这样实现:
a[2] = 5;
显然借助顺序存储结构的特点,我们可以随机存或者取存储的各个元素。这也就解释了“线性表的顺序存储结构,又可以称为随机存取结构”。

和随机存取结构相对的,是顺序存取结构。通过前面的学习我们知道,采用链表存储的数据,它们所在的物理空间并不紧挨着,而是分散在内存中的各个位置。仍以存储 0、1、2、和 3 这 4 个元素为例,如果采用链式存储结构,则各个元素的存储状态可能为:

链式存储 0、1、2 和 3
图 2 链式存储 0、1、2 和 3

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

总之,线性表的顺序存储结构,又可以称为随机存取结构;而线性表的链式存储结构(以及栈结构和队列结构),又可以称为顺序存取结构。