Format: data type name * pointer variable name 1, * pointer variable name 2 or define one separately and then define it multiple times to complete.

Note: The data stored in pointer variables must be the [address] of [variables of the same type]. This is also the reason why a data type name is required when defining [it can indicate whether the pointer and variable data types are the same]. If we define If the type of the variable is the same as the pointer type, then the first address of the variable storing data can be assigned to the pointer.

Format: data type name * pointer variable name = initial value;

Note: The initial value is the address, so if you assign the variable address to a pointer variable, you need to use the address operator.

Note: You need to pay attention to the priority, order of operations, and understand the special *address operation when defining [it does not serve as a value when defined]

Note: After the definition of the pointer variable is completed, if the operation does not involve the data pointed to the variable but only the address in the pointer variable, please do not add the * sign, and vice versa. (Please contact the [Pointer Operations] section for details.

Example:

Example: [It can be seen that the value of the variable in the pointer has changed by 16, which is the product of the subtracted 4 and the basic integer number of bytes 4]

The connection between pointers and arrays: The array name is neither a pointer constant nor a constant pointer. At some point, it can degenerate into a pointer pointing to the first element of the array. That is to say, the array name can be implicitly converted to a pointer type. .

Advantages: Since array subscripts need to be converted into pointers during compilation, directly using pointers can reduce system compilation time.

Note: You need to consider whether the array is out of bounds when using it, and you also need to consider it when using pointers.

Subscript method: expressed by array subscript, please find the details in the array section.

Pointer method: All elements of the array are represented by the operation of pointers. It is necessary to pay attention to the specialness of pointer operation, which has been summarized in pointer operation.

Key point: The subscript method and the pointer method are closely related in subsequent studies, especially in the connection between pointers and multi-dimensional arrays. The representation of pointer method has detailed examples in [Representation of pointers and multi-dimensional arrays]

Properties of multidimensional arrays: In all arrays, we use subscripts to represent arrays. For arrays of different dimensions, we will represent the corresponding subscript. When the subscript is less than the dimension, it represents the address of this dimension instead of this dimension. The value of the number. In multi-dimensional array pointer operation, when the array name is added or subtracted, it indicates the first address of the added value, and the value operator needs to be used twice.

Pointers and one-dimensional arrays

Pointers and two-dimensional arrays

Pointer variable pointing to a two-dimensional array

array of pointers

Advantages: When an address is assigned to a pointer, the pointer's pointer changes accordingly. Therefore, when we use character pointer variables, it will be more convenient to process strings.

Reference method: Define a character pointer and use it to point to the starting address of the string to reference the string. At this time, there is no need to use the address operator.

define format

Output method: Output the string through %s and character pointer variable name. If you want to output a specific character in a string, you can use pointer arithmetic to change the address pointed by the character pointer to the address of the specific character.

First: the character pointer variable name can be assigned multiple times, but the character array name is an address constant and cannot be assigned. Secondly, the size of the array is fixed and space needs to be allocated in advance.

Second: The type and occupied storage unit are different. The former is the first address of the string, and the latter is the allocated space.

Third: The elements in the array can be reassigned, but we cannot indirectly modify the value of the character constant through the character pointer, otherwise the consequences are unpredictable.

Summary: The character pointer is a variable that can be directly assigned multiple times and points to the first address of the string. The size of the character array is fixed, and the elements in the array are assigned multiple times. When assigning values ​​directly, they must be assigned during initialization. You can also use input functions for assignment, but you cannot use assignment statements.

Purpose: Use pointers as function parameters to ensure that the address passed to the formal parameter is the address. Since modifications made by the called function to parameters are not passed to the main function, sometimes pointer variables are used as function parameters to save such modifications.

Features are: shared memory, two-way transfer

Explanation of this method: To implement this method, you need to ensure that the formal parameters passed are pointers, and secondly, use the formal parameters to participate in the function. You need to know that when executing a statement in a function, it is not the address of the formal parameter that participates in the function, but the formal parameter. Due to the particularity of the pointer, the transformation of the formal parameter at this time is actually the transformation of the variable in the memory address. To ensure accuracy, I verified it and gave an example below

examples:

Reason: Function names and array names have similar characteristics. The function name represents the starting address of the function. The compiler uses the function name to index the entry address of the function.

Definition of function pointer

Initialization and use of function pointers

The function type is determined by the return value. This function whose return value is a pointer is called a pointer function.

Definition form: data type * function name (parameter list);

Note: The return value must be a variable pointer and array pointer of external or static storage class.

examples:

Function: malloc allocates a continuous space of length size from the dynamic storage area of ​​the memory. The parameter of the malloc function is an unsigned integer, and the return value is a pointer to point to the starting address of the allocated dynamic storage area. It should be noted that when the space is failed to be allocated successfully, the malloc function will allocate a null pointer, so when we use it, we must detect whether the return value is a null pointer and perform corresponding operations. For example, in the figure below, the operation that needs to be performed can be to display allocation errors.

Prototype: void *malloc(unsigned int size)

Explanation: void * is the type of the return value, unsigned int is written as an unsigned integer, and size is used to calculate the size, such as size(int), the result is 4.

examples:

Key point: The difference from the malloc function is that the calloc function will initialize the allocated memory space to zero first, and the others are basically the same.

Prototype: void *calloc(num, size)

Explanation: The usage is the same as the malloc function. When one or more of num and size are zero, an allocation error will occur, so you know.

Usage and examples:

Reason: Since memory cannot be allocated infinitely, we must save resources. Therefore, after using the dynamic memory management function, the allocated space must be released to facilitate the use of other variables.

Prototype: void free (void *ptr)

Precautions

Explanation: The essence is the definition of pointers, so it is consistent with the use of basic type definitions. Therefore, the name after typedef also has the same effect.

Form: structure name * pointer variable name; [without struct at this time]

#include <stdio.h>

#include "stdio.h"

Limitation: Can only be applied to input of [single character]

How to use the three: Assign the input characters to character variables or integer variables, which can serve as assignment statements or participate in operations as part of the operation.

Understanding: The character input functions are defined in stdio.h and have no parameters.

getchar (can be used to clear the buffer, that is, act as a pause key)

getche

getch

examples

putchar

Usage format: putchar (formal parameter);

Explanation: Output a single character to the screen, where the formal parameters can be character constants, character variables and expressions. If the formal parameter is a control character, the control function is executed. Because the control character is invisible, the cursor position changes and sounds can only be visually observed.

Format: puts (character array name/string)

Function: Output a string to the computer screen and wrap the string after the output is completed.

Note: The character array must end with '\0'.

Format: gets (character array)

Function: Enter a string ending with a carriage return from the keyboard and put it into the character array, and then automatically add '\0' at the end to get a function value, which is the starting address of the character array.

Description: The input string should be smaller than the length of the character array.

Format: strcat (character array 1, character array 2)

Function: Connect the string in character array 2 to character array 1, remove the '\0' at the end of the string in character array 1, and retain the '\0' at the end of string 2.

Note: Character array 1 must be large enough. The return value of this function is the first address of character array 1.

Format: strcpy (character array 1, character array 2)

Function: Assign the string in character array 2 to character array 1, including the trailing '\0'. Character array 2 can also be a string constant, which is equivalent to assigning a string to a character array.

Note: Character array 1 must be large enough, and assignment statements cannot be used to assign values ​​to the character array.

Format: strcmp (character array 1, character array 2)

Function: Compare two strings from left to right [the character ASCLL is compared] until they encounter differences or '\0'.

The former is equal to the latter, and the return value is 0

The former is greater than the latter, and the return value is a positive integer

If the former is less than the latter, the return value is a negative integer

Note: When comparing strings, only strcmp can be used. It can be used between string constants, and even between character arrays and string constants.

Format: strlen (character array)

Function: Measure the actual length of the string [excluding '\0'] and use it as the return value.

Format: strupr (character array), function: convert all characters to uppercase

Format: strlwr (character array), function: convert all characters to lowercase

Format: strset (character array, character), function: convert all characters into specific characters

Definition: The printf function is called the format control output function

Definition location: <stdio.h>

Basic format: printf("format control string", parameter 1, parameter 2,...);

Declaration of printf function format

The evaluation order of printf: The order is different in different compilation systems. In VC, it is from right to left [very important, be clear]

Definition: The scanf function is called the format control output function

Definition location: <stdio.h>

Basic format: scanf("format control string", address 1, address 2,...);

Scanf function declaration

A description of the scanf function

Knowledge related to integer data

Classification

Knowledge about real data (floating point data)

Classification

character variable

Character constant

Operations on character data

String constant

Note: Character data only occupies one byte in memory.

Finiteness: The algorithm must be able to complete the algorithm through finite steps within the range of human tolerance in every situation it contains.

Feasibility: The algorithm can be completed through the identified basic operations and limited steps.

Determinism: Each statement must be certain and cannot be ambiguous, ensuring that the program produces the same result under the same input conditions.

I/O: The algorithm must have zero or more inputs, and one or more outputs.

Validity: Each step of the algorithm must be able to be executed efficiently

In addition, the determination of the quality of an algorithm also needs to consider correctness, readability, robustness, time complexity and space complexity (efficiency).

Natural language: a language that people use daily, but people’s understanding of it is prone to differences, which reduces the certainty of the program.

Flow chart: The regulations are relatively clear, but too many flow lines can easily cause confusion, make modifications inconvenient, and take time and effort to draw.

N-S diagram: A truly structured method, but it still has factors that make it complicated to modify and draw.

Pseudocode: has many advantages, is easy to modify, uses computer language and natural language, and is easy to understand.

Explanation: The execution time of the algorithm is equal to the sum of the execution time of all statements, and the execution time of all statements is equal to the time of execution once and the number of executions.

Statement frequency: The number of times a statement is repeated.

Definition: The order of magnitude of algorithm execution time is called time complexity, T(n)=Q(f(x))

Sorting (time complexity): constant order < logarithmic order < linear order < linear logarithmic order < square order < cubic order < kth power order < exponential order

Note: It increases with the size of the problem.

Including: [Instructions, constants, variables and input data when the program is executed] and [auxiliary space required for data operations]

Note: If the auxiliary space required is a constant relative to the input data when the program is executed, the algorithm is said to work in place.

Note: The definition is in the above two sentences

Single branch if statement

if...else double branch if statement

if nested statement

if multi-branch statement

General form: switch (expression) {case constant expression: statement; break;...default: statement; break;}

Notice

General form: while (expression) statement;

Explanation: If the expression is always true, the corresponding statement will always be executed. If the expression cannot always be true, an infinite loop will occur. Therefore, the expression of the loop must be false, or there must be a break statement after the corresponding statement.

Note: Expression positions are generally relational expressions and logical expressions, but they can also be other types of expressions. For example, self-added, relationship, 1 and 0.

General form: do{statement;}while (expression);

Explanation: It is very similar to whlie, but there are some differences in form and execution methods. The while loop is judged first and then executed, while this kind of statement is executed once and then judged. It is this execution method that makes it less applicable than the while statement.

General form: goto statement identifier;

Explanation: Execute the statement marked by the symbol, generally used in conjunction with the if statement

Note: If it has returned, it will jump out of the loop directly.

struct structure name {data type variable name;...};

When defining a structure: typedef struct structure name {data type variable name;...} new data type name;

Note: In the above use process, the structure name is omitted, which does not affect the result. However, the structure name cannot be used when defining the structure variables because you omitted it.

Use after definition: typedef data type or data type name [such as int and struct structure name] new data type name

1. Structure members can be any basic data type. In addition, they can also be array and pointer types.

Second, the size and number of structures must be certain, and dynamic structures cannot be defined [not supported in C language]

Third, a structure can be defined in multiple nests, but it cannot be defined recursively [use the structure name to define the structure members in the structure]

4. The names of structure members cannot be the same.

5. You can use the structure name to define pointer variables in the structure, and the pointer variable can point to the structure variable.

First, define the structure first [you can choose to use typedef here], and then define the structure variables by adding the variable name to the struct. Because it is defined separately, you can use the new name after ty to define it. These two methods belong to the [sequential category]

2. When defining the structure, define the structure variables [write the variable name directly after the curly braces, and use commas to separate multiple variables]. At this time, the structure variable name can be omitted, but there are restrictions. Please refer to the structure definition. Related concepts. These two methods belong to the [simultaneous category]

General form: many forms, that is, the defined structure - [structure type] structure variable name = {initial value table};

Specifically: Define the structure first, and initialize the [structure variable] while defining the [structure variable]. Or, define the structure and define and initialize the structure variables at the same time. In the definition and initialization process of the former, if you do not use typedef to establish an alias, you cannot omit the structure type and directly select the variable name for definition.

Explanation: The so-called many forms roughly divide the definition and initialization process into two categories, [sequentially] and [simultaneously], both of which have their own characteristics. [sequentially] can be used with typedef, and [simultaneously] can choose to omit the structure name.

Note: Initialization and the definition of variables are closely related. When initialized through [assignment operation], the definition and initialization are inseparable, [but basic types can be used, this is also the difference]. In addition, [in the initial value table] The order must be consistent with the order of the members in the structure, and there must be no mistakes]

