【数据结构】超详细动态顺序表实现（C语言）完整代码+原理解析

【数据结构】超详细动态顺序表实现C语言完整代码原理解析一、前言顺序表是数据结构中最基础、最重要的线性结构之一它采用连续的内存空间存储数据支持随机访问查询效率极高。顺序表分为两种静态顺序表固定数组大小空间开辟过多浪费、开辟过少溢出灵活性极差动态顺序表基于动态内存开辟按需扩容灵活高效实际开发中主流使用本文将手把手实现动态顺序表包含初始化、增删查改、扩容、销毁等全套核心功能附带完整可运行代码、详细注释和易错点解析。二、动态顺序表结构设计动态顺序表需要三个核心成员变量动态数组指针、有效数据个数、总容量以此实现动态扩容功能。// 重定义数据类型方便后期修改存储类型typedefintSLDataType;// 动态顺序表结构体typedefstructSeqList{SLDataType*arr;// 指向动态开辟的数组intsize;// 当前有效数据个数intcapacity;// 当前数组总容量}SL;核心逻辑当有效数据个数size等于总容量capacity时自动扩容保证数据正常插入。三、头文件声明SeqList.h头文件负责结构体定义、函数声明、头文件包含实现代码解耦供源文件调用。#includestdio.h#includestdlib.h#includeassert.h//定义动态顺序表的结构typedefintSLDataType;typedefstructSeqList{SLDataType*arr;intsize;//有效数据个数intcapacity;//空间容量}SL;//打印顺序表voidSLPrint(SL*ps);//初始化顺序表voidSLInit(SL*ps);//检查容量不足则扩容voidSLCheckCapacity(SL*ps);//尾插数据voidSLPushBack(SL*ps,SLDataType x);//头插数据voidSLPushFront(SL*ps,SLDataType x);//尾删数据voidSLPopBack(SL*ps);//头删数据voidSLPopFront(SL*ps);//指定位置插入数据voidSLInsert(SL*ps,intpos,SLDataType x);//删除指定位置数据voidSLErase(SL*ps,intpos);//查找数据返回下标intSLFind(SL*ps,SLDataType x);//销毁顺序表voidSLDestory(SL*ps);四、功能实现详解SeqList.c本章节逐行解析所有核心功能包含逻辑思路、代码实现、易错点提醒。4.1 顺序表初始化初始化时将动态数组置空有效个数和容量归零创建一个空的顺序表。#includeSeqList.h//初始化顺序表voidSLInit(SL*ps){ps-arrNULL;ps-sizeps-capacity0;}4.2 容量检查与动态扩容这是动态顺序表的核心函数。当数据存满时自动扩容初始容量为0时默认开辟4个空间后续每次二倍扩容。//判断空间是否足够不足则扩容voidSLCheckCapacity(SL*ps){if(ps-sizeps-capacity){// 空表默认开辟4个空间非空二倍扩容intnewCapacityps-capacity0?4:ps-capacity*2;// 动态内存扩容SLDataType*tmp(SLDataType*)realloc(ps-arr,newCapacity*sizeof(SLDataType));if(tmpNULL){perror(realloc fail);exit(1);}ps-arrtmp;ps-capacitynewCapacity;}}易错点perror必须传入字符串常量.4.3 顺序表打印遍历有效数据打印所有存储的值用于调试查看结果。voidSLPrint(SL*ps){for(inti0;ips-size;i){printf(%d ,ps-arr[i]);}printf(\n);}4.4 尾插数据在顺序表末尾插入数据先检查扩容再直接在末尾赋值效率较高。//尾插数据voidSLPushBack(SL*ps,SLDataType x){assert(ps);// 断言防止空指针传入SLCheckCapacity(ps);// 检查扩容ps-arr[ps-size]x;// 末尾赋值有效个数1}4.5 头插数据在表头插入数据需要将所有原有数据整体后移一位空出头部位置再赋值。//头插数据voidSLPushFront(SL*ps,SLDataType x){assert(ps);SLCheckCapacity(ps);// 数据后移for(intips-size;i0;i--){ps-arr[i]ps-arr[i-1];}ps-arr[0]x;ps-size;}4.6 尾删数据删除末尾数据无需移动数据直接将有效数据个数减一即可逻辑删除。//尾删数据voidSLPopBack(SL*ps){assert(psps-size);// 防止空表删除ps-size--;}4.7 头删数据删除头部数据将后续所有数据整体前移一位覆盖头部数据。//头删数据voidSLPopFront(SL*ps){assert(psps-size);for(inti0;ips-size-1;i){ps-arr[i]ps-arr[i1];}ps-size--;}4.8 指定位置插入数据支持任意合法下标位置插入数据先校验下标合法性数据后移再插入新值。//在指定位置之前插入数据voidSLInsert(SL*ps,intpos,SLDataType x){assert(ps);assert(pos0posps-size);// 校验下标合法范围SLCheckCapacity(ps);// pos及之后数据后移for(intips-size;ipos;i--){ps-arr[i]ps-arr[i-1];}ps-arr[pos]x;ps-size;}4.9 删除指定位置数据删除指定下标数据后续数据整体前移覆盖完成删除。//删除指定位置的数据voidSLErase(SL*ps,intpos){assert(ps);assert(pos0posps-size);// pos之后的数据前移for(intipos;ips-size-1;i){ps-arr[i]ps-arr[i1];}ps-size--;}注意删除操作不会增加数据量无需扩容检查。4.10 数据查找遍历顺序表找到目标数据返回对应下标未找到返回-1。//查找数据返回下标intSLFind(SL*ps,SLDataType x){assert(ps);for(inti0;ips-size;i){if(ps-arr[i]x){returni;// 找到返回下标}}return-1;// 遍历结束未找到返回-1}4.11 顺序表销毁释放动态开辟的堆内存防止内存泄漏重置结构体成员变量。//销毁顺序表voidSLDestory(SL*ps){assert(ps);if(ps-arr)free(ps-arr);// 释放堆区空间ps-arrNULL;ps-sizeps-capacity0;}五、测试用例main函数完整可运行测试代码全覆盖验证所有增删查改功能。#includeSeqList.hvoidTestSeqList(){SL sl;SLInit(sl);// 尾插测试SLPushBack(sl,1);SLPushBack(sl,2);SLPushBack(sl,3);SLPushBack(sl,4);printf(尾插后);SLPrint(sl);// 头插测试SLPushFront(sl,0);printf(头插后);SLPrint(sl);// 指定位置插入SLInsert(sl,2,99);printf(下标2插入99后);SLPrint(sl);// 删除测试SLErase(sl,2);printf(删除下标2数据后);SLPrint(sl);// 查找测试intposSLFind(sl,3);if(pos!-1)printf(数据3的下标为%d\n,pos);elseprintf(未找到该数据\n);// 头尾删除SLPopBack(sl);SLPopFront(sl);printf(头尾删除后);SLPrint(sl);// 销毁顺序表SLDestory(sl);}intmain(){TestSeqList();return0;}运行结果尾插后1 2 3 4 头插后0 1 2 3 4 下标2插入99后0 1 99 2 3 4 删除下标2数据后0 1 2 3 4 数据3的下标为3 头尾删除后1 2 3六、顺序表优缺点总结6.1 优点内存连续支持随机访问通过下标可直接访问元素查询效率 O(1)内存利用率高无额外指针开销缓存命中率高6.2 缺点插入、删除非末尾数据时需要移动大量元素时间复杂度 O(N)动态扩容需要重新开辟内存、拷贝数据存在性能损耗不能灵活增减空间扩容后多余空间暂时浪费七、全文总结本文完整实现了C语言动态顺序表的全部核心功能修复了新手常见的代码BUG包含初始化、动态扩容、头尾增删、指定位置增删、数据查找、内存销毁等功能。顺序表是后续栈、队列、数组算法题的基础掌握动态扩容逻辑和增删原理是入门数据结构的关键第一步。