C语言数据结构深入探索顺序表 C语言数据结构深入探索顺序表

1.顺序表的概念及结构
2.增删查改的实现

2.1扩容
2.2插入数据

2.2.1尾插
2.2.2头插
2.2.3任意位置插入

2.3删除数据

2.3.1尾删
2.3.2头删
2.3.3任意位置删除

2.4查找

2.5修改数据

2.6销毁空间

1.顺序表的概念及结构顺序表是使用一段连续物理地址的单元来依次储存数据的线性结构，一般采用数组存储。在数组上完成增删查改。

文章图片

顺序表分为两类：
静态顺序表：使用定长数组储存元素

struct SeqList{int data; //存储的数据int size; //记录数据个数int 1000; //给定当前顺序表的总容量为1000};

【C语言数据结构深入探索顺序表】动态顺序表：使用动态开辟的数组存储

struct SeqList{int data; //存储的数据int size; //记录数据个数int capacity; //顺序表的总容量};

2.增删查改的实现当我们需要储存的数据数目不确定时我们使用动态顺序表更佳，所以下面就用动态顺序表来实现增删查改。

2.1扩容
首先我们动态顺序表想要实现自动扩容，当当前数据量size等于总容量capacity时我们就需要自动增容，具体就是使用malloc函数开辟一定数量的空间，假如我们设定每次扩充二倍，代码如下：

//增容void SLCheckcapacity(SL* pc){ assert(pc != NULL); //检查容量，满了就扩容 if (pc->sz == pc->capacity) {//一次扩容二倍，如果初始为0就先扩容到4int newcapacity = pc->capacity == 0 ? 4 : pc->capacity * 2; //注意类型转换SLDatatype* tmp = (SLDatatype*)realloc(pc->data, sizeof(SLDatatype) * newcapacity); if (tmp == NULL){perror("SLCheckcapacity::realloc"); exit(-1); }//讲开辟的空间tmp给到数组pc->data = https://www.it610.com/article/tmp; pc->capacity = newcapacity; }}

2.2插入数据
插入数据时我们有三种情况，头插尾插和中间任意位置插。

2.2.1尾插先从最简单的尾插开始，我们尾插时需要记录下当前的size，这样插入的时候就可以直接找到尾部，我们需要注意的是，我们插入之前需要判断一下当前的容量满了没有，如果满了就需要扩容，没满就可以直接插入。

//尾插void SLPushBack(SL* pc, SLDatatype x){ assert(pc != NULL); //需要判断是否需要增容 SLCheckcapacity(pc); pc->data[pc->sz] = x; pc->sz++; }

2.2.2头插头插相对来说要复杂一点，当头上没有数据时，我们就可以看成尾插直接插入，当头上有数据时，我们为了避免数据的覆盖，需要将所有数据向后移动，再放入在头部，在我们向后移动数据时我们也需要判断是否满容了。

//头插void SLPushFront(SL* pc, SLDatatype x){ assert(pc != NULL); SLCheckcapacity(pc); //挪动数据 int end = pc->sz - 1; while (end >= 0) {pc->data[end + 1] = pc->data[end]; --end; } //插入数据 pc->data[0] = x; pc->sz++; }

2.2.3任意位置插入我们任意位置插入时有三种情况，当在第一个位置时就是头插可以调用头插的函数，在最后一个位置时就是尾插，就调用尾插的函数，当我们在中间的时我们需要找到需要插入的位置，然后将数据从这个位置开始向后挪动，再插入进去。

//任意位置插入void SLInsert(SL* pc, int pos, SLDatatype x){ assert(pc); //判断pos是否在有效数据范围内 assert(pos >= 0 && pos <= pc->sz); SLCheckcapacity(pc); //挪动数据 int end = pc->sz - 1; while (end >= pos) {pc->data[end+1] = pc->data[end]; --end; } pc->data[pos] = x; pc->sz++; }

2.3删除数据
删除数据和上面的插入数据差不多，我们也需要凑够三个方面来撕开，头部删除，尾部删除，中间任意位置删除，当我们删除数据时我们只需要将这个数据后的数据依次向前挪动，覆盖住这个数据即可。这里我们不能用free函数去释放那块地址的空间来删除，因为顺序表的物理地址是连续的。链表可以，下一章会介绍。

2.3.1尾删尾部后面没有数据那么就把最后一个数据制成0就好了

//尾删void SLPopBack(SL* pc){ assert(pc != NULL); //不能删多了 assert(pc->sz > 0); pc->sz--; }

2.3.2头删将从第二个位置开始的数据往前挪动，这里需要注意，删除需要检查，以免越界。

//删除需要检查，删多了会越界//头删void SLPopFront(SL* pc){ assert(pc != NULL); //检查 assert(pc->sz > 0); //从第二个元素开始从后往前挪直接将其覆盖 int begin = 0; while (begin <= pc->sz) {pc->data[begin-1] = pc->data[begin]; ++begin; } pc->sz--; }

2.3.3任意位置删除任意位置删除我们只需要将我们需要删除的位置后面的数往前挪动就行了

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

2.4查找
我们给一个数据x来表示我们想要查找的数据，从前往后把顺序表遍历一遍，当给的X等于顺序表中的X时就找到了，返回当前位置的下标。

//查找int SLFind(SL* pc, SLDatatype x){ assert(pc != NULL); for (int i = 0; i < pc->sz; ++i) {if (pc->data[i] == x){return i; } } printf("找不到\n"); return; }

2.5修改数据
当我们想要修改某一个地方的数据时，直接将那个位置的数据输入新的数据覆盖掉就行了。

//改数据void SlModify(SL* pc, int pos, SLDatatype x){ assert(pc != NULL); if (pos >= 0 && pos <= pc->sz) {pc->data[pos] = x; } else {printf("超出范围了\n"); }}

2.6销毁空间
当我们顺序表使用完成过后，我们需要注意的是，我们malloc的空间并没有得到释放，可能会造成内存泄漏等问题（可参考前面的博客 '动态内存开辟' ），释放内存就需要用到free函数