数据结构：顺序表详解

1.顺序表的概念与定义

2.顺序表的初始化与销毁

3.顺序表的头/尾部的插入与删除

4.顺序表指定位置的插入和删除

4.对顺序表中的数据的查找

5.总结

我以过客之名，祝你前程似锦

一.顺序表的概念与定义

1.概念：

顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中

2.定义：

 （1）数据类型定义：

typedef struct   //定义数据类型
{
	int size;
	int capability;
}Seqlist;

 （2）顺序表的定义：

#define  _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>

typedef struct   //定义数据类型
{
	int size;
	int capability;
}Seqlist;

typedef int SLDataType;
typedef struct SeqList
{
    SLDataType* a;
	int size;     // 有效数据个数
	int capacity; // 空间容量

}SL;              //命名了一个数据类型为struct Seqlist的叫SL的顺序表

二.顺序表的初始化与销毁

1.初始化：

以下是将初始化分装为函数并且在text.c里调用以便调试（接下来会有很多处这样的分装）

这里有一个非常值得注意的地方：就是对于顺序表的传址调用是用的一级指针，而在后续的链表却使用的是二级指针，这其中主要的原因是：

‌两者在内存管理方式上的差异。‌

顺序表和链表的基本概念和操作方式
‌顺序表‌：顺序表是将数据依次存储在连续的整块物理空间中，通过计算地址可以直接访问任何数据元素。顺序表的尾插操作是通过调整数组的容量和索引来实现的，不需要改变原有指针的指向，因此传递一级指针即可
‌链表‌：链表是通过节点之间的链接来存储数据，每个节点包含数据部分和指向下一个节点的指针。链表的尾插操作需要创建一个新节点，并将其链接到链表的末尾，同时更新尾指针。由于需要修改指针的指向，因此必须传递二级指针（即指针的地址）

如果这里不太理解的话不用担心，下面还会进行详细介绍的

2.销毁（置0）：

不同于链表的销毁，顺序表的销毁只不过是将原有的数据清零（覆盖），而顺序表需要通过使用free函数释放掉每个结点的内存（在顺序表的介绍里我会不时地提到链表，一是因为这俩确实很像，同时也方便你对这俩兄弟的理解，所有如果对于链表还不了解的兄弟可以适当忽略我在这里写的话，后面自然而然就会懂了，加油）

三.顺序表的头/尾部的插入与删除

1.尾插（从顺序表尾部插入）：

void SLPushBack(SL* ps, SLDataType x)
{

	//方法一,判断用户传入的是否为空指针
	//if (ps == NULL)
	//{
	//	return;
	//}
	//方法二
	assert(ps);

	//ps->arr[ps->size++] = x;
	//插入数据前看空间够不够
	if(ps->capacity==ps->size)
	{
		//申请空间
		int newCapacity = ps->capacity == 0 ? 4 : 2*sizeof(SLDataType);//防止初始化的capacity为0（也可以直接在初始化就申请）
		//ps->arr = realloc(ps->arr, newCapacity * sizeof(SLDataType));
		//万一申请空间不成功（malloc申请空间不一定成功）
		SL*tmp =(SL*) realloc(ps->arr, newCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc failed!");
			exit(1);//直接退出程序
		}
		//空间申请成功
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
	ps->arr[ps->size++] = x;
}

别紧张，虽然代码量看着比较多，但也就那几个部分，我在这里详细讲讲这个尾插的解法，其他的代码就会很简单了

第二部分如果后续觉得在每一个插入的地方都重复使用的话会显得有些繁琐，所以这里我们也可以单独把他拎出来封装成另外一个函数（即我们的检验扩容函数）

同时我再说一下那个三目操作符为什么是2 * sizeof(SLDataType)，主要是通过数学逻辑证明每次扩大二倍的效率最高

//检验，扩容
void SLCheckCapacity(SL* ps)
{
    //插入数据前看空间够不够
	if (ps->capacity == ps->size)
	{
		//申请空间
		int newCapacity = ps->capacity == 0 ? 4 : 2 * sizeof(SLDataType);//防止初始化的capacity为0（也可以直接在初始化就申请）
		//ps->arr = realloc(ps->arr, newCapacity * sizeof(SLDataType));
		//万一申请空间不成功（malloc申请空间不一定成功）
		SL* tmp = (SL*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc failed!");
			exit(1);//直接退出程序
		}
		//空间申请成功
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}

2.头插（理解了尾插后头插就会显得容易多了）：

//头插
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	//先让顺序表中已有的数据往后挪动一位
	for (int i = ps->size; i>0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];//为了确保最后一次挪动为arr[0]=arr[1],故i的范围要注意
	}
	ps->arr[0] = x;
	ps->size++;//插入数据的同时也要使size跟着变动
}

3.尾删：

//尾删
void SLPopBack(SL* ps)
{
	assert(ps && ps->size);//尾删时一个要注意的时顺序表本身不为空，另外一个里面的有效数据个数（size）不为0
	--ps->size;
}

注意：这里assert的两个限制条件都是为了确保顺序表里有元素的存在

4.头删：

//头删
void SLPopFront(SL* ps)
{
	assert(ps && ps->size);//顺序表不为空
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];//所有数据向前挪动一位，比如arr[1]=arr[0]
	}
	--ps->size;//有效数据再减一，兄弟，这里是真的容易忘（捂脸）
}

注意：最后一个有效数据减一

四.顺序表指定位置的插入和删除

1.指定位置的插入：

//指定位置插入数据
void SeqListInsert(SL* ps, int pos, SLDataType x)//pos是下标
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	SLCheckcapacity(ps);//正常检查空间是否充足
	int i = 0;
	for (i = pos; i < ps->size; i++)
	{
		ps->arr[i + 1] = ps->arr[i];
	}//使pos后面的数据一起往后挪动一位
	ps->arr[pos] = x;
	++ps->size;
}

2.指定位置的删除：

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

五.对顺序表中的数据的查找

//查找
int SeqListFind(SL* ps, SLDateType x)
{
	int i = 0;
	for (i = 0;i < ps->size;i++)
	{
		if (ps->arr[i] == x)
		{
			return i;
		}
	}//遍历整个顺序表
	return 0;//没找到
}

其实只要把开头的尾插搞懂，下面的一系列代码也就迎刃而解了，跟做减法一样

六.总结

顺序表要预先分配空间，会导致空间闲置或溢出，采用随机存取，

时间复杂度为O(1),但删除和插入要一项一项的移动，时间复杂度为O(n)

适用情况

1.表长变化不大，且能事先确定变化的范围

2.很少进行插入或删除操作，经常按元素序号访问数据元素