数据结构-动态顺序表（C语言）

本期是用于记录一下我个人了解下的顺序表。

首先，我们从顺序表的概念上来理解：即为物理地址连续的存储空间依次存储数据的一种线性结构，一般采用数组存储，并且在数组上完成数据的增删查改。根据不同的空间开辟方式，我们可以分为：静态顺序表和动态顺序表。

1：静态顺序表：即使用定长的数组存储元素。个人理解：我认为可以直接理解成空间大小固定的数组，更容易理解。我们可以将静态顺序表看作一个火车，在这个火车（静态顺序表）上的最大承载人员数量固定（内容存储空间大小固定）。

例如当前这幅图的火车，我们就可以看作一个静态顺序表，仅有四个车厢（4个内存大小）仅可存放4个游客（4个类型相同的数据），上完即止，无法增加。这种时候我们如果要扩容，就得换一辆空间更大的火车（用realloc重新申请一块更大空间来存储数据）。

2：动态顺序表：即使用动态开辟的数组存储。个人理解：我认为就是将一个用malloc动态空间的数组。可以比喻成一个可以添加车厢的火车，每当我们当前的车厢已满（存储空间已满），我们就给我们的火车加装车厢。

这一趟火车如果无法满足我们当前的载客量需求，我们可以给他加车厢，直到满足为止。其实我认为可以说两者就是静态数组和动态数组的差别。

应用场景：一般采用动态顺序表，因为静态顺序表的使用场景为已知固定大小，所以我们在实际情况中会使用动态顺序表。接下来，我们来完成一次动态顺序表的实现。

首次，我们创建一个工程，这个工程组成如下：源文件：SeqList.c和test.c   头文件：SeqList.h

SeqList.h：声明函数和应用库函数

SeqList.c：存放函数内容

test.c：调试内容

接下来，我们在SeqList.h中先构建一个结构体（SeqList）这个结构体由动态顺序表（array），顺序表当前存储数量：size还有顺序表当前最大存储量（capicity）构成，内容如下：

一个顺序表我们必须拥有的基本功能函数是顺序表的初始化，顺序表的尾插，顺序表的内存清理，为了检测我们当前的顺序表建立是否正常，我们还需要一个函数将我们顺序表的内容输出。由此我们可以构建出这几个函数：

我们先完成顺序表的初始化（SeqListInit ）：因为我们申请的是动态顺序表，所以我们的结构体中的2顺序表是一个数组指针，所以我们先将指针指向NULL，剩下的已经存储数量（size）和当前最大容量（capicity）我们直接赋值为0即可。

然后我们完成一下清空函数（SeqListDestory）：在内存中，我们需要将我们的动态顺序表的内容释放，然后将指针置为空，将我们的size和capicity变为0即可。这其中为了防止我们仅仅传输了一个未开辟的动态顺序表，我们使用一个if判断一下，满足条件我们才释放空间。

接下来，来到我们较为重要的尾插函数（SeqListPushBack）：我们尾插时，就是将我们顺序表的最后一位设置为我们添加的函数即可，并且将当前存储数量（size）增加，在这里我们就可以直接使用：psl  ->  array[ psl -> size ] 因为当前我们的size就是我们顺序表的最后一个位置。不光以上内容我们就可以完成，我们还需要判断我们的空间是否足够，这时我们后续可能还有函数需要使用的情况下，我们将空间判断写成一个功能函数：ChechCapicity。

在检查空间是否足够中，我们只需要将size和capicity对比即可，当我们的capicity与size相等，那么我们需要扩容。但是我们在初始化时，将capicity设置为0，所以我们还需要一个初始的空间大小来申请。

在这个函数中，我们初始申请空间为4，后续申请空间翻倍，每次使用realloc函数来申请空间。

在我们添加上判断内存是否充足函数（CheckCapicity）之后，我们的尾插函数其实也完成啦。

随即我们只剩下一个打印顺序表的函数（SeqListPrint）函数：打印顺序表，我们可以先定义一个size_t i 使它等于我们的size，然后使用一个while循环，每次i--，i = 0时打印完成即可。

完成上述的函数之后，我们可以先进行调试，我这里进行了4个数据的尾插查看我们的函数是否出现了问题，内容和结果如下：

在上述功能的完成且无误的情况下，我们来进行扩展功能函数。

我们添加一个尾删，头删，头插，查找，在固定位置插入x，删除固定位置的值

接下来，我们就根据上述图片的顺序来逐一完善我们的动态顺序表。

首先是尾删函数（SeqListPopBack）：我们仅仅需要将我们的size--即可，这样后续在尾部的修改会将值覆盖，我们不需要过多修改。

头插（SeqListPushFront)：因为这是一个顺序表，我们可以将我们全部数据从后往前，将数据后移1个单位，然后将首位数据覆盖即可。

头删（SeqListPopFront）：我们直接从顺序表下标为1的地方开始，将后续的数据将前面覆盖即可，然后将size--。

查找（SeqListFind）：我们使用while循环将顺序表遍历，当出现我们所寻找的值时，返回下标即可。

在pos位置插入数据（SeqListInsert）：我们先将pos之后的值全部后移一位，然后将数据直接赋值即可。

删除pos位置的值（SeqListErase）：我们直接将pos之后的所有值，向前覆盖即可，然后将

size--。

