[RTOS training camp] course learning methods and structural knowledge review + linked list knowledge

One 、 Learning methods

Because some students are new to the Group , So let's talk about learning methods here .

1. preview

We will inform the chapters to be previewed after each evening class , Students need to watch relevant videos as follows .

​ 1.1 Open the website ： Official website of baiwen.com

​ 1.2 Click... On the home page " In depth study of single-chip dual architecture dual system project practice line work "

​ 1.3 Click again " Single chip dual architecture dual system project practice ", Watch Video

On the computer 、 In the mobile browser 、 Wechat or QQ in , You can open our official website , And then use Super clear watch （ At present, wechat applet does not support ultra clear viewing ）.

2. Evening class

After the preview, we have classes in the evening , Precautions for evening classes are as follows ：

Most of our students are at work , You may not be able to attend the evening course , So we are the first 2 Tianhui will sort out the graphic notes of the evening class on the official website , In the following similar positions ：

In this picture 4-7、4-8 It is based on the supplementary and expanded content recorded in the previous evening class .

Not every evening class 2 Video will be recorded every day , But there must be pictures and texts .

The last file in the red box in the figure is one of ours AI Course 、AI The playback , Basically QQ Reproduction of chat content .

3. Have a problem

If you encounter problems in your study, you can ask questions about the corresponding version in our forum , How to use the Forum ：

​ 3.1 Browser open ： On the official website of baiwen.com, click the Q & A Forum
​ 3.2 Login username ： The mobile number when purchasing the course
​ Initial password ： 100ask （ It is suggested to change your password ）

​ （ If you are a student who recently registered for class , The system may not have entered an account , Please register with your mobile number , Then contact the head teacher to open the permission to post ）

​ 3.3 If there is a problem with the account , Contact the head teacher .

The learning method of this course , Is the last repetition , I won't repeat it in the next class .

Two 、 Review

In the previous lesson , We spent a lot of time talking about variables and addresses 、 The pointer .

There is a pithy formula to remember ：

Variable 、 Variable , It can change .
It can change , It means readable and writable .
If you can write , It must be in memory .

Take a look at this picture first ：

Defined 4 A variable , Since it's a variable , It must be in memory .

Attention, everyone , For the pointer , stay 32 Bit processor , The address must be 32 Bit , That is to say 4 Bytes .
Pointers are used to store addresses , So pointer variables , Its size is also 32 Bit , It's also four bytes .

In the picture, we decide ： A structure person The pointer to ,
Despite this person The structure is very large , But its pointer is still 4 byte .

3、 ... and 、 Linked list

3.1 Basic knowledge of linked list

Okay , Variables and addresses 、 Pointer review completed , Now let's review the linked list .

Let's assume that there are three spies ,ABC.

A The offline of is B,B The offline of is C.

let me put it another way , Namely A Yes B The address of ,B Yes C The address of .

That's what code is like ：

Draw a picture for everyone , This picture has been drawn for you in the last class .

First, we define three structures ,ABC.

There must be these three structures in memory .

Take another look at the following sentence , What will happen to him ：
A.next_addr = &B;

Remember the picture above , Structure A Inside next_address, be equal to B The address of .

I drew the blue arrow , It just gives us an understanding of the image , Structure A There are B The address of .

The core of the linked list is :

There is a pointer in the linked list structure , This pointer , Equal to the address of other structures .

In terms of human visualization , It's the structure A A pointer inside , Point to the structure B.

Okay , Now I still review the knowledge of the previous evening class , Now let's talk about new knowledge .

First, as a linked list , There must be a head , How can we determine the head of this linked list ？

In fact, we use a pointer to represent the chain header , The code is as follows ：

Take a look at this code , We define three structures , There is also a structure pointer .

They are all variables , There are corresponding spaces in the memory .

In the picture above , In the red box , We use that pointer to represent the chain header .

Now this chain header , Its value is empty , That is to say, the address saved in it is empty ： This is an empty list .

How can we judge whether a linked list is empty ？

if (pHead == NULL)
   printf("It is empty list");

So how can we add an element to this linked list ？

Let's use a graph to show , Suppose the structure A Put it on the list :

Again, it's very simple to insert the first item , I make this chain header directly equal to the structure A The address of .

We use arrows to indicate , Let's understand the linked list more vividly ：

In this picture, I added this arrow , There are no arrows in the code ,
It's just pHead This variable , Its value is equal to the structure A The address of .

3.2 Insertion of linked list

Now put another structure B Put it in the list . There are two ways , You put it at the head of the list ？ Or at the end of the linked list ？

We draw a picture ：

On the left , Yes, there are only elements in this linked list A.

We can do it in A Insert this new element to the left of B, It can also be in A Insert this new element to the right of B.

