What is the data structure?
The data structure is a term widely used throughout computer science and technology. It is used to reflect the internal composition of a data, that is, a data consists of those components data, which is constituted, what is the structure. The data structure has logically data structures and physical data structures. The logical data structure reflects the logical relationship between the component data, and the physical data structure reflects the storage arrangement of the component data in the computer. The data structure is in the form of data.
The data structure is an organizational mode of information, and its purpose is to improve the efficiency of the algorithm, which is usually corresponding to a set of algorithms, and the data in the data structure can be performed by this set of algorithms.
2. What is the main study of the data structure?
Data Structure As a large number of logical structures and storage structures of the main research data, and various operations for data. Therefore, there are mainly three aspects: the logical structure of the data; the physical storage structure of the data; the operation (or algorithm) of the data. Typically, the design of the algorithm depends on the logical structure of the data, and the implementation of the algorithm depends on the physical storage structure of the data.
3. What is data? What is the structure? What is a logical structure and physical structure?
Data refers to a collection of elements consisting of limited symbols (such as "0", and "1", with its own structure, operation, and corresponding semantics). The structure is a collection of relationships between elements. In general, a data structure DS can be expressed as a binary group:
DS = (d, s), //i.e., Data-structure = (data-part, logic-structure-part)
Here D is a collection of data elements (or "node", possibly containing "data items" or "data field"), S is a collection of relationships defined on D (or other collections), s = {r | R: D × D × ...}, called the logical structure of the element.
There are four basic types of logical structures: collection structure, linear structure, tree structure, and network structure. Tables and trees are the most commonly used high-efficiency data structures, many efficient algorithms can be designed with these two data structures. Table is a linear structure (full order relationship), tree (predecessor or hierarchical relationship) and chart (WEAK / Local Orders) is a non-linear structure.
The physical structure of the data structure refers to the storage mirroring of the logical structure. The physical structure P of the data structure DS corresponds to a mapping from DS data elements to the storage area M (maintaining logic structure S):
P: (d, s) -> M
Memory Model: A memory m is a series of fixed-size storage units, each unit u, has a unique address A (U), which is continuously encoded. Each unit U has a unique subsequent unit u '= SUCC (U).
P 4 Basic Mapping Models: Sequential, Linked, Indexed, and Hashing mapping.
Therefore, we can at least 4 × 4 possible physical data structures:
Sequential (Sets) Linked Lists Indexed Trees Hash Graphs
(Not all possible combinations reasonable)
4. Action on the Data Structure (DS):
All operations defined on the DS must keep the DS logic and physical structure when changing data elements (nodes) or nodes.
5. Basic operation on the DS:
Any other advanced operations for DS can be implemented with these basic operations. It is best to treat DS and all of his basic operations as a whole - call it module. We can further abstract the module as a data type (where the storage structure of the DS is represented as a private member, the basic operation is represented as a public method), called ADT. As an ADT, stacks, and queues are a special table, they have a subset of the operations of the table. The advanced operation of DATS can be designed (not packaged) algorithm, and the DS is processed by the basic operation.
6. Ok and bad DS:
If a DS can be converted to a linear DS (for example, a linear form) via a "linear rule", it is called a good DS. Good DS usually corresponds to a good (efficient) algorithm. This is determined by the computing power of the computer because the computer can only access logic continuous memory cells, so if there is no linearized structure logically unparalleled. For example, to operate a figure, all nodes to access the graph, you must sequentially access all nodes in some order (to form a prejudice), and must be converted to a linear structure in some way. The graph can be operated.
Tree is a good DS - it has a very simple and efficient linearization rule, so you can use the tree to design a lot of very efficient algorithms. The implementation and use of trees is very simple, but you can solve a large number of special complex problems, so the tree is the most important and most useful data structure in actual programming. The structure of the tree has a recursive properties - each leaf node can be replaced by a sub-tree, and vice versa. In fact, each of the recursive structures can be converted to (or equivalent) tree structure.
