A data structure
1, concept: data structure refers to the mutual relationship between one or more specific set of data elements, it mainly describes the way of storing and organizing data by computer, the data structure is divided into logical structure, physical structure (storage) and the data of the operation of three parts,
2, the famous Swiss computer scientists nicolas Wirth (. Niklaus Wirth) put forward "algorithm=data structure + program" point of view, and points out the importance of data structure, and is able to skillfully selection and design of various data structures and algorithms of a business logic is the difference between programmers level of an important symbol, therefore, is the purpose of learning data structure can make the students to write faster, more efficient procedures,
3, the logical structure of data structure includes the following four kinds of structure:
(1) linear structure: one-on-one linear relationship exists between the data elements; In addition to the first and last data element, the rest of the each data element is only a precursor and a subsequent data elements,
(2) tree structure: the level of the one-to-many relationship exists between the data elements. In addition to the root node, the rest of the each data element is only a precursor data elements, as well as zero or a number of subsequent data elements,
(3) graph (network) structure: data elements exist between arbitrary many-to-many relationship; Each data element can have zero or several precursor data elements and zero or several subsequent data elements,
(4) sets: between data elements in addition to "belongs to a collection of" relationship, there is no other relations,
(storage) 4, the data structure is physical structure refers to the logical structure of data stored in the computer form, it divided into
(1) sequential storage structure: the data elements in the sequence is stored in a storage addresses a set of continuous storage unit, its logical relation between the data elements and physical relationship is consistent,
(2) chain storage structure: the data element is stored in any storage unit, its memory address can provide continuous, can also be a discontinuous; The physical relationship of data elements of it can't reflect the logical relationship, so use pointer to indicate the logical relationship between data elements,
5, in data structure, logical structure and physical structure (storage) are closely related, any design is of an algorithm depends on the selected data logical structure, and the realization of the algorithm is dependent on the storage structure, adopted by the
Second, the algorithm
1, the algorithm is the method to solve the problem, it is the essence of the program design, the essence of the program design is to construct the algorithm to solve the problem, and the design of the algorithm depends on the logical structure of data, the realization of the algorithm depends on the physical storage structure of data,
2, the concept: algorithm is a description of a specific problem solving steps, it is the directive finite sequence, which each instruction said one or more operations,
3, the algorithm has the following five important characteristics:
(1) have poor sex: refers to an algorithm should contain a finite number of steps, and the algorithm after performing a number of steps is automatically end rather than an infinite loop, and each step in the limited time,
(2) uncertainty: refers to every step of the algorithm has to have the exact meaning, does not produce ambiguity,
(3) the feasibility: refers to the algorithm of each step should be to perform effectively, and get a certain result,
(4) input: refers to the algorithm executes, obtain the necessary data from the outside world, the computer running the program is for the purpose of data processing, in most cases, these data needs to be obtained by input, and in some cases, data has been included in the algorithm, the algorithm is executed don't need any data, so an algorithm can have zero or more input,
(5) output: refers to an algorithm of at least one or more output, this is the result of algorithm after data processing, no output of the algorithm is pointless,
These features of algorithm, constraint algorithm for programmers to write correctly and make it to correct implementation, so as to achieve expected effect for solving problems,
4, good or bad about execution efficiency of algorithm design, the design of the algorithm must meet the following four requirements:
(1) the correctness, validity means algorithm for all legal input data to be able to meet the requirements of results, but the fact is to prove the validity of the algorithm is extremely difficult, because usually legal input data volume is too big, one by one by exhaustive method validation is not realistic, the so-called algorithm correctness refers to meet the test requirements,
(2) the readability, the algorithm of readability refers to a person to the difficulty of the reading comprehension of algorithm, the algorithm of readable to facilitate communication, promotes the debugging and modification of algorithm, generally increase the readability of algorithm is written when writing algorithm used by the indentation, points module writing methods, such as
(3) robustness for illegal input data, algorithm can give the corresponding response, rather than have unpredictable consequences,
(4) the low efficiency and storage requirements, efficiency refers to the algorithm's execution time; Multiple algorithm for solving the same problem, the algorithm of short execution time of high efficiency and storage needed during the implementation of demand refers to the algorithm of maximum storage space; The smaller storage requirements of algorithm efficiency is high,
5, the efficiency of the algorithm includes two aspects of space and time, called time complexity and space complexity,
6, the time complexity of the algorithm is the time measurement algorithm, with the problem size n increased, the growth rate of the execution time of the algorithm and f (n) at the same rate, called the algorithm of the gradual time complexity, for short time complexity, denoted by T (n)=O (f (n)), among them, the number of executions T (n) is a function about the problem of size n, f (n) is a function of problem size n,
7, the algorithm in the execution of the statement number available to measure the efficiency of an algorithm,
8, the statement refers to statements in an algorithm of frequency, the number of repeat
9, the algorithm's time complexity is lower, the higher the efficiency, the time complexity of the algorithm is raised to prioritize for: O (1) a constant order, O (log2n) logarithmic order, linear order, O (n) O (nlog2n), O (n2) square order, O (n3) cubic order, order O (2 n) index,
10 and the space complexity of the algorithm is as a measure of the required storage space, do remember S (n)=O (f (n)), among them, n is the scale of the problem; F (n) is a statement about the storage space of n functions, note:
(1) in general, when running a program in the machine, in addition to the need to store the program itself, constants, variables, and the input data, also need to store some data operation of secondary storage space,
(2) for the input data of the specific storage only depends on the problem itself, and the algorithm has nothing to do, it only need to analyze the algorithm is implemented in the number of auxiliary space unit,
(3) if the algorithm to perform the necessary auxiliary space relative to the amount of input data is a constant, says that the algorithm is to work for in situ, the space complexity of O (1),
(4) because the algorithm of the execution time and the cost of storage space is a pair of contradiction, namely the algorithm implementation of efficient and often at the expense of the additional storage space, and vice versa,
(5) in terms of general situation, often based on algorithm execution time as the main measure of algorithm,