“Data Structure C Language Edition Yan Weimin 2nd Edition”: Introduction

1. Basic concepts and terminology

1. Data, data elements, data items and data objects

Data: Data is a symbolic representation of objective things. It is a general term for all symbols that can be input into a computer and processed by a computer program.
Data Element: Data Element is the basic unit of data, which is usually considered and processed as a whole in computers.
- In some cases, data elements are also called elements, records, etc.
Data item: Data item is the smallest indivisible unit that constitutes a data element and has independent meaning.
Data Object: Data Object is a collection of data elements with the same properties and is a subset of data.

Regardless of whether the set of data elements is an infinite set or a finite set, or a set of composite data elements composed of multiple data items, as long as the properties of the elements in the set are the same, it can be called a data object.

2. Data structure

Data structure: Data structure is a collection of data elements that have one or more specific relationships with each other.

A data structure is a collection of data elements with “structure”, which refers to the relationship between data elements.

1) Logical structure

The logical structure of data describes the data in terms of logical relationships. It has nothing to do with the storage of data and is independent of the computer.

The logical structure of data can be regarded as a mathematical model abstracted from specific problems.

Using different storage methods for the same logical structure can result in different storage structures.

Elements of the logical structure of data

data element

relation

According to the different characteristics of the relationships between data elements, there are usually four types of basic structures (in order of complexity):

Collection structure
- There is no other relationship between data elements other than the relationship of “belonging to the same collection”
Linear Structure
- There is a one-to-one relationship between data elements
Tree structure
- There is a one-to-many relationship between data elements
Graph or network structure
- There is a many-to-many relationship between data elements

Among them, set structure, tree structure, graph structure or network structure are all non-linear structures.

Linear structure:
- linear table
- stacks and queues
- string
- array
- generalized table
Nonlinear structure:
- Trees and Binary Trees
- Directed and undirected graphs

2) Storage structure

The storage representation of data objects in the computer is called the storage structure of the data, also called the physical structure

Ⅰ. Sequential storage structure

The sequential storage structure uses the relative position of the elements in the memory to represent the logical relationship between data elements. It is usually described with the help of the array type of the programming language.

Ⅱ. Chain storage structure

The sequential storage structure requires all elements to be stored in a continuous storage space, while the chain storage structure does not need to occupy a whole storage space.

However, in order to express the relationship between nodes, a pointer field needs to be attached to each node to store the storage address of subsequent elements.

Linked storage structures are usually described with the help of pointer types in programming languages.

3. Data types and abstract data types

1) Data type

Data type: Data type is a collection of values and a set of operations defined on this value set.

2) Abstract data type

Abstraction is to extract the essence of the actual problem

Abstract Data Type: Abstract Data Type (ADT) generally refers to a mathematical model defined by the user to represent an application problem, and the name of a set of operations defined on this model.

Abstract data types include three parts:

data object

A collection of relationships on a data object

A collection of basic operations on data objects

The definition format of abstract data type:

ADT abstract data type name{
    Data object: <Definition of data object>
    Data relationship: <Definition of data relationship>
    Basic operations: <Definition of basic operations>
}ADT abstract data type name

The definition format of basic operations:

Basic operation name (parameter list)
 Initial conditions: <Initial condition description>
 Operation result: <Operation result description>

The basic operation has two parameters:

Assignment parameters only provide input values for the operation
Reference parameters start with “& amp;” and in addition to providing input values, they will also return the results of the operation.

The initial conditions describe the conditions that the data structure and parameters should meet before the operation is executed. If the initial conditions are empty, the operation results are omitted. The results describe the changes in the data structure and the results that should be returned after the operation is completed normally.

2. Representation and implementation of abstract data types

The concept of abstract data types is consistent with the idea of object-oriented methods

Abstract data types are independent of specific implementations and encapsulate data and operations so that user programs can only access the data through certain operations defined by abstract data types, thereby achieving information hiding.

Express part

typedef struct{ // Plural type
    float Realpart; // real part
    float Imagepart; // imaginary part
}Complex;

Implementation part

void Create( & amp;Complex C, float x, float y){
    //Construct a complex number
    C.Realpart=x;
    C.Imagepart=y;
}

float GetReal(Complex C){
    //Get the real part of the complex number C=x + yi
    return C.Realpart;
}

float Getimag (Complex C){
    //Get the imaginary part of the complex number C=x + yi
    return C.Imagepart;
}

Complex Add(Complex Cl, Complex C2){
    //Find the sum of two complex numbers Cl and C2
    Complex sum;
    sum.Realpart = Cl.Realpart + C2.Realpart;
    sum.Imagepart = Cl.Imagepart + C2.Imagepart;
    return sum;
}

