Data-data
The data is the carrier of information. It can be processed by computer identification, storage, and processing, is "raw materials" processing of computer program processing. With the expansion of the computer application, the scope of data includes: integer, real, string, image, and sound, etc. Data Element-data elements
The data element is the basic unit of the data. Data elements are also known as elements, nodes, vertices, records. A data element can be composed of several data items (also known as fields, domain, attributes). Data items are minimum identification units with independent meaning. Data structure-data structure
The data structure refers to the interrelationship between data, that is, the organizational form of data.
Logical structure-data logical structure
Storage structure-data storage structure
Data Operation - Operation of Data
Immediate predecessor - directly
Nodes in the table, adjacent to it and in front of it
Immediate Successor - Directly
Adjacent to any junction in the table and after its subsequent point
Sequential Storage Structure - Sequence Storage Structure
Store logically adjacent nodes in the physical location in the physical location, the logical relationship between the node is reflected by the neighboring relationship of the memory cell. Usually described by means of an array of program languages.
LINKED Storage Structure - Link Storage Structure
No logical adjacent nodes are also adjacent to the physical location, and the logical relationship between nodes is represented by the additional pointer field. Usually descriptions are described by means of a program language.
Dense index - dense index
The additional index table is usually established while the node information is stored. The index table consists of several index items. If each node has an index item in the index table.
Spare index-sparse index
The additional index table is usually established while the node information is stored. The index table consists of several index items. If a set of nodes can only correspond to one index item in the index table.
1. The data structure generally includes the following three aspects:
1 logical relationship between data elements, also known as the logical structure; the logical structure of the data is to describe data from the logical relationship, and is independent of the computer. The logical structure of the data can be regarded as a mathematical model from a specific problem abstraction.
2 Data elements and their relationships in the computer memory, called the storage structure; the storage structure of the data is the implementation of the logical structure computer language (also known as an image), which depends on the computer language. For machine language, the storage structure is specific. Typically, the storage structure is discussed only at the level of the advanced language.
3 The operation of the data, that is, the operation applied to the data. The operation of data is defined on the logical structure of the data, and each logical structure has a collection of operations. The most commonly used retrieval, insertion, deletion, update, sorting is actually just a series of abstract operations applied on abstract data. The so-called abstract operation means that we only know that these operations are "what", without considering "how to do". These calculations are considered only after the storage structure is determined.
In order to increase the sensibility of the data structure, the concept of the data structure is explained below. [Example 1.1] Student transcript, see the table below. Note: In the table, the concept (1) of the data element, data item, start node, and terminal nodes (1) The logical structure table is a data element (or record, node), which is named, name, Data items such as performance and average score. The logical relationship between the data elements in the table is: only one of the nodes in the table, adjacent to it and its previous nodes (IMMEDIATE Predecessor directly) only one; adjacent to any junction in the table And in its subsequent nodes (Immediate Successor directly) only one. There is only the first node in the table that is not straightforward. The end node is called a terminal. For example, the direct front trend and direct successive nodes of "Mark" in the table are the nodes of "Ding Yi" and "Zhang San". The relationship between the above nodes constitutes this student score. The logical structure of the table. (2) Storage structure The storage structure of the table refers to this relationship between the computer language, that is, the nodes in the table are in the order, and in a continuous unit, or use a pointer to Node link together? (3) The operation of the data is in the student transcript of the above, it may always look at a score of a student; when the student is eating out of school; to delete the corresponding node; enter the new student to increase the node. How to find, delete, insert, this is the operational problem of data. I figured out the above three issues, and I figure out the data structure of the student transcript. 2. The logical structure of the data is classified without confusion, and the logical structure of the data is often referred to as the data structure. There are two major categories: (1) logical features of linear structure linear structure: if the structure is non-empty set, there is only one start node and a terminal node, and all nodes have only one Directly and a direct successor. Linear table is a typical linear structure. Stack, queue, string are both linear structure.
(2) Nonlinear structural nonlinear structures are: a node may have multiple direct and direct successive. The data structures such as arrays, generalized forms, trees and maps are non-linear structures.
3. The storage structure of the four basic storage method data of the data can be obtained by following four basic storage methods: (1) Sequential storage method This method stores logically adjacent nodes in the physical location adjacent storage unit, node The logical relationship is reflected by the neighboring relationship of the storage unit. The resulting store representation is called a sequential storage structure, typically description by array of program languages. This method is primarily applied to a linear data structure. Nonlinear data structures can also be stored in a certain linearization method.
(2) Link storage method This method does not require logically adjacent nodes in the physical location, and the logical relationship between nodes is represented by an additional pointer field. The resulting store is referred to as a chain storage structure, typically description by means of a programs.
(3) Index storage method This method usually establishes an additional index table while saving node information. The index table consists of several index items. If each node has an index item in the index table, the index table is called a dense index. If a set of nodes correspond to only one index item in the index table, the index table is called a spars index. The general form of the index is: (keyword, address) keyword is the only data item that can uniquely identify a node. The address indication of the address indication of the dedicated index neutralization node; the address of the sparse index neutral index indicates the start storage location of a set of nodes. (4) The basic idea of this method is that the storage address of the node is directly calculated according to the keywords of the node.
Four basic storage methods may be used singly or in combination. Different storage structures can be obtained by different storage methods. Which storage structure is selected to indicate the corresponding logical structure, depending on the specific requirements, mainly considering the convenience of operation and the time and space requirements of the algorithm.
4. The logical structure of the three aspects of the data structure, the data storage structure, and the data of the data of the data is a whole. Isolate an aspect without paying attention to the connection between them. The storage structure is an indispensable data structure: the different storage structures of the same logical structure can be identified by different data structural names. [Example] Linear European is a logical structure. If the storage representation of the sequential method, it can be called a sequence table; if a chain storage method is used, it can be called a linked list; if the hash storage method, it can be called For a lague table. The operation of the data is also an aspect of the data structure inseparable. After a given logical structure and storage structure, the characterization of the calculation and its operations may also result in a completely different data structure according to the defined calculation set and its operation. [Example] If the insertion of the linear table is limited to one end of the table, the linear representation is stack; if the insert limit is limited to one end of the table, the deletion is limited to the other end of the table. This linear representation is a queue. Further, if the linear table uses a sequence table or a linked list as a storage structure, after the insertion and deletion operations are described above, the order stack or chain stack, sequential queue or chain queue can be obtained separately. Data Type The so-called data type is a collection of values and a general name of a set of operations defined on these values. The usual data type can be considered as the data structure that has been implemented in the programming language. [Example 1.2] "Integer Type" in the C language defines a range of integer values (whose maximum int-max is dependent on the specific machine) and the addition, minus, multiplication, division of the integer. Wave operation. Press "Value" to decompose, you can divide the data type into two categories: 1 Atomic type: its value is not decomposed. It is usually provided directly by the language. [Example] Simple export type of standard type and character type and other standard types and pointers; 2 Structural types: It can be broken down into several components (or component). It is user defined by the user by means of the language provided by the language, which is usually derived from a standard type, so it is also an export type. [Example] Ar groups, structures, etc. of C. Abstract Data Type (ABSTRACT TYPE ADT) ADT refers to an organization of abstract data and related operations. It can be seen as the logical structure of the data and its operations defined on the logical structure. An ADT can be described as: ADT ADT-NAME {data: // Description of the logical relationship between data elements Operations: // Operating Instructions Operation1: // Operation 1, it usually uses C or C function prototypes Description INPUT: Description of the input data preconDitions: Perform the status // of the system before this action // can be seen as the initial condition process: Operation of the data Output: Instructions for returning data Postconditions: Perform the status of the system after this operation / / "System" can be seen as a data structure Operation2: // operation 2 ...} // ADT abstract data type can be seen as a model that describes the problem, which is independent of the specific implementation. It has the advantage that the data and operation are packaged together, so that the user program can only access the data in some operations defined in the ADT, thereby implementing information hide. In C , we can use the description of the class (including template class) to represent the ADT, use the implementation of the class to implement ADT [see [10]]. Therefore, the classes implemented in C correspond to the storage structure of the data and its operations for data implemented on the storage structure.
