数据结构（C语言篇）：（二）顺序表

_OP_CHEN

发布于 2026-01-14 09:29:47

610

文章被收录于专栏：C++C++

前言

顺序表是C语言中最基础且重要的线性数据结构之一，它以连续的存储空间和高效的随机访问特性著称。通过数组实现，顺序表在内存中占据一段地址连续的单元，能够以O(1)时间复杂度完成元素的查找和修改，为算法设计提供了高效的底层支持。然而，其插入删除操作可能引发大量数据移动，这种空间与时间的权衡正是学习顺序表的核心价值所在。掌握顺序表的增删改查操作，不仅能深入理解数据结构的存储本质，还能为后续学习链表、栈、队列等动态结构奠定基础。本文将从零开始剖析顺序表的实现原理与应用场景，帮助读者构建系统化的数据结构思维。下面就让我们正式开始吧！

一、线性表的定义

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

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

二、顺序表

2.1 概念与结构

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

那么我们可以思考一下，顺序表和数组的区别是什么呢？

实际上，顺序表的底层结构就是数组，对数组的封装，实现了常用的增删查改等接口。顺序表和数组的关系就像下图所示：

2.2 分类

2.2.1 静态顺序表

静态顺序表 是使用定长（固定大小）的数组来存储数据元素的顺序表。

它的两个核心特征是：

顺序存储：在内存中占用一段连续的存储空间，依次存放各个数据元素。这意味着只要知道第一个元素的地址（基地址），通过数学推导就可以直接计算出任何一个元素的位置，因此访问速度极快（随机访问特性）。
静态分配：数组的长度（即顺序表的最大容量）在程序编译阶段就已经确定。通常通过定义一个固定大小的数组来实现（如 int data[100];）。这个容量一旦定义，在程序运行期间就无法再改变。

一个静态顺序表通常由两部分信息组成：

存储数据的数组 (data)：一个固定长度的数组，用于实际存储数据元素。
当前长度 (length)：一个整型变量，用于记录顺序表中当前实际存在的数据元素个数，它一定小于或等于数组的最大容量。

其结构示意如下所示：

静态顺序表具有以下优点：

随机访问效率高：由于内存连续，可以通过下标直接访问任何一个元素（即 data[i]），时间复杂度为 O(1)。这是它最突出的优点。
存储密度高：无需为元素之间的逻辑关系增加额外的存储开销（例如链表的指针），几乎所有的存储空间都用来存数据。
结构简单，易于实现。

当然，静态顺序表还是存在不少缺陷的，比如当空间给少了就会导致内存不够用，给多了又会造成内存的浪费。还有插入和删除操作效率低等问题。

2.2.2 动态顺序表

动态顺序表是使用动态内存分配的数组来实现的顺序表。它与静态顺序表的主要区别在于：其存储空间是在程序运行时动态申请和调整的，而不是在编译期就固定好的。

我们可以做个简单的简单比喻：

静态顺序表像一个固定大小的玻璃杯，水（数据）多了就会溢出；而动态顺序表像一个智能伸缩杯，当水快满时，它会自动换一个更大的杯子，把原来的水倒进去。

一个动态顺序表通常由三个关键部分组成：

数据指针 (*data): 指向动态分配的数组内存块的首地址。
当前大小 (size): 记录表中当前实际存储的元素个数。
当前容量 (capacity): 记录当前分配的内存空间最多能容纳的元素个数。

动态顺序表的结构定义如下：

其中，SLDatatype是我们自定义的一个数据类型，在这我们将它定义为int类型，如下：

typedef int SLTDataType;

动态顺序表有如下优点：

随机访问高效：支持O(1)时间复杂度的按索引访问。
存储密度高：除了数据本身，几乎不需要额外空间。
容量可动态增长：无需预先知道数据规模，实用性极强。
尾部操作高效：在尾部插入/删除元素的时间复杂度为O(1)(均摊)。

同样地，动态顺序表也有着不少缺点：

中间插入删除慢：需要移动元素，时间复杂度为O(n)。
扩容有性能开销：扩容时需要数据拷贝，虽然均摊后性能很好，但单次扩容开销较大。
可能产生内存碎片：频繁申请释放不同大小的内存块可能产生碎片。
需要手动管理内存：在C等语言中需要小心处理，否则容易造成内存泄漏。

