数据结构之顺序表

顺序表

线性表

线性表： 零个或多个数据元素的有限序列

而线性表又分为两种存储结构：

• 顺序存储结构：是指使用依次使用连续的空间存放线性表的数据元素，它在逻辑结构和物理结构上都是线性的。

• 链式存储结构：使用n个节点链接成的链表，逻辑结构是线性的，物理结构不一定是线性的。

顺序表是线性表的一种，基于顺序存储结构实现

• 逻辑结构：线性
• 物理结构：线性

分类：

• 静态顺序表：空间有限个，空间给大了尴尬，给小了不够用
• 动态顺序表：自动扩容，动态申请空间，刚好够用，效率高

动态循序表结构

typedef int SLType;
typedef struct SeqList
{
    SLType* arr;
    int size;//有效数据个数
    int space;//空间大小
}SL;
//typedef struct SeqList SL;

动态顺序表一般扩容是以当前空间大小的**2倍（3倍）**增加。

顺序表的顶层逻辑是数组，它可以对数据进行增删查改的操作；

功能实现

//SeqList.h
//初始化
void SLInit(SL* p);
//销毁
void SLDestory(SL* p);
//打印
void SLPrint(SL* p);
//扩容，当顺序表空间不足是进行扩容
void SLSpace(SL* p);
//头插，对顺序表第一个位置插入数据
void SLFrontPush(SL* p, SLType x);
//尾插，对顺序表最后一个位置插入数据
void SLBackPush(SL* p, SLType x);
//头删，删除顺序表第一个位置的数据
void SLFrontDel(SL* p);
//尾删，删除顺序表最后一个位置的数据
void SLBackDel(SL* p);
//查找--查找某个数据的位置（下标）
int SLFind(SL* p, SLType x);
//指定位置增加（之前）
void SLInsert(SL* p, SLType x, int pos);
//指定位置删除
void SLErase(SL* p,int pos);

小tips~

​ 在实现顺序表之前可以创建三个文件，一个头文件用于对主要功能的声明，一个SeqList.c的源文件用于对函数功能的实现，最后一个源文件test.c用于对实现功能的测试。这种做法，将不同的功能分开，提高代码的可读性，整洁性。本文也是基于这三个文件分别介绍。

顺序表的结构和初始化

顺序表结构

​ 顺序表的类型是用户自定义的，使用struct结构体进行声明。

typedef int SLType;
typedef struct SeqList
{
	SLType* arr;
	int space;//空间大小
	int size;//有效数据个数
}SL;

//typedef struct SeqList SL;

• 动态顺序表可以实现动态增容，所以使用指针变量来定义，在使用顺序表时不能不知道空间大小和存放了多少个数据，这里添加了两个整形变量的成员用于管理。
• 顺序表存储的数据类型可以有整形，字符类型登，这时使用typedef对类型重命名，在后续函数里使用int类型的部分可以替换为SLType，当需要改变存储数据的类型时在 typedef int SLType;里该变即可。
• 结构体类型的名称过长了 ，这里使用了两种方法对它进行重命名。

顺序表初始化和销毁

//test.c
	SL s;
	//初始化
	SLInit(&s);
	//销毁
	SLDestory(&s);

​ 对顺序表进行初始化及销毁需要对它（s）进行修改，均需要对形参，传地址才会对它进行改动。

//SeqList.c
//初始化
void SLInit(SL* p)
{
	p->arr = NULL;
	p->size = 0;
	p->space = 0;
}
//销毁
void SLDestory(SL* p)
{
	if (p->arr)
	{
		free(p->arr);
	}
	p->size = 0;
	p->space = 0;
}

​ 初始化，对结构体里的成员进行赋值为0，和NULL空指针即可，由于后续开辟动态内存在销毁顺序表时需要使用free函数进行释放~。

对于有没有成功初始化，以及销毁可以使用vs里的调试，逐语句功能（F11），然后点击调试，打开监视，输入名称s就可以观察了。

顺序表的扩容

​ 顺序表什么时候需要扩容呢？空间不足又如何判断？顺序表里有两个成员 int size;//有效数据个数，int space;//空间大小当有效数据个数等于空间大小，这时候就需要对顺序表进行扩容。对功能的实现也很容易理解，使用realloc函数对顺序表开辟一块连续的空间就可以了。

//SeqList.h
//扩容，当顺序表空间不足是进行扩容
void SLSpace(SL* p);

//SeqList.c
//扩容
void SLSpace(SL* p)
{
	if (p->size == p->space)
	{

		int newSpace = p->space == 0 ? 4 : (p->space) * 2;
		SLType* newSL = (SLType*)realloc(p->arr, sizeof(SLType) * newSpace);
		//SL* newSL = (SL*Tpye)realloc(p,sizeof(SLType)* newSpace);逆天犯错！！
		if (newSL == NULL)
		{
			perror("realloc: ");
			exit(1);
		}
		p->arr = newSL;
		p->space = newSpace;
	}
}

​ 在函数里，需要对有效数据个数和空间大小是否相等进行判断，所以使用if语句，在if语句里，使用realloc函数开辟，为啥不使用malloc函数呢~，我们需要实现的动态开辟，空间越开越大，可能会在新的位置开辟一块空间，malloc函数做不到。前文简单说过，对空间的增容是原空间大小的2（3）倍，这是因为，增容到原空间的2倍或3倍可以减少扩容操作的频率。如果每次只增加少量空间，那么在元素数量增长时，需要频繁进行扩容操作，这会降低性能。

​ 我们对顺序表进行初始化时空间大小为0，直接乘2还是0，这里使用了三目操作符巧妙地解决的这种问题，还完成对空间的倍数增长。

