简单实现顺序表

1.什么是顺序表？

首先，我们先来了解一下顺序表的概念。顺序表是数据结构中的一种，他的底层逻辑非常简单，就是数组，是基于数组来存储东西的。他主要的功能可以分为，头插，尾插，头删，尾删，任意插入数据，任意删除数据等等，当然还有一个最基本的功能，就是打印数据啦~。顺序表可以用来当作通讯录，一些信息管理系统等等的底层代码。在我们将要实现这些东西的时候，我们就可以直接来调用这个顺序表。

2.顺序表的代码实现

既然顺序表是可以当作一个底层的东西来提供调用的，那么他的代码是怎么实现的呢？就让我们一起来看看。

(1).万物之基—结构体

既然前面说了，顺序表的底层逻辑是数组，那么，我们是需要创建一个数组才对的。但是这里为什么说是创建一个结构体？为什么说结构体是搭建顺序表的第一步？因为我们不仅仅是要记录数组，还要创建两个变量，一个是size，一个是capacity

typedef int Type;
typedef struct SeqList
{
	Type* arr;
	int size;
	int capacity;
}SL;

size和capacity是什么东西？我来解释一下~

size：表示arr有效数据的个数。注意：虽然说size表示的是arr数组里面的有效个数，但是他的指针是指向arr里面有效个数的下一个位置的。(这里我一开始就错在这里了)

capacity：顾名思义，就是空间。这个capacity在这里代表了开辟了多少的空间。那他为什么是int类型呢？这个先埋个伏笔，在代码后面会大有用处。

对于这个代码，我还想要解释的是。因为我们不确定未来存进去的元素是什么类型的，所以在第一行的位置，把int类型typedef成Type，如果未来不想传int类型的数据了，直接把int改成你想要传的数据类型就可以了。

(2).顺序表的初始化和销毁

这个东西比较容易理解。所谓的初始化就是把结构体里面的东西都赋予一个初始值。而销毁的操作跟初始化大同小异。这边就直接上代码了

void SeqList_Init(SL* sl)
{
	assert(sl);
	sl->arr = NULL;
	sl->capacity = sl->size = 0;
}
void SeqList_Dest(SL* sl)
{
	assert(sl);
	if (sl->arr != NULL)
	{
		sl->arr = NULL;
		free(sl);
	}
	sl->size = 0;
	sl->capacity = 0;
}

怎么这里又出现了一个新的变量SL*sl？可能到这里，一些基础不好的同学(比如我)，可能就会晕掉。其实，SL只是结构体的重命名，然后，我用这个名字来创建了一个新的结构体变量，名字叫做sl而已，用于接受从主函数里面传来的结构体变量，跟函数的传参和接收是一个意思。类比一下

ok让我们回到这边。assert是什么？他其实是一个用来判断的工具，如果像我们写成那样的话，assert(sl)，那么这个操作就是帮助我们判断指针是否为空值，如果是的话，会将程序强行中断。在初始化顺序表的代码里面，我们需要把数组赋为空值，其他的全部都是0，而在销毁顺序表的操作中，却是多出了一个free的操作，这又是为什么？因为在我们的这个顺序表中，是使用动态内存开辟的，会使得顺序表的存储灵活性更大，因此我们的这个顺序表又称作动态顺序表，与之对应的当然有一个静态顺序表。当然我们今天只谈前者，后者暂时不谈。

(3).顺序表的空间开辟

我们在执行尾插，头插等一些列往顺序表里面插入数据的操作时候，如果顺序表一开始的空间是0，也就是初始化之后的顺序表空间。那么这个时候我们就需要对顺序表的空间进行开辟。

那如何来开辟顺序表空间呢？我们说可以借助size和capacity这两个值来判断顺序表里面空间是否足够。如果size==capacity，那么就会有两种情况

(1).size和capacity都等于0，这就说明了这个顺序表一开始就没有数据

(2).size和capacity的数值相等，但不为0。这就说明了目前顺序表里面是有存储数据的，有效数据size和内存capacity相等。

如果出现了以上的这两种情况，我们就可以进行开辟空间的操作了。那么具体开辟多少？那如果是第一种情况的话，我们就可以先开辟5个空间；如果是第二种情况，我们就可以以二倍的增长量来开辟，也就是说开辟前一个空间的二倍。

那具体怎么操作？

首先判断sl->capacity是否为0，如果sl->capacity为0，则给他5个空间，如果不为0，则sl->capacity*2，这个值放在一个新变量里面存着。

接下来就可以使用realloc来延长内存了。为什么要用realloc而不是malloc？

首先我们要明白一个概念，malloc是用来开辟一个没有的东西，就像在一个混沌之中来开辟一块可以存放东西的地方；而realloc是用来延长那块可以存放东西的。虽然说我们的顺序表一开始没有存放东西，但不代表没有可以给存放东西的地方存在，也就是说，顺序表的arr一开始是初始化成0了的，是有某种意义上的一块空间的，只是为0。因此，我们是需要借助realloc来开辟更大的空间。

具体代码操作如下:

