如何实现顺序表的增删查改功能？

本文共计4745个文字，预计阅读时间需要19分钟。

什么是顺序表？我们要知道什么是顺序表，首先我们要知道什么是线性表。线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表（linear list）（linear+list）是n个具有相同特性的数据元素的有限序列。线性表是一种在现实中广泛使用的、具有n个具有相同特性的数据元素的有限序列的数据结构。

什么是顺序表

我们要知道什么是顺序表首先我们就要知道什么是线性表，

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使

用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。常见的线性表：顺序表、链表、栈、队列、字符串..。

然后我们来讲解什么是顺序表？

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存

储。在数组上完成数据的增删查改。 顺序表一般可以分为：

静态的顺序表和动态的顺序表

静态顺序表

静态顺序表：使用定长数组存储元素。

图像表示：

对于这种顺序表有几个不好的点：

1.我们存储数据的空间是固定的，以上图为例子我们如果想要储存八个数据呢？那这个顺序表很显然是无法满足条件的。

2.为了能够储存足够的数据，也许有的人就会一开始就给定长数组给一个很大的空间，例如给与数组100的空间，但是这样又可能会造成大量空间的浪费，或是若要储存101个数据，这样的顺序表也无法满足条件。

在此基础上也就出现了动态顺序表：

动态顺序表

动态顺序表：使用动态开辟的数组储存数据

图像表示

这样的动态顺序表也就解决了空间不足的问题。

我们接下来也以完成一个动态顺序表作为讲解重点。

要完成的功能（动态顺序表）

我们要完成的功能有，增删查改，当然这只是一个总括

增：实现顺序表的头插，尾插，中间任何位插入

删：头删，尾删，中间任何位删除

查：查找数据

改：修改任意位的数据

我们先创建一个头文件来创建我们的顺序表。

#include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int SLlistdata;//便于我们修改要储存数据的类型 typedef struct SLlist { SLlistdata* arr;//用以创建空间 int size;//判断有效数据的个数 int capacity;//容量，判断是否需要扩容 }SL; void SeqListInit(SL* psl); // 检查空间，如果满了，进行增容 void CheckCapacity(SL* psl); // 顺序表尾插 void SeqListPushBack(SL* psl, SLlistdata x); // 顺序表尾删 void SeqListPopBack(SL* psl); // 顺序表头插 void SeqListPushFront(SL* psl, SLlistdata x); // 顺序表头删 void SeqListPopFront(SL* psl); // 顺序表查找 int SeqListFind(SL* psl, SLlistdata x); // 顺序表在pos位置插入x void SeqListInsert(SLlistdata* psl, int pos, SLlistdata x); // 顺序表删除pos位置的值 void SeqListErase(SL* psl, int pos); // 顺序表销毁 void SeqListDestory(SL* psl); // 顺序表打印 void SeqListPrint(SL* psl);

接口1：尾插打印和初始化功能

下面我们来实现初始化功能：

void InitList(SL* psl) { psl->size = 0; psl->capacity = 4; psl->arr = (SLlistdata*)malloc(sizeof(SLlistdata) * 4); } //我这里初始化给了顺序表默认的四个空间的存量

初始化完成接下来我们肯定是要尾插数据到这个顺序表里面

尾插数据很简单因为我们有一个变量size，代表的是有效数据个数，而顺序表的空间是连续的，我们可以运用访问数组的方式去完成尾插，因为数组下表为从零开始的所有size恰好就成为了最后一个下标，那么如果出现空间的情况呢？所以我们对于要插入数据时都要先检查空间是否足够。

检查空间代码：

