数据结构之顺序表-任意位置插入删除

「这是我参与2022首次更文挑战的第3天，活动详情查看：2022首次更文挑战」

2.8头删

注意:要考虑数组中是否还有元素可以被删除

头删：即把第二个元素往前覆盖

注意：要从前面开始往前覆盖！ 删除元素：size–

void SeqListPopFront(SeqList* ps)
{
	if (ps->size == 0)
	{
		printf("已经没有元素\n");
		return ;
	}
	int i = 0;
	for (i = 0; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i+1];
	}
	//写法2：
	//int begin = 1;
	//while (begin < ps->size)
	//{
	//	ps->a[begin - 1] = ps->a[begin];
	//	++begin;
	//}

	//写法3：
	//int begin = 0;
	//while (begin < ps->size-1)
	//{
	//	ps->a[begin] = ps->a[begin+1];
	//	++begin;
	//}

	ps->size--;	
}

2.9查找

遍历数组进行查找即可，如果数组是有序的，可以使用二分查找。如果找到了，返回对应下标，找不到返回-1

int SeqListFind(SeqList* ps, SLDateType x)
{
	//遍历查找
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
	}
	//找不到
	return -1;
}

2.10 pos位置插入

注意：插入要考虑容量是否足够的问题，还要考虑pos位置是否合法。pos位置可以在0位置插入，也可以在size位置插入(因为size标志的是成员个数，同时也是最后一个元素的下一个位置的下标) 插入后：size++

在pos位置插入：即把pos位置的数据往后移动

注意：要从后往前移动

void SeqListInsert(SeqList* ps, size_t pos, SLDateType x)
{
	//断言：如果括号内为真就无视，如果为假就报错
	//所以写成：assert(pos < 0 || pos >ps->size)是错误的

	//插入可以在size位置插入，因为size标识的是元素个数，指向的是数组最后一个元素的下一个位置
	assert(pos >= 0 && pos<=ps->size);
	CheckCapacity(ps);

	//写法1
	//int i = 0;
	////往后移动
	//for (i = ps->size-1 ; i > pos; i--)
	//{
	//	ps->a[i+1] = ps->a[i];
	//}
	//ps->a[pos] = x;
	//ps->size++;
	
	//写法2：
	int i =ps->size ;
	while (i > pos)
	{
		ps->a[i] = ps->a[i-1];
		i--;
	}
	ps->size++;
	ps->a[pos] = x;
}

头插尾插的写法：

头插：即在0位置插入

尾插：即在size-1位置插入

头插：SeqListInsert(ps, 0, x);
尾插：SeqListInsert(ps,ps->size - 1,x)

2.11pos位置删除

注意：删除也要保证位置的合法性 删除后，size–

在pos位置删除，即把pos后面的数据向前覆盖。

从前往后移动(先移动pos+1位置的数据往前覆盖)

void SeqListErase(SeqList* ps, size_t pos)
{
	//此时pos不可以为size，
	//因为size标识的是元素个数，指向的是数组最后一个元素的下一个位置，这个位置没有存元素，不可以删除
	assert(pos >= 0 && pos < ps->size);
	int i = 0;
	for (i = pos; i < ps->size -1; i++)
	{
		ps->a[i] = ps->a[i+1];
	}
    /*
	//写法2：
	int begin = pos + 1;
	while (begin < ps->size)
	{
		ps->a[begin-1] = ps->a[begin];
		begin++;
	}
	*/
	ps->size--;
}

头删尾删的写法

头删：SeqListErase(ps,0)
尾删：SeqListErase(ps, ps->size - 1);

2.12销毁

因为数组指向的空间是动态开辟的，所以结束时要把空间销毁，防止内存泄漏。

销毁之后要把指针置空！！防止造成野指针

void SeqListDestory(SeqList* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

注意事项

插入元素考虑因素：

整个顺序表空间是否满了，满了则扩容，插入之后size要++

头插：从后往前移动(先移动最后的数据)

尾插：直接插入到size位置

删除元素考虑因素

是否还有元素可以被删除，删除元素之后size–

头删：从前往后移动(先移动前面的数据进行覆盖)

尾删：直接size–即可

写的时候遇到的坑点：

//在pos位置插入
//错误写法：
void SeqListInsert(SeqList* ps, size_t pos, SLDateType x)
{
	assert(pos >= 0 && pos<=ps->size);
	CheckCapacity(ps);
	//写法1
	//int i = 0;
	////往后移动
	//for (i = ps->size-1 ; i >= pos; i--)
	//{
	//	ps->a[i+1] = ps->a[i];
	//}
	//ps->a[pos] = x;
	//ps->size++;
	
	//写法2：
	int i =ps->size -1 ;
	while (i >= pos)
	{
		ps->a[i+1] = ps->a[i];
		i--;
	}
	ps->size++;
	ps->a[pos] = x;
}

错误原因：pos是size_t类型，无符号整形。i为整形

pos和i进行比较时，i会提升为无符号整形，即i的范围为：[0,2147483 648]，i恒大于0.所以若在pos = 0位置插入，则 i>=pos恒成立，会造成死循环。

pos为其他正数值的时候不会发生，因为i的返回时[0,2^31]，i终究会变到小于pos的值跳出循环！！，但是若pos为0，则i>=pos恒满足，死循环。所以这是个很隐藏的错误，

即使i也定义为无符号整形也是如此

i和pos进行比较不能取相等！！！防止出现pos位置取0的情况！

//正确写法：
void SeqListInsert(SeqList* ps, size_t pos, SLDateType x)
{
	//断言：如果括号内为真就无视，如果为假就报错
	//所以写成：assert(pos < 0 || pos >ps->size)是错误的

	//插入可以在size位置插入，因为size标识的是元素个数，指向的是数组最后一个元素的下一个位置
	assert(pos >= 0 && pos<=ps->size);
	CheckCapacity(ps);

	//写法1
	//int i = 0;
	////往后移动
	//for (i = ps->size-1 ; i > pos; i--)
	//{
	//	ps->a[i+1] = ps->a[i];
	//}
	//ps->a[pos] = x;
	//ps->size++;
	
	//写法2：
	int i =ps->size ;
	while (i > pos)
	{
		ps->a[i] = ps->a[i-1];
		i--;
	}
	ps->size++;
	ps->a[pos] = x;
}

同理在pos位置删除时，i和pos比较也不能取等号