1. Sequence table
1.1 Concept and structure
A sequence table is a linear 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, checking and modification of data on the array.
The sequence table can generally be divided into:
1. Static sequence table: Use fixed-length arrays to store elements.2. Dynamic sequence table: Use dynamically opened array storage.
1.2 Interface function
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. Therefore, in reality, dynamic sequence tables are basically used to dynamically allocate space according to needs, so below we implement dynamic sequence tables.
typedef int SLDataType;
//Dynamic storage of sequence table
typedef struct SeqList
{
SLDataType* array; // Points to a dynamically allocated array
size_t size; // Number of valid data
size_t capacity; //The size of the capacity space (if the space is not enough, it needs to be expanded)
}SeqList;
//Basic add, delete, check and modify interface
//Sequence table initialization
void SeqListInit(SeqList* psl);
// Check the space, if it is full, increase the capacity
void CheckCapacity(SeqList* psl);
//Insert at the end of the sequence table
void SeqListPushBack(SeqList* psl, SLDataType x);
//Delete at the end of the sequence table
void SeqListPopBack(SeqList* psl);
// Insert sequence header
void SeqListPushFront(SeqList* psl, SLDataType x);
//Delete sequence header
void SeqListPopFront(SeqList* psl);
//Sequence table lookup
int SeqListFind(SeqList* psl, SLDataType x);
// The sequence table inserts x at position pos
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
//Delete the value of pos position in the sequence table
void SeqListErase(SeqList* psl, size_t pos);
//Sequence list destroyed
void SeqListDestory(SeqList* psl);
//Print sequence table
void SeqListPrint(SeqList* psl);
1.3 Implementation of interface functions
//Sequence table initialization
void SeqListInit(SeqList* psl)
{
psl->array = NULL;
psl->capicity = 0;
psl->size = 0;
}
// Check the space, if it is full, increase the capacity
void CheckCapacity(SeqList* psl)
{
if (psl->size == psl->capicity)
{
int new = psl->capicity == 0 ? 4 : 2 * (psl->capicity);
SLDataType* temp = (SLDataType*)realloc(psl->array, sizeof(SLDataType) * new);
if (temp == NULL)
{
perror("realloc");
return;
}
psl->array = temp;
psl->capicity = new;
}
}
//Insert at the end of the sequence table
void SeqListPushBack(SeqList* psl, SLDataType x)
{
CheckCapacity(psl);
psl->array[psl->size] = x;
psl->size + + ;
}
//Delete at the end of the sequence table
void SeqListPopBack(SeqList* psl)
{
//Check if it is empty
assert(psl->size > 0);
psl->size--;
}
// Insert sequence header
void SeqListPushFront(SeqList* psl, SLDataType x)
{
CheckCapacity(psl);
int end = psl->size - 1;
while (end >= 0)
{
psl->array[end + 1] = psl->array[end];
--end;
}
psl->array[0] = x;
psl->size + + ;
}
//Delete sequence header
void SeqListPopFront(SeqList* psl)
{
//The data moves forward to cover, size--
assert(psl->size > 0);
int begin = 1;
while (begin < psl->size)
{
psl->array[begin - 1] = psl->array[begin];
}
psl->size--;
}
//Sequence table lookup
int SeqListFind(SeqList* psl, SLDataType x)
{
assert(psl);
for (int i = 0; i < psl->size; i + + )
{
if (psl->array[i] == x)
{
return i;
}
}
return -1;
}
// The sequence table inserts x at position pos
//Note that pos is a subscript here, starting from 0
//And size is the number of data
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
assert(psl);
assert(pos >= 0 & amp; & amp; pos <= psl->size);
CheckCapacity(psl);
int end = psl->size - 1;
while (end >= psl->size)
{
psl->array[end + 1] = psl->array[end];
--end;
}
psl->array[pos] = x;
psl->size + + ;
}
//Delete the value of pos position in the sequence table
void SeqListErase(SeqList* psl, size_t pos)
{
assert(psl);
assert(pos >= 0 & amp; & amp; pos <= psl->size);
int begin = pos;
while (begin < psl->size)
{
psl->array[begin] = psl->array[begin + 1];
+ + begin;
}
psl->size--;
}
//Sequence list destroyed
void SeqListDestory(SeqList* psl)
{
if (psl->array != NULL)
{
free(psl->array);
psl->array = NULL;
psl->capicity = 0;
psl->size = 0;
}
}
//Print sequence table
void SeqListPrint(SeqList* psl)
{
assert(psl);
for (int i = 0; i < psl->size; i + + )
{
printf("%d ", psl->array[i]);
}
printf("\
");
}
1.4 Implementation details:
1. Capacity expansion problem
Here we directly use the realloc function, which is more convenient than the malloc function. When the space is 0, the space is directly opened. When the space is insufficient, the capacity will be increased.
The meaning of this statement is that when the space is 0, open up a space the size of 4 structures.
2.Print
It is very simple to implement the printing operation. You only need to print valid data (size).
3.Tail plug
It is very simple to implement tail insertion. You only need to store data at the size position and then + + size the data.
4.Tail deletion
To delete, we must first assert whether the sequence table is empty. If it is empty, the deletion operation will not be performed. Then, just –size can complete the deletion operation.
5.Head plug
To insert the head of the sequence table, you only need to move the data after the first element backward, and then write the data of the first element.
At this time, we use the end pointer to receive and move the data.
6. Header deletion
To delete the head, you just need to overwrite the first element. This time, use begin to move the data forward.
7. Insert anywhere
There is not much difference between inserting at any position and inserting at the beginning. Just move the data backward from the node you want to insert, but be careful not to access out of bounds.
8. Delete anywhere
This is also very similar to head deletion. If you delete a piece of data, the data will be moved forward.
9. Destruction sequence table
Finally, of course, we must not forget to destroy the sequence list.
2. Complete code of sequence table.
list.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDataType;
//Dynamic storage of sequence table
typedef struct SeqList
{
SLDataType* array; // Points to a dynamically allocated array
size_t size; // Number of valid data
size_t capacity; //The size of the capacity space (if the space is not enough, it needs to be expanded)
}SeqList;
//Basic add, delete, check and modify interface
//Sequence table initialization
void SeqListInit(SeqList* psl);
// Check the space, if it is full, increase the capacity
void CheckCapacity(SeqList* psl);
//Insert at the end of the sequence table
void SeqListPushBack(SeqList* psl, SLDataType x);
//Delete at the end of the sequence table
void SeqListPopBack(SeqList* psl);
// Insert sequence header
void SeqListPushFront(SeqList* psl, SLDataType x);
//Delete sequence header
void SeqListPopFront(SeqList* psl);
//Sequence table lookup
int SeqListFind(SeqList* psl, SLDataType x);
// The sequence table inserts x at position pos
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
//Delete the value of pos position in the sequence table
void SeqListErase(SeqList* psl, size_t pos);
//Sequence list destroyed
void SeqListDestory(SeqList* psl);
//Print sequence table
void SeqListPrint(SeqList* psl);
list.c
#include"list.h"
//Sequence table initialization
void SeqListInit(SeqList* psl)
{
psl->array = NULL;
psl->capicity = 0;
psl->size = 0;
}
// Check the space, if it is full, increase the capacity
void CheckCapacity(SeqList* psl)
{
if (psl->size == psl->capicity)
{
int new = psl->capicity == 0 ? 4 : 2 * (psl->capicity);
SLDataType* temp = (SLDataType*)realloc(psl->array, sizeof(SLDataType) * new);
if (temp == NULL)
{
perror("realloc");
return;
}
psl->array = temp;
psl->capicity = new;
}
}
//Insert at the end of the sequence table
void SeqListPushBack(SeqList* psl, SLDataType x)
{
CheckCapacity(psl);
psl->array[psl->size] = x;
psl->size + + ;
}
//Delete at the end of the sequence table
void SeqListPopBack(SeqList* psl)
{
//Check if it is empty
assert(psl->size > 0);
psl->size--;
}
// Insert sequence header
void SeqListPushFront(SeqList* psl, SLDataType x)
{
CheckCapacity(psl);
int end = psl->size - 1;
while (end >= 0)
{
psl->array[end + 1] = psl->array[end];
--end;
}
psl->array[0] = x;
psl->size + + ;
}
//Delete sequence header
void SeqListPopFront(SeqList* psl)
{
//The data moves forward to cover, size--
assert(psl->size > 0);
int begin = 1;
while (begin < psl->size)
{
psl->array[begin - 1] = psl->array[begin];
}
psl->size--;
}
//Sequence table lookup
int SeqListFind(SeqList* psl, SLDataType x)
{
assert(psl);
for (int i = 0; i < psl->size; i + + )
{
if (psl->array[i] == x)
{
return i;
}
}
return -1;
}
// The sequence table inserts x at position pos
//Note that pos is a subscript here, starting from 0
//And size is the number of data
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
assert(psl);
assert(pos >= 0 & amp; & amp; pos <= psl->size);
CheckCapacity(psl);
int end = psl->size - 1;
while (end >= psl->size)
{
psl->array[end + 1] = psl->array[end];
--end;
}
psl->array[pos] = x;
psl->size + + ;
}
//Delete the value of pos position in the sequence table
void SeqListErase(SeqList* psl, size_t pos)
{
assert(psl);
assert(pos >= 0 & amp; & amp; pos <= psl->size);
int begin = pos;
while (begin < psl->size)
{
psl->array[begin] = psl->array[begin + 1];
+ + begin;
}
psl->size--;
}
//Sequence list destroyed
void SeqListDestory(SeqList* psl)
{
if (psl->array != NULL)
{
free(psl->array);
psl->array = NULL;
psl->capicity = 0;
psl->size = 0;
}
}
// Print sequence table
void SeqListPrint(SeqList* psl)
{
assert(psl);
for (int i = 0; i < psl->size; i + + )
{
printf("%d ", psl->array[i]);
}
printf("\
");
}
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 57323 people are learning the system