数据结构---顺序表实现

3.我们定义一个结构体struct seqlist里面的是结构体成员，数组（大小未知），数组元素的个数，空间的大小，因为为了简化我们每次定义结构体变量都要写struct seqlist，我们进行typedef的重定义，定义名字为sl;这样我们定义变量sl s,就相当于struct seqlist s;比较简洁；

4.我们假定数组元素的类型都是int类型，我们进行typedef重定义，如果想要修改为char类型，只需要在第四行进行修改即可；

5.第12行是进行函数的声明，函数的声明和函数的定义第一行是一样的，就是结尾加上了分号；

顺序表的源文件：

测试函数的源文件：

6.可见，两个源文件都包含了头文件，我们在测试的函数里面重新定义了一个sltest01函数，在主函数里面进行调用；

7.我们如果进行传值，达不到真正的初始化的目的，应该传递指针，这样形参的改变才会影响到实参，我们在test01里面先定义了一个结构体的变量，把这个变量的地址传递到顺序表源文件里面进行初始化，初始化的时候，使用结构体成员访问操作符把第一个指针置为空指针，第二个和第三个元素初始化为0；

8.调试观察：

我们进行调试，刚开始我们自己定义的sl1变量是随机值，当初始化完成之后，就可以发现arr变成了空指针，size和capacity都是被初始化为0了，这样就算测试成功，达到我们初始化的目的；

（5）顺序表销毁

初始化之后，我们就要对顺序表填充功能（增删查改），最后进行销毁，我们先看一下如何进行销毁：

顺序表的源文件里面，我们要销毁，就是释放掉数组开辟的空间，然后把arr置为空指针，size和capacity全部赋值为0；

（6）顺序表的插入

顺序表的插入分为头部插入和尾部插入，我们首先看尾部插入（尾插）：

a.尾插

我们上面的举例是数组的空间比较大，我们可以直接插入，当数组元素的个数和我们的空间容量的大小相同时，我们就需要使用动态内存管理的相关的函数开辟内存空间，然后进行数据的插入:

头文件里面进行函数的声明：

顺序表的源文件里面的注意事项比较多，我们一一说明：

1.我们首先能够想到的就是插入数据，然后把size++;

2.我们需要判断是否有空间能够让我们插入数据，否则我们需要进行增容，增容就是使用realloc函数开辟空间，呢么需要开辟多大的空间呢？

这个一次开辟多大的空间需要使用数学里面概率论的知识，我们这里只要记住结论：一次按照原来的两倍进行增容就可以了；

3.但是我们前面进行初始化的时候，capacity==size=0，如果直接进行capacity*2，得到的结果就是0，因此我们需要提前进行设置；

4.怎么进行设置呢，这个地方我们就用到了三目运算符，如果capacity=0,我们就会把空间的容量，设置为4，否则就在原来的基础上面乘以2（这个就是代码里面的三目运算符表达式的含义了）；

5.我们不能直接使用ps->arr进行接收，我们应该了解realloc的原理，如果开辟成功，我们就可以使用，如果开辟失败，那么我们原来的数据就没了，因此我们需要定义一个临时的相同的数据类型的指针变量进行接收，如果不是空的，我们在传递给ps->arr;

6.增容之后，我们就需要把新的容量赋值给capacity，实现空间的增大，为了增加代码的健壮性，我们进行断言（防止传递过来的空指针导致程序的崩溃）；

测试的源文件里面我们插进去的数字是8，我们也可以多次插入，看看调试的时候的增容的实现过程：

b.头插

尾部插入数据，同样需要判断数组的容量的大小够不够，还是要用到头插里面一样的代码，因此我们可以把代码封装成为一个函数check，这样我们在头插，尾插可以直接进行调用，提高我们的代码的可读性和实用性：

因为，我们顺序表的功能完成之后，我们要进行测试，为了简单起见，我们可以把头插，尾插后的顺序表里面的数组元素打印出来进行验证，因此我们定义了slprint函数：

我们有了这个判断的函数以后，重新实现尾插和头插：

下面的两段代码对比之后就可以发现，异曲同工，都是先进行指针的断言和size的断言，

尾插比较简单：判断之后，直接在size下标的位置加上数字就可以了；

