Data structure as a basic part of programming , I haven't systematically combed , In addition to the relevant knowledge learned before , The rest is basically returned to the school .
Recently, I'm going to rearrange a data structure tag , View of , In the process of carding, you may realize many things you didn't think of before .
This paper combs the preface of data structure , It's also the most basic part . Although basic, there are still many new things to share , The final list is as follows ：
One In data structure C（C++） language knowledge
Most of the examples in data structure are in the form of C language-written , To understand the example , At least master the basic concepts of data type and function .
1.1 data type
1.1.1 Structural type
In addition to the basic data types in data structures , It also uses a relatively complex structural type .
Structural type generally refers to the use of existing basic types (int 、float、double etc. ) Or self created structured data types that you recreate , Data types in structs can be inconsistent .
Structured data definition method ：
typedef struct { int a; char b; float c; }TypeC;
The code uses typedef The keyword defines the name TypeC Structural data for , You can see that structured data can be a collection of different data types .
Here with a one-dimensional array for the next comparison, easy to understand , The types in the array are consistent, but the types in the structure can be inconsistent ：
alike , Structured data may also form arrays , Compare two-dimensional arrays ：
It can be seen that structured data storage is more flexible , It's also easier to get data .
1.1.2 Pointer type
Pointer is C The soul of language , stay C Language Can operate memory directly through pointer . Compare the Java,Java There is no pointer in ,Java There is only a quotation in ,Java The reference in is actually an object , Still need to occupy memory , So in terms of execution efficiency Java It's not as good as C Of .
Definition of pointer ：
int *a; double *b; TypeC *c;
The definition is very simple , A common identifier is preceded by a * The sign indicates the pointer .
hypothesis m Is a pointer variable , also m It points to a variable n, that m The variables are stored in n Address ,*m It's taking variables n The content of .
&n Is to take n The address of ,m = &n It's a variable n The address of is assigned to m, That's what they say The pointer m Point to n.
// In code Put the variable n Assign a value to a variable x x = n Equivalent to x = *m; (*m It's taking variables n The content of )
1.1.3 Node type
Generally, the construction of node data cannot be separated from pointer , Here we mainly look at the construction of linked list and binary tree node ：
- Linked list
The definition of linked list node ：
typedef struct Node { int data;// The value of the node struct Node *next;// Point to Node Pointer to node }Node;
Be careful ： All defined structural types contain pointer types , And the pointer type points to the same structural type as itself , Then we need to define the structural type of typedef struct Add the name of the node type . above typedef struct Node, This Node Must be added .
- Binary tree
Definition of binary tree node ：
typedef strcut BTNode { int data;// Save values struct BTNode *lchild;// Point to the left child node struct BTNode *rchild;// Point to the right child node }BTNode
- Node creation
The node has been defined , Using the node creation method is recommended ：
BTNode *BT; BT = ( BTNode *) malloc(sizeof(BTNode)) // Fixed way to apply memory
The fixed mode is node space application function ：
explain ：
malloc () ： How to apply for memory needed by new node
sizeof：C Keywords in , It is used to calculate the space occupied by nodes
BT = ( BTNode *) malloc(sizeof(BTNode))
After the above code is executed , Will get BTNode Node of type , And assign the address of the node to BT. If you want to get the content of the node, assign it to x Variable , You should use ：
x = BT -> data;
You can see that using structure variables to get data components , have access to ".", Instead, you use a pointer to a struct variable to get the component , Use "->".
If you want to use "." To get data The value in should be written like this :
x = (*BT).data // Equivalent to x= BT-> data
From the contents of the second part of the pointer, we can see that *BT In fact, it takes the value of the variable it points to , That's the variable that you're pointing to , Since it is a variable value, it is natural to use ".", and BT It means the pointer , Pointer value should be used naturally "->".
1.1.4 typedef and #define
These two words are usually used to name variables .
typedef It's actually C Keywords in language , It means to alias variables .
#define Actually sum #include equally , It's a preprocessing instruction , Preprocessing is also called precompiling , It's a pre compile step , use #define In general, a constant is defined for an identifier ：
#define maxValue 100; // Defined constant maxValue by 100
1.2 function
The function part is more complicated , But when using functions, be clear about the most basic problems , Whether the parameters passed in to the function will change 、 Whether the parameter passes a value or a pointer （ Address ）.
1.2.1 Whether the parameters passed in to the function will change
The function passes in the type if it passes a value , Parameters don't change in general , Because the transmission value The formal and actual parameters of a function are actually two variables , They will not affect each other , such as ：
int x = 0; void insert(int y) { y++; // After calling the function, the original x Value doesn't change }
But when you pass in an address instead of a number ：
int x = 0; void insert(int &y) { y++; // After calling the function, the original x Values change , The address passed in is equivalent to }
When the parameter passed in is a pointer type , And when the pointer type needs to be changed ：
int x = 0; void insert(int *&y) { y++; // After calling the function The pointer y Values change }
1.2.2 Pass value or reference or pointer
The determination of the parameters of the function needs to be considered , Can't generalize , As for parameter types, pass values or references or pointers , Need specific analysis ：
such as , I want to manipulate the data , It's a good time to pass and quote ：
// Data operations pass in values or addresses void insert (dateList &l, int) { // The insert }
To manipulate linked list data , It's better to pass the pointer ：
// It's not appropriate to pass in the whole list operation , You can pass in the head pointer of the linked list int searchAndDelete(LNode *C,int x){ // List operation }
Two Time complexity and space complexity
2.1 Time complexity
Time complexity is a measure of the number of basic operations of the algorithm .
So identify which of the basic operations in the algorithm , And calculate the basic number of operations , Finally, the time complexity is calculated .
2.2 Spatial complexity
Space complexity refers to the measurement of the storage space required by the algorithm at runtime . Different judgments need to be made according to different types of data structures .
About time complexity and space complexity , I also had a detailed introduction to ：）
3、 ... and Basic concepts of data structures and algorithms
3.1 The basic concept of data structure
The data structure contains 3 Aspects of ： Logical structure 、 Storage structure and operation of data .
- Logical structure
Logical structure refers to the logical relationship between data , It has nothing to do with the storage structure of the data , The same logical structure may have multiple storage structures .
The logical structure is divided into Linear structure And Nonlinear structure .
Linear structure refers to the existence between data elements “ one-on-one ” The linear relationship of , Such as arrays 、 Single chain list, etc .
There is a one to many relationship in the nodes of nonlinear structures , It can be divided into tree structure and graphic structure .
- Storage structure
Generally, there are 4 A common storage method ： Sequential storage 、 Chain store 、 Index storage 、 Hash store .
Sequential storage ： Logically adjacent nodes are stored in physically adjacent storage cells , The logical relationship between nodes is represented by the adjacency of storage units .
Chain store ： Logically adjacent nodes do not require physical storage to be adjacent , The logical relationship between nodes is represented by additional pointer fields .
Index storage ： Index is stored in addition to the establishment of storage node information , We also need to create an additional index table to identify the node location .
Hash table （Hash Storage ）： According to the key words of the node, the storage address of the node is calculated by hash function .
3.2 The basic concept of algorithm
Computer algorithms refer to the sequence of steps to solve a problem , It can be understood as a complete problem-solving step composed of basic operation and prescribed operation sequence .
Characteristics of the algorithm ： Fineness 、 deterministic 、 Input 、 Output 、 The feasibility of .
Here are some simple examples of algorithms ：
Frankly speaking, data structure and algorithm are just a simple concept , In the sharing of the following chapters, we will gradually deepen .
Data structures and algorithms are the soul of the program , No matter how the architecture changes , These soul things don't change , So it's very important to understand them .
-- The End --
