顺序表——重置版

本期我们来实现数据结构的顺序表（这个之前写过一次，不过本期和之前可能会略有不同，但大体相同），大家可以看一下我们之前完成的顺序表

(6条消息) 顺序表及其多种接口的实现_顺序表类中实现接口方法_KLZUQ的博客-CSDN博客

目录

顺序表的结构

顺序表的初始化

顺序表的销毁

尾插

尾删

打印顺序表的元素

扩容

头插

头删

任意位置插入

任意位置删除

查找

realloc相关知识

完整代码

---

我们继续用工程化的写法来保证好的代码习惯

顺序表的结构

我们仍然是先写出顺序表的结构

typedef int SLDataType;
#define INIT_CAPACITY 10 //初始容量
typedef struct SeqList {SLDataType* a;int size;//有效数据个数 int capacity;//空间容量
}SL;

 因为顺序表大小的原因，开多了浪费，开少了不够用，所以我们需要定义一些变量来帮助我们对顺序表的大小进行调整

顺序表的初始化

void SLInit(SL* ps) {//初始化assert(ps);ps->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);if (ps->a == NULL) {perror("malloc fail");return;}ps->size = 0;ps->capacity = INIT_CAPACITY;
}

初始化参数我们需要传顺序表这个结构体的指针，然后使用malloc开辟空间给顺序表，这个空间就是我们用来存储数据的，同时我们要判断是否开辟成功，失败时我们用perror来返回错误信息即可，开辟成功后，我们将有效数据个数置0，容量置为我们设置的初始容量

第一行的断言是因为我们传入的是顺序表这个结构体的指针，是不可能为空的，所以需要断言，而顺序表里的内容是否为空是由size来进行决定的

顺序表的销毁

void SLDestory(SL* ps) {//销毁assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->size = 0;
}

顺序表的销毁我们free的是ps->a，而不是直接free掉ps，然后我们将ps置为空即可

尾插

