Static sequence table of data structure (including game menu)

catalogue

I What is a sequence table?

II Differences between static sequence table and dynamic sequence table

III What is a static sequence table

4: Function interface implementation

1. Initialize structure

2. Print data

3. Head insert data

4. Trailing data

5. Header deletion data

6. Tail deletion data

Attachment: original code link

I What is a sequence table?

Sequential table is a linear structure in which data elements are stored in sequence with a storage unit with continuous physical addresses. Generally, array storage is used. Complete the addition, deletion, query and modification of data on the array. The sequence table is divided into static sequence table and dynamic sequence table.

Simply put: sequential table: continuous physical space storage - it is an array, and the data must be stored from scratch in turn.

II Differences between static sequence table and dynamic sequence table

        1. Static sequential table: use fixed length array storage.

         2. Dynamic sequential table: use dynamic array storage.

Among them, because the dynamic sequence table is opened dynamically, we have to release (free) space at last. Let's see how to add, delete, check and modify the static sequence table. As for the dynamic sequence table, please see the next article of the author!

III What is a static sequence table

First, the static sequence table is stored in an array. We also need to identify how many significant numbers there are, so we can define a structure.

struct SeqList
{
    int arr[50];    //Arrays are used to store data
    int size;       //Identify the number of valid data
};

In order to facilitate the subsequent change of data type and array size, we use #define macro to define the array size, and typedef to rename the data type. In this way, if you want to change the type later or change the array size, you only need to change one position, which increases the maintainability of the program.

->

//Note: #define is not followed by a semicolon
//typedef is followed by a semicolon

#define Max_size 10
typedef int SeqlistType;

typedef struct Seqlist
{
	SeqlistType arr[Max_size];	//Fixed length array	
	SeqlistType size;	//Effective number
}SQ;

4: Function interface implementation

1. Initialize structure

At first, there was no significant number, so we defined the size as 0, initialized the array with menset and initialized by the number of bytes.

Note: we create a structure variable. If only the value is passed, the change of the formal parameter will not affect the argument. The formal parameter is only a temporary copy of the argument. So we need to pass the address of the structure variable and receive it with the structure pointer.!!!

void SeqlistInit(SQ* s)
{
	memset(s->arr, 0, sizeof(SeqlistType) * Max_size);
	s->size = 0;	//There are no valid numbers initially
}

2. Print data

Note: you only need to traverse the array for printing, and the structure will not be modified, so you can pass values and addresses!

Method 1: value transfer

void SeqlistPrint(SQ s)
{
	int i = 0;
	for (i = 0; i < s.size; i++)
	{
		printf("%d ", s.arr[i]);
	}	
	printf("\n");
}

Method 2: address transmission

void SeqlistPrint(SQ* s)
{
	int i = 0;
	for (i = 0; i < s->size; i++)
	{
		printf("%d ", s->arr[i]);
	}
}

3. Head insert data

Note: because the array is a fixed length array, when inserting data, you should first ensure that there is an empty position in the array and judge!

Header insertion: put the data in the position of arr[0], just move the data of the original array backward. After inserting data, remember + 1 for the effective number

Note: start moving from the last edge. If you start moving from the front, the data behind will be overwritten.

void SeqlistPushFront(SQ* s,SeqlistType x)
{
	//Make sure you don't cross the line
	if (s->size == Max_size)
	{
		printf("Full\n");
		return ;
	}
	int i = 0;
	//Move data back
	for (i = s->size; i > 0; i--)
	{
		s->arr[i ] = s->arr[i-1];
	}
	//insert
	s->arr[0] = x;
	//Significant digit + 1
	s->size++;
}

4. Trailing data

Similarly, the tail interpolation should also ensure that the data has an empty position.

For tailoring data, you only need to put the data into the ARR [PS - > size] position of the array. The subscript of the array starts from 0, and size is used to identify the effective number,

Before insertion:

After insertion:- > code implementation

//Tail insertion
void SeqlistPushBack(SQ* s ,SeqlistType x)
{
	//Make sure you don't cross the line
	if (s->size == Max_size)
	{
		printf("Full\n");
		return;
	}
	s->arr[s->size] = x;
	s->size++;
}

5. Header deletion data

Header deletion: that is, remove the elements of array arr[0], and > overwrite the following elements forward. This time is different from the head plug. This time it should be covered from the beginning!!! Delete an element - > size--

//Header deletion
void SeqlistPopFront(SQ* s)
{
	int i = 0;
	for (i = 0; i < s->size; i++)
	{
		s->arr[i] = s->arr[i+1];
	}
	s->size--;
}

6. Tail deletion data

Because size identifies the effective number, using size to control printing requires only size --, which is equivalent to removing the last data, but the last data is still in the array space, but we can't access it.

void SeqlistPopBack(SQ* s)
{
    s->size--;
}

Precautions:

1. Whether the parameter is passed by value or address.  

Pass value: a formal parameter is a temporary copy of an argument. Modification of the formal parameter will not affect the argument.

Address: the modification of formal parameters is the modification of arguments.

2. Before inserting data, first judge whether the array is full, otherwise it will cause the problem of data out of bounds.

