Addition, deletion, check and modification of sequence table

One Preface

Sequence table is a kind of data structure . It's essentially an array . Because it is continuous in memory , Data is also stored continuously . Next, add, delete, check and modify this data structure .

We first create a dynamic array , Easy to store data . Dynamic array can avoid frequent capacity increase due to insufficient capacity , It can also reduce the waste of capacity .

typedef int SLDataType;
typedef struct slist
{
	SLDataType*a;
	int size;
	int capacity;
}SL;

Because the type of data stored in the sequence table is unknown , So first assume that this sequence table is used to store int Type of data .

Two Tail insertion

The basic idea of tail insertion ： Tail insertion is at the end of the array . Subscript to be size Insert a data at the position of . But when inserting data , If the array is full , Then you need to expand the capacity of the array to store data .

Expansion of array : Generally, the expansion capacity is twice the current capacity . Because the capacity of the array is initialized to 0, Therefore, what needs to be considered is , If it is the first expansion , There is no point in expanding two cups . Therefore, the array capacity needs to be 0 Consider this situation alone .

It should be noted that , Because the data has been stored in the array , Therefore, the number of data stored in the array size It will change .

Illustration of tail interpolation ：

 

void SlistCapacityCheck(SL* ps)
{
	assert(ps);

	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newcapacity);
		assert(tmp);
		ps->capacity = newcapacity;
		ps->a = tmp;
	}
}

void SlistBackPush(SL* ps, SLDataType data)
{
	assert(ps);

	SlistCapacityCheck(ps);

	ps->a[ps->size] = data;
	ps->size++;
}

3、 ... and Deletion at the end

The basic idea of tail deletion ： There are several assumptions about tail deletion ：

① Change the data of the tail position to other numbers . But this cannot be distinguished from the data that may have been saved before .

② Will store data in the array size--, Directly round off the last data .

Illustration of tail interpolation ：

 

Implementation of tail insertion  

void SlistBackPop(SL* ps)
{
	assert(ps);
	assert(ps->size);

	ps->size--;
}

Four Head insertion

The basic idea of head inserting ： First, the data in the original array , from size-1 To 0 The location of （ From back to front ） Move one data in turn .

If you move from front to back , Moving past data will overwrite the data to be moved .

After the array 0 There will be an extra vacancy in the position , Insert the required data .

It should be noted that , You need to consider the capacity problem when inserting data ！

The illustration ：

 

Realization

void SlistFrontPush(SL* ps, SLDataType data)
{
	assert(ps);

	SlistCapacityCheck(ps);

	int i = 0;
	for (i = ps->size; i >0; i--)
	{
		ps->a[i] = ps->a[i - 1];
	}

	ps->a[0] = data;
	ps->size++;
}

 

5、 ... and Head deletion

The basic idea ： Delete the words from 1 Start to size-1 Location data （ Before and after ） Move the size of one data forward in turn , In this way, the first data can be overwritten , And ensure that the data stored later will not be overwritten

It should be noted that , If the array is empty, you can't delete it anymore , Otherwise The inserted data is the location that was previously deleted , Unable to insert .

The illustration ：

 

Realization ：

void SlistFrontPop(SL* ps)
{
	assert(ps);
	assert(ps->size);

	int i = 0;
	for (i = 1; i < ps->size; i++)
	{
		ps->a[i - 1] = ps->a[i];
	}

	ps->size--;
}

6、 ... and Insert... At a specific location

The basic idea ： In fact, the basic idea is similar to head inserting , It is also necessary to move the data to vacate the location, and then insert the data in this location .

from size-1 To pos The location of the data , All move back one position , Then insert .

In fact, the operation of inserting data at a specific location can be reused as header insertion （ When a specific position is the first position of the array ） It can also be reused as tail insertion （ When a specific position is the last position of the array ）

Realization ：

void SlistPosInsert(SL* ps, SLDataType data,int pos)
{
	assert(ps);
	SlistCapacityCheck(ps);

	int i = 0;
	for (i = ps->size; i > pos; i--)
	{
		ps->a[i] = ps->a[i - 1];
	}

	ps->a[pos] = data;
	ps->size++;
}

7、 ... and Delete in a specific location

Same as above .

Code implementation ：

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

	int i = 0;
	for (i = pos  ; i < ps->size; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}

	ps->size--;
}

If it is operated at the head or tail , It can also be reused as header deletion and tail deletion .

It should be noted that , For the insertion and modification of specific positions , This position must be in the array .

8、 ... and Look up the sequence table

The basic idea ： Traversal search

int SlistFind(SL* ps, SLDataType data)
{
	assert(ps);

	int i = 0;
	while (i < ps->size)
	{
		if (ps->a[i] != data)
		{
			i++;
		}
		else
		{
			return i;
		}
	}
	return -1;
}

IX. modification of specific positions in the sequence table

void SlistModify(SL* ps, SLDataType data, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);

	ps->a[pos] = data;
}

Ten summary

The efficiency of tail insertion and tail deletion of sequence table is relatively high .

But there is a waste of space or frequent expansion in the sequence table .