1.顺序表的概念
1.顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储，在数组上完成数据的增删查改
2.顺序表一般可以分为静态顺序表（使用定长数组存储元素）和动态顺序表（使用动态开辟的数组存储）
2.静态顺序表的缺点
静态顺序表只适用于确定知道需要存多少数据的场景 , 静态顺序表的定长数组导致空间开多了浪费，开少了不够用的弊端,所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小,下面也会详细讲解动态顺序表的实现,不过掌握了动态顺序表相信静态的对你来说也是小菜一碟的
3.动态顺序表
3.1结构
typedef int SLDataType;//数据类型 typedef struct SeqList { SLDataType* a;//指向动态开辟的数组 int size;//记录储存多少个有效数据 int capacity;//记录空间容量大小 }SL;
图解:
3.2接口实现
3.2.1初始化顺序表
将有效数据个数和容量都初始化为0,并将指针指空
void SLInit(SL* ps) { assert(ps); ps->a = NULL; ps->size = 0; ps->capacity = 0; }
3.2.2打印顺序表
遍历打印数组中的内容
void SLprint(SL* ps) { assert(ps); for (int i = 0; i < ps->size; ++i) { printf("%d ", ps->a[i]); } printf("\n"); }
3.2.3 尾插
在数组尾部插入数据,首先要考虑扩容问题,再插入数据,同时元素个数增加
void SLPushBack(SL* ps, SLDataType x) { assert(ps); if (ps->size == ps->capacity) { int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //初始状态size=capacity=0的情况下先对容量开4个空间，后面就二倍开辟空间 SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newCapacity); //先用一个指针tmp接收,防止扩容失败,成功扩容的话再将地址给到a if (tmp == NULL) { perror("realloc fail"); exit(-1); } else { ps->a = tmp;//如果空间开辟成功,将地址给到a ps->capacity = newCapacity;//容量调整为新的容量大小 } } ps->a[ps->size] = x;//尾部插入数据 ps->size++;//元素个数增加 }
3.2.4尾删
删除数组尾部的数据,同时元素个数减小,要考虑数组为空不能删的情况
void SLPopBack(SL* ps) { assert(ps); //断言数组为空的情况 assert(ps->size > 0); ps->size--; }
3.2.5扩容
由于多个接口需要检查数组容量,我们可以直接将判断扩容这一步骤封装成一个函数
void SLCheckCapacity(SL* ps) { assert(ps); if (ps->size == ps->capacity) { int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //初始状态size=capacity=0的情况下先对容量开4个空间，后面就二倍开辟空间 SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType)); //先用一个指针tmp接收,防止扩容失败,成功扩容的话再将地址给到a if (tmp == NULL) { perror("realloc fail"); exit(-1); } else { ps->a = tmp;//如果空间开辟成功,将地址给到a ps->capacity = newCapacity;//容量调整为新的容量大小 } } }
这样子我们就可以对上面的尾插接口进行简化了:
void SLPushBack(SL* ps, SLDataType x) { assert(ps); SLCheckCapacity(ps); ps->a[ps->size] = x; ps->size++; }
3.2.6头插
在数组尾部插入数据,首先要考虑扩容问题,再将数组的每个元素依次向后移动一位，再在第一个位置插入数据即可,同时元素个数增加
void SLPushFront(SL* ps, SLDataType x) { assert(ps); SLCheckCapacity(ps); //从最后一个数据开始依次向后挪动一位数据进行覆盖 int end = ps->size - 1; while (end >= 0) { ps->a[end + 1] = ps->a[end]; end--; } ps->a[0] = x;//头部插入数据 ps->size++;//元素个数增加 }
3.2.7头删
从第二个数据开始将后面的数据依次向前移动一位进行覆盖即可达到头删的效果
void SLPopFront(SL* ps) { assert(ps); assert(ps->size > 0); int begin = 1; //从第二个数据开始将后面的数据依次向前移动一位进行覆盖 while (begin < ps->size) { ps->a[begin - 1] = ps->a[begin]; begin++; } ps->size--; }
3.2.8任意位置插入数据
首先检查容量，再将目标位置之后的数据依次向后移动一位，再在此位置插入数据
void SLInsert(SL* ps, int pos, SLDataType x) { assert(ps); assert(pos >= 0); assert(pos <= ps->size); SLCheckCapacity(ps);//检查容量 //从最后一个数据到目标位置结束开始依次向后挪动一位数据覆盖 int end = ps->size - 1; while (end >= pos) { ps->a[end + 1] = ps->a[end]; end--; } ps->a[pos] = x; ps->size++; }
3.2.9 任意位置删除数据
将目标位置之后的数据依次向前移动一位进行覆盖即可达到删除效果
void SLErase(SL* ps, int pos) { assert(ps); assert(pos >= 0); assert(pos < ps->size); //将目标位置之后的数据依次向前移动一位进行覆盖 int begin = pos + 1; while (begin < ps->size) { ps->a[begin - 1] = ps->a[begin]; begin++; } ps->size--; }
3.2.10查找数据位置
从该位置向后遍历数组，找到该数据就返回其下标，没找到就返回-1
int SLFind(SL* ps, SLDataType x, int begin) { assert(ps); //从begin开始，找到返回下标，没找到返回-1 for (int i = begin; i < ps->size; ++i) { if (ps->a[i] == x) { return i; } } return -1; }
3.2.11销毁顺序表
释放顺序表的空间,并将指针指空,容量和数据个数置0 (只有在数组不为空的情况下才会销毁)
void SLDestroy(SL* ps) { if (ps->a != NULL) { free(ps->a); ps->a = NULL; ps->size = ps->capacity = 0; } }
4.复用优化
既然我们写了任意位置插入删除的接口,那么我们是否可以将其复用给头插尾插,头删尾删呢?答案是可以的,下面我们就来对代码进行优化
4.1头插尾插优化
头插:
void SLPushFront(SL* ps, SLDataType x) { //在下标为0的位置插入数据(首元素) SLInsert(ps, 0, x); }
尾插:
void SLPushBack(SL* ps,SLDataType x) { //在下标为size的位置插入数据(末尾元素的下一个) SLInsert(ps, ps->size, x); }
4.2头删尾删优化
头删
void SLPopFront(SL* ps) { //删除下标为0的数据(首元素) SLErase(ps, 0); }
尾删
void SLPopBack(SL* ps) { //删除下标为size-1的数据(末尾元素) SLErase(ps, ps->size - 1); }
动态顺序表到这里就介绍结束了，期待大佬们的三连！
文章有写的不足或是错误的地方，欢迎评论或私信指出，我会在第一时间改正
