~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
Development tools and key technology: data structure
Author: li yu good
Writing time: on May 8, 2020,
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

1. The data, data elements, data items and data types data: all can be input into the computer, a collection of symbols and the processing by a computer, is the floorboard of the object of computer operation,
Data elements: an "individual" in data (collection), the basic unit of data and structure discussed in
Data item: the indivisibility of the smallest unit, a data element may consist of several data items,
Data type: in a programming language, variables of the data types, integer, floating point, character, etc.
2. The data structure, logical structure and storage structure
Logical structure: the relationship between data, collection: the structure of the data elements besides belongs to a type, there is no other relations,
Linear structure: a one-to-one relationship between the data element
A tree structure: a one-to-many relationship between data elements
Figure structure or mesh structure: structure of a many-to-many relationship between data elements are
In data structures, logically can be divided into linear and nonlinear structural physical structure/storage structure: the data in the computer said,
Specific physical structure is to describe the data stored in the memory (such as: order structure, the chain structure, index structure, the hash structure) data structures such as the basic operation of the set of the most important rule is: to realize the application and storage structure of independence, to realize the application is "logic structure, storage is the physical structure, logical structure is mainly for the operation of setting structure, physical structure is to describe the data in the memory of the store (such as: order structure, the chain structure, index structure, a hash structure), etc.,
3. The data type and abstract data types
Data type: in a programming language, variables of the data types, integer, floating point, character abstract data types, such as: a mathematical model, and define a set of operations on the model,
Abstract data types can describe the real world, make it easier for our example: student achievement table is described by using linear table, with a tree or graph to describe the genetic relationship,
Key: the use of its people can only care about its logical features, don't need to know the way to store, to define it also unnecessary care about how to store it,
Example: linear table such abstract data types, its mathematical model is: a collection of data elements, the collection of elements have such relationships: besides the first and the last one, before each element has a unique and the only successor, can have such operation: insert an element, delete an element, such as
4. The representation of abstract data types and implementation
Detailed definition format: ADT abstract data type name {data objects: & lt; The definition of a data object & gt; Data: & lt; The definition of data relations & gt; Basic operation: & lt; The definition of basic operation & gt; } ADT abstract data type name
Algorithm and algorithm analysis:
1, five features: the definition and features of algorithm has poor sex, the certainty, feasibility, input, output algorithm design requirements: correctness, readability, robustness, high efficiency and low storage requirements, (good)
2, the basic standard algorithm that has the performance of evaluation algorithm pseudo procedures, flow charts, N - S structure, etc., e-r diagram is entity relationship model, not application way of description, design algorithm needs to be considered in execution time: choose the size of the algorithm, the scale of the problem
: 3, the time complexity of the algorithm time complexity of the algorithm execution time proportional to the sum of the original operating frequency, time complexity are small to large: O (1), O (logn), O (n), O (nlogn), O (n2), O (n3), the exponential time complexity are small to large O (2 n), O (n!) , O (nn)
4, space complexity space complexity of our algorithm: if only depends on the problem of input data space, and the algorithm has nothing to do, only need to analyze secondary variables except input and application of extra space, (1) a program that don't meet have poor sex, operating system, as long as the whole system is not damaged, it will never stop, even if there is no work need to deal with, it is still in the dynamic waiting, as a result, the operating system is not an algorithm, (2) in the program instructions must be machine executable, and the instruction, no this limit in the algorithm, algorithm represents the solution of the problem, and the program is specific implementation algorithm in computer, (3) if an algorithm in a programming language to describe, it is a program that