Data Structure [Elementary]–Sequence List

Table of Contents

1. The concept of linear table

2. Sequence table

(1) Concept

(2)Classification

1. Static sequence table (use fixed-length array to store elements)

2. Dynamic sequence table (using dynamically opened arrays to store data)

(3)Interface implementation

1.Initialization sequence table

2. Destruction sequence table

3. Sequence table capacity check

4. Insert data using sequential table end interpolation method

5. Insert data using sequential header interpolation

6. Sequential table tail deletion method to delete data

7.Delete data using sequential header deletion method

8. Insertion of elements with subscripts at any position

9. Deletion of elements subscripted at any position

---

1. The concept of linear table

• A linear list is a finite sequence of n data elements with the same characteristics. Linear table is a data structure widely used in practice. Common linear tables: sequential list, linked list, stack, queue, string…
• A linear table is logically a linear structure, that is, a continuous straight line. However, the physical structure is not necessarily continuous. When linear tables are physically stored, they are usually stored in the form of arrays and linked structures.

• Illustration

2. Sequence List

(1)Concept

A sequence table is a linear structure that uses a segment of physical addresscontinuous storage units to store data elements in sequence. Generally, array storage is used. Complete the addition, deletion, checking and modification of data on the array.

(2)Category

1. Static sequence table (use fixed-length array to store elements)

#define N 7
typedef int SLDataType;

typedef struct SeqList
{
SLDataType arr[N];//fixed length array
size_t size;//The number of valid data
}SeqList;

• Illustration

Disadvantages: Static sequence tables are only suitable for scenarios where you know how much data needs to be stored. The fixed-length array of the static sequence table causes N to be too large. If the space is too much, it is wasted, and if it is too little, it will not be enough.

2. Dynamic sequence table (using dynamically developed arrays to store data)

#define N 7
typedef int SLDataType;

typedef struct SeqList
{
SLDataType* arr;//points to a dynamically opened array
size_t size;//Number of elements
size_t capacity;//The size of the capacity
}SeqList;

• Illustration

(3)Interface implementation

1.Initialization sequence table

void SLInit(SL* ps)
{
ps->arr = NULL;
ps->num = 0;
ps->capacity = 0;
}

2. Destruction sequence table

void SLDestroy(SL* ps)
{
if (ps->arr != NULL)
{
free(ps->arr);
ps->arr = NULL;
ps->num = 0;
ps->capacity = 0;
}
}

3. Sequence table capacity check

void SLCheckCapacity(SL* ps)
{
if (ps->num == ps->capacity)
{
int newcapacity =ps->capacity== 0 ? 4 : ps->capacity * 2;
        //Avoid expansion failure causing the original space to be overwritten and data lost.
SLDataType* ptr = (SLDataType*)realloc(ps->arr, sizeof(SLDataType) * newcapacity);
if (ptr == NULL)
{
perror("realloc fail");
return;
}
ps->arr = ptr;
ps->capacity = newcapacity;
}
}

4. Insert data using sequential end-of-table interpolation

void SLPushBack(SL* ps, SLDataType x)
{
SLCheckCapacity(ps);
ps->arr[ps->num] = x;//num is the number of elements in the sequence table, which is 1 greater than the subscript position of the element
                         //So it just points to the next position of the last element
ps->num + + ;
}

5. Insert data using sequential header interpolation

void SLPushFront(SL* ps, SLDataType x)
{
SLCheckCapacity(ps);
SLDataType end = ps->num - 1;//points to the last element
    //Move data
while (end >= 0)
{
ps->arr[end + 1] = ps->arr[end];
--end;
}
    //Insert data
ps->arr[0] = x;
ps->num + + ;
}

6. Deleting data by sequential table tail deletion

void SLPopBack(SL* ps, SLDataType x)
{
ps->num--;//Equivalent to changing the number of valid data
}

• There is a problem

Suppose we have inserted 6 pieces of data, but we have called the tail delete function 7 times:

At this time num (the number of elements in the sequence table ) is equal to -1, but since we did not access the location of -1 at this time, the compiler did not report an error.

But if we want to insert new data at this time, such as re-inserting data 1, 2, 3:

It can be found that the data 1 inserted at the beginning is indeed missing. Therefore, we need to avoid the problem of continuing to delete the sequence table when it is empty:

Therefore, it is necessary to check the number of elements in the sequence list:Use assertion() to check violently.

7. Deleting data by deleting sequential headers

• Define variable begin=1

void SLPopFront(SL* ps)
{
assert(ps);
assert(ps->num > 0);
int begin = 1;
while (begin < ps->num)
{
ps->arr[begin - 1] = ps->arr[begin];
+ + begin;
}
ps->num--;
}

• Define variable begin=0

void SLPopFront(SL* ps)
{
assert(ps);
assert(ps->num >= 0);
int begin = 0;
while (begin <ps->num - 1)
{
ps->arr[begin]=ps->arr[begin + 1];
+ + begin;
}
ps->num--;
}

8. Insertion of elements with subscripts at any position

void SLInsert(SL* ps, int pos, SLDataType x)
{
assert(ps);
assert(pos >= 0 & amp; & amp; pos <= ps->num);//equal to num is equivalent to tail insertion
SLCheckCapacity(ps);
int end = ps->num - 1;
//Move the data starting from pos and beyond
while (end >= pos)
{
ps->arr[end + 1]=ps->arr[end];
--end;
}
//Insert data at pos
ps->arr[pos] = x;
ps->num + + ;
}

9. Deletion of elements subscripted at any position

void SLErase(SL* ps, int pos, SLDataType x)
{
assert(ps);
assert(pos >= 0 & amp; & amp; pos <= ps->num);
SLCheckCapacity(ps);
int begin = pos + 1;//reference header deletion method
while (begin < ps->num)
{
ps->arr[begin - 1] = ps->arr[begin];
+ + begin;
}
ps->num--;
}

The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 57261 people are learning the system