朋友们、伙计们，我们又见面了，本期来给大家解读一下数据结构方面有关顺序表的相关知识点，如果看完之后对你有一定的启发，那么请留下你的三连，祝大家心想事成！

C语言专栏：C语言：从入门到精通

数据结构专栏：数据结构

个人主页：stackY、

1.线性表 

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储
 

2.顺序表

2.1概念及结构 

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般可以分为：

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

//静态顺序表
#define N 5
typedef  int SLDataType;
typedef struct SeqList
{SLDataType a[N]; //定长数组 int Size;        //顺序表中的有效元素的个数
}SL;

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

//动态顺序表
typedef int SLDataType;typedef struct SeqList
{SLDataType* a;  //指向动态开辟的数组int Size;       //有效元素的个数int Capactiy;	//容量
}SL;

 

2.2接口实现 

 静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。在动态顺序表中我们主要实现增删查改的功能，我们可以分板块来写，类似于通讯录的样式，这样方便使用，当然大家也可以在一个源文件中写，我们这里创建两个源文件：Test.c和SeqList.c，再创建一个头文件：SeqList.h,这里的文件命名不做要求，表示的有意义就行。同样的我们在Test.c中实现基本逻辑，在SeqList.c中实现顺序表的细节，在SeqList.h中进行函数声明和头文件包含等，话不多说，我们直接开始：

2.2.1初始化顺序表 

在初始化通讯录里面我们需要为顺序表动态开辟一块空间，然后初始给顺序表的容量为4，默认有效元素个数是0。

头文件：SeqList.h

#include <stdio.h>
#include <stdlib.h>//静态顺序表
//#define N 5
//typedef  int SLDataType;
//typedef struct SeqList
//{
//	SLDataType a[N]; //定长数组 
//	int Size;        //顺序表中的有效元素的个数
//}SL;//动态顺序表
typedef int SLDataType;typedef struct SeqList
{SLDataType* a;  //指向动态开辟的数组int Size;       //有效元素的个数int Capactiy;	//容量
}SL;//初始化
void SLInit(SL* ps);

源文件：Test.c

#include "SeqList.h"
//   数据结构————顺序表int main()
{SL s;//初始化SLInit(&s);return 0;
}

源文件：SeqList.c

#include "SeqList.h"//初始化
void SLInit(SL* ps)
{assert(ps);ps->a = (SLDataType*)malloc(sizeof(SLDataType) * 4);  //由于类型重新命名了，我们直接用即可if (ps->a == NULL){perror("malloc fail:");return;}ps->Size = 0;ps->Capactiy = 4;  //默认是4个容量
}

2.2.2释放顺序表 

 释放顺序表指的就是把为顺序表动态开辟的空间释放掉，将有效的元素个数和顺序表的容量都置为0。

头文件：SeqList.h

//释放
void SLDestroy(SL* ps);

源文件：Test.c

#include "SeqList.h"
//   数据结构————顺序表int main()
{SL s;//初始化SLInit(&s);//释放SLDestroy(&s);return 0;
}

源文件：SeqList.c

//释放
void SLDestroy(SL* ps)
{assert(ps);free(ps->a);   //释放ps->a = NULL;  //释放之后一定要置为NULLps->Size = 0;  //有效元素个数置为0ps->Capactiy = 0; //容量置为0
}

2.2.3容量检查

容量检查就是要检查顺序表中有效元素的个数是否达到了顺序表的最大容量，如果等于最大容量，那么就表示满了、放不下了，就需要进行扩容，那怎么扩容呢？

由于我们的顺序表是由malloc开辟来的，所以可以通过realloc 来进行扩容，我们这里就规定每次扩容至原空间的2倍：

头文件：SeqList.h

//容量检测
void SLCheckCapactiy(SL* ps);

源文件：SeqList.c

//检测容量
void SLCheckCapactiy(SL* ps)
{assert(ps);if (ps->Size == ps->Capactiy) //有效元素个数等于顺序表的容量之后{SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * ps->Capactiy * 2);if (tmp == NULL){perror("realloc fail:");return;}ps->a = tmp;  //将扩充之后的空间再赋给原空间ps->Capactiy *= 2;  //容量扩容值2倍}
}

