데이터 구조의 복잡 한 링크 복사

데이터 구조의 복잡 한 링크 복사
1. 복잡 한 링크 는 무엇 입 니까?
복잡 한 링크 란 링크 의 모든 노드 를 말 합 니 다. 하 나 는 next 포인터 가 다음 노드 를 가리 키 고 다른 random 포인터 가 이 링크 의 무 작위 노드 나 NULL 을 가리 키 는 것 을 말 합 니 다.
무슨 뜻 이 죠?우리 그림 보고 얘 기 하 자.
그림 과 같이 모든 결점 은 next 포인터 로 다음 결점 을 가리 키 는 동시에 random 포인터 로 임의의 결점 을 가리 키 고 있 습 니 다. 여기 있 는 random 포인터 의 가리 키 는 방향 은 마음대로 되 며 모든 결점 (NULL 포함) 을 가리 킬 수 있 습 니 다.
2. 어떻게 복사 하나 요?
그러면 우 리 는 어떻게 이런 체인 시 계 를 복제 합 니까?많은 사람들의 첫 반응 은 각 노드 의 random 포인터 가 가리 키 는 정 보 를 기록 한 다음 에 기 록 된 정보 에 따라 복사 하 는 것 이다.이것 은 문제 가 있 을 것 이다. 링크 를 복사 하 는 것 이 라면 복 제 된 링크 의 모든 노드 는 새로 개 발 된 것 이 고 자신의 공간 이 있다. 이 공간 은 원래 링크 에 해당 하 는 노드 의 공간 이 아 닐 것 이다.우 리 는 어떻게 random 포인터 가 가리 키 는 새로운 공간의 주 소 를 찾 습 니까?한 가지 방법 이 있 습 니 다. N * N 의 배열 을 열 어 원 링크 의 모든 노드 간 의 관 계 를 저장 합 니 다.그러나 이런 방법의 시간 과 공간 비용 은 매우 크다.
복잡 한 링크 복사 방안 을 제공 합 니 다.모두 3 단계 로 나 뉜 다. 1. 원 링크 의 모든 노드 에 값 이 같은 새로운 노드 를 삽입 합 니 다. 2. 새로운 노드 를 삽입 하 는 랜 덤 포인터 도 메 인 에 값 을 부여 합 니 다. 3. 새로운 노드 를 원래 표 에서 다시 떼 어 냅 니 다.
첫 번 째 단계: 원본 링크 의 모든 노드 에 같은 값 의 새로운 노드 를 삽입 합 니 다.
두 번 째 단계: 결점 을 새로 삽입 한 무 작위 포인터 영역 에 값 을 부여 합 니 다.값 이 1 인 결점 을 예 로 들 면 결점 기 는 p 이 고 p 결점 에서 복 사 된 결점 기 는 pC 이다.핵심 코드 는: pC -> random = p -> random -> next;주의해 야 할 점 은 결점 의 random 포인터 가 NULL 을 가리 킬 때 이 결점 에서 복 사 된 결점 의 random 지침 을 NULL 로 직접 설정 하 는 것 이다.
세 번 째 단계: 새로운 결점 을 원래 표 에서 다시 떼 어 낸다.값 이 1 인 결점 을 예 로 들 면 결점 기 는 p 이 고 p 결점 에서 복 사 된 결점 기 는 pC 이다.핵심 코드 는 p -> next = pC -> next 입 니 다.pC->next = p->next->next;
최종 효 과 는 링크 길이 가 n 이 라 고 가정 하면 전체적인 시간 복잡 도 는 O (n) 이 고 공간 복잡 도 는 O (1) 이다.

typedef struct PNode{
    DataType data;
    struct PNode *next;
    struct PNode *random;
}*PNode, Node;

PNode AddNode(DataType data)        //    
{
    PNode p = (PNode)malloc(sizeof(Node));
    if (p != NULL)
    {
        p->data = data;
        p->next = NULL;
        p->random = NULL;
        return p;
    }
    assert(p);
    return NULL;
}

PNode CopyComplexList(PNode pHead)   //       
{
    PNode pHead2 = NULL;
    PNode pNext = NULL; //        
    PNode pCur = NULL;  //             
    if (pHead == NULL)
    {
        return NULL;
    }

//                   
    pCur = pHead;
    pNext = pHead->next;    
    while(pNext)
    {
        pCur->next = AddNode(pCur->data);   //               
        pCur->next->next = pNext;           //      next  ，                 
        pCur = pNext;                       //  pCur  
        pNext = pNext->next;                //  pNext  
    }
    pCur->next = AddNode(pCur->data);       //        ， next NULL。     
    pCur->next->next = pNext;

//              
    pCur = pHead;
    pNext = pHead->next;
    while(pNext->next)  //       n-1    random    
    {
        if (pCur->random == NULL)
        {
            pNext->random = NULL;
        }
        else
        {
            pNext->random = pCur->random->next;
            pCur = pNext->next;
            pNext = pCur->next;
        }    
    }
    if (pCur->random == NULL)   //       ，    
        pNext->random = NULL;
    else
        pNext->random = pCur->random->next;

//              
    pCur = pHead;
    pNext = pHead->next;
    pHead2 = pHead->next;
    while(pNext->next)  //       n-1      
    {
        pCur->next = pNext->next;
        pNext->next = pCur->next->next;
        pCur = pCur->next;
        pNext = pNext->next;
    }
     pCur->next = pNext->next;  //          

     return pHead2;
}