[Data Structure] Copy of the complex chain table

By Data Structure

Complex linked lists and single linked lists

First of all, I have to tell everyone[complex linked list] and [normal linked list] Some differences

but this is not very easy to describe

But, I have here[fourprimary school students] to help everyone understand< /span>


< /p>


Little A, Little B, Little C and Little D in childhood

We There are four classmates A, B, C, D

They【 Happy] are lined up

They stand one by one, with nothing to do He thought, everyone only remembers the person behind, then the team will not be scattered

< span style="font-size:18px">

The growth of small A, small B, small C and small D

The A, B, C, and D that were originally well-off have grown up

Some burst between them [LoveThe sparks]

Will each other be [A contradiction arises]? ? ?

[Friendship Boat] Will you just turn it over? ?

In the growing process of Little A, Little B, Little C and Little D

They found [Love]This thing

Little A: I like Little C

Little C: But I like Little B

Little B: Means< strong>[Helpless], I don’t want to take a trip to this muddy water (for fear of Xiao A’s revenge)

< span style="font-size:18px">Little D: As a [single dog], I just love myself


Now , The question is coming, please answer the reader

1, among the above four good friends, 【Several Love】?

2, why B rejected C
< /p>


Okay, is it very It’s messy, even a bit dizzy

So that’s right, this is < strong>[complex linked list]


The definition of complex linked list

In the structure of the linked list, except for one pointing to [next node](the person behind)[Pointer]

There is also a point to[The linked list itself][Any node (or NULL)] [Pointer]

< span style="font-size:18px">Then this linked list is called [complex linked list]
< p>

Processing of complex linked lists

Complex The structure of the linked list (the full version code is at the end)

Structure: 

typedef struct DNode{ int data; struct DNode* next; struct DNode* random;}DNode,*PDNode;

Apply for a node: 

PDNode BuyNewNode(int data){ PDNode NewNode = (PDNode)malloc(sizeof(DNode )); if (NewNode == NULL) {return NULL;} NewNode->data = data; NewNode->next = NULL; NewNode->random = NULL; return NewNode;}

The complex linked list shown:

