1.C language-sequence table-head insertion, head deletion, tail insertion, tail deletion, search, insertion and deletion

Article directory

• Introduction
• • Dynamic sequence list structure
  • 1.Head plug function
  • 2.Header deletion function
  • 3.Tail plug function
  • 4. Tail deletion function
  • 5. Search function
  • 6.Insert function
  • 7. Delete function
  • 8. This program contains a total of 4 files, 2 .c files and 2 .h files
  • • 8.1 SeqList.h file
    • 8.2 SeqList.c file
    • 8.3 test.h file
    • 8.4 test.c file
  • 9.Test results
  • • 9.1 Test the running results of tail insertion and tail deletion
    • 9.2 Test the running results of header insertion and removal
    • 9.3 Test the results of search, insertion and deletion
  • 10. Warm reminder

Introduction

 This article mainly introduces the head insertion, head deletion, tail insertion, tail deletion, search, insertion and deletion of sequence tables. All .c and .h files are provided to ensure that users can directly copy and paste them into the compiler. Run the program.

Dynamic sequence table structure

typedef int SLDataType; /*Type of stored data*/

/*Dynamic sequence table*/
typedef struct SeqList
{<!-- -->
SLDataType* a;
int size; /*Indicates how much data is stored in the data*/
int capacity; /*What is the actual space capacity of the array that can store data*/
}SL;

1.Head plug function

 The idea is to first find the last element of the array, and then move the elements one position back one by one. Finally, place the data x to be inserted at the head of the array.

void SeqListPushFront(SL* ps, SLDataType x)
{<!-- -->
/*Check whether to expand*/
SeqListCheckCapacity(ps);

int end = ps->size - 1;

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

ps->a[0] = x;
ps->size + + ;

return;
}

 Checking whether to expand is to check whether the number of data exceeds the maximum capacity or whether space needs to be opened when inserting elements. If space needs to be opened or expanded.

void SeqListCheckCapacity(SL* ps)
{<!-- -->
/*If there is no space or insufficient space, expand the capacity*/
if (ps->capacity == ps->size)
{<!-- -->
int newCapacity = (ps->capacity == 0) ? 4 : ps->capacity * 2;
SLDataType* temp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));
if (NULL == temp)
{<!-- -->
printf("realloc fail!\
");
exit(-1);
}

ps->a = temp;
ps->capacity = newCapacity;
}

return;
}

2. Header deletion function

 The idea is to first find the second element of the array, then start from the second data, and move each data forward one bit to overwrite the data.

void SeqListPopFront(SL* ps)
{<!-- -->
assert(ps->size > 0);

int begin = 1;

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

return;
}

3. Tail plug function

 The idea is to first check whether expansion is needed, and then put the data x that needs to be inserted directly at the end of the array.

void SeqListPushBack(SL *ps, SLDataType x)
{<!-- -->
/*Check whether to expand*/
SeqListCheckCapacity(ps);
\t
ps->a[ps->size] = x;
ps->size + + ;

return;
}

4. Tail deletion function

 The idea is to directly reduce the number of valid data by 1 to achieve the purpose of deleting the last element in the array.

/*Delete the end*/
void SeqListPopBack(SL* ps)
{<!-- -->
assert(ps->size > 0);
ps->size--;

return;
}

5. Search function

 The idea is to traverse the numbers in the sequence table, find the number that meets the conditions and return the corresponding subscript, otherwise return -1.

/*Find the specified number*/
int SeqListFind(SL* ps, SLDataType x)
{<!-- -->
int i = 0;
/*Return the subscript after finding it, if not found, return -1*/
for (i = 0; i < ps->size; i + + )
{<!-- -->
if (ps->a[i] == x)
{<!-- -->
printf("X was found, the subscript is %d\
", i);
return i;
}
}

printf("x is not in the sequence list!\
");

return -1;
}

6. Insert function

 The idea is to first find the last position of the array, and then move the data one position back one by one.
Note: The insertion function can realize the head insertion function and the tail insertion function
Header plug: SeqListInsert(ps, 0, 10);
Tail insertion: SeqListInsert(ps, ps->size, 10);

/*Insert a number at the specified position*/
void SeqListInsert(SL* ps, int pos, SLDataType x)
{<!-- -->
assert(pos >= 0 & amp; & amp; pos <= ps->size);

int end = ps->size - 1;

SeqListCheckCapacity(ps);

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

ps->a[pos] = x;
ps->size + + ;

return;
}

7. Delete function

 The idea is to first find the position after the insertion position, and then overwrite the data one by one to the previous position.
