[Data Structure] Full analysis of the construction and implementation of dynamic sequence tables that is very easy to understand! (C language implementation) Source code included

This is read_ovo, thank you for seeing me
If you don’t understand anything, please comment~
Please point it out if there are any mistakes, thank you sincerely!
If it helps you, can you give me a like? Thank you!

Foreword

Linear table is a commonly used data structure.
A linear table that uses sequential storage is called a sequential table, that is, the physical memory storage units are continuous.
It is a very important beginning for data structure algorithms.

1. Constructing a dynamic sequence table

//Create a sequence list
typedef struct seqlist
{<!-- -->
datatype* a; //Data to be stored
int size;//Number of valid data
int capacity;//space capacity
}SL;

2. Basic operations of sequence tables

Assert

Before we start, let’s talk about a very useful function assert().
It is in the header file of assert.h and needs to be quoted.
You can think of assert as a restrictive statement that nothing happens when the conditions in the parentheses are met.
When the condition in the brackets is false, the program will report an error.

Initialization

Initializing the size to four storage types at the beginning will be more convenient later.

void init(SL* L)
{<!-- -->
L->a = (datatype*)malloc(sizeof(datatype) * 4);//Expand the pointed space to four storage types
if (L->a == NULL)//If it fails, it will return empty
{<!-- -->
printf("Initialization failed!");
exit(-1); //End the entire program
}
L->size = 0;
L->capacity = 4;//Changes in space and number of valid data
}

Destroy

It refers to the dynamically opened space pointed to by destruction.

void destroy(SL* L)
{<!-- -->
if(L->a)//If there is data in the space pointed by a
free(L->a);//Destroy the space
L->a = NULL; // Make the pointer point to null to prevent wild pointers
L->capacity = L->size = 0;//The number of valid data and space are initialized to 0
}

Head plug

One thing you need to think about when inserting is whether expansion is needed

void push_front(SL* L, datatype x)
{<!-- -->
    assert(L);
//Is there enough space? , not enough expansion
if (L->size == L->capacity)//When the effective number is equal to the number of space capacity, the space is full, which means expansion is needed
{<!-- -->
datatype* temp = (datatype*)realloc(L->a, L->capacity * sizeof(datatype) * 2);//The space to store this data type is doubled
if (temp == NULL)//If realloc fails to expand the space, it will return NULL (empty)
{<!-- -->
printf("realloc fail!\
");
return;
}
L->a = temp;//make a point to the first address of the expanded space
L->capacity = L->capacity * 2;
}
//The following is the head plug operation. For the convenience of explanation, I will explain it in sequence below~
int end = L->size - 1;
while (end >= 0)
{<!-- -->
L->a[end + 1] = L->a[end];
end--;
}
L->a[0] = x;
L->size + + ;
}

Analysis of head plug operation
For the convenience of thinking, we refer to a new variable end, which points to the last significant number

int end = L->size - 1;

The operation of head plug requires us to move all the original data backward, and we need to use loop.
In order to prevent 2 from being overwritten by 1 when data 1 is moved to 2, we need to start moving from the end of the data.

The code is implemented as follows

while (end >= 0)
{<!-- -->
L->a[end + 1] = L->a[end];
end--;
}

What are the conditions for determining whether the loop should stop? This is very simple, let’s just make an assumption.
Because the subscript of data 1 is 0, when end– reaches 0, is it necessary to move the data?

It is needed. We need to move the data at the 0 subscript position backward, so the condition is end>=0

Finally insert the data

L->a[0] = x;
L->size + + ;//Increase valid data

Put together it is

int end = L->size - 1;
while (end >= 0)
{<!-- -->
L->a[end + 1] = L->a[end];
end--;
}
L->a[0] = x;
L->size + + ;
}

Tail insert

void push_back(SL* L, datatype x)
{<!-- -->
if (L == NULL)//This is similar to the assertion of head insertion
{<!-- -->
printf("The table was not found!"); exit(-1);
}
//Is there enough space? Not enough and needs expansion
if (L->size == L->capacity)//This is also the expansion that needs to be thought of when inserting. For convenience, we can also write a function to check the space, which will be discussed later.
{<!-- -->
/*int newcapcity = L->capacity == 0 ? 4 : 2 * L->capacity;*/
datatype* temp=(datatype *)realloc(L->a, L->capacity * sizeof(datatype) * 2);
if (temp == NULL)
{<!-- -->
printf("realloc fail!\
");
return;
}
L->a = temp;//make a point to the first address of the expanded space
L->capacity = L->capacity * 2;
}

//Insert
//This can be inserted directly into the empty position of the last size.
L->a[L->size] = x;
L->size + + ;//Increase valid data
}

Header deletion

Deletion without expansion
Head deletion operation: We only need to move the following numbers forward and overwrite the first valid data.
The second important thing is logically, the size effective data is reduced.

