)
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）：
#ifndefSEQLIST_H#defineSEQLIST_H#include<stdio.h>#include<stdlib.h>// malloc, realloc, free// 定义数据类型（这里用 int，可换成其他）typedefintElemType;// 顺序表结构体typedefstruct{ElemType*data;// 动态数组intsize;// 当前元素个数intcapacity;// 当前容量}SeqList;// 函数声明voidinitSeqList(SeqList*list);// 初始化voiddestroySeqList(SeqList*list);// 销毁intisEmpty(SeqList*list);// 判断空intisFull(SeqList*list);// 判断满voidexpandCapacity(SeqList*list);// 扩容voidinsert(SeqList*list,intindex,ElemType val);// 插入voiddelete(SeqList*list,intindex);// 删除intfind(SeqList*list,ElemType val);// 查找（返回索引）voidprintSeqList(SeqList*list);// 打印#endif源文件（seqlist.c）：
#include"seqlist.h"// 初始化voidinitSeqList(SeqList*list){list->capacity=10;// 初始容量list->data=(ElemType*)malloc(list->capacity*sizeof(ElemType));if(list->data==NULL){printf("内存分配失败！\n");exit(1);}list->size=0;}// 销毁voiddestroySeqList(SeqList*list){free(list->data);list->data=NULL;list->size=0;list->capacity=0;}// 判断空intisEmpty(SeqList*list){returnlist->size==0;}// 判断满（实际用扩容避免满）intisFull(SeqList*list){returnlist->size==list->capacity;}// 扩容（1.5倍增长）voidexpandCapacity(SeqList*list){intnewCapacity=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]）voidinsert(SeqList*list,intindex,ElemType val){if(index<0||index>list->size){printf("插入位置无效！\n");return;}if(isFull(list)){expandCapacity(list);}// 后移元素for(inti=list->size;i>index;i--){list->data[i]=list->data[i-1];}list->data[index]=val;list->size++;}// 删除（index 从0开始）voiddelete(SeqList*list,intindex){if(index<0||index>=list->size){printf("删除位置无效！\n");return;}// 前移元素for(inti=index;i<list->size-1;i++){list->data[i]=list->data[i+1];}list->size--;}// 查找（返回第一个匹配索引，-1表示未找到）intfind(SeqList*list,ElemType val){for(inti=0;i<list->size;i++){if(list->data[i]==val){returni;}}return-1;}// 打印voidprintSeqList(SeqList*list){if(isEmpty(list)){printf("顺序表为空！\n");return;}printf("顺序表元素：");for(inti=0;i<list->size;i++){printf("%d ",list->data[i]);}printf("\n");}测试主函数（main.c）：
#include"seqlist.h"intmain(){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// 查找intidx=find(&list,10);printf("10 的位置: %d\n",idx);// 1// 删除delete(&list,1);// [5,20]printSeqList(&list);// 输出: 5 20// 扩容测试（插入多个）for(inti=30;i<=100;i+=10){insert(&list,list.size,i);}printSeqList(&list);// 会自动扩容destroySeqList(&list);return0;}编译运行：用 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。
- 与链表比较：顺序表适合读多写少；链表适合写多读少。
掌握顺序表，你就打好了数据结构基础！接下来可以学链表、栈、队列。如果想看动态演示代码或调试技巧，继续问我~ 🚀
