【线性表】—动态顺序表的增删查改实现

小菜坤日常上传gitee代码：https://gitee.com/qi-dunyan（所有的原码都放在了我上面的gitee仓库里）

数据结构知识点存放在专栏【数据结构】后续会持续更新
❤❤❤
个人简介：双一流非科班的一名小白，期待与各位大佬一起努力！
推荐数据结构书籍：《大话数据结构》

前言

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

采用数组存储的原因是，数组的地址也是连续的，随着下标的增长而增长。其实在我们之前写的通讯录，本质其实就是一个顺序表。

顺序表又分为静态与动态顺序表，所谓静态顺序表，就是提前开好固定大小的数组空间，而动态顺序表与之相比则更加灵活多变，因此，我们大多使用的都是动态顺序表。

最后，数据结构这里一定要多画图，通过图形来写代，会很容易。

接口实现

前期准备

两个源文件。分别用来测试，以及存放函数定义 一个头文件。存放函数声明与头文件包含
（另建议：有些书本上面会写菜单栏，但是为了方便调试与观察，不建议书写菜单栏）

//动态顺序表
typedef int SLDateType;
typedef struct SeqList
{
	SLDateType* a;//定义一个指针指向数组
	int size;//数据数量
	int capacity;//容量
}SeqList;
1
2
3
4
5
6
7
8

初始化

这里我们来实现初始化接口，我们可以在测试文件里直接定义一个结构体，也可以定义一个结构体指针，定义结构体的话就不用再malloc结构体空间了。

接口实现：
初始化

//初始化
void SeqListInit(SeqList* ps)
{
	//断言
	assert(ps);
	//初始化
	ps->a = NULL;//指针指向空（也可以在这里直接malloc出一个空间）
	ps->size = 0;
	ps->capacity = 0;
}
1
2
3
4
5
6
7
8
9
10

尾插与尾删

尾插

尾插的实现非常简单，就是直接在下标为size位置处进行插入即可。唯一需要注意的就是扩容情况，即size ==
capacity时就意味着空间已满，然后就得扩容，这里由于后面的一些插入也需要进行判断扩容，所以把它写成一个check函数，后面直接调用即可。

