Data structures and algorithms —- sequence table

Recently, I began to review and summarize the knowledge of data structures and algorithms, starting from the sequence table of this article.

I. Logical structure and physical structure

1.1 Logical Structure

Logical structures that represent relationships between data elements, such as one-to-one, one-to-many, and many-to-many. Common logical structures include set structure, linear structure, tree structure and graph structure.

Collection structure: There is no specific relationship between elements, as shown below

Linear structure: Elements have a one-to-one relationship, as shown in the figure

Tree structure: Elements have a one-to-many relationship, as shown in the figure

Graph structure: Elements have a many-to-many relationship, as shown in the figure

1.2 Physical Structure

Physical structure, also known as storage structure, describes how data is stored on a disk. It is generally divided into sequential storage, chain storage, index storage, and hash storage. This paper mainly deals with sequential structure and chain structure.

Sequential storage structure: Storage in a contiguous segment of disk space

Advantages: Because the address is continuous, so it can be randomly accessed, easy to search

Disadvantages: It is inefficient to delete or insert data, and the space is determined during initialization. Therefore, it cannot be dynamically expanded

Chain storage structure: Storage on disk is discontinuous

Advantages: When inserting or deleting a node, you only need to change the node pointing, and the node can be dynamically expanded. Theoretically, there is no space limit

Disadvantages: the search needs to traverse, low efficiency, can not be random access

Second, the order table

2.1 Introduction to the Sequence Table

Linear list is a kind of data structure with linear structure, which can be stored by chain storage structure, called linked list; It can also be stored in a sequential storage structure, known as a sequential table. So the sequential list is a kind of data structure with linear logical structure and sequential storage.

2.2 Initialization of the sequence table

First we need to define a data item that represents the order table as follows

#define MAXSIZE 30
typedef int ElemType; // redefine the int type
typedef int Status;

struct SequenceList {
    ElemType *data; // An array of sequential table data
    int length;     // Sequence table length
};
Copy the code

The space of a sequential table is a contiguous space of a fixed size. We can create space during initialization and set length to 0, as shown below

Status ListInit(SqList *L) {
    L->data = malloc(sizeof(ElemType) * MAXSIZE);  // Create a contiguous space of 30 * sizeof(ElemType)
    if(! L->data) {// ERROR is returned when space fails to be opened
        return ERROR;
    }
    L->length = 0; // When initialized, no element is added and the length is 0
    return OK;
}
Copy the code

2.3 Inserting data into a sequence table

Insert data is required to insert the corresponding element in the sequence table with the specified index. Consider the following points:

  • 1. Check whether the sequence table is full. If the sequence table is full, it cannot be inserted
  • 2. If the subscript I is valid, I <0 or I >length is invalid and cannot be inserted
  • 3, linear table insertion, I and the elements after I need to be moved one bit later, and then insert; If I is after the last element, it is inserted without moving back
  • 4, insert elements, add 1 to the linear table length

The specific code is as follows:

Status ListInsert(SqList *L, int i, ElemType data) {
    // We consider the insertion position starting from 0
    if (i < 0 || i > L->length) {
        // If the table is empty, length is 0. If the table starts from 0, it can be inserted. If the table is larger than 0, it cannot be inserted
        // If the table is not empty, take 0, 1, 2, 3 as an example
        // if I =3, insert into position 3
        // if I =4, insert into the end of the table. If I = 5, insert into the end of the table
        return ERROR;
    }
    
    if (L->length >= MAXSIZE) {
        // The table is full and cannot be inserted
        return ERROR;
    }
    
    if (i <= L->length - 1) {
        for (int j = L->length - 1; j >= i; j--) {
            // select * from 'I' to 'I'; select * from 'I' to 'I'
            // Move back one bit to empty the position of I
            L->data[j+1] = L->data[j];
        }
    }
    L->data[i] = data; // Assign to I directly
    L->length++; // Insert data into the table and add 1 to the table
    
    return OK;
}
Copy the code

2.4 Deleting the sequence table

To delete the sequence table, you need to move all the elements after the position to be deleted one bit forward. The following things need to be considered:

  • 1, the table is empty, and length==0, not allowed to delete
  • 2, the same operation, I <0 or I >length input is illegal, cannot be inserted
  • 4. All elements after I move forward one bit
  • 4. The length of the element decreases by 1 after the element moves forward

The deleted code is as follows:

Status ListDelete(SqList *L, int i) {
    if (L->length == 0) {
        // The table is empty and cannot be deleted
        return ERROR;
    }
    if (i < 0 || i >= L->length) {
        return ERROR;
    }
    
    for (int j = i; j < L->length- 1; j++) {
        L->data[j] = L->data[j+1];
    }
    L->length--;  // Delete the sequence table by reducing length by 1. The original data will be overwritten
    return OK;
}
Copy the code

2.5 Modification and Query

The order table modification and query operation is relatively simple, according to the subscript to extract the corresponding element, if it is to find the location of the element with a given value, you need to traverse the order table. The traversal sequence table code is as follows:

// Iterate over the order table
void Traversal(SqList L) {
    if (L.length == 0) {
        return;
    }
    printf("\n");
    for (int i = 0; i < L.length; i++) {
        printf("%d\n",L.data[i]);
    }
    printf("\n");
}
Copy the code

Third, summary

Note: the examples in this article are all implemented with the subscript starting with 0, or can also be used to start with 1, the interested friends can implement themselves.

In the process of learning the sequence table, the author encountered several problems:

  • 1, why do not need to free space order table drop?

Order table space once opened, will not change, just need to change the length can be

  • 2. When inserting or deleting, does it affect the space occupied by the order table?

No impact. The space of the order table does not change, only the length changes. If we insert or delete elements in an array, the count of the array changes, but the size of the array does not.

The above is the author about the order of the list of learning, if there are shortcomings, welcome to correct. This time only summarizes the knowledge of linear lists with sequential structure, and will continue to summarize related knowledge of linked lists in the future.