3.size is used to identify the effective number. After inserting / deleting data, the size will also change.

Original code (including game menu):

SeqList.h files always include function declarations and type redefinitions

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
//Yes h file
#include<stdio.h>
#include <string.h>
//Note: #define is not followed by a semicolon
//typedef is followed by a semicolon
#define Max_size 10
typedef int SeqlistType;

//Create structure type
typedef struct Seqlist
{
	SeqlistType arr[Max_size];	//Fixed length array	
	SeqlistType size;	//Effective number
}SQ;
	
//If you want to change the content of the structure, you can pass the address. If you don't change the content, you can pass the value
 	
//Initialize structure	
void SeqlistInit(SQ* s);

//Print structure
void SeqlistPrint(SQ s);

//Head insert
void SeqlistPushFront(SQ* s, SeqlistType x);

//Tail insertion
void SeqlistPushBack(SQ* s,SeqlistType x);

//Header deletion
void SeqlistPopFront(SQ* s);

//Tail deletion
void SeqlistPopBack(SQ* s);



In Seqlist Implement interface functions in files

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include"Seqlish.h"

//Initialize structure
void SeqlistInit(SQ* s)
{
	memset(s->arr, 0, sizeof(SeqlistType) * Max_size);
	s->size = 0;	//There are no valid numbers initially
}

//When printing structure value transfer
void SeqlistPrint(SQ s)
{
	int i = 0;
	for (i = 0; i < s.size; i++)
	{
		printf("%d ", s.arr[i]);
	}	
	printf("\n");
}

When transmitting address
//void SeqlistPrint(SQ* s)
//{
//	int i = 0;
//	for (i = 0; i < s->size; i++)
//	{
//		printf("%d ", s->arr[i]);
//	}
//}

//Head insert
void SeqlistPushFront(SQ* s,SeqlistType x)
{
	//Make sure you don't cross the line
	if (s->size == Max_size)
	{
		printf("Full\n");
		return ;
	}
	int i = 0;
	//Move data back
	for (i = s->size; i > 0; i--)
	{
		s->arr[i ] = s->arr[i-1];
	}
	//insert
	s->arr[0] = x;
	//Significant digit + 1
	s->size++;
}

//Tail insertion
void SeqlistPushBack(SQ* s ,SeqlistType x)
{
	//Make sure you don't cross the line
	if (s->size == Max_size)
	{
		printf("Full\n");
		return;
	}
	s->arr[s->size] = x;
	s->size++;
}


//Tail deletion
void SeqlistPopBack(SQ* s)
{
	s->size--;
}

//Header deletion
void SeqlistPopFront(SQ* s)
{
	int i = 0;
	for (i = 0; i < s->size; i++)
	{
		s->arr[i] = s->arr[i+1];
	}
	s->size--;
}

In test Check whether there is any problem with the test interface in the C file (including the game menu)

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include"Seqlish.h"

void menu()
{
	printf("************************************\n");
	printf("*******1.Header data    2.Tail interpolation data********\n");
	printf("*******3.Header deletion data    4.Tail deletion data********\n");
	printf("********	0.exit	********\n");
}

int main()
{
	//Define structure variables
	SQ s1;
	SeqlistInit(&s1);


	int input = 0;
	int n = 0;
	do
	{
		menu();
		printf("Please enter your choice->\n");
		scanf("%d", &input);
		switch (input)
	{
		case 1:printf("Please enter the number you want to insert for header insertion->\n");
			scanf("%d", &n);
			//Head insert
			SeqlistPushFront(&s1, n);
			printf("The sequence after insertion is:->");
			SeqlistPrint(s1);
			break;
		case 2:
			printf("For tail insertion, please enter the number you want to insert->\n");
			scanf("%d", &n);
			//Tail insertion
			SeqlistPushBack(&s1, n);
			printf("The sequence after insertion is:->");
			SeqlistPrint(s1);
			break;
		case 3 :
			if (s1.size > 0)
			{
				printf("Perform header deletion. The original sequence is:->");
				SeqlistPrint(s1);
				printf("After deletion->");
				SeqlistPopFront(&s1);
				SeqlistPrint(s1);
			}
			else
				printf("Please insert data first\n");
			break;
		case 4:
			if (s1.size > 0)
			{
				printf("Perform tail deletion. The original sequence is:->");
				SeqlistPrint(s1);
				printf("After deletion->");
				SeqlistPopBack(&s1);
				SeqlistPrint(s1);
			}
			else
				printf("Please insert data first\n");
			break;
		case 0:
			printf("Exit successful\n");
			break;
		default:printf("Selection error, reselect\n");
			break;
	}
	} while (input);
}

Attachment: original code link

Welcome to my gitee to get the original code file!

https://gitee.com/maple-that-never-stays-up-late/my_code-source/tree/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84

In the next blog, I will take you in-depth understanding of the dynamic sequence table ~ welcome everyone to pay attention. If there are mistakes, welcome criticism and correction!

Keywords: data structure

Added by ztron on Mon, 03 Jan 2022 06:17:44 +0200