前言

顺序表标是一种简单的线性结构。一般也是数据结构初学者对最开始接触到的一种数据结构。本文将会对顺序表进行相关介绍，为以后深入学习其他数据结构打下基础。

1.顺序表的相关介绍

1.什么是顺序表

顺序表顾名思义就是按顺序排列的数据集合。之前博客介绍了通讯录的实现，其实当时实现的通讯录本质就是顺序表。顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

顺序表可以分为静态顺序表和动态顺序表。静态顺序表：使用定长数组存储元素。动态顺序表：使用动态开辟的数组存储。之前最开始实现通讯录就是静态的顺序表，后来简单的改造一下，就是将静态的顺序表改成动态的顺序表用来存储数据。

2.顺序表的具体实现

1.顺序表的创建和相关接口的介绍

既然要实现顺序表首先肯定是定义创建顺序表这种数据结构。有了顺序表后就是对顺序表中的数据进行增删改查。这些增删改查实际都是通过调用相关功能函数实现的。所以接着就是实现这些函数。同时我们知道调用函数只用知道函数名传入相关的参数即可。这些函数就像充电线的接口一样，要给苹果手机充电就用苹果接口的充电线。要给小米手机充电就用小米接口充电线。我们要查找数据时就调用查找函数即可，所以这些函数又称接口。

静态顺序表接口

接口大致分为如下：
顺序表初始化： SeqListInit
顺序表头插： SeqListPushFront
顺序表尾插：SeqListPushBack
顺序表指定位置插入：SeqListInsert
顺序表头删：SeqListPopFront
顺序表尾删：SeqListPopBack
顺序表指定位置删除：SeqListErase
顺序表指定数据查找： SeqListFind
顺序表打印：SeqListPrint

动态顺序表接口

动态的顺序表的接口就是在静态的接口上增加了两个接口。
检查空间增容接口： CheckCapacity(如果满了，进行增容）
顺序表销毁接口：SeqListDestory
只所以会多了两个接口，因为动态顺序表是采用动态开辟空间来实现顺序表的。当给顺序表分配的空间使用完了以后，可以申请动态内存空间进行扩容。同时因为使用的是动态内存空间，所以要及时释放申请到的内存空间，避免造成内存泄漏，所以也就有了一个销毁顺序表的接口。

2.代码具体实现

1.静态顺序表相关代码实现

1.定义静态顺序表

#include<stdio.h>
#define DataType int
#define MAX 100
typedef struct SeqList
{
	DataType data[MAX];//存储数据
	int sz;//记录数据个数

}SeqList;

int main()
{
	SeqList list;//创建顺序表
	SeqList* ps = &list;//通过指针访问顺序表

}

在实现数据结构时，建议将接口函数和数据结构的声明定义 接口函数的实现 数据结构的测试代码分别编写在不同的文件中，就像实现通讯录那样建立头文件和.c文件，这样写代码更加规范。同时每完成一个功能就测试一下有没有问题，不然随着代码量的增大，调试代码时会有点微麻烦。我这里为了演示方便就没有分开写，但是在实际编写代码时一定要规范一点。
定义了一个顺序表的结构体，同时使用了define预处理指令，这样做的做的目的是，避免将程序写死了，以后如果想存储其他的类型的数据时，只需要更改预处理部分即可，同时使用指针来访问这个顺序表操作起来比较方便，而且数据操作肯定也是地址传参调用接口才能真正修改数据，既然涉及了地址，指针肯定必不可少的。这样通过指针访问顺序表可谓是好处多多。sz记录了存储数据的个数。

2.各个接口的实现

首先初始化顺序表

void SeqListInit(SeqList* ps,int n)//初始化
{
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &(ps->data[i]));
	}
	ps->sz = n;
	return;
}

初始化数据根据自己的想法，可以设置固定数据录入顺序表，也可以手动输入，我这里是手动自己输入，录入数据的个数也是自己决定。但是我这里没有写对空指针的判断和对n的判断，n是不能超过100的，因为最开始设置的数据最大存储量是100。

接着就是数据的插入

头插实现

void SeqListPushFront(SeqList* ps,DataType x)//头插
{    
	 ps->sz++;//因为插入一个数据所以现增容
	if (ps->sz <= 100)//同时最大的存储量是100，所以判断增容后超限了没
	{
		for (int i = ps->sz - 1; i >0; i--)
		{
			ps->data[i] = ps->data[i - 1];
		}
		ps->data[0] = x;
	}
	return;
   
}

