Separation of stored values ​​and addresses, data and p_next in a singly linked list

Professor Zhou Ligong's years of hard work "Programming and Data Structure" and "Programming for AMetal Framework and Interface (I)", after the publication of the book content, set off a learning boom in the electronics industry. Authorized by Professor Zhou Ligong, this public number has serialized the contents of the book "Programming and Data Structure" and is willing to share it.

The third chapter is the algorithm and data structure. This paper is the separation of 3.2.1 stored value and address in 3.2 unidirectional linked list and 3.2.2 data and p_next.

> > > 3.2.1 Stored Value and Address

1, stored value

In the structure, although the "current structure type" cannot be used as the type of the structure member, the "pointer to the current structure type" can be used as the type of the structure member. such as:

Where slist is an abbreviation for single list, indicating that the node is a singly linked list node. Since the AMetal platform stipulates that the case can't be mixed, and the type name, variable name, function name, etc. can only use lowercase letters, the macro definition can only use uppercase letters, so in order to be consistent with the AMetal platform, the letters in the type name are all lowercase. .

Since p_next is a pointer type rather than a struct, it points to the same type of struct variable. In fact, the compiler knows the length of the pointer before determining the length of the structure, so this type of self-referencing is legal. P_next is not only a member of the struct _slist_node type, but also points to the struct _slist_node type of data, and then begins to create the type name slist_node_t for this structure. which is:

AMetal specifies that new type names defined with typedef must end with "_t", and in order to be consistent with AMetal, subsequent type names end with "_t". But be sure to be wary of the following declaration traps:

When the p_next pointer is declared, the typedef is not finished yet, and slist_node_t is not yet available, so the compiler reports an error message. Of course, you can also use typedef before defining the structure, you can use the type definition slist_node_t when declaring the p_next pointer. such as:

Finally, it can also be defined in the following form in combination with the above two methods:

That is, a structure type is defined. This method is often used for lists, trees, and many other dynamic data structures. P_next is called a link, and each structure will be linked to the following structure by p_next, as shown in Figure 3.1. Among them, data is used to store the data in the node, the data is provided by the caller (application), p_next is used to store the pointer (address) pointing to the next node in the linked list. The arrow indicates the chain, and the value of p_next is the address of the next node. When the value of p_next is NULL (0), it indicates that the linked list has ended. So you can think of a linked list as a series of contiguous elements. The link between elements and elements is just to ensure that all elements are accessible. If a link is mistakenly lost, all elements from this position will not be accessible.

Figure 3.1 Schematic diagram of the linked list

It is usually necessary to define a pointer p_head pointing to the link header node to facilitate sequential access to all nodes in the list starting from the head node of the list. such as:

After adding the head node p_head, the complete list of linked lists is shown in Figure 3.2.

Figure 3.2 Add a pointer to the node header

At this point, as long as the value of p_head is obtained, all the nodes of the linked list can be traversed (visited) in order. such as:

For functions that operate on linked lists, tests must be performed to ensure that the operation of the empty linked list is also correct. If you use p_head to access each node directly, when the traversal is over, the value of p_head is NULL, it no longer points to the first node, thus losing the entire list, so you must access each node of the list through a temporary pointer variable. . such as:

Next, consider adding nodes to the end of the list. In the initial state, the linked list is an empty table that does not contain any nodes. At this time, p_head is NULL, then the newly added node is the head node, and the value of p_head is directly modified to change from NULL to point to the new node. The pointer, the change of the linked list is shown in Figure 3.3.

Figure 3.3 Adding a node when the linked list is empty

Since the new node is added at the end of the list, the value of p_next in the new node is NULL, as shown in Listing 3.6.

Listing 3.6 Add Node Sample Program (chain table is empty)

Now let's write a simple example to verify that the node is added successfully, as shown in Listing 3.7.

Listing 3.7 Add Node Sample Program (1)

If the node is successfully added, the data 1 can be printed out by printf. Unfortunately, after running the program, nothing happened. When the linked list is empty, the core job of adding a node is to "modify the value of p_head from NULL to a pointer to the new node." Has p_head been modified since slist_add_tail() was called?

When a pointer is passed to a function, it passes the value. If you want to modify the original pointer instead of a copy of the pointer, you need to pass a pointer to the pointer. P_head is defined in the main program, and only the NULL value is passed as an argument to the formal parameter of slist_add_tail(). Since then p_head has no association with slist_add_tail(), so slist_add_tail() is impossible to modify p_head at all. To modify p_head at the time of the call, the address of the pointer must be passed to slist_add_tail(), as described in Listing 3.8.

Listing 3.8 Sample program for adding a new node when the linked list is empty

The test program shown in Listing 3.9 can verify that the addition of the node is successful. First, initialize the linked list to empty, then pass the address of p_head, and then start from the head node and access each node in turn.

Listing 3.9 Adding a Node Sample Program (2)

When the linked list is not empty, it is assumed that there is already a node with the value of data1, and then a node with the value of data2 is added. The change of the linked list is shown in Figure 3.4.

