【数据结构】详解顺序表

忘是亡心i 2024-03-27 09:37 75阅读 0赞

**目录**

1.线性表和顺序表

1.线性表

2.顺序表

2.接口的实现

1. 接口1---初始化顺序表

2. 接口2，3---头插，尾插

3. 接口4，5---头删，尾删

4. 接口6，7---插入，删除

5. 接口8---查找

6. 接口9---修改

7. 接口10---打印

8. 接口11---销毁

3.完整代码及效果展示

--------------------

### 1.线性表和顺序表 ###

#### 1.线性表 ####

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...。

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。如下：

![5a874292df094ebeba9896f2035f40f1.png][]

#### 2.顺序表 ####

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

顺序表一般可以分为：

1. 静态顺序表：使用定长数组存储。使用结构体变量来维护每一张顺序表，结构体的第一个成员是存储顺序表的数组，第二个成员则是存储顺序表内的元素个数。

![d1246ddd06fc4638842b165a5adf2fbf.png][]

![99e56f7e71a34fde8f4486ee50804793.png][]

> 为了提高代码可维护性 ，我们使用宏定义定义数组的元素个数N，并且使用typedef关键字将int重命名为SQDateType，后续如果需要改变顺序表元素类型则只需将int改为其他类型即可，无需修改代码其他地方。

2. 动态顺序表：使用动态开辟的数组存储，同样使用结构体变量来维护每一张顺序表，不同的是，由于数组是动态开辟的，所以需要增加一个成员来表示每个顺序表当前的容量。

![754fd63f166c4f2da5e9aa08581fb923.png][]

![559b0fac8471436baff07128f8133242.png][]

### 2.接口的实现 ###

谈到数据结构，就少不了各种各样接口的实现。但在这之前，需要说明的是：静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N如果定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态地分配空间大小，所以下面我们实现动态顺序表的各种接口，如增删改查。

#### 1. 接口1---初始化顺序表 ####

初始化想必我们都不陌生，每当我们使用局部变量的时候都需要对其进行初始化或者赋值，否则这个变量就是一个随机值，会导致程序出错。我们一般在定义变量的同时对其进行初始化，这是一个良好的编程习惯。顺序表也是如此，在使用之前，我们先对其进行初始化：

//对顺序表进行初始化
    void SeqListInit(SL* s)   //SL为结构体类型的重命名
    {
    	s->a = NULL;
    	s->size = 0;
    	s->capacity = 0;
    }

> 需要注意的是，我们需要传入一个结构体指针，否则修改的只是形参的内容。

#### 2. 接口2，3---头插，尾插 ####

在实现插入的接口时，我们要考虑到顺序表的空间是否满了。如果满了，则将数组的容量扩大两倍，我们可以将扩容封装为函数提高代码的复用。如果数组空间足够，则将数据插入，尾插则直接将数据插入尾部，头插则需要先将数据向后移动一位，然后再插入头部。

//检查顺序表是否满了，满了则扩容
    void CheckSpace(SL* s)
    {
    	//空间满了
    	if (s->size == s->capacity)
    	{
    		int newcapcity = (s->capacity == 0 ? 4 : 2 * s->capacity);  //计算新空间大小
    		SQDateType* tmp = (SQDateType*)realloc(s->a, newcapcity*sizeof(SQDateType));
    		if (tmp == NULL)
    		{
    			exit(-1); //扩容失败，退出程序
    		}
    		else
    		{
    			s->a = tmp;
    			s->capacity = newcapcity;  //更新空间
    		}
    	}
    }
    
    //尾插
    void SeqListPushBack(SL* s, SQDateType x)
    {
    	CheckSpace(s);
    	(s->a)[s->size] = x; //从尾部插入
    	(s->size)++; //顺序表元素加一
    }
    
    //头插
    void SeqListPushFront(SL* s, SQDateType x)
    {
    	CheckSpace(s);
    	for (int i = (s->size) - 1; i >= 0; i--) //集体后移一位
    	{
    		(s->a)[i + 1] = (s->a)[i];
    	}
    	(s->a)[0] = x; //从头部插入
    	(s->size)++; //顺序表元素加一
    }

#### 3. 接口4，5---头删，尾删 ####

由于我们使用size来维护顺序表的元素个数，所以我们只需将size--即可实现尾删；而头删则是从第二个元素开始向前覆盖一个元素，然后size--，即可完成头删。在执行删除操作时，要保证顺序表不为空：

//尾删
    void SeqListPopBack(SL* s)
    {
    	assert(s->size > 0); //判断顺序表是否为空
    	(s->size)--;
    }
    
    //头删
    void SeqListPopFront(SL* s)
    {
    	assert(s->size > 0);
    	for (int i = 1; i < s->size; i++) //第二个元素起向前覆盖
    	{
    		(s->a)[i - 1] = (s->a)[i];
    	}
    	(s->size)--;
    }

#### 4. 接口6，7---插入，删除 ####

我们可以将头删尾删，头插尾插4个接口进行扩展，使其能在任意合法位置进行插入或删除，如下：

