Basic operation implementation of sequence table

Catalog

1.　 Definition of sequence table

2.　 Implementation of basic operation of sequence table  

(1)　 The insert  

(2)　 Delete operation

(3)　 According to the value lookup （ In order to find ）

---

1.　 Definition of sequence table

　　 The sequential storage of linear table is also called sequential table . It is a group of storage units with continuous addresses that successively store the data elements in the linear table , Thus, two logically adjacent elements are also adjacent in physical position .

Assume that the element type of the linear table is ElemType , Then the sequential storage type of the linear table is described as ：

#define MaxSize 50                // Defines the maximum length of a linear table 
typedef struct{
    ElemType data[MaxSize];       // Elements of a sequence table 
    int length;                   // The current length of the sequence table 
}SqList;                          // Type definition of sequence table 

　　 One dimensional arrays can be statically allocated , It can also be dynamically allocated .  In static allocation , Because the size and space of the array have been fixed in advance , Once the space is full , Adding new data will create an overflow , And then cause the program to crash .

　　 And in dynamic allocation , The space for storing arrays is allocated by dynamically storing statements during the execution of the program , Once the data space is full , Just open up a bigger storage space , To replace the original storage space , So as to achieve the purpose of expanding the storage array space , There is no need to divide all spaces for the linear table at one time .

#define MaxSize 100                // The initial definition of table length 
typedef struct{
    ElemType *data;                // Pointer to dynamically allocate array 
    int MaxSize,length;            // The maximum capacity and current number of arrays 
}SeqList;                          // Type definition of dynamic allocation array order table 

Ｃ The initial dynamic allocation statement of is ：

L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);

Ｃ++ The initial dynamic allocation statement of is ：

L.data = new ElemType[InitSize];

2.　 Implementation of basic operation of sequence table  

　　 The basic operation of a linear table refers to its core 、 The most basic operation . Other complex operations can be realized by calling their basic operations . The main operations of the linear table are as follows ： 

(1)　 initialization  

　　 For the sequence table Ｌ Dynamically allocate an array space of predefined size , send data  Point to the base address of this space . Set the current length of the table to ０. 

bool InitList(SqList &L){
// This algorithm is used to initialize the sequence table Ｌ
    L.data = new ElemType[MaxSize];    // Assign a size of... To the sequential table MaxSize The array space of 
    if(!L.data)
        exit(OVERFLOW);                // Storage allocation failed exit 
    l.length = 0;                      // The length of the table is ０
    return true;
}

(2)　 Value  

　　 Take order table Ｌ Of the 1 <= i <= L.length Position element values , And use ｅ return . if ｉ Invalid input for , Then return to false , Indicates that the value failed .

bool GetElem(SqList L, int i, ElemType e){
// This algorithm is used to obtain the sequence table Ｌ pass the civil examinations ｉ The value of the elements 
    if(i <= 1||i >= L.length)                // Judge ｉ Whether the value is reasonable 
        return false;
    e = L.data[i-1];
    return true;
}

(3)　 The insert  

　　 In the sequence table Ｌ Of the  1 <= i <= L.length+1 Place to insert new elements ｅ. if ｉ Invalid input for , Then return to false , Indicates that the insertion failed ; otherwise , Put the first... Of the sequence table ｉ Elements and all elements after them move one position to the right , Make an empty space to insert new elements ｅ, Length of sequence table plus １, Insert the success , return true .

bool ListInsert(SqList &L, int i, ElemType e){
// This algorithm realizes the element ｅ Insert into the sequence table Ｌ pass the civil examinations ｉ A place 
    if(i < 1||i > L.length+1)　　　　　　　　　　　　// Judge ｉ Whether the scope of the 
        return false;
    if(L.length >= MaxSize)                      // Determine whether the maximum range of the array is exceeded 
        return false;
    for(int j = L.length; j >= i; j--)           // take ｉ Elements and subsequent elements are moved back 
        L.data[j] = L.data[j-1];
    L.data[i-1] = e;                             // stay ｉ Insert... At position ｅ
    L.length++;                                  // Linear meter length plus １
    return true;
}

The best situation ： Insert in epitope , The time complexity is O(1).

The worst ： Insert... In the header , The time complexity is O(n).

On average ： Suppose it's on the ｉ The probability of inserting a node at a location , When the length is n When inserting a node into a linear table of , The average number of mobile nodes required is O((1+n)/2)

therefore , The time complexity of linear table insertion algorithm is O(n).

(4)　 Delete operation

　　 The order sheet Ｌ Of the  1 <= i <= L.length Location elements , Return if successful true, And use the deleted element as a reference variable ｅ return , Otherwise return to false . 

bool ListDlelete(SqList &L, int i, ElemType &e){
// This algorithm can delete the order table Ｌ pass the civil examinations ｉ Elements of position 
    if(i < 1||i > L.length)　　　　　　　　　　　　  // Judge ｉ Whether the scope of the 
        return false;
    e = L.data[i-1];                             // Assign the deleted element to ｅ
    for(int j = i; j < L.length; j++)            // Will be the first ｉ The element after one position moves forward 
        L.data[j-1] = L.data[j];
    L.length--;                                  // The length of the linear table minus １
    return true;
}

The best situation ： Delete the footer element , The time complexity is O(1).

The worst ： Delete header element , The time complexity is O(n).

On average ： Suppose you delete the ｉ The probability of a node at a location , When the length is n When a node is deleted from the linear table of , The time complexity required is O(n).

(5)　 According to the value lookup （ In order to find ）

　　 In the sequence table Ｌ Find the value of the first element equal to ｅ The elements of , And return to its order .

int LocateElem(SqList L, ElemType e){
// This algorithm realizes that the median value of the lookup order table is ｅ The elements of , If the search is successful , Returns the element order , Otherwise return to ０
    int i;
    for(i = 0; i<L.length; i++)
        if(e == L.data[i])
            return i+1;                 // Subscript to be ｉ The element value of is equal to ｅ, Returns its bit order ｉ＋１
    return 0;
}

The best situation ： The element to find is in the header , The time complexity is O(1).

The worst ： The element found is at the end of the table , The time complexity is O(n).

On average ： Suppose that the element to be searched is in  1 <= i <= L.length Probability at one location , When the length is n The lookup value in the linear table of is ｅ The average number of element comparisons required (n+1)/2

therefore , The time complexity of the linear table lookup algorithm is O(n).