Member operator: structure variable name. member name

Pointer plus value operator: (*pointer variable name).member name

Pointer plus member selection pointer: pointer variable name -> member name

Note: It cannot be quoted as a whole. It can only be used by referencing some variables through the above three methods. It has the function of an ordinary variable, and when it is referenced, it can only be used as a whole first and then as a part.

General form: struct structure name structure array name [size]

struct structure variable name { } structure array name [size]

Definition: Variables defined within a function or in a compound statement are called local variables

Valid scope: Local variables are only valid within the function or compound statement in which they are defined. There is no priority between the two. If there is a compound statement in the function, it will only take effect in one of them according to the defined scope.

Definition: A global variable is a variable defined outside all functions and can be shared by all functions in the same program. When it changes, only the global variable with the same name in the compound statement in the function is not changed.

Valid range: from the defined position to the end of the program.

Note: The use of global variables will reduce the readability of the program, so try not to define global variables.

Scope: global variables, static local variables

Life cycle: When the program is executed, space is allocated and will be released after the entire program is completed.

Scope: automatic variables, formal parameter variables, interrupted field data

Life cycle: From the time the function is called to the end, it runs through the entire execution process of the function.

Automatic variable explanation: refers to local variables that are not declared using static

Explanation of formal parameter variables: refers to parameters in the form of functions

