数据结构 顺序表(1)
目录
1.线性表
2.顺序表
1.线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用
的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就是说是连续的一条直线。但是在物理结构上并不一定是连续的，
线性表在物理上存储时，通常以数组和链式结构的形式存储。
线性表在数据结构中有着重要的作用, 线性表在数据结构里，是搭建知识体系的“基石”，也是解决
实际线性数据问题的“实用工具箱”，学好它对掌握更深入的数据结构和算法知识，有着“牵一发而动
全身”的关键价值。
而本篇我们将要学习存储数据的第一种结构，也就是线性表中的顺序表:
2.顺序表
2.1 概念和结构
概念：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数
组存储。
它的结构如下:
2.2 分类
2.2.1 静态顺序表
-静态顺序表：使用定长数组来存储数据元素的顺序表。在C语言中，一般通过预先定义好长度的数
组来实现，并且会用一个变量记录当前已存储的有效数据个数 。例如：
2.2.2 动态顺序表
动态顺序表：基于动态内存分配（如C语言中的 malloc 和 free ）来管理存储空间的顺序表。它包
含一个指向动态分配内存空间的指针，同时会记录当前已存储的数据个数以及整个顺序表的容量。
当数据元素增加导致空间不足时，可以通过重新分配内存（如 realloc ）来扩大存储空间。示例代
码如下
区别:
存储空间分配:
- 静态顺序表：在编译时就确定了数组的大小，其占用的内存空间是固定的。一旦定义，在程序运
行过程中无法改变数组的长度。
- 动态顺序表：初始时分配一定大小的内存空间，在使用过程中，根据实际需求（如插入元素时发
现空间不足），通过动态内存分配函数来增加或减少内存空间，具有更好的灵活性。
空间利用率:
- 静态顺序表：如果预先分配的空间过大，会造成内存浪费；若分配空间过小，在数据量超出时又
无法存储更多数据，容易导致溢出错误 。例如定义了长度为100的静态顺序表，但实际只存储10个
数据，就浪费了90个数据单元的空间。
- 动态顺序表：根据实际数据量动态调整内存空间，能更合理地利用内存资源。不过，动态内存分
配和重新分配操作也会带来一定的额外开销（如频繁调用 realloc ）。
插入和删除操作的复杂度（涉及扩容情况）:
- 静态顺序表：插入和删除操作时，如果不涉及数组越界，时间复杂度主要是移动元素的开销，平
均时间复杂度为 O(n) 。但如果在插入时数组已满，就无法完成操作，需要提前预估足够大的空
间。
- 动态顺序表: 在空间足够的情况下，插入和删除操作与静态顺序表类似，平均时间复杂度为 O(n)
。而当空间不足需要扩容时，除了移动元素的开销，还需要进行动态内存分配（如用 realloc ），
虽然单次扩容操作时间复杂度较高，但均摊到每次插入操作上，平均时间复杂度仍接近 O(1) （采
用均摊分析） 。
实现复杂度:
- 静态顺序表：实现相对简单，不需要处理动态内存分配、释放以及扩容等复杂逻辑，代码编写和
理解起来相对容易。
- 动态顺序表：需要处理动态内存的申请、释放以及在空间不足时的扩容操作，实现过程相对复
杂，同时还要注意内存泄漏等问题（如忘记释放不再使用的内存）。
综上所述，通过静态表和动态表的对比区别，我们可以得出动态表更加全面，在写代码的过程中也
更加复杂。所以我们下面学习的顺序表是围绕着动态顺序表展开的。
感谢大家的观看, 下篇文章，我们将讲述关于顺序表的实现，也是关于顺序表最重要的内容。