Table of Contents
1. Initial definition of sequence table
1.1 Create new header files and source files
1.2 Preparation work in SeqList.h
2. Initialization and destruction of sequence tables
3. Insert elements from beginning to end
4. Delete elements from beginning to end
5. Insert elements in the middle
6. Delete elements in the middle
7. Find the subscript of the specified element
8. Source code
1. Initial definition of sequence table
1.1 New header file and source file
When we want to implement the address book, we will customize a contact.h file to store our various declarations, customize a contact.c file to store the functions that implement the declaration, and there will also be a test.c to test us Code feasibility.
When we study the sequence table here, we should also use this method to divide our code to make the program more concise and attractive: 
In SeqList.h, we need to declare the header files we need, the redefined types, the functions we need…
Preparation work in 1.2 SeqList.h
In order to facilitate us to modify the data type in the sequence table, we redefine the type in our sequence table (int as an example) as SLDataType. In this way, if we want to modify the data type in the future, we can directly change int to double here. …..
typedef int SLDataType;
Secondly, the sequence table we defined is actually a structure, which contains a table header (a pointer), the actual saved data and the capacity of the table. Here we also redefine the structure name to an abbreviation to facilitate subsequent use.
typedef struct SeqList
{
int* p;//header
int size;//The actual amount of data stored
int capacity;//The capacity in the table at this time
}SL;
What characteristics should our sequence table have?
1. Dynamic storage, which can dynamically open up space for use
2. Add, delete, check and modify various positions, divided into head, tail and middle.
2. Initialization and destruction of sequence table
Initialization and destruction:
First, use assertions to ensure that the incoming pointer is not null. Secondly, we need to use the SLInit function to assign initial values to the data in the structure one by one. Secondly, when destroying the data, we must also ensure that the object of the free function is a non-null pointer. Then re-initialize the data.
void SLInit(SL* psl) //Initialization sequence table
{
assert(psl != NULL);
psl->p = NULL;
psl->size = 0;
psl->capacity = 0;
}
void SLDestroy(SL* psl) //Destroy sequence table
{
assert(psl != NULL);
if (psl->p != NULL)
{
free(psl->p);
psl->size = 0;
psl->capacity = 0;
}
}
Because our sequence table opens up space dynamically, it is necessary to write a function to check the real-time capacity. Here we use the double expansion method to open up memory space, but during initialization we assign our capacity to 0 , it is still 0 when double expansion is performed. At this time, the ternary operator can be used to perfectly avoid this problem.
Check and expand capacity:
And we use new temporary variables to save the expanded space, and then return the value to the original variable when there is no problem.
void SLCheckCapacity(SL* psl)
{
assert(psl != NULL);
if (psl->size == psl->capacity)
{
//Because the capacity is 0 during initialization, it will also be 0 after double expansion. The ternary operator can be used here to solve the problem very well.
SLDataType NewCapacity = (psl->capacity == 0) ? 4 : psl->capacity * 2;
//The dynamically opened space is for the sequence table. Be careful not to reverse the upper and lower data of the new row.
//sizeof() Don’t forget! !
SLDataType* tmp = (SLDataType*)realloc(psl->p, sizeof(SL) * NewCapacity);
if (tmp == NULL)
{
perror("SLCheckCapacity -> realloc");
return;
}
psl->capacity = NewCapacity;
psl->p = tmp;
}
}
3. Insert elements at the beginning and end
Print sequence table:
In order to better test our code, we can first write a printing function to print our sequence list.
void SLPrint(SL* psl)
{
assert(psl != NULL);
int i = 0;
for (; i < psl->size; i + + )
{
printf("%d ", psl->p[i]);
}
printf("\\
");
}
Insert element at the end:
void SLPushBack(SL* psl, SLDataType x)
{
assert(psl != NULL);
SLCheckCapacity(psl);//Check whether expansion is needed
psl->p[psl->size] = x;
psl->size + + ;
}
Header insertion element:
Inserting elements at the head is a little more complicated than inserting elements at the tail. We need to let the previous elements cover the following elements. In the figure below, we simulate 8 elements in the sequence table (size == 8). Let’s take a look at how our code should be written. ：
We let i start from the back and move forward to ensure that useful elements will not be overwritten. At the same time, we infer the value range of i based on the coverage subscripts of the first and last elements.
//The first value
void SLPushFront(SL* psl, SLDataType x)
{
assert(psl != NULL);
SLCheckCapacity(psl);
int i = psl->size;
for (; i > 0; i--)
{
psl->p[i] = psl->p[i - 1];
}
psl->p[0] = x;
psl->size + + ;
}
//Second value
void SLPushFront(SL* ps, SLDateType x)//?Pro? O(n); n O(n^2)
{
assert(ps != NULL);
SLCheckCapacity(ps);
int i = ps->size - 1;
for (; i >= 0; i--)
{
ps->p[i + 1] = ps->p[i];
}
ps->p[0] = x;
ps->size + + ;
}
4. Delete elements from the beginning and the end
Remove elements at the end:
Here we use the size– method, so that we cannot directly access the last element. The next time it is added, it will be overwritten by a new element to achieve the deletion operation. At the same time, it is asserted that our actual number of elements must be more than 0
void SLPopBack(SL* psl)
{
assert(psl != NULL);
assert(psl->size > 0);
psl->size--;
}
Header deleted element:
void SLPopFront(SL* psl)
{
assert(psl != NULL);
int i = 1;
for (; i <= psl->size; i + + )
{
psl->p[i - 1] = psl->p[i];
}
psl->size--;
}
void SLPopFront(SL* ps)
{
assert(ps != NULL);
assert(ps->size > 0);
int i = 0;
for (; i < ps->size - 1; i + + )
{
ps->p[i] = ps->p[i + 1];
}
ps->size--;
}
5. Inserting elements in the middle
void SLInsert(SL* psl, int num, SLDataType x)
{
assert(psl != NULL);
assert(num >= 0 & amp; & amp; num <= psl->size);
SLCheckCapacity(psl);
int i = psl->size - 1;
for (; i >= num; i--)
{
psl->p[i + 1] = psl->p[i];
}
psl->p[num] = x;
psl->size + + ;
}
6. Delete elements in the middle
void SLErase(SL* psl, int num)
{
assert(psl != NULL);
assert(num >= 0 & amp; & amp; num < psl->size);
SLCheckCapacity(psl);
int i = num;
for (; i < psl->size - 1; i + + )
{
psl->p[i] = psl->p[i + 1];
}
psl->size--;
}
7. Find the subscript of the specified element
int SLFind(SL* ps, SLDataType x)
{
assert(ps != NULL);
int i = 0;
for (; i < ps->size; i + + )
{
if (ps->p[i] == x)
{
return i;
}
}
return -1;
}
Eight. Source Code
Welcome to my Gitee – Gitee.com
https://gitee.com/bright-and-sparkling-at-night/studying /commit/dd1f9978f81f9decce01805623b4708b7671f3e0
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 57207 people are learning the system