Data structure and algorithm
(1) What is the data structure data structure to reflect the internal configuration of a data, and 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.
What is the main study of data structures? The data structure is a variety of logical structures and storage structures for the main research data, and various operations (or algorithms) for data.
What is the data 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. Generally, a data structure DS can be represented as a binary group: DS = (D, S), // IE, Data-Structure = (Data-Part, Logic-structure-part) D is a collection of data elements (Or "Node", may also contain "data item" 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: a collection structure, linear structure, and tree structure 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 of data elements from the DS to the storage area M (maintaining a logical structure S): PD, S) -> M memory model: A memory M is a series of fixed-size storage The unit, 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 get at least 4 × 4 possible physical data structures: SEQUENTIAL (SETS) Linked Lists Indexed Trees Hash Graphs
(Not all possible combinations reasonable) Action on Data Structure DS: All Decimal Operations must keep DS logic and physical structures when changing data elements (nodes) or nodes. Basic operations 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.
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. 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. We know that the algorithm is defined as an arithmetic sequence. All operations in this computing sequence are defined on a specific type of data model and to solve a specific problem. This arithmetic sequence should have the following four characteristics. Finite, that is, the number of items is limited, and each of the calculations can be completed within a limited time; the determinism, that is, each of the sequences has a clear definition, no means; no input However, it must have an output computing 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 discriminate whether a determined arithmetic sequence is called an algorithm, but to be called an algorithm for algorithms, reviewing we used to express it in programming languages.
The procedure of the algorithm is expressed, and the procedure of the algorithm is the procedure of the algorithm, 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 calculation sequence; various calculations in the calculation sequence; the control transfer in the calculation sequence. These three elements are simply referred to as data, operations, and control, respectively. Since the algorithm is energized, it changes thousand, and the object data acts in which the operation acts, the result data has a wide range of data, and it is not amended. The simplest, most basic, Boolean data, character data, integers, and real data, etc., slightly complex, matrix, record and other data; more complex collection, trees, and maps, there are sounds, graphics, images and other data. . Also because the algorithm is endless, the change is thousands, the types of calculations are varied, colorful. The most basic initial et al. Has assignment operations, arithmetic operations, logical operations and relationships, etc. In addition, there may be composite and nested in the above-mentioned operations. About control transfer, relatively simple. In serial calculations, it only has several sequential, branch, loop, recursive and unconditional transfer.
(1) Default order control ";". (2) Condition (branch) control: "IF expression (true) THEN S1 ELSE S2;". (3) Select (case): "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) The call, including recursive functions, and recursive processes. (6) unconditional transfer goto.
