How to define the data structure of the linked list node

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

1 typedef struct _slist_node{

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

3 }slist_node_t;

Since there is no data in the node, the memory space is saved. 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:

1 typedef struct _slist_int{

2 slist_node_t node; // contains linked list nodes

3 int data; // int type data

4 }slist_int_t;

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

1 #include

2 typedef struct _slist_int{

3 slist_node_t node;

4 int data;

5 }slist_int_t;

6

7 int main (void)

8 {

9 slist_node_t head = {NULL};

10 slist_int_t node1, node2, node3;

11 slist_node_t *p_tmp;

12

13 node1.data = 1;

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

15 node2.data = 2;

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

17 node3.data = 3;

18 slist_add_tail(&head, &node3.node);

19 p_tmp = head.p_next;

20 while (p_tmp != NULL){

21 printf("%d ", ((slist_int_t *)p_tmp)->data);

22 p_tmp = p_tmp->p_next;

twenty three }

24 return 0;

25 }

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:

Int slist_init (slist_node_t *p_head);

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

Typedef slist_node_t slist_head_t;

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

Int slist_init (slist_head_t *p_head);

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

1 int slist_init (slist_head_t *p_head)

2 {

3 if (p_head == NULL){

4 return -1;

5 }

6 p_head -> p_next = NULL;

7 return 0;

8 }

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

Slist_node_t head;

Slist_init(&head);

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

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

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

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

2 {

3 slist_node_t *p_tmp;

4

5 if ((p_head == NULL) || (p_node == NULL)){

6 return -1;

7 }

8 p_tmp = p_head;

9 while (p_tmp -> p_next != NULL){

10 p_tmp = p_tmp -> p_next;

11 }

12 p_tmp -> p_next = p_node;

13 p_node -> p_next = NULL;

14 return 0;

15 }

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:

1 slist_node_t *p_tmp = head.p_next;

2 while (p_tmp != NULL){

3 printf("%d ", ((slist_int_t *)p_tmp)->data);

4 p_tmp = p_tmp->p_next;

5 }

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

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

Slist_node_t *slist_next_get (slist_head_t *p_head, slist_node_t *p_pos);// Get the next node of a node

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

The implementation code is detailed in Listing 3.17 .

Listing 3.17    Traversing related function implementation

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

2 {

3 if (p_pos) { // find the node pointed to by p_pos

4 return p_pos->p_next;

5 }

6 return NULL;

7 }

8

9 slist_node_t *slist_begin_get (slist_head_t *p_head)

10 {

11 return slist_next_get(p_head, p_head);

12 }

13

14 slist_node_t *slist_end_get (slist_head_t *p_head)

15 {

16 return NULL;

17 }

The first user node acquires program, which essentially is the next node in the first node, it is possible to directly call slist_next_get () implementation. Although slist_next_get() 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 . Once you have these interface functions, you can complete the traversal, as shown in Listing 3.18 .

Listing 3.18    Sample program for traversing using various interface functions

1 slist_node_t *p_tmp = slist_begin_get(&head);

2 slist_node_t *p_end = slist_end_get(&head);

3 while (p_tmp != p_end){

4 printf("%d ", ((slist_int_t *)p_tmp)->data);

5 p_tmp = slist_next_get(&head, p_tmp);

6 }

Thus , the return value of slist_begin_get() and slist_end_get() determines the range of the currently active node, which is a semi-closed 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:

Typedef int (*slist_node_process_t) (void *p_arg, slist_node_t *p_node);

Int slist_foreach(slist_head_t *p_head,

Slist_node_process_t pfn_node_process,

Void *p_arg);

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

1 int slist_foreach( slist_head_t *p_head,

2 slist_node_process_t pfn_node_process,

3 void *p_arg);

4

5 {

6 slist_node_t *p_tmp, *p_end;

7 int ret;

8

9 if ((p_head == NULL) || (pfn_node_process == NULL)){

10 return -1;

11 }

12 p_tmp = slist_begin_get(p_head);

13 p_end = slist_end_get(p_head);

14 while (p_tmp != p_end){

15 ret = pfn_node_process(p_arg, p_tmp);

16 if (ret < 0) return ret; // no longer continue traversing

17 p_tmp = slist_next_get(p_head, p_tmp); // Continue to the next node

18 }

19 return 0;

20 }

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

1 #include

2 #include "slist.h"

3

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 }

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_tail(&head, &(node3.node));

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

28 return 0;