顺序表的含义与顺序表数据操作代码详解！

一，顺序表的含义

        顺序表其实为线性表的一种，而线性表则代表着具有相同特性数据结构的集合。如果说顺序表是西瓜，链式表是葡萄，那么线性表则是水果，是一类含有相同特征的事物的总称。

        对于顺序表来说，它的底层逻辑其实就是数组，而我们知道，数组具有着物理结构上的连续和逻辑结构上的连续。

如图所示：

        所以对应到顺序表，则顺序表也同时具有以下特征：1，物理结构上为线性连续的。2，逻辑结构上也为线性连续的。

二，顺序表的分类

1，静态顺序表

        上文提到，顺序表就相当于数组，所以静态顺序表那么就相当于静态数组了。

        那我们又如何理解静态一词的含义呢？其实答案很简单，静态的含义就是数组的总大小无法发生改变。所以我们便可编写出以下代码来表示一个静态顺序表。

struct SeqList//创建一个静态顺序表的结构体
{
	int arr[100];//创立一个定长数组
	int size;//size表示当前数组中有效元素的个数
};

        但是当我们真正使用起来静态顺序表时，我们总会发现它的缺点是致命的。1，当有效元素较少时，会造成空间的浪费。2，当需要存储的数据较多时，静态顺序表可能无法完全保存。

        而这些缺点在实际应用中则会是致命的，所以为了满足我们对顺序表的使用需求，我们则会更偏向于使用另一种顺序表，叫做动态顺序表。

 2，动态顺序表

        有了上文的静态顺序表做铺垫，那么理解动态顺序表一词就更简单了。

        何为动态？so easy，动态一词的含义其实就是数组的总大小可以发生改变。所以我们便可以编写出以下列代码来表示一个动态顺序表。

struct SeqList//创建一个动态顺序表的结构体
{
	int* arr;//数组指针
	int size;//有效数据个数
	int capacity;//空间大小
};

         后文中，我们将会基于动态顺序表来对其进行一系列的操作，以达到对动态顺序表中元素的增删查改工作！！

三，顺序表操作函数的实现

1，准备工作和注意事项

        首先，为了更好更有条理地实现顺序表操作函数，我们将生成三个文件。

        在SeqList.h文件中我们以如下方式定义结构体，因为顺序表中的数据可以为整型也可以为字符型，所以为了方便我们更改顺序表的数据类型，我们将使用typedef函数来命名顺序表的数据类型为SLdatatype。

typedef int SLdatatype;
typedef struct SeqList//创建一个动态顺序表的结构体
{
	SLdatatype* arr;//数组指针
	SLdatatype size;//有效数据个数
	SLdatatype capacity;//空间大小
}SL;//将顺序表改名为SL

        其次，为了实现顺序表的动态增长效果，我们需要实现一个函数为SLcheck来判断顺序表的空间是否足够，若不够的话我们将使顺序表的空间大小（也就是capacity）呈2倍数增长。