void SeqListErase(SL* s, int pos)
    {
    	assert(pos < (s->size));  //检查位置是否合法
    	int start = pos + 1;
    	for (int i = start; i < s->size; i++)
    	{
    		(s->a)[i - 1] = (s->a)[i];
    	}
    	(s->size)--;
    }
    
    void SeqListInsert(SL* s, int pos, SQDateType x)
    {
    	assert(pos <= s->size);
    	CheckSpace(s);
    	int end = s->size-1;
    	for (int i = end; i >= pos; i--)
    	{
    		(s->a)[i + 1] = (s->a)[i];
    	}
    	(s->a)[pos] = x;
    	(s->size)++;
    }

#### 5. 接口8---查找 ####

遍历顺序表，当找到需要查找的元素时则返回对应的下标，如果不存在则返回-1，因为-1不会是任何数的下标。

//查找
    int SeqListFind(SL* s, SQDateType x)
    {
    	for (int i = 0; i < s->size; i++)  //遍历顺序表
    	{
    		if ((s->a)[i] == x)
    		{
    			return i;
    		}
    	}
        //没找到
    	return -1;
    }

#### 6. 接口9---修改 ####

作用是将用户指定位置的元素修改为指定元素，通过下标直接进行修改即可。同样的，需要先检查指定的位置是否合法：

//修改
    void SeqListModify(SL* s, int pos, SQDateType x)
    {
    	assert(pos < s->size);  //位置是否合法
    	(s->a)[pos] = x;
    }

#### 7. 接口10---打印 ####

有了上述接口，我们就算完成了一个顺序表增删查改基本功能的实现了。我们可以调用上面的接口对顺序表进行操作。当我们需要查看我们的操作结果时，我们可以把顺序表的元素打印出来：

//打印
    void SeqListPrint(const SL* s)
    {
    	for (int i = 0; i < (s->size); i++)
    	{
    		printf("%d ", (s->a)[i]);
    	}
    }

#### 8. 接口11---销毁 ####

由于我们使用的是动态顺序表，空间是通过realloc向系统申请，开辟在堆上的。当我们不需要时，需要手动释放空间，于是我们可以再设计一个接口用于销毁空间：

//销毁
    void SeqListDestroy(SL* s)
    {
    	free(s->a);
    	s->a = NULL;
    	s->capacity = 0; //容量置0
    	s->size = 0; //元素个数置0
    }

### 3.完整代码及效果展示 ###

我们可以采用多文件编写的形式，将上述接口的定义实现放在SeqList.c文件中，然后将接口的声明和结构体的定义放于SeqList.h头文件中，以达到封装的效果。这样我们如果需要使用顺序表，就只需要在文件中包含对应的头文件SeqList.h就可以使用我们上面定义的各种接口。以下为本文实现的顺序表完整代码以及效果展示：

//Seqlist.h文件，用于声明接口函数，定义结构体
    #pragma once
    #include<stdio.h>
    #include<stdlib.h>
    #include<assert.h>
    //增强程序可维护性
    typedef int SQDateType;
    typedef struct SeqList
    {
    	SQDateType* a;
    	int size;   //元素个数
    	int capacity;  //容量
    }SL;
    
    void SeqListInit(SL* s);
    void SeqListPrint(const SL* s);
    void SeqListPushBack(SL* s, SQDateType x);
    void SeqListPopBack(SL* s);
    void SeqListPushFront(SL* s, SQDateType x);
    void SeqListPopFront(SL* s);
    void SeqListErase(SL* s, int pos);
    void SeqListInsert(SL* s,int pos, SQDateType x);
    int SeqListFind(SL* s, SQDateType x);
    void SeqListModify(SL* s, int pos, SQDateType x);
    void SeqListDestroy(SL* s);

