Before learning data structures, you should generally have pre knowledge of classes and objects:

Class is the basis of information encapsulation in Object-Oriented Programming (OOP). Class is a user-defined reference data type, also known as class type. Each class contains data description and a set of functions to operate data or pass messages. The instance of class is called object.

C + + class definition

Defining a class is essentially a blueprint for defining a data type. This does not actually define any data, but it defines what the class name means, that is, it defines what the class object includes and what operations can be performed on this object.

In fact, when you learn class, you will inevitably think of the structure struct learned from C program. What is the difference between class and struct? Some functions of class and struct are similar, but class belongs to data type, while struct belongs to value type. Class can define abstract data type ADT, but class can't. more importantly, class is like a robot equipped with various tool functions. It not only has various tools, but also programs how to use these tools, and struct is like a toolbox.

How to define a class?

class Class name
{
 
public:
public members 
private:
Private member
 
protected:
Protect members
};

The keyword "class" defines the Box data type, as shown below:

class Box
{
   public:
      double length;   // Length of box
      double breadth;  // Width of box
      double height;   // Height of box
};

The keyword public determines the access properties of class members. Within the scope of a class object, public members are accessible outside the class. You can also specify that the members of the class are private or protected.

Define C + + objects

Classes provide a blueprint for objects, so basically, objects are created based on classes. Declaring objects of classes is like declaring variables of basic types. The following statement declares two objects of class Box:

Box Box1;          // Declare Box1, type Box
Box Box2;          // Declare Box2, type Box

Access object members are used To use.

C + + class member functions

Class member functions refer to those functions that write definitions and prototypes inside the class definition, just like other variables in the class definition. Class member function is a member of a class. It can operate any object of the class and access all members in the object.

Let's take a look at the previously defined class Box. Now we want to use the member function to access the members of the class instead of directly accessing the members of these classes:

class Box
{
   public:
      double length;         // length
      double breadth;        // width
      double height;         // height
      double getVolume(void);// Return volume
};

getVolume is a class function.

You can define this class function outside the class in this way. Of course, you can also put the definition inside the class. Both of these are legal.

double Box::getVolume(void)
{
    return length * breadth * height;
}

Using class functions for classes is also very simple, just like accessing public variables of classes:

Box myBox;          // Create an object
 
myBox.getVolume();  // Call the member function of the object

C + + class constructor & destructor

Class constructor

The constructor of a class is a special member function of a class, which is executed every time a new object of the class is created.

The constructor name is exactly the same as the class name, and will not return any type, nor will it return void. Constructors can be used to set initial values for some member variables.

The following example helps to better understand the concept of constructor:

#include <iostream>
 
using namespace std;
 
class Line
{
   public:
      void setLength( double len );
      double getLength( void );
      Line();  // This is a constructor
 
   private:
      double length;
};
 
// Member function definitions, including constructors
Line::Line(void)
{
    cout << "Object is being created" << endl;
}
 
void Line::setLength( double len )
{
    length = len;
}
 
double Line::getLength( void )
{
    return length;
}
// Main function of program
int main( )
{
   Line line;
 
   // Set length
   line.setLength(6.0); 
   cout << "Length of line : " << line.getLength() <<endl;
 
   return 0;
}

Output results:

Object is being created
Length of line : 6

The default constructor does not have any parameters, but it can also take parameters if necessary. In this way, the object will be assigned an initial value when it is created, as shown in the following example:

#include <iostream>
 
using namespace std;
 
class Line
{
   public:
      void setLength( double len );
      double getLength( void );
      Line(double len);  // This is a constructor
 
   private:
      double length;
};
 
// Member function definitions, including constructors
Line::Line( double len)
{
    cout << "Object is being created, length = " << len << endl;
    length = len;
}
 
void Line::setLength( double len )
{
    length = len;
}
 
double Line::getLength( void )
{
    return length;
}
// Main function of program
int main( )
{
   Line line(10.0);
 
   // Gets the length of the default setting
   cout << "Length of line : " << line.getLength() <<endl;
   // Set the length again
   line.setLength(6.0); 
   cout << "Length of line : " << line.getLength() <<endl;
 
   return 0;
}