//顺序表的空间申请
void SLcheck(SL* ps)
{
	//查看空间是否足够，不够的话2倍增加空间
	if (ps->size == ps->capacity)//有效元素大小如果等于空间大小则代表着空间需要增长
	{
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//三目操作符
		//使用ralloc函数实现对空间的动态改变
		SLdatatype* temp = (SLdatatype*)realloc(ps->arr, 2 * sizeof(SLdatatype) * ps->size);
		//查看内存空间是否申请成功，不然就直接退出程序
		if (temp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		//空间申请成功
		ps->arr = temp;
		ps->capacity = newcapacity;
	}
}

        最后，对于我们每实现一个顺序表操作函数，我们都必须在test.c中进行一次测试!以防在最后实现代码时错误过多而无法修改。

2,顺序表的初始化

        当我们拿到一个顺序表之后，我们需要对它进行初始化。而初始化则非常简单，我们只需要将顺序表中的数组指针初始化为NULL，size和capacity初始化为零就可以了。整个操作我们将于SeqList.c中进行。

#include"SeqList.h"//包含头文件！！
//顺序表的初始化函数
void SLInit(SL* ps)//传址调用
{
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

        当然，要记住头文件的包含和传址调用。

         我们先应该在SeqList.h中声明这个函数，再使用test.c对这个函数进行测试！

        在test.c中，测试代码如下：

#include"SeqList.h"
void test()
{
	SL s1;
	SLInit(&s1);
}
int main()
{
	test();
	return 0;
}

        调试加监视代码走起来！

        顺序表初始化函数实现成功！

3，顺序表的销毁

        当我们使用完一个顺序表，我们需要对他进行销毁操作。我们只需要对数组指针所指向的内容free掉，然后将size和capacity置为零就可以了。

//顺序表的销毁函数
void SLDestroy(SL* ps)
{
	if (ps->arr)//判断arr是否为空指针
	{
		ps->arr = NULL;
		free(ps->arr);//free函数释放空间
	}
	ps->size = ps->capacity = 0;//置零
}

         然后在SeqList.h中声明后就可以在test.c中进行测试了。

        顺序表销毁函数实现成功！

4，顺序表的尾插

        现在准备进入顺序表中烧脑的部分了，但如果尾插听懂了，其他的操作函数对你来说那简直就是不在话下了。

        何为尾插？尾插就是在顺序表末尾插入一个数据。我们画图解释。

         如图所示，我们在顺序表中最后插入一个x，那么就相当于在下标为size的地方加入一个x，并且同时size也要往后移动一位。但是值得注意的是，如果顺序表空间不够，那我们又拿什么来存放插入的x呢？所以我们应当先使用SLcheck函数来判断空间是否足够，后再进行数据的插入。

//顺序表的尾插
void SLPushBack(SL* ps, SLdatatype x)
{
	assert(ps);//assert断言，判断ps是否为空
	SLcheck(ps);//检查顺序表空间是否足够
	ps->arr[ps->size] = x;//尾部插入x
	ps->size += 1;//size加1，表明有效元素个数加1
}

        于SeqList.h中声明后，于test.c中测试。

#include"SeqList.h"
void test()
{
	SL s1;
	SLInit(&s1);
	SLPushBack(&s1, 1);
	SLPushBack(&s1, 2);
	SLPushBack(&s1, 3);
	SLPushBack(&s1, 4);
	SLDestroy(&s1);
}
int main()
{
	test();
	return 0;
}

        调试加监视，代码走起来，结果如下。

        顺序表尾插函数实现成功！

5，顺序表的头插

        头插头插，顾名思义其实就是在顺序表的头部插入一个数据x。我们画图解释。

        所以由图可知，每当我们想要在顺序表头部插入一个数据x的时候，我们需要先判断空间是否足够，再将顺序表的数据挨着挨着从后面开始依次向后移动一位，arr[1]=arr[0]则代表着最后一次元素的移动。最后再于arr[0]中插入x，同时size加1即可。所以代码如下。

//顺序表的头插
void SLPushFront(SL* ps, SLdatatype x)
{
	assert(ps);//assert断言，ps是否为空
	SLcheck(ps);//判断空间是否足够
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];//arr[1]=arr[0];
	}
	ps->arr[0] = x;//顺序表头部插入x
	ps->size += 1;
}

        在SeqList.h中声明后，于test.c中测试。

#include"SeqList.h"
void test()
{
	SL s1;
	SLInit(&s1);
	SLPushBack(&s1, 1);
	SLPushBack(&s1, 2);
	SLPushFront(&s1, 3);//头插
	SLPushFront(&s1, 4);//头插
	SLDestroy(&s1);
}
int main()
{
	test();
	return 0;
}

         调试加监视，代码走起来，结果如图。

        顺序表头插函数实现成功！

6，顺序表的尾删

        尾删函数则十分简单，因为根本不需要进行空间是否足够的判断和顺序表元素的移位操作，我们只需要判断ps和ps->arr是否为空，然后让size减1就可以了，所以画图如下：

        所以对于该函数，代码如下：

//顺序表的尾部删除
void SLDeleteBack(SL* ps)
{
	assert(ps);//判断顺序表是否为空
	assert(ps->size);//判断顺序表是否有有效元素
	ps->size-=1;//顺序表有效元素减一
}

        在SeqList.h中声明，后于test.c中进行测试。

#include"SeqList.h"
void test()
{
	SL s1;
	SLInit(&s1);
	SLPushBack(&s1, 1);
	SLPushFront(&s1, 4);
	SLDeleteBack(&s1);//顺序表的尾删
	SLDestroy(&s1);
}
int main()
{
	test();
	return 0;
}

        调试加监视，代码走起来！结果如图：

        顺序表尾删函数实现成功！

7，顺序表的头删

        顺序表的头删，就是删除顺序表的第一个元素。具体方式我们画图解释。

        所以由图可知，我们只需要从前往后依次将前面的元素向前移动一位，最后一次移位arr[size-2]=arr[size-1]，再最后size减1。所以我们的顺序表头删函数如下：

//顺序表的头部删除
void SLDeleteFront(SL* ps)
{
	assert(ps);
	assert(ps->arr);
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];//arr[size-2]=arr[size-1]标志着最后一次移位;
	}
	ps->size -= 1;有效元素个数减1
}

        在SeqList.h函数中声明，于test.c中测试

