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

This article mainly explains "how to copy complex linked lists in C language". The content of the explanation in this article is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought. Let's study and learn how C language replicates complex linked lists.

What is a complex linked list?

A complex linked list refers to a linked list with several nodes, each node has a data field for storing data, and two pointer fields, one of which points to the next node. there is also a random point to any node or an empty node in the current complex linked list. What we are going to implement today is to create a new complex list for such a complex list replication.

The data structure of a complex linked list is as follows:

Typedef int DataType; / / types of data fields / / data structures of complex linked lists typedef struct ComplexNode {DataType _ data; / / data struct ComplexNode * _ next; / / pointer to the next node struct ComplexNode * _ random; / / points to random nodes (which can be any node in the linked list or null)} ComplexNode

The figure above is an example of a complex linked list, so how should we replicate a complex linked list?

1, first of all, we should create a new complex linked list according to the existing complex linked list, but the random pointers of all nodes of this new complex linked list point to null, which is easy to achieve, which is equivalent to creating a simple single linked list (newlist). The linked list we want to copy can be called oldlist.

2. Next, we should merge the newly created complex linked list (newlist) with the existing complex linked list (oldlist) into the following form:

In this case, we have merged two complex linked lists into a single linked list (called linklist). Through the observation of this linked list (linklist), we can find that the next pointer of the last node pold (belonging to oldlist node) of the last node pold (belonging to oldlist node) in the merged linklist list (newlist) should be the node that the randow pointer of the pnew node points to.

In this way, we let the pold and pnew pointers go all the way back and finally point all the random pointers that belong to the newly created complex linked list (newlist) to the corresponding nodes. The complex linked list is as follows

After completing the above steps, what we need to do is very simple, we just need to separate the linked list linklist into our newlist linked list and oldlist linked list.

In this way, we have completed the copy of the complex linked list perfectly. Here is the code for the implementation:

Header file complexnode.h:

# ifndef _ _ COMPLEX__NODE__H__#define _ COMPLEX__NODE__H__// contains header file # include#include # include typedef int DataType; / / Type of data field / / data structure of complex linked list typedef struct ComplexNode {DataType _ data; / / data struct ComplexNode * _ next; / / pointer to the next node struct ComplexNode * _ random / / point to a random node (which can be any node in the linked list or null)} ComplexNode; / / create a node ComplexNode * BuyComplexNode (DataType x) of a complex linked list; / / print a complex single linked list void Display (const ComplexNode * cplist); / / copy ComplexNode * CopyComplexNode (ComplexNode * cplist) of a complex linked list; # endif//__COMPLEX__NODE__H__

Specific functions to achieve complexnode.c

# include "complexnode.h" / / create a node of a complex linked list ComplexNode * BuyComplexNode (DataType x) {ComplexNode * cnode = (ComplexNode *) malloc (sizeof (ComplexNode)); if (cnode = = NULL) / / creation failed {perror ("BuyComplexNode ():: malloc"); return NULL;} / / created successfully cnode- > _ data = xscape cnode- > _ next = NULL;cnode- > _ random = NULL;return cnode } / / print complex single linked list void Display (const ComplexNode * cplist) {ComplexNode * pnode = cplist;while (pnode) {printf ("% d data,pnode-% d->", pnode- > _ data,pnode- > _ random- > _ data); pnode = pnode- > _ next;} printf ("over\ n"); / copy ComplexNode * CopyComplexNode (ComplexNode * cplist) {ComplexNode * pold = NULL;ComplexNode * pnew = NULL;ComplexNode * newlist = NULL / pointer to the header node of the new complex linked list pold = cplist;// create a new complex linked list while (pold! = NULL) {ComplexNode * new_node = BuyComplexNode (pold- > _ data); if (newlist = = NULL) / / when there are no nodes in the new complex linked list {newlist = new_node;} else// when the new complex linked list has nodes {ComplexNode * node = newlist While (node- > _ next! = NULL) / / find the last node {node = node- > _ next;} node- > _ next = new_node;// insert a new node} pold = pold- > _ next;} / / create a new complex linked list end / / merge two complex linked lists pold = cplist;pnew = newlist;while (pold) {ComplexNode * curold = NULL;ComplexNode * curnew = NULL;curold = pold- > _ next;curnew = pnew- > _ next If (pold- > _ next = = NULL) {pold- > _ next = pnew;pold = curold;pnew = curnew;break;} pold- > _ next = pnew;pnew- > _ next = curold;pold = curold;pnew = curnew;} / / merge the random pointer of all nodes on the newly created complex linked list to the corresponding node pold = cplist;pnew = newlist;while (pnew) {pnew- > _ random = pold- > _ random- > _ next Pold = pnew- > _ next;if (pold = = NULL) / / the _ next pointer of pnew has pointed to null {break;} pnew = pold- > _ next;} / / end / / end / / detach the merged complex linked list pold = cplist;pnew = newlist;while (pold) {ComplexNode * curold = NULL;ComplexNode * curnew = NULL;if (pnew- > _ next = = NULL) / / the separation has been completed {pold- > _ next = NULL;pnew- > _ next = NULL;break } curold = pold- > _ next- > _ next;curnew = pnew- > _ next- > _ next; pold- > _ next = curold;pnew- > _ next = curnew;pold = curold;pnew = curnew;} / / end of the return newlist;} test code test.c:#include "complexnode.h" / copy of the complex linked list. ? Each node of the linked list, is there? A pointer to next points down? Section / point, and? Random pointer to this linked list? A random node or NULL is now required to copy the linked list and return the copied new linked list. / / ps: the structure of the complex linked list void test () {ComplexNode * cplist;ComplexNode * copylist;ComplexNode * node1;ComplexNode * node2;ComplexNode * node3;ComplexNode * node4;cplist = BuyComplexNode (1); node1 = BuyComplexNode (2); node2 = BuyComplexNode (3); node3 = BuyComplexNode (4); node4 = BuyComplexNode (5); cplist- > _ next = node1;node1- > _ next > _ next = node3;node3- > _ next = node4;cplist- > _ random = node3;node1- > _ random = node4;node2- > _ random = cplist Node3- > _ random = node1;node4- > _ random = node2;Display (cplist); copylist = CopyComplexNode (cplist); Display (copylist);} int main () {test (); return 0;}

The running result of the program is as follows:

Thank you for your reading. the above is the content of "how C language replicates complex linked lists". After the study of this article, I believe you have a deeper understanding of how C language replicates complex linked lists. the specific use of the situation also needs to be verified by practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

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.