When the function of the above class is created, the len value of the new class is assigned.

Object is being created, length = 10
Length of line : 10
Length of line : 6

Check the output. Obviously, len==10;

Class destructor

Class destructor is a special member function of a class, which is executed every time the created object is deleted.

The name of the destructor is exactly the same as that of the class, except that it is prefixed with a tilde (~), which will not return any value or take any parameters. The destructor helps to release resources before jumping out of the program (such as closing files, freeing memory, etc.).

#include <iostream>
 
using namespace std;
 
class Line
{
   public:
      void setLength( double len );
      double getLength( void );
      Line();   // This is a constructor declaration
      ~Line();  // This is the destructor declaration
 
   private:
      double length;
};
 
// Member function definitions, including constructors
Line::Line(void)
{
    cout << "Object is being created" << endl;
}
Line::~Line(void)
{
    cout << "Object is being deleted" << endl;
}
 
void Line::setLength( double len )
{
    length = len;
}
 
double Line::getLength( void )
{
    return length;
}
// Main function of program
int main( )
{
   Line line;
 
   // Set length
   line.setLength(6.0); 
   cout << "Length of line : " << line.getLength() <<endl;
 
   return 0;
}

Output results:

Object is being created
Length of line : 6
Object is being deleted

OK, the class knowledge has been supplemented.

The following is the knowledge of linear tables:

Basic architecture of a sequential table class: (taking abstract data types as an example)

 

The operation of a linear table is nothing more than: find a specific element and return a value / address; Add / delete elements in the table; Returns the table length.

The sequential table has two structures: sequential storage and chain storage. The difference is mainly reflected in the position of data in memory. The former has a whole block of continuous memory, while the latter is random storage. There is no physical adjacency, but represents the predecessor and successor through pointers. Therefore, the two storage structures are also somewhat different at the code level:

For the reference of class definition, if there is no accident, because of the advantages of class in structure storage, we generally use class to implement sequence table

This figure is from SZUOJ

As shown in the figure, get is a search, while insert and del correspond to addition and deletion. Finally, the size of the table length and the output module display are obtained. The name can be changed according to your preference. Anyway, it's OK. The functions of creating and deconstructing classes mentioned above and other functions mentioned below.

The first is the int list above_ size() ; Calculation table length;

int SeqList::list_size(){//Check list length function
   int i;
    for(i=0;i<4;i++){
       if(this== nullptr)
           break;
       else continue;

   }

    return this->size;
}

Get element int list_get(int i) //i is location

int SeqList::list_get(int i)//Query function
{   
    if (i < 1 || (i > list_size()))
    {
      	cout<<"error\n";
        return 0;
    }
    //The sequence number of the data element starts from 1, the following table of the array starts from 0, and the array subscript corresponding to the ith element is i-1;
    cout<< this->list[i]<<endl;


}

This is followed by the insert operation int list_insert(int i,int item)

int SeqList::list_insert(int i,int item){
//Insert element function

    int*p,*q;

    if(i<1||i>size+1){ 
        cout<<"error\n";
        return error;
    }


    else if(this->size>=maxsize)
    {
        cout<<"error\n";
        return 0;
    }

    else
    {
        
        q=&(this->list[i]);  //Insertion position
        p=this->list+this->size+1;//p points to the last position

        for(p=(this->list)+(this->size); p>=q; p--) *(p+1)=*(p); //Move back
        *q=e;   //Insert e

        this->size++;    //Table length plus 1


    }
    list_display();
//Insert function complete -- run through.

    return 0;
}

When you see that you need to move a group of elements back here, you can know that this is sequential storage. When frequent insertion and deletion are required, the feature of sequential storage will greatly reduce the running speed of the program. This is the advantage of chained storage.

Finally, delete int list_del(int i)

int list_dei(int i){
    if(i<1||i>size+1) {
        cout<<"error\n";
        return 0;
    }

    //int*e =this->list[i - 1];
    for (int k = i; k < this->size+1; k++)
    {
        this->list[k - 1] = this->list[k];
    }
    this->size--;//abnormal
    list_display();
    return 0;

}