顺序表的增删查改

一 前言

顺序表是数据结构的一种。本质上是数组。因为他在内存中是连续的，数据也是连续存放的。下面对这一种数据结构进行增删查改。

我们先创建一个动态的数组，便于存放数据。动态数组可以避免因容量不够频繁增容，也可以减少容量的浪费。

typedef int SLDataType;
typedef struct slist
{
	SLDataType*a;
	int size;
	int capacity;
}SL;

由于顺序表存放数据的类型未知，因此先假设这一个顺序表是用来存放int类型的数据的。

二 尾插

尾插的基本思想：尾插就是在数组尾部。下标为size的位置插入一个数据。但是插入数据的时候，如果数组已经满了，那么就需要对数组进行扩容再来存放数据。

数组的扩容:一般扩容当前容量的两倍。由于初始化的时候将数组的容量初始化成了0，因此需要考虑到的是，如果是第一次扩容，扩容两杯就没有意义。因此需要对数组容量为0这一种情况来单独进行考虑。

需要注意的是，由于数据已经存放在了数组里面，因此数组中存放数据的个数size就会变化。

尾插的图解：

 

void SlistCapacityCheck(SL* ps)
{
	assert(ps);

	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newcapacity);
		assert(tmp);
		ps->capacity = newcapacity;
		ps->a = tmp;
	}
}

void SlistBackPush(SL* ps, SLDataType data)
{
	assert(ps);

	SlistCapacityCheck(ps);

	ps->a[ps->size] = data;
	ps->size++;
}

三 尾删

尾删的基本思想：尾删有以下几种设想：

①将尾部的位置的数据修改成其他的数字。但是这样无法与之前有可能保存的数据相区分。

②将存放数据的数组中size--，直接舍去最后一个数据。

尾插的图解：

 

尾插的实现 

void SlistBackPop(SL* ps)
{
	assert(ps);
	assert(ps->size);

	ps->size--;
}

四 头插

头插的基本思想：先将原先数组中的数据，从size-1到0的位置（从后往前）依次挪动一个数据。

如果是从前往后进行挪动的话，挪动过去的数据会覆盖将要挪动的数据。

之后数组的0的位置就会多出一个空位，把所需的数据插入即可。

需要注意的是，插入数据都需要考虑容量问题！

图解：

 

实现

void SlistFrontPush(SL* ps, SLDataType data)
{
	assert(ps);

	SlistCapacityCheck(ps);

	int i = 0;
	for (i = ps->size; i >0; i--)
	{
		ps->a[i] = ps->a[i - 1];
	}

	ps->a[0] = data;
	ps->size++;
}

 

五 头删

基本思想：头删的话从1开始到size-1位置的数据（从前往后）依次往前挪动一个数据的大小，这样就可以覆盖掉第一个数据，并且保证之后存储的数据不会被覆盖掉

需要注意的是，如果数组已经为空了就不能再继续删除了，否则之后 插入的数据是之前被删除的位置，无法插入了。

图解：

 

实现：

void SlistFrontPop(SL* ps)
{
	assert(ps);
	assert(ps->size);

	int i = 0;
	for (i = 1; i < ps->size; i++)
	{
		ps->a[i - 1] = ps->a[i];
	}

	ps->size--;
}

六 在特定位置插入

基本思想：基本思想其实和头插差不多，也是需要挪动数据空出位置之后再在这个位置将数据插入。

从size-1到pos的位置的数据，全部往后挪动一个位置，之后插入。

其实在特定位置插入数据的操作可以复用成头插（当特定位置是数组第一个位置的时候）也可以复用成尾插（当特定位置是数组最后一个位置的时候）

实现：

void SlistPosInsert(SL* ps, SLDataType data,int pos)
{
	assert(ps);
	SlistCapacityCheck(ps);

	int i = 0;
	for (i = ps->size; i > pos; i--)
	{
		ps->a[i] = ps->a[i - 1];
	}

	ps->a[pos] = data;
	ps->size++;
}

七 在特定位置删除

道理同上。

代码实现：

void SlistPosPop(SL* ps, int pos)
{
	assert(ps);
	assert(ps->size);
	assert(pos >= 0 && pos < ps->size);

	int i = 0;
	for (i = pos  ; i < ps->size; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}

	ps->size--;
}

如果是在头部或者尾部操作，也可以复用成头删和尾删。

需要注意的是，对于特定位置的插入和修改，该位置必须在数组里。

八 顺序表的查找

基本思想：遍历查找

int SlistFind(SL* ps, SLDataType data)
{
	assert(ps);

	int i = 0;
	while (i < ps->size)
	{
		if (ps->a[i] != data)
		{
			i++;
		}
		else
		{
			return i;
		}
	}
	return -1;
}

九顺序表特定位置的修改

void SlistModify(SL* ps, SLDataType data, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);

	ps->a[pos] = data;
}

十 总结

顺序表的尾插和尾删的效率比较高。

但是顺序表存在空间的浪费或者频繁扩容。