头插相对而言比较复杂：先进行断言和判断，因为是头插，我们呢要后面的一个数据覆盖前面的数据就，然后插入的数据放到0下标就可以了，这个就要用到for循环，最重要的是循环条件的判断，因为最后的覆盖是arr[1]=arr[0],所以循环的终止条件就是i=1，但是不能是0，因此i>0就可以了；

（7）顺序表的删除

a.尾删

尾删也是先进行断言，然后进行减小容量（比较简单，但是不好想明白，我是这样的）；

我们就可以理解为原来有1 2 3 4这四个数，我们把size--，size就变为3，这样进行打印的时候，就是以size作为判断的条件的，没有删掉，但是打印结果不会显示，因为那个末尾的数字已经不再我们的范围里了，好像已经“删除”了，（因为本质上就没有删，只不过不打印，不属于我们的范围而已了）；

b.头删

头删也是进行的移动覆盖，前面的头插是集体向后移，为第一个数字的插入腾空间，头删就是集体向前移，把最前面的数据给覆盖掉，这里移动的时候同样用到了循环，循环终止条件的判断尤为重要，最后的移动覆盖是arr[size-2]=arr[size-1],同理，1234这四个数字，2覆盖1，3覆盖2，4覆盖3，最后就是2344，其实最后的4覆盖前面之后自己还是存在的，但是我们打印的时候不打印他，因为我们的size--了啊，先当于循环的时候就不会这第二个四这个地方；

（8）指定位置之前插入

先进行断言，范围判断；把指定位置腾出来(循环向后移动），在向这个位置放进去数据，增大size;

（9）指定位置删除

先进行断言，从pos位置开始，循环向前移动数据，把指定位置的数据给覆盖掉，这样就实现指定位置的数据删除，最后size--；

（10）顺序表查找数据

我们使用循环遍历整个数组就可以了；我们这里的返回值是int类型，这个用来显示我们是否找到了，找到了就返回数字的下标，没有就返回无效的下标（因为肯定没有数字的下标是-1）；

当然为了让打印的结果更加的直观，我们可以测试的时候对函数的返回值进行判断，有效就说找到了指出下标，没找到就显示未找到。

3.我的心得体会（可跳过）

（1）写到这个位置真正完成了这个全部功能的实现，我也如释重负，但是我知道自己还没有完全掌握，“纸上得来终觉浅，绝知此事要躬行”，只有多多巩固，才能真正的自己写出来；

（2）我自己第一次遇到顺序表的时候，听了一遍也是一头雾水，例如里面的各种重新命名，参数的设置（实参形参），但是当你真正理解一个功能的实现方法之后，其他的就不是问题了，重要的是实现功能的方法逻辑；

（3）现在回想一下，这些功能的实现时候，有许多相似的地方，例如进行断言（指针是否为空指针，空间的容量是否为零，为零的话我们就不能进行删除等操作）；

（4）当然他们也有区别，例如在进行循环的时候，循环终止条件的判断，移动覆盖，从前向后移动还是从后向前移动，例如头插就是从后向前移动（腾开位置），头删就是从前向后移动（覆盖掉位置）；

（5）我觉得，这个里面比较难的还是循环终止条件的判断，我们不要去用脑子想，要画出来，写出最后一次循环的时候的情况，找出对应的下标和已知的参数的关系，再进行判断；

（6）当然，还有我们进行指定位置之前的插入pos可以等于size的大小，但是进行指定位置指定位置的删除的时候，我们就不能让pos==size了，这个能不能取等，我们也要举例验证；

（7）在test.c文件里面进行测试的时候，例如指定位置的删除，我们要测试3种情况，在第一个位置删除（也就是头删），在中间的位置删除，在最后的位置删除（也就是尾删），对于这样的，既应该满足中间删除的普通情况，也应该满足头删尾删的特殊情况，这几种情况都要进行测试，都通过才证明我们的代码是没有问题的；

（8）感谢你看到这里，听我细细道来，路漫漫其修远兮，we将上下而求索，加油💪！

4.顺序表完整代码

（1）seqlist.h文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int sldatatype;

typedef struct seqlist
{
	sldatatype* arr;
	int size;
	int capacity;
}sl;

//顺序表的初始化
void slinit(sl* ps);

//顺序表的销毁
void sldestory(sl* ps);

//顺序表的尾部插入数据
void slpushback(sl* ps, sldatatype x);

//顺序表的数组元素的打印
void slprint(sl s);

//顺序表的头部插入数据
void slpushfront(sl* ps, sldatatype x);

//顺序表的尾删
void slpopback(sl* ps);

//顺序表的头删
void slpopfront(sl* ps);

//顺序表的打印
void slprint(sl s);

//顺序表的指定插入
void slinsert(sl* ps, int pos, sldatatype x);

//顺序表的指定删除
void slerase(sl* ps, int pos);

//顺序表的数据的查找
int slfind(sl* ps, sldatatype x);

（2）seqlist.c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"seqlist.h"
void check(sl* ps)
{
	if (ps->size == ps->capacity)
	{
		//我们插入数据，需要增大空间，动态内存开辟空间
		int newcapacity = ps->arr == 0 ? 4 : 2 * ps->capacity;
		sldatatype* temp = realloc(ps->arr, newcapacity * 2 * sizeof(sldatatype));
		if (temp == NULL)
		{
			perror("realloc");
			exit(1);//直接退出，不再继续执行
		}
		ps->arr = temp;
		ps->capacity = newcapacity;
	}
}
//顺序表的初始化
void slinit(sl* ps)
{
	ps->arr = NULL;
	ps->size = 0;
	ps->capacity = 0;
}
//顺序表的销毁
void sldestory(sl* ps)
{
	if (ps->arr != NULL)
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}
//顺序表的尾部插入数据
void slpushback(sl* ps, sldatatype x)
{
	//对传进来的指针进行断言
	assert(ps);
	//判断数组大小和空间的容量是否相同
	check(ps);
	ps->arr[ps->size] = x;
	ps->size++;
}
//顺序表的头部插入数据
void slpushfront(sl* ps, sldatatype x)
{
	assert(ps);
	check(ps);
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size++;
}
//顺序表的打印
void slprint(sl s)
{
	for (int i = 0; i < s.size; i++)
	{
		printf("%d ", s.arr[i]);
	}
	printf("\n");
}
//顺序表的尾删
void slpopback(sl* ps)
{
	assert(ps);
	assert(ps->size);//如果我们顺序表本来就没有数据，我们进行减减就会变为-1了，显然不对，进行断言
	ps->size--;//渐渐就减少了范围，直接把最后的元素删除，就相当于最后一个元素不属于顺序表了
}
//顺序表的头删
void slpopfront(sl* ps)
{
	assert(ps);
	assert(ps->size);
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];//最后是arr[size-2]=arr[size-1];
	}
	ps->size--;
}

