顺序表专题

1.为什么需要顺序表

顺序表的底层是数组，在数据结构（相关概念见算法的时间复杂度和空间复杂度-CSDN博客）的学习中，顺序表是最基础的线性结构之一。它如同一个 “数据容器”，能高效地组织和管理数据。以通讯录项目为例，若没有合适的数据结构，实现联系人的增删改查会变得复杂且低效（编写代码时需要找到数组中以有元素的个数，再进行增删改查操作）。顺序表作为数组的封装，不仅提供了基础的数据存储能力，还通过优化操作接口，让复杂的数据管理变得可行。

顺序表say：“虽然我大底层是数组，但是我提供了很多现成的方法，开箱即用，我就变成了一个新的很厉害的数据结构。其实也就是在数组的基础上，增加了增删改查等方法。”

在之前的学习中，对于C语言文件而言，分为.c，文件以及.h头文件

在.h 文件中包含:顺序表结构，声明顺序表的方法

在.c文件中包含:实现顺序表的方法

2.线性表与顺序表的定义

顺序表是线性表的一种！

1）线性表

• 线性表：由 n 个相同类型数据元素组成的有限序列，逻辑上呈线性结构（如一条直线），物理存储可以是数组或链表。常见的线性表包括顺序表、链表、栈、队列等。

线性表指的是物理结构、逻辑结构具有相同特征的数据结构的集合。

线性表的物理结构:不一定连续

线性表的逻辑结构:连续的

比如:

蔬菜:小白菜，莲藕，莴笋……

水果:香蕉，草莓，苹果……

2）顺序表

• 顺序表：线性表的一种实现方式，其物理存储基于数组，逻辑上相邻的元素在内存中也连续存储。

顺序表的物理结构:是连续的

顺序表的逻辑结构:一定是连续的

3.静态顺序表与动态顺序表的对比

int arr[10] = {0}

这是一个定长的数组

如果刚开始不知道数组的长度呢？

int* arr，这个时候就需要动态内存开辟，在确定大小之后再去动态申请。

顺序表分为静态顺序表以及动态顺序表。

1）静态顺序表

定义:

struct SeqList

{

      int arr[100];//定长数组

      int size;//顺序表当前有效的数据个数

};

2）动态顺序表

定义:

struct SeqList

{

      int* arr;

      int size;//有效的数据个数

      int capacity;//空间大小

};

顺序表为什么要叫SeqList:

因为Sequence表示顺序的，List表示列表。

3）对比

对比一下哪种顺序表更好？

按照相较而言，动态顺序表更加好，因为静态顺序表会面临数组大小如果给小的话，空间会不够用的情况。如果说当数组给大的话，会造成空间浪费的情况。而动态顺序表，可以动态增容。

4.动态顺序表的核心实现

动态顺序表的关键在于通过动态内存管理实现灵活扩容，以下是核心功能模块：

1）初始化

初始化：分配初始空间，设置初始容量和数据个数。

代码:

.h文件:

#pragma once

#include <stdio.h>
#include <stdlib.h>
//定义顺序表的结构
//#define N 100
 
静态顺序表
//struct SeqList
//{
//	int arr[N];
//	int size;
//	//有效个数
//};

//定义数据类型
typedef int SLDataType;

//动态顺序表
typedef struct SeqList
{
	int* arr;
	int size;
	//有效个数
	int capacity;
	//空间大小
}SL;
//定义结构体名称为SL

//顺序表初始化
void SLInit(SL ps);

.c文件:

SeqList.c:

#define _CRT_SECURE_NO_WARNINGS 1
#include"test.h"
void SLInit(SL s)
{
	s.arr = NULL;
	s.size = s.capacity = 0;

}

test.c:

#define _CRT_SECURE_NO_WARNINGS 1
#include"test.h"

//测试初始化对不对
void SLTest01()
{
	SL sl;
	SLInit(sl);
}
int main()
{
	SLTest01();
	return 0;
}

我们测试一下:

发现报错了，为什么？

要区别一下，传值与传地址。

形参传给实参，在这个过程中，实际上是传值，即值的拷贝。

此时此刻sl没有初始化，所以会报错，所以此时此刻需要，对sl初始化就应该传地址。[用取地址操作符，用指针来操作地址]

调试一下：

2）销毁

销毁：释放内存，避免内存泄漏。

代码：

test.c文件补充：

//销毁
SLDestory(&sl);

SeqList.c文件补充：