In order to avoid covering everything with the same data, we start moving from the previous one.

void dele_front(SL* L)//You only need to move the following numbers forward until the last element is also moved
{<!-- -->
int start = 0;
while (start < L->size - 1)
{<!-- -->
L->a[start] = L->a[start + 1];
start + + ;
}
L->size--;//Reduction of effective data
}

To facilitate thinking, we also create a new variable start pointing to the first valid data.

Judgment condition: when start reaches 3, the data has been moved and can be stopped, so it does not need to reach the position of size-1 (4).

Tail deletion

Tail deletion only requires logical deletion.
Logical deletion has made the last data meaningless no matter how much it is.

void dele_back(SL* L)
{<!-- -->
L->size--;
}

Short call

If the table is empty, returns 1,
Otherwise return 0.

int empty(SL* L)
{<!-- -->
if (L->size == 0)
{<!-- -->
return 1;
}
else return 0;
}

Print

void display(SL* L)
{<!-- -->
if (empty(L))//If empty, return 1, indicating an empty list.
{<!-- -->
printf("There are no elements in the table! Printing failed!\
");
return; //End function
}
int end = L->size - 1;//It is convenient to think about taking the new variable end to point to the last valid data
for (int i = 0; i <= end; i + + )//Print from beginning to end
{<!-- -->
printf("%d ", L->a[i]);
}
printf("\
");
}

Expansion

The above-mentioned head plug and tail plug have been explained, and it is very simple to make a function.

void check_capacity(SL *L)
{<!-- -->
if (L->size == L->capacity)
{<!-- -->
datatype* temp = (datatype*)realloc(L->a, L->capacity * sizeof(datatype) * 2);//The space for storing data is doubled
if (temp == NULL)
{<!-- -->
printf("realloc fail!\
");
return;
}
L->a = temp;//make a point to the first address of the expanded space
L->capacity = L->capacity * 2;
}
}

Insert before the specified position

void insert_pos(SL* L, int position, datatype x)
{
assert(L);//If L is empty, an error will be reported
check_capacity(L);//Insertion needs to determine whether expansion is needed
assert(position >= 0 & amp; & amp; position <= L->size);//The inserted position must be within the range, 0 to size are all places that can be inserted, if it is size, it is equivalent to tail insertion Got it
//Implementation of inserting at specified position
int end = L->size - 1;
for (end; end >= position; end--)//Move the original data
{
L->a[end + 1] = L->a[end];
}
L->a[position] = x;//Insert data
L->size + + ;//Increase valid data
}

Implementation of inserting at specified position
In order to facilitate thinking, it is better to quote an end.
Insertion at a specified position is somewhat similar to header insertion, except that the position changes from 0 to position.

When end– reaches the position, do you still need to move the data?

Yes, because when end moves to position, we also need to move the data at position backward.
So the judgment condition is end>=position

Delete the specified location

The operation of deleting a specified position is similar to deleting the table header.
Move the data behind position forward, overwriting the data at position.
And logically valid data reduction.

void dele_pos(SL* L, int position)
{<!-- -->
if (L == NULL)//Similar to assertion, the table is empty and ends the function, but no error is reported
{<!-- -->
return;
}
//Delete operation
for (position; position < L->size - 1; position + + )
{<!-- -->
L->a[position] = L->a[position + 1];
}
L->size--;
}

Delete operation analysis

position + + does not need to reach the position of size-1 to complete the operation.

So the judgment condition is position

Search

The int type is used to return the position of the found element.
If not found return -1;

int find(SL* L, datatype x)
{<!-- -->
assert(L);
int i = 0;
for (i = 0; i <= L->size - 1; i + + )//Find the end of the table from the head
{<!-- -->
if (L->a[i] == x)
{<!-- -->
printf("Found it!");
return i;//Find the subscript position of the returned element
}
}
if (i == L->size)
{<!-- -->
printf("Not found!"); return -1;
}
}

Full code

seqlist.h header file
seqlist.c functions to implement various sequence lists
test.c implements the main function

seqlist.h

#pragma once

#include 

typedef int datatype;

//Create a sequence list
typedef struct seqlist
{<!-- -->
datatype* a; //Data to be stored
int size;//Number of valid data
int capacity;//space capacity
}SL;

//initialization
void init(SL* L);//All three data in the table must be changed


//destroy
void destroy(SL* L);//Destruction is a data space in the table, and the type of this data space is the structure type of the table

//Head plug
void push_front(SL* L, datatype x);

//Tail insertion
void push_back(SL *L,datatype x);

//Delete header
void dele_front(SL *L);

//Delete tail
void dele_back(SL *L);

//Print
void display(SL *L);

//Short call
int empty(SL* L);

//Insert before the specified position
void insert_pos(SL *L,int position,datatype x);

//Delete the specified location
void dele_pos(SL* L, int position);

