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(已經復制時取等號)。

本文配套源碼