#include"SeqList.h"
void test()
{
	SL s1;
	SLInit(&s1);
	SLPushBack(&s1, 1);
	SLPushFront(&s1, 4);
	SLDeleteFront(&s1);//顺序表的头删
	SLDestroy(&s1);
}
int main()
{
	test();
	return 0;
}

        调试加监视，代码走起来，结果如下：

        顺序表头删函数实现成功！

8，顺序表指定位置插入数据

        该方法其实也就包括了顺序表的头插和尾插，该函数可以做到顺序表指定位置插入数据。还是老样子，咱们画图解释！

        由图知，该函数有着一个新的参数pos（表示想要插入的位置的下标），当然一定不能忘记pos有大小限制，在写函数的时候我们应该对pos进行限制。其次，每当我们插入一个数的时候，我们应当首先判断空间是否足够，然后再将顺序表从最后到pos的元素一个一个向右移动一位，直到最后一次移位为arr[pos+1]=arr[pos]。最后再插入x（别忘了size要加1），这样,一个顺序表操作的新函数就被我们刨析地十分清楚了。那么我们的函数如下：

//顺序表中指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLdatatype x)
{
	assert(ps);
	assert(ps->arr);
	assert(pos >= 0 && pos < ps->size);//对pos的值进行限定！
	SLcheck(ps);//判断空间是否足够
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];//arr[pos+1]=arr[pos];
	}
	ps->arr[pos] = x;//插入x
	ps->size += 1;//有效元素个数加1
}

        老样子，先声明再测试：

#include"SeqList.h"
void test()
{
	SL s1;
	SLInit(&s1);
	SLPushBack(&s1, 1);
	SLPushBack(&s1, 2);
	SLPushBack(&s1, 3);
	SLPushBack(&s1, 4);
	SLInsert(&s1, 1, 6);//在下标为1的地方插入数据x=6
	SLDestroy(&s1);
}
int main()
{
	test();
	return 0;
}

         调试加监视，代码咱们走起来！结果如图：

        顺序表指定位置s插入数据函数实现成功！

9，顺序表指定位置删除数据 

        该函数的作用是删除指定位置的数据，当然，它的功能肯定比头删和尾删更强大。话不多说，咱们直接上图！

        通过看图后，我们可以很清楚地发现，当我们想要删除pos位置的数据时，其实我们可以直接使用arr[pos+1]位置的数据将它覆盖掉，并以此类推，将顺序表中pos之后的元素从前往后一个一个向前移动一位，最后一次移动为arr[size-2]=arr[size-1]。最后的最后一定不要忘掉size减1。那么函数代码如下：

//顺序表中指定位置删除数据
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(ps->arr);
	assert(pos >= 0 && pos < ps->size);
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];//arr[size-2]=arr[size-1];
	}
	ps->size -= 1;//顺序表有效数据减少1个
}

        咱们先声明，再于test.c中测试：

#include"SeqList.h"
void test()
{
	SL s1;
	SLInit(&s1);
	SLPushBack(&s1, 1);
	SLPushBack(&s1, 2);
	SLPushBack(&s1, 3);
	SLErase(&s1, 1);//删除顺序表中下标为1的数据
	SLDestroy(&s1);
}
int main()
{
	test();
	return 0;
}

      调试加监视，代码走起来，结果如图所示：

        顺序表指定位置删除数据函数实现成功！

10，顺序表的查找

        该函数的作用是从顺序表中找到你想要的那个数据，并且返回数据的下标，如果没找到，那么就返回一个无效值（其中无效值我们可以用-1来表示，因为数组的下标肯定不会为负数）。

        这么简单的函数我们就不用画图展示了，使用for循环便可以搞定我们想要的操作，直接上代码！

//顺序表中指定数据的查找
int SLFind(SL* ps, SLdatatype x)
{
	assert(ps);
	assert(ps->arr);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			//找到了
			return i;
		}
	}
	//没有找到
	return -1;
}

        老规矩，先声明再测试：

#include"SeqList.h"
void test()
{
	SL s1;
	SLInit(&s1);
	SLPushBack(&s1, 1);
	SLPushBack(&s1, 2);
	SLPushBack(&s1, 3);
	int find1 = SLFind(&s1, 2);//寻找顺序表中数据为2的元素的下标
	int find2 = SLfind(&s1, 5);//寻找顺序表中数据为5的元素的下标
	SLDestroy(&s1);
}
int main()
{
	test();
	return 0;
}

         调试加监视，代码走起来看结果！

        find1的值为1，说明下标为1，find2的值为-1，说明该数据不存在。

        那么顺序表查找函数实现成功！

四，结语

        六千四百多个字，再加图片加代码，手指头酸死了，希望我的blog讲解的足够详细，能对你有所帮助，有错误也欢迎指正，希望您可以给我一套三连，您的支持就是对我莫大的鼓励！！！