catalogue
II Differences between static sequence table and dynamic sequence table
III What is a static sequence table
4: Function interface implementation
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!
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!