Complex Sub(Complex Cl, Complex C2){
    //Find the difference between two complex numbers Cl and C2
    Complex difference;
    difference.Realpart=Cl.Realpart-C2.Realpart;
    difference.Imagepart=Cl.Imagepart-C2.Imagepart;
    return difference;
}

3. Algorithm and algorithm analysis

1. Definition and characteristics of algorithms

Algorithm: An algorithm is a finite-length sequence of operations specified to solve a certain type of problem.

An algorithm must satisfy the following five important characteristics:

Finiteness

An algorithm must always end after executing a finite number of steps, and each step must be completed in finite time

certainty

The corresponding operations in each case are clearly specified in the algorithm, without ambiguity, so that both the executor and the reader of the algorithm can clearly understand its meaning and how to operate it.

Feasibility

All operations in the algorithm can be implemented by executing the basic operations a limited number of times.

input

An algorithm has zero or more inputs

output

An algorithm has zero or more outputs

2. Basic standards for commenting on the pros and cons of algorithms

correctness
- With reasonable data input, correct results can be obtained within limited running time.
Readability
- A good algorithm should first be easy for people to understand and communicate with each other, and secondly it should be machine executable
Robustness
- When the input data is illegal, a good algorithm can respond appropriately or handle it accordingly without producing some inexplicable output results.
Efficiency
- Efficiency includes both time and airborne aspects
  - Time efficiency means that the algorithm is reasonably designed and has high execution efficiency, which can be measured by time complexity.
  - Space efficiency means that the storage capacity occupied by the algorithm is reasonable, which can be measured by space complexity.
- Time complexity and space complexity are the two main indicators for measuring algorithms.

3. Time complexity of the algorithm

1) Question size and statement frequency

Problem scale: The problem scale is the input amount of the algorithm to solve the problem. It is the essential representation of the problem size. It is generally represented by the integer n.

The execution time of an algorithm is roughly equal to the sum of the execution times of all its statements

The execution time of a statement is the product of the number of times the statement is executed repeatedly and the time required to execute it once.

The number of times a statement is repeatedly executed is called Statement frequency (Frequency Count)

Algorithm for finding the product of two n-order matrices

for(i=1; i<=n; j + + ){ // Frequency is n + 1
    for(j=1; j<=n; j + + ){ // Frequency is n * (n + 1)
        c[i][j] = 0; // frequency is n * n
        for(k=1; k<=n; k + + ) // Frequency is n * n * (n + 1)
            c[i][j] = c[i][j] + a[i][k] * b[k][j]; // Frequency is n * n *n
    }
}

The sum of the frequencies of all statements in this algorithm is a function of the matrix order tree n, represented by f(n). That is, the execution time of the above algorithm is proportional to f(n)

$f(n) = 2n^{3} + 3n^{2} + 2n + 1$

2) Definition of time complexity of algorithm

In general, the number of repeated executions of basic statements in the algorithm is a function f(n) of the problem size n, and the time measurement of the algorithm is expressed as

$T(n) = O(f(n))$

It means that as the problem size n increases, the growth rate of the algorithm execution time is the same as the growth rate of f(n), which is called the asymptotic time complexity of the algorithm, or time complexity for short. (TimeComplexity)

3) Algorithm time

Common time complexities, arranged in order of increasing order of magnitude, are:

Constant order $O(1)$ , logarithmic order $O(log_{2}n)$ , linear order $O(n)$ , linear logarithmic order $O(nlogn )$ , square order $O(n^{2})$ , cubic order $O(n^{3})$ ,…, Kth power order $O(n ^{k})$ , exponential order $O( 2^{n})$ etc.

Generally speaking, as n increases, the algorithm with slower growth of T(n) is the better algorithm.

4) Best, worst and average time complexity

The time complexity of an algorithm in the best case is the best time complexity, which refers to the minimum possible calculation amount of the algorithm.

The time complexity of an algorithm in the worst case is the worst time complexity, which refers to the maximum possible calculation amount of the algorithm.

The average time complexity of an algorithm refers to the weighted average of the calculation amount of the algorithm when the input instances appear with equal probability in all possible situations.

4. Space complexity of the algorithm

Asymptotic space complexity (Space Complexity) is a measure of the storage space required by the algorithm, referred to as space complexity. It is also a function of the problem size n, recorded as:

$S(n) = O(f(n))$

Generally, when a program is executed on a machine, in addition to registering the instructions, constants, variables and input data used by itself, it also needs some auxiliary storage space for data operations. Among them, the specific storage amount occupied by the input data depends on the problem itself and has nothing to do with the algorithm. In this way, you only need to analyze the auxiliary space required for the implementation of the algorithm. If the auxiliary space required for algorithm execution is constant relative to the amount of input data, the algorithm is called working in place.

Auxiliary space is O(1)

Usually, in view of the sufficient computing space, people use the time complexity of the algorithm as a measure of the algorithm’s quality

One leaf knows autumn, mysteries and mysteries