[C++知识库]利用c语言实现顺序表的增删改查

顺序表(物理结构和逻辑结构均是连续的)（类似于封装数组）
特点：
1、可动态增长的数组
2、数据在数组中的存储是连续的

缺点：
中间插入或删除的效率较慢，需挪动数据，时间复杂度是O(N)。
空加不够增容会造成一定程度的空间浪费。

优点：
可以随机访问！！利好排序查找等操作。
缓存利用率较高！

基本结构：

typedef struct SeqList
{
	SLDataType *a;
	int size;//有效数据的个数
	int capicity;//容量空间大小（不够可以扩容——动态）
}SL, SeqList;

注：（这里的SLDataType是宏定义类型，由于顺序表中可能存储不同类型的数据，同时也方便维护，故采用宏定义的类型来定义）

编程思想：

1、主要方法

顺序表类似于数组，所以我们可以借助数组并加以可动态扩容的行为来完成顺序表的构建，所以可以利用C语言自带的动态分配空间来实现动态扩容。

2、初始化

顺序表是一种特殊的数据类型，根据定义我们不难发现它包括一个数组、数据的个数、当前的容量这三个基本特征，所以需要利用结构体进行说明。代码如下：

typedef struct SeqList
{
	SLDataType *a;
	int size;//有效数据的个数
	int capicity;//容量空间大小（不够可以扩容——动态）
}SL, SeqList;

注：由于不能确定数组大小，故利用指针来进行维护数组。

3、插入数据

首先插入数据之前，我们应当考虑当前顺序表的容量是否够我们插入数据，如果不够的话我们需要对其进行扩容操作。而扩容操作需要借助C语言自带的扩容函数（将原空间扩大两倍），扩容编程如下：

void SeqListCheckCapacity(SL* ps)//检查是否需要扩容函数，凡是插入操作的都要考虑扩容！
{
	if (ps->size >= ps->capicity)//如果满了需要增容
	{
		ps->a = (SLDataType*)realloc(ps->a, (SLDataType*)malloc(sizeof(SLDataType) * ps->capicity));//c语言自带扩容函数，需要地址和扩容大小两个参数
		if (ps == NULL)
		{
			printf("扩容失败！\n");
			exit(-1);
		}
	}
}

其次我们需要知道当前数据往哪插，跟据顺序表的定义不难发现能够插入的位置无非就是头部插入、尾部插入和中间任意位置插入。

头插入：

在一个顺序表的头部插入一个数据（a[0]位置处插入数据）首先我们需要判断当前顺序表容量是否够用如果不够用需要进行扩容（凡是插入数据都需要判断是否要扩容），其次如果只是简单的将第一位数据换成当前插入的值，那么原先存在第一位的值会消失，不符合实际应用。所以，我们只能先将每一位数据向后移，使得在保证原数据不被改动的条件下插入数据到第一位。

代码如下

void SeqListPushFront(SL* ps, SLDataType x)//顺序表头插入函数
{
	int end = ps->size - 1;
	if (ps == NULL)
	{
		printf("结构体传参错误！\n");
		exit(-1);
	}
	SeqListCheckCapacity(ps);//如果满了需要增容
	while (end >= 0)//顺序表中每一位数据向后移
	{
		ps->a[end + 1] = ps->a[end];
		--end;
	}
	ps->a[0] = x;
	ps->size++;
}

尾插入：

尾插入相对来说比较简单，由于顺序表结构中有表征当前顺序表有多少数据的变量size，所以我们只需找到最后一位数据然后在其后一位插入即可。

代码如下：

void SeqListPushBack(SL* ps, SLDataType x)//顺序尾插函数
{
	if (ps == NULL)
	{
		printf("结构体传参错误！\n");
		exit(-1);
	}
	SeqListCheckCapacity(ps);//如果满了需要增容
	ps->a[ps->size] = x;
	ps->size++;//有效数字+1
	
}

中间任意位置插入：

顺序表的任意位置插入较为快速，只需要知道插入位置的下标就可轻松插入数据，类似于头插入，要保证数据不会被改变，则需要在插入位置处的后面每一位数据都向后移。

代码如下：

void SeqListInsert(SL* ps, int pos, SLDataType x)//任意位置插入函数
{
	if (ps == NULL||pos < 0)
	{
		printf("传参错误！\n");
		exit(-1);
	}
	SeqListCheckCapacity(ps);//如果满了需要增容
	int tmp=ps->size;
	while (tmp > pos)
	{
		ps->a[tmp] = ps->a[tmp-1];
		tmp--;
	}
	ps->a[pos] = x;
	ps->size++;
}

4、删除数据

首先，顺序表中的删除是指将原数据使用新的数据覆盖掉，而不是单纯的把数据改为0，而为了保证顺序表的连贯性，故我们需要将每一位数据向前移动，并且每删除一个数据都要将长度减一。

对应插入，删除的位置无非就是头删除，尾删除，和中间任意位置删除。

头删：对应头插入，首先找到头的位置，然后将数据一次向前移一位即可完成头删除操作。

代码如下：

void SeqListPopFront(SL* ps)//顺序表头删除函数
{
	int start = 0;
	while (start < ps->size - 1)
	{
		ps->a[start] = ps->a[start+1];
		start++;
	}
	ps->size--;
}

尾删除：

在顺序表中，尾删除的操作较为简单，只需要把表征顺序表元素个数的变量减去一，即可使数组无法利用元素个数变量找到最后一个元素，即完成尾删除。

代码如下：

void SeqListPopBack(SL* ps)//顺序表尾删函数
{
	if (ps == NULL)
	{
		printf("无法找到顺序表\n");
		exit(-1);
	}
	ps->size--;
}

任意位置删除：

顺序表的任意位置删除比较简单，只需考虑三个位置，若给的位置为头，则直接调用头删除函数，若给的位置在尾部，则直接利用尾删除函数，但若给的位置在中间的话，我们只需要将删除位置其后的元素依次向前移动一位即可删除这个位置的元素。

代码如下：

void SeqListErase(SL* ps, int pos)//任意位置删除函数
{
	int tmp=pos;
	while (tmp<ps->size)
	{
		if (pos == 0)
		{
			SeqListPopFront(ps);
			break;
		}
		else
		{
			ps->a[tmp] = ps->a[tmp+1];
			tmp++;
			if (tmp == ps->size - 1)
			{
				SeqListPopBack(ps);
			}
		}
	}
}

5、查找数据

查找数据，首先要提供查找的数据是什么，其次我们需要明确，当在顺序表中查找到数据后返回的是当前数据在顺序表中的下标，在这里由于可能会有重复的数据所以我利用数组来接收下标并通过指针返回到调用处。代码如下：

SLDataType * SeqListLocate(SL* ps, SLDataType x)//顺序表查找函数
{
	int i = 0;
	int p = 0;
	SLDataType b[100] = { 0 };
	for (i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			b[p++]=i;
		}
	}
	if (p != 0)
	{
		return b;
	}
	if (p == 0)
	{
		return -1;
	}

6、改数据

对比与其他数据结构，顺序表的改数据就十分简单了。我们只需要在数组中找到提供的位置处的数组元素，直接修改即可。代码略。

至此，顺序表的增删改查原理及代码提供完毕，限编者水平有限，代码可能存在少许问题，时间匆忙，未能在代码中充足注释。

才疏学浅，仍需一赞!