顺序表的实现

目录

序言

关于框架结构：

基本函数的构建

1.初始化数据

2.销毁数据 

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

 检查扩容

4.尾删

打印数据

 尾删  

5.头插 

6.头删

7.顺序表查找

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

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

改进和优化

---

序言

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

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

 静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致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--;
}

改进和优化

我们知道 我们数据表里的数据 不一定都是整形 为了方便我们对数据进行修改；

我们可以预先用  #define 来 定义 类型的名称；

以上代码 断言部分并不充分，需要进行优化。