C语言顺序表详解：静态与动态实现及核心操作

顺序表的概念与物理特性

线性表（Line List）是 n 个具有相同特性的数据元素的有限序列，是实际开发中最广泛使用的数据结构之一。常见的线性表包括顺序表、链表、栈、队列和字符串。虽然线性表在逻辑上表现为一条连续的直线，但在物理内存的存储上，并不一定连续，通常以数组和链式结构两种形式存在。

顺序表是采用一段地址连续的存储单元依次存储数据元素的线性结构，一般情况下基于数组实现。根据容量的固定与否，顺序表可分为两类：

• 静态顺序表：使用定长数组存储，容量在编译时确定，修改需改源码或宏定义。
• 动态顺序表：使用动态开辟的内存（堆区）存储，运行时可根据需要扩充或收缩。

静态顺序表实现

结构定义与初始化

为了便于管理和扩展类型，建议首先定义数据类型的宏或别名，并使用结构体封装底层数组和有效元素数量。以下是基础的结构定义：

#define N 10  // 定义常量大小，方便后续维护
typedef int SQDataType; // 重命名数据类型，提高兼容性

struct SeqList {
	SQDataType a[N]; // 预分配的定长数组
	int size;        // 当前已存放的有效数据个数
};

初始化顺序表的目标是将内部状态重置为“空”。这通常涉及将数组内容清零并归零计数器。

#include <stdio.h>
#include <string.h>

void SeqListInit(struct SeqList *ps) {
	// 按字节将内存置为 0
	memset(ps->a, 0, sizeof(SQDataType) * N);
	ps->size = 0;
}

void TestSeqList() {
	struct SeqList sl;
	SeqListInit(&sl); // 传址调用，确保外部变量被修改
}

int main() {
	TestSeqList();
	return 0;
}

提示：若觉得每次定义结构体繁琐，可使用 typedef struct { ... } SL; 语法为结构体重命名。

基本操作：尾插法

在尾部追加数据是最简单的插入方式。操作核心在于判断当前是否还有剩余空间，若有则在下标等于 size 的位置赋值并递增计数器。

void SeqListPushBack(struct SeqList *ps, SQDataType x) {
	if (ps->size >= N) {
		printf("SeqList is full!\n");
		return;
	}
	// 直接对当前最后一个位置的下一个空间赋值
	ps->a[ps->size] = x;
	ps->size++; // 逻辑长度 +1
}

如图所示，当顺序表有 7 个空间且存入了 5 个数据（即 size=5）时，新数据的下标应为 5，恰好对应 a[ps->size]。静态顺序表的主要缺点在于容量不足时需改写代码，而容量过大则会浪费系统内存。

动态顺序表实现

为解决静态顺序表的局限性，引入了动态管理内存的方案。其核心差异在于使用指针指向堆区内存，并维护 capacity（总容量）来跟踪可用空间。

结构定义与动态初始化

初始化阶段，指针应设为空，大小和容量均设为 0，表示未分配任何空间。

struct DynSeqList {
	SQDataType* a;     // 动态内存指针
	int size;          // 有效数据个数
	int capacity;      // 当前分配的总容量
};

void DynSeqListInit(struct DynSeqList *ps) {
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

核心机制：空间检查与扩容（realloc）

在所有涉及增加数据元素的接口（如头插、尾插、任意插入）中，第一步必须是判断空间是否充足。如果空间已满，需调用 realloc 进行扩容。扩容策略通常是将容量翻倍（原容量为 0 时设为初始值如 4），以减少频繁内存交换带来的性能损耗。

动态顺序表接口大全

第 1 步：尾部插入（PushBack）

目的：在列表末尾添加元素。 入口参数：struct DynSeqList *ps, SQDataType x。
动作逻辑：

1. 容量检查：若 size == capacity，调用 realloc 扩容。
2. 数据落盘：ps->a[ps->size] = x。
3. 状态更新：ps->size++。

void PushBack(DynSeqList *ps, SQDataType x) {
	if (ps->size == ps->capacity) {
		int newcap = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SQDataType* tmp = (SQDataType*)realloc(ps->a, newcap * sizeof(SQDataType));
		if (!tmp) {
			printf("realloc failed\n");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcap;
	}
	ps->a[ps->size] = x;
	ps->size++;
}

第 2 步：头部插入（PushFront）

目的：在列表最前端添加元素。
动作逻辑：由于数组头部没有前置节点，插入必须将现有所有元素整体向后移动一位，腾出下标 0 的位置。

void PushFront(DynSeqList *ps, SQDataType x) {
	// 1. 同样先处理扩容逻辑（此处复用上述扩容思想）
	if (ps->size == ps->capacity) { /*...同上...*/ }
	
	// 2. 数据搬移：从后向前遍历，依次后移
	int end = ps->size - 1;
	while (end >= 0) {
		ps->a[end + 1] = ps->a[end];
		--end;
	}
	// 3. 插入新值
	&nbs;nbsp; ps->a[0] = x;
	&nbs;nbsp; ps->size++;
}

第 3 步：尾部删除（PopBack）

目的：移除末尾元素。
结果状态：实际上不需要修改数组内的数值，只需将逻辑长度 size 减 1 即可。下次访问时，编译器会忽略超出的旧数据。

void PopBack(DynSeqList *ps) {
	assert(ps->size > 0); // 必须有元素可删
	&nbs;nbsp; ps->size--;
}

第 4 步：头部删除（PopFront）

目的：移除头部元素。
动作逻辑：将所有剩余元素整体向前挪动一位，覆盖掉第一个元素，随后缩小 size。

void PopFront(DynSeqList *ps) {
	assert(ps->size > 0);
	int start = 1;
	while (start < ps->size) {
		ps->a[start - 1] = ps->a[start];
		&nbs;nbsp; start++;
	}
	&nbs;nbsp; ps->size--;
}

第 5 步：任意位置插入（Insert）

目的：在下标 pos 处插入新值。
安全警告：严禁非法越界访问，插入位置必须小于当前有效数据数。同时，操作前仍需进行扩容校验。

void Insert(DynSeqList *ps, int pos, SQDataType x) {
	assert(pos < ps->size); // 防止越界
	// 扩容检测...
	int end = ps->size - 1;
	// 从插入点开始，直至末尾，依次向后挪一位
	while (end >= pos) {
		ps->a[end + 1] = ps->a[end];
		&nbs;nbsp; end--;
	}
	&nbs;nbsp; ps->a[pos] = x;
	&nbs;nbsp; ps->size++;
}

第 6 步：任意位置删除（Erase）

目的：移除下标 pos 处的元素。
动作逻辑：将 pos 之后的所有元素向前覆盖移动一位，最后减小 size。

void Erase(DynSeqList *ps, int pos) {
	assert(pos < ps->size);
	int start = pos + 1;
	while (start < ps->size) {
		ps->a[start - 1] = ps->a[start];
		&nbs;nbsp; start++;
	}
	&nbs;nbsp; ps->size--;
}

总结

顺序表是一种高效利用 CPU 缓存的数据结构，特别适合随机读取的场景。实现中的关键在于处理好指针、长度与容量的边界关系。上述演示的所有“删除”操作仅改变逻辑上的长度标记，并未在物理层面释放或移动多余的内存区块。以上就是C语言编程简单却重要的数据结构顺序表全面讲解的详细内容，更多关于C语言数据结构顺序表的资料请关注本站其它相关文章！