Understanding data structures starts with this article~

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 ：）

 

What is the time complexity

 

 

---

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 ：

 

Dichotomy

 

Sort

 

---

 

 

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 --