//检查扩容
void SeqListCheck(SeqList* ps)
{
	if (ps->capacity == ps->size)
	{
		//容量为0时赋值4，每次扩容扩大2倍
		int Newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDateType* pf = (SLDateType*)realloc(ps->a, Newcapacity * sizeof(SLDateType));
		if (pf == NULL)
		{
			perror("realloc");
			return;
		}
		ps->a = pf;
		ps->capacity = Newcapacity;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

尾插

//尾插
void SeqListPushBack(SeqList* ps, SLDateType x)
{
	//断言
	assert(ps);
	//检查扩容
	SeqListCheck(ps);
	//插入数据
	ps->a[ps->size] = x;
	ps->size++;
}
1
2
3
4
5
6
7
8
9
10
11

尾删
我们发现，尾删也很简单，其实只需要size–，就可以实现尾删的功能了

但是这里需要注意的是，当顺序表为空的时候，是不能进行删除的！

//尾删
void SeqListPopBack(SeqList* ps)
{
	//断言
	assert(ps->size>0);
	ps->size--;
}

1
2
3
4
5
6
7
8

打印

这里我们写一个用来打印顺序表的函数，以便于我们用来打印观察，打印的实现也很简单，只需要打印下标从零开始，一直到 下标为size-1的即可

//打印
void SeqListPrint(SeqList* ps)
{
	//断言
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12

这里我们在测试文件里进行测试，看一下是否有问题：

//尾插尾删
void TestSeqList1()
{
	SeqList s;//定义结构体
	//初始化
	SeqListInit(&s);
	//尾插
	SeqListPushBack(&s,1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListPrint(&s); //1 2 3 4

	//尾删
	SeqListPopBack(&s);
	SeqListPopBack(&s);
	//打印
	SeqListPrint(&s);//1 2
	//一直删到为空
	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPrint(&s);//error
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

我们发现，以上是没问题的，不管是增容、还是尾删到空继续尾删，都在我们掌控之中，接下来我们进行头插与头删的操作

头插与头删

头插
顾名思义就是在数组下标为0的位置进行插入，这里我们通过画图来理解,这里头插完后记得size++

头插的时候切记注意检查扩容情况！

//头插
void SeqListPushFront(SeqList*ps,SLDateType x)
{
	//断言
	assert(ps);
	//检查扩容
	SeqListCheck(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
14
15
16
17
18

头删
所谓头删，就是删除头部数据，这里还是通过覆盖的方式，画图即可更加方便理解

切记空表状态不可进行删除！

//头删
void SeqListPopFront(SeqList* ps)
{
	assert(ps);
	assert(ps->size > 0);
	int begain = 0;
	//挪动
	while (begain < ps->size - 1)
	{
		ps->a[begain] = ps->a[begain + 1];
		begain++;
	}
	ps->size--;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

测试
这里通过测试发现，代码是没问题的

void TestSeqList2()
{
	SeqList s;
	SeqListInit(&s);
	//头插
	SeqListPushFront(&s, 6);
	SeqListPushFront(&s, 5);
	SeqListPushFront(&s, 4);
	SeqListPushFront(&s, 3);
	SeqListPrint(&s); // 3 4 5 6

	//头删
	SeqListPopFront(&s);
	SeqListPopFront(&s);
	SeqListPrint(&s);//5 6
	SeqListPopFront(&s);
	SeqListPopFront(&s);
	//删除空表
	SeqListPopFront(&s);
	SeqListPrint(&s);//error，报错
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

查找

顺序表查找也是一件很简单的事，从begain位置开始查找

//顺序表查找
int SeqListFind(SeqList* ps, SLDateType x,int begain)
{
	assert(ps);
	assert(begain>0&&begain<ps->size);
	//begain的位置必须在顺序表范围内（begain其实就是下标，从下标为begain位置处开始查找）
	int i = 0;
	//遍历数组进行查找
	for (i = begain; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			return i;//找到直接返回下标
		}
	}
	//查找不到，返回-1
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

查找本身并不复杂，就是遍历数组而已

在任意位置插入与删除

这里还是要通过画图，能更加容易理解，另外插入的时候一定注意扩容情况！

还有就是，这个pos必须是在数组的有效范围内，不能跑到别的地方插入数据，因为顺序表的地址是连续的，如果超过了这个范围，就不构成连续了，如下：

代码实现：

//在pos位置插入
void SeqListInsert(SeqList* ps, int pos, SLDateType x)
{
	assert(ps);
	assert(pos >= 0);
	assert(pos <= ps->size);
	//检查扩容
	SeqListCheck(ps);
	int end = ps->size - 1; 
	//挪动数据
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

任意位置删除

另外，pos位置也必须在有效范围内

//pos位置删除
void SeqListErase(SeqList* ps, int pos)
{
	assert(ps);
	assert(pos >= 0);
	assert(pos <= ps->size);
	int begain = pos + 1;
	//覆盖即可
	while (begain < ps->size)
	{
		ps->a[begain - 1] = ps->a[begain];
		begain++;
	}
	ps->size--;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

测试
在测试文件里通过数据来观察

//任意位置插入删除
void TestSeqList3()
{
	SeqList s;
	SeqListInit(&s);//初始化
	SeqListPushFront(&s, 6);
	SeqListPushFront(&s, 5);
	SeqListPushFront(&s, 4);
	SeqListPushFront(&s, 3);
	//pos位置插入
	SeqListInsert(&s, 2, 1);
	SeqListPrint(&s); // 3 4 1 5 6
	SeqListInsert(&s, 4, 1);
	SeqListPrint(&s); // 3 4 1 5 1 6
	//pos位置删除
	SeqListErase(&s, 4);
	SeqListErase(&s, 4);
	SeqListInsert(&s, 3, 4);
	SeqListPrint(&s); // 3 4 1 4 5 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

我们发现，也是没什么问题的，说明我们已经正式写完了整个顺序表。
不过这里有一点需要注意的是，任意位置的插入与删除，如果这个位置是下标为0的地方，这就等同于头插头删，如果这个pos是在下标为size处，这就是尾插尾删
所以我们的头插可以也写为：

//头插
void SeqListPushFront(SeqList*ps,SLDateType x)
{
	断言
	//assert(ps);
	检查扩容
	//SeqListCheck(ps);
	//int end = ps->size-1;
	挪动数据
	//while (end >= 0)
	//{
	//	ps->a[end + 1] = ps->a[end];
	//	end--;
	//}
	在头部插入数据
	//ps->a[0] = x;
	//ps->size++;
	SeqListInsert(ps, 0, x);//从0位置处插入，就是头插
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

其余类比也是同理。

销毁

最后是顺序表的销毁，也很简单，释放a指向的空间，并置空a指针，然后size与capacity归零即可
这里注意，假如a是个空指针（未开辟空间就直接释放），就不能进行释放，具体原因动态内存章节已讲解，即空指针不能释放，所以加了个if判断条件。

//释放
void SeqListDestroy(SeqList* ps)
{
	//断言
	assert(ps);
	//释放空间
	if (ps->a != NULL)
	{
		free(ps->a);
		ps->a = NULL;
		ps->capacity = 0;
		ps->size = 0;
	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

总结

最后再总结以下，需要注意的细节地方无非是传来的参数是否为空指针，涉及到任意位置就要考虑下pos是否位置合理，还有就是只要涉及插入数据的操作，就必然要考虑到扩容，涉及到删除的操作，就必然考虑到空表问题。
最后，一定要多画图，才能更好理解！顺序表本身并不难，包括后面的链表，多画图就会很好的理解！

---

end
生活原本沉闷，但跑起来就会有风！❤