[Data structure] (sequence table) addition, deletion, checking and modification

Table of Contents

Foreword:

Sequence table:

1. Concept and classification

1.1 Sequence table classification

static sequence table

dynamic sequence table

2. Interface implementation

2.1 Functional requirements

2.2 Function implementation

Initialization sequence table

Destruction sequence table

Insert at the end of the sequential table

Check whether to expand the capacity

Print sequence table

Sequential header insertion

Sequence header deletion

Delete at the end of the sequence table

Insert value at pos position in sequence table

Delete the position of pos in the sequence table

total code

test.c

SeqList.c

SeqList.h

Foreword:

Data structures are the way computers store and organize data.

A data structure refers to a collection of data elements that have one or more specific relationships with each other. Data structure reflects the internal composition of data, that is, what parts of data are composed of, how it is composed, and the structure present among data elements.

Able to store data (such as sequence lists, linked lists, etc. structures)
Stored data can be easily found

Sequence table:

The data structure is divided into: Linear table and Nonlinear table,

Sequential tables are a subcategory of linear tables.

What is a linear table: A linear table refers to a finite sequence of n data elements with the same properties.

Common linear lists include: sequential lists, linked lists, stacks, queues, strings, etc.

Note: The physical structure of a linear list is not necessarily linear, but its logical structure must be linear (this is easy to understand. After we finish learning the golden partners of sequential lists and singly linked lists, I understand the meaning of this sentence. (The logical structure is similar to that imagined, such as arrows, which exist in memory))

The sequence list is a linear list.The sequence list is linear in both logical structure and physical structure.

1. Concept and classification

Sequence list (SeqList): A sequence list is a linear structure that uses a storage unit with a continuous physical address to store data elements in sequence (Continuous storage of data, no jumps).

Similar to an array, but the sequence list is continuous (can only be continuous from the beginning), and the array does not need to be continuous;

1.1 Sequence List Classification

static sequence table

Concept: Use fixed-length arrays to store elements

Defects: Too little space is not enough? Too much space results in a waste of space.

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

Dynamic sequence table

Concept: Use dynamically allocated array storage.

//Dynamic sequence table
typedef int SLDateType;
typedef struct SeqList
{
    SLDateType* array; //points to a dynamically opened array
    size_t size; //Data stored in data
    size_t capacity; //Capacity of array
}SeqList;

It is recommended to use Dynamic Sequence List. Compared with static sequence list, dynamic sequence list is easier to adjust the size of the sequence list. Next, I will also take the dynamic sequence table as an example to introduce how to implement the addition, deletion, checking and modification of the dynamic sequence table.

2. Interface implementation

2.1 Functional Requirements

#pragma once
#include<stdio.h>
#include<assert.h>

//Initialization of sequence table
void SeqListInit(SL* ps);

//Destroy the sequence table
void SeqListDestroy(SL* ps);

//Print the sequence table
void SeqListPrint(SL* ps);

//Insertion into the tail of the sequence table
void SeqListPushBack(SL* ps, SLDataType x);

//Insert into the head of the sequence table
void SeqListPushFront(SL* ps, SLDataType x);

//Delete the sequence header
void SeqListPopFront(SL* ps);

//Delete the tail of the sequence table
void SeqListPopBack(SL* ps);

//Sequence table lookup
//int SeqListFind(SeqList* ps, SLDateType x);
 
// The sequence table inserts x at position pos
void SeqListInsert(SL* ps, int pos, SLDataType x);


//Delete the value of pos position in the sequence table
void SeqListErase(SL* ps, int pos);

2.2 Function Implementation

Initialization sequence table

There’s not much to say, I’ve already talked about it in the [C Language] series, link 3 2 1

//Initialization
void SeqListInit(SL* ps)
{
assert(ps);
ps->arry = NULL;
ps->size = 0;
ps->capacity = 0;
}

Destruction sequence table

//Destroy
void SeqListDestroy(SL* ps)
{
assert(ps);
if (ps->arry != NULL)
{
free(ps->arry);
ps->arry = NULL;
ps->size = 0;
ps->capacity = 0;
}
}

Sequential end-of-table insertion

Here we need to check whether expansion is needed. We also need to encapsulate a function in advance.

//Tail insertion into sequence table
void SeqListPushBack(SL* ps, SLDataType x)
{
assert(ps);
//Check whether expansion is needed
CheckCapacity(ps);
ps->arry[ps->size] = x;
ps->size + + ;
}

Check whether the capacity is expanded

What needs to be noted here is that when we initialize, the capacity is 0. If we use the conventional *2 method to expand the capacity, 0*2 will still be 0;

So here you can use the previous ternary operator to avoid it; realloc can open up space for null pointers, which is equivalent to malloc