2.2.4从尾部插数据

 从尾部插入数据就比较简单了，首先要进行容量检查，然后就是将要插入的放在顺序表中下标为Size的位置上，放完之后需要对Size进行加一。

头文件：SeqList.h

//尾插
void SLPushBack(SL* ps, SLDataType num);

源文件：SeqList.c

//尾插
void SLPushBack(SL* ps, SLDataType num)
{SLCheckCapactiy(ps);ps->a[ps->Size] = num;  //将要插入的数据放在最后面ps->Size += 1;
}

2.2.5从头部插入数据 

从头部插入数据首先还是要进行容量检查，然后就是将数据放在顺序表中下标为0的位置上， 然后将数据依次向后面挪动一个位置，在这里的挪动就有说法了，是从前面的开始挪还是从后面的开始挪呢？答案是从后面的开始挪，如果你从前面开始挪，那你把你挪动的数据放在下一个位置上面是不是把它覆盖掉了，所以我们需要从后面的开始挪动：

头文件：SeqList.h

//头插
void SLPushFront(SL* ps, SLDataType num);

源文件：SeqList.c

//头插
void SLPushFront(SL* ps, SLDataType num)
{SLCheckCapactiy(ps);int end = ps->Size - 1;  //注意这里的判断条件不唯一，是根据end的值来进行判断//可以进行画图来区分while (end >= 0){ps->a[end + 1] = ps->a[end];--end;}ps->a[0] = num;   //将要插入的数据放在顺序表的头部ps->Size++;
}

2.2.6从尾部删除数据 

 从尾部删除数据就更加简单了，首先我们得检查我们的顺序表中是否有元素，有元素才可以进行删除，没有元素删不了，所以可以将顺序表的有效元素个数进行断言，删除尾部元素最简单的方法就是直接对有效元素的个数进行减1，因为顺序表就相当于数组嘛，我们是通过数组的下标来进行访问数组，所以直接将顺序表的有效元素减一之后就访问不到最后一个元素了，这不也就达到了我们所想要的效果了嘛，当然有的老铁会想到将最后一个元素改为0，但是如果最后一个元素本来就是0呢？因此最简单有效的方法就是我们直接对顺序表的有效元素的个数减一就可以达到我们从尾部删除数据的效果。

头文件：SeqList.h

//尾删
void SLPopBack(SL* ps);

源文件：SeqList.c

//尾删
void SLPopBack(SL* ps)
{assert(ps);assert(ps->Size > 0);  //判断是否存在数据ps->Size--;
}

2.2.7从头部删除数据 

从头部删除数据就是将顺序表中下标为0的数据删掉，那我们可以直接进行覆盖，这里的覆盖也有门道了，我们是从前面开始挪呢？还是从后面开始挪呢？答案是从前面开始依次向前挪动一个位置，这里要注意，如果从后面依次开始挪动，那么最后面的数据挪到前面会将前一个数据覆盖掉 ，这样就达不到我们预期的效果了，当然了，在删除之前我们也需要进行判断顺序表中是否有数据，删除成功之后需要将我们的有效元素个数减一。

头文件：SeqList.h

//头删
void SLPopFront(SL* ps);

源文件：SeqList.c

//头删
void SLPopFront(SL* ps)
{assert(ps);assert(ps->Size > 0);  //判断是否存在数据int start = 0;while (start < ps->Size - 1)  //判断条件还是需要进行画图来观察，切记不要越界访问{ps->a[start] = ps->a[start + 1];start++;}ps->Size--;
}

2.2.8 指定位置插入数据

将数据插入顺序表中下标为pos的位置上，首先呢我们需要进行容量检查，然后再判断pos的合法性，是否在0~Size之间，如果是0那么就代表头插，如果是Size就代表尾插，所以在这里我们还是需要进行挪动数据，腾出地方来让我们插入数据，所以呢，就需要将pos位置后面的数据依次挪动一个位置，这里注意需要从后面开始挪动，以防数据被覆盖掉，挪动之后将数据放在pos的位置上，然后顺序表的有效元素个数加1。

 头文件：SeqList.h

//在pos位置插入数据
void SLInsert(SL* ps, int pos, SLDataType num);

源文件：SeqList.c

