[Data structure] Sequence table | Detailed explanation

There are two basic storage structures used to store linear tables in computers: sequential storage structures and chained storage structures. This article introduces the use of sequential storage structure to realize linear table storage.

Sequential storage definition

The sequential storage structure of a linear list refers to a storage unit with consecutive addresses that stores the data elements of the linked list in sequence.

Linear table ( $^{a_1{}}$ , $^{a_2{}}$ …… $^{a_n{}}$ )’s sequential storage diagram is as follows:

For example, during college, we had a classmate in the same dormitory who was very honest and enthusiastic. We often asked him to help us occupy seats in the library, and he always agreed. Think about it, he and we share the same dormitory. Nine people, this is actually a matter of bullying. Every time he finished breakfast, he would rush to the library, pick a good place, and place the books in his schoolbag one by one according to the seats. If there were not enough books in his schoolbag, he would put them in his lunch box, He used both water glasses and pens, and he had to occupy nine seats in a long row. Later, he almost got into a fight over seat occupation.

Sequential storage method

To put it bluntly, the sequential storage structure of a linear table is the same as the example just now. It means finding a piece of land in the memory, occupying a certain amount of memory space in the form of placeholders, and then storing data elements of the same data type in sequence. In this clearing. Since the type of each data element in the linear table is the same, you can use the one-dimensional array in C language (the same in other languages) to implement the sequential storage structure, that is, store the first data element in In the position where the array index is 0, the adjacent elements of the linear list are stored in adjacent positions in the array.

In a linear table, we estimate the maximum storage capacity of the linear table and create an array. The length of the array is the maximum storage capacity. As data is inserted, the length of our linear table begins to grow, but the current length of the linear table cannot exceed the storage capacity, that is, the length of the array.

The difference between data length and linear table length

Note that there are two concepts here: “data length” and “linear table length” that need to be distinguished.

The length of the array is the length of the storage space that stores the linear table. In a statically allocated one-dimensional array, this amount generally remains unchanged after storage allocation. But in a dynamically allocated one-dimensional space, dynamic allocation of arrays can be achieved.

The length of the linear table is the number of data elements in the linear table. This amount changes as the insertion and deletion operations of the linear table proceed.

Address calculation method

Since we all start counting from 1, the definition of a linear table cannot be exempted. The starting point is also 1. However, the array in C language starts from 0, so the i-th element of the linear table must be stored in the array. The position where the subscript is i-1, that is, there is a corresponding relationship between the serial number of the data element and the array subscript in which it is stored.

Using an array to store a sequence table means allocating a fixed-length array space. Since insertion and deletion operations can be performed in a linear table, the allocated array space must be greater than or equal to the length of the current linear table.

Each storage unit in the memory has its own number, which is called an address. After the previous address is determined, the subsequent positions can be calculated. Because each data element, whether it is an integer, a real type or a character type, it needs to occupy a certain storage unit space. Assuming that c storage units are occupied, then the storage location of the i + 1th data element and the storage location of the i-th data element in the linear table satisfy the following relationship (LOC represents the function to obtain the storage location).

LOC( $a_{i + 1}$ )=LOC( $a_{i}$ ) + c

So for the i-th data element $a_{i}$ can be determined by $a_{1}$ It is calculated that:

LOC( $a_{i}$ )= LOC( $a_{i}$ ) + (i-1)*c

The address calculation formula can calculate the address of any position in the linear table at any time, whether it is the first or the last, it is the same time. Then when we store or retrieve data at each linear table position, it takes equal time for the computer, which is a constant. Therefore, using the concept of time complexity learned in our algorithm, its access time Performance is O(1). The storage structure with this characteristic is called a random access structure.

Code implementation analysis of sequence table

A sequence table is a data structure that uses a storage unit with a continuous physical address to store data elements in sequence. Generally, array storage is used. Complete the addition, deletion, modification and query of data on the array.

The sequence table can generally be divided into:

Static sequence table: uses fixed-length arrays to store elements.
Dynamic sequence table: Use dynamically opened array storage.

//Static storage of sequence table
#define N 7
typedef int SLDataType;
typedef struct SeqList
{
SLDataType array[N];//fixed length array
size_t size; //Number of valid data
}SL;


//Dynamic storage of sequence table
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* array; //points to a dynamically opened array
size_t size;//Number of valid data
size_t capacity;//The size of the capacity space
}SL;

In fact, in daily and future working environments, static storage is rarely practiced because we don’t know how much memory space is needed. If N is too large, it will not be enough, and if N is small, it will be wasteful. Static sequence tables are only suitable for scenarios where you know how much data needs to be stored. Therefore, in reality, dynamic sequence tables are basically used to dynamically allocate space according to needs, so below we implement dynamic sequence tables.

Structure code of sequence table

