【データ構造】複雑なチェーンのコピー

2107 ワード

スペース include データ構造

複雑なチェーンのコピーを実現します.
    複雑なチェーンテーブルには各ノードが任意のノードを指すポインタを持っているからです.このチェーンのコピーを確認する時に.私たちは時間の効率と引き換えに空間を作る必要があります.その後、チェーンテーブルのコピー項目を分割に結合することができます.
    考え方はこのようにします
    直接コードを与えます.

#pragma once
#include 
#include 
#include 

typedef int DataType;

typedef struct ComplexNode
{
	DataType	 _data;				//   
	struct ComplexNode* _next;		//           
	struct ComplexNode* _random;	//       
}ComplexNode;

void creatComplexNode(ComplexNode* &pHead,DataType x);
ComplexNode* CopyComplexNode(ComplexNode* pHead);
//      。
void creatComplexNode(ComplexNode* &pHead,DataType x)
{
	ComplexNode *ret,*endNode;
	if(pHead == NULL)
	{
		pHead = (ComplexNode*)malloc(sizeof(ComplexNode));
		pHead->_random = NULL;
		pHead->_data = x;
		pHead->_next = NULL;
		return;
	}
	endNode = pHead;
	ret = endNode;
	while(endNode->_next)
	{
		ret = endNode;
		endNode = endNode->_next;
	}
	endNode->_next = (ComplexNode*)malloc(sizeof(ComplexNode));
	endNode = endNode->_next;
	endNode->_next = NULL;
	endNode->_data = x;
	endNode->_random = ret;
}

//         。          3   ：
//  。
//       。
//  。
ComplexNode *CopyComplexNode(ComplexNode *pHead)
{
	ComplexNode *copyNode;
	ComplexNode *pNode = pHead;
	ComplexNode *newLink = NULL;
	ComplexNode *newNode = NULL;
	assert(pHead);
	while(pNode != NULL)
	{
		copyNode = (ComplexNode*)malloc(sizeof(ComplexNode));
		copyNode->_data = pNode->_data;
		copyNode->_next = pNode->_next;
		copyNode->_random = NULL;

		pNode->_next = copyNode;
		
		pNode = copyNode->_next;
	}

	pNode = pHead;

	while(pNode != NULL)
	{
		copyNode = pNode->_next;
		if(pNode->_random != NULL)
		{
			copyNode->_random = pNode->_random->_next;
		}
		pNode = copyNode->_next;
	}

	pNode = pHead;
	newLink = pNode->_next;
	while(pNode != NULL)
	{
		newNode = pNode->_next;
		pNode->_next = newNode->_next;
		pNode = pNode->_next;
		if(newNode->_next != NULL)
			newNode->_next = pNode->_next;
	}
	return newLink;
}

簡易計算機プログラム