文章目录1.结构体与接口(SqList.h)2.完整实现(SqList.c)3.测试(test.c)1.结构体与接口(SqList.h)#pragmaonce// SqList.h 一般这些接口函数声明放到.h中// 下面的接口函数的实现放到SqList.cpp中#includestdio.h#includestdlib.h#includestdbool.h#includeassert.hstructSnakeData{introw;intcol;// ...};// typedef是为了方便类型替换//typedef SnakeData SqDataType; // 数据元素类型typedefintSqDataType;// 数据元素类型// typedef struct SequenceList{typedefstruct{SqDataType*arr;// 存储数据的动态数组的指针intsize;// 记录顺序表中已经存入的数据个数intcapacity;// 动态数组的容量空间的大小}SqList;// 初始化顺序表voidSqListInit(SqList*ps);// 有些书本上的用法//void SqListInit(SqList s);// 销毁顺序表voidSqListDestroy(SqList*ps);// 返回顺序表中第i个下标位置元素的值SqDataTypeGetElem(SqList*ps,inti);// 返回第一个等于x的数据元素的下标若不存在返回-1intLocateElem(SqList*ps,SqDataType x);// 书本i通常是位序位序是从1开始// 我们实现的时候i用的是下标// 在顺序表的第i个位置插入元素xvoidSqListInsert(SqList*ps,inti,SqDataType x);// 删除顺序表中第i个元素并返回删除的值SqDataTypeSqListDelete(SqList*ps,inti);// 打印顺序表中的元素voidSqListPrint(SqList*ps);// 检测顺序表是否为空空返回true否则返回falseboolEmptySqList(SqList*ps);// 获取顺序表中有效元素个数intSqListSize(SqList*ps);// 以下接口复用上面的Insert和Delete即可完成// 头插尾插voidSqListPushBack(SqList*ps,SqDataType x);voidSqListPushFront(SqList*ps,SqDataType x);// 头删尾删voidSqListPopBack(SqList*ps);voidSqListPopFront(SqList*ps);2.完整实现(SqList.c)/* * SqList.c * 动态顺序表Sequential List各接口函数的实现。 * * 对应的声明见 SqList.hSqList 结构体由 arr动态数组指针、size有效元素 * 个数、capacity容量三个成员组成SqDataType 为数据元素类型目前是 int。 * * 本文件统一约定 * 1. 参数 i 一律表示“下标”从 0 开始插入时 i 的合法范围是 [0, size] * 删除/读取时是 [0, size-1]注意与书本上从 1 开始的“位序”不同。 * 2. 每个函数入口都用 assert 检查 ps 非空便于在调试期尽早发现空指针。 * 3. 扩容策略容量不足时按原来的 2 倍申请新空间使连续插入的均摊复杂度为 O(1)。 * * 说明以下注释均是在原代码基础上新增的原代码的逻辑与顺序没有做任何改动。 */#define_CRT_SECURE_NO_WARNINGS1// 初始化顺序表#includeSqList.h// 初始化与销毁 /* * SqListInit —— 初始化顺序表 * param ps 指向待初始化的顺序表 * 初始申请可容纳 4 个元素的动态数组并把 size 置 0、capacity 置 4。 * 若内存申请失败则打印错误信息并直接返回此时 arr 为 NULL。 */voidSqListInit(SqList*ps){assert(ps);// 初始容量为 4申请 4 个 SqDataType 大小的连续堆空间ps-arr(SqDataType*)malloc(sizeof(SqDataType)*4);if(ps-arrNULL){//申请失败则退出printf(InitSqList: 内申请空间失败 !!!\n);//exit(-1);return;}// 记录有效元素个数与当前容量ps-size0;ps-capacity4;}/* * SqListDestroy —— 销毁顺序表 * 释放动态数组占用的堆空间并把 arr 置为 NULL、size 与 capacity 清零 * 避免留下悬空指针重复调用本函数也是安全的。 */voidSqListDestroy(SqList*ps){assert(ps);// arr 非空说明空间申请成功过需要释放if(ps-arr){free(ps-arr);// 释放后复位成员避免后续误用已释放的内存ps-size0;ps-capacity0;ps-arrNULL;}}/* * SqListInsert —— 在下标 i 处插入元素 x * param ps 指向顺序表 * param i 插入位置的下标合法范围 [0, size]i size 即尾插 * param x 待插入的数据元素 * 若容量已满先按 2 倍扩容再把下标 [i, size-1] 的元素整体后移一位 * 空出下标 i 的位置放入 x最后 size 加 1。时间复杂度 O(n)。 */voidSqListInsert(SqList*ps,inti,SqDataType x){assert(ps);// 下标合法性检查i 可以等于 size尾插但不能越界assert(i0ips-size);// 容量已满需要先扩容if(ps-sizeps-capacity){// 用 realloc 把容量扩大为原来的 2 倍结果先存入 tmp避免丢失原指针SqDataType*tmp(SqDataType*)realloc(ps-arr,sizeof(SqDataType)*ps-capacity*2);// 扩容失败realloc 返回 NULL原空间仍然有效直接返回if(tmpNULL){printf(SqListInsert:内存申请空间失败!!!\n);return;}// 扩容成功更新数组指针与容量ps-arrtmp;ps-capacity*2;}// 从后往前把 [i, size-1] 的元素依次后移一位腾出下标 i 的位置for(intjps-size-1;ji;j--){ps-arr[j1]ps-arr[j];}// 在腾出的位置写入 x并让有效元素个数加 1ps-arr[i]x;ps-size;}/* * SqListDelete —— 删除下标 i 处的元素 * param ps 指向顺序表 * param i 待删除元素的下标合法范围 [0, size-1] * return 被删除的元素值 * 先保存被删元素再把 [i1, size-1] 的元素整体前移一位覆盖它最后 size 减 1。 * 时间复杂度 O(n)。 */SqDataTypeSqListDelete(SqList*ps,inti){assert(ps);// 下标合法性检查删除时 i 必须落在 [0, size-1] 内assert(i0ips-size);// 先保存被删除的元素用于返回SqDataType xps-arr[i];// 把 i 之后的元素依次前移一位覆盖被删除的元素for(intji1;jps-size;j){ps-arr[j-1]ps-arr[j];}// 有效元素个数减 1ps-size--;returnx;}/* * SqListPrint —— 打印顺序表中的所有元素 * 按下标从 0 到 size-1 的顺序输出元素之间用空格分隔末尾不换行。 */voidSqListPrint(SqList*ps){assert(ps);// 按下标顺序遍历并输出每个元素for(inti0;ips-size;i){printf(%d ,ps-arr[i]);}}/* * SqListPushFront —— 头插在下标 0 处插入元素 x * 相当于 SqListInsert(ps, 0, x)这里单独实现以便观察“元素整体后移”的过程。 * 容量不足时同样按 2 倍扩容。 */voidSqListPushFront(SqList*ps,SqDataType x){assert(ps);// 容量已满按 2 倍策略扩容与 SqListInsert 中的处理一致if(ps-sizeps-capacity){// realloc 扩容失败时保留原空间直接返回SqDataType*tmp(SqDataType*)realloc(ps-arr,sizeof(SqDataType)*ps-capacity*2);if(tmpNULL){printf(SqListInsert:内存申请空间失败!!!\n);return;}ps-arrtmp;ps-capacity*2;}// 把所有元素整体后移一位腾出下标 0 的位置for(intjps-size-1;j0;j--){ps-arr[j1]ps-arr[j];}// 下标 0 放入 x并让有效元素个数加 1ps-arr[0]x;ps-size;}/* * SqListPushBack —— 尾插在顺序表末尾追加元素 x * 相当于 SqListInsert(ps, size, x)不需要移动已有元素时间复杂度 O(1)。 * 容量不足时按 2 倍扩容。 */voidSqListPushBack(SqList*ps,SqDataType x){assert(ps);// 容量已满按 2 倍策略扩容if(ps-sizeps-capacity){SqDataType*tmp(SqDataType*)realloc(ps-arr,sizeof(SqDataType)*ps-capacity*2);if(tmpNULL){printf(SqListInsert:内存申请空间失败!!!\n);return;}ps-arrtmp;ps-capacity*2;}// 下标 size 正好是末尾的空闲位置写入 x 后让 size 加 1ps-arr[ps-size]x;ps-size;}/* * SqListPopFront —— 头删删除下标 0 处的元素 * 把 [1, size-1] 的元素整体前移一位再让 size 减 1时间复杂度 O(n)。 * 本函数不检查顺序表是否为空调用前应保证 size 0。 */voidSqListPopFront(SqList*ps){assert(ps);// 从前往后把后一个元素覆盖到前一个位置for(intj0;jps-size-1;j){ps-arr[j]ps-arr[j1];}// 有效元素个数减 1ps-size--;}/* * SqListPopBack —— 尾删删除顺序表末尾的元素 * 只需把 size 减 1时间复杂度 O(1)被“删除”的空间会在下次插入时被覆盖。 */voidSqListPopBack(SqList*ps){assert(ps);// size 减 1 即视为删除末尾元素底层数组空间不释放ps-size--;}/* * LocateElem —— 查找元素 x 第一次出现的下标 * return 找到时返回对应下标不存在时返回 -1 * 采用顺序查找时间复杂度 O(n)。 */intLocateElem(SqList*ps,SqDataType x){assert(ps);// 从下标 0 开始逐个比较找到第一个相等的元素就返回其下标for(intj0;jps-size;j){if(xps-arr[j])returnj;}// 遍历结束仍未找到返回 -1return-1;}/* * EmptySqList —— 判断顺序表是否为空 * return size 0 时返回 true否则返回 false */boolEmptySqList(SqList*ps){assert(ps);returnps-size0;}/* * SqListSize —— 获取顺序表中有效元素的个数 * return 当前 size 的值 */intSqListSize(SqList*ps){assert(ps);returnps-size;}/* * GetElem —— 获取下标 i 处的元素值 * param i 下标合法范围 [0, size-1] * return 下标 i 处的数据元素 * 时间复杂度 O(1)。 */SqDataTypeGetElem(SqList*ps,inti){assert(ps);// 下标合法性检查越界时 assert 会在调试版中触发assert(i0ips-size);returnps-arr[i];}3.测试(test.c)#define_CRT_SECURE_NO_WARNINGS1#includeSqList.hvoidTestSqList1(){SqList L;SqListInit(L);SqListInsert(L,0,9);SqListInsert(L,1,10);SqListInsert(L,2,20);SqListInsert(L,3,30);SqListInsert(L,4,40);SqListInsert(L,5,50);// 扩容SqListPrint(L);// 头插SqListInsert(L,0,0);SqListPrint(L);// 尾插SqListInsert(L,SqListSize(L),60);SqListPrint(L);// 中间插入SqListInsert(L,2,2);SqListPrint(L);}voidTestSqList2(){SqList L;SqListInit(L);SqListInsert(L,0,9);SqListInsert(L,1,10);SqListInsert(L,2,20);SqListInsert(L,3,30);SqListInsert(L,4,40);SqListInsert(L,5,50);// 扩容SqListPrint(L);// 删除顺序表第1位置上的元素printf(顺序表中有效元素个数为: %d \n,SqListSize(L));// 删除第一个数据printf(删除的元素是:%d \n,SqListDelete(L,0));// 删除末尾的数据printf(删除的元素是:%d \n,SqListDelete(L,SqListSize(L)-1));// 删除中间的数据printf(删除的元素是:%d \n,SqListDelete(L,2));SqListPrint(L);printf(顺序表中第%d个元素是: %d\n,1,GetElem(L,1));printf(40 的下标是%d\n,LocateElem(L,40));SqListDestroy(L);}intmain(){TestSqList1();//TestSqList2();return0;}