Newcomer Xiaobai's blog
️ I hope you will pay more attention
It will be updated frequently in the future ~
️ Personal home page ： Collection and attention , Never get lost ~ ️

---

Preface

Programming to achieve the following basic operations of the sequence table ： Create sequence table , Modify sequence table , Insert sequence table , Delete order table .

---

Tips： It's a little long , Little Lord, please watch patiently ~~

One 、 Purpose

Deep understanding of the logical structure of the sequence table 、 Physical structure and other concepts , Master the programming implementation of the basic operation of the sequence table , Note that the sequence table is inserted 、 The movement of data elements during operations such as deletion . When writing a program , Consider the robustness of the program , Master the method of returning function results through function parameters .ヾ(◍°∇°◍)ﾉﾞ

Two 、 step

1. Define storage representation

For example, the maximum length of the sequence table , Storage base address , Watch length, etc .

// Define storage representation 
typedef int ElemType;       // Definition ElemType The type is int
# define MAXSIZE 100 //  The maximum length of the sequence table 

typedef struct              // If you don't use it later , The structure name can be omitted 
{
    
    ElemType *elem;         // Storage base address 
    int    length;          // Current table length （ Especially the number of elements ）
} SqList;

2. Define the operation function

Initialize the function , Construct functions that destroy linear tables DestoryList, Clear the function of linear table ClearList, Find the function of linear table length GetLength, A function that determines whether the linear table is empty ListEmpty, Gets the content of the element at the specified position in the linear table GetElem, Seeking precursor 、 Subsequent functions , A function that inserts an element at a specified position in a linear table ListInsert, Delete linear table specified location element ListDelete, Show linear table functions and exit operations .

// Define the operation function 
typedef int Status;
Status   InitList(SqList &L)
{
    
    // Construct an empty linear table L.
    L.elem = new ElemType[MAXSIZE];
    L.length = 0;  //  The length of the empty meter is 0
    return   1;
}

void DestroyList(SqList &L)
{
    
    if (L.elem) delete[ ] L.elem;    // Free up storage space 
    L.length=0;
    L.elem=NULL;
}

int GetLength(SqList L)
{
    
    return L.length;
}

bool ListEmpty(SqList L)
{
    
    if (L.length==0)
        return true;
    else
        return false;
}

Status ListInsert(SqList &L,int i,ElemType e)
{
    
    if(i<1 || i>L.length+1)  return -1;   //i Illegal value 
    if(L.length==MAXSIZE)  return -1;
    // The current storage space is full 
    for( int j=L.length-1; j>=i-1 ; j--)
        L.elem[ j+1]=L.elem[ j];   // The insertion position and subsequent elements are moved backward 
    L.elem[i-1]=e;                     // The new element e Put in the i A place 
    ++L.length;	// Table length increase 1
    return 1;
}

Status ListDelete(SqList &L,int i, ElemType &e)
{
    
    if((i<1)||(i>L.length)) return -1;	 //i Illegal value 
    e=L.elem[i-1];
    for (int j=i; j<=L.length-1; j++)
        L.elem[ j-1]=L.elem[j];// The element after the deleted element moves forward 
    --L.length;               	      // Watch length minus 1
    return 1;
}

Status ListPrior(SqList &L,int i,ElemType &e)
{
    
    if((i<2)||(i>L.length)) return -1;	 //i Illegal value 
    else cout<<L.elem[i-2]<<endl;
    return 1;
}

Status ListNext(SqList &L,int i,ElemType &e)
{
    
    if((i<1)||(i>L.length-1)) return -1;	 //i Illegal value 
    else cout<<L.elem[i]<<endl;
    return 1;
}

void DisplayList(SqList L)
{
    
    for(int i=1; i<=L.length; ++i)
        cout<<L.elem[i-1]<<" ";
    cout<<endl;
}

void ClearList(SqList &L)
{
    
    L.length=0;                // Set the length of the linear table to 0
}

Status GetElem(SqList L,int i,ElemType &e)
{
    
    // Judge i Whether the value is reasonable , If it's not reasonable , return ERROR
    if (i<1||i>L.length) return -1;
    e=L.elem[i-1];   // The first i-1 The first unit stores the i Data 
    return 1;
}

