clone模式在平衡排序二叉树实现中的应用

来源： 互联网 作者： rocket   2008-03-18/13:28

软件频道 编程学院 C/C++/VC 精华文摘 正文

• 实现
• 应用
• 排序
• 平衡
• 模式
• clone
• 复制
• 组件
• 一个

clone模式既prototype模式,是构造模式中的一种。其意图为:用原型实例指定创建对象的种类,并且通过拷贝这些原型创建新的对象。

关键代码如下:

virtual product * prototype::clone(){

	return new prototype(this->datas);

}

virtual product * concreteprototype_1::clone(){

	//return copy of self

	return new concreteprototype_1(this->datas);

}

virtual product * concreteprototype_2::clone(){

	//return copy of self

	return new concreteprototype_2(this->datas);

}

有Java经验的会在Object中看到clone方法。

clone模式有两个问题:
(一)内存泄漏,在clone函数中新建了一个对象,如果没有在外部接收它,它就不会自己释放自己。
(二)clone一个组件,如组合模式(composite)产生的抽象对象。
第一个问题的解决方案为智能指针,有很多文献介绍过这类问题。
这里讨论如何用clone模式clone一个组件。

virtual component * component::clone(){

	component * pnew = new component(this->datas);

	for(all components of this object (this->o)){

		if(this->o != NULL)

		//复制本组件中的每一个元件

		pnew->o = this->o->clone();

	}

	return pnew;

}

譬如一个链表结点类:

class Node{

private:

	DataType datas;

	Node *   next;

public:

	virtual Node* clone(){

		Node* pnew=new Node(this->datas);

		if(this->next != NULL)pnew->next = this->next->clone();

		return pnew;

	}

	//other codes

}

这样复制一个结点与复制一个链表统一起来了,不是很好吗?大功告成。
但是不要高兴太早,现在有一个链表,是循环链表(单向),试用上面方法复制它。 你将会进入死循环,最后内存耗竭而报错.
最后一个结点的下一个为头结点,应该将其后向指针指向新建的头结点,而不是再生成一个结点。
即将上面代码改为:

...

for(all components of this object (this->o)){

	if(this->o ==NULL){

		pnew->o=NULL;

	}else if(this->o 未被复制){

		//复制本组件中的每一个元件

		pnew->o = this->o->clone();

	}else{

		pnew->o = this->o 的复制品;

	}

	return  pnew;

}

为判断组件 o 是否已经被复制应该在组件 o 中加一个标志cloned,cloned为真表示已经被复制。 为找到组件 o 的复制品应该在组件 o 中保存复制品的地址 pclone。

this->cloned=true;

this->pclone=pnew;

...

if(this->o == NULL)

	pnew->o=NULL;

}else if(this->o->cloned==false){

	//复制本组件中的每一个元件

	pnew->o = this->o->clone();

}else{

	pnew->o = this->o->pclone;

}

注意,执行一次clone操作后必须将cloned置false.
当然还有其它方法表示是否已经复制.

class Node{

	static  int Cloned=0;

	int     cloned=0;

	...

	virtual Node * clone(){

		...

		if(cloned==Cloned){

			//已经复制		

			...

		}else{

			//未复制

			...

		}

		...

	}

public:

	Node * clone_for_call(){

		Cloned++;

		return clone();

	}

	...

}

如果Cloned不溢出,就有对每个结点node,node.cloned<=Cloned(已经复制时取等号)。