First, the concept of the sequence table

*(1)* The sequence table is a linear structure in which data elements are sequentially stored in a segment of storage units with consecutive physical addresses. Generally, array storage is used. Implement various functions on arrays

*(2)* Here we note that the sequence table has the word sequence because the biggest difference between it and the array is that the data elements are stored in sequence (that is, they are stored in sequence).
The sequence table can be divided into static sequence table and dynamic sequence table.

2. Static sequence table (skipable)

We first create an array and use several interface functions to complete the sequence table. The difference from the past is that the naming style of interface functions follows STL. The code is as follows

#define MAX 100
typedef int SLDataType;
typedef struct Seqlist
{
SLDataType a[MAX];
Int size
}SL;

This is the beginning of the creation of static arrays, and the originally complex noun Seqlist is written as SL through typedef (redefinition). At the same time, SLDataType better implements the trouble of replacing variables of other types later. Today, we focus on the realization of dynamic sequence table.

3. The dynamic idea of ​​dynamic sequence table

When the dynamic sequence table and the static sequence table are initially established, we will create a pointer a to point to this array because we need to meet the needs of re-expansion, and create a capacity to indicate how much space the array can actually store.

code show as below

typedef struct Seqlist
{
	SLDataType* a;
	int size;// Indicates how many "pieces" of data are stored in the array
	int capacity; // How much space can the array actually store data?
}SL;

Fourth, the initialization sequence table

When using the sequence table, we generally initialize it first to avoid unnecessary trouble later. code show as below

void SeqlistInit(SL* ps)
{
	ps->a = NULL;
	ps->size = ps->capacity = 0;// initialization
}

Fifth, check the expansion

(1) This is a dynamic sequence table, so we need to expand it when its data is full. This program will also be used in other interface functions later, so we write it out separately. At this point, note that since we have initialized capacity to 0 for the first time, when expanding the capacity again, newcapacity cannot be directly *0. code show as below

void SeqlistCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;// Expansion
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));// realloc counts bytes
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);// Here return is not good, exit directly terminates the program
		}

		ps->a = tmp;
		ps->capacity = newcapacity;
	}
}

(2) In this code, we first judge whether the capacity is 0, and assign it a value if it is 0. We assign 4 to it here. We choose to multiply the capacity by 2 times (it doesn't matter how much to multiply by 1.5 times, but 2 times is how to say it, it is very suitable for such a value, if it is smaller, the expansion will be frequent, and if it is expanded, it will cause a waste of space).
Some people will say that there is a problem with ps->a being NULL. In fact, it doesn't matter, don't worry, if the first parameter of the realloc function is empty, the realloc function is the same as malloc.
(3) If the development fails here, we use exit(-1) to end, and many times we write code to use return-1 to terminate. And here, if the development fails, we cannot proceed with the rest of the content, so here we use exit instead of return.

6. Realization of various functions

6.1 Tail insertion (deletion) sequence table

1. Tail insertion function: The first thing we need to do is to check whether the space is full. If it is full, we will expand the capacity. Here we first refer to the previous capacity expansion function.
Insert the X we want to insert into the array. Since size is the number of Yuan Xu, it is also the position of the element after the last element at the tail. So you can directly ++, the code is as follows:

void SeqlistPushBack(SL* ps, SLDataType x) // tail plug
{
	 SeqlistCheckCapacity(ps);
	     ps->a[ps->size] = x;
	     ps->size++; 
}

2. Tail deletion function: After the tail insertion function is successfully implemented, we can implement the tail deletion function. In the tail deletion function, we can change the last number to 0, and then reduce the size. The reduction before or after does not affect the actual result. And there are two methods, the code is as follows:

void SeqlistPopBack(SL* ps)
{
	
	/*  if (ps->size > 0)
	  {
		//ps->a[ps->size - 1] = 0; No problem with this
		ps->size--;
	   }
	*/  // method one

	assert(ps->size > 0); //If it is true, continue, if it is false, that is, <=0, it will terminate the program and indicate that the assertion failed.
	ps->size--;
}

6.2 Header insert (delete) function

1. Header function: As shown in the figure, we need to move the elements in the array to one position in turn, as shown in the figure (forgive me. The drawing is a bit abstract)

Here end points to the position of size-1, size is the number of array elements, minus one is to point to the last position, the code is implemented as follows

void SeqlistPushFront(SL* ps, SLDataType x)
{
	   SeqlistCheckCapacity(ps);
	    // mobile data
	     int end = ps->size - 1;
	     while (end >= 0)
	     {
		    ps->a[end + 1] = ps->a[end];
		    --end; // Front and rear can be
	     }
	     ps->a[0] = x;
	     ps->size++;
    }

2. Header delete function: move the next data forward, the code is as follows:

void SeqlistPopFront(SL* ps)
{
	assert(ps->size > 0);
	int begin = 1;               //begin = 0
	while (begin < ps->size)     // size - 1
	{
		ps->a[begin - 1] = ps->a[begin];  // begin begin + 1
		++begin;
	}
	ps->size--;
	// mobile data
}

6.3 Insert data

The first thing we should consider when inserting data is whether the array space is full and out of bounds. There are two methods as above. We still use the assertion method, as shown in the figure.

code show as below:

void SeqlistInsert(SL* ps, int pos, SLDataType x)
{
	/*   if (pos > ps->size || pos < 0)  out of bounds
	    {
		   printf("pos invalid\n");
		   return;
	    }
	*/      //two methods
	assert(pos >= 0 && pos <= ps -> size);

	SeqlistCheckCapacity(ps); // Insert considering expansion
	int end = ps->size - 1;
	// mobile data
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		--end;
	}
	ps->a[pos] = x;
	ps->size++;
}