顺序表头插就是顺序表第一个位置插入数据，因为顺序表是用数组存储数据的，所以就是在数组首位置插入数据，插入数据就是增加一个数据，所以sz自增加1.但是插入了数据原来存储的数据的位置肯定会改变。因此在插入之前需要将数组中的数据进行挪动。把位置先让出来，在将数据插入进去。挪动数据实际就是元素覆盖，将前一个数据给后一个。挪动数据的时候是从尾部开始往前挪动。这样能保证数据准确无误的迁移。不然数据被错误覆盖就会丢失数据。最后将要插入的数据移动到数组首位置。之所以最后才插入数据要保证原来的数据都能迁移到新位置上。如果开始就插入，那么原来首位置处的数据就丢失了。

尾插实现

void  SeqListPushBack(SeqList* ps,DataType x)//尾插
{
	ps->sz++;//插入数据，数据增加
	if (ps->sz <= 100)
	{
		ps->data[ps->sz - 1] = x;
	}
	return;
}

尾插实现就简单了。可以通过sz快速找到尾部，甚至都不需要遍历数组。将数据直接插入尾部即可。我没有对空指针进行判断，严谨一点应该加上空指针的判断。

指定位置插入

//顺序表指定位置插入
void SeqListInsert(SeqList* ps, DataType x, int pos)
{
	if ((pos > ps->sz)&&ps->sz>=100)
	{
		return;
	}
	ps->sz++;
	for (int i = ps->sz - 1; i >= pos; i--)
	{
		ps->data[i] = ps->data[i - 1];
	}
	ps->data[pos-1] = x;
	return;
}

顺序表之所以是叫顺序表是因为存储数据是按顺序一个个存储的，就跟做核酸排队时一样，一个接一个。所以插入数据要在已有的位置进行插入。或者是紧接着尾部插入数据。其次要注意数组下标，因为数组下标是从0开始的。同时除了尾插其他外插入数据都需要挪动数据。一般都是从尾部开始往前挪动，这样逻辑清晰，也不容易出错。

数据的删除

头删的实现

void SeqListPopFront(SeqList*ps)//头删
{
	if (ps->sz == 0)
	 {
		return ;//顺序表为空直接返回
     }
	for (int i = 0; i < ps->sz-1; i++)//注意下标范围
	{
		ps->data[i] = ps->data[i + 1];
	}
	ps->sz--;//删除一个元素，sz减1
}

顺序表头删就是删除首位置处的数据，数组中的元素实际上是不能删除的，都是利用元素覆盖来实现的。所以也需要挪动数据。和头插的挪动方式不一样，这个是从前开始往前挪动。当元素挪动完后，就实现了删除数据。sz需要减减，表示存储的数据少了一个。

尾删的实现

void SeqListPopBack(SeqList* ps)//尾删
{
	if (ps->sz == 0)//顺序表为空直接返回
	{
		return;
	}
	ps->sz--;//直接sz减1即可
}

顺序表的尾删实现很简单就sz减减表示删除少了一个数据即可。因为顺序表打印和输入都是以sz为数组下标界限的。sz不仅能记录数据个数，还能通过sz找到顺序表的尾部，充当数组下标来使用。

指定位置的删除

void SeqListErase(SeqList* ps, int pos)//指定位置删除
{
	if (pos > ps->sz)//位置非法
	{
		return;
    }

	for (int i = pos-1; i < ps -> sz-1; i++)
	{
		ps->data[i] = ps->data[i+1];
	}
	ps->sz--;// 如果是最后一个位置，直接相当于尾删直接减减即可
	         //不是最后一个位置，删除一个数，sz也要减减
}

头删是从头开始进行元素覆盖，指定位置是删除就是从指定位置开始元素覆盖。因为这个指定位置的范围是从1到n，不是从0开始的，所以要注意数组下表。如果是最后一个位置删除，不会进入for循环直接相当于尾删直接sz减减即可,如果不是最后一个位置，删除一个数，sz也要减减。

数据的查找和数据打印显示

数据查找的实现

int  SeqListFind(SeqList* ps, DataType x)//相当于遍历数组
{
	if (ps->sz == 0)//顺序表为空
	{
		return -2;
	}
	for (int i = 0; i < ps->sz; i++)
	{
		if (ps->data[i] == x)
		{
			
			return i+1;
		}
	}
	return -1;
}

顺序表查找数据就相当于遍历数组，所以挨个遍历比对即可。如果找到了就返回所在的位置。因为位置是范围是从1到n的，所以i+1。这点是我自己的设想，想从0到n也行，但是代码也要做相应的调整。如果没找到就返回一个不可能是数组下标的值，我设置的是负1。

打印显示数据

void Print(SeqList* ps)//打印显示
{
	for (int i = 0; i < ps->sz; i++)
	{
		printf("%d ", ps->data[i]);
	}
	printf("\n");
	return;
}