Interrupt context data interpretation: context guarding and return values ​​for function calls

Explanation: When defining variables, we usually use data type definitions, but variables also have storage categories. In C language, variables have two attributes, data type and data storage type.

The complete definition form of the variable: storage category data type identifier variable name;

automatic variable (auto)

Register variable (register)

static variables

external variables (extern)

【1】From the user's perspective, files can be divided into device files and ordinary files.

【2】From the logical structure point of view, files can be divided into record files and streaming files.

【3】From the perspective of encoding method, files can be divided into text files and binary files.

Note: In C language, access to files is achieved through file pointers.

Pointer to file type: The FILE type in C language is a structure type used to store information about files. It is defined in <stdio.h>

File structure pointer: In C language, all external devices are treated as files, called device files.

Function: fopen

Format: file pointer name=fopen (file name, file open mode)

[File pointer name] must be a pointer variable declared as FILE type

[File name] can be a string constant or a character array.

[Open file mode] refers to the file type and operation requirements, as follows

Example

Note: After using the file, you should use the fclose function to close it to prevent the file from being lost or the file being misused again.

Form: fclose (file pointer)

[1] [The closing operation of the file will cause the file pointer to no longer point to the FILE structure corresponding to the file, thus disconnecting the file]

【2】【When writing data to a file, the data will be put into the buffer first. The buffer content will not be sent to the disk until the buffer is full. If it is not full, the buffer content will not be sent. Closing the file will force the buffer content to be sent. 】

