one . Sequence table classification

* Static sequence table
* Dynamic sequence table
Static sequence table : Use a fixed length array to store elements

Dynamic sequence table : Using dynamic array storage

two . Interface implementation

The static sequence table is only applicable to the scenario where you know how much data needs to be stored . Fixed length array of static sequence table N It's too big , There are many waves in the space
fee , Not enough to drive . Therefore, in reality, dynamic sequence table is basically used , Dynamically allocate space size as needed , So here we are Current dynamic sequence table .

Functions to be realized :

Basic addition, deletion, query and modification , include :

initialization , Check space , Tail insertion , Head insert , Tail deletion , Head insert , Header deletion , lookup , Insert at the specified location , Deletes the value at the specified location , Destroy , Print
// Sequence table initialization void SeqListInit(SeqList* psl, size_t capacity); // Check space , If full , Increase capacity
void CheckCapacity(SeqList* psl); // End of sequence table void SeqListPushBack(SeqList* psl,
SLDataType x); // Sequential tail deletion void SeqListPopBack(SeqList* psl); // Sequential header insertion void
SeqListPushFront(SeqList* psl, SLDataType x); // Sequential header deletion void
SeqListPopFront(SeqList* psl); // Sequential table lookup int SeqListFind(SeqList* psl,
SLDataType x); // Sequence table in pos Position insertion x void SeqListInsert(SeqList* psl, size_t pos,
SLDataType x); // Sequence table deletion pos Value of position void SeqListErase(SeqList* psl, size_t pos); //
Sequence table destruction void SeqListDestory(SeqList* psl); // Sequence table printing void SeqListPrint(SeqList*
This is the structure of the definition :
// Redefine type , Easy to change typedef int SLDataType // Definition of dynamic sequence table , For convenience of subsequent use , redefinition typedef struct
SeqList { SLDataType* a; int sz; int capacity; }SL, SeqList;
notes : The following implementations have been implemented assert Assert , Because the pointer passed cannot be null , Otherwise it makes no sense

1. Initialization sequence table

Because there are no precautions , Direct release code
void SeqListInit(SeqList* psl) { assert(psl);// Air judgment psl->a = NULL; psl->sz = 0;
psl->capacity = 0; }
2. Insert at the end of sequence table

It is worth noting that it is necessary to judge whether capacity expansion is needed
void SeqListPushBack(SeqList* psl, SLDataType x) { assert(psl);// Air judgment
SeqListCheckcapacity(psl);// Capacity check // Whether there is capacity increase or not , All have to be inserted at the end psl->a[psl->sz] = x;
psl->sz++; }
3. Capacity check

Need attention , During capacity expansion , If the initial capacity is 0, Then there will be problems , This method can effectively deal with when the initial capacity is set to 0 Situation at
void SeqListCheckcapacity(SeqList* psl) { assert(psl);// Air judgment // increase capacity if (psl->sz ==
psl->capacity) { size_t newcapacity = psl->capacity == 0 ? 4 : psl->capacity *
2; // To prevent initialization, the value is zero , Cannot be multiplied directly 2, The following expansion will fail SLDataType* temp =
(SLDataType*)realloc(psl->a, sizeof(SLDataType) * newcapacity); if (temp ==
NULL) { printf("open failed\n"); exit(-1);// Termination procedure , No longer running } else { psl->a = temp;
psl->capacity = newcapacity;// Assign the capacity increase space to the old capacity } } }
4. Delete the tail element of the sequence table

It should be noted that if the subscript decreases all the time, it will lead to cross-border , Need to deal with cross-border issues
void SeqListPopBack(SeqList* psl) { assert(psl);// Air judgment if (psl->sz >
0)// This condition must be added , Otherwise, the continuous reduction may cross the border { psl->sz--;// Tail deletion direct sz--, Because space is recyclable , No need to cover yourself } }
5. Destruction sequence table

Free space juxtaposition 0
void SeqListDestroy(SeqList* psl) { assert(psl);// Air judgment // Release and empty free(psl->a);
psl->a = NULL; // Set 0 psl->sz = 0; psl->capacity = 0; }
6. Print sequence table

No precautions
void SeqListPrint(SeqList* psl) { assert(psl);// Air judgment int i = 0; for (i = 0; i <
psl->sz; i++) { printf("%d ", psl->a[i]); } printf("\n"); }
7. Sequence table header insert

Nothing special
void SeqListPushFront(SeqList* psl, SLDataType x) { assert(psl);// Air judgment
SeqListCheckcapacity(psl);// Capacity check int end = psl->sz - 1; while (end >=
0)// Header insertion should assign data back ,0 Also included { psl->a[end+1] = psl->a[end]; end--; } psl->a[0] = x;
psl->sz++; }
8. Sequence table header deletion

Attention required , The subscript cannot be reduced all the time , Otherwise it will lead to cross-border
void SeqListPopFront(SeqList* psl) { assert(psl);// Air judgment int begin = 1; if
(psl->sz > 0)// This condition must be added , Otherwise, the continuous reduction may cross the border { while (begin < psl->sz) { psl->a[begin -
1] = psl->a[begin]; begin++; } psl->sz--; } }
9. Insert anywhere

1. Because the array subscripts are always greater than 0, therefore , according to C++ Implementation in , We should also set unsigned integers , Not signed integers

2. it is to be noted that pos Is it out of bounds

3. When inserting , In particular, pay attention to the cross-border problem of unsigned integers , May cause dead circulation , Or the use of signed and unsigned integers together leads to the problem of shaping promotion bug problem
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x) {
assert(psl);// inspect psl // Check whether it is out of bounds if (pos > psl->sz) { printf(" Cross the border \n"); return; }
// Check whether capacity expansion is required SeqListCheckcapacity(psl); // Subscripts use unsigned shaping ,end Point to the last element size_t end =
psl->sz; // Insert , Here's a note , When other than this // If unsigned and signed shaping appear together , It should be noted that unsigned shaping and signed shaping will improve the shaping efficiency during calculation
// If you use all unsigned shaping , Then pay attention end Don't cross the border and lead to a dead circle while (end > pos) { psl->a[end] = psl->a[end -
1]; --end; } psl->a[pos] = x; psl->sz++; }
10. Delete data at the specified location

Be careful not to cross the line
void SeqListErase(SeqList* psl, size_t pos) { assert(psl);// Air judgment // Judgment crossing if (pos
>= psl->sz) { printf(" Cross the border \n"); return; } size_t begin = pos + 1; // Start moving while
(begin < psl->sz) { psl->a[begin - 1] = psl->a[begin]; ++begin; } --psl->sz; }
11. Find the specified data

No precautions
void SeqListFind(SeqList* psl, SLDataType x) { assert(psl);// Air judgment // Traversal search , Return subscript
for (int i = 0; i < psl->sz; i++) { if (psl->a[i] == x) { return i; } }
// Return not found -1 Error code return -1; }

©2019-2020 Toolsou All rights reserved,
【C++ Must see for entry 】C++ from 0 reach 1 Introductory programming axios Interceptor packaging and use Spring Boot Interview must ask : Automatic configuration principle VMware 16 install centos 7 Detailed tutorial C Language data structure - Sequence table delete duplicates V2.0.0 The 12th Blue Bridge Cup c++b Group personal problem solving On sending data from serial port single chip microcomputer to upper computer centos7 install RabbitMqjava Polymorphic array of opencv-python Fourier transform and inverse transform