开发学院软件开发VC clone模式在平衡排序二叉树实现中的应用 阅读

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

 2007-03-16 21:56:35 来源:WEB开发网   
核心提示:本文示例源代码或素材下载 clone模式既prototype模式,是构造模式中的一种,其意图为:用原型实例指定创建对象的种类,并且通过拷贝这些原型创建新的对象,clone模式在平衡排序二叉树实现中的应用,关键代码如下:virtual product * prototype::clone(){return new

本文示例源代码或素材下载

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(已经复制时取等号)。

Tags:clone 模式 平衡

编辑录入:爽爽 [复制链接] [打 印]
[]
  • 好
  • 好的评价 如果觉得好,就请您
      0%(0)
  • 差
  • 差的评价 如果觉得差,就请您
      0%(0)
更多精彩
    赞助商链接

    热点阅读
      焦点图片
        最新推荐
          精彩阅读