数据结构.2.2动态顺序表（完整代码）

1.结构体与接口(SqList.h)

#pragmaonce// SqList.h 一般这些接口函数声明放到.h中// 下面的接口函数的实现放到SqList.cpp中#include<stdio.h>#include<stdlib.h>#include<stdbool.h>#include<assert.h>structSnakeData{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.h：SqList 结构体由 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// 初始化顺序表#include"SqList.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->arr==NULL){//申请失败，则退出printf("InitSqList: 内申请空间失败 !!!\n");//exit(-1);return;}// 记录有效元素个数与当前容量ps->size=0;ps->capacity=4;}/* * SqListDestroy —— 销毁顺序表 * 释放动态数组占用的堆空间，并把 arr 置为 NULL、size 与 capacity 清零， * 避免留下悬空指针；重复调用本函数也是安全的。 */voidSqListDestroy(SqList*ps){assert(ps);// arr 非空说明空间申请成功过，需要释放if(ps->arr){free(ps->arr);// 释放后复位成员，避免后续误用已释放的内存ps->size=0;ps->capacity=0;ps->arr=NULL;}}/* * 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(i>=0&&i<=ps->size);// 容量已满，需要先扩容if(ps->size==ps->capacity){// 用 realloc 把容量扩大为原来的 2 倍，结果先存入 tmp，避免丢失原指针SqDataType*tmp=(SqDataType*)realloc(ps->arr,sizeof(SqDataType)*ps->capacity*2);// 扩容失败：realloc 返回 NULL，原空间仍然有效，直接返回if(tmp==NULL){printf("SqListInsert:内存申请空间失败!!!\n");return;}// 扩容成功：更新数组指针与容量ps->arr=tmp;ps->capacity*=2;}// 从后往前把 [i, size-1] 的元素依次后移一位，腾出下标 i 的位置for(intj=ps->size-1;j>=i;j--){ps->arr[j+1]=ps->arr[j];}// 在腾出的位置写入 x，并让有效元素个数加 1ps->arr[i]=x;ps->size++;}/* * SqListDelete —— 删除下标 i 处的元素 * @param ps 指向顺序表 * @param i 待删除元素的下标，合法范围 [0, size-1] * @return 被删除的元素值 * 先保存被删元素，再把 [i+1, size-1] 的元素整体前移一位覆盖它，最后 size 减 1。 * 时间复杂度 O(n)。 */SqDataTypeSqListDelete(SqList*ps,inti){assert(ps);// 下标合法性检查：删除时 i 必须落在 [0, size-1] 内assert(i>=0&&i<ps->size);// 先保存被删除的元素，用于返回SqDataType x=ps->arr[i];// 把 i 之后的元素依次前移一位，覆盖被删除的元素for(intj=i+1;j<ps->size;j++){ps->arr[j-1]=ps->arr[j];}// 有效元素个数减 1ps->size--;returnx;}/* * SqListPrint —— 打印顺序表中的所有元素 * 按下标从 0 到 size-1 的顺序输出，元素之间用空格分隔（末尾不换行）。 */voidSqListPrint(SqList*ps){assert(ps);// 按下标顺序遍历并输出每个元素for(inti=0;i<ps->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->size==ps->capacity){// realloc 扩容，失败时保留原空间直接返回SqDataType*tmp=(SqDataType*)realloc(ps->arr,sizeof(SqDataType)*ps->capacity*2);if(tmp==NULL){printf("SqListInsert:内存申请空间失败!!!\n");return;}ps->arr=tmp;ps->capacity*=2;}// 把所有元素整体后移一位，腾出下标 0 的位置for(intj=ps->size-1;j>=0;j--){ps->arr[j+1]=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->size==ps->capacity){SqDataType*tmp=(SqDataType*)realloc(ps->arr,sizeof(SqDataType)*ps->capacity*2);if(tmp==NULL){printf("SqListInsert:内存申请空间失败!!!\n");return;}ps->arr=tmp;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(intj=0;j<ps->size-1;j++){ps->arr[j]=ps->arr[j+1];}// 有效元素个数减 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(intj=0;j<ps->size;j++){if(x==ps->arr[j])returnj;}// 遍历结束仍未找到，返回 -1return-1;}/* * EmptySqList —— 判断顺序表是否为空 * @return size == 0 时返回 true，否则返回 false */boolEmptySqList(SqList*ps){assert(ps);returnps->size==0;}/* * 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(i>=0&&i<ps->size);returnps->arr[i];}

3.测试(test.c)

#define_CRT_SECURE_NO_WARNINGS1#include"SqList.h"voidTestSqList1(){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;}