void SeqList_Space_Open(SL* sl)
{
	if (sl->capacity == sl->size)
	{
		int NewCapacity = sl->capacity == 0 ? 5 : 2 * sl->capacity;
		Type* p = realloc(sl->arr, NewCapacity * (sizeof(Type)));
		if (p == NULL)
		{
			perror("p");
			return 1;
		}
		sl->arr = p;
		sl->capacity = NewCapacity;
	}
}

 (4).尾插

有了空间，我们就可以往顺序表里面插入数据了，首先，我们来执行一下尾插的操作。

我们首先来思考一下尾插的逻辑。尾插是从顺序表的尾部插入数据，也就是说，是sl->arr数组的尾部插入。那么我们该如何找到sl->arr数组的尾部？回想一下，我们一开始是不是用了size来记录有效个数？如果往顺序表里面存入了一个数据，那么这个size指针就++往后挪动一位

如上图为例，当顺序表里面插入了四个数据之后，此时的sl->size指针就刚好指向了第五个sl->capacity的开头。正因如此，我们就可以直接把变量插入到arr[sl->size]的这个位置

基本逻辑确定了，那就还有一些小地方需要注意。且听我细说。既然是尾插，那么我们是不是应该确定有没有内存空间足够我们尾插数据进去。那此时此刻我们就可以利用sl->size和sl->capacity来判断。如果sl->size==sl->capacity，那么就说明此时的有效个数和空间一样，意味着剩余的空间不够我们来插入新的数据，因此需要重新开辟空间；如果sl->size<sl->capacity，则就意味着有效个数是小于剩余的空间的，是有足够的空间来允许我们插入新的数据。

代码实现

void SeqList_Push_Back(SL* sl, Type x)//x是需要插入的变量
{
	assert(sl);
	if (sl->capacity > sl->size)
	{
		sl->arr[sl->size] = x;
		sl->size++;
	}
	else if  (sl->capacity == sl->size)
	{
		SeqList_Space_Open(sl);
		sl->arr[sl->size] = x;
		sl->size++;
	}
}

(5).头插

顾名思义，头插就是从顺序表的头部插入。这依旧要分情况，一种是顺序表里面有数据，一种是没有数据。

（1).没有数据的情况

如果顺序表里面没有数据，则直接开辟新的空间。

(2).有数据的情况

如果顺序表里面有数据，我们的思路可以是把顺序表里面的数据整体向后移动一位。考虑到顺序表的底层逻辑就是数组，可以使用for循环来进行后移一位。然后在arr[0]的位置肯定会空出一个地方，这个地方就是我们插入数据的地方。

以下是代码实现:

void SeqList_Push_Fron(SL* sl,Type x)
{
	assert(sl);
	if (sl->size == sl->capacity)
	{
		SeqList_Space_Open(sl);
	}
	if (sl->capacity > sl->size)
	{
		for (int i = sl->size; i > 0; i--)
		{
			sl->arr[i] = sl->arr[i - 1];
		}
		sl->arr[0] = x;
		sl->size++;
	}
}

(6).尾删

尾删的思路很简单，只是需要直接把数组最后一个元素删掉即可，也就是说，在执行尾删的操作的时候，只需要把sl->size进行--操作就行。

但是需要注意的一个点就是，在删除数据之前，需要判断顺序表里面是否有数据，这个时候我们可以引入一个新的函数-----bool函数。

什么是bool函数？

(1).bool函数

bool函数又称为布尔函数，布尔函数是一个用来记录某个值是真还是假的函数，如果是真值，就返回true，如果是假值，就返回false。在顺序表中，我们可以使用布尔函数来判断顺序表里面是否有数据，代码如下

bool Check_Empty(SL* sl)
{
	assert(sl);
	return sl->size == 0;
}

在此代码中， 我们把sl->size==0当成一个判断语句，如果sl->size==0为真，那么bool的返回值就是true，如果sl->size==0为假，那么bool的返回值就是false。

那解决了顺序表的判空问题，代码就可以接着往下走了，以下是尾删的代码

void SeqList_Del_Back(SL* sl)
{
	assert(sl);
	assert(!Check_Empty(sl));
	sl->size--;
}

(7).头删

头删的思路同样也是非常的简单，因为顺序表的底层逻辑就是一个数组，所以我们如果想实现头删的操作，就可以直接把数组的数据整体往前挪一位，那么第一个的数据就会被后面的数据给覆盖掉，然后整体数据进行自减操作就可以了，代码如下

void SeqList_Del_Fron(SL* sl)
{
	assert(sl);
	assert(!Check_Empty(sl));
	for (int i = 0; i < sl->size; i++)
	{
		sl->arr[i] = sl->arr[i + 1];
	}
	sl->size--;
}

需要注意的是，for循环里面的i变量是从0开始变化的，为什么呢？因为我们是从前面开始，往后i就一直自增。也就是说，整个数组往前挪动一位是从最小的下标开始移动的，一直到sl->size 为止。

(8).从任意位置后面插入数据

