数据结构（初阶）第二节：顺序表

从本文正式进入对数据结构的讲解，开始前友友们要有C语言的基础，熟练掌握动态内存管理、结构体、指针等章节，方便后续的学习。

顺序表（Sequence List）

线性表的概念：线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是⼀种在实际中⼴泛使⽤的数据结构，常⻅的线性表：顺序表、链表、栈、队列、字符串...线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

线性表是对存储具有某种共同点的数据集合的统称，顺序表和数组就是线性表的一种。顺序表的底层逻辑是利用数组实现的，但是相较于数组，顺序表的功能更齐全、丰富，顺序表新增了增、删、查、改等功能。

顺序表的分类

根据定义格式的不同，顺序表又可分为静态顺序表和动态顺序表。

静态顺序表

#include <stdio.h>

struct SeqList//定义顺序表
{
	int arr[10];//定长数组
	int size;//顺序表中有序的元素个数
};

静态顺序表的缺陷：空间给少了不够⽤，给多了造成空间浪费。静态顺序表的定义方式已经基本被淘汰，现在大多采用动态顺序表的定义方式。

动态顺序表

动态顺序表不同于静态顺序表，它很好的解决了空间浪费的问题，动态顺序在定义时不直接指明内存空间的大小（在初始化时有一定的空间），而是根据需求通过动态内存分配的方式开辟内存，等到存储空间不够时再扩容。

#include <stdio.h>

typedef int SLDateType;

typedef struct SeqList
{
	SLDateType* a;//动态数组
	int size;//有效元素个数
	int capacity;//已经开辟的空间大小
}SL;

在一开始定义时，使用typedef关键字对数据类型和结构体重命名，方便后续修改，比如说将存储int的数组改为存储char的数组，只需要将typedef int SLDateType中的int改为char即可，可以提高开发效率。

顺序表的功能

初始化

在初始化时，我们选择malloc函数为数组分配内存，初始的内存空间一般定义为4个字节的大小。

注意：在对初始化函数传参时一定要传地址值，也就是参数一定是指针变量，不能直接将非指针变量传递过去，因为形参和实参不在同一块内存空间中，直接传参的话会导致初始化失败，程序报错。
void SLinit(SL* ps)
{
	ps->a = malloc((sizeof(SLDateType)) * 4);//初始内存4个字节
	if (ps->a == NULL)//分配内存失败
	{
		perror("malloc fail");
		return;
	}
	ps->capacity = 4;
	ps->size = 0;
}

扩容

在对顺序表进行扩容时应该首先判断该情况下是否需要扩容，即ps->capacity == ps->size，判断之后使用realloc函数进行扩容，每次扩容应为上一次的两倍。
void SLcheckCapcity(SL* ps)
{
	if (ps->capacity == ps->size)//判断是否需要扩容
	{
		SLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * ps->capacity * 2);//一般每次扩容到上一次的2倍
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		ps->a = tmp;
		ps->capacity *= 2;
	}
}

头插

在顺序表的头部插入一个元素，其余元素按顺序向后移动。
void SLpopFront(SL* ps, SLDateType x)
{
	assert(ps);
	SLcheckCapcity(ps);
	for (int i = ps->size; i >= 1; i--)
	{
		ps->a[i] = ps->a[i - 1];
	}
	ps->a[0] = x;
	ps->size++;
}

尾插

顺序表尾部插入元素，在尾部插入时就一定要进行数组扩容。通过调用SLpopBack函数在尾部插入元素，ps->size最开始指向0索引，每次插入元素时size总在最后一个有效元素的下一位。
void SLpopBack(SL* ps, SLDateType x)
{
	assert(ps);
	SLcheckCapcity(ps);
	ps->a[ps->size++] = x;
}

头删

从顺序表头部删除元素，将元素按顺序前移，覆盖要删除的元素。
void SLpushFront(SL* ps)
{
	assert(ps && ps->size);//当顺序表为空时不用删除元素
	for (int i = 1; i < ps->size; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}

尾删

void SLpushBack(SL* ps)
{
	assert(ps && ps->size);
	ps->size--;
}

销毁

void SLdestory(SL* ps)
{
	free(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->size = 0;
}

打印顺序表

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

示例

int main()
{
	SL p;
	SLinit(&p);

	printf("这是尾插:");//尾插1 2 3 4 5
	SLpopBack(&p, 1);
	SLpopBack(&p, 2);
	SLpopBack(&p, 3);
	SLpopBack(&p, 4);
	SLpopBack(&p, 5);
	SLprint(&p);

	printf("这是头插:");//头插6 7 8
	SLpopFront(&p, 8);
	SLpopFront(&p, 7);
	SLpopFront(&p, 6);
	SLprint(&p);

	printf("这是头删:");//头删6 7 8
	SLpushFront(&p);
	SLpushFront(&p);
	SLpushFront(&p);
	SLprint(&p);

	printf("这是尾删:");//尾删3 4 5
	SLpushBack(&p);
	SLpushBack(&p);
	SLpushBack(&p);
	SLprint(&p);

	SLdestory(&p);

	return 0;
}

运行结果：