当前位置：网站首页>Implementation of a sequence table

The implementation of the sequence table can generally be divided into two types：静态的顺序表(It is stored in the form of a fixed-length array) 和 动态的顺序表(使用动态开辟的数组进行存储)

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

About the frame structure：

The basic function of the sequence table 增删查找改插入几大功能,We do this with functions 下面我们先来对 Structure is constructed, One more declaration of the base function,This completes the basic framework.

typedef struct SeqList
{
	int* a;
	int size;  // 存储数据的个数
	int capicity;  // Because we have a dynamic sequence table here,We need a capacity.
}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);

Construction of basic functions

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.尾插（Insert data from the tail）

Because we have a dynamic sequence table here Think about it when inserting data 我们的capicity容量是否充足？

Here we are going to use a function;void CheckCapacity(SL* psl)

Determine whether there is enough memory area for inserting data 不够的话 We will do dynamic expansion;

检查扩容

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;
	}
}

Now let's construct the tail plug again：

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

4.尾删

这个比较简单,We explained earlier in the struct size is used to count data;It is based on when we print the data size 来进行打印的.Now since the issue of printing data is mentioned So let's write a function that prints data first

打印数据

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 to reduce 就行了;因为我们是根据sizeThe size of the data to determine the storage.

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

5.头插

在 Insert a data at the beginning; 同样是插入同样也需要检查扩容;Actually here's the head plug 效率不高 Also traverse the mobile data;

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.顺序表查找

Find the subscript where a data is located 返回值为 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

Insert to cite 检查扩容

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遍历数组从 This subscript position 依次向前覆盖;

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--;
}