Shulou(Shulou.com)06/03 Report--

1. Overview

Data structure definition:

How to save a large number of complex problems in reality to the main memory (memory) with specific data types and specific storage structures, and the corresponding operations performed to achieve certain functions (such as element CURD, sorting, etc.), this corresponding operation is also called algorithm.

Data structure = element + element relationship

Algorithm = operation on data structure

Algorithm:

The algorithm is: the methods and steps to solve the problem.

The measurement algorithm has the following criteria:

Time complexity

The number of times the program is to be executed, not the execution time

Space complexity

The maximum memory to be occupied during the execution of the algorithm

Degree of difficulty (readability)

Robustness

two。 The characteristics and status of data structure

Status:

The data structure is at the core of the software.

Such as the difference between stack and heap in computer memory, people who do not understand data structures may think that memory is divided into two parts, one is called stack and the other is called heap, which is obviously a very superficial and incorrect conclusion.

In fact, if a piece of memory is allocated by pressing the stack out of the stack, then this piece of memory is called stack memory, and if it is allocated by heap sorting, then this piece of memory is called heap memory. The most fundamental difference is the difference in its memory allocation algorithm.

For example, the function is also called by pushing the stack off the stack, or the multi-thread operation in the operating system has the concept of queue, which is used to ensure the operation order of multi-thread. this is also the content of the data structure, or there is the concept of syntax tree in the principle of computer compilation, which is actually the tree in the data structure, such as software engineering, database and so on.

Features:

Data structure training is internal skills, which can not directly solve practical problems, but with this internal skills will be of great benefit to you in other aspects of learning.

Preliminary knowledge (C language)

Learning data structures should have the following knowledge:

Pointer

Structural body

Allocation and release of dynamic memory

Use memory across functions

This section mainly introduces the basis of learning data structure, and explains the relevant knowledge a little.

Pointer

Pointer is the soul of C language, and its importance needless to say.

Pointer definition

Address:

Address is the number of the memory unit

Its number is a non-negative integer starting at 0.

Range: 0-0xFFFFFFFF (232-1) Note: this refers to x86 platform, the maximum memory address on x64 platform is (264-1)

Pointer:

The pointer is the address, and the address is the pointer.

A pointer variable is a variable that stores the address of a memory unit, and the value stored inside it is the corresponding address, and the address is the number of the memory unit (such as the memory address value: 0xffc0).

The essence of the pointer is a non-negative integer with limited operation.

In a computer system, CPU can operate memory directly. The principle of CPU's operation and control of memory can be easily understood as shown in the following figure.

Address line: determine which address unit to operate

Control line: controls the read and write properties of the data unit

Data cable: transferring data between CPU and memory

Classification of pointers

Pointer to the basic type

Int I = 10; / / define a × × variable I initial value of 10

Int * p = I; / / defines a pointer variable p that points to the address of I

Int * p; / / these two lines are equivalent to the above line

P = & I

P stores the address of I, we can say "p points to I", but p and I are two different variables, modifying one side will not affect the value of the other.

* p is equivalent to I, and I is equivalent to * p; both are a piece of memory space, in which the value changes.

Pointers and functions

/ / modify the value of the external argument

Void func (int * p)

{

* p = 100; / / modify the value of external variables within the function

}

/ / modify the value of external argument, the value of secondary pointer

Void func2 (int * * p)

{

* p = 100

/ / modify the value of the external variable within the function. What is actually modified here is the internal address of the pointer. It is neither rigorous nor safe to modify it directly, just to express the meaning.

}

Int main (void)

{

/ / modify external arguments

Int I = 10

Func (& I)

Printf ("I =% d", I)

/ / modify external secondary pointer

Int * p = I; / / equivalent to int * p; p = & I

Func & p

Printf ("I =% d", I)

Return 0

}

/ / change the value of the external variable (argument) of the function through function call

Pointers and arrays

[pointer] and [one-dimensional array]

Int a [5] = {1, 2, 3, 4, 5}

A [3] = (a + 3)

/ / equivalent to a [3] = * (3 + a) = 3 [a]