2.3 动态顺序表的实现

由于静态顺序表的实现比较简单，且只要学会了动态顺序表的实现，实现静态顺序表就基本不成问题了。这里我们就来学习一下动态顺序表的实现。

2.3.1 工程结构

要实现动态顺序表，我们需要准备三个文件，分别是：

头文件（SeqList.h）：用于定义动态顺序表的结构，并声明函数。
源文件（SeqList.c）：用于定义函数，需要包含SeqList.h头文件。
测试文件（test.c）：用于测试所定义的函数。

2.3.2 函数声明与定义

（1）SLInit( )函数（动态顺序表初始化函数）

因为在此函数中，形参的改变要影响实参，所以我们在这要给该函数传一个变量的地址，即传一个指针变量，其为SL*类型。

在头文件中声明如下：

void SLInit(SL* ps);

对函数在源文件中定义如下：

void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

上述函数定义的核心思路是在创建顺序表时不预先分配任何内存资源，而是将其初始化为一个完全的"空壳"状态。这种设计的主要考量是最大化资源利用效率和最小化初始化开销。通过将arr指针设为NULL并将size和capacity都置为0，函数确保了初始化操作几乎零成本完成，且永远不会因为内存分配失败而报错。

这种"懒加载"的方式特别适合那些使用情况不确定的场景——如果顺序表最终没有被使用，就不会有任何内存浪费；而当真正需要插入数据时，再在第一次插入操作中动态分配内存并逐步扩容。这种设计虽然会导致第一次插入操作相对较慢（需要额外处理内存分配），但换来了初始化阶段极高的效率和极强的稳定性，是一种典型的"用时再取"的资源管理哲学。

（2）SLPushBack( )函数（尾插函数）

在头文件中声明如下：

//尾插
void SLPushBack(SL* ps, SLTDataType x);

下面我们来分析一下函数实现的思路：

1. 空间足够时：

触发条件：ps->size < ps->capacity（当前元素数小于容量）

处理逻辑如下：

ps->arr[ps->size] = x;  // 直接写入数据
ps->size++;             // 更新元素计数
return;                 // 立即返回，结束函数

2. 空间不够时：

触发条件：ps->size >= ps->capacity（需要扩容）

处理逻辑如下：

// 完整的扩容流程
1. 计算新容量 → 智能容量决策
2. 分配新内存 → 使用realloc智能扩容  
3. 错误处理 → 严格的内存分配检查
4. 更新状态 → 重置指针和容量值
5. 执行插入 → 完成原本的插入操作

为了有效降低增容的次数，减少空间的浪费，我们可以这样处理容量：

int newCapacity = (ps->capacity == 0) ? 4 : (ps->capacity * 2);

初始状态：容量为0 → 分配基础容量4
扩容状态：容量不为0 → 采用翻倍策略

尾插代码的完整实现如下：