void CheckCapacity(SL* psl) { if (psl->size == psl->capacity) { psl->capacity += 4; psl->arr = (SLlistdata*)realloc(psl->arr,sizeof(SLlistdata)*(psl->capacity)); if (psl->arr == NULL) { perror("realloc fail:"); return; } }//如果有效数据个数等于容量代表已经满员需要扩容 }

现在空间也已足够，我们便可以进行尾插了。

代码实现：

void SeqListPushBack(SL* psl, SLlistdata x)//尾插数据 { //我们要实现尾插肯定是要先检测顺序表的空间是否足够 CheckCapacity(psl);//调用函数判断是否需要扩容 psl->arr[psl->size] = x; psl->size++;//这只是尾插的实现方法一，后面还有另外的方式 }//下面我们来检验一下这两个函数是否有错误

我们这里再次创建一个test.c的文件，

#include"SLlist.h" void test1() { SL t1;//创建一个顺序表 InitList(&t1);//初始化 SeqListPushBack(&t1, 6); SeqListPushBack(&t1, 5); SeqListPushBack(&t1, 4); SeqListPushBack(&t1, 3); SeqListPushBack(&t1, 2); SeqListPrint(&t1); }//检验头插功能和检测容量功能是否正常 int main() { test1(); return 0; }

运行结果如图下：证明功能并没有出现错误。

当然这只是尾插的一种实现方法，待到后面我会介绍第二种方法

头插功能

想象一下一片连续的空房间，现在都已经住了人了，为了让一个新来的人能够住进第一个房间并且不改变原来人员居住的顺序，我们肯定是要将已经住进去的人全部向后移动一位，然后让新来的人住进第一个房间。

图像表示：

代码实现：

void SeqListPushFront(SL* psl,SLlistdata x) { CheckCapacity(psl); //容量足够之后我们开始插入 //从后往前开始移动数据 for (int i = psl->size - 1; i >= 0; i--) { psl->arr[i + 1] = psl->arr[i]; } psl->arr[0] = x; psl->size++;//完成头插 }//我们再次去检测一下函数的实现

主函数里面的测试用例：

void test2() { SL t1; InitList(&t1); SeqListPushFront(&t1, 6); SeqListPushFront(&t1, 5); SeqListPushFront(&t1, 4); SeqListPushFront(&t1, 3); SeqListPushFront(&t1, 2); SeqListPushFront(&t1, 1); SeqListPrint(&t1); }

下面的运行图像证明头插功能正常，但是这只是其中一种实现方法。

头删和尾删功能

我们想象一下一个数据如何才能被删除呢？

很明显用不用删除的数据将其覆盖就可以了。

头删：

还是用旅馆的例子。

假设这里有1 2 3 4 5 四个编号的房间，其中1 2 3 4已经有人住了，现在我们需要将1房间里的数据将其删除，只要将2 3 4 里面的人都向前移动一个房间就可以。

图像表示：

代码实现：

void SeqListPopFront(SL* psl)//头删从前往后移动数据，若是从后往前会造成数据复制 { //我们就要删除这一个数据自然就不需要检测空间是否足够了 assert(psl);//防止传入空指针 assert(psl->size > 0);//防止一直删除，这是一种暴力解决的方法，如果一直删除在有效数据个数size为0之后就会报错。 for (int i = 0; i < psl->size; i++) { psl->arr[i] = psl->arr[i + 1]; } psl->size--;//删除一个数据之后让size减一 }//运用test3去检测功能

主函数检测：

void test3() { SL t1; InitList(&t1); SeqListPushFront(&t1, 6); SeqListPushFront(&t1, 5); SeqListPushFront(&t1, 4); SeqListPushFront(&t1, 3); SeqListPushFront(&t1, 2); SeqListPushFront(&t1, 1); SeqListPrint(&t1); SeqListPopFront(&t1); SeqListPopFront(&t1); SeqListPopFront(&t1); SeqListPrint(&t1);//这里只删除了三个数据 //若放开后面的就会强制报错 //SeqListPopFront(&t1); //SeqListPopFront(&t1); //SeqListPopFront(&t1); //SeqListPopFront(&t1);//这里多删除了一个数据 }

没有放开后面的删除

放开后面的删除

下面为尾部删除：

尾删和头删有点不同

即只需要将size--就可以了

代码实现：

void SeqListPopBack(SL* psl) { psl->size--; }//运用test4去检测功能

test 4

void test4() { SL t1; InitList(&t1); SeqListPushFront(&t1, 6); SeqListPushFront(&t1, 5); SeqListPushFront(&t1, 4); SeqListPushFront(&t1, 3); SeqListPushFront(&t1, 2); SeqListPushFront(&t1, 1); SeqListPrint(&t1); SeqListPopBack(&t1); SeqListPopBack(&t1); SeqListPopBack(&t1); SeqListPrint(&t1);//这里只删除了三个数据 }

实现中间任意位置插入数据

那么我们要怎么样去实现这个功能呢？

运用图像表示：

代码实现：

void SeqListInsert(SL* psl, int pos, SLlistdata x) { assert(psl);//防止传入空指针 assert(pos >= 0 && pos <= psl->size);//防止在可控空间以外的位置插入 CheckCapacity(psl);//先检测容量 for (int i = psl->size-1; i >= pos; i--) { psl->arr[i+1] = psl->arr[i]; } psl->arr[pos] = x;//这样就完成了， psl->size++; }//运用test5去检测功能

tsst5：

void test5() { SL t1; InitList(&t1); SeqListPushFront(&t1, 6); SeqListPushFront(&t1, 5); SeqListPushFront(&t1, 4); SeqListPushFront(&t1, 3); SeqListPushFront(&t1, 2); SeqListPushFront(&t1, 1); SeqListPrint(&t1); SeqListInsert(&t1, 0, 10); SeqListPrint(&t1); }

实现中间任意位置删除数据

思路依旧为覆盖

即将从pos的位置往后的数据整体前移一位即可：

代码实现：

void SeqListErase(SL* psl, int pos) { assert(psl->size > 0);//依旧是防止过量删除 assert(psl);//防止传入空指针 assert(pos >= 0 && pos < psl->size);//这里不能等于size因为角标为size的空间不受我们控制。 for (int i = pos; i < psl->size; i++) { psl->arr[i] = psl->arr[i + 1]; } psl->size--; }//test6检测

void test6() { SL t1; InitList(&t1); SeqListPushFront(&t1, 6); SeqListPushFront(&t1, 5); SeqListPushFront(&t1, 4); SeqListPushFront(&t1, 3); SeqListPushFront(&t1, 2); SeqListPushFront(&t1, 1); SeqListPrint(&t1); SeqListErase(&t1, 1); SeqListPrint(&t1); }

实现修改特定位的数据和查找特定的数据

修改特定位的数据功能非常容易实现，因为我们可以使用数组的方式去访问顺序表。

代码实现

void SeqModify(SL* psl, int pos, SLlistdata x) { assert(psl);//防止传入空指针 assert(pos >= 0 && pos < psl->size);//防止越界访问 psl->arr[pos] = x; }//test7检测功能是否实现

对于查找功能我们这里规定若找到就返回角标，若没有找到就返回-1。

思路就是遍历查找

代码实现

int SeqListFind(SL* psl, SLlistdata x) { assert(psl); for (int i = 0; i < psl->size; i++) { if (psl->arr[i] == x) { return i; } } return -1; }

对于这个功能的检测我们可以带入到一个情景里面，假设这里有一个顺序表里面储存的是1 2 3 4 5 6

你并不知道其中是否存在6，然后要你删除6，那么我们就可以先利用查找函数找到6的下标，然后运用特定位置删除函数删除6，若本身便不含6那么就会assert强制停止。

代码实现：

void test8() { SL t1; InitList(&t1); SeqListPushFront(&t1, 6); SeqListPushFront(&t1, 5); SeqListPushFront(&t1, 4); SeqListPushFront(&t1, 3); SeqListPushFront(&t1, 2); SeqListPushFront(&t1, 1); SeqListPrint(&t1); int ret =SeqListFind(&t1, 6);//查找6的下标 SeqListErase(&t1, ret);//完成删除 SeqListPrint(&t1); }

完成头删尾删和头插尾插的优化

我们想象一下如果将实现中间任意位置插入数据里面的任意数，改成0和size是不是就完成了头插和尾插的优化

同理对于头删和尾删也是一样的，只用修改实现中间任意位置删除数据，里面的位置改成0和size-1就可以达到头删和尾删的功能。

代码：

SeqListInsert(psl, psl->size, x);//尾插 SeqListInsert(psl, 0, x);//头插 SeqListErase(psl, 0);//头删 SeqListErase(psl, psl->size-1);//尾删

顺序表销毁功能

对于我们创建的空间在创建完毕之后我们肯定是要将其free掉的

代码实现

void SeqListDestory(SL* psl) { free(psl->arr); psl->arr = NULL; psl->size = 0; psl->capacity = 0; }

完整test.c里面的代码（运行逻辑）

#include"SLlist.h" void test1() { SL t1;//创建一个顺序表 InitList(&t1);//初始化 SeqListPushBack(&t1, 6); SeqListPushBack(&t1, 5); SeqListPushBack(&t1, 4); SeqListPushBack(&t1, 3); SeqListPushBack(&t1, 2); SeqListPrint(&t1); }//检验头插功能和检测容量功能是否正常 void test2() { SL t1; InitList(&t1); SeqListPushFront(&t1, 6); SeqListPushFront(&t1, 5); SeqListPushFront(&t1, 4); SeqListPushFront(&t1, 3); SeqListPushFront(&t1, 2); SeqListPushFront(&t1, 1); SeqListPrint(&t1); } void test3() { SL t1; InitList(&t1); SeqListPushFront(&t1, 6); SeqListPushFront(&t1, 5); SeqListPushFront(&t1, 4); SeqListPushFront(&t1, 3); SeqListPushFront(&t1, 2); SeqListPushFront(&t1, 1); SeqListPrint(&t1); SeqListPopFront(&t1); SeqListPopFront(&t1); SeqListPopFront(&t1); SeqListPrint(&t1);//这里只删除了三个数据 //若放开后面的就会强制报错 //SeqListPopFront(&t1); //SeqListPopFront(&t1); //SeqListPopFront(&t1); //SeqListPopFront(&t1);//这里多删除了一个数据 } void test4() { SL t1; InitList(&t1); SeqListPushFront(&t1, 6); SeqListPushFront(&t1, 5); SeqListPushFront(&t1, 4); SeqListPushFront(&t1, 1); SeqListPushFront(&t1, 50); SeqListPrint(&t1);//这里只删除了三个数据 SeqListDestory(&t1); } void test5() { SL t1; InitList(&t1); SeqListPushFront(&t1, 6); SeqListPushFront(&t1, 5); SeqListPushFront(&t1, 4); SeqListPushFront(&t1, 3); SeqListPushFront(&t1, 2); SeqListPushFront(&t1, 1); SeqListPrint(&t1); SeqListInsert(&t1, 2, 10); SeqListPrint(&t1); } void test6() { SL t1; InitList(&t1); SeqListPushFront(&t1, 6); SeqListPushFront(&t1, 5); SeqListPushFront(&t1, 4); SeqListPushFront(&t1, 3); SeqListPushFront(&t1, 2); SeqListPushFront(&t1, 1); SeqListPrint(&t1); SeqListErase(&t1, 1); SeqListPrint(&t1); } void test7() { SL t1; InitList(&t1); SeqListPushFront(&t1, 6); SeqListPushFront(&t1, 5); SeqListPushFront(&t1, 4); SeqListPushFront(&t1, 3); SeqListPushFront(&t1, 2); SeqListPushFront(&t1, 1); SeqListPrint(&t1); SeqModify(&t1, 0, 10); SeqListPrint(&t1); } void test8() { SL t1; InitList(&t1); SeqListPushFront(&t1, 6); SeqListPushFront(&t1, 5); SeqListPushFront(&t1, 4); SeqListPushFront(&t1, 3); SeqListPushFront(&t1, 2); SeqListPushFront(&t1, 1); SeqListPrint(&t1); int ret =SeqListFind(&t1, 6);//查找6的下标 SeqListErase(&t1, ret);//完成删除 SeqListPrint(&t1); } int main() { //test1();//检测尾插的功能 //test2();//检查头插功能 //test3();//检测头部删除的功能 test4();//检测尾部删除的功能 //test5();//检测中间任意值插入数据 //test6();//检测中间任意值删除功能 //test7();//检测修改特定值的功能 //test8();//删除6 return 0; }

完整实现函数的.c文件

#include"SLlist.h" void SeqListPrint(SL* psl) { assert(psl);//断言防止传入空指针 for (int i = 0; i < psl->size; i++) { printf("%d ", psl->arr[i]); } printf("\n"); } void InitList(SL* psl) { psl->size = 0; psl->capacity = 4; psl->arr = (SLlistdata*)malloc(sizeof(SLlistdata) * (psl->capacity)); } void CheckCapacity(SL* psl) { if (psl->size == psl->capacity) { psl->capacity += 4; psl->arr = (SLlistdata*)realloc(psl->arr,sizeof(SLlistdata)*(psl->capacity)); if (psl->arr == NULL) { perror("realloc fail:"); return; } }//如果有效数据个数等于容量代表已经满员需要扩容 } void SeqListPushBack(SL* psl, SLlistdata x)//尾插数据 { ////我们要实现尾插肯定是要先检测顺序表的空间是否足够 //CheckCapacity(psl);//调用函数判断是否需要扩容 //psl->arr[psl->size] = x; //psl->size++;//这只是尾插的实现方法一，后面还有另外的方式 //实现方式二： SeqListInsert(psl, psl->size, x); }//下面我们来检验一下这两个函数是否有错误 void SeqListPushFront(SL* psl,SLlistdata x) { //CheckCapacity(psl); ////容量足够之后我们开始插入 ////从后往前开始移动数据 //for (int i = psl->size - 1; i >= 0; i--) //{ // psl->arr[i + 1] = psl->arr[i]; //} //psl->arr[0] = x; //psl->size++;//完成头插 SeqListInsert(psl, 0, x); }//我们再次去检测一下函数的实现 void SeqListPopFront(SL* psl)//头删从前往后移动数据，若是从后往前会造成数据复制 { //我们就要删除这一个数据自然就不需要检测空间是否足够了 //assert(psl);//防止传入空指针 //assert(psl->size > 0);//防止一直删除，这是一种暴力解决的方法，如果一直删除在有效数据个数size为0之后就会报错。 //for (int i = 0; i < psl->size; i++) //{ // psl->arr[i] = psl->arr[i + 1]; //} //psl->size--;//删除一个数据之后让size减一 SeqListErase(psl, 0); }//运用test3去检测功能 // 顺序表尾删 void SeqListPopBack(SL* psl) { //psl->size--; SeqListErase(psl, psl->size); }//运用test4去检测功能 // 顺序表在pos位置插入x void SeqListInsert(SL* psl, int pos, SLlistdata x) { assert(pos >= 0 && pos <= psl->size); CheckCapacity(psl);//先检测容量 for (int i = psl->size-1; i >= pos; i--) { psl->arr[i+1] = psl->arr[i]; } psl->arr[pos] = x; psl->size++; //这样就完成了， }//运用test5去检测功能 // 顺序表删除pos位置的值 void SeqListErase(SL* psl, int pos) { assert(psl->size > 0);//依旧是防止过量删除 assert(psl);//防止传入空指针 assert(pos >= 0 && pos <= psl->size);//这里不能等于size因为角标为size的空间不受我们控制。 for (int i = pos; i < psl->size; i++) { psl->arr[i] = psl->arr[i + 1]; } psl->size--; }//test6检测 void SeqModify(SL* psl, int pos, SLlistdata x) { assert(psl);//防止传入空指针 assert(pos >= 0 && pos < psl->size);//防止越界访问 psl->arr[pos] = x; }//test7检测功能是否实现 int SeqListFind(SL* psl, SLlistdata x) { assert(psl); for (int i = 0; i < psl->size; i++) { if (psl->arr[i] == x) { return i; } } return -1; } // 顺序表销毁 void SeqListDestory(SL* psl) { free(psl->arr); psl->arr = NULL; psl->size = 0; psl->capacity = 0; }

完整头文件：

#include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int SLlistdata;//便于我们修改要储存数据的类型 typedef struct SLlist { SLlistdata* arr;//用以创建空间 int size;//判断有效数据的个数 int capacity;//容量，判断是否需要扩容 }SL; // 检查空间，如果满了，进行增容 void CheckCapacity(SL* psl); // 顺序表尾插 void SeqListPushBack(SL* psl, SLlistdata x); // 顺序表尾删 void SeqListPopBack(SL* psl); // 顺序表头插 void SeqListPushFront(SL* psl, SLlistdata x); // 顺序表头删 void SeqListPopFront(SL* psl); // 顺序表查找 int SeqListFind(SL* psl, SLlistdata x); // 顺序表在pos位置插入x void SeqListInsert(SL* psl, int pos, SLlistdata x); // 顺序表删除pos位置的值 void SeqListErase(SL* psl, int pos); // 顺序表销毁 void SeqListDestory(SL* psl); // 顺序表打印 void SeqListPrint(SL* psl); //初始化顺序表 void InitList(SL* psl); //修改顺序表特定位的值 void SeqModify(SL* psl, int pos, SLlistdata x);

希望这篇博客对你有所帮助，如果有错误请严厉指出，我一定虚心接收