void SLPushBack(SL* ps, SLDataType x)//尾插
{assert(ps);if (ps->size == ps->capacity) {//扩容SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2*sizeof(SLDataType));if (tmp == NULL) {perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2;}ps->a[ps->size++] = x;
}

尾插前我们需要对容量进行判断，如果不够就需要先扩容，我们这里扩容扩二倍，接着把数据放入数组里即可（我们的size是从0开始的，也就是说size的位置是我们当前存放数据最后一个的下一个位置）

尾删

void SLPopBack(SL* ps)//尾删
{assert(ps);//严格的判断//assert(ps->size>0);//温柔的判断if (ps->size == 0) {return;}ps->size--;
}

因为是顺序表，我们使用size来控制当前数据个数，所以直接size-1即可，我们不需要将这里的数据置为0，因为没有必要，而且我们也不能释放空间，因为这是数组，是连续的空间，当然在删除数据前，我们要先判断数组是否为空，这里我们有两种方法，一种是用assert直接断言，另一种是当作无事发生（更推荐assert一些）

打印顺序表的元素

有了尾插尾删，我们需要对程序进行测试，所以我们对顺序表的元素进行打印

void SLPrint(SL* ps) {//打印assert(ps);for (int i = 0; i < ps->size; i++) {printf("%d->", ps->a[i]);}printf("NULL\n");
}

扩容

我们在写头插时，发现插入都需要先判断是否需要扩容，所以我们把扩容代码提取出来封装为一个函数方便后续使用

void SLCheckCapaicty(SL* ps)//扩容
{assert(ps);if (ps->size == ps->capacity) {//扩容SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(SLDataType));if (tmp == NULL) {perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2;}
}

头插

void SLPushFront(SL* ps, SLDataType x)//头插
{assert(ps);SLCheckCapaicty(ps);int end = ps->size - 1;while (end>=0) {ps->a[end + 1] = ps->a[end];--end;}ps->a[0] = x;ps->size++;
}

头插的效率不高，需要挪动后续所有元素，如果有n个元素，我们要插入n个元素，时间复杂度就是n^2了，而尾插n个数据的数据复杂度是n，这是非常恐怖的，比如我们要插入1w个数据，那么头插就是1w*1w了，而尾插是1w，所以我们要避免使用头插

头删

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--;
}

如果size为0，那么顺序表为空，不能进行删除，删除时我们只需将a[0]之后的元素向前挪动即可，接着size-1，同样的，头删的效率也很低，时间复杂度也是n^2，所以我们也要少用头删

任意位置插入

void SLInsert(SL* ps, int pos, SLDataType x)//任意位置插入
{assert(ps);assert(pos>=0 && pos<=ps->size);SLCheckCapaicty(ps);int end = ps->size - 1;while (end>=pos) {ps->a[end + 1] = ps->a[end];--end;}ps->a[pos] = x;ps->size++;
}

如果我们想在顺序表中间某个位置插入，就可以使用该函数，因为是插入，所以也需要先判断是否需要扩容，另外，我们传入的pos是位置，所以要符合顺序表元素的个数，所以要断言一下，下面的插入代码和头插几乎一样

任意位置删除

void SLErase(SL* ps, int pos)//任意位置删除
{assert(ps);assert(pos >= 0 && pos < ps->size);int begin = pos + 1;while (begin < ps->size) {ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;
}

这里的断言和任意位置插入稍有不同，我们发现pos<ps->szie，而不能等于，而且我们不需要检查size是否大于0，因为pos会间接检查，因为size不可能为负数，而pos要大于等于0

查找

int SLFind(SL* ps, SLDataType x)//查找
{assert(ps);for (int i = 0; i < ps->size; i++) {if (ps->a[i] == x) {return i;}}return -1;
}

任意位置的插入和删除，一般是配合查找来使用的，查找返回的是下标，找不到时返回-1

realloc相关知识

最后我们在补充一点其他的只是，我们的顺序表扩容时使用了realloc函数，而realloc函数分配空间扩容会分为两种，一种是原地扩容，另一种是异地扩容，原地扩容就是将当前位置的后续空间使用权也分配给我们，而异地扩容则是新找了一块空间将使用权分配给我们，然后把原来的空间使用权归还给操作系统，当我们扩容小的时候，一般是原地扩容，但是当扩容次数较多时，后续空间会不足，就会进行异地扩容，找一块更大的空间给我们，异地扩容的效率是比原地扩容低很多的，异地扩容不仅要找一块新的空间，还要把原空间里的数据给拷贝过来，再释放原空间

完整代码

最后，在这里附上全部代码

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLDataType;
#define INIT_CAPACITY 10 //初始容量
typedef struct SeqList {SLDataType* a;int size;//有效数据个数 int capacity;//空间容量
}SL;void SLInit(SL* ps);//初始化
void SLDestory(SL* ps);//销毁
void SLPrint(SL* ps);//打印
void SLPushBack(SL* ps,SLDataType x);//尾插
void SLPushFront(SL* ps, SLDataType x);//头插
void SLPopBack(SL* ps);//尾删
void SLPopFront(SL* ps);//头删
void SLCheckCapaicty(SL* ps);//扩容
void SLInsert(SL* ps, int pos, SLDataType x);//任意位置插入
void SLErase(SL* ps, int pos);//任意位置删除
int SLFind(SL* ps, SLDataType x);//查找

 

#include "SeqList.h"void SLInit(SL* ps) {//初始化assert(ps);ps->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);if (ps->a == NULL) {perror("malloc fail");return;}ps->size = 0;ps->capacity = INIT_CAPACITY;
}void SLCheckCapaicty(SL* ps)//扩容
{assert(ps);if (ps->size == ps->capacity) {//扩容SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(SLDataType));if (tmp == NULL) {perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2;}
}void SLPrint(SL* ps) {//打印assert(ps);for (int i = 0; i < ps->size; i++) {printf("%d->", ps->a[i]);}printf("NULL\n");
}void SLDestory(SL* ps) {//销毁assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->size = 0;
}void SLPushBack(SL* ps, SLDataType x)//尾插
{assert(ps);SLCheckCapaicty(ps);ps->a[ps->size++] = x;
}
void SLPushFront(SL* ps, SLDataType x)//头插
{assert(ps);SLCheckCapaicty(ps);int end = ps->size - 1;while (end>=0) {ps->a[end + 1] = ps->a[end];--end;}ps->a[0] = x;ps->size++;
}
void SLPopBack(SL* ps)//尾删
{assert(ps);//严格的判断assert(ps->size>0);//温柔的判断/*if (ps->size == 0) {return;}*/ps->size--;
}
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--;
}int SLFind(SL* ps, SLDataType x)//查找
{assert(ps);for (int i = 0; i < ps->size; i++) {if (ps->a[i] == x) {return i;}}return -1;
}void SLInsert(SL* ps, int pos, SLDataType x)//任意位置插入
{assert(ps);assert(pos>=0 && pos<=ps->size);SLCheckCapaicty(ps);int end = ps->size - 1;while (end>=pos) {ps->a[end + 1] = ps->a[end];--end;}ps->a[pos] = x;ps->size++;
}
void SLErase(SL* ps, int pos)//任意位置删除
{assert(ps);assert(pos >= 0 && pos < ps->size);int begin = pos + 1;while (begin < ps->size) {ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;
}

以上就是本期全部内容，希望大家可以有所收获

如有错误，还请指正