目录

1.线性表

2.顺序表

2.1 顺序表与线性表的关系?

2.2 概念和结构

2.3 分类

2.3.1 静态顺序表

2.3.2 动态顺序表

1.线性表

• 线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
• 线性表在逻辑上是线性结构，也就是说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
• 线性表在数据结构中有着重要的作用, 线性表在数据结构里，是搭建知识体系的“基石”，也是解决实际线性数据问题的“实用工具箱”，学好它对掌握更深入的数据结构和算法知识，有着“牵一发而动全身”的关键价值。

而本篇我们将要学习存储数据的第一种结构，也就是线性表中的顺序表

2.顺序表

2.1 顺序表与线性表的关系?

顺序表是线性表的一种核心存储实现方式，二者是“抽象概念”与“具体实现”的关系——线性表定义了数据的逻辑结构（一对一关系），顺序表则用“连续内存空间”的物理结构，将这种逻辑关系落地实现。
1. 逻辑结构 vs 物理结构

• 线性表：聚焦“数据元素间的逻辑关系”（仅规定元素有序、一对一，不关心元素存在哪里），是一种抽象的数据结构定义。
• 顺序表：聚焦“数据在内存中的存储方式”（要求元素存于连续地址空间，通过索引映射逻辑顺序），是线性表的具体物理实现。

2. 包含关系

• 线性表的实现方式不止顺序表一种，还包括链表（用分散内存+指针连接实现）；但顺序表完全遵循线性表的逻辑规则，是线性表的“子集”，所有线性表的通用操作（增、删、改、查），顺序表都能通过连续内存的特性来完成。

顺序表如何体现线性表的逻辑关系？
线性表要求“元素有序、每个元素（除首尾）有唯一前驱/后继”，顺序表通过以下方式保证这一逻辑：

• 用连续的内存单元存储元素，比如元素A存在地址100，下一个元素B就存在104（假设int类型占4字节），物理地址的连续性直接对应逻辑上的“先后顺序”；
• 用索引（下标） 唯一标识元素位置，比如索引0是首元素（无前驱），索引n-1是尾元素（无后继），索引i的元素前驱是i-1、后继是i+1，完美匹配线性表的“一对一”逻辑。

对比：顺序表与线性表的其他实现（链表）
二者同属线性表的实现，但存储方式不同，也体现了线性表“同一逻辑、多种物理实现”的灵活性：

• 顺序表：用“连续内存”实现线性表，优势是随机访问快（O(1)） ，劣势是中间增删需移动元素（O(n)）；
• 链表：用“分散内存+指针”实现线性表，优势是中间增删快（O(1)） ，劣势是无法随机访问（需遍历，O(n)）。

简言之，顺序表是线性表最经典、最常用的实现之一，它让线性表的“抽象逻辑”变成了可操作、可落地的“具体结构”。

2.2 概念和结构

概念：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。

它的结构如下:

2.3 分类

2.3.1 静态顺序表

静态顺序表：使用定长数组来存储数据元素的顺序表。在C语言中，一般通过预先定义好长度的数组来实现，并且会用一个变量记录当前已存储的有效数据个数 。例如：

2.3.2 动态顺序表

动态顺序表：基于动态内存分配（如C语言中的 malloc 和 free ）来管理存储空间的顺序表。它包含一个指向动态分配内存空间的指针，同时会记录当前已存储的数据个数以及整个顺序表的容量。当数据元素增加导致空间不足时，可以通过重新分配内存（如 realloc ）来扩大存储空间。示例代码如下

区别:

存储空间分配:

• 静态顺序表：在编译时就确定了数组的大小，其占用的内存空间是固定的。一旦定义，在程序运行过程中无法改变数组的长度。
• 动态顺序表：初始时分配一定大小的内存空间，在使用过程中，根据实际需求（如插入元素时发现空间不足），通过动态内存分配函数来增加或减少内存空间，具有更好的灵活性。

空间利用率:

• 静态顺序表：如果预先分配的空间过大，会造成内存浪费；若分配空间过小，在数据量超出时又无法存储更多数据，容易导致溢出错误 。例如定义了长度为100的静态顺序表，但实际只存储10个数据，就浪费了90个数据单元的空间。
• 动态顺序表：根据实际数据量动态调整内存空间，能更合理地利用内存资源。不过，动态内存分配和重新分配操作也会带来一定的额外开销（如频繁调用 realloc ）。

插入和删除操作的复杂度（涉及扩容情况）:

• 静态顺序表：插入和删除操作时，如果不涉及数组越界，时间复杂度主要是移动元素的开销，平均时间复杂度为 O(n) 。但如果在插入时数组已满，就无法完成操作，需要提前预估足够大的空间。
• 动态顺序表: 在空间足够的情况下，插入和删除操作与静态顺序表类似，平均时间复杂度为 O(n)。而当空间不足需要扩容时，除了移动元素的开销，还需要进行动态内存分配（如用 realloc ），虽然单次扩容操作时间复杂度较高，但均摊到每次插入操作上，平均时间复杂度仍接近 O(1) （采用均摊分析） 。

实现复杂度:

• 静态顺序表：实现相对简单，不需要处理动态内存分配、释放以及扩容等复杂逻辑，代码编写和理解起来相对容易。
• 动态顺序表：需要处理动态内存的申请、释放以及在空间不足时的扩容操作，实现过程相对复杂，同时还要注意内存泄漏等问题（如忘记释放不再使用的内存）。综上所述，通过静态表和动态表的对比区别，我们可以得出动态表更加全面，在写代码的过程中也更加复杂。所以我们下面学习的顺序表是围绕着动态顺序表展开的。

感谢大家的观看,  下篇文章，我们将讲述关于顺序表的实现，也是关于顺序表最重要的内容。