到了这里，程序就开始变得有些复杂了，当然也不是很复杂。且听我细说~

 首先我们来说一下总体的思路，那既然是从任意位置的后面插入数据，我们首先得知道是从哪个位置插入数据，是不是有些抽象了，画个图来具象化以下

在这里，我们定义一个变量pos来接收要在哪个地方的后面来插入数据，以上面这个例子，此时pos的值就是1，需要插入的数据就是5。此时此刻我们已经定义好了pos，那在走之前还要确定一个点，那就是判断顺序表里面的空间是是足够的。

(1).没有足够的空间

判断是否有没有足够空间，我们可以使用sl->size和sl->capacity来判断，如果此时两者相等，那就说明此时此刻的空间是不足够的，只有在size<capacity的情况下，才会有足够的空间

如果顺序表里面没有足够的空间，我们就可以让代码走向代码的开辟空间的函数。

(2).有足够的空间

如果此时空间足够，那么我们就可以思考一下代码的走向了。

既然是要在pos位置的后面插入数据，那肯定得给这个数据腾一个位置出来，怎么腾位置？还是把数据向后移动。从哪个位置开始移动？是从后往前移动。要移多少？移到pos就可以停止了。

因此，这个时候的i的初始值可以是有效个数有效个数-1，i要>=pos，i--，所以，代码就可以写成以下这个样子~

void SeqList_Insert(SL* sl, int pos, Type x)
{
	assert(sl);
	assert(pos >= 0 && pos <= sl->size);
	if (sl->size == sl->capacity)
	{ 
		SeqList_Space_Open(sl);
	}
	if (sl->capacity > sl->size)
	{
		for (int i = sl->size; i >= pos; i--)
		{
			sl->arr[i] = sl->arr[i - 1];
		}
		sl->arr[pos] = x;
		sl->size++;
	}
}

(9).删除任意位置的数据

这个大体思路跟这个"从任意位置插入数据"是一样的。

为什么这么说？请看，如果你要删除一个数据，那也是要确定该删除数据所在的位置pos吧？删除的主要思想仍然是覆盖，从后往前覆盖。在for循环里面，i初始化成pos，i<sl->size，i++,然后，把后面的数据赋值给前一个位置，把他从pos的位置开始覆盖掉。代码如下

void SeqList_Del_EverWhere(SL* sl, int pos)
{
	assert(sl);
	assert(pos >= 0 && pos < sl->size);
	for (int i = pos; i < sl->size; i++)
	{
		sl->arr[i] = sl->arr[i + 1];
	}
	sl->size--;
}

注意：有细心的同学可能会发现，这个地方的assert断言处，pos<sl->size，跟上面的相比，好像少了一个=号。这是为什么？

sl->size在该顺序表中，起到的是一个记录有效数据的作用，也就是说，如果存入一个数，这个size就进行自加的操作。他永远都指向有效数据个数的下一个，此时，如果传入的pos是sl->size的话，这个位置的指针是指向一个空的地方，是违法的，因为这个地方并没有数据。

(10).修改和查询

由于修改和查询的两个执行方式都相差不大，因此我把这两个放到一起写(绝不是因为偷懒)

我们写顺序表的时候可以发现，覆盖是一个好用的东西。

在"修改数据"这个地方，好像也是可以使用覆盖数据来执行操作。

那么如何进行思考？首先我们想一下，修改数据，是不是得传入你想修改数据的地方？其次，得传入你想修改之后的数据。然后直接把数据覆盖到原本的位置就可以了。

那也就是说，我们首先得找到那个数据的原来的位置。怎么寻找？我们可以写一个循环，遍历整个数组，然后，如果数组里面有我们输入想要查询的数据，就返回当前数据的下标。最后把这个下标的地方，用我们想修改后的数据覆盖上去就可以了。代码如下。

int Findby(SL* sl, Type x)
{
	for (int i = 0; i < sl->size; i++)
	{
		if (sl->arr[i] == x)
		{
			return i;
		}
		if (sl->arr[i] != x)
		{
			return -1;
		}
	}
	
}
void SeqList_Modify(SL* sl)
{
	assert(sl);
	printf("请输入要修改的地方:\n");
	int x = 0;
	scanf("%d", &x);
	int ret = Findby(sl, x);
	if (ret >= 0)
	{
		printf("请输入要修改的数据:\n");
		int y = 0;
		scanf("%d", &y);
		sl->arr[ret] = y;
		printf("修改成功!\n");
	}
	if(ret==-1)
	{
		printf("没有找到这个数据\n");
	}
}

而查询的操作，也是与这个大同小异~~直接遍历数组，如果找到相同的数据，直接输出~

 
void SeqList_Find(SL* sl)
{
	assert(sl);
	printf("请输入你要查找的数据:\n");
	int n = 0;
	scanf("%d", &n);
	int ret = Findby(sl, n);
	if (ret >= 0 )
	{
		printf("找到了，是:%d", sl->arr[ret]);
	}
	else
	{
		printf("找不到\n");
	}
}

3.结尾

以上就是顺序表的总体思路和写法，对于这个，我也花了一天的时间来消化他。总体来说，还是比较容易能理解滴。虽然代码量比较多哈哈哈哈~