顺序表的实现（增删查改）

一，顺序表的定义

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

二，顺序表的结构

顺序表一般可以分为：

1. 静态顺序表：使用定长数组存储元素。
2. 动态顺序表：使用动态开辟的数组存储。
   当然我们构建顺序表的时候一般采用动态的顺序表。

2.1静态顺序表

//静态顺序表
//#define N 1000
//typedef int SLDateType;
//
//struct SeqList
//{
//	SLDateType a[N];
//	int size;
//};
1
2
3
4
5
6
7
8
9

2.2动态顺序表

typedef int SLDateType;
typedef struct SeqList
{
	SLDateType* a;
	int size;  //存储的大小
	int capacity;  //空间大小
}SL;
1
2
3
4
5
6
7

这里补充一点我们在实现这种比较大的代码的时候我们一般会重新命名数据类型这样我们在之后使用的时候可以随时切换我们想要的数据类型。

三.顺序表的内容实现

//管理数据——增删查改
void SLInit(SL* ps);//初始化结构体
void SLDestroy(SL* ps);//销毁数据
void SLPrint(SL* ps);//展示数据
void SLCheckCapacity(SL* ps);//检查空间是否够
头插头删 尾插尾删
//尾插
void SLPushBack(SL* ps, SLDateType x);
//尾删
void SLPopBack(SL* ps);
//头插
void SLPushFront(SL* ps, SLDateType x);
//头删
void SLPopFront(SL* ps);
顺序表查找
int SLFind(SL* ps, SLDateType x);
顺序表在pos位置上插入x
void SLInsert(SL* ps, int pos, SLDateType x);
顺序表删除pos位置上的值
void SLErase(SL* ps, int pos);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3.1初始化

//初始化结构体
void SLInit(SL* ps)
{
	ps->a = (SLDateType*)malloc(sizeof(SLDateType) * 4);
	if (ps->a == NULL)
	{
		perror("malloc failed");
		exit(-1);
	}
	ps->size = 0;
	ps->capacity = 4;
}
1
2
3
4
5
6
7
8
9
10
11
12

在初始化的时候我们可以先给一定的空间，后续的代码会有判断是否需要扩容的函数.

3.2顺序表的扩容

//判断空间是否需要在扩大
void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		SLDateType* tmp = (SLDateType*)realloc(ps->a, ps->capacity * 2 * (sizeof(SLDateType)));
		if (tmp == NULL)
		{
			perror("realloc failed");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity *= 2;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

我们刚开始给顺序表的容量是4个，当size等于capacity的时候就是我们需要扩容的时候。每次扩容增加四个，减少空间的浪费。

3.3销毁空间

void SLDestroy(SL* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}
1
2
3
4
5
6
7

在我们创建了空间之后，我们的代码全部运行结束我们需要对创建的空间进行销毁。

3.4打印顺序表

//展示数据
void SLPrint(SL* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9

这里打印方便我们进行代码的调试。

3.5顺序表的插入

我的代码中有三种不同位置的插入分别是：尾插，头插，在指定位置下插入。下面我们依次来实现它们。

3.5.1顺序表的尾插

//尾插
void SLPushBack(SL* ps, SLDateType x)
{
	SLCheckCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
}
1
2
3
4
5
6
7

顺序表的本质其实就是数组，我们知道数组在尾部增加数是非常方便的。

3.5.2顺序表头插

//头插
void SLPushFront(SL* ps, SLDateType x)
{
	SLCheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end+1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;
	ps->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

顺序表头插是比较麻烦的一件事，数组在头部插入数据，那么原本的数据都需要向后挪动位置，所以这里我们先保存尾的下标，然后把尾部的值赋给它的下一个那么头部的位置就是我们要插入的x。

3.5.3顺序表在pos位置插入

//顺序表在pos位置上插入x
void SLInsert(SL* ps, int pos, SLDateType x)
{
	SLCheckCapacity(ps);
	int tmp = ps->size-1;
	while (pos - 1 <= tmp)
	{
		ps->a[ tmp+ 1] = ps->a[tmp];
		tmp--;
	}
	ps->a[pos - 1] = x;
	ps->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

这里在指定位置插入数据其实和头插有异曲同工之妙，我们还是先记录尾部的下标，在pos位置向下依次遍历数据。

3.6顺序表删除数据

上面我们讲了三种插入的方式，当然删除的方式也有三种。

3.6.1尾删

//尾删
void SLPopBack(SL* ps)
{
	assert(ps->size > 0);
	ps->size--;
}
1
2
3
4
5
6

因为数组的特性，尾删依然非常的方便，只需要让size减减就好了。

3.6.2头删

//头删
void SLPopFront(SL* ps)
{
	int end = ps->size - 1;
	assert(ps->size > 0);
	for (int i = 0; i < end; i++)
	{
		ps->a[i] = ps->a[i+1];
	}
	ps->size--;
}
1
2
3
4
5
6
7
8
9
10
11

和头插一样我们先记住尾的下标然后把后一个数值赋给前一个。

3.6.3删除pos位置上的值

//顺序表删除pos位置上的数
void SLErase(SL* ps, int pos)
{
	int tmp = ps->size - 1;
	assert(ps->size > 0);
	for (int i = pos - 1; i < tmp; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}
1
2
3
4
5
6
7
8
9
10
11

pos删除和头删一样，先保存pos位置的下标然后依次赋值。

3.7顺序表查找

//顺序表查找
int SLFind(SL* ps, SLDateType x)
{
	for (int i = 0; i < ps->size-1; i++)
	{
		if (x == ps->a[i])
		{
			return i;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11

四，总结

初入数据结构，我们要先适应大的代码书写，还要对细节进行把握，希望这篇文章对你有帮助！！！