顺序表.md

什么是顺序表

​ 顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常成为顺序表。顺序表将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。

简介

​ 将表中的元素一个接一个地存入一组地址连续的存储单元中，这种存储结构就是顺序结构。采用顺序存储结构的线性表简称为顺序表。顺序表的存储特点是：只要确定了起始位置，表中任一元素的地址都可以通过下列公式得到： $$ LOC（a_{i}) = LOC(a_{1}) + (i - 1) * L (1<=i<=n) $$ 其中L是元素占用存储单元的长度。

特点

• 支持随机访问，即通过首地址和元素序号可以在O(1)的时间复杂度内找到指定的元素。

• 内存地址是连续的。