c 語言 復雜鏈表的復制

c 語言 復雜鏈表的復制

//頭文件
#pragma once
typedef int DataType;
 
typedef struct ComplexNode
{
    DataType     _data;                // 數據
    struct ComplexNode* _next;        // 指向下一個節點的指針
    struct ComplexNode* _random;  // 指向隨機節點
}ComplexNode,*pComplexNode;
 
void BuyNode(pComplexNode& pNode,DataType x);
void PushBack(pComplexNode& pHead,DataType x);
void CopyCplexList(pComplexNode pHead,pComplexNode& NewpHead);
pComplexNode Find(pComplexNode pHead, DataType Data);
void PrintLinkList(pComplexNode pHead);
//函數文件
#include<stdio.h>
#include"ComplexList.h"
#include<assert.h>
#include<malloc.h>
 
//創建節點
void BuyNode(pComplexNode& pNode, DataType x)
{
    pNode = (pComplexNode)malloc(sizeof(ComplexNode));
    pNode->_data = x;
    pNode->_next = NULL;
    pNode->_random = NULL;
}
//頭插
void PushBack(pComplexNode& pHead,DataType x)
{
    pComplexNode tmp = pHead;
    if (pHead == NULL)
    {
        BuyNode(pHead, x);
        return;
    }
    while (tmp->_next != NULL)
    {
        tmp = tmp->_next;
    }
    BuyNode(tmp->_next, x);
}
//復雜鏈表復制
void CopyCplexList(pComplexNode pHead, pComplexNode& NewpHead)
{
    pComplexNode tmp = pHead;
    pComplexNode head = pHead;
    if (pHead == NULL)
        return;
    while (head != NULL)
    {
        tmp = head->_next;
        BuyNode(NewpHead, head->_data);
        head->_next = NewpHead;
        NewpHead->_next = tmp;
        head = tmp;      
    }
    head = pHead;
    while (head != NULL)
    {
        tmp = head->_next;
        if (head->_random == NULL)
            tmp->_random == NULL;
        else
            tmp->_random = head->_random->_next;
        head = head->_next->_next;
    }
    head = pHead;
    NewpHead = head->_next;
    while (head!=NULL)
    {
        tmp = head->_next;
        head->_next = tmp->_next;
        head = tmp->_next;
        if (head == NULL)
            return;
        tmp->_next = head->_next;
    }
}
//查找
pComplexNode Find(pComplexNode pHead, DataType Data)
{
    pComplexNode tmp = pHead;
    assert(pHead);
    while (tmp)
    {
        if (tmp->_data == Data)
            return tmp;
        tmp = tmp->_next;
 
    }
    return NULL;
}
//輸出
void PrintLinkList(pComplexNode pHead)
{
    pComplexNode tmp = pHead;
    if (pHead == NULL)
    {
        printf("鏈表為空！\n");
    }
    while (tmp)
    {
        printf("%d ", tmp->_data);
        tmp = tmp->_next;
    }
    printf("\n");
}
//測試用例 主函數
#include<stdio.h>
#include"ComplexList.h"
 
void test1()
{
    pComplexNode pHead=NULL,NewpHead=NULL;
    PushBack(pHead, 1);
    PushBack(pHead, 2);
    PushBack(pHead, 3);
    PushBack(pHead, 4);
    PrintLinkList( pHead);
    Find(pHead, 1)->_random = Find(pHead, 3);
    Find(pHead, 2)->_random = Find(pHead, 4);
    Find(pHead, 3)->_random = Find(pHead, 2);
    Find(pHead, 4)->_random = Find(pHead, 1);
    CopyCplexList(pHead, NewpHead);
    PrintLinkList(NewpHead);
}
 
int main()
{
    test1();
    return 0;
}