3. The menu style is adopted to make the operation more convenient and clear .

This function is used to realize a small menu

void show_help()
{
    
    cout<<"******* Data Structure ******"<<endl;
    cout<<"1---- Empty the linear table "<<endl;
    cout<<"2---- Determine whether the linear table is empty "<<endl;
    cout<<"3---- Find the length of the linear meter "<<endl;
    cout<<"4---- Get the location element specified in the linear table "<<endl;
    cout<<"5---- Seeking precursor "<<endl;
    cout<<"6---- Succ "<<endl;
    cout<<"7---- Insert the element in the specified position of the linear table "<<endl;
    cout<<"8---- Delete linear table specified location element "<<endl;
    cout<<"9---- Show linear table "<<endl;
    cout<<"  sign out , Input 0"<<endl;

}

4. Debug the experimental code and test it , The experimental results are obtained .

Here comes the complete code ：

#include <iostream>

using namespace std;
// Define storage representation 
typedef int ElemType;       // Definition ElemType The type is int
# define MAXSIZE 100 //  The maximum length of the sequence table 

typedef struct              // If you don't use it later , The structure name can be omitted 
{
    
    ElemType *elem;         // Storage base address 
    int    length;          // Current table length （ Especially the number of elements ）
} SqList;

// Define the operation function 
typedef int Status;
Status   InitList(SqList &L)
{
    
    // Construct an empty linear table L.
    L.elem = new ElemType[MAXSIZE];
    L.length = 0;  //  The length of the empty meter is 0
    return   1;
}


void DestroyList(SqList &L)
{
    
    if (L.elem) delete[ ] L.elem;    // Free up storage space 
    L.length=0;
    L.elem=NULL;
}


int GetLength(SqList L)
{
    
    return L.length;
}

bool ListEmpty(SqList L)
{
    
    if (L.length==0)
        return true;
    else
        return false;
}

Status ListInsert(SqList &L,int i,ElemType e)
{
    
    if(i<1 || i>L.length+1)  return -1;   //i Illegal value 
    if(L.length==MAXSIZE)  return -1;
    // The current storage space is full 
    for( int j=L.length-1; j>=i-1 ; j--)
        L.elem[ j+1]=L.elem[ j];   // The insertion position and subsequent elements are moved backward 
    L.elem[i-1]=e;                     // The new element e Put in the i A place 
    ++L.length;	// Table length increase 1
    return 1;
}
Status ListDelete(SqList &L,int i, ElemType &e)
{
    
    if((i<1)||(i>L.length)) return -1;	 //i Illegal value 
    e=L.elem[i-1];
    for (int j=i; j<=L.length-1; j++)
        L.elem[ j-1]=L.elem[j];// The element after the deleted element moves forward 
    --L.length;               	      // Watch length minus 1
    return 1;
}
Status ListPrior(SqList &L,int i,ElemType &e)
{
    
    if((i<2)||(i>L.length)) return -1;	 //i Illegal value 
    else cout<<L.elem[i-2]<<endl;
    return 1;
}
Status ListNext(SqList &L,int i,ElemType &e)
{
    
    if((i<1)||(i>L.length-1)) return -1;	 //i Illegal value 
    else cout<<L.elem[i]<<endl;
    return 1;
}

void show_help()
{
    
    cout<<"******* Data Structure ******"<<endl;
    cout<<"1---- Empty the linear table "<<endl;
    cout<<"2---- Determine whether the linear table is empty "<<endl;
    cout<<"3---- Find the length of the linear meter "<<endl;
    cout<<"4---- Get the location element specified in the linear table "<<endl;
    cout<<"5---- Seeking precursor "<<endl;
    cout<<"6---- Succ "<<endl;
    cout<<"7---- Insert the element in the specified position of the linear table "<<endl;
    cout<<"8---- Delete linear table specified location element "<<endl;
    cout<<"9---- Show linear table "<<endl;
    cout<<"  sign out , Input 0"<<endl;

}
void DisplayList(SqList L)
{
    
    for(int i=1; i<=L.length; ++i)
        cout<<L.elem[i-1]<<" ";
    cout<<endl;
}
void ClearList(SqList &L)
{
    
    L.length=0;                // Set the length of the linear table to 0
}
Status GetElem(SqList L,int i,ElemType &e)
{
    
    // Judge i Whether the value is reasonable , If it's not reasonable , return ERROR
    if (i<1||i>L.length) return -1;
    e=L.elem[i-1];   // The first i-1 The first unit stores the i Data 
    return 1;
}


