[数据结构与算法][数据结构]——顺序表详解（增，删，查，改）

1.什么是顺序表

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

2.顺序表的接口实现

void SeqLstInit(s* ps); /*初始化*/

void DestorySeqList(s* ps);/* 销毁数据*/

void PrintSeqList(s* ps); /*打印数据*/

void CheckSeqList(s* ps); /*检查空间容量*/

void PushBck(s* ps, SeqListdatatype x);  /*尾部增加数据*/

void PushFront(s* ps, SeqListdatatype x); /*头部插入数据*/

void PopBackSeqList(s* ps); /*尾部删除数据*/

void PopFrontSeqList(s* ps); /*头部删除数据*/

int FindSeqList(s* ps,SeqListdatatype x); /*查找数据*/

void InsertSeqList(s* ps,size_t pos,SeqListdatatype x); /*在pos位置插入数据*/

void EraseSeqList(s* ps, size_t pos);  /*在pos位置删除数据*/

1）顺序表的初始化

顺序表的初始化，一般情况下采用数组存储，这样构成一个静态顺序表，而静态1只适用于确定知道需要存多少数据的场景，静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

typedef int SeqListdatatype;
typedef struct S
{
	SeqListdatatype* pc; /*用来存放数据的*/
	int count; /*数据的个数*/
	int capacity; /*容量的大小*/
}s;

通过指针和动态内存管理的使用，从而实现动态的顺序表功能

2）尾部插入数据

void PushBck(s* ps, SeqListdatatype x)
{
	assert(ps);
	/*检查空间容量*/
	if (ps->count == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SeqListdatatype* tmp=(SeqListdatatype*)realloc(ps->capacity,newcapacity*sizeof(SeqListdatatype));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		ps->pc = tmp;
		ps->capacity = newcapacity;
	}
	ps->pc[ps->count] = x;
	ps->count++;
}

在实现这一功能接口时，我们需要注意在增加数据之前，数组是否有足够的空间，所以我们需要进行一个检查空间容量的操作并进行相对应的扩容，我们可以将这一系列操作封装为一个新的接口。

void CheckSeqList(s* ps)
{
	assert(ps);
	/*检查空间容量*/
	if (ps->count == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		int* tmp = realloc(ps->capacity, newcapacity * sizeof(SeqListdatatype));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		ps->pc = tmp;
		ps->capacity = newcapacity;
	}
}

这一部分代码就是 3）检查空间容量 接口。

3）检查空间容量

上文所述。

4）头部插入数据

void PushFront(s* ps, SeqListdatatype x)
{
	assert(ps);
	CheckSeqList(ps);
	int end = ps->count - 1;
	while (end >= 0)
	{
		ps->pc[ps->count+1] = ps->pc[ps->count];
		end--;
	}
	ps->pc[0] = x;
	ps->count++;
}

头部插入的原理，检查空间容量是否足够，并进行扩容操作，然后就所有的数据向后依次挪动一位，最后将新数据放在头部

5）尾部删除数据

void PopBackSeqList(s* ps)
{
	assert(ps);
	ps->count--;
}

6）头部删除数据

void PopFrontSeqList(s* ps)
{
	assert(ps);
	int end = ps->count - 1;
	while (end >= 0)
	{
		ps->pc[ps->count] = ps->pc[ps->count + 1];
		end--;
	}
	ps->count--;
	ps->capacity--;
}

7）查找某个数据

int FindSeqList(s* ps,SeqListdatatype x)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->count; i++)
	{
		if (x == ps->pc[i])
			return i;
	}
}

8）在pos位置插入数据

void InsertSeqList(s* ps, size_t pos, SeqListdatatype x)
{
	assert(ps);
	assert(pos <= ps->count);
	CheckSeqList(ps);
	size_t end = ps->count;
	while (end > pos)
	{
		ps->pc[end] = ps->pc[end - 1];
		--end;
	}
	ps->pc[pos] = x;
	++ps->count;
}

9）在pos位置删除数据

void EraseSeqList(s* ps, size_t pos)
{
	assert(ps);
	assert(pos < ps->count);
	size_t begin = pos;
	while (begin < ps->count - 1)
	{
		ps->pc[begin] = ps->pc[begin + 1];
		++begin;
	}
	ps->count--;
}

10）打印顺序表

void PrintSeqList(s* ps)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->count; i++)
	{
		printf("%d", ps->pc[i]);
	}
	printf("\n");
}

11）销毁顺序表

void DestroySeqList(s* ps)
{
	assert(ps);
	free(ps);
	ps->pc = NULL;
	ps->capacity = 0;
	ps->count = 0;
}

11）销毁顺序表

void DestroySeqList(s* ps)
{
	assert(ps);
	free(ps);
	ps->pc = NULL;
	ps->capacity = 0;
	ps->count = 0;
}