//Expansion
void check_capacity(SL* L);

//Find
int find(SL* L, datatype x);

seqlist.c

#define _CRT_SECURE_NO_WARNINGS 1
#include 
#include "seqlist.h"
#include 
#include 

void init(SL* L)
{
/*L->a = NULL;
L->size = 0;
L->capacity = 0;*/
L->a = (datatype*)malloc(sizeof(datatype) * 4);
if (L->a == NULL)
{
printf("Initialization failed!");
exit(-1);
}
L->size = 0;
L->capacity = 4;
}

void destroy(SL* L)
{
if(L->a)
free(L->a);//Delete the space
L->a = NULL;//Prevent wild pointers
L->capacity = L->size = 0;

}

void push_front(SL* L, datatype x)
{
assert(L);
//Is there enough space? , expansion
if (L->size == L->capacity)
{
datatype* temp = (datatype*)realloc(L->a, L->capacity * sizeof(datatype) * 2);//The space for storing data is doubled
if (temp == NULL)
{
printf("realloc fail!\
");
return;
}
L->a = temp;//make a point to the first address of the expanded space
L->capacity = L->capacity * 2;
}


//Insert
int end = L->size - 1;//points to the position of the last number
while (end >= 0)//When equal to 0, move back further
{
L->a[end + 1] = L->a[end];
end--;
}
L->a[0] = x;
L->size + + ;
}


void push_back(SL* L, datatype x)
{
if (L == NULL)
{
printf("The table was not found!"); exit(-1);
}
//Is there enough space? Not enough and needs expansion
if (L->size == L->capacity)
{
/*int newcapcity = L->capacity == 0 ? 4 : 2 * L->capacity;*/
datatype* temp=(datatype *)realloc(L->a, L->capacity * sizeof(datatype) * 2);//The space for storing data is doubled
if (temp == NULL)
{
printf("realloc fail!\
");
return;
}
L->a = temp;//make a point to the first address of the expanded space
L->capacity = L->capacity * 2;
}

//Insert
L->a[L->size] = x;
L->size + + ;
}


void dele_front(SL* L)//You only need to move the following numbers forward until the last element is also moved
{
int start = 0;
while (start < L->size - 1)
{
L->a[start] = L->a[start + 1];
start + + ;
}
L->size--;
}

void dele_back(SL* L)//Tail deletion does not require expansion
{
L->size--;
}


void display(SL* L)
{
if (empty(L))
{
printf("There are no elements in the table! Printing failed!\
");
return;
}
int end = L->size - 1;
for (int i = 0; i <= end; i + + )
{
printf("%d ", L->a[i]);
}
printf("\
");
}

int empty(SL* L)
{<!-- -->
if (L->size == 0)
{<!-- -->
return 1;
}
else return 0;
}
         
void check_capacity(SL *L)
{
if (L->size == L->capacity)
{
/*int newcapcity = L->capacity == 0 ? 4 : 2 * L->capacity;*/
datatype* temp = (datatype*)realloc(L->a, L->capacity * sizeof(datatype) * 2);//The space for storing data is doubled
if (temp == NULL)
{
printf("realloc fail!\
");
return;
}
L->a = temp;//make a point to the first address of the expanded space
L->capacity = L->capacity * 2;
}
}


void insert_pos(SL* L, int position, datatype x)
{
assert(L);
check_capacity(L);
assert(position >= 0 & amp; & amp; position <= L->size);


int end = L->size - 1;
for (end; end >= position; end--)
{
L->a[end + 1] = L->a[end];
}
L->a[position] = x;
L->size + + ;
}


void dele_pos(SL* L, int position)
{
assert(L);
if (L == NULL)
{
return;
}
for (position; position < L->size - 1; position + + )
{
L->a[position] = L->a[position + 1];
}
L->size--;

}

int find(SL* L, datatype x)
{
assert(L);
int i = 0;
for (i = 0; i <= L->size - 1; i + + )
{
if (L->a[i] == x)
{
printf("Found it!");
return i;
}
}
if (i == L->size)
{
printf("Not found!"); return -1;
}
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "seqlist.h"


SEQLIST()
{<!-- -->
SL L;//Create table
init( & amp;L);//Initialization
push_back(&L, 1);//Tail insertion
push_back(&L,2);
push_back( & amp;L,1);
push_back( & amp;L,1);
push_front(&L, 5);//Head plug
push_front(&L, 8);
dele_back( & amp;L);//Tail deletion
dele_front( & amp;L);//head deletion
display(&L);//print
insert_pos( & amp;L, 4, 9);//Insert before the specified position
display(&L);
dele_pos(&L, 4);//Delete at specified position
display(&L);
find(&L, 10);//Find
destroy(&L);//Destroy

}

int main()
{<!-- -->
SEQLIST();
return 0;
}

Directory