数据结构-顺序表_顺序结构表

目录

一、顺序表介绍

1.1 静态顺序表

1.2 动态顺序表 

二、顺序表的功能实现 

2.1 顺序表的定义

2.2 顺序表的初始化

2.3 顺序表的增与删

2.4 顺序表查询

2.5 顺序表的插入与删除

三、顺序表的优劣

3.1 优势

3.2 劣势

四、代码展示：

顺序表是我们最熟悉不过的数组所组成的存储单元连续的线性结构，它简单而且容易理解，让我们来see see它是如何实现的。

一、顺序表介绍

顺序表可以分为：静态顺序表与动态顺序表

1.1 静态顺序表

静态顺序表就是数据存储的空间大小在一开始初始化的时候就定好了，后面运行后不能随意增加或缩小，当你不清楚所需存储数据多少的时候不建议使用，如果给太大就会浪费、太小又不能够存储完，但是如果一开始就知道所需空间大小，静态顺序表就会做到刚好不浪费空间。

1.2 动态顺序表

动态顺序表则是将数据存储的空间变成可以任意改变的，而不是死板、固定的一块空间，他的空间改变之后任然回事连续的、不会影响其特点，因此当你不了解数据的大小时，选择动态绝对错不了、它方便而且节省空间。

二、顺序表的功能实现

2.1 顺序表的定义

 此顺序表采用的是动态定义的方法，我们需要将初始化中自己创建在堆上的动态空间传给指针变量a、用a访问空间存储所需数据，而size就代表我们所存储数据的个数，capacity表示顺序表的动态空间大小；最上面的宏定义表示初始化容量设定，typedef定义的类型表示所存数据类型。

2.2 顺序表的初始化

初始化显而易见，需要将顺序表里面的成员都赋予初值以便后面使用，我们只需将每个成员一个一个赋值即可。

 注意：断言是为了用户使用初始化函数传参传错时的一个暴力检测，我们所传的顺序表地址一定不会为空。

因为是动态开辟的，我们需要使用的库函数malloc来开辟一个堆上的空间，大小由INITCAPACITY确定，顺序表还没有存数据size赋值0，capacity就给予初始顺序表空间即可。

2.3 顺序表的增与删

我们所需要注意的就是在增加数据时检查顺序表空间是否足够，在删除数据时顺序表内是否存在数据。

删除数据我们只需要将size本身自减1即可；增加数据就相对繁琐一些、先判断在从尾部加入所需要的数据，在存储空间不够时我们扩展空间所使用的库函数为realloc，它能够为我们在堆上重建一块空间或者在原空间后增加一段大小。我们不用害怕重建空间时数据丢失，realloc会为我们自动将原数据复制到新的空间上。

2.4 顺序表查询

此功能实现非常简单我们只需要遍历一下顺序表查找所需数据是否存在即可，返回值为所查找元素的下标，如果没有就返回-1。

2.5 顺序表的插入与删除

对于顺序表插入与删除功能我们需要配合查找功能来使用，具体操作如下：

在数据X前插入数据data

删除数据x：

 在插入或删除时多数情况下我们需要将数据先移动，在进行操作代码量相对其它功能较为复杂一点，配合着我们的查找功能实现两个函数。

2.6顺序表的打印与销毁

我们在开辟动态空间时是在堆上申请的，因此用完后一定要将内存还给堆系统，如果不还会形成内存泄露，这是非常可怕的。

  

我们需要养成一个申请了动态内存就要释放的好习惯！！！

三、顺序表的优劣

3.1 优势

顺序表最大的优势就是他的存储空间时连续的，这是其他数据结构做不到的；它访问数据也非常方便，只需要知道其下表即可，不用将数组遍历一次。

3.2 劣势

顺序表在插入和删除数据时非常不方便，需要挪动数据十分麻烦时间消耗很大。

四、代码展示：

void SListInit(SLT* pst)
{
	assert(pst);
	//给顺序表开辟一个动态空间存放数据
	pst->a = (SLTDataType*)malloc(sizeof(SLTDataType) * INITCAPACITY);
	if (pst->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	pst->size = 0;
	pst->capacity = INITCAPACITY;
 
}
 
 
void SLTPush(SLT* pst, SLTDataType x)
{
	assert(pst);
	if (pst->size == pst->capacity)
	{
		SLTDataType* tmp = (SLTDataType*)realloc(pst->a, sizeof(SLTDataType) * pst->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		pst->a = tmp;
		pst->capacity *= 2;
	}
	pst->a[pst->size] = x;
	pst->size++;
}
 
void SLTPop(SLT* pst)
{
	assert(pst);
	assert(pst->size);
	pst->size--;
}
 
int SLTFind(SLT* pst, SLTDataType x)
{
	assert(pst);
	int i = 0;
	for (i = 0; i < pst->size; i++)
	{
		if (pst->a[i] == x)
			return i;
	}
	printf("没有此数据\n");
	return -1;
}
 
void SLTInsert(SLT* pst, SLTDataType x, SLTDataType data)
{
	assert(pst);
	if (pst->size == pst->capacity)
	{
		SLTDataType* tmp = (SLTDataType*)realloc(pst->a, sizeof(SLTDataType) * pst->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		pst->a = tmp;
		pst->capacity *= 2;
	}
	int ret = SLTFind(pst, x);
	if ( ret == -1)
		return;
	int end = pst->size - 1;
	while (end >= ret)
	{
		pst->a[end + 1] = pst->a[end];
		end--;
	}
	pst->a[end + 1] = data;
	pst->size++;
}
 
void SLTErase(SLT* pst, SLTDataType x)
{
	assert(pst);
	int ret = SLTFind(pst, x);
	if (ret == -1)
		return;
	while (ret < pst->size - 1)
	{
		pst->a[ret] = pst->a[ret + 1];
		ret++;
	}
	pst->size--;
}
 
void SLTPrint(SLT* pst)
{
	assert(pst);
	int i = 0;
	for (i = 0; i < pst->size; i++)
	{
		printf("%d ", pst->a[i]);
	}
	printf("\n");
}
 
//顺序表销毁
void SLTDestroy(SLT* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->capacity = pst->size = 0;
}