Implementation of sequencelist sequence table

The concept of sequence table is simply combed and discussed

Sequential table means that the elements in the table are stored consecutively ,c The built-in type array in the language can be said to be a sequential table , But it does not support dynamic growth , The advantage of this kind of data structure is that the elements in the table can be accessed randomly , You can directly find an element in the sequence table by subscript . Because it is stored tightly in memory , Generally speaking, the access sequence table has better spatial locality , Faster access . The disadvantages are still caused by their close connection in storage , If the sequence table is large , The requested memory space will be relatively long , And if there are many such data structures , It also causes memory fragmentation , Cause some memory waste . In addition, the size of the sequence table may not be predicted in advance , And dynamic development memory if one time development less , It may cause frequent memory development and slow running speed , And if more are opened up at one time , It may also waste some space .

Implementation of sequence table

The basic idea

To store data through arrays , A variable that records the size of the current sequence table and the capacity of a record sequence table .

The following is the function declaration of structure declaration and operation

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#define MINSIZE 4
typedef int DataType;
typedef struct SeqList SeqList;
typedef size_t Position;
struct SeqList
{
	DataType* data; 
	size_t size;
	size_t capacity;
};

void SeqListInit(SeqList* L, size_t S);
void SeqListPushBack(SeqList* L, DataType D);
void SeqListPopBack(SeqList* L);
void SeqListPushFront(SeqList* L, DataType D);
void SeqListPopFront(SeqList* L);
void SeqListInsert(SeqList* L, DataType D, Position P);
void SeqListErase(SeqList* L, Position P);
void SeqListPrint(SeqList* L);
void SeqListDestroy(SeqList* L);
DataType SeqListFind(SeqList* L, DataType D);
void ExpandCapacity(SeqList* L);
int IsEmpty(SeqList* L);
int IsFull(SeqList* L);

initialization ：

void SeqListInit(SeqList* L,size_t S)
{
	L->capacity = S > MINSIZE ? S : MINSIZE;
	L->data = (DataType*)malloc(sizeof(DataType) * L->capacity);
	L->size = 0;
}

Quick judgment Empty and full Function of ：

int IsEmpty(SeqList* L)
{
	return L->size == 0;
}
int IsFull(SeqList* L)
{
	return L->size == L->capacity;
}

Dynamic capacity ：

void ExpandCapacity(SeqList* L)
{
	DataType* tmp;
	tmp = (DataType*)realloc(L->data, sizeof(DataType) * 2 * L->capacity);
	if (tmp == NULL)
	{
		printf("FatalError:expand capacity failed!\n");
		exit(-1);
	}
	else
	{
		L->data = tmp;
		L->capacity *= 2;
	}
}

Tail insertion and tail deletion ：

void SeqListPushBack(SeqList* L, DataType D)
{
	assert(L);
	if (IsFull(L))
		ExpandCapacity(L);

	L->data[L->size] = D;
	L->size++;
}
void SeqListPopBack(SeqList* L)
{
	assert(L);
	if (!IsEmpty(L))
		L->size--;
}

Header insertion and header deletion ：

void SeqListPushFront(SeqList* L, DataType D)
{
	assert(L);
	if (IsFull(L))
		ExpandCapacity(L);

	size_t end = L->size;
	while (end > 0)
	{
		L->data[end] = L->data[end - 1];
		end--;
	}
	L->data[0] = D;
	L->size++;
}
void SeqListPopFront(SeqList* L)
{
	assert(L);
	if (!IsEmpty(L))
	{
		size_t begin = 0;
		while (begin < L->size)
		{
			L->data[begin] = L->data[begin + 1];
			begin++;
		}
		L->size--;
	}
}

Random access insert and random access delete ：

void SeqListInsert(SeqList* L, DataType D, Position P)
{
	assert(L);
	if (IsFull(L))
		ExpandCapacity(L);

	if (P<0 || P>L->size)
		printf("invaild position!\n");
	else
	{
		size_t end = L->size;
		while (end > P)
		{
			L->data[end] = L->data[end - 1];
		}
		L->data[P] = D;
		L->size++;
	}
}
void SeqListErase(SeqList* L, Position P)
{
	assert(L);
	if (!IsEmpty(L))
	{
		if (P<0 || P>L->size - 1)
			printf("invaild position!\n");
		else
		{
			while (P < L->size - 1)
			{
				L->data[P] = L->data[P + 1];
				P++;
			}
			L->size--;
		}
	}
}

Find value ：

int SeqListFind(SeqList* L, DataType D)
{
	assert(L);
	int i;
	for (i = 0; i < L->size; i++)
	{
		if (L->data[i] == D)
			return i;
	}
	return -1;
}

Print and destroy form ：

void SeqListDestroy(SeqList* L)
{
	assert(L);
	free(L->data);
	L->data = NULL;
	L->capacity = 0;
	L->size = 0;
}

void SeqListPrint(SeqList* L)
{
	int i;
	for (i = 0; i < L->size; i++)
	{
		printf("%d ", L->data[i]);
	}
	printf("\n");
}

Last but not least , Routines can be reused between routines , For example, head to tail insertion is a special case of random position insertion , Head deletion and tail deletion are special cases of random position deletion , You can use this to simplify your code , Enhanced readability and ease of debugging