顺序表知识总结
顺序表作为线性表的一种物理实现,是数据结构中最基础、最重要的存储结构之一。它使用一段地址连续的存储单元依次存储线性表中的数据元素,从而使得逻辑上相邻的元素在物理存储上也相邻。下面将从原理、操作、实现、优缺点及应用等方面进行详细总结。
一、 顺序表的基本原理与性质
顺序表的核心是数组。通过数组的下标(索引) 可以随机访问任意位置的元素。设顺序表的起始地址(基地址)为 LOC(A),每个元素占用 L 个存储单元,则第 i 个元素(从1开始计数)的存储位置可以通过公式 LOC(ai) = LOC(A) + (i-1) * L 直接计算得出。这种随机存取能力是顺序表的核心优势 。
其基本性质如下:
| 物理结构 | 地址连续的一段存储空间,通常使用数组实现。 | |
| 逻辑关系 | 逻辑上相邻的元素,在物理存储上也必然相邻。 | |
| 访问方式 | 支持随机访问,通过下标(索引)可在 O(1) 时间内访问任意元素。 | |
| 存储密度 | 存储密度高,因为只需存储数据元素本身,无需附加指针等额外信息。 |
二、 顺序表的分类与结构定义
顺序表主要分为两类:静态顺序表和动态顺序表。



