顺序表的增删查改（数据结构）

你好，我是史丰源
欢迎你的来访，希望我的博客能给你带来一些帮助。

我的Gitee：代码仓库.☀️

我的联系方式：
QQ：1756786195
邮箱：Marksky126@outlook.com

今天我们来学习顺序表的基本操作：
增删查改

头文件

#pragma once

#include
#include
#include
//创建顺序表

#define ElemType int//顺序不要反了

typedef struct SeqList
{
	ElemType* data;//指向动态开辟的数组
	unsigned int size;//顺序表的大小
	unsigned int Capacity;//扩容使用
}SeqList;

void SeqListInit(SeqList* ps);//初始化顺序表
void SeqListDestroy(SeqList* ps);//销毁顺序表
void PushfrontSeqList(SeqList *ps,ElemType x);//头插
void PopfrontSeqList(SeqList *ps);//头删
void PushBack(SeqList *ps,ElemType x);//尾插
void PopBack(SeqList *ps);//尾删
void SeqListFind(SeqList* ps);//按值查找
void SeqListInsert(SeqList* ps, unsigned int pos, ElemType x);
//按位置插入

void SeqListDelete(SeqList* ps, unsigned int pos, ElemType x);
//按位置删除

如下图所示，在需要修改顺序表中的值时需要使用指针，去取需要修改值的地址。
因为形参只是实参的一份临时拷贝，子函数结束形参自动销毁


我们创建并且初始化了顺序表，接下来我们就需要进行顺序表的增删查改操作。
在操作之前，我们会去检查顺序表的空间是否足够：

void CheckSeqList(SeqList* ps)//检查空间是否足够.
{
	int newCapcity = ps->Capacity == 0 ? 4 : ps->Capacity * 2;//以防Capacity为0;
	ElemType* newnode = (ElemType*)realloc(ps->data,sizeof(ElemType));//为数据空间扩容
	if (ps->size == ps->Capacity)
	{
		if (newnode == NULL)
		{
			perror("realloc::");
			return;
		}

		ps->data = newnode;
		ps->Capacity = newCapcity;
	}
}

顺序表的一个缺点就是：在头部删除/增加一个元素后，需要挪动原有的元素

头插：

void PushfrontSeqList(SeqList* ps, ElemType x)
{
	assert(ps);
	CheckSeqList(ps);
	int end = ps->size-1;
	
	while (end>=0)
	{
		ps->data[end + 1] = ps->data[end];//挪动数据
		end--;
	}
	ps->data[0] = x;//执行插入操作
	ps->size++;
}

头删:

void PopfrontSeqList(SeqList* ps)//头删
{
	assert(ps);
	//int end = ps->size - 1;
	//while (end > 0)
	//{
	//	ps->data[end] = ps->data[end + 1];//不能从后往前挪

	//}
	//ps->size--;
	int begin = 1;
	while (begin < ps->size)
	{
		ps->data[begin-1] = ps->data[begin];//要从1开始挪动，而不是从0；从后往前
	 	begin++;
	}
	ps->size--;
}

上图为头删注释部分代码的演示图，故我们不能从最后一个挪动元素至第一个。

通过上图，我们可以看到头删是从下标为1的地方，将后方的数据依次往前移动，实现了对需要删除的元素的覆盖。

尾插：

void PushBackSeqList(SeqList* ps, ElemType x)
{
	assert(ps);
	CheckSeqList(ps);
	//找到最后一个位置
	ps->data[ps->size] = x;
	ps->size++;
}

尾删：
大家可能会想用一个数字去代替被删除的那个数，但是顺序表中的数据每个数字都可能出现，所以这个方案不可行
最简单的方法就是直接让顺序表的长度减1.

void PopBack(SeqList* ps)
{
	assert(ps->size>0);
	ps->size--;
}

void SeqListInsert(SeqList* ps, unsigned int pos, ElemType x)//插入操作
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	CheckSeqList(ps);
	int end = ps->size - 1;

	while (end >= pos)
	{
		ps->data[end + 1] = ps->data[end];//元素后移
		--end;
	}
	ps->data[pos] = x;
	ps->size++;
}

void SeqListDelete(SeqList* ps, unsigned int pos, ElemType x)//删除操作
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	CheckSeqList(ps);
	int begin = pos-1;
	while (beginsize)
	{
		ps->data[begin - 1] = ps->data[begin];//中间差2个元素，跳过pos
		begin++;
	}
	ps->size--;

}

可以从上述代码观察到，头插与头删的挪动操作在这里被复用。
以上就是顺序表的增删查改，顺序表最麻烦的地方就是挪动数据，而接下来学习的链表就可以完美地解决这个问题。