p->space == 0 ? 4 : (p->space) * 2，将表达式的结果赋给 int newSpace，使用它开辟一个SLType* 的空间，大小为

sizeof(SLType) * newSpace，由于在开辟空间是可能会开辟失败，导致数据丢失，这里使用 SLType* newSL来接受，如果开辟成功将它赋给p->arr即可，最后不能忘记对 space，更新大小。在后续涉及到增加数据的操作，都应使用这个函数对空间大小进行判断是否可行。

顺序表的插入与删除

​ 上述功能实现里的，头插、尾插、头删、尾删。在指定位置插入（之前）、指定位置删除，这两个函数功能里都会体现出来。本文着重介绍这两个功能的实现。

//SeqList.h
//指定位置增加（之前）
void SLInsert(SL* p, SLType x, int pos);

//SeqList.c
//指定位置插入
void SLInsert(SL* p, SLType x, int pos)
{
	SLSpace(p);
	assert(p);//assert(p != NULL);
	assert(pos >= 0 && pos <= p->size);
	for (int i = p->size; i > pos; i--)
	{
		p->arr[i] = p->arr[i - 1];
	}
	p->arr[pos] = x;
	p->size++;
}

​ 从头开始介绍插入功能，首先需要对顺序表插入数据，那就会对顺序表进行更改，这里选择传地址，想要插入指定位置插入数据，那还需要 SLTpye x, int pos两个参数来接受待插入的数据，及插入数据的位置。在函数起始，使用SLSpace对空间进行检查够否~

​ 为啥使用assert断言？咋不可能对空指针进行插入，这样程序运行起来会报错，在assert函数里条件为假，终止程序运行，条件为真正常运行，在第二个assert断言里，pos必须时在有效数据元素的范围里插入才是有效的，这里限定里范围。

​ 当 pos == 0，插入函数的逻辑是头插，及在下标为0的元素之前插入一个数据，这时我们需要使用循环将所有数据向后挪动一位，然后将数据x插入 p->arr[pos] = x；

在挪动所有数据时需要注意两个点：

• 起始位置 i ，是将说有数据整体后移一位，理应从最后一个数据开始移动 p->arr[p->size] = p->arr[p->size-1];，否则会造成数据的丢失。
• 终点 i 应为i - 1，当 i 减到最小时 等价于 poa + 1，这里只需将pos及之后的数据后移，数组下标 i - 1对应pos位置的元素。

当 pos == p->size，插入函数的逻辑是尾插，这时不需要挪动所有数据，只需在最后一个位置（size）插入即可。

最后别忘了，增加了一个数据，p->size需要加加。

为什么不是指定位置之前，而是指定位置之后？如果是指定位置之后就无法实现头插的逻辑。

//SeqList.h
//指定位置删除
void SLErase(SL* p,int n);

//SeqList.c
//指定位置删除
void SLErase(SL* p, int pos)
{
	assert(p);
	assert(pos >= 0 && pos <= p->size - 1);
	for (int i = pos; i > p->size - 1; i++)
	{
		p->arr[i] = p->arr[i + 1];
	}
	p->size--;
}

​ 在指定位置删除的函数里assert的逻辑与，实现指定位置（之前）插入数据是类似的，但有一点 pos <= p->size - 1，最后pos为啥不能等于 p->size，呢？顺序表最后一个元素的下标是 p->size - 1，若等于前者就会访问到奇怪的东西~

​ 在删除数据时，该怎么删除，是将pos位置对应的数据置为0吗？还是将pos位置对应的数据置为其它数（-1），这些都是多次一举，万一顺序表其余位置的数据刚好有这些数，岂不是完完。这里只需要将pos的位置进行覆盖就可以了~，使用循环将pos之后的数据向前挪动将其覆盖，就完成了指定位置删除的逻辑，是不是很easy，快去实现O(∩_∩)O。

​ 需要注意：

• 在for循环里数组的起始位置及最终位置，由于是从pos位置开始从后往前移，所以起始位为pos，最终的位置是 i = size - 2，因为在代码里 p->arr[i] = p->arr[i + 1]，i + 1后对应的位置就是最后一个元素的位置。

顺序表的查找

可以有两种查找方式，一是查找数据对应的下标，二是查找下标所对应的数据。

//SeqList.h
//查找--查找某个数据的位置（下标）
int SLFind(SL* p, SLType x);

//SeqList.c
//查找--查找某个数据的位置（下标）
int SLFind(SL* p, SLType x)
{
	assert(p);
	//循环遍历查找
	for (int i = 0; i < p->size; i++)
	{
		if (p->arr[i] == x)
		{
			return i;
		}
	}
	return -1;
}

这里实现的是查找数据对应的下标并返回。

​ 函数参数，这里不会对顺序表进行修改，理应使用传值调用，这里还是选择了传地址，是为了保持一致性，与上述实现的模快都是使用传地址。为避免混淆都采用传址调用。

​ 在函数里，顺序表不可能为空的，需要使用断言进行检查，对于查找的逻辑，使用for’循环遍历顺序表的数据，在for循环里嵌套if语句，p->arr[i] == x通过判断两者相等否，相等就返回 下标 i 即可。

arr[i] == x)
{
return i;
}
}
return -1;
}

这里实现的是查找数据对应的下标并返回。

​	函数参数，这里不会对顺序表进行修改，理应使用传值调用，这里还是选择了传地址，是为了保持一致性，与上述实现的模快都是使用传地址。为避免混淆都采用传址调用。

​	在函数里，顺序表不可能为空的，需要使用断言进行检查，对于查找的逻辑，使用for’循环遍历顺序表的数据，在for循环里嵌套if语句，`p->arr[i] == x`通过判断两者相等否，相等就返回 下标 i 即可。