当前位置：网站首页>顺序表的实现

顺序表的实现

2022-07-31 03:06:00 【蓝猫骑士】

序言

关于框架结构：

序言

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

顺序表的实现一般可以分为两种：静态的顺序表(采用定长数组的形式进行存储) 和 动态的顺序表(使用动态开辟的数组进行存储)

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

关于框架结构：

顺序表的基本功能增删查找改插入几大功能，我们用函数来实现下面我们先来对结构体进行构造, 再对基本函数进行一个声明，以此来完成基本框架。

typedef struct SeqList
{
	int* a;
	int size;  // 存储数据的个数
	int capicity;  // 因为我们这里是一个动态的顺序表，我们需要一个容量。
}SL;

// 初始化
void SeqListInit(SL* psl);
// 检查空间，如果满了，进行增容
void CheckCapacity(SL* psl);
// 顺序表尾插
void SeqListPushBack(SL* psl, int x);
// 顺序表尾删
void SeqListPopBack(SL* psl);
// 顺序表头插
void SeqListPushFront(SL* psl, int x);
// 顺序表头删
void SeqListPopFront(SL* psl);
// 顺序表查找
int SeqListFind(SL* psl, int x);
// 顺序表在pos位置插入x
void SeqListInsert(SL* psl, size_t pos, int x);
// 顺序表删除pos位置的值
void SeqListErase(SL* psl, size_t pos);
// 顺序表销毁
void SeqListDestory(SL* psl);
// 顺序表打印
void SeqListPrint(SL* psl);

基本函数的构建

1.初始化数据

将 a 指针置为空以及把size 和 capicity 的大小置为 0 ；

void SeqListInit(SL* psl)
{
	assert(psl);
	psl->a = NULL;
	psl->size = psl->capicity = 0;
}

2.销毁数据

void SeqListDestory(SL* psl);

void SeqListDestory(SL* psl)
{
	if (psl->a)
	{
		free(psl->a);
		psl->a = NULL;
		psl->capicity = psl->size = 0;
	}
}

3.尾插（从尾部进行插入数据）

因为我们这里是动态的顺序表插入数据的时候要考虑一下我们的capicity容量是否充足？

这里我们要用到一个函数；void CheckCapacity(SL* psl)

判断是否有足够的内存区进行插入数据不够的话我们将进行动态的扩容；

检查扩容

void CheckCapacity(SL* psl)

void CheckCapacity(SL* psl)
{
	assert(psl);
	if (psl->capicity == psl->size)
	{
		int newcapicity = psl->size == 0 ? 4 : (psl->size) * 2;
		int* tmp = (int*)realloc(psl->a,sizeof(int)*newcapicity);
		if (tmp == NULL)
		{
			perror("ralloc fail");
			return;
		}
		psl->a = tmp;
		psl->capicity = newcapicity;
	}
}

现在我们再来构造尾插：

void SeqListPushBack(SL* psl, int x)
{
	assert(psl);
	CheckCapacity(psl);
	psl->a[psl->size] = x;
	psl->size++;
}

4.尾删

这个比较简单，我们前面说明了结构体中的 size 是用来对数据进行计数的；我们打印数据的时候就是根据 size 来进行打印的。现在既然提到了打印数据的问题那么我们先写一个打印数据的这个函数

打印数据

void SeqListPrint(SL* psl);

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

尾删

直接把 size 进行减减就行了；因为我们是根据size的大小来判断数据的存储。

void SeqListPopBack(SL* psl)
{
	assert(psl);
	if (psl->size == 0)
	{
		return;
	}
	psl->size--;
}

5.头插

在开头插入一个数据；同样是插入同样也需要检查扩容；其实这里的头插效率不高还要遍历挪动数据；

void SeqListPushFront(SL* psl, int x)
{
	assert(psl);
	CheckCapacity(psl);
	int i = 0;
	for (i = psl->size+1; i > 0; i--)
	{
		psl->a[i] = psl->a[i-1];
	}
	psl->a[0] = x;
	psl->size++;
}

6.头删

void SeqListPopFront(SL* psl)
{
	assert(psl);
	assert(psl->size > 0);
	int i = 0;
	for (i = 0; i < psl->size-1;i++)
	{
		psl->a[i] = psl->a[i + 1];
	}
	psl->size--;
}

7.顺序表查找

查找一个数据所在的下标返回值为 int 如果不存在则返回 -1。

int SeqListFind(SL* psl, int x)
{
	assert(psl);
	int i = 0;
	for (i = 0; i < psl->size; i++)
	{
		if (psl->a[i] == x)
			return i;
	}
	return -1;
}

8.顺序表在pos位置插入x

插入要引用检查扩容

void SeqListInsert(SL* psl, size_t pos, int x)
{
	assert(psl);
	CheckCapacity(psl);
	size_t i = 0;
	for (i = psl->size + 1; i > pos; i--)
	{
		psl->a[i] = psl->a[i - 1];
	}
	psl->a[pos] = x;
	psl->size++;
}

9.顺序表删除pos位置的值

利用 SeqListFind 来找出 pos 位置的下标利用for遍历数组从此下标位置依次向前覆盖；

void SeqListErase(SL* psl, size_t pos)
{
	assert(psl);
	int A = SeqListFind(psl, pos);
	int i = 0;
	for (i = A; i < psl->size-1; i++)
	{
		psl->a[A] = psl->a[A + 1];
	}
	psl->size--;
}