Note: The delete function can implement head deletion function and tail deletion function.
Header deletion: SeqListErase(ps, 0);
Tail deletion: SeqListErase(ps, ps->size - 1);

/*Delete the number at the specified position*/
void SeqListErase(SL* ps, int pos)
{<!-- -->
assert(pos >= 0 & amp; & amp; pos < ps->size);

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

ps->size--;

return;
}

8. This program contains a total of 4 files, 2 .c files and 2 .h files

8.1 SeqList.h file

The

 file contains the header file of the function and the corresponding structure.

#pragma once
#include 
#include 


typedef int SLDataType; /*Type of stored data*/

/*Dynamic sequence table*/
typedef struct SeqList
{<!-- -->
SLDataType* a;
int size; /*Indicates how much data is stored in the data*/
int capacity; /*What is the actual space capacity of the array that can store data*/
}SL;

/*Interface function*/
void SeqListInit(SL *ps);
void SeqListPushBack(SL *ps, SLDataType x); /*Tail insertion*/
void SeqListPopBack(SL *ps); /*Delete tail*/
void SeqListPushFront(SL *ps, SLDataType x); /*Header plug*/
void SeqListPopFront(SL *ps); /*Delete header*/
void SeqListCheckCapacity(SL* ps); /*Check capacity*/
void SeqListFree(SL *ps); /*Release space*/

int SeqListFind(SL* ps, SLDataType x); /*Find the specified number*/
void SeqListInsert(SL* ps, int pos, SLDataType x);/*Insert a number at the specified position*/
void SeqListErase(SL* ps, int pos); /*Delete the data at the specified position*/

/*Auxiliary printing function*/
void SeqListPrint(SL *ps); /*auxiliary printing*/

8.2 SeqList.c file

The

 file contains the specific implementation of the function function.

#define _CRT_SECURE_NO_WARNINGS
#include "SeqList.h"
#include 

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

if ((NULL == ps->a) & amp; & amp; (0 == ps->size) & amp; & amp; (0 == ps->capacity))
{
printf("Init Success!\
");
}
else
{
printf("Init Fail!\
");
}
return;
}
/*Tail insert*/
void SeqListPushBack(SL *ps, SLDataType x)
{
/*Check whether to expand*/
SeqListCheckCapacity(ps);

ps->a[ps->size] = x;
ps->size + + ;

return;
}

/*Delete tail*/
void SeqListPopBack(SL* ps)
{
assert(ps->size > 0);
ps->size--;

return;
}

/*Head plug*/
void SeqListPushFront(SL* ps, SLDataType x)
{<!-- -->
/*Check whether to expand*/
SeqListCheckCapacity(ps);

int end = ps->size - 1;

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

ps->a[0] = x;
ps->size + + ;

return;
}

/*Delete header*/
void SeqListPopFront(SL* ps)
{<!-- -->
assert(ps->size > 0);

int begin = 1;

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

return;
}

/*Expansion*/
void SeqListCheckCapacity(SL* ps)
{<!-- -->
/*If there is no space or insufficient space, expand the capacity*/
if (ps->capacity == ps->size)
{<!-- -->
int newCapacity = (ps->capacity == 0) ? 4 : ps->capacity * 2;
SLDataType* temp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));
if (NULL == temp)
{<!-- -->
printf("realloc fail!\
");
exit(-1);
}

ps->a = temp;
ps->capacity = newCapacity;
}

return;
}

/*Release space*/
void SeqListFree(SL* ps)
{
free(ps->a);

ps->a = NULL;
ps->capacity = ps->size = 0;

return;
}


/*Auxiliary printing function*/
void SeqListPrint(SL* ps)
{
assert(ps != NULL);

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

printf("\
");

return;
}
/*Find the specified number*/
int SeqListFind(SL* ps, SLDataType x)
{<!-- -->
int i = 0;
/*Return the subscript after finding it, if not found, return -1*/
for (i = 0; i < ps->size; i + + )
{<!-- -->
if (ps->a[i] == x)
{<!-- -->
printf("X was found, the subscript is %d\
", i);
return i;
}
}

printf("x is not in the sequence list!\
");

return -1;
}
/*Insert a number at the specified position*/
void SeqListInsert(SL* ps, int pos, SLDataType x)
{<!-- -->
assert(pos >= 0 & amp; & amp; pos <= ps->size);

int end = ps->size - 1;

SeqListCheckCapacity(ps);

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

ps->a[pos] = x;
ps->size + + ;

return;
}
/*Delete the number at the specified position*/
void SeqListErase(SL* ps, int pos)
{<!-- -->
assert(pos >= 0 & amp; & amp; pos < ps->size);

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

ps->size--;

return;
}

