
线性表是一种 逻辑结构,顺序表是线性表的 顺序存储
Q:线性表明明是顺序存储 为什么是随机存取?
A: 随机存取 指的是获取数据时的时间复杂度,并不是存储方式
1. 什么是“顺序存储”?(侧重于【空间布局】)
顺序存储 Sequential Storage 是指在内存中开辟一块连续的存储空间,将线性表中的元素按照逻辑顺序依次放入这块空间中(最典型的实现就是数组)。
因为空间是连续的,所以每个元素的物理地址和它的逻辑序号之间有一个严格的数学关系。
假设首元素地址是 ,每个元素占 个字节,那么第 个元素的地址就是:
2. 什么是“随机存取”?(侧重于【时间效率】)
这里的“随机”在英文中是 Random Access。在计算机科学中,“随机”不代表“胡乱、随机挑选”,而是代表“任意位置”
随机存取的意思是:**访问第 1 个元素和访问第 10000 个元素,所花费的时间是完全一样的(时间复杂度为 O(1)