顺序表的实现与通讯录几乎一模一样，写过通讯录的来看看这篇文章就可以立马搞定顺序表。

首先我们按照惯例创建三个文件，一个里面是本工程所需要的头文件，一个里面是存放测试代码的文件，最后一个是放函数具体实现代码的文件。如图所示：

顺序表实际上是结构体里有一个你要存放数据类型的指针，每次增加数据都是给这个指针开辟空间，所以我们定义一个结构体变量，里面存放要保存什么类型的指针和一个记录位置的变量sz和记录空间容量的变量capcity。将结构体重命名为SeqList是为了后面更简单的使用结构体指针，将int重命名为SLDateType是为了以后方便存储其他类型数据只需要修改typedef后面的类型即可。代码如图：

 

接下来就进入正文了，我们的顺序表大致可以分为以下几个功能：

//初始化
void SeqListInit(SeqList* ps);
//释放
void SeqListDestory(SeqList* ps);
//打印
void SeqListPrint(SeqList* ps);
//尾插
void SeqListpushback(SeqList* ps, SLDateType x);
//检查扩容
void SeqListcheckcapcity(SeqList* ps);
//头插
void SeqListpushfront(SeqList* ps,SLDateType x);
//尾删
void SeqListpopback(SeqList* ps);
//头删
void SeqListpopfront(SeqList* ps);
//顺序表查找
int SeqListFind(SeqList* ps, SLDateType x);
//顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDateType x);
//顺序表删除pos位置
void SeqListErase(SeqList* ps, int pos);

 首先我们实现初始化函数，初始化就是将结构体里的指针初始化为空指针，两个变量都初始化为0.既然初始化会修改结构体里变量的值，那么传递参数的时候一定是地址然后用指针接收，修改的时候解引用这样才能成功初始化，如果只传值过来那么实参不会发生改变。

void SeqListInit(SeqList* ps)
{
	assert(ps != NULL);
	ps->data = NULL;
	ps->sz = 0;
	ps->capcity = 0;
}

 

初始化后我们进行释放内存的操作，因为在开辟了空间后我们退出程序前要释放开辟的空间不然就会发生内存泄漏。释放的时候只需要free结构体里存放数据的指针，然后置为空，将变量初始化为0.

 

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

 

接下来我们进行尾插操作，尾插就是每次在最后一个数据的后面插入新数据，既然是插入就需要判断是不是需要增加容量，当sz==capcity的时候就增加容量，在这里我为了后续方便将增容写成了一个函数这样其他模块也可以使用这个函数，如图所示：

 

void SeqListcheckcapcity(SeqList* ps)
{
	if (ps->sz == ps->capcity)
	{
		int newcapcity = ps->capcity == 0 ? 4 : 2 * ps->capcity;
		SLDateType* tmp = (SLDateType*)realloc(ps->data, newcapcity * sizeof(SLDateType));
		if (tmp == NULL)
		{
			perror("realloc:");
			exit(-1);
		}
		ps->data = tmp;
		ps->capcity = newcapcity;
	}
}

 

在这里我们定义了一个新容量大小，为什么定义在判断条件里面呢？那当然是因为第一次进来容量为空必然需要开辟空间所以并不用定义在外面，这里使用了三目操作符如果容量为0新空间就是4否则就是旧空间的两倍。然后我们用realloc开辟了新的容量大小的空间，使用realloc函数需要判断函数返回值是否为空，如果为空指针则开辟空间失败，所以我们用了if语句来判断，开辟成功后将空间给data指针并且把容量改成新的容量。

void SeqListpushback(SeqList* ps, SLDateType x)
{
	SeqListcheckcapcity(ps);
	ps->data[ps->sz] = x;
	ps->sz++;
}

 在尾插前需要先判断是否增加容量，如果需要增加则增加，如果不需要则直接将数据存入并且是位置指针加一。解决完尾插后我们进行头插，头插就是将新数据放在第一个位置，要实现这样的操作我们就需要把所有数据往后移一个位置，然后将新的数据插入到第一个位置，在这里切记要从最后一个数据开始移，如果从第一个开始就会发生数据覆盖.

void SeqListpushfront(SeqList* ps, SLDateType x)
{
	SeqListcheckcapcity(ps);
	int end = ps->sz - 1;
	while (end >= 0)
	{
		ps->data[end + 1] = ps->data[end];
		end--;
	}
	ps->data[0] = x;
	ps->sz++;
}

头插完后我们进行尾删，尾删很简单只需要将位置指针减1但是需要注意的是只有在有数据的情况下才需要删，有数据的情况介绍位置指针大于1的情况。

void SeqListpopback(SeqList* ps)
{
	assert(ps->sz > 0);
	ps->sz--;
}

尾删后我们进行头删，头删就是将第一个数据之后的数据依次向前移一个位置，与尾删一样都是在有数据的情况下删除，在这里要注意的是需要从前向后将数据往前覆盖，不能从最后一个数据开始向前因为这样会发生数据覆盖。

void SeqListpopfront(SeqList* ps)
{
	assert(ps->sz > 0);
	int begin = 1;
	while (begin < ps->sz)
	{
		ps->data[begin - 1] = ps->data[begin];
		begin++;
	}
	ps->sz--;
}

接下里我们介绍一下打印函数，打印函数很简单我们直接放代码：

void SeqListPrint(SeqList* ps)
{
	int i = 0;
	for (i = 0; i < ps->sz; i++)
	{
		printf("%d ", ps->data[i]);
	}
	printf("\n");
}

搞完打印函数后我们进行查找功能，查找功能就是查一个数在哪个位置这个位置就是下标，所以我们用for循环判断只要哪个位置的数据和要查找的数据相等我们就返回该数据的下标，否则就返回-1.

int SeqListFind(SeqList* ps, SLDateType x)
{
	int i = 0;
	for (i = 0; i < ps->sz; i++)
	{
		if (ps->data[i] == x)
		{
			return i;
		}
	}
	return -1;
}

查找函数后就需要在某个位置插入数据，我们先放代码：

void SeqListInsert(SeqList* ps, int pos, SLDateType x)
{
	assert(ps);
	assert(pos <= ps->sz&&pos >= 0);
	SeqListcheckcapcity(ps);
	if (pos == 0)
	{
		SeqListpushfront(ps, x);
		return;
	}
	int end = ps->sz-1;
	while (end >= pos)
	{
		ps->data[end + 1] = ps->data[end];
		end--;
	}
	ps->data[pos] = x;
	ps->sz++;
}

插入数据要保证传来的结构体地址不是空指针并且位置也有要求这些位置都必须在0到位置指针之前的这个区间，然后所有插入都需要先判断是否增容，当位置为0是就是头插我们实现头插功能即可，否则就将这个位置的后面的所有数据都往后移一个位置，同样是将数据从最后开始移移完后将数据放入指定位置即可。然后位置指针加1。

接下里我们进行最后一个功能指定位置删除，指定位置删除就是将这个位置的数据覆盖即可，如何覆盖呢?只需要将这个位置的后一个数据从前往后移一个位置就将pos位置覆盖，代码如下：

void SeqListErase(SeqList* ps, int pos)
{
	assert(pos >= 0 && pos < ps->sz);
	int begin = pos + 1;
	while (begin < ps->sz)
	{
		ps->data[begin - 1] = ps->data[begin];
		begin++;
	}
	ps->sz--;
}

同样位置需要判断是否在合理区间并且删除需要判断传来的结构体地址是否为空这里我没加到，只需要在assert后面一行加assert(ps)即可。这样我们就搞定了C语言顺序表的实现，大家快去试试吧。

顺序表的问题及思考