【数据结构手札】顺序表实战指南（一）：线性表定义

🌈个人主页：聆风吟
🔥系列专栏：数据结构手札
🔖少年有梦不应止于心动，更要付诸行动。

文章目录

📚专栏订阅推荐
📋前言 - 顺序表文章合集
一. ⛳️线性表
- 1.1 🔔线性表的定义
- 1.2 🔔线性表的存储结构
二. ⛳️顺序表的定义
三. ⛳️顺序表的分类
- 3.1 🔔静态顺序表
- - 3.1.1 静态顺序表的结构定义
  - 3.1.2 静态顺序表的优缺点
- 3.2 🔔动态顺序表
- - 3.2.1 动态顺序表的结构定义
  - 3.2.2 动态顺序表的优缺点
- 3.3 🔔小结
📝全文总结

📚专栏订阅推荐

专栏名称	专栏简介
数据结构手札	本专栏主要是我的数据结构入门学习手札，记录个人从基础到进阶的学习总结。
数据结构手札・刷题篇	本专栏是《数据结构手札》配套习题讲解，通过练习相关题目加深对算法理解。

📋前言 - 顺序表文章合集

-【顺序表实战指南（一）：线性表定义 | 顺序表定义】

后续文章会陆续补充，尽情期待…

一. ⛳️线性表

1.1 🔔线性表的定义

线性表（linear list）：是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表有数组、链表、栈、队列、字符串等等。

这里需要强调一下几点：
首先它是一个序列。也就是说，元素之间是有顺序的。线性表中的元素称为结点，相邻结点之间的关系称为邻接关系。除第一个结点无前驱和最后一个结点无后继外，其他每个结点有且仅有一个前驱和一个后继。如下图所示：

注意：
线性表元素个数n (n >= 0)定义为线性表的长度，当n=0时，称为空表。

1.2 🔔线性表的存储结构

线性表的存储结构有顺序存储结构和链式存储结构两种。前者称为顺序表，后者称为链表：

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是线性的（顺序表物理连续，链表物理不连续），线性表在物理上存储时，通常以数组和链式结构的形式存储。

为了便于后续学习，本系列将首先讲解线性表的顺序存储结构 ——顺序表。线性表的链式存储将在后续章节展开。接下来，让我们正式进入今天的学习重点。

二. ⛳️顺序表的定义

顺序表（Sequential List）：用一段物理地址连续的存储单元依次存储数据元素的线性结构。一般情况下采用数组存储。在数组上完成数据的增删查改。

📝顺序表和数组的区别？
顺序表的底层结构是数组，对数组的封装，实现了常用的增删查改等接口。

通俗点讲：数组是 “兵”，顺序表是 “将”。数组提供了最基础的存储能力（士兵），而顺序表则用这些“士兵”组织起了一套完整的作战逻辑和指挥体系（将军），知道如何调度（增删）、如何侦查（查找）、如何整编（修改）。

三. ⛳️顺序表的分类

顺序表一般可以分为：静态顺序表和动态顺序表。

3.1 🔔静态顺序表

静态顺序表：指存储空间是固定的并且在程序运行前就已经确定大小的顺序表。它通常使用数组来实现，即通过定义一个固定长度的数组来存储数据元素。

📝知识点补充：
适用场景：数据量固定且已知，且不希望有运行时内存管理开销的场景。

3.1.1 静态顺序表的结构定义

//静态顺序表结构定义#defineMAXSIZE7//存储单元初始分配量typedefintSLDataType;//类型重命名，便于统一修改元素类型typedefstructSeqList{SLDataType data[MAXSIZE];//定长数组intsize;//当前有效数据的个数}SeqList;

我们可以发现描述静态顺序表需要三个属性：

存储空间的起始位置：数组data，他的存储位置就是存储空间的存储位置；
线性表的最大存储容量：数组长MAXSIZE；
线性表的当前位置：size。

3.1.2 静态顺序表的优缺点

✅优点：

实现简单，无内存管理成本
无需手动分配 / 释放内存，直接通过数组下标操作，代码量少。
访问效率极致，无扩容开销
数组物理地址连续，支持随机访问（时间复杂度 O(1)），且无需考虑扩容带来的拷贝开销，适合数据量固定、访问频繁的场景。
内存开销小（无冗余空间）
数组长度固定，不会像动态顺序表那样预留额外扩容空间，内存利用率在数据量刚好匹配数组长度时达到 100%。

❌缺点：