//在pos位置插入数据
void SLInsert(SL* ps, int pos, SLDataType num)
{SLCheckCapactiy(ps); //容量检测assert(pos >= 0 && pos <= ps->Size);  //判断pos位置的合法性//挪动int end = ps->Size - 1;while (end >= pos){ps->a[end + 1] = ps->a[end];--end;}ps->a[pos] = num;  //插入数据ps->Size++;
}

2.2.9 指定位置删除数据

在指定位置删除数据就直接挪动覆盖就好了，所以呢我们需要先进行pos的合法性检查，是否在0~Size之间，如果是0那么就代表头删，如果是Size就代表尾删，在这里的挪动也是需要先从前面的开始挪动，在删除成功之后就将顺序表的有效元素个数减1。

 头文件：SeqList.h

//在pos位置删除数据
void SLErase(SL* ps, int pos);

源文件：SeqList.c

//在pos位置删除数据
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos <= ps->Size);  //判断pos位置的合法性int start = pos;while (start < ps->Size){ps->a[start] = ps->a[start + 1];start++;}ps->Size--;
}

 2.2.10优化插入、删除数据 

 当我们写出了从指定位置插入或删除数据的时候，我们可以发现，当我们指定的位置是0和Size的时候就表示从顺序表的头部和尾部进行插入或删除，因此我们可以直接在头插、头删、尾插、尾删中套用SLInsert和SLErase这两个函数，在传参的时候直接传递0或Siez即可。

源文件：SeqList.c

//尾插
void SLPushBack(SL* ps, SLDataType num)
{SLInsert(ps, ps->Size - 1, num);}//头插
void SLPushFront(SL* ps, SLDataType num)
{SLInsert(ps, 0, num);
}//尾删
void SLPopBack(SL* ps)
{SLErase(ps, ps->Size - 1);}//头删
void SLPopFront(SL* ps)
{SLErase(ps, 0);
}//在pos位置插入数据
void SLInsert(SL* ps, int pos, SLDataType num)
{SLCheckCapactiy(ps); //容量检测assert(pos >= 0 && pos <= ps->Size);  //判断pos位置的合法性//挪动int end = ps->Size - 1;while (end >= pos){ps->a[end + 1] = ps->a[end];--end;}ps->a[pos] = num;  //插入数据ps->Size++;
}//在pos位置删除数据
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos <= ps->Size);  //判断pos位置的合法性int start = pos;while (start < ps->Size){ps->a[start] = ps->a[start + 1];start++;}ps->Size--;
}

2.2.11查找数据 

 查找顺序表中的某一个数据，如果查找成功就返回它的下标，如果查找失败就返回-1，所以我们需要遍历一下顺序表进行查找。

 头文件：SeqList.h

//查找数据
int SLFind(SL* ps, SLDataType num);

源文件：SeqList.c

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

2.2.12修改数据 

修改数据就更加简单了，直接将pos位置的数据进行赋值你所要改的值，所以先要进行对pos的合法性检查，然后再修改。

 头文件：SeqList.h

//修改数据
void SLModify(SL* ps, int pos, SLDataType num);

源文件：SeqList.c

//修改数据
void SLModify(SL* ps, int pos, SLDataType num)
{assert(ps);assert(pos >= 0 && pos < ps->Size);ps->a[pos] = num;
}

2.2.13打印顺序表 

打印顺序表和打印数组一模一样，通过有效元素个数来控制打印次数。

头文件：SeqList.h

//打印
void SLPrint(SL* ps);

源文件：SeqList.c

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

2.2.14未优化的完整代码

这里指的是没有优化插入和删除数据的代码：

源文件：Test.c

#define _CRT_SECURE_NO_WARNINGS 1#include "SeqList.h"
//   数据结构————顺序表int main()
{SL s;//初始化SLInit(&s);//在这里可以加上增添、查找、删除、修改等函数的调用//...//...//...//打印SLPrint(&s);//释放SLDestroy(&s);return 0;
}

 头文件：SeqList.h