In fact, we can apply it to the head and tail of your array after we complete the insertion implementation, so we can change the code to this:

void SeqlistPushFront(SL* ps, SLDataType x)
{
	/*    SeqlistCheckCapacity(ps);
	    // mobile data
	     int end = ps->size - 1;
	     while (end >= 0)
	     {
		    ps->a[end + 1] = ps->a[end];
		    --end; // Front and rear can be
	     }
	     ps->a[0] = x;
	     ps->size++;
	*/
	SeqlistInsert(ps, 0, x);
}

Like this, yes, that's right.

6.4 Delete

The idea of ​​deletion is similar to the previous one, as shown in the figure

The implementation of the code is as follows

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

	int begin = pos + 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		++begin;    
	}
	ps->size--;
}

6.5 Find

This is relatively easy, let's go directly to the code:

int SeqlistFind(SL* ps, SLDataType x)
{
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}

6.6 Printing

void SeqlistPrint(SL* ps)
{
	for (int i = 0; i < ps->size; ++i)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

7. Complete code

In this way, we have basically implemented all the code, the following is the complete code:
test.c

#include "Seqlist.h"

void TestSeqlist1()
{
	SL s1;
	SeqlistInit(&s1);
    SeqlistPushBack(&s1, 1);
	SeqlistPushBack(&s1, 2);
	SeqlistPushBack(&s1, 3);
	SeqlistPushBack(&s1, 4);
	SeqlistPushBack(&s1, 5);
	SeqlistPrint(&s1);

	SeqlistPopBack(&s1);
	SeqlistPopBack(&s1);
	SeqlistPrint(&s1);

	SeqlistDestory(&s1);
}

void TestSeqlist2()
{
	SL s1;
	SeqlistInit(&s1);
	SeqlistPushBack(&s1, 1);
	SeqlistPushBack(&s1, 2);
	SeqlistPushBack(&s1, 3);
	SeqlistPushBack(&s1, 4);
	SeqlistPushBack(&s1, 5);
	SeqlistPrint(&s1);

	SeqlistPushFront(&s1, 10);
	SeqlistPushFront(&s1, 20);
	SeqlistPushFront(&s1, 30);
	SeqlistPrint(&s1);

	SeqlistPopFront(&s1);
	SeqlistPopFront(&s1);
	SeqlistPrint(&s1);

	SeqlistDestory(&s1);
}

void TestSeqlist3()
{
	SL s1;
	SeqlistInit(&s1);
	SeqlistPushBack(&s1, 1);
	SeqlistPushBack(&s1, 2);
	SeqlistPushBack(&s1, 3);
	SeqlistPushBack(&s1, 4);
	SeqlistPushBack(&s1, 5);
	SeqlistPrint(&s1);

	SeqlistInsert(&s1, 2, 30);
	SeqlistPrint(&s1);

	int pos = SeqlistFind(&s1, 4);
	if (pos != -1)
	{
		SeqlistInsert(&s1, pos, 40);
	}
	SeqlistPrint(&s1);

	SeqlistDestory(&s1);
}

void TestSeqlist4()
{
	SL s1;
	SeqlistInit(&s1);
	SeqlistPushBack(&s1, 1);
	SeqlistPushBack(&s1, 2);
	SeqlistPushBack(&s1, 3);
	SeqlistPushBack(&s1, 4);
	SeqlistPushBack(&s1, 5);
	SeqlistPrint(&s1);

	int pos = SeqlistFind(&s1, 3);
	if (pos != -1)
	{
		SeqlistErase(&s1, pos);
	}
	SeqlistPrint(&s1);
	SeqlistDestory(&s1);
}

enum
{
	PushFront = 1,
	PopFront,
	PushBack,
	PopBack,
	Insert,
	Erase,
	Find,
	Print
};

// menu
void Menu()
{
	printf("*********************************\n");
	printf("*****    Please select your action:>   *****\n");
	printf("*****  1,head plug    2. Head delete   *****\n");
	printf("*****  3,tail plug    4. Tail deletion   *****\n");
	printf("*****  5,insert    6. Delete   *****\n");
	printf("*****  7,find    8. Print   *****\n");
	printf("*****      -1,quit         *****\n");
	printf("*********************************\n");
}

int main()
{
	//TestSeqlist1();
	//TestSeqlist2();
	//TestSeqlist3();
	SL s1;
	SeqlistInit(&s1); // initialization
	int input = 0;
	int x;
	int pos = 0;
	while (input != -1)
	{
		Menu();
		scanf("%d", &input);
		switch (input)
		{
		case PushFront:
			printf("Please select the data you want to insert,-1 Finish\n");
			do
			{
				scanf("%d", &x);
				if (x != -1)
				{
					SeqlistPushFront(&s1, x);
				}
			} while (x != -1);
			break;

		case PopFront:
			SeqlistPopFront(&s1);
			break;

		case PushBack:
			printf("Please select the data you want to insert,-1 Finish\n");
			do
			{
				scanf("%d", &x);
				if (x != -1)
				{
					SeqlistPushBack(&s1, x);
				}
			} while (x != -1);
			break;

		case PopBack:
			SeqlistPopBack(&s1);
			break;

		case Insert:
			printf("Please select the data you want to insert and where to insert it,-1 Finish\n");
			do
			{
				scanf("%d %d", &pos, &x);
				if (x != -1)
				{
					SeqlistInsert(&s1, pos, x);
				}
			} while (x != -1);
			break;

		case Erase:
			printf("Please select the data you want to delete,-1 Finish\n");
			do
			{
				scanf("%d", &x);
				if (x != -1)
				{
					SeqlistErase(&s1, x);
				}
			} while (x != -1);
			break;

		case Find:
			printf("Please select the data you are looking for,-1 Finish\n");
			do
			{
				scanf("%d", &x);
				if (x != -1)
				{
					printf("found, subscripted as%d\n", SeqlistFind(&s1, x));
				}
				else
				{
					printf("did not find\n");
				}
			} while (x != -1);
			break;

		case Print:
			SeqlistPrint(&s1);
			break;
		default:
			printf("No such option, please select again\n");
			break;
		}
	}
	SeqlistDestory(&s1);
	TestSeqlist4();
	return 0;
}

SeqList.c

#include "Seqlist.h"

void SeqlistPrint(SL* ps)
{
	for (int i = 0; i < ps->size; ++i)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

void SeqlistInit(SL* ps)
{
	ps->a = NULL;
	ps->size = ps->capacity = 0;// initialization
}

void SeqlistDestory(SL* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

void SeqlistCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;// Expansion
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));// realloc counts bytes
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);// Here return is not good, exit directly terminates the program
		}

		ps->a = tmp;
		ps->capacity = newcapacity;
	}
}

