The storage structure of data can be obtained through the following four basic storage methods:
1、 Sequential storage method
This method stores logically adjacent nodes in physically adjacent storage units, and the logical relationship between nodes is reflected by the adjacency relationship of the storage units< Br/>
The resulting storage representation is called a Sequential Storage Structure, typically described using arrays in programming languages< Br/>
This method is mainly applied to linear data structures. Nonlinear data structures can also be sequentially stored through some linearization method< Br/>
2、 Link storage method
This method does not require logically adjacent nodes to be physically adjacent, and the logical relationships between nodes are represented by additional pointer fields. The resulting storage representation is called a Linked Storage Structure, which is typically described using pointer types in programming languages< Br/>
3、 Index storage method
This method typically establishes additional index tables while storing node information. The index table consists of several index entries. If each node has an index entry in the index table, the index table is called a DenseIndex. If a set of nodes corresponds to only one index entry in an index table, the index table is called a SpareIndex. The general form of index entries is:
(Keywords, Address)
Keywords are data items that can uniquely identify a node. The address of the index entry in a dense index indicates the storage location of the node; The address of an index entry in a sparse index indicates the starting storage location of a set of nodes< Br/>
4、 Hash storage method
The basic idea of this method is to directly calculate the storage address of a node based on its keywords< Br/>
Four basic storage methods can be used alone or combined to store and image data structures< Br/>
Using different storage methods for the same logical structure can result in different storage structures. The choice of storage structure to represent the corresponding logical structure depends on specific requirements, mainly considering the convenience of computation and the spatiotemporal requirements of the algorithm< Br/>
The relationship between the three aspects of data structure
The logical structure of data, the storage structure of data, and the operation of data are three aspects that form a whole. It is not advisable to understand one aspect in isolation without paying attention to the connections between them. Storage structure is an indispensable aspect of data structure: different storage structures of the same logical structure can be identified by different data structure names< Br/>
A linear table is a logical structure, and if a storage representation using sequential methods is used, it can be called a sequential table; If the chain storage method is used, it can be called a linked list; If a hash storage method is used, it can be called a hash table< Br/>
The operation of data is also an inseparable aspect of data structure. After giving the logical and storage structure of the data, the defined set of operations and their properties may also lead to completely different data structures< Br/>
If the insertion and deletion operations on a linear table are limited to one end of the table, the linear table is called a stack; If insertion is restricted to one end of the table and deletion is restricted to the other end of the table, the linear table is called a queue. Furthermore, if a linear table uses a sequential or linked list as its storage structure, after the above limitations on insertion and deletion operations, sequential or chain stacks, as well as sequential or chain queues, can be obtained respectively.