通过以上补充，我们就得到了一个动态的顺序表啦，大家在每一个函数写完后一定要调试一下，防止错误产生。

感谢您花费宝贵的时间观看，代码我放在下面啦，欢迎各位大佬指导修改！！！！

//SeqList.h
#pragma once
#include#include
#includetypedef int SLDataType;
typedef struct SeqList
{
	SLDataType* array;
	size_t size;
	size_t capicity;
}SeqList;
//初始化
void SeqListInit(SeqList* psl);
//内存清理
void SeqListDestory(SeqList* psl);
//尾插
void SeqListPushBack(SeqList* psl, SLDataType x);
//输出
void SeqListPrint(SeqList* psl);
//尾删
void SeqListPopBack(SeqList* psl);
//头插
void SeqListPushFront(SeqList* psl, SLDataType x);
//头删
void SeqListPopFront(SeqList* psl);
//查找
size_t SeqListFind(SeqList* psl, SLDataType x);
//在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
//删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos);

//SeqList.c
#define _CRT_SECURE_NO_WARNINGS
#include"SeqList.h"
//初始化
void SeqListInit(SeqList* psl)
{
	assert(psl);
	psl->array = NULL;
	psl->size = 0;
	psl->capicity = 0;
}
//清空
void SeqListDestory(SeqList* psl)
{
	assert(psl);
	if (psl->array != NULL)
	{
		free(psl->array);
		psl->array = NULL;
		psl->size = psl->capicity = 0;
	}
}
void ChechCapicity(SeqList* psl)
{
	if (psl->size == psl->capicity)
	{
		size_t newcapicity = psl->capicity == 0 ? 4 : psl->capicity * 2;
		SeqList* tmp = (SeqList*)realloc(psl->array, sizeof(SeqList) * newcapicity);
		if (tmp == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		psl->array = tmp;
		psl->capicity = newcapicity;
	}
}
//尾插
void SeqListPushBack(SeqList* psl, SLDataType x)
{
	assert(psl);
	ChechCapicity(psl);
	psl->array[psl->size] = x;
	psl->size++;
}
void SeqListPrint(SeqList* psl)
{
	assert(psl);
	SLDataType* data = psl->array;
	size_t i = psl->size;
	while (i > 0)
	{
		printf("%d -> ", *data);
		data++;
		i--;
	}
	printf("NULL\n");
}
//尾删
void SeqListPopBack(SeqList* psl)
{
	assert(psl);
	psl->size--;
}
//头插
void SeqListPushFront(SeqList* psl, SLDataType x)
{
	assert(psl);
	ChechCapicity(psl);
	size_t i = psl->size;
	while (i > 0)
	{
		SLDataType prev = psl->array[i - 1];
		psl->array[i] = prev;
		i--;
	}
	psl->array[0] = x;
	psl->size++;
}
//头删
void SeqListPopFront(SeqList* psl)
{
	assert(psl);
	int begin = 1;
	while (begin < psl->size)
	{
		psl->array[begin - 1] = psl->array[begin];
		++begin;
	}
	psl->size--;
}
//查找
size_t SeqListFind(SeqList* psl, SLDataType x)
{
	assert(psl);
	size_t tmp = 0;
	while (tmp < psl -> size)
	{
		if (psl->array[tmp] == x)
		{
			return tmp;
		}
		tmp++;
	}
	return -1;
}
//在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
	assert(psl);
	ChechCapicity(&psl);
	size_t i = psl->size;
	while (i >= pos)
	{
		SLDataType prev = psl->array[i - 1];
		psl->array[i] = prev;
		i--;
	}
	psl->array[pos] = x;
	psl->size++;
}
//删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos)
{
	assert(psl);
	while (pos < psl->size - 1)
	{
		psl->array[pos] = psl->array[pos + 1];
		pos++;
	}
	psl->size--;
}

//test.c
#define _CRT_SECURE_NO_WARNINGS
#include"SeqList.h"
void Test1()
{
	SeqList sl;
	SeqListInit(&sl);
	SeqListPushBack(&sl, 1);
	SeqListPushBack(&sl, 2);
	SeqListPushBack(&sl, 3);
	SeqListPushBack(&sl, 4);
	SeqListPrint(&sl);
	SeqListPopBack(&sl);
	SeqListPrint(&sl);
	SeqListDestory(&sl);
}
void Test2()
{
	SeqList sl;
	SeqListInit(&sl);
	SeqListPushBack(&sl, 1);
	SeqListPushBack(&sl, 2);
	SeqListPushBack(&sl, 3);
	SeqListPushBack(&sl, 4);
	SeqListPushFront(&sl, 5);
	SeqListPrint(&sl);
	SeqListPopFront(&sl);
	SeqListPrint(&sl);
	SeqListDestory(&sl);
}
void Test3()
{
	SeqList sl;
	SeqListInit(&sl);
	SeqListPushBack(&sl, 1);
	SeqListPushBack(&sl, 2);
	SeqListPushBack(&sl, 3);
	SeqListPushBack(&sl, 4);
	SeqListPrint(&sl);
	size_t pos = SeqListFind(&sl, 3);
	SeqListInsert(&sl, pos, 8);
	SeqListPrint(&sl);
	SeqListErase(&sl, pos);
	SeqListPrint(&sl);
	SeqListDestory(&sl);
}
int main()
{
	Test3();
	return 0;
}

test.c运行结果如图：