Implementation of sequence table

1. The linear table

The linear table （linear list） yes n A finite sequence of data elements with the same characteristics .

Linear table is a kind of widely used in practice Data structure used , Common linear tables ： The order sheet 、 Linked list 、 Stack 、 queue 、 character string ... A linear table is logically a linear structure , That is to say, it is a continuous straight line . But it is not necessarily continuous in physical structure , When a linear table is physically stored , It is usually stored in the form of array and chain structure .

2. The order sheet

2.1 Concept and structure

A sequence table is a linear structure in which data elements are sequentially stored in a section of storage cells with continuous physical addresses , Generally, array storage is used Store . Add, delete, check and modify the data on the array . The order table can be divided into ：

1. Static sequence table ： Use a fixed length array to store elements .

2. Dynamic sequence table ： Use dynamic array storage .

2.2 Interface implementation

The static sequence table is only applicable to the scenario where you know how much data needs to be stored . A fixed length array of a static order table results in N It must be big , empty There is too much waste in the room , It's not enough . Therefore, in reality, dynamic sequence tables are basically used , Dynamically allocate space as needed size , So let's implement the dynamic sequence table .

 

The first thing we need to do is initialize and destroy the sequence table , This step is best done in succession , Because this can prevent yourself from forgetting to release

void SLInit(Seqlist* psl)
{
	psl->a =NULL;
	psl->capacity = 0;
	psl->sz = 0;
}

void SLdestory(Seqlist* psl)
{
	if (psl->a != NULL)
	{
		free(psl->a);
		psl->a = NULL;
		psl->capacity = 0;
		psl->sz = 0;
	}
}

We have to check the capacity increase before inserting , So we can write a function independently , Let each function run independently

void checkcapacity(Seqlist* psl)// Check the capacity increase 
{
	assert(psl);
	if (psl->sz == psl->capacity)
	{
		int newcapacity = psl->capacity == 0 ? 4 : 2 * psl->capacity;
		SLDatatype* tmp = (SLDatatype*)realloc(psl->a, newcapacity * sizeof(SLDatatype));
		if (tmp == NULL)
		{
			perror("realloc fail");// Prevent expansion failure 
			return;
		}
		else
		{
			psl->a = tmp;
			psl->capacity = newcapacity;
		}
	}
}

Below is our head plug deletion , The tail is inserted and deleted

void SLpophead(Seqlist* psl)// Head deletion 
{
	assert(psl);
	checkcapacity(psl);
	int begin = 0;
	while (begin < psl->sz - 1)
	{
		psl->a[begin] = psl->a[begin + 1];
		++begin;
	}
	psl->sz--;
}

void SLpushhead(Seqlist* psl, SLDatatype x)// Head insertion 
{
	assert(psl);
	checkcapacity(psl);
	int end = psl->sz-1;
	while (end--)
	{
		psl->a[end+1] = psl->a[end];
	}
	psl->a[0] = x;
	psl->sz++;
}

void SLpushback(Seqlist* psl, SLDatatype x)// Tail insertion 
{
	assert(psl);
	checkcapacity(psl);
	psl->a[psl->sz] = x;
	psl->sz++;
}

void SLpopback(Seqlist* psl)// Deletion at the end 
{
	assert(psl);
	assert(psl->sz > 0);
	psl->sz--;
}

After that, it can be printed out for easy observation , Then there is the function of printing

void SLPrint(Seqlist* psl)
{
	int i = 0;
	for (i = 0; i < psl->sz; i++)
	{
		printf("%d ", psl->a[i]);
	}
}

Simple plug and tail deletion obviously does not meet our requirements when processing data

Now let's delete and insert anywhere

void SLInsert(Seqlist* psl,size_t pos, SLDatatype x)// Insert at any position 
{
	assert(psl);
	assert(pos <= psl->sz);
	checkcapacity(psl);
	size_t end = psl->sz ;
	while (end >pos)
	{
		psl->a[end] = psl->a[end-1];
		end--;
	}
	psl->a[pos] = x;
	psl->sz++;
}

void SLErase(Seqlist* psl, size_t pos)// Delete anywhere 
{
	assert(psl);
	assert(pos < psl->sz);
	size_t begin = pos;
	while (begin < psl->sz-1)
	{
		psl->a[begin] = psl->a[begin + 1];
		++begin;
	}
	psl->sz--;
}

The code of deleting the tail of the plug can be modified , Just call anywhere to delete , The inserted function can be modified ,

So what's the significance of making a head and tail deletion function alone ?

In fact, this is also meaningful , Because when dealing with data, we often choose head plug deletion and tail insertion deletion . So it's better to encapsulate a function independently .