【3】【Return 0 for normal file operation, otherwise return EOF】

Division 1

Division 2

Sequential storage: [requires all elements to be stored in continuous storage space in sequence], using the location of elements in the memory to represent the logical relationship between elements. Usually represented by an array.

Chain storage: [Data elements are not required to be stored in continuous storage space, but the data items in each data element are stored in continuous space], and a pointer field needs to be attached to each node. The address used to store subsequent elements.

Definition: A finite sequence composed of n data elements with the same data characteristics is called a linear table. When n equals 0, it is called an empty list.

Features

Sequential storage representation of linear table [sequential table]

Implementation of the basic operations in the sequence table [For the following operations, please set the conditions to determine whether they are legal or not. If they are not legal, an error will be returned]

defect:

non-numeric value, characteristic, operation

is to enable computers to perform non-numerical processing more efficiently,

1. Data

2. Data element (element): the basic unit in data, also called node (node)

3. Data item: The smallest unit that constitutes a data element in the data and has independent meaning and is indivisible.

Scope: Data>Data Object>Data Element>Data Item (scope included)

Data object: Data elements with the same properties, which are subsets of data.

Subgraph: A graph formed by selecting some of the existing points and edges in a given graph and following the connection method in the given graph.

Undirected complete graph and directed complete graph