//顺序表销毁
void SLDestory(SL* ps)
{
	if (ps->arr)
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

3）数据操作接口

插入操作：尾部插入（O (1)）、头部插入（O (n)）、指定位置插入（O (n)）。

删除操作：尾部删除（O (1)）、头部删除（O (n)）、指定位置删除（O (n)）。

查找与修改：按值查找（O (n)）、按位置修改（O (1)）。

//头部插入删除 / 尾部插入删除
void SLPushBack(SL * ps, SLDataType x);//尾部插入
void SLPopBack(SL * ps);
void SLPushFront(SL * ps, SLDataType x);//头部插入
void SLPopFront(SL * ps);

（1）尾插

顺序表ps:

如图所示原始：size = 4；capacity = 6；

现在插入x = 5 ；（尾插，在 size 处插入 x ）

之后变为：size = 5；capacity = 6；

代码：

//顺序表尾插
void SLPushBack(SL* ps, SLDataType x)
{
	/*ps->arr[ps->size] = x;
	++ps->size;*/
	//可以写为
	ps->arr[ps->size++] = x;

}

测试一下：

	//尾插
	SLPushBack(&sl, 1);

 报错了，调试一下：

发现空间为0，所以需要我们在插入前保证是有可用空间的，修改代码如下：

//顺序表尾插
void SLPushBack(SL* ps, SLDataType x)
{
	//首先观测空间够不够
	if (ps->capacity == ps->size)
	{
		//三目表达式
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		//申请空间
		//使用realloc 
		SLDataType * tmp = (SLDataType*)realloc(ps->arr, newCapacity * 2 * sizeof(SLDataType));
		//动态的容易报错,申请失败，则可以补充SLDataType* tmp
		if (tmp == NULL)
		{
			//判断有没有动态申请成功
			perror("realloc 失败!");
			//直接退出程序，不再继续
			exit(1);
		}
		//申请成功
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
	//ps->arr[ps->size] = x;
	//++ps->size;
	//可以写为
	ps->arr[ps->size++] = x;
}

 调试一下：

补充：申请空间需要用下面哪个函数？

malloc  calloc realloc 

比如给一个空间：int arr[100] 需要增容用realloc

malloc 申请空间

calloc申请空间并且初始化

需要申请多大的空间呢？一次性增容多大？

初始有四个空间，但是现在空间不够了，所以我们应该增容一个空间变成五个空间，还是说增加很多很多个变成n个空间呢?

增容通常来说是成倍数的增加，一般情况下是两倍或者三倍，这是数学推理出来的，用二倍或三倍更加合理。

realloc 增容是怎么增的呢？

在一块内存中，arr 已经有一部分空间，我果需要增加空间，在后面继续申请，如果说它后面的这部分空间依然不够，则需要重新另辟蹊径找一个空间足够大的地址，继续申请空间，在下图中，黑色为原始空间，绿色为申请的空间。

在其他地址申请空间时，需要将原始的数据拷贝过来，并且将之前的空间释放掉，成为一个新的 arr [绿色的位置] ，代替原来的 arr [黑色的位置]，的空间。

注意的是这个步骤非常的麻烦，如果要频繁的增容，则会造成程序的运行效率大大降低的现象。

如果一次给大呢？就会造成空间浪费的问题。

所以需要成倍数增加。

可以乱加数据吗？

SLPushBack(NULL, 5);

加一段代码，测试一下：

这里是因为NULL为空，传在指针的位置不可以对空指针进行解引用[野指针]，所以此时的代码还是比较脆弱的，在进行以下补充，防止用户传输奇怪的值:

//加强代码
if (ps == NULL)
{
	return;
}

或者直接断言：

	//断言
	assert(ps);
	//等价于assert(ps != NULL)

断言需要添加头文件：

#include<assert.h>

 （2）头插

同样的，涉及到插入数据，我们就要思考空间够不够？够的话直接插入空间，不够的话需要增容。

所以我们将上述的判断空间够不够的一段代码进行封装函数:

//判断空间的封装函数
void SLChackCapacity()
{
	//首先观测空间够不够
	if (ps->capacity == ps->size)
	{
		//三目表达式
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;

		//申请空间
		//使用realloc 
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * 2 * sizeof(SLDataType));

		//动态的容易报错,申请失败，则可以补充SLDataType* tmp
		if (tmp == NULL)
		{
			//判断有没有动态申请成功
			perror("realloc 失败!");

			//直接退出程序，不再继续
			exit(1);
		}
		//申请成功
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}

尾插是从size处开始插入数据，而头插则应当从下标为零的地方开始插入数据，也就是第一个位置开始插入数据。

需要将原始数据，从后向前依次全部向后挪，第一个位置空出来，再插入数据。

代码如下:

//顺序表头插
void SLPushFront(SL* ps, SLDataType x)
{
	//判断空间
	SLChackCapacity(ps);

	//断言
	assert(ps);
	//等价于assert(ps != NULL)

	//已有的数据向后移动
	for (int i = ps->size; i > 0; i--)
	{
		//arr[1] = arr[0]
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
}

测试一下:

//头插
SLPushFront(&sl, 5);
SLPushFront(&sl, 6);

调试:

是一个一个向后挪动的：

 接下来插入6：

 打印一下（打印代码见下述）：

我们发现，该代码也有问题，因为我们需要增加数据，所以在数据表中 size 也需要++，添加代码如下所示:

	ps->size++;

分割线:以下内容还较不全面，今天时间太晚啦，明天将会补充完整

（3）尾删

前提是数据表不能为空，所以需要一个断言。

assert(ps);

删完数数据以后要少一个，所以需要 size--。

关于删除数据，我们可以用这个办法:

ps->arr[size-1] = -1;

size--

注意观测顺序表是否为空？如果为空的话，我们则不能进行删除操作。所以此刻还需要一个断言及顺序表，不能为空。

assert(ps->size);

尾删代码如下:

尾删中size减减会影响后续的数据操作吗？

不会的，因为当删除时执行一次 size--，当增加数据时，在size的位置插入数据，并且执行 size++。当修改数据时，也在size内。查找数据时，循环条件为不能超过 size，所以对，后续是没有影响的。

（4）头删

怎么操作的呢？

是将第一个数据删除后，后面的数据一个接一个依次向前挪动一个位置，之后再执行 size--，代码如下:

测试一下:

打印:

4）打印

在上述描述中，每次测试时都需要通过调试去观测代码的编写是否正确，这样非常的麻烦。我们可以通过顺序表的打印，来观测结果，这样更加便捷。

//顺序表打印
void SLPrint(SL s)
{
	for (int i = 0; i < s.size; i++)
	{
		printf("%d", s.arr[i]);
	}
	printf("\n");
}

打印的话打印值，不需要指针。