/ / 3 [a] this way of writing is just not commonly used, and it is correct in principle. An is equivalent to a [0].

/ / an is the first element in the array, and each element occupies the same length of memory unit

The I in / a [I] actually represents a multiple of the unit length.

Array name:

The one-dimensional group name is a pointer constant (its value is immutable)

It stores the address of the first element of the one-dimensional array (the one-dimensional array name points to its first element)

The relationship between subscript and pointer:

(1), a [I] is equivalent to * (a + I)

(2) assume that the name of the pointer variable is p

Then the value of p + I is p + I * (the number of bytes of the variable that p points to)

(3) each subscript represents the first element, and each byte has a corresponding memory address number according to the length of bytes allocated according to the element type (4 bytes of int type), and the pointer variable p holds the address of the first byte of the element.

Operation of pointer variables:

Pointer variables cannot be added, multiplied, or divided.

If the two pointer variables belong to the same array, they can be subtracted

Pointer variables can be added or subtracted by an integer, provided that the final result does not exceed the maximum accessible range of the pointer

/ / Operation of pointer variables

The value of p + I is p + i* (the number of bytes of the variable pointed to)

The value of p-I is p-i* (the number of bytes of the variable pointed to)

Pendant + is equivalent to p1.

P-is equivalent to p-1

/ / the following is a function that modifies the internal elements of the array

Void my_Array (int * a, int length)