#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>//静态顺序表
//#define N 5
//typedef  int SLDataType;
//typedef struct SeqList
//{
//	SLDataType a[N]; //定长数组 
//	int Size;        //顺序表中的有效元素的个数
//}SL;//动态顺序表
typedef int SLDataType;typedef struct SeqList
{SLDataType* a;  //指向动态开辟的数组int Size;       //有效元素的个数int Capactiy;	//容量
}SL;//初始化
void SLInit(SL* ps);
//释放
void SLDestroy(SL* ps);
//容量检测
void SLCheckCapactiy(SL* ps);//尾插
void SLPushBack(SL* ps, SLDataType num);
//头插
void SLPushFront(SL* ps, SLDataType num);
//尾删
void SLPopBack(SL* ps);
//头删
void SLPopFront(SL* ps);//在pos位置插入数据
void SLInsert(SL* ps, int pos, SLDataType num);//在pos位置删除数据
void SLErase(SL* ps, int pos);//查找数据
int SLFind(SL* ps, SLDataType num);//修改数据
void SLModify(SL* ps, int pos, SLDataType num);//打印
void SLPrint(SL* ps);

源文件：SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"//初始化
void SLInit(SL* ps)
{assert(ps);ps->a = (SLDataType*)malloc(sizeof(SLDataType) * 4);  //由于类型重新命名了，我们直接用即可if (ps->a == NULL){perror("malloc fail:");return;}ps->Size = 0;ps->Capactiy = 4;  //默认是4个容量
}//释放
void SLDestroy(SL* ps)
{assert(ps);free(ps->a);   //释放ps->a = NULL;  //释放之后一定要置为NULLps->Size = 0;  //有效元素个数置为0ps->Capactiy = 0; //容量置为0
}//检测容量
void SLCheckCapactiy(SL* ps)
{assert(ps);if (ps->Size == ps->Capactiy) //有效元素个数等于顺序表的容量之后{SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * ps->Capactiy * 2);if (tmp == NULL){perror("realloc fail:");return;}ps->a = tmp;  //将扩充之后的空间再赋给原空间ps->Capactiy *= 2;  //容量扩容值2倍}
}//尾插
void SLPushBack(SL* ps, SLDataType num)
{SLCheckCapactiy(ps);ps->a[ps->Size] = num;ps->Size += 1;}//头插
void SLPushFront(SL* ps, SLDataType num)
{SLCheckCapactiy(ps);int end = ps->Size - 1;while (end >= 0){ps->a[end + 1] = ps->a[end];--end;}ps->a[0] = num;ps->Size++;
}//尾删
void SLPopBack(SL* ps)
{assert(ps);assert(ps->Size > 0);  //判断是否存在数据ps->Size--;}//头删
void SLPopFront(SL* ps)
{assert(ps);assert(ps->Size > 0);  //判断是否存在数据int start = 0;while (start < ps->Size - 1){ps->a[start] = ps->a[start + 1];start++;}ps->Size--;
}//在pos位置插入数据
void SLInsert(SL* ps, int pos, SLDataType num)
{SLCheckCapactiy(ps); //容量检测assert(pos >= 0 && pos <= ps->Size);  //判断pos位置的合法性//挪动int end = ps->Size - 1;while (end >= pos){ps->a[end + 1] = ps->a[end];--end;}ps->a[pos] = num;  //插入数据ps->Size++;
}//在pos位置删除数据
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos <= ps->Size);  //判断pos位置的合法性int start = pos;while (start < ps->Size){ps->a[start] = ps->a[start + 1];start++;}ps->Size--;
}//查找数据
int SLFind(SL* ps, SLDataType num)
{assert(ps);int i = 0;for (i = 0; i < ps->Size; i++){if (ps->a[i] == num){return i;}}return -1;
}//修改数据
void SLModify(SL* ps, int pos, SLDataType num)
{assert(ps);assert(pos >= 0 && pos < ps->Size);ps->a[pos] = num;
}//打印
void SLPrint(SL* ps)
{assert(ps);int i = 0;for (i = 0; i < ps->Size; i++){printf("%d ", *(ps->a + i));}printf("\\n");
}

2.2.15优化过后的完整代码 

 这里是优化过插入和删除数据的代码：

源文件：Test.c

#define _CRT_SECURE_NO_WARNINGS 1#include "SeqList.h"
//   数据结构————顺序表int main()
{SL s;//初始化SLInit(&s);//在这里可以加上增添、查找、删除、修改等函数的调用//...//...//...//打印SLPrint(&s);//释放SLDestroy(&s);return 0;
}

 头文件：SeqList.h