Figure 3.4 Adding a node when the linked list is not empty

The implementation process only needs to modify the value of the original end-of-spin node p_next to change it from a NULL pointer to a pointer to the new node. See Listing 3.10 for details.

Listing 3.10 New Node Sample Program

It is now possible to add more nodes as a test program based on Listing 3.9, as detailed in Listing 3.11.

Listing 3.11 Add Node Sample Program (3)

Through this program, you can verify that the node is added successfully, but you can see that the program list 3.10 can be found. When adding a node, you need to determine whether the current linked list is empty, and then make corresponding processing according to the actual situation. The reason for the conditional judgment is that the linked list may be empty and there is no valid node. If the linked list initially has a node head:

Since this is an actual node, it is no longer a pointer to the head node, so the linked list cannot be empty. The schematic diagram of the linked list is shown in Figure 3.5.

Figure 3.5 Schematic diagram of the linked list

For this type of linked list, there is always a head node that does not require valid data. For an empty linked list, it contains at least the head node. The schematic diagram of the empty linked list is shown in Figure 3.6. Since no other nodes are included in the initialization, the value of p_next is NULL.

Figure 3.6 Schematic diagram of the empty linked list

When you need to add a new node, look for the tail node from the head node. When the tail node is found, the p_next value of the tail node is modified to change from a NULL pointer to a pointer to the new node, as shown in Listing 3.12.

Listing 3.12 New Node Sample Program

Note that p_head here always points to the existing head node, which is different from p_head in Listing 3.6. It can be tested using the test program shown in Listing 3.13. Since there is no successor node during initialization, the p_next field The value is NULL.

Listing 3.13 Add Node Sample Program (4)

Although the program shown in Listing 3.12 no longer uses the judgment statement, it brings a new problem. The data of the head node is idle, and only p_next is used, which is bound to waste memory. Of course, for the current example, data is int type data, occupying only 4 bytes, and wasting 4 bytes may be acceptable, if data is other types?

If the elements of the linked list are data in the student record, the structure is the best choice because the data in the student record is different types of data. As a sample program, it is not possible to cover everything, so only a few typical data is taken as a member of the structure. Based on this, a structure type and a new structure type name are specifically defined for the data in the student record. Its data type is defined as follows:

That is, the structure can be used to store the data in the student record, and the storage relationship of its members in memory is shown in Figure 3.7. If the element_type_t declaration is of the same type as student_t, the linked list data structure is:

Figure 3.7

That is, the type of data related to the application is another structure type student_t.

At this point, as long as you define a variable node of type slist_node_t, you can reference the members of the structure:

Then the storage relationship of each member of the linked list in memory is determined, as shown in Figure 3.8. If using an expression

Figure 3.8

The member data of the slist_node_t structure can be referenced through the node variable. At this point, just use node.data as a student_t type variable, you can use the expression

References the member name of the student_t structure member data (data in the student record).

When the data in the linked list changes from int type to student_t, the wasted space will be the size of the student_t type. Here is just an example. The student record may contain more information, such as student number, grade, blood type, dormitory number, etc., and the head node will waste more space.

At the same time, there is also a problem here. The change of the data type will lead to the change of the program behavior, making the program unable to be universal. The data type must be determined before compilation, and the program cannot be released in the form of a general library. If you want to make the code generic, use void * that accepts any data type.

2, storage address

In order to store the void * type elements in the linked list, you can use the linked list to store any pointer type data passed by the user. The data structure of the linked list node is defined as follows:

The data field type of the node is void * type pointer, data points to user data, and the data in the node is user data provided by the caller (application).

Although void * seems to be a pointer, it is essentially an integer, because in most compilers the pointer is the same size as the int, so the universal list is a linked list of the int data type. Only the data field of the node stores the address of the user data associated with the application.

Assuming that the data stored in the student record of the struct _student structure is user data, it is sufficient to pass the address of the structure variable storing the student record to the data field of the linked list node, that is, the structure of p->data pointing to the user data. Storage space, as shown in Figure 3.9. If the void * pointer points to a structure or a string, but a simple type such as an int, then just cast it at the time of use.

Figure 3.9 data points to user data

If you want to associate the linked list data with the student record structure, you must first define a student record and then point the void * pointer in the linked list node to the student record. Each node consumes more space for a void * pointer than a linked list of data members that directly use the student structure as a linked list node. Although there is not much space for a node, if there are many nodes, the wasted memory is quite considerable, especially in embedded systems where the memory resources themselves are very tight.

Obviously, to save memory space, you can't define void * type pointers. You must put data (such as student records) and p_next of linked list nodes together, but you can't reuse the linked list program.

Analysis of the definition of the current linked list node, which mainly consists of two parts: the p_next pointer of the linked list and the data data of the user's concern. Looking back at the slist_add_tail() function shown in Listing 3.12, there is no code to access data, indicating that data is independent of the linked list. In this case, can you separate them?

