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, namely
A data is composed of those ingredient data, which is constituted in any configuration. The data structure has logically data structure and physical
Data structure. Logical data structure reflects logical relationships between component data, and physical data structures reflect the component data
Storage arrangement inside the computer. The data structure is in the form of data. The data structure is an organization of information, and its purpose is to mention
The efficiency of the high algorithm is usually corresponding to the collection of a set of algorithms, and the data in the data structure can be performed in a set of algorithms.
Work.
What is the main study of data structures?
Data Structure As a large number of logical structures and storage structures of the main research data, and various operations for data. Therefore, the main
There are three aspects of content: data logical structure; physical storage structure of data; operation (or algorithm). Usually, algorithm
Design depends on the logical structure of the data, the implementation of the algorithm depends on the physical storage structure of the data.
What is a data structure? What is a logical structure and physical structure?
Data is an element that consists of a limited symbol (such as "0", "0", "0", "1", with its own structure, operation, and corresponding semantic).
set. 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 domain"), S is defined in D (
Or a collection of relationships on or other collection, s = {r | R: D × D × ...}, called the logical structure of the element. There are four logical structures.
Basic Type: Collection Structure, Linear Structure, Tree Structure and Network Structure. Tables and trees are the most commonly used high-efficiency data structures, many efficient
The algorithm can be implemented with these two data structures. Table is a linear structure (full order relationship), tree (predecessor or hierarchical relationship) and chart (bureau
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 from DS
A mapping of data elements to the storage area m (maintaining logical structure s):
(PD, 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). Four Basics of P
Map: 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)
Operation on the Data Structure DS: All definitions must keep DS when changing the data element (node) or node domain
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 make DS and all of his basic
The operation is considered to be a whole - calling into a module. We can further abstract the module as a data type (where the DS's storage structure is represented.
For private members, basic operations are expressed as public methods), called ADT. As an ADT, stacks and queues are a special table, they
A subset of the operation of the table. For the advanced operation of DATS, it can be designed (not packaged) algorithm, and the DS is performed by the basic operation.
.
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
Good DS. Good DS usually corresponds to a good (efficient) algorithm. This is determined by the computer's computing power because the computer is essentially
Access logic continuous memory cells, so how to not linearize the structure logically. For example, operate a picture,
To access all nodes of the map, you must access all nodes in some order (to form a prejudice), you must pass some way
Conversion of the figure-flexible nonlinear structure into a linear structure to operate.
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. tree
The implementation and use are very simple, but you can solve a large number of special complex issues, so the tree is the most important and most useful number of actual programming.
According to the structure. 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
An recursive structure can be converted to (or equivalent) tree structure.
Abstraction from machine language to advanced languages
We know that the algorithm is defined as an arithmetic sequence. All operations in this arithmetic sequence are defined on a specific type of data model.
And go to a class of specific issues. This arithmetic sequence should have the following four characteristics. Finite, that is, the number of items is limited, and
Each operation can be completed within a limited time; the determinism, that is, each of the sequences has a clear definition, no meaning; no
Enter the operation item, but must have an output operation item; feasibility, that is, the corresponding correct output can be obtained for any given legal input.
. These features can be used to determine whether a determined arithmetic sequence is called a algorithm. However, our current problem is not to be sentenced
Don't be a deterministic sequence of operations, it is a algorithm, but to a computational sequence of algorithms, reviews We have
How to express it with programming language.
The procedure of the algorithm is expressed, and the procedure of the algorithm is the program expression, because each element of the algorithm is clearly expressed
The entire algorithm is not a problem.
As an algorithm for the arithmetic sequence, there are three elements. As data of various operations of various operations in the operation sequence;
Various operations in the column; control transfer in the operation sequence. These three elements are simply referred to as data, operations, and control, respectively. Due to the algorithm
Do not end, change thousands, the object data of the operation acts and the result of the result data is wide, and the enumeration. The simplest and most basic
There is boolean data, character data, integers, and real data, etc.; slightly complex, matrices, records and other data; more complex collection,
Trees and graphs, there are data such as sound, graphics, images. Also because the algorithm is energized, the change is thousands, the types of calculations
Multi-color. The most basic first, etc. have assignment, arithmetic operations, logical operations, and relationships, etc.; slightly complex arithmetic expressions and
Logical expression, etc .; more complex function value calculations, vector operation, matrix operation, collection, and table, stack, queue, tree and map
Operation, etc. In addition, there may be composite and nesting of the above-mentioned operations. About control transfer, relatively simple. In the serial calculation, it
Only several sequential, branches, cycles, recursive and unconditional transfer are all.
Let's review that since the computer has been introduced, the above three elements of the algorithm have been expressed and have experienced a process. The earliest programming language is a machine language, that is, a specific set of specific computers. At that time, all algorithms to run on the computer
Both must be expressed directly to the machine language, the computer can accept it. The calculation sequence of the algorithm includes operational objects and calculation results must be converted to
Instruction sequence. Each of these instructions appear in the form of encoding (instruction code and address code). Algorithm for expression with algorithm language, more than 100,000
Eight thousand miles. For those who are not subject to the process of design, a program is just a "Tianshu", which makes people look at the cloud, readability
Extreme.
The operation, data and control of the algorithm of the machine language are very complicated, because the instructions provided by the machine language are equal, the original.
The machine language only accepts the arithmetic operation, the bit logic operation and the number of comparison comparisons. For a slightly complex operation, you must decompose one by one.
Until the initial et al. To replace it with the corresponding instruction. The data that can directly expresses the most original bit, bytes, and
Three words. Even in the algorithm, even the simplest data such as Boolean, characters, integers, and real numbers, must also map in place, bytes, and words one by one.
In, you have to allocate their storage units one by one. The expression of data in the algorithm is much more troublesome. Control provided by machine language
The transfer instruction also only has conditional transfer, conditional transfer, entry subroutine, and the most basic sects such as returning from subroutines. Use them to construct cycle
Ring, forming branches, calling functions and processes have to do many preparations in advance, have to rely on many techniques. Direct machine language expression algorithm
Many disadvantages.
A large number of complicated trivial details contain programmers to make them more time and effort to engage in creative labor, implementation
They are more important tasks. Ensure the correctness of the program, efficiency. The programmer must be able to control the overall situation of the program.
Details of the country, even if the intelligence super group of programmers often lose their mistakes, so the program reliability
Poor, and the development cycle is long. Due to the machine language design, the thinking and expression of the manner is in the case, only through
The programmers for long-term professional training can be competent, making the programming tall and widowed. Because its written form is all "secret" code, you can read
Sex, not convenient for communication and cooperation. Because it relies hard to detrimentally, the portability is poor, and the reuse is poor. These disadvantages
Computer applications at that time failed to be promoted quickly.
Overall the way the above disadvantage is abstracted in the programming language, allowing it to approach the algorithm language as much as possible. To this end, people first note
It is readability and portability because they are relatively easy to improve by abstraction. So, a assembly language will soon appear. This
Language to the abstraction of the machine language, first manifesting each of the instructions in the machine language: the instruction code generation is remembered, address code
Instead, in the symbolic address, the meaning of its meaning is now displayed and no longer hidden in the encoding, which can let people look "text". Secondly, in this language
If you get rid of the specific computers, you can run on a computer of different instruction sets, as long as the computer is equipped with a assembly language
sequence. This is undoubtedly a step in the machine language faculty language. However, it is too far from the algorithm language, and the procedures cannot be divided.
Data, operations, and controlled to assemble to the compiled instructions are freed out in the complex trivial transactions. In the mid-1950s
, The advanced language of the program design such as Fortran, Algol60, and the later PL / L, PASCAL, etc., the program expression of the algorithm is generated.
A big leap.
It is true that the algorithm ultimately expresses the machine language on the specific computer to run on the computer and get the required results. But
Practice in the language inspired people, expressing into a machine language does not have to be stepped in place, you can walk or can build a bridge over the river. Even the table reaches a mediation language, then turn into a machine language. As a mediation language, the assembly language is not a big success because it is lying in French.
The words are too far. This guides people to design a normative language that is close to the algorithm language, the so-called advanced language, so that the programmer can use
It is convenient to express an algorithm, and then use the "translation" of the specified high-level language to the specified machine language, and finally express the algorithm as a machine language.
. Moreover, since the advanced language and machine language have normative, "translation" is fully mechanized by the computer, just like
The assembly language is translated into a machine language, as long as the computer is equipped with a compiler. The above two steps, the previous step is completed by the programmer.
The next step can be done by the compiler. These two steps are completely independent after the specified clear they do. They respectively
Why do you don't coherence? The previous step is only to correctly express a given algorithm in advanced languages, producing a senior language program;
It is only to translate the advanced language programs obtained by the first step into a machine language program. As for how programmers use advanced language to express algorithms and compile
How to translate the algorithm of advanced language expressed into machine language expressions, obviously not coherent.
The above ideological method for processing the complex process from the algorithm language final table to reach a machine language is an abstraction. Assembly language and high-level language
The appearance of words is such an abstraction example. The huge success of advanced languages compared to assembly language lies in data, operations, and control.
Introducing many concepts and tools of approaching algorithm language in expression, greatly increasing the abstract expression algorithm. In terms of operation, high
Level language such as Pascal, in addition to the four calculations, logical operations, relationship operations, arithmetic expressions, logic of algorithm language
Outside the expression, a powerful function and process tool is also introduced, and the user is customized. The importance of this tool is not only on it streamlined
A complex program text segment, and it reflects the two-level abstraction of the program.
In the function and process call level, people only care about what it can do, don't care about how it does. Just when the function is defined by the function, people
They give the details of how to do. Readers who have used high-level languages know that once the function and the name, parameters and functions are specified clearly,
Then, call them in the program to explain them completely from the heads of the program. You can modify or even replace the function and process, and
Does not affect their called. If the function is seen with the process name as an operation name, regard the parameters as the result of the operation, then
, The reference to the function and the process of the process is not quoted. Use functions and processes and their composite or nested can be naturally
Any complicated operation in the algorithm language.
In terms of data, advanced languages such as Pascal attracted the concept of data types, that is, categorize all data. Every data (package
Including expression) or each data variable belongs to a class. This type of data is called a data type. Therefore, the data type is
The instructions of the data or data variable class indicate all values that may take on the data or data variable. For unable structure, advanced language
Such as Pascal, in addition to providing standard basic data types - Boolean, characters, integer, and except, providing users can customizable enumeration classes
, Sub-boundary type and pointer type. These types (except for pointers), their usage methods comply with the habits used in the algorithm language. for
Structured data, advanced language such as Pascal, providing four standard data types such as arrays, records, restrictions, and files, etc.
. Among them, the array is the vector, matrix abstraction in scientific calculations; records are abstractions of records in business and management; there is a collection of mathematics
Abstraction of the potential set of sufficiently small sets; files are abstractions such as external storage data such as disk.
It is possible to construct a structural data using the basic data types provided (including standard and custom), constructor, comparable, restricted, and file constructors. In addition, users are allowed to utilize standard structural data types, and more than composite or nested constructs.
Structured data of a hetero-higher layer. This makes the data type in the advanced language in a significant hierarchy. The stratification of data types in advanced languages is not
Poor exhaust, thus use them to express data in any complex level in the algorithm language. In terms of control, advanced languages such as Pascal provide
The expression algorithm controls six ways.
(1) Default order control ";".
(2) Condition (branch) control: "IF expression (true) THEN S1 ELSE S2;".
(3) Select (case) control:
"CASE expression of
Value 1: S1 value 2: S2 ... Value N: SN End "
(4) loop control:
"While Expression (true) Do S;" or "Repeat S Until Expression (true);" or "for variable name: = initial value to / DOWNTO final value DO S;"
(5) Call of functions and processes, including recursive functions and recursive processes.
(6) unconditional transfer goto. These six expression methods not only cover all controls in the algorithm language, but it is no longer like machine language or assembly language.
At the beginning, it was cumbersome, as concealed, but as seen above, the expression of natural language was different. Programming language slave
The abstraction of advanced languages, the main benefits are: advanced language approach the algorithm language, easy to learn, easy to master, general engineering technicians
As long as we can take a few weeks of training, you can work for programmers; advanced languages provide programmers with structural programming environment and tools,
Make the design of the program is well-readable, maintainable, high reliability; advanced language is remote from the machine language, with specific computer hardware
Not large, thus the procedure written can be portable, and the reuse rate is high; because the complicated trivial affairs are handed over to the compiler,
High automation, the development cycle is short, and the pre-sequence will be free, you can concentrate time and energy to engage in them more important for them.
Creative labor to improve, the quality of the program.
Data structure, data type and abstract data type
Data structure, data types, and abstract data types, these three terms are different from differently similar, reflecting their meaning
The difference is related.
The data structure is a term widely used throughout computer science and technology. It is used to reflect the internal composition of a data, namely
What is the component data consisting of a data, what is the structure. The data structure has logically data structure and physical
Data structure. Logical data structure reflects logical relationships between component data, and physical data structures reflect the component data in calculation.
Storage arrangement in the machine. The data structure is in the form of data.
The data is classified according to the data structure, and the data with the same data structure is the same. All the same type of data is called a data class
type. In the program design advanced language, the data type is used to illustrate the property in the data classification. It is an attribute of data. This
The attribute limits the range of variations of the data. In order to solve the problem, according to the type of the data structure, the advanced language defines a series of data.
Types of. Data types defined by different advanced languages are not the same. The type of data type defined by the Pascal language.
Among them, the simple data type corresponds to a simple data structure; the construction data type corresponds to a complex data structure; in a complex data structure
In that, the component data is allowed to have a complex data structure, and thus the configuration data type allows the composite nested; the pointer type corresponds to the data
The relationship between the constituent component data, the simple data type of the surface, actually points to the complex ingredient data, the data in the data type, so it does not spread it into the simple data type, and has not been placed into the construction data type. And separately draw a class.
The data structure reflects the configuration of the data inside, which often uses a structural diagram: each component data in the data is considered as one
A node, and use a square box or circle, and the relationship between the component data is represented by a connection between the respective nodes. If the ingredient data
It has its own structure, and the structure is nest. The nested nested here also allows recursive nested.
Due to the introduction of pointer data, it is possible to construct a variety of complex data structures. The relationship between the components in the data structure,
The data structure is linear and nonlinear. There are also hierarchical and mesh in nonlinear data structures. Since the data type is based on the data
Structure, therefore, a class of data structures correspond to a data type. The data type is also available in the structure present in this type.
Sex and nonlinearity, levels and mesh. A data variable, type description of the type in advanced language must be the data of the read variable
The data type corresponding to the structure. The most commonly used data structure is an array structure and a recording structure. The array structure is:
The number of components data is fixed, and the logical relationship between them is reflected by the sequence number of the ingredient data (or the subscript of the array). These components
It is arranged in the order of the serial number. Each ingredient data has the same structure (which can be a simple structure,
To be a complex structure), it belongs to the same data type (correspondingly a simple data type or constructive data type). This same data class
The type is called a base type. All ingredient data is arranged in a continuous storage unit sequentially. In summary, the array structure is a linear
Uniform, its ingredient data can be randomly accessed.
Because of this, the structure has these good characteristics, so it is most often used. In the advanced language, correspond to the array structure,
The data type is an array type, that is, the data variable of the array structure must be described as array [i] of t0, where i is an array, the subscript of the structure.
Type, and T0 is the base type of array structure. The recording structure is another commonly used data structure. Its features are: like array structures,
The number of points of data is fixed. However, there is no natural sequence between ingredient data, and they are in equal position. Each component data is referred to as a domain and assigns
Gamename. Different domains have different domain names. Different domains allow different structures, thus allowing different data types. Niece
Like the same, they can be randomly accessed, but the route of access is domain name. The data type corresponding to the record structure in the advanced language is the record class.
type. The variable of the data of the record structure must be described as the type of record.
The meaning of abstract data type has been specifically described in the previous paragraph. It can be understood as further abstraction of data types. That is, the data type and
The calculation on the data type is bundled together and packaged. The purpose of introducing abstract data types is to operate the representation and data type of data type.
The implementation is separated from these data types and calculations in the program to make them independent of each other. For the description of the abstract data type, except
It is necessary to describe its data structure, and must also describe the calculation (process or function) defined above it. Process and letters defined on abstract data types
The data structure of the data of this abstract data type should have.
Panmeter design and data structure and algorithm
Below I want to talk about the latest promotion of generic programming models for data structures and algorithms, generic thinking has putted data
The basic idea of the structure and algorithm is abstract to an unprecedented height, and now there is a variety of programming language to support generic design, such as
ADA, C , and it is said to fully support generic design in Java's next version and C #.
Let's talk about the basic ideas of generic design: generic programming, below the following direct GP strategy) is a new
Program design ideas, and OO, OB, PO These are known to those skilled in the program, and the GP abstract degree is higher. The coupling of the assembly based on the GP design is not inherited, so the intertency between the components And extension is very high. We all know that any algorithm is
Using a specific data structure, the easiest example is the rapid sorting algorithm is the most fundamental implementation condition is the object being sorted.
Store in an array, because rapid sorting is because of the random storage characteristics of the array, you can exchange long-distance pairs within unit time.
Icon, not just the two objects, and if you use a joint table to store the object, because the time to get the object in the couplet is both both the linear O [N]
This will make the rapid sorting to lose its fast feature. In other words, when we design a algorithm, we always consider it.
The data structure, such as array lookup, lapsery, tree lookup, diagram finding its core is looking for, but because the data structure of the role is different
There will be a variety of different expressions. This close relationship between data structures and algorithms has always been our previous understanding. Foundation of generic design
Thought is to separate the data structure of the algorithm and its role, that is, we don't think about our design algorithm when we design the algorithm.
What data structures will be actued. The ideal status of generic design is a lookup algorithm to act on arrays, links, trees, and maps.
Above the data structure, becomes a universal, generic algorithm. Is this ideal that is very tempting?
The generic programming is that unprecedented elasticity and abstraction, GP and OO are different, it does not require you through extra
Indirect layer to call function: it allows you to write completely and reused algorithms, its efficiency is designed for specific data structures.
Flag is quite. We all know that the data structure can be represented by a user-defined type in C , and the template technology in C is class
As a parameter, then I can imagine that using template technology can realize our GP idea, that is, a template function can be transmitted
The type of hand is played, and these types can be all of our definitions.
The generic algorithm is extracted from a specific type and a specific data structure, making it adapting to the usual type of general as possible, the algorithm itself is only for
The logical essence of the integration of the algorithm is not interfered with the implementation details of various data structures. This means a generic algorithm
There are two parts. 1. Use to describe the actual instructions of the algorithm nature logic; 2. Correctly specify a set of nature of its parameter types must meet
Condition. At this point, I believe that many people have begun to be confused, huh, don't matter. After all, GP is a very high-abstract programming idea.
Thought, the core inside is the abstract condition becoming the core of the programming process, which replaces the type of the core in Oo,
It is because the type is not the focus of our consideration, and the type has become a coat of abstract conditions, so we call such procedures for generic thinking.
I want to ------ generalize the type.
Personal learning experience
As for how to learn the data structure, I personally think the right way is that I will first recognize the nature, data of the data structure.
Close relationship between structure and algorithms, and application methods of data structures. Otherwise, we are likely to fall into the complex characteristics of various data structures.
But I still don't know what is the essence of the data structure. I have learned a lot for a lot of time, but I didn't understand anything. Here I said to me.
Personal point about the nature of the data structure:
The most important thing to learn the data structure is the understanding of the programming method and program language concept and implementation INT i;
INT i []; struct i {}; adt i {};
What is the difference in the way, this is the problem of programming language implementation.
Defining a data type is to define a class of operation INT I, J; i = J 1;
Such an operation is implemented in the language itself, that is, you don't need to care about how such an operational program is completed, so
INT is the basic data type
Abstract basic data types are data structures.
When you define
ADT P {};
When you are, if P is a list, you want you to achieve a variety of operations. And all the operations that P can be completed must be
Realization, and you implement the foundation is these CHAR INT FLOAT * P ... basic data types. This is the abstract data type.
When you complete the type definition, the rest is the algorithm to complete the control of the program process.
So: Data Structure Algorithm = Program
Also want to say, design ideas, programming language, and data structures, always facilitate the development of computer software science development.
. Generally speaking, it is a language that supports this kind of thinking and the type of data that contains such thoughts.
Specifically:
Machine programming machine language, assembly language
Process programming C. . . . Language
Object-oriented programming JAVA C
Of course, the idea is just a thought, you can do it in different languages. However, it must be explained that only the language on one level can be implemented.
For example, the machine language, due to its low abstraction, low arrival, is like an operation to assign a value to an object, it is also necessary to operate.
. It does not support this level in the language. Why can't I enter the object-oriented programming? The key is good in C
ADT. He can use complex ADT to replace C C has become a class of basic data types, but it is because of completing OO to complete OO,
The programmer is required to implement (define the ADT). Therefore, C is not suitable for developing OO software. However, C just defines CLASS to a basic type.
This completes the abstraction of the hierarchy of OO. Of course, because C is a super-collection of C, he is also fully supported.
So much, that is, I want to talk about the relationship between data structure and program language and design ideas. When we can learn and learn the data structure
When the order design language, the program design idea is linked, I think we have a more profound understanding of the data structure itself.
We are no longer panic when we learned to every new data structure, because we know that any data structure has its common commonality and
Special features, each data structure is reality in a field. From this aspect, the data structure itself has inheritance.
Sex, we can use a inherited tree to represent a complete data structure system, and each data structure is a child in the inheritance system.
node.
Finally, here I recommend several books that I feel more excellent in data structures:
"Data Structure and Algorithm ------ Object-Oriented C Design Mode" Electronic Industry Press Publishing. On Amazon is a five-star evaluation,
Personally think that its overall description of the data structure is very good.
"Algorithm IN C I-V" is the work of RS "Algorithm In C" C version, completely describing various algorithms,
Amazon's five-star evaluation, Higher Education Press has its own photocopy.
"Data Structure In C with STL" uses the C standard template library to describe the data structure, which is a method using generic design.
A comprehensive textbook that describes the data structure. Tsinghua published the Chinese version, but there is a copy version.
