Data Structure University Tutorial The Complete Data Structure Training Course Chapter 1 Data Structure and Its Basic Concept Chapter 1 Data Structure And It's Basic Concepts
1.1 What is the data structure (What is data structure)
If you ask a carpenter: What should you use, he may answer you: "I just have a hammer and a saw." But if you ask an old woodworking or a master's architect, he will tell you "I need some precise tools." Since the problems solved by the computer are abstracting problems in life, their complexity is self-evident, so we need this precise and effective tool to solve complex problems in real life. Algorithms, data structures, programming languages are such a tool. The data structure is an organization mode of information. For the same algorithm, different data structures represent different execution efficiency. This is necessary to study the efficiency differences of various abstract data structures in different data structures, and their applicable occasions.
[1] What is data structure (What is 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, which component data is made, what is the structure, which is constituted. 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 an organizational mode of information, and a good data structure can improve the efficiency of the algorithm, which is usually corresponding to the set of algorithms, and the data in the data structure can be performed in a set of algorithms. From the perspective of discipline, the data structure is a discipline that studies the operational objects of the computer in the programming problem of non-numerical calculations and the relationships and operations between them.
[2] The object of Data Structure Discipline (The Object of Data Structure Research)
As a subject, the data structure, the main research data, the various logical structures and storage structures, and the various operations of the data. Therefore, there are mainly three aspects of content: data logical structure; physical storage structure of data; operations for data (ie, algorithm). 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. The research of data structures not only involves research, such as storage devices and access methods, but also resolves the important foundation of the compilation principle, operating system, database system data element in memory.
1.2 Basic Concepts and Discipline Terms (Basic Concepts and Terminologies)
Data (DATA): is a collection of a collection, indicating the symbol of objective things, in computer science, refers to the symbol of all can be entered into the computer and is processed by the computer. It is a specific symbol representation of the information of the computer processing.
Data Element: It is the basic unit of the data, one "individual" in the data. Also known as "record" or "expression".
Data Item: Inseparable minimum unit of data. The data element is a collection of data items.
Data Object: It is a collection of data elements as the nature, which is a subset of data.
[to sum up]
Data item constitutes data elements, data elements constitute data objects, data object composition data
Data structure: It is a collection of data elements that exist between one or more specific relationships. It consists of three aspects: the logical structure of the data element, the storage structure, and the comparative operation (operation).
The logical relationship between data elements is called the logical structure of the data element, which can be represented by a binary group: DATA_STRUCTURE = (D, S) // Data_Structure = (data-part, logic-structure-part)
Here D is a collection of data elements, and s is a collection of relationships defined on D (or other collections).
S = {r │ r: D × D × ...}.
The logical structure of the data can be attributed to the following four categories:
(1) Collection structure
In addition to the relationship between the data elements in the structure, there is no other relationship.
http://tack.smice.net/docs/images/ds1/jihe.jpg ">
(2) Linear structure
There is a forward subsequent relationship between the data elements in the structure.
http://tack.smice.net/docs/images/ds1/lian.jpg ">>
In this configuration:
Some, there is only one element inadequate elements
Some and have only one element inseparable elements
The rest of any of the elements is only one foregoing and there is only one subsequent element.
(3) Tree structure
There is a relationship between multiple data elements in the structure.
There is a maximum of any one of the nodes, there can be multiple successors, it is a typical nonlinear structure.
http://tack.smice.net/docs/images/ds1/tree.jpg ">>
(4) Figure-like structure (mesh structure)
There is a plurality of relationships between data elements in the structure.
This structure is characterized by any one of the elements, and there may be multiple successes, which is a multi-to-many forward subsequent relationship.
http://tack.smice.net/docs/images/ds1/graphic.jpg ">
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 representation (also known as an image) in the computer is called the storage structure of the data (physical structure)
The physical structure of the data structure refers to the storage image 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) LinkedListSindexedtreeshashinggraphs
It is to be pointed out that not all possible combinations are reasonable.
Action on the Data Structure DS: All operations that define the operation on the DS to change the DS element (node) or node domains must keep the DS logic and physical structure.
Basic operations on the DS: Any other advanced operations for DS can be implemented with these basic operations. It is best to think of DS and all of his basic operations as a whole - called Mode (Model). 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 (ie, the abstract data type Abstract Data Type, refers to a mathematical model and A set of operations defined on the model). ADT is divided into the following three types according to different characteristics of its value:
Atomic Data Type: Variables are non-structural, non-decomposable.
Fixed-aggregate data type: The value is composed of certain structures according to certain structures.
Variable-aggregate data type: The number of ingredients is uncertain
Description method of abstract data type
Abstract data types are available (D, S, P) three-tuple representation
Where D is the data object, S is D is D. The P is the basic operation set of D.
ADT Abstract Data Type Name {Data Object:
Among them, the definition of data objects and data relationships is described by pseudo code, and the definition format of basic operations is
Basic Operator Name (Parameter Table) Initial Condition:
Basic operations There are two parameters: assignment parameters only provide input values for operations; reference parameters are set to & head, except for input values, will also return the results. "Initial Condition" describes the conditions that the data structure and parameters should meet the conditions before the operation execution. If it is not satisfied, the operation failed and returned to the corresponding error information. "Operation Results" illustrates the change in the data structure and the result of returning after the operation is completed. If the initial condition is empty, it will be omitted. It should be noted that the abstract data type needs to be implemented by inherent data types (data types that have been implemented in advanced programming languages).
By the way, Polymorphic Data Type is a data type that is indeterminate of the ingredients of the value, but this is not very common, or can be represented by ADT, so we will discuss it in the future chapter.
Good and bad DS: If a DS can be converted to a linear DS (for example, a linear form) through some "linear rule), it is called it as 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 how to not be linearly structural logically. 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.