in other words , We can insert new nodes in the head of the linked list , You can also insert a new node at the end of the list

In the picture on the right , The above one is B Insert it at the end of the linked list , Here is a B Insert it at the head of the linked list .

How to write code ？

Let's take a look first , hold B Insert it at the head of the linked list ：

void InsertNodeToHead(struct spy *newNode)
{
    
	/*  Insert it at the front of the linked list  */
	newNode->next_addr = pHead;
	pHead = newNode;
}

Let's draw a picture to demonstrate ：

In this picture , On the left is the code , On the right is the result .

Suppose you first insert the structure A,

The label in the execution diagram is 2 When it comes to code , Namely ：A.next_addr = pHead Equal to the initial value NULL.

Execute the label in the above figure as 3 When it comes to code , Namely ：pHead = A The address of .

The result is on the right side of the figure above ,
I also wrote the label in the picture 2、 label 3.
label 2 Where? A Of next_address be equal to NULL,
label 3 Where? pHead Equal to structure A The address of .

Next, let's add a number 2 Elements B, We insert elements at the head of the linked list B.

Use blue labels in this picture , Mark the calling process .

On the left is the code , See the label as 4 Code for , You use this function to put elements B Insert the list . How to do it? ？ There are also two steps ：

• The first 1 Step ：

  Don't you insert it into the head ？ Then I'll let B Point to the head .

But the head is equal to A, In fact, it is B Yes A.

So now B Yes A, The head also points A.

• The second step ：

Keep your head pointing B:

This is a complete insertion process .

This figure needs to be supplemented , Let the end point to NULL.

Put the linked list , Want to be a team holding hands , It's easy to understand .

Just now we talked about inserting an element into the head of the linked list , Then how to insert an element at the end of a linked list ？

Let's assume that there are several elements in this diagram , We are on the right of the last element , And insert new elements .

The results are as follows ：

It's also easier to write in code ：

tmp Suppose it's the last element ,B It's a new element .

tmp->next_addr = &B;
B.next_addr = NULL;

The key to the problem is , How can I find the last element in the original list .

Take a look at this code , Use one while loop ：

The red circle in the picture , What are its characteristics : its next_addr be equal to NULL.

If it's not the last item , Let's take out the one on his right ： tmp = tmp->next_addr.

This sentence may be difficult for some students to understand , Draw a picture here to explain ：

Look at the code in the circle , Is it on the right temp->next_addr ?

Then I let this tmp The pointer , Point to the structure on the right ：tmp = On the right .

This is how these two sentences of code are written together ： tmp = tmp->next_addr;

Insert the code at the end :

void InsertNodeToTail(struct spy *newNode)
{
    
	struct spy *tmp;
	
	/*  Find the last one  */
	tmp = pHead;
	while (tmp)
	{
    
		if (tmp->next_addr == NULL) /* tmp That's the last item  */
			break;
		else
			tmp = tmp->next_addr;
	}
	
	/*  The last item points to the new node  */
	if (!tmp)  /*  Empty queue  */
	{
    
		pHead = newNode;
	}
	else
	{
    
		tmp->next_addr = newNode;
	}
	
	/*  The new node points to NULL */
	newNode->next_addr = NULL;
}

3.3 Deletion of linked list

Let's talk about ： In the list , How to delete an element .

Look at this picture again , In the linked list, we want to delete this node in the red box

Imagine again , In a team holding hands , A man is leaving , Is the person in front of him holding hands with the person behind him ？

So we need to find out the person in front and the person behind .

hypothesis tmp It's the person in front , Who is the man behind ？oldNode->next_addr,oldNode Represents the node to delete .

How to write the code ：tmp->next_addr = People behind = oldNode->next_addr

So the key is how we find the person in front : tmp.

It's also relatively simple , Traversing the linked list ：

It's also a cycle , If my next item is equal to yours , I'm your last one .

After finding it , Just execute this instruction ： tmp->next_addr = People behind = oldNode->next_addr

3.4 The use of linked list

Now understand the insertion and deletion of linked lists , So how do we use the linked list ？

For example, in the last class, we said , The head teacher needs to count the information of each student , How to operate with a linked list ？

How to print out all these information , You can traverse the linked list from the chain header ：

Now back to our video , Our video also talks about the operation of linked lists .

I'll draw this picture for you ：

First, we define a structure ：List list.

It's a variable , There must be a corresponding space in the memory .

After initializing the linked list , Its result is like the figure above .

Because this linked list has a root node , So set the number of nodes to 1.

At the beginning of this list, there was only one element ,
Its next element is itself , Its last element is itself .

This is a two-way circular linked list , The two-way circular linked list is a little more complicated ,

But how complicated , It is composed of two one-way linked lists , Let's not talk about it here .