8.3 test.h file

The

 file defines switches to control macros, which are used to conveniently control the number of insertions and deletions during testing.

#pragma once

/*Macro definition switch to control the number of insertions and deletions*/

#define SEQ_LIST_PUSH_BACK_NUM 5 /*Tail insertion-the number of inserted data*/
#define SEQ_LIST_POP_BACK_NUM 3 /*Tail deletion - number of deleted data*/

#define SEQ_LIST_PUSH_FRONT_NUM 15 /*Header plug-number of inserted data*/
#define SEQ_LIST_POP_FRONT_NUM 3 /*Header deletion-number of deleted data*/

8.4 test.c file

 Used to test corresponding functions, TestSeqList1() and TestSeqList2(), to test tail insertion, tail deletion and head insertion and head deletion respectively. Users can control annotations themselves to test different functions.

#define _CRT_SECURE_NO_WARNINGS
#include "SeqList.h"
#include "test.h"

/*Test tail insertion and tail deletion functions*/
void TestSeqList1()
{<!-- -->
SLs;
int i = 0;
/*Initialization*/
SeqListInit( & amp;s);

/*Tail insert*/
for (i = 0; i < SEQ_LIST_PUSH_BACK_NUM; i + + )
{<!-- -->
SeqListPushBack( & amp;s, i);
}
\t
\t/*Print*/
SeqListPrint( &s);

/*Delete tail*/
for (i = 0; i < SEQ_LIST_POP_BACK_NUM; i + + )
{<!-- -->
SeqListPopBack( & amp;s);
}

\t/*Print*/
SeqListPrint( &s);

/*Release space*/
SeqListFree( & amp;s);

return;
}

/*Test the header insertion and header deletion functions*/
void TestSeqList2()
{<!-- -->
SLs;
int i = 0;
/*Initialization*/
SeqListInit( & amp;s);

/*Tail insert*/
for (i = 0; i < SEQ_LIST_PUSH_BACK_NUM; i + + )
{<!-- -->
SeqListPushBack( & amp;s, i);
}

\t/*Print*/
SeqListPrint( &s);

/*Head plug*/
for (i = 10; i < SEQ_LIST_PUSH_FRONT_NUM; i + + )
{<!-- -->
SeqListPushFront( & amp;s, i);
}

\t/*Print*/
SeqListPrint( &s);
\t
/*Delete header*/
for (i = 0; i < SEQ_LIST_POP_FRONT_NUM; i + + )
{<!-- -->
SeqListPopFront( & amp;s);
}
\t
\t/*Print*/
SeqListPrint( &s);

/*Release space*/
SeqListFree( & amp;s);

return;
}
/*Test search and insertion*/
void TestSeqList3()
{<!-- -->
SLs;
int i = 0;
/*Initialization*/
SeqListInit( & amp;s);

/*Tail insert*/
for (i = 0; i < SEQ_LIST_PUSH_BACK_NUM; i + + )
{<!-- -->
SeqListPushBack( & amp;s, i);
}

\t/*Print*/
SeqListPrint( &s);

/*Search*/
SeqListFind( & amp;s, 1);

/*Insert*/
SeqListInsert( & amp;s, 3, 100);

\t/*Print*/
SeqListPrint( &s);

/*Delete the number at the specified position*/
SeqListErase( & amp;s, 2);

\t/*Print*/
SeqListPrint( &s);

/*Release space*/
SeqListFree( & amp;s);

return;
}
int main()
{<!-- -->
TestSeqList1(); /*Test tail insertion and tail deletion*/

// TestSeqList2(); /*Test header insertion and header deletion*/

// TestSeqList3(); /*Test search and insertion*/

return 0;
}

9.Test results

9.1 Test the running results of tail insertion and tail deletion

 It can be seen from the running results that the tail insertion function inserted 5 elements, which are 0, 1, 2, 3, and 4. After performing tail deletion, the following three elements are deleted.

9.2 Test the running results of header insertion and header deletion

 It can be seen from the running results that the 5 elements inserted first are 0, 1, 2, 3, and 4 through tail insertion.
Then perform head insertion and insert five elements 10, 11, 12, 13, and 14. Finally, perform head deletion and delete the first three elements.

9.3 Test the results of search, insertion and deletion

 It can be seen from the running results that through the search function, the number 1 is found at the position with subscript 1;
Then execute the insert function. It can be seen that at the position with subscript 3, the number 100 is inserted;
Finally, the delete function is executed, and it can be seen that the number 2 at the position with subscript 2 is deleted.

10. Warm reminder

 The number of insertions and deletions is controlled by the macro definition in test.h.