---

前言

数据结构中的线性表是数据结构基础的开始，也是我们在后续学习中需要多次实现的内容，其中的常见接口我们需要熟练掌握，本文将从概念性质、概念图解、接口代码等方面来讲解线性表中的顺序表的知识内容

---

1.线性表

1.1线性表的概念&理解

定义：线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。

线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。

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

PS:线性表在逻辑上是线性结构，有就是说，若果我们用一条线将各个元素连在一起，可以拉成一条直线，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

1.2线性表的图解

图解：
1.1线性的感官认识

1.2链表的结构展示（逻辑结构）

图中接头的存在就是逻辑结构，我们通过箭头的绘制，使得这些数据直观的看起来连成一条直线，但实际上，链表在内存中的存储形式，可能并非如此整齐，例如下图

1.3链表的结构展示（物理结构）图中的地址值仅是举例使用，并非有效真实数据

1.4顺序表

---

2.顺序表

2.1顺序表的概念&结构

定义：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

我们面对的顺序表常见为两种情况：
①静态顺序表

②动态顺序表：

---

2.2顺序表接口的实现

顺序表中的我们需要对其进行一系列接口（函数）的实现，而这些接口在我们后续的链表，队列等地方都需要实现这些接口以及对这些接口的改变，所以接口的实现是至关重要的。

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

首先我们创建顺序表结构：

typedef int SQDataType;
typedef struct SeqList
{
	SQDataType * a;//指向动态开辟的数组空间
	int size;//有效数据个数，当前顺序表以及存储元素个数
	int capacity;//顺序表容量空间大小：
}SLT;

2.2.1顺序表的初始化

void SeqListInit(SLT* ps1)
{
	assert(ps1 != NULL);//当为假时报错；
	ps1->a = NULL;
	ps1->size = ps1->capacity = 0;
}

2.2.2顺序表判断空间是否已满，进行增容

SeqListCheckCapacity(SLT * ps1)//判断是否需要增容
{
	assert(ps1);

	if (ps1->size == ps1->capacity)
	{
		size_t newcapacity = ps1->capacity == 0 ? 4 : ps1->capacity * 2;
		//一般增容时，增容为当前存储能力的两倍：
		ps1->a = realloc(ps1->a, newcapacity*sizeof(SQDataType));
		ps1->capacity = newcapacity;
	}
}

2.2.3顺序表的尾插

void SeqListPushBack(SLT* ps1, SQDataType x)///尾插
{
	assert(ps1);
	SeqListCheckCapacity(ps1);//判断是否需要增容
	ps1->a[ps1->size] = x;
	ps1->size++;

}

2.2.4顺序表的尾删

void SeqListPopBack(SLT* ps1)//尾删
{
	assert(ps1);
	//ps1->a[ps1->size - 1] = 0;
	//这一句代码可以不写，因为可以只将当前的有效数字记录减一，这里的数据我们就不看它了，它依然存在；因为如果这里数据不再是int型的数据，而是其他类型的数据不能直接用0覆盖(结构体等)
	ps1->size--;
}

2.2.5顺序表的头插

void SeqListPushFront(SLT* ps1, SQDataType x)//头插
{
	assert(ps1);

	SeqListCheckCapacity(ps1);//判断是否需要增容

	int end = ps1->size - 1;//将顺序表数组中的数据后移
	while (end >= 0)
	{
		ps1->a[end + 1] = ps1->a[end];
		end--;
	}

	ps1->a[0] = x;//实现头插
	ps1->size++;

}

2.2.6顺序表的查找

int SeqListFind(SLT* ps1, SQDataType x)//查找函数
{
	assert(ps1);
	for (int i = 0; i < ps1->size; i++)//循环判断，不断后移判断元素
	{
		if (ps1->a[i] == x)
		{
			return i;
		}
	}

	return -1;
}

2.2.7顺序表在pos位置插入x

void SeqListInsert(SLT* psl, size_t pos, SQDataType x)
{
	assert(psl);
	assert(pos <= psl->size && pos >= 0);
	SeqListCheckCapcity(psl);

	size_t end = psl->size;//size_t为无符号数据类型
	while (end > pos)
	{
		psl->a[end] = psl->a[end-1];
		--end;
	}

	psl->a[pos] = x;
	psl->size++;
}

2.2.8顺序表删除pos位置的值

void SeqListErase(SLT*ps1, size_t pos)//指定位置删除
{
	assert(ps1);
	assert(pos < ps1->size);

	size_t begin = pos + 1;
	while (begin < ps1->size)
	{
		ps1->a[begin - 1] = ps1->a[begin];
		begin++;
	}

	ps1->size--;
}

2.2.9顺序表的销毁

void SeqListDestory(SLT* ps1)
{
	assert(ps1 != NULL);//当为假时报错；
	if (ps1->a)
		free(ps1->a);

	ps1->size = ps1->capacity = 0;
}

2.2.10顺序表的打印

void SeqListPrint(SLT * ps1)
{
	assert(ps1);
	for (int i = 0; i < ps1->size; i++)
	{
		printf("%d ", ps1->a[i]);
	}
	printf("\n");
}

---

2.3顺序表的缺点

①当我们使用动态内存函数实现创建顺序表时，当判断当前内存不足时，增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了1个数据，后面没有数据插入了，那么就浪费了99个数据空间。

②每一次增容需要申请新空间，拷贝数据，释放旧空间，会造成一定的消耗。

③当我们在执行插入接口时，如果指定的位置是中间或者头部，那么我们在移动数据时，其时间复杂度为O(N)。

如果我们想要避免这些问题，那么我们可以采用链表的形式解决。

---

总结

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

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

③链表在实现时，会造成内存空间浪费 ，时间复杂度较高等一系列缺点，而这些缺点我们可以通过链表来解决。

---

以上就是我对这种方法的个人理解

上述内容如果有错误的地方，还麻烦各位大佬指教【膜拜各位了】【膜拜各位了】