Is a linear linked list a linked storage structure of a linear list?

According to the complexity of the relationship between each data element in the data structure, data structures are generally divided into two major types: linear structures and non-linear structures.

Linear linked list, as the name suggests, is similar to a chain list. The opposite of linear linked list is linear sequence list. Both The difference is that a linear sequence table needs to open a continuous area in the memory, so the state of the stored data in the memory is continuous, while the storage of the linear linked list in the memory is random, and the connection between the data relies on pointer. (Recommended learning: web front-end video tutorial)

If a non-empty data structure meets the following two conditions:

①There is and only one root node Point;

②Each node has at most one antecedent and at most one consequent. The data structure is called a linear structure, also known as a linear table. Therefore, linear lists, stacks and queues, and linear linked lists are all linear structures, while binary trees are nonlinear structures.

A linear table with a linked storage structure, which uses a set of storage units with arbitrary addresses to store data elements in the linear table. Logically adjacent elements are not required to be physically adjacent and cannot be accessed randomly. . Generally described by nodes: node (representing data elements) = data domain (image of data elements) pointer domain (indicating the storage location of subsequent elements)

In the chain storage structure, the storage of the data structure The space may be discontinuous, and the storage order of each data node may be inconsistent with the logical relationship between data elements, while the logical relationship between data elements is determined by the pointer field. The chain storage method can be used to represent both linear structures and nonlinear structures.

Generally speaking, in the linked storage structure of a linear list, the storage symbols of each data node are discontinuous, and the positional relationship and logical relationship of each node in the storage space are also inconsistent. For a linear linked list, you can start from the head pointer and scan along the pointers of each node to all nodes in the linked list.

Building a linear linked list is a process of dynamically generating link points and linking them to the linked list in turn. Let the pointer of the first link point of the linear linked list be list.

When the first link point is generated, the linked list is empty, just send the link point to the list directly. Every time a data element is obtained, a link point is generated for the data element. While the data information of the obtained data element is sent to the data field of the new node, the pointer field of the new node is set to NULL, and then the new node is The node is inserted at the end of the linked list.

The following algorithm reads strings line by line from a file named data.txt as data elements of a linear linked list. The algorithm is as follows:

LinkList creatList() {
    LinkList r, p, list = NULL;
    char data[ 100 ];
 
    FILE *f = fopen( "data.txt", "rb" );
    while( fgets( data, 100, f ) )
    {
        p = ( LinkList )malloc( sizeof( LNode ) );
        if( p != NULL ){
            strcpy( p->data, data );
            p->link = NULL;
 
            if( list == NULL )
                list = p;
            else
                r->link = p;
            r = p;
        }
    }
    fclose( f );
 
    return list;
}

The above is the detailed content of Is a linear linked list a linked storage structure of a linear list?. For more information, please follow other related articles on the PHP Chinese website!