Interface problem with single link

Recently, Professor Zhou Ligong has published his painstaking work "Programming and Data Structure" for several years. The electronic version has been distributed to electronic engineers and college groups for free download. Authorized by Professor Zhou Ligong, the content of this book is serialized.

> > >> 1.1.1 Interface

In actual use, it is not enough to add these interface functions to the end of the linked list and traverse the linked list. For example, in the node add function, it is only according to people's habits, the node is added to the end of the linked list, so that the added node is behind the first added node. When writing a function, knowing that adding a node to the tail implementation process requires modifying the p_next value in the end of the original list header and changing it from NULL to a pointer to the new node.

Although the operation is simple, the premise of performing this operation is to find the tail node of the linked list before adding the node. You need to start from the p_head pointer to the head node and traverse each node in turn until the p_next value in the node is found. Until NULL (tail node). As you can imagine, the efficiency of adding a node will gradually decrease as the length of the list increases. If the list is long, the efficiency will be very low, because the list will be traversed each time before adding a node.

Since adding a node to the end of the list will result in inefficiency due to the need to find the tail node, why not change the idea and add the node to the head of the list. Since there is a p_head pointer pointing to the head node in the linked list, the head node can be used for use, and no need to look for it, the efficiency will be greatly improved. When adding a node to the head of the list, the changes in the list are shown in Figure 3.11.

Figure 3.11 Add a node to the list header

In the implementation process, you need to complete the modification of two pointers: (1) modify p_next in the new node to point to the node pointed to by p_next in the head node; (2) modify the p_next of the head node to make it Point to the new node.

Compared with the process of adding a node to the tail of the linked list, it is no longer necessary to find the process of the tail node. No matter how long the linked list is, the addition of the node can be completed through these two steps. The function prototype (slist.h) that adds the node to the head of the list is:

Int slist_add_head (slist_head_t *p_head, slist_node_t *p_node);

Among them, p_head points to the link header node, p_node is the node to be added, and its implementation is shown in Listing 3.21.

Listing 3.21 Adding a sample program to the linked list header

1 int slist_add_head (slist_head_t *p_head, slist_node_t *p_node)

