general discussion
1.1 Basic concepts and terminology
1.1.1 Basic concepts
Computers deal with numerical data, and when computers deal with the data in the user information table, they need to figure out three issues
1. Logical structure of data
What are the intrinsic connections between the data, where one and only one of the data is the first/last node, and the other nodes have one and only one neighboring node located before and after it
2. Data storage structure
The way data is stored in a computer is called a storage structure. In C, it is most common to store the entire user's information table in a structure array, where each structure array element is also a structure for representing a node of the information user. Neighboring nodes in the user's information table, corresponding to elements in the structure array, are also contiguous, and in this type of storage, logically neighboring nodes would have to be physically neighboring, known as thesequential storage, and there are other ways to store it.
3. Operational ensembles of data
The storage of data must involve relevant operations. In the user information table, it is possible to delete a user, add a user, or find a user. The meaning of these operations should be clearly stated. All the operations (or operations) defined for a batch of data constitute a collection of operations (operations).
A data structure is a batch of data composed according to a certain logical structure, using some kind of storage method to store the data in a computer, and defining a collection of operations on this data
1.1.2 Logical structure of data (data structure)
The logical structure of the data is the logical relationship that exists between the data and the data, represented by a binary group
$$
B=(K,R)\K represents the data (a finite set of nodes) and R is a finite set of relations on the set K
$$
For example: five persons, a, b, c, d, e, a is the father of b, b is the father of c, c is the father of d, and d is the father of e. Discussing the paternity between them can be expressed as B=(K, R), where K={a,b,c,d,e},R={r},r={<a,b>,<b,c>,<c,d>. ,<d,e>}.
It can also be represented graphically
ki∈K,Kj∈K，<ki,kj>∈r,kiis kjThe precursor of kjis kiThe successor of the
If a node has no predecessors, it isstarting node; there are no successor nodes, that isend node; the one that is neither the beginning nor the end is the internal node.
linear structure:: A precursor, a successor.
tree structure: one precursor, many successors
graphical structure: multiple precursors, multiple successors
1.1.3 Structure of data storage
The logical structure of the data is independent of the computer, and is not related to the storage in the computer, in order to process the data, it is necessary to store the data, the storage structure of the data there are four main storage methods
(1) Sequential storage
It is common to store data in a linear structure so that logically adjacent nodes must be physically located adjacent to each other
(2) Chained storage
Attach a pointer segment to each node that refers to the successor storage address of that node; a node can have one successor or multiple successors, so there can be one pointer field or multiple pointers, and logically neighboring nodes can be not physically neighboring in the storage area.
(3) Indexed storage
existlinear structureIn this, the start node is index number 1, and the index numbers of other nodes are sequentially added 1. Each node has a unique index number, and the storage address is determined according to the index number.
(4) Hash storage
Construct a function h from a set K to a storage region M with a definition domain of K, a value domain of M, and a storage address consisting of h(K)i) Decision
A data structure is stored in a computer, the storage space occupied by the entire data is not necessarily smaller than the storage space occupied by the data itself, usually the ratio of the storage space occupied by the data itself to the size of the storage space occupied by the entire data structure is called theStorage Density, it is clear that the storage density of data structures is not greater than 1, linear structures have a storage density of 1, and chained structures are less than 1.
1.2 Data Types and Abstract Data Types
1.2.1 Data types
A data type (or type for short) reflects the range of values of data and the operations that can be imposed on such data. A data type is the entirety of the same type of data, a property of the data that defines the range of variability of the data.
1.2.2 Abstract data types
This is a representation-independent datatype, a data model and a set of operations defined in that model. To define an abstract datatype, you must give its name and the names of the operators, and the names of the functions, and specify the nature of the arguments. (Classes in c++ support abstract data types)
The short description is a custom type.
1.3 Algorithm and algorithm analysis
The methods and steps to solve a problem are called algorithms
hallmark
(1) Infinity: the algorithm execution has to take place in a finite number of steps
(2) Determinism: each step is deterministic and non-dualistic
(3) Inputs: can have 0 or more inputs
(4) Output: there must be an output result
(5) Feasibility: each step is feasible
1.3.1 Time complexity and space complexity
An algorithm and its strengths and weaknesses are measured in terms of both the execution time of the algorithm and the storage space used.
(1) Time complexity
Since algorithms execute in different times on different machines, the resource usage is different. So the time complexity is measured using the number of basic operations during the execution of the algorithm, using the large O asymptotic representation (O()), which only relates to the essential differences of the algorithms and does not take into account the minor differences when evaluating the time complexity of the algorithms.
Constant order 31 O(1)
Linear order 2*n+17 O(n)
Square order n^2+10 O(n^2)
Cubic order 2*n^3 O(n^3)
Common algorithmic time complexity
O（1）<O(log n)<O(n)<O(n*log n)<O(n2)<O(n3)<……<O(2^n)
(2) Space complexity
In addition to the storage space attached to the data, the metric is similar to time complexity