//Check whether expansion is needed
void CheckCapacity(SL* ps)
{
assert(ps);
if (ps->size == ps->capacity) //Need to expand capacity
{
int new =ps->capacity == 0 ? 4 :ps->capacity * 2;
SLDataType* tmp = (SLDataType*)realloc(ps->arry, sizeof(SLDataType)*new);
//Check whether the expansion is successful
if (tmp == NULL)
{
perror("realloc");
return;
}
ps->arry = tmp;
ps->capacity = new;
printf("Expansion successful\\
");
}
}

Print sequence table

//Print sequence table
void SeqListPrint(SL* ps)
{
assert(ps);
int i = 0;
for (i = 0; i < ps->size; i + + )
{
printf("%d ", ps->arry[i]);
}
printf("\\
");
}

Regardless of whether it is inserted at the beginning or at the end or inserted at any subsequent position, you need to check whether expansion is needed.

Header insertion is equivalent to moving the data to the right first, leaving the head position empty, and then inserting new data.

//Header insertion
void SeqListPushFront(SL* ps, SLDataType x)
{
assert(ps);
CheckCapacity(ps);
int begin = ps->size;
while (begin>0)
{
ps->arry[begin] = ps->arry[begin - 1];
begin--;
}
ps->arry[0] = x;
ps->size + + ;
}

Because the logical structure of the sequence table is consistent with the physical structure, and the data is closely connected, the data can be directly overwritten forward.

//Header deletion
void SeqListPopFront(SL* ps)
{
assert(ps);
int begin = 1;
while (begin > 0 & amp; & amp; begin < ps->size )
{
ps->arry[begin - 1] = ps->arry[begin];
begin++;
}
ps->size--;
}

Delete at the end of the sequential table

What needs attention is that when the size reaches a negative number, we adopt a “Septwolves-style warning” and directly “fry meat with bamboo strips”

//Delete the tail
void SeqListPopBack(SL* ps)
{
assert(ps);
//Check the size to prevent crossing the boundary
assert(ps->size > 0);
ps->size--;
}

Insert value at pos position in sequence table

Insert at any position within the capacity, move the data after that position back, and assign the new element

//The sequence table inserts x at position pos
void SeqListInsert(SL* ps, int pos, SLDataType x)
{
assert(ps);
assert(pos >= 0 & amp; & amp; pos <= ps->size);
CheckCapacity(ps);
int begin = ps->size;
while (begin > pos)
{
ps->arry[begin] = ps->arry[begin - 1];
begin--;
}
ps->arry[pos] = x;
ps->size + + ;
}

Delete the position of pos in the sequence table

//Delete the value of pos position in the sequence table
void SeqListErase(SL* ps, int pos)
{
assert(ps);
assert(pos >= 0 & amp; & amp; pos <= ps->size);
int begin = pos;
while (begin < ps->size)
{
ps->arry[begin] = ps->arry[begin + 1];
begin++;
}
ps->size--;
}

Total code

Note that when we complete each function implementation, it is best to test it separately and do not leave it to the end, otherwise it will be like this

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
//11-4
#include<stdio.h>

void test1()
{
SL s1;
SeqListInit( & amp;s1);
SeqListPushBack( & amp;s1,1);
SeqListPrint( & amp;s1);

SeqListDestroy( & amp;s1);
}

void test2()
{
SL s2;
SeqListInit( & amp;s2);
SeqListPushBack( & amp;s2, 1);
SeqListPushBack( & amp;s2, 2);
SeqListPushBack( & amp;s2, 3);
SeqListPushBack( & amp;s2, 4);
SeqListPushBack( & amp;s2, 5);

SeqListPushFront( & amp;s2,10);
SeqListPrint( &s2);
\t
}

//void test3()
//{
//SL s3;
// SeqListInit( & amp;s3);
// SeqListPushBack( & amp;s3, 1);
// SeqListPushBack( & amp;s3, 2);
// SeqListPushBack( & amp;s3, 3);
// SeqListPushBack( & amp;s3, 4);
// SeqListPushBack( & amp;s3, 5);
// SeqListPrint( & amp;s3);
//
// SeqListPopFront( & amp;s3);
// SeqListPrint( & amp;s3);
//}

void test4()
{
SL s4;
SeqListInit( & amp;s4);
SeqListPushBack( & amp;s4, 1);
SeqListPushBack( & amp;s4, 2);
SeqListPushBack( & amp;s4, 3);
SeqListPushBack( & amp;s4, 4);
SeqListPushBack( & amp;s4, 5);
SeqListPrint( &s4);

SeqListInsert( &s4, 2, 66);
SeqListPrint( &s4);
}
void test5()
{
SLs5;
SeqListInit( & amp;s5);
SeqListPushBack( & amp;s5, 1);
SeqListPushBack( & amp;s5, 2);
SeqListPushBack( & amp;s5, 3);
SeqListPushBack( & amp;s5, 4);
SeqListPushBack( & amp;s5, 5);
SeqListPrint( &s5);
SeqListErase( & amp;s5, 2);
SeqListPrint( &s5);
}
int main()
{
//test1();
//test2();
//test3();
//test4();
test5();
return 0;
}

SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
//Initialization
void SeqListInit(SL* ps)
{
assert(ps);
ps->arry = NULL;
ps->size = 0;
ps->capacity = 0;
}
//Destroy
void SeqListDestroy(SL* ps)
{
assert(ps);
if (ps->arry != NULL)
{
free(ps->arry);
ps->arry = NULL;
ps->size = 0;
ps->capacity = 0;
}
}
//Check whether expansion is needed
void CheckCapacity(SL* ps)
{
assert(ps);
if (ps->size == ps->capacity) //Need to expand capacity
{
int new =ps->capacity == 0 ? 4 :ps->capacity * 2;
SLDataType* tmp = (SLDataType*)realloc(ps->arry, sizeof(SLDataType)*new);
//Check whether the expansion is successful
if (tmp == NULL)
{
perror("realloc");
return;
}
ps->arry = tmp;
ps->capacity = new;
printf("Expansion successful\\
");
}
\t
}
//Insertion into the tail of the sequence table
void SeqListPushBack(SL* ps, SLDataType x)
{
assert(ps);
//Check whether expansion is needed
CheckCapacity(ps);
ps->arry[ps->size] = x;
ps->size + + ;
}
//Print sequence table
void SeqListPrint(SL* ps)
{
assert(ps);
int i = 0;
for (i = 0; i < ps->size; i + + )
{
printf("%d ", ps->arry[i]);
}
printf("\\
");
}
//Header insertion
void SeqListPushFront(SL* ps, SLDataType x)
{
assert(ps);
CheckCapacity(ps);
int begin = ps->size;
while (begin>0)
{
ps->arry[begin] = ps->arry[begin - 1];
begin--;
}
ps->arry[0] = x;
ps->size + + ;
}
//Header deletion
void SeqListPopFront(SL* ps)
{
assert(ps);
int begin = 1;
while (begin > 0 & amp; & amp; begin < ps->size )
{
ps->arry[begin - 1] = ps->arry[begin];
begin++;
}
ps->size--;
}
//Delete tail
void SeqListPopBack(SL* ps)
{
assert(ps);
//Check the size to prevent crossing the boundary
assert(ps->size > 0);
ps->size--;
}

// The sequence table inserts x at position pos
void SeqListInsert(SL* ps, int pos, SLDataType x)
{
assert(ps);
assert(pos >= 0 & amp; & amp; pos <= ps->size);
CheckCapacity(ps);
int begin = ps->size;
while (begin > pos)
{
ps->arry[begin] = ps->arry[begin - 1];
begin--;
}
ps->arry[pos] = x;
ps->size + + ;
}

//Delete the value of pos position in the sequence table
void SeqListErase(SL* ps, int pos)
{
assert(ps);
assert(pos >= 0 & amp; & amp; pos <= ps->size);
int begin = pos;
while (begin < ps->size)
{
ps->arry[begin] = ps->arry[begin + 1];
begin++;
}
ps->size--;

SeqList.h

#pragma once
#include<stdio.h>
#include<assert.h>
typedef int SLDataType;

typedef struct SeqList
{
SLDataType* arry; //Dynamicly developed array
int size; //Number of records
int capacity; //record capacity
}SL;



//Initialization of sequence table
void SeqListInit(SL* ps);

//Destroy the sequence table
void SeqListDestroy(SL* ps);

//Print the sequence table
void SeqListPrint(SL* ps);

//Insertion into the tail of the sequence table
void SeqListPushBack(SL* ps, SLDataType x);

//Insert into the head of the sequence table
void SeqListPushFront(SL* ps, SLDataType x);

//Delete the sequence header
void SeqListPopFront(SL* ps);

//Delete the tail of the sequence table
void SeqListPopBack(SL* ps);

//Sequence table lookup
//int SeqListFind(SeqList* ps, SLDateType x);
 
// The sequence table inserts x at position pos
void SeqListInsert(SL* ps, int pos, SLDataType x);


//Delete the value of pos position in the sequence table
void SeqListErase(SL* ps, int pos);

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

Foreword:

Sequence table:

1. Concept and classification

1.1 Sequence List Classification

static sequence table

Dynamic sequence table

2. Interface implementation

2.1 Functional Requirements

2.2 Function Implementation

Initialization sequence table

Destruction sequence table

Sequential end-of-table insertion

Check whether the capacity is expanded

Print sequence table

Sequential header insertion

Sequential header deletion

Delete at the end of the sequential table

Insert value at pos position in sequence table

Delete the position of pos in the sequence table

Total code

test.c

SeqList.c

SeqList.h