//顺序表的指定位置之前插入
void slinsert(sl* ps, int pos, sldatatype x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	check(ps);
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
}

//顺序表的指定删除
void slerase(sl* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	for (int i = pos; i < ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

//顺序表的数据的查找
int slfind(sl* ps, sldatatype x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		//找到了
		if (ps->arr[i] == x)
		{
			return i;
		}
	}
	//没有找到
	return -1;//无效的下标
}

（3）test.c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"seqlist.h"
void sltest01()
{
	sl sl1;

	//顺序表的初始化
	slinit(&sl1);

	//顺序表的尾部插入数据
	slpushback(&sl1, 8);
	slpushback(&sl1, 9);
	slpushback(&sl1, 10);
	slpushback(&sl1, 11);

	//尾部插入之后打印
	slprint(sl1);

	//顺序表的头部插入数据
	slpushfront(&sl1, 5);
	slpushfront(&sl1, 6);

	//头部插入之后打印
	slprint(sl1);

	//顺序表的尾删
	slpopback(&sl1);
	slprint(sl1);

	//顺序表的头删
	slpopfront(&sl1);
	slprint(sl1);

	//顺序表的指定位置之前插入
	slinsert(&sl1, 1, 0);
	slprint(sl1);

	//顺序表的指定删除
	slerase(&sl1, 1);
	slprint(sl1);

	//顺序表的数据的查找
	int ret = slfind(&sl1, 100);
	if (ret < 0)
	{
		printf("没有找到\n");
	}
	else
	{
		printf("找到了，下标是%d\n", ret);
	}
	//顺序表的销毁
	sldestory(&sl1);
}

int main()
{
	//顺序表的功能测试函数
	sltest01();
	return 0;
}