顺序表和链表从零详细梳理(顺序表篇)-Toy模板网

这篇具有很好参考价值的文章主要介绍了顺序表和链表从零详细梳理(顺序表篇)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1、线性表

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

下面借助图形直观感受一下顺序表和链表的结构:
顺序表和链表从零详细梳理(顺序表篇),数据结构与算法,链表,数据结构,c语言

2、顺序表

2.1 概念和结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表有静态和动态两种。
1.静态顺序表:使用定长数组存储元素。
顺序表和链表从零详细梳理(顺序表篇),数据结构与算法,链表,数据结构,c语言
2.动态顺序表:使用动态开辟的数组存储元素。

其中在存储过程中都会存在空间不够的情况，通常情况下我们用realloc(C语言的一个重点，后面复习会单独写博客来详细介绍)来扩容。

其中呢，realloc有两种扩容方式:
a.原地扩容:其效率非常高。
顺序表和链表从零详细梳理(顺序表篇),数据结构与算法,链表,数据结构,c语言

b.异地扩容:相较于原地扩容来讲，效率会低一些。
要用到异地扩容的原因是因为后面的空间已经分配给别人了，所以此方法是将原有空间拷贝到异地，再将原空间释放，最终会返回新的地址。

因此要判断扩容类型也很简单:
只需要验证返回地址即可。
顺序表和链表从零详细梳理(顺序表篇),数据结构与算法,链表,数据结构,c语言
下面我们一起通过两个例子看看如何通过地址判断是原地扩容还是异地扩容。

原地扩容:
顺序表和链表从零详细梳理(顺序表篇),数据结构与算法,链表,数据结构,c语言
异地扩容:

注意一点: realloc在异地扩容的时候，会自动释放空间，不需要我们去判断空间是否相等来决定是否需要释放。

2.2 接口实现

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

typedef int SLDataType;
// 顺序表的动态存储
typedef struct SeqList
{
SLDataType* array; // 指向动态开辟的数组
size_t size ; // 有效数据个数
size_t capicity ; // 容量空间的大小
}SL;
// 基本增删查改接口
// 顺序表初始化
void SLInit(SeqList* psl);
// 检查空间，如果满了，进行增容
void SLCheckCapacity(SeqList* psl);
// 顺序表尾插
void SLPushBack(SeqList* psl, SLDataType x);
// 顺序表尾删
void SLPopBack(SeqList* psl);
// 顺序表头插
void SLPushFront(SeqList* psl, SLDataType x);
// 顺序表头删
void SLPopFront(SeqList* psl);
// 顺序表查找
int SLFind(SeqList* psl, SLDataType x);
// 顺序表在pos位置插入x
void SLInsert(SeqList* psl, size_t pos, SLDataType x);
// 顺序表删除pos位置的值
void SLErase(SeqList* psl, size_t pos);
// 顺序表销毁
void SLDestory(SeqList* psl);
// 顺序表打印
void SLPrint(SeqList* psl);

有了整体框架之后,我们就能更清晰地去实现顺序表了。
下面让我们一起各接口的具体实现方法吧!

2.2.1 顺序表初始化、销毁与打印

void SLInit(SL* psl)//初始化
{
	assert(psl);

	psl->a = NULL;
	psl->size = 0;
	psl->capacity = 0;
}

void SLDestroy(SL* psl)
{
	assert(psl);

	if (psl->a != NULL)
	{
		free(psl->a);
		psl->a = NULL;
		psl->size = 0;
		psl->capacity = 0;
	}
}

void SLPrint(SL* psl)
{
	assert(psl);

	for (int i = 0; i < psl->size; i++)
	{
		printf("%d ", psl->a[i]);
	}
	printf("\n");
}

2.2.2 检查空间容量(是否增容)

在这个地方我们加入一个 SLCheckCapacity 函数实现该接口功能。

void SLCheckCapacity(SL* psl)
{
	assert(psl);

	if (psl->size == psl->capacity)
	{
		int newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(psl->a, sizeof(SLDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}

		psl->a = tmp;
		psl->capacity = newCapacity;
	}
}

2.3 顺序表头插尾插

首先我们来看尾插,尾插就直接在后空间插入,空间不够的话有SLCheckCapacity函数接口检查,自动扩容插入就OK了。咱们直接上代码:

void SLPushBack(SL* psl, SLDataType x)
{
	assert(psl);

	SLCheckCapacity(psl);

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

但是头插就不太一样了,因为我们没有向前扩容的说法，更不允许这么做。所以我们想完成头插，就要挪动数据(将前面的数据往后挪)。
顺序表和链表从零详细梳理(顺序表篇),数据结构与算法,链表,数据结构,c语言
特别注意:size是指向最后一个数据的下一个位置。

void SLPushFront(SL* psl, SLDataType x)
{
	assert(psl);

	SLCheckCapacity(psl);

	// 挪动数据
	int end = psl->size - 1;
	while (end >= 0)
	{
		psl->a[end + 1] = psl->a[end];
		--end;
	}

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

2.4 顺序表的头删尾删

就如下图所示,想要把最后一个数据删除,我们只要把size从之前的5改为4就可以了,这其实就代表了改动之后只有前4个数据是有效的。

顺序表和链表从零详细梳理(顺序表篇),数据结构与算法,链表,数据结构,c语言
有一点需要注意:在这个地方,被删掉的数据的内存不需要free,也不能free。

原因是:申请的空间如果要释放,那么就要全部释放,不能只释放一个内存单元。(这样就不连续了)
同时呢,如果我们还要进行头尾查,被删除的数据所留下的那处空间也会被重新覆盖,不必麻烦。

OK，根据上述思路上代码:

void SLPopBack(SL* psl)
{
	assert(psl);

	// 空
	// 温柔的检查
	/*if (psl->size == 0)
	{
		return;
	}*/

	// 暴力检查:如果size小于0直接报错
	assert(psl->size > 0);
	
	psl->size--;
}

头删其实原理差不多了

void SLPopFront(SL* psl)
{
	assert(psl);

	// 暴力检查
	assert(psl->size > 0);

	int begin = 1;
	while (begin < psl->size)
	{
		psl->a[begin - 1] = psl->a[begin];
		++begin;
	}

	psl->size--;
}

2.5 顺序表插入(在pos插入x)

原理同样有挪动的思想在里面
顺序表和链表从零详细梳理(顺序表篇),数据结构与算法,链表,数据结构,c语言

void SLInsert(SL* psl, int pos, SLDataType x)
{
	assert(psl);
	assert(pos >= 0 && 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++;
}//pos是下标,size是数据个数，如果看做下标的话，它是最后一个数据的下一个位置

2.6 顺序表在pos处消除x

思想:后一个数据往前面一个数据覆盖(挪动覆盖)
顺序表和链表从零详细梳理(顺序表篇),数据结构与算法,链表,数据结构,c语言

void SLErase(SL* psl, int pos)
{
	assert(psl);
	assert(pos >= 0 && pos < psl->size);

	// 挪动覆盖
	int begin = pos + 1;
	while (begin < psl->size)
	{
		psl->a[begin - 1] = psl->a[begin];
		++begin;
	}

	psl->size--;
}