The data structure

—— The way data structures enable computers to organize and store data.

—— refers to the way a set of data is organized and stored in a computer with one or more specific relationships to each other, and the set of operations defined on that set of data.

The steps a computer takes to solve a specific problem:

1) Abstract a mathematical model from a specific problem;

2) Design an algorithm to solve the mathematical model;

3) Use some computer language to write the program to realize the algorithm, debug and run to solve the problem.

Computer problem solving is a process of data to logical storage, which involves: original data, logical structure (algorithm), storage structure (programming). The diagram below:

The basic concept

Data – objects stored and processed by computers. The meaning of data is very wide, for example, the use of iterative method to find the root of the equation program to deal with the object of real numbers, voice acquisition program to deal with the object of sound.

Data element (element) – The basic unit of data that is considered and processed as a whole in a program. Is the basic unit of operation, with complete and definite practical significance.

Data Items – Data elements are composed of data items. In the database, the data item is also called field or field, which is the minimum identifier of the indivisible data.

Logical structure of data – Logical relationships between data elements (logical relationships are how data elements are related or “adjacencies”).

Basic logical structure

A collection of	Linear structure	A tree structure	The graph structure
There is no adjacency between any two nodes and the form is loose.	In order to form a “chain”, the nodes are joined one by one.	There are branches, hierarchical, the upper node can be adjacent to multiple lower nodes, anti is not.	Most complex, any two nodes can be adjacent.

The storage structure of data

1) Store data elements;

2) The association between data elements.

—— Sequential storage: nodes are in a contiguous storage area.

—— chain storage: in addition to a data element, each storage node also includes Pointers. Each pointer points to a node that has a logical relationship with the node, and Pointers represent the logical relationship between data elements.

algorithm

1. Function description form

Function type Function name (Function parameter list)// Algorithm description{statement sequence}Copy the code

Input and output statements

Input statement:

Scanf (format string, variable 1,... , the variable n);Copy the code

Output statement:

Printf (format string, variable 1... , the variable n);Copy the code

3. Select statements

Conditional statement:

if(expression) statement;if(expression) statement;elseStatements;Copy the code

Branch statements:

switch{case1: statement sequence;break; Case2: statement sequence;break; . Casen: statement sequence;break;
    default: statement sequence;/ / can be omitted
}
Copy the code

4. Loop statements

forSequence of initial assignment expressions; Conditions; Modify expression sequence) statement;while(conditional) statement;do{statement; }while(conditions);Copy the code

Algorithm analysis

1) Time complexity T(n)

Problem: compiling function for 1! + 2! +… +n! The algorithm is as follows:

int fact1(int n)
{    int i, j,temp,s;
    s=0;
    for(i=1; j<=i; j++) { temp=1;
        for(j=1; j<=i; j++) s=s+temp; }return s;
}
    
Copy the code

Multiplication in facT1 algorithmOperation timesforIt withIs proportional to the.

In the fact1Times of multiplication, addition, and assignmentRemember to;T (n)approximation, the algorithm execution time andIs proportional to the.

Time complexity of FACT1, when n is sufficiently large, the execution time of the algorithm is proportional to n.

The order of time complexity

2) Spatial complexity

—— Storage space consumed by the algorithm (space occupied by program code, input data, auxiliary variables)

——S(n)=O(g(n)), where g(n) is a function of the problem size N.

Problem: read n=100 integers into an array, write the array inverse algorithm, analyze the space complexity.

void f1(int a[],int n)
{    int i,temp;
    for(i=0; i<=n/2- 1; i++) { temp=a[i]; a[i]=a[n- 1-i];
        a[n- 1-i]=temp; }}Copy the code

The auxiliary variables required in F1 are two integer variables I and temp, which have nothing to do with the problem size and their spatial complexity is O(1).