摘要本文从线性表的定义出发介绍顺序表的概念与结构对比静态顺序表与动态顺序表的区别并完整实现一个基于 C 语言的动态顺序表涵盖初始化、销毁、打印、扩容、头尾插删、指定位置插删及查找等核心接口最后通过测试代码验证各功能的正确性。文章目录1. 线性表2. 顺序表2.1 概念与结构2.2 分类2.2.1 静态顺序表2.2.2 动态顺序表3. 动态顺序表的实现3.1 首先创建文件3.2 头文件 SeqList.h 声明3.3 SeqList.c 文件内实现函数3.3.1 包含头文件3.3.2 初始化函数的实现3.3.3 销毁函数的实现3.3.4 打印函数的实现3.3.5 扩容函数的实现3.3.6 头插函数的实现3.3.7 尾插函数的实现3.3.8 头删函数的实现3.3.9 尾删函数的实现3.3.10 指定位置插入数据3.3.11 指定位置删除数据3.3.12 查找指定数据3.4 test.c文件进行测试1. 线性表线性表linear list是 n 个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构常见的线性表有顺序表、链表、栈、队列、字符串……线性表在逻辑上是线性结构——连续的一条直线但是在物理结构上并不一定是连续的。线性表在物理上存储时通常以数组和链式结构的形式存储。2. 顺序表2.1 概念与结构概念顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。顺序表和数组的区别顺序表的底层结构是数组是对数组的封装实现了常用的增删改查等接口。2.2 分类2.2.1 静态顺序表使用定长数组存储元素// 静态顺序表typedefintSLDataType;#defineN6typedefstructSeqList{SLDataType a[N];// 定长数组intsize;// 有效数据个数}SL;缺陷空间给少了不够用给多了造成空间浪费。2.2.2 动态顺序表按需申请空间——容量不够时扩容是实际使用的方式。3. 动态顺序表的实现3.1 首先创建文件3.2 头文件 SeqList.h 声明// SeqList.h#pragmaonce//避免重复包含#define_CRT_SECURE_NO_WARNINGS//防止VS报错#includestdio.h#includestdlib.h#includeassert.h//定义数据类型typedefintSLDataType;// 动态顺序表 -- 按需申请typedefstructSeqList{SLDataType*arr;//创建指针变量intsize;// 有效数据个数intcapacity;// 空间容量}SL;// 初始化和销毁voidSLInit(SL*ps);voidSLDestroy(SL*ps);//打印voidSLPrint(SL*ps);// 扩容voidSLCheckCapacity(SL*ps);// 头部插入删除 / 尾部插入删除voidSLPushBack(SL*ps,SLDataType x);//尾部插入数据xvoidSLPopBack(SL*ps);//尾部删除数据voidSLPushFront(SL*ps,SLDataType x);//头部插入数据xvoidSLPopFront(SL*ps);//头部删除数据// 指定位置插入 / 删除数据voidSLInsert(SL*ps,intpos,SLDataType x);//在指定位置pos插入数据xvoidSLErase(SL*ps,intpos);//在指定位置pos删除数据// 查找intSLFind(SL*ps,SLDataType x);//查找数据x3.3 SeqList.c 文件内实现函数3.3.1 包含头文件// SeqList.c#includeSeqList.h3.3.2 初始化函数的实现//初始化voidSLInit(SL*ps){//断言assert(ps!NULL);//初始化数组ps-arrNULL;ps-sizeps-capacity0;}3.3.3 销毁函数的实现// 销毁voidSLDestroy(SL*ps){//断言assert(ps!NULL);//销毁值free(ps-arr);//置空ps-arrNULL;ps-sizeps-capacity0;}3.3.4 打印函数的实现// 打印voidSLPrint(SL*ps){assert(ps!NULL);for(inti0;ips-size;i)printf(%d ,ps-arr[i]);printf(\n);}3.3.5 扩容函数的实现// 扩容voidSLCheckCapacity(SL*ps){assert(ps!NULL);if(ps-sizeps-capacity){//如果原容量为零直接初始化为4//不为零则初始化为原容量的2倍intnewCapacityps-capacity0?4:2*ps-capacity;SLDataType*tmp(SLDataType*)realloc(ps-arr,newCapacity*sizeof(SLDataType));//检验是否成功扩容if(tmpNULL){perror(realloc failed:);exit(1);}ps-arrtmp;//更新指针ps-capacitynewCapacity;//更新容量信息}}3.3.6 头插函数的实现// 头插voidSLPushFront(SL*ps,SLDataType x){//断言assert(ps!NULL);//检查空间是否足够SLCheckCapacity(ps);//空间足够,所有数据向后移动for(intips-size;i0;i--){ps-arr[i]ps-arr[i-1];}ps-arr[0]x;//插入新数据ps-size;//有效数据个数增加}3.3.7 尾插函数的实现// 尾插voidSLPushBack(SL*ps,SLDataType x){//断言assert(ps!NULL);//检查空间是否足够SLCheckCapacity(ps);//空间足够直接插入ps-arr[ps-size]x;//后置插入数据后更新有效数据个数}3.3.8 头删函数的实现// 头删voidSLPopFront(SL*ps){//断言assert(ps!NULL);assert(ps-size!0);//直接将所有元素前移覆盖第一个元素for(inti0;ips-size-1;i){ps-arr[i]ps-arr[i1];}ps-size--;//更新有效数据个数}3.3.9 尾删函数的实现// 尾删voidSLPopBack(SL*ps){//断言assert(ps!NULL);assert(ps-size!0);//直接减少有效数据个数ps-size--;}3.3.10 指定位置插入数据// 指定位置之前插入voidSLInsert(SL*ps,intpos,SLDataType x){//断言assert(ps!NULL);assert(ps-sizepospos0);//检查空间是否足够SLCheckCapacity(ps);//将指定位置后数据后移for(intips-size;ipos;i--){ps-arr[i]ps-arr[i-1];}ps-arr[pos]x;//插入数据直接覆盖指定位置数据ps-size;//更新有效数据个数}3.3.11 指定位置删除数据// 指定位置删除数据voidSLErase(SL*ps,intpos){//断言assert(ps!NULL);assert(ps-sizepospos0);//直接将指定位置后数据前移覆盖指定位置数据for(intipos;ips-size-1;i){ps-arr[i]ps-arr[i1];}ps-size--;//更新有效数据个数}3.3.12 查找指定数据// 查找intSLFind(SL*ps,SLDataType x){//断言assert(ps!NULL);for(inti0;ips-size;i){if(ps-arr[i]x)returni;//查找成功则返回下标}return-1;}3.4 test.c文件进行测试intmain(){SL s;SLInit(s);SLPushBack(s,1);SLPushBack(s,2);SLPushBack(s,3);SLPushFront(s,0);SLPrint(s);// 0 1 2 3SLInsert(s,4,4);// 末尾插入SLPrint(s);// 0 1 2 3 4SLInsert(s,0,-1);// 头部插入SLPrint(s);// -1 0 1 2 3 4SLErase(s,0);SLPrint(s);// 0 1 2 3 4printf(find 3 %d\n,SLFind(s,3));// 3// 触发扩容for(inti5;i20;i)SLPushBack(s,i);SLPrint(s);SLDestroy(s);return0;}