剖析：顺序表的增删改查

//扩容函数
void SeqListCheckCapacity(SL* pc)
{
	//判断顺序表是否满
	if (pc->size == pc->capacity)
	{
		//三目操作符：表达式1？表达式2:表达式3
		//判断是否为空
		int newcapacity = (pc->capacity == 0) ? 3 : pc->capacity * 2;
		SLDataType* ps = (SLDataType*)realloc(pc->arr, newcapacity * sizeof(SLDataType));
		if (NULL == ps)
		{
			printf("realloc is failed");
			exit(-1);//异常退出，不同于return
		}
		pc->arr = ps;
		pc->capacity = newcapacity;
	}
}

如上代码所示，当之后我们需要在顺序表中新增空间时，如果当 size和capaticy 一样大时，说明当前顺序表要么没有一个空间，要么当前的空间已经满了，需要新增空间然后存放数据了。

这里需要注意的有两个方面：

首先是，realloc增容，因为realloc的特性，我们需要改函数来每次追加空间或者开辟新空间（如有小伙伴对于动态内存开辟相关内容不熟悉的话可以移步up主动态内存开辟的文章哦！）。一般情况下，我们会开辟原空间的两倍大小为新空间。

当然，最后一定不能忘记的是，当使用完顺序表之后，一定要将开辟的空间释放哦！！！

2.3增加元素

//头插入
void SeqListFrontPush(SL* pc, SLDataType x)
{
	assert(pc);
	SeqListCheckCapacity(pc);
	//插入
	int end = pc->size;
	while (end--)
	{
		pc->arr[end + 1] = pc->arr[end];
	}
	pc->arr[0] = x;
	pc->size++;
}

//尾插入
void SeqListBackPush(SL* pc, SLDataType z)
{
	assert(pc);
	SeqListCheckCapacity(pc);
	pc->arr[pc->size] = z;
	pc->size++;
}

那么首先，插入有三种方式，这里我们先了解两种，分别为头插和尾插。也就是说一个在顺序表的头部一次插入，一个是在尾部一次插入元素。

头插：首先对于头插，我们需要判断顺序表是否是满的，如果当前开辟的空间已经用完了，就需要使用 realloc 开辟新空间。然后因为对于数组而言，如果想进行头插的话，就需要将所有元素先往后移动一位，然后再将新元素插入，否则原有第一个元素将会被覆盖。然后，我们需要将计数成员size加一。

尾插：那么对于尾插是不需要移动元素的，因为尾巴上插入内容不会影响前面元素。所以我们只需要在最后一个位置上插入即可。

2.4删除元素

//头删除
void SeqListFrontPoP(SL* pc, SLDataType y)
{
	assert(pc && pc->size > 0);
	if (y > pc->size)
	{
		printf("删除元素个数错误\n");
		SeqListClosePs(pc);
		exit(-1);
	}
	else
	{
		int i = 0;
		for (i = 0; i < pc->size - y; i++)
		{
			pc->arr[i] = pc->arr[i + y];
		}
		pc->size -= y;
	}
}

//尾删除
void SeqListBackPoP(SL* pc, SLDataType i)
{
	//有元素才能删
	assert(pc && pc->size > 0);
	//应该有一个判断，删除过量？
	if (i > pc->size)
	{
		printf("删除错误\n");
	}
	else
		pc->size -= i;
}

这里我们没有一个一个的删除，而是根据传递的参数 SLDataType 的值来决定删除几个元素，但是大概实现都是一样的。

首先是头删，因为删除个的个数 y 是确定的，所以我们可以知道首元素和接下来的每个元素应该待的位置的间距一定是 y ，就相当于删除几个元素，每个元素就往前移动几位。所以将剩余元素一次往前移动 y 位，最后再将size减去 y ，便是最后结果了。

尾删的话，就更加简单了，因为不需要移动元素，所以只是将现有元素个数减去需要删除的元素个数即可。

2.5查找元素

如上图所示，查找相对来说是比较简单的，这里我们不做过多赘述。

2.6指定位置元素的插入和删除

2.6.1指定位置元素的插入

//在指定pos位置添加指定数字
//假定x值为整型数
void SeqListInsert(SL* pc, int pos, SLDataType x)
{
	assert(pc && x < INT_MAX && x >INT_MIN);
	SeqListCheckCapacity(pc);
	int tmp = pc->size-1;
	while (tmp >= pos)
	{
		pc->arr[tmp+1] = pc->arr[tmp];
		tmp--;
	}
	pc->arr[pos] = x;
	pc->size++;
}

如上所示，在经过断言以及增容函数的检查之后，用 tmp 记住当前最后一个元素的下标，然后将 pos 位置以及之后的元素全部往后移动一位，最后再将 x 插入当前 pos 位置。最后再将计数个数size增加一位。

这里需要我们注意的是，对于顺序表而言，元素个数一定不等于元素下标，在实际使用的时候，必须要注意区分。

那么我们发现，其实任意位置的插入也可以适用于头插和尾插，所以这里的认为位置插入就是我们的第三种万能插入方法。我们只需要对插入的位置进行适当的调整，最后插入即可。

2.6.2指定位置元素的删除

根据上面的插入函数，对于任意位置的删除其实也是很方便的。只是我们需要先检查要删除的元素是不是当前顺序表中存在的元素。然后再将 pos 位置后面的元素依次往前移动一位即可。此 pos 位置元素被覆盖掉，也就完成了我们对于该位置元素的删除。

那么我们也知道，任意位置的删除同样适用于头删和尾删。那么此时就将便利许多。

好的，那么关于顺序表，我们就了解这么多，如有问题，还请小伙伴们指正呀！！！

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构

c语言