> > > 3.2.2 Data is separated from p_next

Since the linked list only cares about the p_next pointer, there is no need to define the data field in the linked list node, so it is only necessary to keep the p_next pointer. The data structure of the linked list node (slist.h) is defined as follows:

Since there is no data in the node, the memory space is saved, and the schematic diagram is shown in Figure 3.10.

Figure 3.10 Schematic diagram of the linked list

When users need to use linked lists to manage data, they only need to associate data with linked list nodes. The easiest way is to package the data and linked list nodes together. Take the int type data as an example. First, the linked list node is used as a member of it, and then the int type data related to the user is added. The structure is defined as follows:

Thus, no matter what the data, the linked list node is only a member of the user data record. When calling the linked list interface, you only need to use the address of the node as the linked list interface parameter. When defining the data structure of the linked list node, since only the data member is deleted, the original slist_add_tail() function can be used directly. The sample program for managing int data is detailed in Listing 3.14.

Listing 3.14 Sample program for managing int data

Since the user needs to initialize the head to NULL, and the traversal needs to operate the p_next pointer of each node. The purpose of separating the data from p_next is to separate the respective functional responsibilities. The linked list only needs to be concerned with the processing of p_next, and the user only cares about the processing of the data. Therefore, for the user, the definition of the linked list node is a "black box", which can only access the linked list through the interface provided by the linked list, and should not access the specific members of the linked list node.

In order to complete the initial assignment of the head node, an initialization function should be provided, which essentially sets the p_next member in the head node to NULL. The prototype of the linked list initialization function is:

Since the type of the head node is the same as the type of other common nodes, it is easy for the user to think that this is a function to initialize all the nodes. In fact, the meaning of the head node is different from that of the ordinary node. Since the head node can be traversed through the entire linked list, the head node is often held by the owner of the linked list, while the ordinary node only represents a single node. a node. In order to avoid the user confusing the head node with other nodes, you need to define a header node type (slist.h):

Based on this, modify the linked list initialization function prototype (slist.h) to:

Among them, p_head points to the link header node to be initialized, and the implementation of the slist_init() function is shown in Listing 3.15.

Listing 3.15 List initialization function

Before adding a node to the linked list, you need to initialize the head node. which is:

Since the type of the head node is redefined, the function prototype that adds the node should also be modified accordingly. which is:

Among them, p_head points to the link header node, p_node is the new node, and the implementation of the slist_add_tail() function is shown in Listing 3.16.

Listing 3.16 New Node Sample Program

Similarly, the traversal of the current linked list is also a way to directly access the members of the node. The core code is as follows:

Here mainly three operations on the linked list: (1) get the first user node; (2) get the next node of the current node; (3) determine whether the linked list ends, compared with the end tag (NULL).

Based on this, three corresponding interfaces will be provided to implement these functions, so as to avoid direct access to node members. Their function prototype is (slist.h):

The implementation code is detailed in Listing 3.17.

Listing 3.17 traversing the relevant function implementation

The first user node obtained in the program is essentially the next node of the head node, so it can be called directly by calling slist_next_get(). Although slist_next_get() does not use the p_head parameter when it is implemented, the p_head parameter is passed in, because the p_head parameter will be used to implement other functions, for example, to determine if p_pos is in the linked list. Once you have these interface functions, you can complete the traversal, as shown in Listing 3.18.

Listing 3.18 Example program for implementing traversal using various interface functions

Thus, the return value of slist_begin_get() and slist_end_get() determines the range of the currently valid node, which is a semi-open and semi-closed space, namely: [begin, end), including begin, but does not include end. When begin and end are equal, it indicates that the current linked list is empty and there is no valid node.

In the traversal program shown in Listing 3.18, only the printf() statement is the statement that the user actually cares about. Other statements are fixed patterns. For this purpose, a general traversal function can be encapsulated, which is convenient for the user to process and link each link. Point the associated data. Obviously, only the user who uses the linked list knows the specific meaning of the data. The actual processing of the data should be done by the user. For example, the print statement in Listing 3.18, so the behavior of accessing the data should be defined by the user, defining a callback function. Passing parameters to the traversal function, each time a node is traversed, the callback function is called to process the data. The function prototype (slist.h) that traverses the linked list is:

Among them, p_head points to the link header node, and pfn_node_process is the node handle callback function. Each time a node is traversed, the function pointed to by pfn_node_process is called, which is convenient for the user to process the node data as needed. When the callback function is called, the user parameter p_arg is automatically used as the first parameter of the callback function, and the pointer to the node currently traversed is used as the second parameter of the callback function.

When traversing to a node, the user may wish to terminate the traversal, as long as a negative value is returned in the callback function. In general, to continue traversing, return 0 after the execution of the function. The implementation of the slist_foreach() function is detailed in Listing 3.19.

Listing 3.19 Traversing the linked list sample program

You can now use these interface functions to iterate through the functions shown in Listing 3.14, as detailed in Listing 3.20.

Listing 3.20 Sample program for managing int data