数据结构-顺序表

一、顺序表及其实现顺序表分为两类一类是静态顺序表另一类则是动态顺序表1、静态顺序表#define N 100 typedef int SLDatatype; typedef struct SeqList { SLDatatype a[N]; //定长数组 int size; //有效数据个数 }SL;静态顺序表底层就是通过一个超大容量的数组来实现这种顺序表优点是使用方便但缺点也很明显实际上我们并不知道开多少的空间能满足各种情况因此会导致空间的浪费同时无法进行二次扩容2、动态顺序表typedef int SLDatatype; typedef struct SeqList { SLDatatype* arr; int size; //有效数据个数 int capacity; //空间容量 }SL;相比较于静态顺序表动态顺序表能针对不同情况进行合理的空间分配一定程度上保证了空间的高效利用因此我们大多数情况下使用的是动态顺序表其特点就是按需申请下面我们就来实现动态顺序表分别创建SeqList.c、SeqList.h、test.c文件用于后续的函数实现与测试首先在头文件函数中定义出动态顺序表的结构#pragma once #include stdio.h #include stdlib.h #include assert.h typedef int SLDatatype; typedef struct SeqList { SLDatatype* arr; int size; //有效数据个数 int capacity; //空间容量 }SL;接着对SL进行初始化初始化传参时一定要传结构体指针要进行传址调用这样函数内部形参的修改才能影响外部实参的改变注意在.h文件中进行声明在.c文件中实现函数1 初始化//初始化 void SLInit(SL* ps) { ps-arr NULL; ps-capacity ps-size 0; }接着我们通过调式来看看初始化是否成功在test文件中进行测试#include SeqList.h void test1() { SL sl; SLInit(sl); } int main() { test1(); return 0; }接下来我们按照顺序依次实现下列函数//尾插 void SLPushBack(SL* ps, SLDatatype x); //头插 void SLPushFront(SL* ps, SLDatatype x); //尾删 void SLPopBack(SL* ps); //头删 void SLPopFront(SL* ps);2 尾插//尾插 void SLPushBack(SL* ps, SLDatatype x) { assert(ps); //首先判断空间够不够不够要动态申请空间 if (ps-size ps-capacity) { //进行扩容 SLDatatype* tmp (SLDatatype*)realloc(ps-arr,2 * ps-capacity * sizeof(SLDatatype)); if (tmp NULL) { perror(realloc failed!\n); exit(1); } //扩容成功 ps-arr tmp; ps-capacity 2 * ps-capacity * sizeof(SLDatatype); } ps-arr[ps-size] x; }在完成尾插之后为了便于测试我们写一个打印函数void SLPrint(SL* ps);3 打印//打印 void SLPrint(SL* ps) { for (int i 0; i ps-size; i) { printf(%d , ps-arr[i]); } printf(\n); }我们在test.c文件中测试一下4 头插在实现头插时我们会发现还是需要判断空间够不够此时我们将判断空间够不够这段代码封装成一个函数void SLCheckCapacity(SL* ps)同时我们将利用三目操作符在首次判断空间时直接给4个大小的空间防止我们后续2倍扩容时存在初始值为0扩容失败的情况第一步先封装void SLCheckCapacity(SL* ps)//自动扩容 void SLCheckCapacity(SL* ps) { if (ps-size ps-capacity) { int Newcapacity ps-size 0 ? 4 : 2 * ps-capacity; SLDatatype* tmp (SLDatatype*)realloc(ps-arr, Newcapacity * sizeof(SLDatatype)); if (tmp NULL) { perror(realloc failed!\n); exit(1); } //扩容成功 ps-arr tmp; ps-capacity Newcapacity; } }封装之后的SLCheckCapacity在进行插入操作时可以直接进行调用并自动判断是否需要扩容调用完成之后ps-arr就是合理的指针此时我们将对尾插进行一次优化//尾插 void SLPushBack(SL* ps, SLDatatype x) { assert(ps); SLCheckCapacity(ps); ps-arr[ps-size] x; }第二步实现头插头插的逻辑就是将所有元素向后移动一位然后将x放入第一个位置即可注意移动要从最后一位开始移动避免已有元素被覆盖掉//头插 void SLPushFront(SL* ps, SLDatatype x) { assert(ps); SLCheckCapacity(ps); //将所有元素向后移动一位 for (int i ps-size - 1; i 0; i--) { ps-arr[i 1] ps-arr[i]; } ps-arr[0] x; ps-size; }来测试一下继续向后走5 尾删尾删要注意两个断言一是ps不能为空二是有效元素个数不为0尾删逻辑就是直接让size--索引值-1//尾删 void SLPopBack(SL* ps) { assert(ps); assert(ps-size 0); ps-size--; }来测一下在当前基础上再删一次看是否会引发断言6 头删头删逻辑是从第二个元素开始将所有元素均向前挪动一位//头删 void SLPopFront(SL* ps) { assert(ps); assert(ps-size 0); //从第二个元素开始均向前挪动一位 for (int i 0; i ps-size - 1; i) { ps-arr[i] ps-arr[i 1]; } ps-size--; }来测一下再删一次看能否引发断言没有问题7 在指定位置之前插入函数逻辑是将pos及其之后的元素全部向后移动一位然后将x放入pos位置//任意位置之前插入 void SLInsert(SL* ps, int pos, SLDataType x) { assert(ps); SLCheckCapacity(ps); assert(pos 0 pos ps-size); for (int i ps-size - 1; i pos;i--) { ps-arr[i 1] ps-arr[i]; } ps-arr[pos] x; ps-size; }来测一下8 删除任意位置函数逻辑是将pos 1及其后面元素向前挪动一位即可//删除任意位置 void SLErase(SL* ps,int pos) { assert(ps); assert(ps-arr); assert(pos 0 pos ps-size - 1); //将pos 1及其后面元素向前挪动一位 for (int i pos 1; i ps-size - 1; i) { ps-arr[i] ps-arr[i 1]; } ps-size--; }来测一下此时若再删一次1位置会触发断言9 查找任意位置函数逻辑是通过遍历整个顺序表看是否有对应的x,有就返回对应的下标若遍历结束还未找到则返回-1//查找任意位置 int SLFind(SL* ps, SLDatatype x) { assert(ps-size); for (int i 0; i ps-size - 1; i) { if (ps-arr[i] x) return i; } return -1; }来测一下最后来实现销毁函数同样是在.c文件中进行实现10 销毁//销毁 void SLDestroy(SL* ps) { if(ps-arr) free(ps-arr); ps-arr NULL; ps-size ps-capacity 0; }我们依旧调式来看销毁是否成功没有问题到此为止顺序表的基本核心功能均已实现后续将会实现基于顺序表的通讯录项目二、对顺序表的反思1.顺序表中使用过多的循环操作是否会导致时间开销是否过大2.顺序表中对空间的利用是否足够高效3.频繁realloc会怎样如有不足之处欢迎指出......