//SeqList.c文件，用于定义接口函数
    #define _CRT_SECURE_NO_WARNINGS 1
    #include "SeqList.h"
    void SeqListInit(SL* s)
    {
    	s->a = NULL;
    	s->size = 0;
    	s->capacity = 0;
    }
    
    void SeqListPrint(const SL* s)
    {
    	for (int i = 0; i < (s->size); i++)
    	{
    		printf("%d ", (s->a)[i]);
    	}
    }
    void CheckSpace(SL* s)
    {
    	//空间满了
    	if (s->size == s->capacity)
    	{
    		int newcapcity = (s->capacity == 0 ? 4 : 2 * s->capacity);
    		SQDateType* tmp = (SQDateType*)realloc(s->a, newcapcity*sizeof(SQDateType));
    		if (tmp == NULL)
    		{
    			exit(-1);
    		}
    		else
    		{
    			s->a = tmp;
    			s->capacity = newcapcity;
    		}
    	}
    }
    void SeqListPushBack(SL* s, SQDateType x)
    {
    	CheckSpace(s);
    	(s->a)[s->size] = x;
    	(s->size)++;
    }
    
    void SeqListPushFront(SL* s, SQDateType x)
    {
    	CheckSpace(s);
    	for (int i = (s->size) - 1; i >= 0; i--)
    	{
    		(s->a)[i + 1] = (s->a)[i];
    	}
    	(s->a)[0] = x;
    	(s->size)++;
    }
    
    
    void SeqListPopBack(SL* s)
    {
    	assert(s->size > 0);
    	(s->a)[s->size - 1] = 0;
    	(s->size)--;
    
    }
    
    void SeqListPopFront(SL* s)
    {
    	assert(s->size > 0);
    	for (int i = 1; i < s->size; i++)
    	{
    		(s->a)[i - 1] = (s->a)[i];
    	}
    	(s->size)--;
    }
    
    void SeqListErase(SL* s, int pos)
    {
    	assert(pos < (s->size));
    	int start = pos + 1;
    	for (int i = start; i < s->size; i++)
    	{
    		(s->a)[i - 1] = (s->a)[i];
    	}
    	(s->size)--;
    }
    
    void SeqListInsert(SL* s, int pos, SQDateType x)
    {
    	assert(pos <= s->size);
    	CheckSpace(s);
    	int end = s->size-1;
    	for (int i = end; i >= pos; i--)
    	{
    		(s->a)[i + 1] = (s->a)[i];
    	}
    	(s->a)[pos] = x;
    	(s->size)++;
    }
    
    
    int SeqListFind(SL* s, SQDateType x)
    {
    	for (int i = 0; i < s->size; i++)
    	{
    		if ((s->a)[i] == x)
    		{
    			return i;
    		}
    	}
    	return -1;
    }
    
    void SeqListModify(SL* s, int pos, SQDateType x)
    {
    	assert(pos < s->size);
    	(s->a)[pos] = x;
    }
    
    void SeqListDestroy(SL* s)
    {
    	free(s->a);
    	s->a = NULL;
    	s->capacity = 0;
    	s->size = 0;
    }

最后， 我们在text.c文件调用顺序表各个接口进行测试，如下：

//text.c文件，用于测试
    #define _CRT_SECURE_NO_WARNINGS 1
    #include "SeqList.h"
    
    void TextSeqList()
    {
    	SL s;
    	SeqListInit(&s);
    	//尾插
    	printf("尾插前\n");
    	SeqListPrint(&s);
    	SeqListPushBack(&s, 1);
    	SeqListPushBack(&s, 2);
    	SeqListPushBack(&s, 3);
    	printf("\n尾插后\n");
    	SeqListPrint(&s);
    	//头插
    	printf("\n头插前\n");
    	SeqListPrint(&s);
    	SeqListPushFront(&s, 1);
    	SeqListPushFront(&s, 2);
    	SeqListPushFront(&s, 3);
    	printf("\n头插后\n");
    	SeqListPrint(&s);
    	//头删
    	printf("\n头删前\n");
    	SeqListPrint(&s);
    	SeqListPopFront(&s);
    	printf("\n头删后\n");
    	SeqListPrint(&s);
    	//尾删
    	printf("\n尾删前\n");
    	SeqListPrint(&s);
    	SeqListPopBack(&s);
    	printf("\n尾删后\n");
    	SeqListPrint(&s);
    	//删除
    	printf("\n删除二号下标前\n");
    	SeqListPrint(&s);
    	SeqListErase(&s, 2);
    	printf("\n删除二号下标后\n");
    	SeqListPrint(&s);
    	//插入
    	printf("\n在2号下标插入200前\n");
    	SeqListPrint(&s);
    	SeqListInsert(&s, 2, 200);
    	printf("\n在2号下标插入200后\n");
    	SeqListPrint(&s);
    	//查找
    	printf("\n元素200所在下标为:%d\n",SeqListFind(&s, 200));
    	//修改
    	printf("\n修改在2号下标为300前\n");
    	SeqListPrint(&s);
    	SeqListModify(&s, 3, 300);
    	printf("\n修改在2号下标为300后\n");
    	SeqListPrint(&s);
    	//销毁
    	SeqListDestroy(&s);
    }
    int main()
    {
    	TextSeqList();
    	return 0;
    }

以下就是测试的最终效果：

![665abac36b1543fea71dab5aba807ae3.png][]

--------------------

***以上，就是本期的全部内容。***

***制作不易，能否点个赞再走呢qwq***

[5a874292df094ebeba9896f2035f40f1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/90492b1d651a4d1ca0a4eb17570a0f5d.png
[d1246ddd06fc4638842b165a5adf2fbf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/7733485526014428a94b930ef805cd06.png
[99e56f7e71a34fde8f4486ee50804793.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/3ff96fc010694c17a00dd72b36b1ea9c.png
[754fd63f166c4f2da5e9aa08581fb923.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/aba6c334e17446849e6d08f8e61c0b4d.png
[559b0fac8471436baff07128f8133242.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/f58f29085ac7447394a5be21f47b326a.png
[665abac36b1543fea71dab5aba807ae3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/3ade8b9f7e69428080fe50978540ab31.png