容量固定，灵活性极差
一旦数组长度定义，无法动态增加容量，若数据量超过数组长度会导致「溢出」；若数据量远小于数组长度，会造成大量内存浪费（例如定义 MAXSIZE=1000，实际仅存储 10 个元素）。
不适合动态数据场景
无法应对数据量不确定的场景（如用户输入、文件读取等动态数据），工程中几乎不用于核心业务，仅适用于简单演示或数据量固定的小众场景（如存储 12 个月的统计数据）。
扩展成本高
若必须扩容，需手动创建新的更大数组，将原数据拷贝到新数组，不仅代码繁琐，还会产生额外的时间开销（O(n)），且原数组内存无法回收（静态数组在栈上分配，生命周期结束后自动释放，无法手动干预）。

3.2 🔔动态顺序表

动态顺序表：通过动态分配内存空间，实现随着数据量的增加而不断扩容的效果。它的结构类似于一个数组，数据元素的存储是连续的，支持随机访问和顺序访问。

📝知识点补充：
为什么要有动态顺序表？静态顺序表的大小固定，当数据量超过预设大小时无法处理，动态顺序表解决了这个问题。
扩容策略：动态顺序表通常采用倍增策略（如 capacity *= 2），这是时间与空间的权衡。
适用场景：数据量不确定或可能增长，需要灵活存储管理的通用场景。

3.2.1 动态顺序表的结构定义

//动态顺序表结构定义typedefintSLDataType;//类型重命名，便于统一修改元素类型typedefstructSeqList{SLDataType*a;//指向动态开辟的数组intsize;//当前有效数据的个数intcapacity;//当前分配的总容量}SL;

我们可以发现描述动态顺序表也需要三个属性：

存储空间的起始位置：指针a，他里面存储的地址就是存储空间的地址；
线性表当前最大存储容量：capacity，可以通过动态分配的方式进行扩容；
线性表的当前位置：size。

3.2.2 动态顺序表的优缺点

✅优点：

容量灵活，适配动态数据场景
可根据数据量自动 / 手动扩容，避免溢出问题，能应对数据量不确定的场景（如用户注册信息存储、动态链表的底层实现等），是工程开发中的主流选择。
空间利用率更高（相对静态顺序表）
扩容时会预留一定冗余空间（如原容量 10，扩容后 20），既避免频繁扩容，又不会像静态顺序表那样预留过多无用空间，平衡了空间浪费与扩容效率。
支持手动释放内存，避免内存泄漏
动态数组在堆上分配内存，使用完毕后可通过free手动释放，适合长期运行的程序（如服务器程序），符合工程化内存管理规范。

❌缺点：

实现复杂，需处理内存细节
需手动实现初始化（malloc分配初始空间）、扩容（realloc重新分配空间 + 数据拷贝）、销毁（free释放内存），容易出现内存泄漏、野指针等问题。
扩容存在额外开销
扩容时需要将原数组数据拷贝到新数组，时间复杂度为O(n)，若扩容频率过高（如每次只扩容 1 个元素），会导致整体效率下降（通常采用倍数扩容减少频率）。
存在冗余空间浪费
扩容后未使用的冗余空间（如容量 20，仅存储 12 个元素）会占用内存，若数据量长期远小于容量，会造成一定的空间浪费。

3.3 🔔小结

对比维度	静态顺序表	动态顺序表
存储空间	固定大小数组	动态分配数组
容量	编译时确定	运行时可调整
结构成员	`data[MAXSIZE]`,`size`	`*a`,`size`,`capacity`
内存管理	栈上分配，自动释放	堆上分配，手动释放
空间效率	可能浪费或不足	相对高效（按需）
时间效率	访问极快，无分配开销	访问快，但扩容有开销
适用场景	数量固定且已知	数量变化较大

📝全文总结

本文围绕线性表与顺序表展开基础讲解，从概念定义到结构分类，层层递进地梳理了核心知识点：

线性表的本质：是n个具有相同特性数据元素的有限序列，逻辑上呈连续线性结构，物理存储则分为顺序存储和链式存储两种方式。
顺序表的定义：作为线性表的顺序存储结构，底层依托数组实现，是对数组的封装并提供增删查改等操作接口，与数组的区别在于“数组是存储载体，顺序表是带操作逻辑的线性结构”。
顺序表的两大分类
- 静态顺序表：使用固定长度数组存储，容量编译时确定，实现简单且访问高效，但灵活性差，仅适用于数据量固定的场景。
- 动态顺序表：通过动态内存分配实现，用指针指向堆区数组，搭配size（有效元素数）和capacity（总容量）管理数据，支持按需扩容，是工程中更常用的实现方式，缺点是需手动处理内存分配与释放，扩容存在数据拷贝开销。

本文为顺序表的后续学习（增删查改操作实现）奠定了理论基础，厘清了线性表与顺序表的关联和区别，帮助读者建立清晰的底层数据结构认知。

今天的干货分享到这里就结束啦！如果觉得文章还可以的话，希望能给个三连支持一下，聆风吟的主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是作者前进的最大动力！