void SeqlistPushBack(SL* ps, SLDataType x) // tail plug
{
	/*   SeqlistCheckCapacity(ps);
	     ps->a[ps->size] = x;
	     ps->size++; 
	*/
	SeqlistInsert(ps, ps->size, x);
}

void SeqlistPopBack(SL* ps)
{
	
	/*  if (ps->size > 0)
	  {
		//ps->a[ps->size - 1] = 0; No problem with this
		ps->size--;
	   }
	*/  // method one

	assert(ps->size > 0); //If it is true, continue, if it is false, that is, <=0, it will terminate the program and indicate that the assertion failed.
	ps->size--;
}

void SeqlistPushFront(SL* ps, SLDataType x)
{
	/*    SeqlistCheckCapacity(ps);
	    // mobile data
	     int end = ps->size - 1;
	     while (end >= 0)
	     {
		    ps->a[end + 1] = ps->a[end];
		    --end; // Front and rear can be
	     }
	     ps->a[0] = x;
	     ps->size++;
	*/
	SeqlistInsert(ps, 0, x);
}

void SeqlistPopFront(SL* ps)
{
	assert(ps->size > 0);
	int begin = 1;               //begin = 0
	while (begin < ps->size)     // size - 1
	{
		ps->a[begin - 1] = ps->a[begin];  // begin begin + 1
		++begin;
	}
	ps->size--;
	// mobile data
}

