欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

复杂链表的复制

程序员文章站 2022-06-11 20:17:23
...

首先我们要搞清楚一个问题,什么是复杂链表呢?
或许有的人并没有听过这个词,这个并不奇怪,对于像我这种小菜鸟来说,可能还有好多没听过的知识点呢!复杂链表的复制我也是昨天花了一天的时间才搞明白(嘿嘿,可能是因为我有点笨吧!)。

在复杂链表中,除了有一个next指针指向下一个结点,还有一个random指针指向任意结点或NULL。

eg:
复杂链表的复制
对复杂链表进行复制时,必须对其random域进行复制,但是random域具有随机性,一般不容易复制,我们可以采用以下方法对复杂链表进行复制:
1.在原链表每个结点后插入与每个结点值相等的新结点
复杂链表的复制
2.给新结点随即指针域random赋值
复杂链表的复制
在这一步,我们需要注意的是:当pre->random == NULL时,令cur->random = NULL。
3.将新结点从原链表中拆下来

代码如下:
ComplexLinkList.h //头文件

#ifndef __COMPLEXLINKLIST_H__
#define __COMPLEXLINKLIST_H__

#include<stdio.h>

typedef int DataType;

typedef struct ListNode
{
    struct ListNode* next;
    struct ListNode* random;
    DataType data;
}Node, *pNode, *pList;

pNode BuyNode(DataType d);
pNode CopyComplexLinkList(pList plist);


#endif //__COMPLEXLINKLIST_H__

ComplexLinkList.c //源文件

#include"ComplexLinkList.h"

pNode BuyNode(DataType d)
{
    pNode newNode = (pNode)malloc(sizeof(Node));
    if (newNode)
    {
        newNode->data = d;
        newNode->next = NULL;
        newNode->random = NULL;
        return newNode;
    }
    else
    {
        printf("创建节点失败\n");
        return NULL;
    }
}

pNode CopyComplexLinkList(pList plist)
{
    //1.在原链表每个结点后插入值相等的新结点 
    pNode pre = plist;
    pNode NewNode = NULL;
    pNode cur = NULL;
    while (pre)
    {
        NewNode = BuyNode(pre->data);
        NewNode->next = pre->next;
        pre->next = NewNode;
        pre = NewNode->next;
    }
    //2.给新结点随机指针域赋值
    pre = plist;
    while (pre)
    {
        cur = pre->next;
        if (NULL == pre->random)
            cur->random = NULL;
        else
            cur->random = pre->random->next;

        pre = cur->next;
    }
    //3.将新结点从原链表中拆下来
    pre = plist;
    pNode pre2 = pre->next;//新链表的头
    pNode next = pre->next;
    while (next)
    {
        pre->next = next->next;
        pre = next;
        next = pre->next;
    }
    return pre2;
}

test.c //测试文件

#include"ComplexLinkList.h"

void ComplexLinkList_test()
{
    Node node1, node2, node3, node4;

    node1.data = 1;
    node1.next = &node2;
    node1.random = &node3;

    node2.data = 2;
    node2.next = &node3;
    node2.random = &node1;

    node3.data = 3;
    node3.next = &node4;
    node3.random = &node3;

    node4.data = 4;
    node4.next = NULL;
    node4.random = NULL;

    pNode ret = CopyComplexLinkList(&node1);

}

int main()
{
    ComplexLinkList_test();

    return 0;
}