数据结构第二讲：顺序表

返回目录

§2 线性表

§2.1 线性表的基本概念

线性表是由若干（可以是零）个相同类型的数据元素组成的有限序列。若至少含有一个元素，则只有唯一的开始元素和终端元素，除了开始元素外其他元素有且仅有一个前驱元素，除了终端元素外其他元素有且仅有一个后继元素。

提醒：如果题目说线性表至少含有一个元素，是错误的。在后续学习中，需特别关注 零 的问题。

§2.2 顺序表

§2.2.1 顺序表的定义

顺序表是 线性表 采用 顺序存储结构 在计算机内存中的存储方式，它由多个连续的存储单元构成，每个存储单元存放线性表的一个元素。顺序表逻辑上相邻的数据元素在内存的存储结构中也是相邻的，不需要额外的内存空间来存放元素之间的逻辑关系。

§2.2.2 线性表基础操作

初始化、销毁函数置空。

指定下标访问$\mathrm{O}(1)$，插入、删除$\mathrm{O}(n)$。

提醒：具体操作的时间复杂度需要从其原理分析，不能死记硬背。