C语言数据结构——顺序表超详解！（含完整实现）
顺序表（Sequential List）是数据结构中最基础的线性结构之一，它使用数组来存储元素，实现逻辑上连续的存储。顺序表是数组的“升级版”，强调动态管理和操作。作为C语言入门数据结构的必学内容，它帮你理解内存分配、指针和基本算法。以下从基础到实现，一步步详解！
1. 顺序表概述
定义：顺序表是一种线性表，使用一组地址连续的存储单元（如数组）依次存储数据元素。元素的位置由索引（下标）决定，逻辑顺序与物理顺序一致。
核心特点：
- 存储方式：数组实现，固定或动态大小。
- 随机访问：通过下标 O(1) 时间访问任意元素。
- 逻辑结构：线性（每个元素有唯一前驱和后继，除首尾）。
与数组的区别：
- 数组是静态的，顺序表可以动态扩展（用 realloc 或自定义扩容）。
- 顺序表封装了操作（如插入、删除），更像一个“类”。
2. 顺序表的优缺点对比表
| 方面 | 优点 | 缺点 |
|---|---|---|
| 访问 | O(1) 时间随机访问（高效） | 无 |
| 插入/删除 | 尾部操作 O(1) | 中间/头部需移动元素，O(n) 时间（低效） |
| 空间 | 连续存储，空间利用率高 | 需预分配空间，浪费或溢出；扩容开销大 |
| 适用场景 | 频繁访问、少修改（如查询系统） | 频繁插入/删除（如队列）不适合，用链表更好 |
3. 顺序表的基本操作
顺序表的核心操作包括初始化、插入、删除、查找、遍历等。时间复杂度分析如下：
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 初始化 | O(1) | 分配数组并设置长度/容量 |
| 插入（指定位置） | O(n) | 需后移元素（最坏 n 次移动） |
| 删除（指定位置） | O(n) | 需前移元素 |
| 查找（按值） | O(n) | 线性扫描 |
| 访问（按索引） | O(1) | 直接下标 |
| 扩容 | O(n) | realloc 拷贝旧数据 |
| 遍历 | O(n) | 循环输出所有元素 |
4. C语言实现顺序表（完整代码）
在C语言中，我们用结构体封装顺序表：包含数组指针、当前长度（size）和容量（capacity）。支持动态扩容（初始容量10，每次扩容1.5倍）。
头文件（seqlist.h）：
#ifndef SEQLIST_H
#define SEQLIST_H
#include <stdio.h>
#include <stdlib.h> // malloc, realloc, free
// 定义数据类型（这里用 int，可换成其他）
typedef int ElemType;
// 顺序表结构体
typedef struct {
ElemType *data; // 动态数组
int size; // 当前元素个数
int capacity; // 当前容量
} SeqList;
// 函数声明
void initSeqList(SeqList *list); // 初始化
void destroySeqList(SeqList *list); // 销毁
int isEmpty(SeqList *list); // 判断空
int isFull(SeqList *list); // 判断满
void expandCapacity(SeqList *list); // 扩容
void insert(SeqList *list, int index, ElemType val); // 插入
void delete(SeqList *list, int index); // 删除
int find(SeqList *list, ElemType val); // 查找（返回索引）
void printSeqList(SeqList *list); // 打印
#endif源文件（seqlist.c）：
#include "seqlist.h"
// 初始化
void initSeqList(SeqList *list) {
list->capacity = 10; // 初始容量
list->data = (ElemType *)malloc(list->capacity * sizeof(ElemType));
if (list->data == NULL) {
printf("内存分配失败！\n");
exit(1);
}
list->size = 0;
}
// 销毁
void destroySeqList(SeqList *list) {
free(list->data);
list->data = NULL;
list->size = 0;
list->capacity = 0;
}
// 判断空
int isEmpty(SeqList *list) {
return list->size == 0;
}
// 判断满（实际用扩容避免满）
int isFull(SeqList *list) {
return list->size == list->capacity;
}
// 扩容（1.5倍增长）
void expandCapacity(SeqList *list) {
int newCapacity = list->capacity + (list->capacity >> 1); // 1.5倍
ElemType *newData = (ElemType *)realloc(list->data, newCapacity * sizeof(ElemType));
if (newData == NULL) {
printf("扩容失败！\n");
exit(1);
}
list->data = newData;
list->capacity = newCapacity;
}
// 插入（index 从0开始，合法范围[0, size]）
void insert(SeqList *list, int index, ElemType val) {
if (index < 0 || index > list->size) {
printf("插入位置无效！\n");
return;
}
if (isFull(list)) {
expandCapacity(list);
}
// 后移元素
for (int i = list->size; i > index; i--) {
list->data[i] = list->data[i - 1];
}
list->data[index] = val;
list->size++;
}
// 删除（index 从0开始）
void delete(SeqList *list, int index) {
if (index < 0 || index >= list->size) {
printf("删除位置无效！\n");
return;
}
// 前移元素
for (int i = index; i < list->size - 1; i++) {
list->data[i] = list->data[i + 1];
}
list->size--;
}
// 查找（返回第一个匹配索引，-1表示未找到）
int find(SeqList *list, ElemType val) {
for (int i = 0; i < list->size; i++) {
if (list->data[i] == val) {
return i;
}
}
return -1;
}
// 打印
void printSeqList(SeqList *list) {
if (isEmpty(list)) {
printf("顺序表为空！\n");
return;
}
printf("顺序表元素：");
for (int i = 0; i < list->size; i++) {
printf("%d ", list->data[i]);
}
printf("\n");
}测试主函数（main.c）：
#include "seqlist.h"
int main() {
SeqList list;
initSeqList(&list);
// 插入测试
insert(&list, 0, 10); // [10]
insert(&list, 1, 20); // [10,20]
insert(&list, 0, 5); // [5,10,20]
printSeqList(&list); // 输出: 5 10 20
// 查找
int idx = find(&list, 10);
printf("10 的位置: %d\n", idx); // 1
// 删除
delete(&list, 1); // [5,20]
printSeqList(&list); // 输出: 5 20
// 扩容测试（插入多个）
for (int i = 30; i <= 100; i += 10) {
insert(&list, list.size, i);
}
printSeqList(&list); // 会自动扩容
destroySeqList(&list);
return 0;
}编译运行：用 gcc 编译 gcc main.c seqlist.c -o seqlist，运行 ./seqlist。注意内存管理，避免泄漏！
5. 深入分析与注意事项
- 扩容策略：1.5倍增长常见（像 vector），避免频繁 realloc。
- 边界检查：插入/删除时检查 index，防止越界。
- 内存泄漏：总是配对 malloc/free，destroy 时释放。
- 改进版：可加清空（clear）、尾插（push_back）、尾删（pop_back）等操作，模拟 std::vector。
- 与链表比较：顺序表适合读多写少；链表适合写多读少。
掌握顺序表，你就打好了数据结构基础！接下来可以学链表、栈、队列。如果想看动态演示代码或调试技巧，继续问我~ 🚀