PDN ode MakeDiffList(){ PDNode pHead = NULL; PDNode CurNode = NULL; PDNode NewNode = BuyNewNode(1); PDNode Node1, Node2, Node3, Node4 = NULL;//Save all four nodes to show them [grow up After] the "crush love" relationship pHead = NewNode; CurNode = pHead; Node1 = CurNode; NewNode = BuyNewNode(2);//NULL CurNode->next = NewNode; CurNode = CurNode->next; Node2 = CurNode; NewNode = BuyNewNode (3);//2 CurNode->next = NewNode; CurNode = CurNode->next; Node3 = CurNode; NewNode = BuyNewNode(4);//self CurNode->next = NewNode; CurNode = CurNode->next; Node4 = CurNode; Node1->random = Node3;//Little A has a crush on Little C Node2->random = NULL;//Little B has no love for anyone Node3->random = Node2;//Little C has a crush on Little B Node4->random = Node4;//小D 爱自己		return pHead;}

这样我们的复杂链表Just enough to make it~~~

Copying complex linked lists

(1) First, the original linked list


< /span>

(2) Then we still first copy each node N as N*, and let N* follow the corresponding N, which is

< br>

Note: During the copying process, the love pointer cannot be copied directly

For example, [A’] points to [C] Instead of [C’]

We should point to [A->love->next] to find [C’] through the next of C.


(3) Finally, delete the generated new complex linked list~


Copy the code of a complex linked list:

PDNode CopyDiffList(PDNode*pHead){ PDNode CurNode = *pHead; PDNode NewHead = NULL; PDNode NewNode = NULL; if (pHead == NULL) {return NULL;} /**************Copy and connect for the first time**** *****************/ while (CurNode!=NULL) {//NewNode = BuyNewNode(CurNode->data*11);//Use 11 times the data in the test, Easy to debug NewNode = BuyNewNode(CurNode->data); NewNode->next = CurNode->next; NewNode->random = CurNode->random; CurNode->next = NewNode; CurNode = NewNode->next;} /** ***********************************************/ /* *************Make a random move*******************/ CurNode = *pHead; while (CurNode!= NULL) { if (CurNode->random != NULL) CurNode->next->random = CurNode->random->next; CurNode = CurNode->next->next;} /************ *************************************/ /*********** *****Delete the original element*******************/ CurNode = *pHead; NewHead = (*pHead)->next; NewNode = (*pHead) ->next; while (CurNo de->next->next!= NULL) {CurNode->next = NewNode->next; NewNode->next = NewNode->next->next; CurNode = CurNode->next; NewNode = NewNode->next;} NewNode->next = NULL; CurNode->next = NULL; /*********************************** **************/ return NewHead;}

Full version code: 

//Structure typedef struct DNode{ int data; struct DNode* next; struct DNode* random;}DNode,*PDNode ;//Generate a new node and return to PDNode BuyNewNode(int data){ PDNode NewNode = (PDNode)malloc(sizeof(DNode)); if (NewNode == NULL) {return NULL;} NewNode->data = data; NewNode ->next = NULL; NewNode->random = NULL; return NewNode;)//Construct a complex linked list PDNode MakeDiffList(){ PDNode pHead = NULL; PDNode CurNode = NULL; PDNode NewNode = BuyNewNode(1); PDNode Node1, Node2, Node3, Node4 = NULL; pHead = NewNode; CurNode = pHead; Node1 = CurNode; NewNode = BuyNewNode(2);//NULL CurNode->next = NewNode; CurNode = CurNode->next; Node2 = CurNode; NewNode = BuyNewNode(3);//2 CurNode->next = NewNode; CurNode = CurNode->next; Node3 = CurNode; NewNode = BuyNewNode(4);//self CurNode->next = NewNode; //CurNode ->random = CurNode; CurNode = CurNode->next; Node4 = CurNode; Node1->random = Node3; Node2->random = NULL; Node3->random = Node2; Node4->random = Node4; return pHead;}/ /Copy complex linked list PDNode CopyDiffList(PDNode*pHead){ PDNode CurNode = *pHead; PDNode NewHead = NULL; PDNode NewNode = NULL; if (pHead == NULL) {return NULL;} /********* ********First copy and connect******************/ while (CurNode!=NULL) {//NewNode = BuyNewNode(CurNode->data* 11);//Use 11 times the data in the test to facilitate debugging NewNode = BuyNewNode(CurNode->data); NewNode->next = CurNode->next; NewNode->random = CurNode->random; CurNode->next = NewNode; CurNode = NewNode->next;} /*************************************** **********/ /************** Make a random move ******************/ CurNode = *pHead; while (CurNode!= NULL) {if (CurNode->random != NULL) CurNode->next->random = CurNode->random->next; CurNode = CurNode->next->next;} /************************************** ***********/ /****************Delete the original element***************** **/ CurNode = *pHead; NewHead = (*pHead)->next; NewNode = (*pHead)->next; while (CurNode->next->next!= NULL) {CurNode->next = NewNode-> next; NewNode->next = NewNode->next->next; CurNode = CurNode->next; NewNode = NewNode->next;} NewNode->next = NULL; CurNode->next = NULL; /***** ********************************************/ return NewHead;}/ /Make test void FunTest(){ PDNode pHead = NULL; PDNode pNewHead = NULL; pHead = MakeDiffList(); pNewHead = CopyDiffList(&pHead); return;)//Main function int main(){ FunTest(); return 0; }

皓皓有话说：< /p>

Q: How to continue reading under the pressure of many courses?

Linux, C++primer

There is also how to preview Java (exceptions, inheritance, regular expressions, etc…) that Mr. Yang gave me.


There will always be a squeeze time, and the class time is ten minutes [Leisure Time] also get in~

WordPress database error: [Table 'yf99682.wp_s6mz6tyggq_comments' doesn't exist]
SELECT SQL_CALC_FOUND_ROWS wp_s6mz6tyggq_comments.comment_ID FROM wp_s6mz6tyggq_comments WHERE ( comment_approved = '1' ) AND comment_post_ID = 5032 ORDER BY wp_s6mz6tyggq_comments.comment_date_gmt ASC, wp_s6mz6tyggq_comments.comment_ID ASC

Leave a Comment

Your email address will not be published.