int main()
{
    
    char operate_code;
    show_help();
    // Define linear table variables , Such as SqList L;
    SqList L;
    // Call the initialization linear table function , Such as Init_List(L);
    InitList(L);
    ElemType e;
    int i;
    while(1)
    {
    
        cout<<" Please enter the operation code :";
        cin>>operate_code;
        if(operate_code=='1')
        {
    
            cout<<"The list has been cleared."<<endl;
            ClearList(L);// Call the operation function 

        }
        else if (operate_code=='2')
        {
    
            if(ListEmpty(L))
                cout<<"The list is empty."<<endl;
            else
                cout<<"The list is not empty."<<endl;

        }
        else if (operate_code=='3')
        {
    
            cout<<"The length of list is:"<<GetLength(L)<<endl;

        }
        else if (operate_code=='4')
        {
    
            cout<<" Please enter the specified location ："<<endl;
            cin>>i;
            if(GetElem(L,i,e) == 1) cout<<" The location of the data is ："<<e<<endl;
            else cout <<"error"<<endl;
        }
        else if (operate_code=='5')
        {
    
            cout<<" Please enter the precursor of which element you want to find ："<<endl;
            cin>>i;
            if(ListPrior(L,i,e) == -1) cout<<"error"<<endl;
        }
        else if (operate_code=='6')
        {
    
            cout<<" Please enter the successor of the element you want to find ："<<endl;
            cin>>i;
            if(ListNext(L,i,e)==-1) cout<<"error"<<endl;
        }
        else if (operate_code=='7')
        {
    
            cout<<" Please enter the inserted element and its location ："<<endl;
            cin>>e>>i;
            ListInsert(L,i,e);

        }
        else if (operate_code=='8')
        {
    
            cout<<" Please enter where you want to delete the element ："<<endl;
            cin>>i;
            if(ListDelete(L,i,e)==-1)  cout<<"error"<<endl;

        }
        else if (operate_code=='9')
        {
    
            cout<<"The contents of the list are:"<<endl;
            DisplayList(L);

        }
        else if (operate_code=='0')
        {
    
            break;
        }
        else
        {
    
            cout<<"\n Opcode error ！！！"<<endl;
            show_help();
        }
    }
    // Call the destroy linear table function , Such as Destroy_List(L);
    DestroyList(L);
    return 0;
}

Tips： It's almost over ~~

3、 ... and 、 Experimental data recording and operation results

Call each operation through the menu ：
1️⃣ insert data （ data , Location ）, When the input position is illegal , The linear table does not show . Such as ：（1,0）、（1 ,2）. Then insert it correctly 3 Data （2,1）、（1,1）、（3,3）;
2️⃣ Display the data in the sequence table , Screen output 1, 2, 3;
3️⃣ Sentenced to empty , The screen output sequence table is not empty ;
4️⃣ Output sequence table length , Screen output 3;
5️⃣ Get the specified location element , The specified position to be measured is 【1,3】 Situations outside the scope and within the scope ;
6️⃣ location , Input ：4, Output ： non-existent , Input 2, The output position is 2;
7️⃣ Ask for a direct precursor , To measure the precursor of the first element 、 There is no direct precursor to the elements in the sequence table , Direct precursors of other elements ;
8️⃣ Ask for a direct successor , To test the successor of the last element 、 There is no direct successor to the elements in the sequence table , Direct successor to other elements ;
9️⃣ Delete , The position to be measured is 【1,3】 Situations outside the scope and within the scope ;
Measure the length after emptying ;

---

Conclusion

This paper is used to introduce the code implementation process and running result example of sequence table in data structure . Use menu style to realize the following basic operations of sequence table ： Create sequence table , Modify sequence table , Insert sequence table , Delete order table .