打印显示的实现也比较简单。还是遍历数组挨个打印即可。

2.动态顺序表相关代码的实现

之前实现了静态的顺序表。动态的顺序表只是在静态的基础上加了两个接口函数。检查空间增容接口： CheckCapacity(如果满了，进行增容）顺序表销毁接口：SeqListDestory。因为这个增容的函数只是在数组空间不够时才进行调用所以，也就是说只有在插入数据才可能会调用该函数，而销毁的接口只是在最后调用一次即可。所以重点会对动态顺序表的定义和插入数据的接口以及销毁接口进行介绍。

1.定义动态顺序表

#define DataType int
#define RL 5//每次增加的容量
typedef struct SeqList
{
	DataType* data;//存储数据
	int sz;//记录数据个数
	int capacity;//记录容量

}SeqList;

动态顺序表和静态的类似，不过data不在是数组形式，是指针用来接收每次分配的动态内存的首地址。sz还是记录数据个数，多了一个成员capacity是用来记录空间容量。RL是每次增加的容量大小。
初始化接口

void SeqListInit(SeqList* ps)//初始化
{
	ps->data = (DataType*)malloc(sizeof(DataType) * RL);
	if (ps->data != NULL)//空指针判断
	{
		 ps->capacity = RL;
		 for (int i = 0; i < RL-2; i++)//可以初始化3个数据
		 {
			 scanf("%d", &ps->data[i]);
		 }
		 ps->sz = RL-2;//记录录入数据的个数
	}
	return;
}

初始化函数只是在最开始调用一次，首先开辟了5个DataType大小的空间，所以容量此时要更新成5。我设定只能初始化3个数据。sz也要更新成3.

2.插入数据和增容空间

在介绍插入数据之前，先介绍如何增容空间。

int CheckCapacity(SeqList* ps)
{
	ps->capacity += RL;
	DataType* ptr = (DataType*)realloc
	(ps->data, sizeof(DataType) *   ps->capacity);
		if (ptr != NULL)
		{
			ps->data = ptr;
			ptr = NULL;
			return 1;
		}
	    return -1;
}

这里增容空间使用的是动态内存管理函数realloc。之所以使用这个函数，这个函数不仅仅能向内存申请空间还能对原空间原有数据进行迁移。关于这个函数我之前博客有过介绍，这里不在做过多的赘述。capacity是记录空间容量的，容量增加capacit也要更新，然后申请空间。申请空间要进行空指针判断，申请成功也就是说增容成功，然后返回1，如果不成功就返回-1。

插入数据是，只需要对每次记录的数据个数进行判断，判断记录的个数是否是等于空间容量，如果不等于说明还有空间，如果相等，就说明没有多余的空间位置来存储插入的数据了。这个时候就需要增容了。

if(ps->sz == ps->capacity)
	  {
		 int ret= CheckCapacity(ps);
		 if (ret == -1)
		 {
			 return;
		 }
	  }

在所有的的插入函数之前只需要加上这个增容判断即可。如果需要增容就增容，增容失败就直接返回。如果不需要增容就直接插入数据。
其余的删除函数和打印显示函数查找函数的实现和静态顺序表基本上是一样的，不在过多的介绍。

3.销毁顺序表

 void SeqListDestory(SeqList*ps)
 {
	 free(ps->data);
	 ps->data = NULL;
	 ps ->sz = 0;
	 ps->capacity = 0;
 }

使用ferr及时释放掉申请的空间，不然就会造成内存泄漏。sz和capacity都置为0.这样就销毁了顺序表。

3.总结

一般来说顺序表都是用数组来存储数据。涉及数组存储数据，都是按顺序挨个存储数据，这也是顺序表的特点。数组是不能直接删除数据的，一般都是挪动数据元素覆盖来实现数据的删除。插入数据就是存储数据，这也会涉及数据挪动，因为只有把要插入的位置给空出来才能插入数据。

在尾插尾删数据时是很简单的。这是因为尾删和尾插就是相当于顺序删除存储数据。直接遍历找到尾部即可。但是通过sz可以快速的找到尾部，甚至不需要遍历，直接就可以操作顺序表。

顺序表实现还是很简单的。顺序表可以理解成排队核酸，从前往后挨个排队，插入数据就相当于有人插队，队尾的人先往后退一个位置，然后依次往后退，把位置腾出来，插队的人才能站到想要的位置。尾插就是按顺序排队，直接站在队尾即可。所以不麻烦。同理，尾删也就是队尾的人不想排了，直接离开这个队列。也不麻烦。

以上内容如有问题，欢迎指正！