#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>//静态顺序表
//#define N 5
//typedef  int SLDataType;
//typedef struct SeqList
//{
//	SLDataType a[N]; //定长数组 
//	int Size;        //顺序表中的有效元素的个数
//}SL;//动态顺序表
typedef int SLDataType;typedef struct SeqList
{SLDataType* a;  //指向动态开辟的数组int Size;       //有效元素的个数int Capactiy;	//容量
}SL;//初始化
void SLInit(SL* ps);
//释放
void SLDestroy(SL* ps);
//容量检测
void SLCheckCapactiy(SL* ps);//尾插
void SLPushBack(SL* ps, SLDataType num);
//头插
void SLPushFront(SL* ps, SLDataType num);
//尾删
void SLPopBack(SL* ps);
//头删
void SLPopFront(SL* ps);//在pos位置插入数据
void SLInsert(SL* ps, int pos, SLDataType num);//在pos位置删除数据
void SLErase(SL* ps, int pos);//查找数据
int SLFind(SL* ps, SLDataType num);//修改数据
void SLModify(SL* ps, int pos, SLDataType num);//打印
void SLPrint(SL* ps);

源文件：SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"//初始化
void SLInit(SL* ps)
{assert(ps);ps->a = (SLDataType*)malloc(sizeof(SLDataType) * 4);  //由于类型重新命名了，我们直接用即可if (ps->a == NULL){perror("malloc fail:");return;}ps->Size = 0;ps->Capactiy = 4;  //默认是4个容量
}//释放
void SLDestroy(SL* ps)
{assert(ps);free(ps->a);   //释放ps->a = NULL;  //释放之后一定要置为NULLps->Size = 0;  //有效元素个数置为0ps->Capactiy = 0; //容量置为0
}//检测容量
void SLCheckCapactiy(SL* ps)
{assert(ps);if (ps->Size == ps->Capactiy) //有效元素个数等于顺序表的容量之后{SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * ps->Capactiy * 2);if (tmp == NULL){perror("realloc fail:");return;}ps->a = tmp;  //将扩充之后的空间再赋给原空间ps->Capactiy *= 2;  //容量扩容值2倍}
}//尾插
void SLPushBack(SL* ps, SLDataType num)
{SLInsert(ps, ps->Size - 1, num);
}//头插
void SLPushFront(SL* ps, SLDataType num)
{SLInsert(ps, 0, num);
}//尾删
void SLPopBack(SL* ps)
{SLErase(ps, ps->Size - 1);
}//头删
void SLPopFront(SL* ps)
{SLErase(ps, 0);
}//在pos位置插入数据
void SLInsert(SL* ps, int pos, SLDataType num)
{SLCheckCapactiy(ps); //容量检测assert(pos >= 0 && pos <= ps->Size);  //判断pos位置的合法性//挪动int end = ps->Size - 1;while (end >= pos){ps->a[end + 1] = ps->a[end];--end;}ps->a[pos] = num;  //插入数据ps->Size++;
}//在pos位置删除数据
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos <= ps->Size);  //判断pos位置的合法性int start = pos;while (start < ps->Size){ps->a[start] = ps->a[start + 1];start++;}ps->Size--;
}//查找数据
int SLFind(SL* ps, SLDataType num)
{assert(ps);int i = 0;for (i = 0; i < ps->Size; i++){if (ps->a[i] == num){return i;}}return -1;
}//修改数据
void SLModify(SL* ps, int pos, SLDataType num)
{assert(ps);assert(pos >= 0 && pos < ps->Size);ps->a[pos] = num;
}//打印
void SLPrint(SL* ps)
{assert(ps);int i = 0;for (i = 0; i < ps->Size; i++){printf("%d ", *(ps->a + i));}printf("\\n");
}

注意：

1.这些函数在这里就不使用案例来测试了，大家有兴趣可以自己动手来敲一敲，熟能生巧！

2.在顺序表的一些操作中是需要通过画图来判断它的限制条件，一定要画图！一定要画图！一定要画图！ 

2.3顺序表的问题及思考

问题：
1. 中间/头部的插入删除，时间复杂度为O(N)。

2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

思考：

如何解决这些问题呢？这时就需要用到我们的链表啦，关于链表的知识我们下期再聊。

朋友们、伙计们，美好的时光总是短暂的，我们本期的的分享就到此结束，欲知后事如何，请听下回分解~，最后看完别忘了留下你们弥足珍贵的三连喔，感谢大家的支持！