1, Introduction to linear table

2, Linear table abstract data type definition

III. sequential storage structure

The sequential storage structure of linear table refers to the sequential storage of data elements of linear table with a section of storage units with continuous addresses.

1. Address calculation method

The linear tables (a1,a2,..., an) are stored in the following order:

Assuming that ElemType occupies c storage units (bytes), the relationship between the storage location of the I + 1st data element and the i-th data element in the linear table is (LOC represents the function to obtain the storage location): LOC(ai+1) = LOC(ai) + c

Therefore, the storage location of the ith data element ai can be calculated from a1: LOC(ai) = LOC(a1) + (i-1)*c

Understand in combination with the following figure:

Through this formula, we can calculate the address of any position in the linear table at any time, whether it is the first or the last, at the same time. Of course, its storage time performance is 0 (1), which is usually called random storage structure.

2. Get element operation

To get the ith element in the linear table L, we only need to return the value of the i-1 subscript of the array.

// Status is the type of function, and its value is the status code of the function result. For example, returning 1 means OK,
//        Return 0 for ERROR.
// Initial condition: sequential linear table l already exists, 1 < = I < = listlength (L)
// Operation result: use e to return the value of the ith data element in L.

Status GetElem(SqList L, int i, ElemType *e)
{
    if( L.length==0 || i<1 || i>L.length )
    {
        return ERROR;
    }
    *e = L.data[i-1];

    return OK;
}

3. Insert operation

Specific ideas for insertion:

– throw an exception if the insertion position is unreasonable;

– if the length of the linear table is greater than or equal to the length of the array, throw an exception or dynamically increase the capacity of the array;

– traverse forward from the last element to the ith position, and move them back one position respectively;

– fill the element to be inserted into position i;

– linear meter length + 1.

Specific code implementation;

/* Initial condition: sequential linear table l already exists, 1 < = I < = listlength (L). */
/* Operation result: insert a new data element e before the ith position in L, l length + 1.*/

Status ListInsert(SqList *L, int i, ElemType e)
{
    int k;

    if( L->length == MAXSIZE )  // The sequential linear table is full
    {
        return ERROR;
    }
    if( i<1 || i>L->length+1)   // When i is out of range
    {
        return ERROR;
    }
    if( i <= L->length )   // If the inserted data position is not at the end of the table
    {
        /* Move the data element back one bit after the position to be inserted */
        for( k=L->length-1; k >= i-1; k-- )
        {
            L->data[k+1] = L->data[k];
        }
    }

    L->data[i-1] = e;  // Insert new element
    L->length++;

    return OK;
}

4. Delete operation

Specific ideas for deletion:

– throw an exception if the insertion position is unreasonable;

– remove and delete elements;

– traverse from the position of the deleted element to the position of the last element, and move them forward one position respectively;

– gauge length + 1;

Specific code implementation

/* Initial condition: sequential linear table l already exists, 1 < = I < = listlength (L) */
/* Operation result: delete the ith data element of L and return its value with e. the length of L is - 1 */

Status ListDelete(SqList *L, int i, ElemType *e)
{
    int k;

    if( L->length == 0 )
    {
        return ERROR;
    }
    if( i<1 || i>L->length )
    {
        return ERROR;
    }

    *e = L->data[i-1];

    if( i < L->length )
    {
        for( k=i; k < L->length; k++ )
        {
            L->data[k-1] = L->data[k];
        }
    }

    L->length--;

    return OK;
}

4, Advantages and disadvantages of linear table sequential storage structure

In the sequential storage structure of linear table, the time complexity is O(1) no matter where it is when storing and reading data. When inserting or deleting, the time complexity is O(n). This shows that it is more suitable for applications where the number of elements is relatively stable, elements are not often inserted and deleted, and more operations are data access.

advantage:

– there is no need to add additional storage space to represent the logical relationship between elements in the table.

– you can quickly access elements anywhere in the table.

Disadvantages:

– insert and delete operations require moving a large number of elements.

– when the length of the linear table changes greatly, it is difficult to determine the capacity of the storage space.

– easy to cause "fragmentation" of storage space