int SeqlistFind(SL* ps, SLDataType x)
{
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}

void SeqlistInsert(SL* ps, int pos, SLDataType x)
{
	/*   if (pos > ps->size || pos < 0)  out of bounds
	    {
		   printf("pos invalid\n");
		   return;
	    }
	*/      //two methods
	assert(pos >= 0 && pos <= ps -> size);

	SeqlistCheckCapacity(ps); // Insert considering expansion
	int end = ps->size - 1;
	// mobile data
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		--end;
	}
	ps->a[pos] = x;
	ps->size++;
}

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

	int begin = pos + 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		++begin;    
	}
	ps->size--;
}

SeqList.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//  #define N 1000
typedef int SLDataType; 

// dynamic sequence table
typedef struct Seqlist
{
	SLDataType* a;
	int size;// Indicates how many "pieces" of data are stored in the array
	int capacity; // How much space can the array actually store data?
}SL;

// Static feature: don't allow insertion if full Disadvantage: can't determine how much fits
// If N is too small, it is not enough, and N is wasted.
// 
//Interface functions -- naming style follows STL

void SeqlistPrint(SL* ps);// print order table
void SeqlistInit(SL* ps);// initialization sequence table
void SeqlistDestory(SL* ps);// destroy the sequence table
void SeqlistCheckCapacity(SL* ps);// Check data augmentation
void SeqlistPushBack(SL* ps, SLDataType x); //tail plug
void SeqlistPopBack(SL* ps); //tail deletion
void SeqlistPushFront(SL* ps, SLDataType x); // head plug
void SeqlistPopFront(SL* ps); // header deletion 
int SeqlistFind(SL* ps, SLDataType x);// Find the position of this value, find the return X subscript position, and not return -1
void SeqlistInsert(SL* ps, int pos, SLDataType x);//Insert at the specified pos subscript position
void SeqlistErase(SL* ps, int pos);//Delete data at pos location

8. Summary

The introduction to the sequence table is here. It can be said that although the sequential table has its own advantages, this feature brings trouble to it, such as O(N), the inefficiency in the process of addition and deletion, and so on.

In the future articles, I have also prepared a lot of my own original articles and opinions for you (there are many things I don't understand, please let me know in the comment area). If you are looking forward to it, please vote for me a lot (bushi). If you make a mistake, please give me three clicks if you are looking forward to it.