Sparse graphs and dense graphs: A graph with few edges or arcs is called a sparse graph, and the opposite is called a dense graph [strongly subjective, the judgment standard is determined by people]

Quanhe.com

Adjacent points: Two points are adjacent through a common edge, which can also be said to be associated with the two points.

Degree, in-degree, out-degree

Path and path length

Loop or Loop: A path whose first and last vertices are the same is called a loop or loop.

Simple path, simple loop (simple loop)

Connectivity related concepts

The spanning tree of a connected graph: first it is a connected subgraph, and then it contains all the vertices in the graph, but only n-1 edges.

Directed tree: a directed graph in which one vertex has an in-degree of 0 and the remaining vertices have an in-degree of 1.

Generative forest: composed of several directed trees.

Adjacency matrix: is a matrix that represents the adjacent relationship between vertices

Adjacency list: It is a linked storage structure of the graph

Depth first search [rules]

Breadth first search [rules]

minimum spanning tree

Shortest path [In a weighted directed graph, it is customary to call the first vertex the source point and the last vertex the end point.

AOV-Net [a directed graph using vertices to represent activities and arcs to represent activity priority relationships]

Topological sorting [Arrange all the vertices in the AOV-net into a linear sequence that satisfies: If there is a path between vertex v(i) and vertex v(j) in the AOV-net, then v(i) must be in v(j)before]

AOE-Net [Weighted directed acyclic graph, using edges to represent activities, vertices to represent events, weights to represent the duration of the activity, each event represents that the activity before it has been completed, and the activity after it can start]

Explanation: When n equals 0, it is called an empty tree, otherwise it is a non-empty tree

Definition of non-empty tree

Understanding: The structure definition of tree is a recursive definition, that is, the definition of tree is used in the definition of tree. Trees can also have other representation forms, [nested set form], [generalized table form], [concave representation]

Basic terminology for trees

Key point: The sum of the degrees of all nodes in the tree is equal to the summary point minus 1 [except for the root node, every node will participate in the calculation of the number of degrees]

tree storage structure

The difference between a binary tree and a tree: Each node of a binary tree has at most two subtrees. The subtrees are divided into left and right subtrees, and their order cannot be reversed.

Definition [Tree terms are basically applicable to binary trees]

Properties of binary trees

Full binary tree: a binary tree with depth k and the number of nodes is 2^k minus 1 [equivalent to the degree of all nodes except the root node and the 2^i-1 terminal nodes at the highest level are 2]

Complete binary tree: A binary tree with n nodes of depth k, if and only if each of its nodes corresponds to the nodes numbered from 1 to n in the full binary tree of depth k. [The difference from a full binary tree lies in the number of nodes]

Binary tree storage structure

Binary tree traversal

Note: The number of elements n in the linear table [n>0] is defined as the length of the linear table. When n is equal to 0, it is an empty table.

Features [Summary: The uniqueness of the head and tail, as well as the fact that the head has no front drive and the tail has no rear drive. 】

Definition: refers to using a set of continuous storage units to store data elements of a linear table in sequence

Features: Logically adjacent elements are also structurally adjacent, that is, the logical and physical structures correspond. It is a random storage structure.

Operation [At the same time of initialization, its continuous storage space has been opened up. We can directly represent each position in the array (for example, L.elem[i]=e), because the pointer variable in the structure points to the first address of the space. , equivalent to the array name. 】

understanding diagram

Definition of chained storage structure: A set of arbitrary storage units stores data elements of a linear table. This set of storage units can be either continuous or discontinuous.

Features: Due to the storage structure, element processing must start from the head pointer, so it is also called a sequential storage access structure.

Reason: It is precisely because of this storage structure that in order to express the logical relationship between adjacent data elements, we express the relationship between the two by storing the storage address of the immediate successor in the immediate predecessor. Therefore, in C language, by defining the data domain and pointer fields to form this element, call it a node. The information stored in the pointer field is called a pointer or a chain, and n nodes form a linear table. [Since there is only one pointer field in the node, the linear list composed in this way is called a linear linked list or a singly linked list. 】

explain, distinguish, note

Create singly linked list

operate