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

复杂链表的复制(链表的每个结点,有一个next指针指向下一个结点,还有一个random指针指向这个链表中的一个随机结点或者NULL)

程序员文章站 2022-06-11 20:24:12
...

举一个复杂链表的例子:

复杂链表的复制(链表的每个结点,有一个next指针指向下一个结点,还有一个random指针指向这个链表中的一个随机结点或者NULL)
首先我们需要创建一个复杂链表:
  1. 要创建链表首先需要一个结构体:(结构体成员须包括数据,next指针,以及random指针)

typedef struct node{
    DataType data;
    struct node* next;
    struct node* random;
}Clinklist;
  1. 创建如上图所示的复杂链表
    Clinklist node1, node2, node3, node4;
    Clinklist *chead=&node1;

    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;

复杂链表的复制

1. 先处理复杂链表为空的情况。 链表若为空,则直接返回。
2. 若复杂链表不为空。想要复制链表,首先在原链表的每个结点后边插入值相等的新结点。
复杂链表的复制(链表的每个结点,有一个next指针指向下一个结点,还有一个random指针指向这个链表中的一个随机结点或者NULL)
3. 给新结点的随机指针域复制。由图可见:新结点的随机指针域 是 原结点随机指针域 的下一个结点。
复杂链表的复制(链表的每个结点,有一个next指针指向下一个结点,还有一个random指针指向这个链表中的一个随机结点或者NULL)即就是pnewnode->random=pcur->random->next;
4. 将复制完成的新结点从原结点中拆下。

复杂链表复制

//复杂链表的复制
Clinklist *CopyComplexlist(Clinklist *chead)
{
    Clinklist *pcur = NULL;
    Clinklist *pnewnode = NULL;
    Clinklist *pnode = NULL;


    //1.处理复杂链表为空的情况
    if (chead == NULL)
    {
        return NULL;
    }
    //2. 复杂链表不为空的情况
    //a. 在原链表的每个节点后插入值相等的新节点

    pcur = chead;
    while (pcur)
    {
        pnewnode = (Clinklist *)malloc(sizeof(Clinklist));
        if (pnewnode == NULL)
        {
            return NULL;
        }
        pnewnode->data = pcur->data;

        pnewnode->next = pcur->next;
        pcur->next = pnewnode;

        pcur = pnewnode->next;
    }
    //记住头结点方便返回
    pnode = chead->next;

    //b.给新结点的随机指针域赋值
    pcur = chead;
    while (pcur != NULL)
    {
        pnewnode = pcur->next;
        if (pcur->random == NULL)
        {
            pnewnode->random = NULL;
        }
        else
        {
            pnewnode->random = pcur->random->next;
        }
        pcur = pnewnode->next;
    }
    //c.将新节点从原链表中拆下

    pcur = chead;
    pnewnode = chead->next;

    while (pnewnode != NULL)
    {
        pcur->next = pnewnode->next;
        pcur = pnewnode;
        pnewnode = pnewnode->next;
    }
    pcur->next = pnewnode;

    return pnode;
}