複雜單連結清單的複制

複雜單連結清單的複制：

一、何為複制單連結清單

就我們所知，單連結清單也就是一個結點包含一個資料域和一個指針域，這樣若幹個結點構成的連結清單。而複雜單連結清單和普通單連結清單差不多，唯一的不同就是多一個random。我們可以用一張圖來表示：

那我們怎麼來進行複雜連結清單的複制呢，現在公認的最有效的方法隻有一種，就是在原有單連結清單的每個元素後面添加一個結點，結點中的data是前一個結點的data，結點的next是原來結點的next。

由上圖可見我們已經将結點都插入到原有複雜單連結清單的後面去了，這樣我們就已經搞定了複雜單連結清單的一個複制：複制next關系。接着要做的就是複制它的random關系，由圖，可以很清楚地看到，要複制單連結清單的結點的random也就是原有結點的random的next。用一個例子來解釋：

由圖：cur的random的data為3，如果要進行複制，那麼複制出來的連結清單的random的data也必須是3，且指向的位置應該和原來的位置是一樣的。那麼可以明顯看到copy->random = cur->random->next。

這樣也就完成了一次random的複制。如此重複，就能将所有的random關系都賦好。

最後也就剩一個拆分了，這步最為簡單，将兩個單連結清單從一個單連結清單中分離出來就行。

二、代碼實作

頭檔案：

#ifndef __COMPLEXLIST_H__
#define __COMPLEXLIST_H__ 

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>


typedef  int DataType;

typedef struct complexnode
{
    DataType _data;
    struct complexnode* _next;
    struct complexnode* _random;
}complexnode;


complexnode* Buycomplexnode(DataType x);//建立一個結點

void display(complexnode* head);//列印連結清單

complexnode* copycomplexnode(complexnode* head);//複制連結清單

void destroylist(complexnode* head);//銷毀連結清單

#endif
           

程式實作檔案：

#include "complexlist.h"


complexnode* Buycomplexnode(DataType x)
{
    complexnode*  newnode = NULL;
    newnode = (complexnode*)malloc(sizeof(complexnode));
    if(newnode == NULL)
    {
        perror("complexnode()::malloc");
        return NULL;
    }
    newnode->_data = x;
    newnode->_next = NULL;
    newnode->_random = NULL;
    return newnode;
}

void display(complexnode* head)
{
    complexnode* cur = head;
    while(cur)
    {
        printf("%d-%d-->",cur->_data,cur->_random->_data);
        cur = cur->_next;
    }
    printf("NULL\n");
}


complexnode* copycomplexnode(complexnode* head)
{
    complexnode* cur = head;
    complexnode* copy =NULL;
    complexnode* prev = NULL;
    complexnode* random = NULL;
    complexnode* newhead = NULL;
    //在原有連結清單的結點之後插入結點
    while(cur)
    {
        complexnode* ptr = Buycomplexnode(cur->_data);
        prev = cur;
        cur = cur->_next;
        ptr->_next = cur;
        prev->_next = ptr;
    }   
    //将原有連結清單的random關系賦給将要複制的連結清單
    cur = head;
    while(cur)
    {
        random = cur->_random;
        copy = cur->_next;
        copy->_random = random->_next;
        cur = cur->_next->_next;
    }
    //将複制完的連結清單拆分，形成兩條連結清單
    cur = head;
    newhead = cur->_next;
    copy = cur->_next;
    while(cur)
    {
        cur->_next = copy->_next;
        cur = cur->_next;
        if(cur != NULL)
        {
            copy->_next = cur->_next;
            copy = copy->_next;
        }
    }
    return newhead;
}

void destroylist(complexnode* head)
{
    complexnode* cur = head;
    while(cur)
    {
        complexnode* del = cur;
        cur = cur->_next;
        free(del);
    }
    free(cur);
    head = NULL;
}
           

測試檔案：

#include "complexlist.h"

void test()
{
    complexnode* head;
    complexnode* newhead;
    complexnode* node1 = Buycomplexnode();
    complexnode* node2 = Buycomplexnode();
    complexnode* node3 = Buycomplexnode();
    complexnode* node4 = Buycomplexnode();
    complexnode* node5 = Buycomplexnode();
    node1->_next = node2;
    node2->_next = node3;
    node3->_next = node4;
    node4->_next = node5;
    node1->_random = node3;
    node2->_random = node4;
    node3->_random = node5;
    node4->_random = node1;
    node5->_random = node2;
    //構造複雜連結清單
    head = node1;
    display(head);//列印連結清單
    newhead = copycomplexnode(head);//複制複雜連結清單
    display(newhead);
    destroylist(head);//銷毀連結清單
    destroylist(newhead);//銷毀連結清單
}

int main()
{
    test();
    return ;
}
           

到此，複雜連結清單的複制完成。