2 {

3 p_node->p_next = p_head->p_next;

4 p_head->p_next = p_node;

5 return 0;

It can be seen that the procedure of inserting the node to the head of the linked list is very simple, no need to find and high efficiency, so in actual use, if there is no requirement for the position, it is preferred to add the node to the head of the linked list.

Modify one line of code in Listing 3.20 as a test, for example, change line 26 to:

26 slist_add_head(&head, &(node3.node));

Since it is possible to add nodes to the head and tail, why not be more flexible, providing an interface function that takes the node to any position? When the node is added to the node pointed to by p_pos, the change of the linked list is shown in Figure 3.12.

Figure 3.12 Adding a Node to an Arbitrary Location

In its implementation, you need to modify two pointers: (1) modify p_next in the new node to point to p_pos to point to the next node of the node; (2) modify p_pos to point to the node's p_next, point it to New node. You can add nodes through these two steps, and add the function prototype (slist.h) from the node to any position in the list as:

Int slist_add (slist_head_t *p_head, slist_node_t *p_pos, slist_node_t *p_node);

Among them, p_head points to the link header node, p_node points to the node to be added, p_pos points to the node to indicate the location of the new node, and the new node is added after the node pointed to by p_pos. For details, see Listing 3.22. .

Listing 3.22 Adding a sample program to any location anywhere in the linked list

1 int slist_add (slist_head_t *p_head, slist_node_t *p_pos, slist_node_t *p_node)

2 {

3 p_node->p_next = p_pos->p_next;

4 p_pos->p_next = p_node;

5 return 0;

Although this function does not use the parameter p_head when it is implemented, the p_head parameter is passed in, because the p_head parameter will be used when implementing other functions, for example, to determine if p_pos is in the linked list.

As you can see from the previous introduction, it is very inefficient to add the node directly to the end of the list. After adding the node to the function at any position, if you add the node to the last added node every time. It is also possible to add a node to the end of the list. See Listing 3.23 for details.

Listing 3.23 Sample program for managing int data

1 #include

2 #include "slist.h"

4 typedef struct _slist_int{

5 slist_node_t node; // contains linked list nodes

6 int data; // int type data

7 } slist_int_t;

8

9 int list_node_process (void *p_arg, slist_node_t *p_node)

10 {

11 printf("%d ", ((slist_int_t *)p_node)->data);

12 return 0;

13 }

15 int main (void)

16 {

17 slist_node_t head;

18 slist_int_t node1, node2, node3;

19 slist_init(&head);

20 node1.data = 1;

21 slist_add(&head, &head, &node1.node); // Add node1 to the end node

23 slist_add(&head, &node1.node, &node2.node); // After adding node2 to node1

24 node3.data = 3;

25 slist_add(&head, &node2.node, &node3.node); // After adding node3 to node2

26 slist_foreach(&head, list_node_process, NULL); // Traverse the linked list, the user parameter is NULL

27 return 0;

Obviously, adding a node to the head and tail of the list is just a special case of adding a node to any position:

● Add a node to the head of the list, that is, after adding the node to the head node;

● Add a node to the end of the list, that is, after adding the node to the end of the list.

The implementation of the slist_add_head() function and the slist_add_tail() function is detailed in Listing 3.24.

Listing 3.24. Adding nodes to the head and tail based on slist_add()

1 int slist_add_tail (slist_head_t *p_head, slist_node_t *p_node)

2 {

3 slist_node_t *p_tmp = p_head; // point to the head node

4 while (p_tmp->p_next != NULL) { // Find the end of the list (until the value of p_next of the node is NULL)

6 }

7 return slist_add(p_head, p_tmp, p_node); // After adding the node to the end node

8 }

9

10 int slist_add_head (slist_head_t *p_head, slist_node_t *p_node)

11 {

12 return slist_add(p_head, p_head, p_node); // Add node to head node

If you want to add a node before a node? In fact, before adding a node to a node, it is just a kind of deformation after adding a node to a node, that is, adding to the back of the node before the node, as shown in Figure 3.13.

Figure 3.13 Schematic diagram of adding a node to any position

Obviously, as long as you get the precursor of a node, you can use the slist_add() function to add a node to the front of a node. To do this, you need to provide a function that gets a node's predecessor, whose function prototype (slist.h) is:

Slist_node_t *slist_prev_get (slist_head_t *p_head, slist_node_t *p_pos);

Where p_head points to the link header node, and the node pointed to by p_pos indicates the location of the lookup node. The return value is p_pos pointing to the previous node of the node. Since there is no pointer to the previous node in the node of the singly linked list, only the traversal of the linked list is started from the head node. When a node's p_next points to the current node, it indicates that it is the current node. For a node, the function implementation is detailed in Listing 3.25.

Listing 3.25. Sample program for obtaining a node predecessor

1 slist_node_t *slist_prev_get (slist_head_t *p_head, slist_node_t *p_pos)

2 {

3 slist_node_t *p_tmp = p_head; // point to the head node

4 while ((p_tmp != NULL) && (p_tmp->p_next != p_pos)) { // find the node pointed to by p_pos

5 p_tmp = p_tmp->p_next;

6 }

7 return p_tmp;

It can be seen that if the value of p_pos is NULL, then when a node's p_next is NULL, it will return, and the returned node is actually the tail node. For the convenience of the user, you can simply wrap a function that finds the tail node. The function prototype is:

Slist_node_t *slist_tail_get (slist_head_t *p_head) ;

The function implementation is detailed in Listing 3.26 .

Listing 3.26 Finding the End Node

1 slist_node_t *slist_tail_get (slist_head_t *p_head)

2 {

3 return slist_prev_get(p_head, NULL);

Since the tail node can be obtained directly through the function, when it is necessary to add the node to the end of the linked list, there is no need to find the tail node by itself. The implementation of modifying the slist_add_tail() function is shown in Listing 3.27 .

Listing 3.27 Finding the End Node

1 int slist_add_tail (slist_head_t *p_head, slist_node_t *p_node)

2 {

3 slist_node_t *p_tmp = slist_tail_get(p_head); // find the tail node

4 return slist_add(p_head, p_tmp, p_node); // After adding the node to the end node

Corresponding to adding a node, you can also delete a node from the linked list. Assuming that there are already 3 nodes in the linked list, and now you want to delete the intermediate nodes, the changes in the linked list before and after the deletion are shown in Figure 3.14 .

Obviously, deleting a node also requires modifying the values ​​of the two pointers: you need to modify the p_next of its previous node to point to the next node of the node to be deleted , and also set the p_next of the deleted node to NULL. .

The function prototype (slist.h) that deletes the node is:

Int slist_del (slist_head_t *p_head, slist_node_t *p_node);

Among them, p_head points to the link header node, p_node is the node to be deleted, and the implementation of the s list_del() function is shown in Listing 3.28 .

Listing 3.28    Delete node sample program

1 int slist_del (slist_head_t *p_head, slist_node_t *p_node)

2 {

3 slist_node_t *p_prev = slist_prev_get(p_head, p_node);// Find the last node of the node to be deleted

4 if (p_prev) {

5 p_prev->p_next = p_node->p_next;

6 p_node->p_next = NULL;

7 return 0;

8 }

9 return -1;

For ease of reference, the contents of the slist.h file are shown as shown in Listing 3.29 .

Listing 3. 29 slist.h file contents

1 #pragma once

2

3 typedef struct _slist_node {

4 struct _slist_node *p_next; // pointer to the next node

5 } slist_node_t;

6

7 typedef slist_node_t slist_head_t; // head node type definition

8 typedef int (*slist_node_process_t) (void *p_arg, slist_node_t *p_node); //Through the callback function type of the linked list

10 int slist_init (slist_head_t *p_head); // chain table initialization

12 int slist_add (slist_head_t *p_head, slist_node_t *p_pos, slist_node_t *p_node); // Add a node

13 int slist_add_tail (slist_head_t *p_head, slist_node_t *p_node); // Add a node to the end of the list

14 int slist_add_head (slist_head_t *p_head, slist_node_t *p_node); // Add a node to the list header

15 int slist_del (slist_head_t *p_head, slist_node_t *p_node); // delete a node

16

17 slist_node_t *slist_prev_get (slist_head_t *p_head, slist_node_t *p_pos); // Find the previous node of a node

18 slist_node_t *slist_next_get (slist_head_t *p_head, slist_node_t *p_pos); // find the last node of a node

19 slist_node_t *slist_tail_get (slist_head_t *p_head); // Get the tail node

20 slist_node_t *slist_begin_get (slist_head_t *p_head); // Get the starting position, the first user node

21 slist_node_t *slist_end_get (slist_head_t *p_head); // Get the end position, the position of the next node at the end node

twenty two

23 int slist_foreach(slist_head_t *p_head, // traverse list

24 slist_node_process_t pfn_node_process,

The comprehensive sample procedure is detailed in Listing 3.30 .

Listing 3.30    Integrated sample program

1 #include

2 #include "slist.h"

3

4 typedef struct _slist_int {

5 slist_node_t node; // include linked list nodes

6 int data; // int type data

7 }slist_int_t;

8

9 int list_node_process (void *p_arg, slist_node_t *p_node)

10 {

11 printf("%d ", ((slist_int_t *)p_node)->data);

12 return 0;

13 }

14

15 int main(void)

16 {

17 slist_head_t head; / / define the chain header node

18 slist_int_t nodel, node2, node3;

19 slist_init(&head);

20

21 node1.data = 1;

22 slist_add_tail(&head, &(node1.node));

23 node2.data = 2;

24 slist_add_tail(&head, &(node2.node));

25 node3.data = 3;

26 slist_add_head(&head, &(node3.node));

27 slist_del(&head, &(node2.node)); // delete node2 node

28 slist_foreach(&head, list_node_process, NULL); // traverse the linked list, the user parameter is NULL

29 return 0;

All the nodes in the program are defined in terms of static memory allocation. That is, the memory occupied by each node has been allocated before the program runs, but the difference is that dynamic memory allocation needs to use malloc at runtime. ) and other functions to complete the allocation of memory.

Since there is no memory leak in static memory, and after the compilation is completed, the memory of each node is already allocated, no need to spend time to allocate memory, and no additional processing code for memory allocation failure. Therefore, in embedded systems, static memory allocation is often used. But its fatal shortcoming is that it can't release memory. Sometimes users want to release their occupied memory when deleting the nodes of the linked list, which requires dynamic memory allocation.

In fact, the core code of the linked list is only responsible for the operation of the linked list, only need to pass the address of the node (p_node), the linked list program does not care about where the memory of the node comes from. Based on this, to achieve dynamic memory allocation, just use the dynamic memory allocation function such as malloc() in the application, as shown in Listing 3.31 .

Listing 3.31    Comprehensive sample program (using dynamic memory)

1 #include

2 #include "slist.h"

3 #include

4

5 typedef struct _slist_int{

6 slist_node_t node; // contains linked list nodes

7 int data; // int type data

8 } slist_int_t;

9

10 int list_node_process(void *p_arg, slist_node_t *p_node)

11 {

12 printf("%d ", ((slist_int_t *)p_node)->data);

13 return 0;

14 }

15

16 int my_list_add(slist_head_t *p_head, int data) // insert a data

17 {

18 slist_int_t *p_node = (slist_int_t *)malloc(sizeof(slist_int_t));

19 if (p_node == NULL) {

20 printf("The malloc memory failed!");

21 return -1;

twenty two }

23 p_node->data = data;

24 slist_add_head(p_head, &(p_node->node)); // Add nodes to the list

25 return 0;

26 }

27

28 int my_list_del (slist_head_t *p_head, int data) // Delete a piece of data

29 {

30 slist_node_t *p_node = slist_begin_get(p_head);

31 slist_node_t *p_end = slist_end_get(p_head);

32 while (p_node != p_end){

33 if (((slist_int_t *)p_node)->data == data){

34 printf(" delete the data %d :", data);

35 slist_del(p_head, p_node); // delete node

36 free(p_node);

37 break;

38 }

39 p_node = slist_next_get(p_head, p_node);

40 }

41 slist_foreach(p_head, list_node_process, NULL); // After deleting the node, print out the data information of all nodes

42 return 0;

43 }

44

45 int main(void)

46 {

47 slist_head_t *p_head = (slist_head_t *)malloc(sizeof(slist_head_t));

48 slist_init(p_head);

49

50 my_list_add(p_head, 1);

51 my_list_add(p_head, 2);

52 my_list_add(p_head, 3);

53 slist_foreach(p_head, list_node_process, NULL); // print out the data information of all nodes

54 my_list_del(p_head, 1);

55 my_list_del(p_head, 2);

56 my_list_del(p_head, 3);

57 free(p_head);

58 return 0;

59 }

If according to an int example using student records management list, you need to add a list node data in the student records. For example :

Typedef struct _student{

Slist_node_t node; // include linked list nodes

Char name[10]; // name is a string

Char sex; // sex is character

Float height, weight; // height and weight are real

Although this definition allows student information to be managed using a linked list, there is a serious problem because modifying the definition of the student record type affects all program modules that use the record structure type. In practical applications, student records can be managed in a linked list or in an array. When using array management, the student record type must be reworked. And node is only the node of the linked list, and has nothing to do with the student record. You can't put nodes directly in the student record structure and should separate them. Based on this, a new struct type needs to be defined to associate the student record with the node so that the student record can be managed with a linked list. such as:

Typedef struct _slist_student{

Slist_node_t node; // include linked list nodes

Student_t student; // student record

See Appendix 3.32 for examples of usage .

Listing 3.32    Comprehensive program example

1 #include

2 #include "slist.h"

3 #include

4

5 typedef struct _student{

6 char name[10]; // name is a string

7 char sex; // sex is character

8 float height, weight; // height and weight are real

9 }student_t;

10

11 typedef struct _slist_student{

12 slist_node_t node; // include linked list nodes

13 student_t student; // student record

14 }slist_student_t;

15

16 int student_info_read (student_t *p_student) // Read student records , randomly generated , for testing purposes only

17 {

18 int i;

19

20 for (i = 0; i <9; i ++) {// random name from 'a' ~ 'z' composition

21 p_student->name[i] = (rand() % ('z' - 'a')) + 'a';

twenty two }

23 p_student->name[i]= '\0'; // string terminator

24 p_student->sex = (rand() & 0x01) ? 'F' : 'M'; // random sex

25 p_student->height = (float)rand() / rand();

26 p_student->weight = (float)rand() / rand();

27 return 0;

28 }

29

30 int list_node_process (void *p_arg, slist_node_t *p_node)

31 {

33 printf("%s : %c %.2f %.2f", p_s->name, p_s->sex, p_s->height, p_s->weight);

34 return 0;

35 }

36

37 int main(int argc, char *argv[])

38 {

39 slist_head_t head;

40 slist_student_t s1, s2, s3, s4, s5;

41 srand(time(NULL));

42 slist_init(&head);

43

44 student_info_read(&s1.student);

45 student_info_read(&s2.student);

46 student_info_read(&s3.student);

47 student_info_read(&s4.student);

48 student_info_read(&s5.student);

49

50 slist_add_head(&head, &s1.node);

51 slist_add_head(&head, &s2.node);

52 slist_add_head(&head, &s3.node);

53 slist_add_head(&head, &s4.node);

54 slist_add_head(&head, &s5.node);

55

56 slist_foreach(&head, list_node_process, NULL); // traverse the linked list, the user parameter is NULL

57 return 0;

In summary , although the linked list is more flexible than the array , it is easy to insert and delete nodes in the linked list , but also loses the " random access " capability of the array . If the node is close to the beginning of the list, then accessing it will be fast; if the node is near the end of the list, accessing it will be slow. However, the singly linked list also has the disadvantage that it cannot be "backtracked". When inserting a node into a linked list, you must know the node in front of the inserted node. When you delete a node from the linked list, you must know the knot in front of the deleted node. Point; it is difficult to reverse the list. If it is a doubly linked list, you can solve these problems.

In the background of the public number, reply to the keyword " program design ", you can read "Programming and Data Structure" online ; reply to the keyword " programming ", you can read "Programming for AMetal Framework and Interface (on)" online.