{

For (int I = 0; I

< length; i++) { *a[i]++; // 给每个元素加 1 } } int main(void){ int a[5] = {1,2,3,4,5}; my_Array(a , 5); // 调用 } 结构体 为什么会出现结构体? 为了表示一些复杂的数据，而普通的基本数据无法满足要求. 什么叫结构体 结构体是用户根据实际需要，自己定义的复合数据类型 // 如学生类型 struct Student{ int age; char * name; // name 不同，赋值方法不同 char name2[100]; // 这个只能 strcpy(s.name2, "zhangwangdsd"); 字符串拷贝 double height; }; 如何使用结构体 总结起来有两种结构体的使用方式：直接使用 && 通过指针使用 struct Student ss = {12,"xiaoyou",1.73,"xiaozhang"}; struct Student *pst = &ss; ss.name ; 这里直接操作结构体本身 pst ->

Name; here through the pointer address operation, more space saving

Struct Student {/ / Custom structure

Int age

Char * name

Double height

Char name2 [100]

}

Int main (void) {

Struct Student s = {12, "xiaoyou", 1.73, "xiaozhang"}

/ / use it directly

Printf ("age =% d\ nname =% s\ nheight =% .2f\ n", s.agejournal s.namepars.height)

S.age = 21

S.name = "xiaozhu"

Strcpy (s.name2, "zhangwangdsd"); / / string copy

S.height = 1.70

Printf ("age =% d\ nname =% s\ nheight =% .2f\ n% s\ n", s.ageparentice s.nameparentis.heightrepars.name2)

/ / use in the form of a pointer

Struct Student * pst = & ss

Pst-> name = "my new name"

Printf ("name =% s\ n", pst- > name)

Printf ("name =% s\ n", (* pst)-> name)

/ / pst-> name is equivalent to (* pst) .name

/ and (* pst) .name is equivalent to ss.name

/ / so pst-> name is equivalent to ss.name

Return 0

}

Matters needing attention

The type of structural body variable is: struct Student

Structural volume variables cannot be added, subtracted, multiplied or divided, but they can be assigned to each other.

The problem of ordinary structural body variables and structural body pointer variables as function parameters

Typedef struct Student {/ / structure definition

Int age

Char * name

Char name2 [100]

Double height

} myStudent

/ / transfer the entire structure data directly, which takes time & & a waste of memory space.

Void func (struct Student st)

/ / Direct delivery only takes up 4 byte pointers, which saves time and efficiency.

Void func2 (struct Student * pst)

Int main (void) {

MyStudent ss = {12, "xiaoyou", 1.73}

Func (ss)

Func2 & ss)

Return 0

}

Void func (struct Student st) {

Printf ("age =% d\ nname =% s", st.age,st.name)

}

Void func2 (struct Student * pst) {

Printf ("age =% d\ nname =% s", (* pst) .age, (* pst) .name)

Printf ("age =% d\ nname =% s", pst- > age,pst- > name)

}

Dynamic memory allocation and release

Usually, the writing method of directly creating an array is created statically, and after it is created, the corresponding memory will be permanently occupied during the running of the program, which will not only cause a waste of memory space, but also cannot dynamically add elements, so it is very limited. in the program, in order to avoid this situation, we should use a dynamic way to create and destroy the array.

/ / create array statically

Int a [5] = {1, 2, 3, 4, 5}

Dynamic construction of one-dimensional array

Dynamically construct an one-dimensional array of int type.

Int p = (int) malloc (int length)

The void * malloc (size_t _ _ size) function, which has only one formal parameter of type int, indicating the number of bytes required to be allocated by the system

The function of the malloc function is to request the length byte memory space of the system. If the request is completed, the address of the first byte is returned.

If the request is unsuccessful, NULL is returned.

The malloc function can and can only return the address of the first byte, so we need to convert the first byte address (dry address) that has no practical meaning into a meaningful address.

So malloc must be preceded by (data type *) to translate this meaningless address into an address of the corresponding type.

Example:

Int p = (int) malloc (50)

Indicates that the address of the first byte of the 50 bytes assigned by the system is converted into an address of type int, or, to be exact, the first address of a group of four addresses

So p points to the first four bytes, and proomi points to the first four bytes, p [0], p [I] is the first, I + 1 element, respectively.

Double * p = (double *) malloc (80)

Indicates that the address of the first byte of the 80 bytes assigned by the system is converted to an address of type double, to be exact, the first address of a group of eight addresses

In this way, p points to the first eight bytes, and I points to the first eight bytes, p [0], p [I], which is the first, I + 1 element, respectively.

Free (p)

Release the memory pointed to by p instead of the memory occupied by p itself

The code example is as follows:

Void test2 (void)

{

Int len

Printf ("Please enter the length of the array you want to create dynamically:")

Scanf ("d", & len)

Int * pArr = (int *) malloc (len); / / dynamically create an array

* pArr = 4; / / equivalent to a [0] = 4; where pArr is equal to the first address of the array, equal to the array name

PArr [2] = 5; / / equivalent to a [2] = 5

Printf ("pArr [0] =% d\ npArr [2] =% d\ n", pArr [0], pArr [2])

Free (pArr); / / after using, release the corresponding array space

}

Use memory across functions

The local variables allocated within the function will be reclaimed by the system after the function call is completed, and its memory will disappear. But programs often need to define a piece of memory that will be recycled when we run out of it. Such as objects in the OC language. So you need to save the allocated memory, you should use dynamic memory allocation, and then release it manually when you run out of it. This is also a deficiency of the C language: memory needs to be created and released manually, which is what we call MRC when the OC language develops iOS programs. [Apple also discovered this deficiency and launched ARC in iOS 5.)

Here is an example of using memory across functions:

/ / this example is already very object-oriented.

Typedef struct Student {/ / Custom student structure

Int age

Char * name

} myStudent

MyStudent * createStudent (void); / / create student

Void showStudent (myStudent *); / / output student

Int main (void) {

MyStudent * p = createStudent (); / / create student

ShowStudent (p); / / output student

Return 0

}

MyStudent * createStudent (void)

{

MyStudent p = (myStudent) malloc (sizeof (myStudent))

P-> age = 20

P-> name = "xiaoyou"

Return p

}

Void showStudent (myStudent * p)

{

Printf ("student.age =% d\ nstudent.name =% s\ n", p-> age,p- > name)

}

Conclusion

Thank you for watching. If there are any deficiencies, you are welcome to criticize and correct them.

If you have a partner who is interested in big data or a veteran driver who works in big data, you can join the group:

658558542

Welcome everyone to exchange and share, study and exchange, and make common progress. There are also a lot of free materials to help you overcome difficulties on your way to becoming big data engineers and even architects! )

Finally, I wish all the big data programmers who encounter bottlenecks to break through themselves and wish you all the best in the future work and interview.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.