数据结构（C）：玩转顺序表

🍺0.前言

🎷1.线性表

🎸2.顺序表

📀动态顺序表的实现

💿初始化

💿检查容量是否满了，进行扩容

💿插入：头插和尾插

💿删除：头删和尾删

💿查找

💿销毁

💿打印

💿在某处插入和删除

💎6.结束语

🍺0.前言

言C之言，聊C之识，以C会友，共向远方。各位博友的各位你们好啊，这里是持续分享数据结构知识的小赵同学，今天要分享的数据结构知识是顺序表，在这一章，小赵将会向大家展开聊聊顺序表。✊

🎷1.线性表

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

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

也就是说我们今天要谈的顺序表就属于我们的线性表。

🎸2.顺序表

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

顺序表一般可以分为：

1. 静态顺序表：使用定长数组存储元素。

2.动态顺序表：使用动态开辟的数组存储。

好了下面我们来看看究竟怎么样才是一个顺序表，其实很简单，小赵在这里给各位画个图

怎么样它的样子是不是非常的眼熟，没错我们的线性表其实就是我们的数组。那为什么有静态和动态之分呢？因为一个可以不断增长自己的内存，一个则是固定容量，那该如何实现呢？下面小赵将会带着大家去实现顺序表。

因为静态顺序表其实和动态的线性表差距不大，而且静态顺序表本身也并不常用（开大了浪费，开小了，不够），所以小赵在这里主要带着大家去实现我们的动态顺序表。

📀动态顺序表的实现

那么动态的顺序表该如何实现呢？在这里为了方便我们在后续知道什么时候该进行扩大我们的数组，我们就用我们的结构体去实现我们的线性动态表。

typedef int SeqDataType;
struct Seqlist
{
	SeqDataType* a;//指向动态开辟的数组
	int size;//顺序表已存元素个数
	int capacity;//顺序表容量
};

那么这样当我们的size 等于我们的capacity的时候我们就可以对我们的数组进行扩容了。

那么对于我们的顺序表，光有这个是不够的，还要具备增删查改，初始化等等功能，下面带着大家一一来实现

💿初始化：

首先是初始化的操作

typedef struct Seqlist SL;
void InitSeq(SL* psl)
{
	assert(psl);//防止传入空指针
	psl->a = NULL;
	psl->capacity = 0;
	psl->size = 0;
}

💿检查容量是否满了，进行扩容

void SLCheckcapacity(SL* psl)
{
	assert(psl);
	if (psl->capacity == psl->size)
	{
		int newcapacity = (psl->capacity==0?4: psl->capacity *2);//如果原容量为零则返回4，其他返回原容量的两倍
		SeqDataType *tmp = (SeqDataType*)realloc(psl->a ,sizeof(SeqDataType) *newcapacity);//reallc新数组
		if (tmp == NULL)
		{
			perror("malloc failed");
			return;
		}
		psl->a = tmp;
		psl->capacity = newcapacity;
	}
}

💿插入：头插和尾插

这里的头插要稍微注意一下，就像我们站个队，忽然要我们在前面给个位子一样，那么我们是不是后面的人都要向后移动，那么如何向后移动呢，如果是从头移动，我们会发现下面的问题。

我们会发现我们前面的数字会盖住后面的数字，那么这里最后的办法就是后面向后移动，给出位子。

然后就可以顺利解决了。代码如下

void SLPushFront(SL* psl, SeqDataType x)
{
	assert(psl);
	SLCheckcapacity(psl);//检查容量
	int n = psl->size-1;
	while (n--);//将所有元素向后移动
	{
		psl->a[n + 1] = psl->a[n];
	}
	psl->a[0] = x;
	psl->size++;
}

尾插就相对比较容易了。

void SLPushBack(SL* psl, SeqDataType x)
{
	assert(psl);
	SLCheckCapacity(psl);
	psl->a[psl->size++] = x;
}

💿删除：头删和尾删

这里的头删的思路和我们的头插的思路很像，只是这里是头边有空位

void SLPopFront(SL* psl)
{
	assert(psl);
	assert(psl->size);//防止元素个数为0
	int n = 1;
	while (n < psl->size)
	{
		psl->a[n-1] = psl->a[n];//把后面的往前移
        n++;
	}
	psl->size--;
}

尾删则相对容易些：

void SLPopBack(SL* psl)
{
	assert(psl);
	assert(psl->size);//防止元素个数为0
	psl->size--;
}

💿查找：

int SLFind(SL* psl, SeqDataType x)
{
	assert(psl);
	int n = 0;
	while (n<psl->size)
	{
		if (psl->a[n] == x)//找到了返回对应位置
			return n;
		n++;
	}
	return -1;//找不到
}

💿销毁：

void SLDestory(SL* psl)
{
	assert(psl);
	free(psl->a);
	psl->a = NULL;
	psl->capacity = 0;
	psl->size = 0;
}

💿打印：

void SLPrint(SL* psl)
{
	assert(psl);
	int n = 0;
	while (n < psl->size)
	{
		printf("%d", psl->a[n]);
		n++;
	}
}

💿在某处插入和删除：

在某处的插入和删除对于逻辑的考察是有的，那么我们先看看如何进行插入：

比方说，我要在三这个位置进行插入操作，那么这个时候3，4，5这几个数字是不是要向后移动，那么其就很像我们的头删，都是从尾部开始向后移动，来完成的。

void SLInsert(SL* psl, int pos, SeqDataType x)
{
	assert(psl);
	assert(0 <= pos && pos <= psl->size);
	SLCheckcapacity(psl);
	int end= psl->size-1;
	while (end >= pos)
	{
		psl->a[end + 1] =psl->a[end];
		end--;
	}
	psl->a[pos] = x;
	psl->size++;
}

接下来是某个位置的删除，类比头删

void SLErase(SL* psl, int pos, SeqDataType x)
{
	assert(psl);
	assert(0 <= pos && pos < psl->size);
	int end = pos;
	while (end<psl->size-1)
	{
		psl->a[end] = psl->a[end+1];
		end++;
	}
	psl->size--;
}

然后我们还可以用这两个代码改我们原本的头尾插，头尾删

void SLPushFront(SL* psl, SeqDataType x)
{
	SLInsert(psl, 0, x);
}
void SLPushBack(SL* psl, SeqDataType x)
{
	SLInsert(psl, psl->size, x);
}
void SLPopFront(SL* psl)
{
	SLErase(psl, 0);
}
void SLPopBack(SL* psl)
{
	SLErase(psl, psl->size-1);
}