typedef int SLDataType;
//Dynamic storage of sequence table
typedef struct SeqList
{
SLDataType* a; //points to a dynamically opened array
size_t size;//Number of valid data
size_t capacity;//The size of the capacity space
}SL;

Initialization of sequence table

There is an array a in this sequence table, a size refers to the number of valid data, and a capacity refers to the size of the capacity space. For size, size is the number of valid data, and when viewed as a subscript, it is the next subscript of the last element.

During initialization, the size and capacity in the array and sequence table structure must be initialized.

void SLInit(SL* psl)
{
psl->a = NULL;
psl->size = 0;
psl->capacity = 0;
}

Destruction of sequence table

At first, the sequence list is an empty list, but after a series of additions, deletions, modifications and checks, some data will be stored. Later, when we destroy the linked list, the linked list will have content, so what we need to pay attention to here is that the destruction It is necessary to assert whether the sequence list is empty. If it is an empty list, what else should be destroyed? Secondly, when destroying, the idea is also very simple, which is nothing more than changing several variables of this sequence table to 0.

void SLDestory(SL* psl)
{
assert(psl);
if (psl->a != NULL)
{
free(psl->a);
psl->a = NULL;
psl->size = 0;
psl->capacity = 0;
}
}

Traversal printing of sequence table

The idea of traversal printing is very similar to the printing of arrays, just use subscripts. The subscript starts from zero, and size is the number of valid data, that is, the next subscript of the last data, so the loop condition here is i

void SeqListPrint(SL* psl)
{
assert(psl);
int i = 0;
for (i = 0; i < psl->size; i + + )
{
printf("%d ", psl->a[i]);
}
printf("\\
");
}

Expansion of sequence table

Because at the beginning, we initialized size and capacity to 0, so in order to prevent each expansion from being 0, we use the ternary operator to judge. If the capacity is 0, then directly expand the capacity by 4 bytes. , the others are expanded by twice its size.

void SLCheckCapacity(SL* psl)
{
assert(psl);
int Newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
SLDataType* tmp = (SLDataType*)realloc(psl->a, Newcapacity * sizeof(SLDataType));
if (tmp == NULL)
{
perror("realloc fail\\
");
}
psl->a = tmp;
psl->capacity = Newcapacity;
}

End insertion of sequence table

When adding data, whether it is inserted before or after or at a specified location, we need to determine whether there is enough space for it, that is, whether it needs to be expanded. After expansion, the data is inserted into the sequential table.

void SeqListPushBack(SL* psl, SLDataType x)
{
assert(psl);
SLCheckCapacity(psl);
psl->a[psl->size - 1] = x;
psl->size + + ;
}

Note here that size + + needs to be changed after tail insertion.

Header plug-in of sequence table

Inserting at the beginning of the sequence table is more difficult than inserting at the end, because all data needs to be moved back one position. So we have to use another pointer to traverse.

void SeqListPushFront(SL* psl, SLDataType x)
{
assert(psl);
SLCheckCapacity(psl);
int end = psl->size - 1;
while (end >= 0)
{
psl->a[end + 1] = psl->a[end];
end--;
}
psl->a[0] = x;
psl->size + + ;
}

Tail deletion of sequence table

Tail deletion is relatively easy, it is nothing more than changing size–, but here we also need to make an assertion to ensure that size is greater than zero.

void SeqListPopBack(SL* psl)
{
assert(psl);
assert(psl->size > 0);
psl->size--;
}

Delete the header of the sequence table

If you want to delete the header, just overwrite the following elements with the previous ones, starting from front to back.

void SeqListPopFront(SL* psl)
{
assert(psl);
assert(psl->size > 0);
int begin = 1;
while (begin <= psl->size - 1)
{
psl->a[begin - 1] = psl->a[begin];
begin++;
}
psl->size--;
}

Searching in sequence table

Search the sequence table to see if there is this array in this sequence table. In fact, this is traversal, it is very simple to use subscripts.

int SeqListFind(SL* psl, SLDataType x)
{
int i = 0;
for (int i = 0; i < psl->size; i + + )
{
if (psl->a[i] == x)
{
return i;
}
}
}

The sequence table inserts the number of x at position pos

Here we need to assert whether this is a valid position.

void SeqListInsert(SL* psl, int pos, SLDataType x)
{
assert(psl);
assert(pos >= 0 & amp; & amp; pos <= psl->size);
SLCheckCapacity(psl);
int end = psl->size - 1;
while (end >= pos)
{
psl->a[end + 1] = psl->a[end];
end--;
}
psl->a[pos] = x;
psl->size + + ;
}

Delete the value at pos position from the sequence table

void SeqListErase(SL* psl, int pos)
{
assert(psl);
assert(pos >= 0 & amp; & amp; pos <= psl->size);
int begin = pos + 1;
while (begin <= psl->size - 1)
{
psl->a[begin - 1] = psl->a[begin];
begin++;
}
psl->size--;
}

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