//尾插
void SLPushBack(SL* ps, SLTDataType x)
{
	assert(ps);
	//空间不够
	if (ps->size == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		//增容
		SLTDataType* tmp = (SLTDataType*)realloc(ps->arr, newCapacity * sizeof(SLTDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
	//空间足够
	ps->arr[ps->size++] = x;
}

我们可以将中间的容量判断部分封装成一个独立的CheckCapacity( )函数，如下所示：

void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		//增容
		SLTDataType* tmp = (SLTDataType*)realloc(ps->arr, newCapacity * sizeof(SLTDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}

//尾插
void SLPushBack(SL* ps, SLTDataType x)
{
	assert(ps);
	//空间不够
	SLCheckCapacity(ps);
	//空间足够
	ps->arr[ps->size++] = x;
}

（3）SLPushFront( )函数（头插函数）

在头文件中声明如下：

//头插
void SLPushFront(SL* ps, SLTDataType x);

本函数的核心算法采用向后整体位移策略，通过从尾部开始向前循环（for (int i = ps->size; i > 0; i--)），将每个元素向后移动一位，为新的头元素腾出空间。这种从后向前移动的顺序能够避免数据覆盖问题。最后，在腾出的数组首位置插入新元素并更新大小计数器，整个过程形成了完整的插入操作闭环。完整代码如下所示：

//头插
void SLPushFront(SL* ps, SLTDataType x)
{
	//温柔的处理方式
	//if (ps == NULL)
	//{
	//	return;
	//}
	assert(ps != NULL); //等价于assert(ps）
	//空间不够
	SLCheckCapacity(ps);
	//数据整体向后挪动一位
	for (int i = ps->size; i > 0 ; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size++;
}

该函数的时间复杂度为O(n)。

（4）SLPopBack( )函数（尾插函数）

头文件中的声明如下：

//尾删
void SLPopBack(SL* ps);

函数定义的主要实现逻辑是通过简单地将大小计数器ps->size减一来实现删除效果，这是一种逻辑删除而非物理删除的方式。

函数完整定义如下：

//尾删
void SLPopBack(SL* ps)
{
	assert(ps && ps->size);
	ps->size--;
}

该函数的时间复杂度为O(1)。

（5）SLPopFront( )函数（头删函数）

头文件中声明如下：

//头删
void SLPopFront(SL* ps);

函数定义部分的核心算法我们采用向前整体位移策略，通过从头部开始向后循环（for (int i = 0; i < ps->size-1; i++)），将每个后续元素向前移动一位，覆盖掉需要删除的头部元素。最后通过简单地将大小计数器ps->size减一来完成删除操作。完整代码如下所示：

//头删
void SLPopFront(SL* ps)
{
	assert(ps && ps->size);
	//数据整体向前挪动一位
	for (int i = 0; i < ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

该函数的时间复杂度为O(n)。

（6）SLInsert( )函数（在指定位置之前插入数据）

在头文件中声明如下：

//指定位置之前插⼊
void SLInsert(SL* ps, int pos, SLTDataType x);

在定义部分，函数首先调用SLCheckCapacity进行容量检查，确保有足够空间容纳新元素。核心算法则采用从后向前的精准位移策略（for (int i = ps->size; i > pos; i--)），将指定位置及之后的元素逐个向后移动一位，为新元素腾出精确的插入空间。最后在腾出的指定位置插入新元素并更新大小计数器。完整代码如下所示：

//指定位置之前插⼊
void SLInsert(SL* ps, int pos, SLTDataType x)
{
	assert(ps);
	//0<= pos < ps->size
	assert(pos >= 0 && pos < ps->size);
	//判断空间是否足够
	SLCheckCapacity(ps);
	//pos及之后数据向后挪动一位
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
}

该函数的时间复杂度为O(n)。

（7）SLErase( )函数（删除指定位置的数据）

头文件中声明如下：

//删除pos位置的数据
void SLErase(SL* ps, int pos);

在定义部分，核心算法采用从前向后的精准位移策略（for (int i = pos; i < ps->size-1; i++)），将指定位置之后的所有元素逐个向前移动一位，覆盖掉需要删除的目标元素。最后同样通过简单地将大小计数器ps->size减一来完成删除操作。完整代码如下：

//删除pos位置的数据
void SLErase(SL* ps, int pos)
{
	assert(ps);
	//pos:[0，ps->size)
	assert(pos >= 0 && pos < ps->size);

	//pos后面的数据向前挪动一位
	for (int i = pos; i < ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

（8）SLFind( )函数（查找指定数据）

头文件中声明如下：

//查找
int SLFind(SL* ps, SLTDataType x);

在函数定义部分，核心算法采用线性遍历搜索策略（for (int i = 0; i < ps->size; i++)），从数组起始位置开始逐个比较每个元素与目标值x。

不仅如此，我们还应该对函数设计明确的返回协议：当找到目标元素时，立即返回该元素的位置索引（正值）；当遍历完所有元素仍未找到时，返回特定的错误标识-1。调用者可以通过判断返回值是否大于等于0来快速确定查找是否成功。完整代码如下所示：

//查找
int SLFind(SL* ps, SLTDataType x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			//找到了
			return i;
		}
	}
	//未找到
	return -1;
}