Tree & SmartPtr
没有命名冲突后,考虑是否要去掉库前缀.
本来想重写泛化N叉树，再派生出泛化二叉树.考虑到效率而且常用性,暂时不重写N叉树.
:第一季tree实现的更改版本
/**//* tree.h :base::adt::tree */
#ifndef TREE__
#define TREE__
#include "base.h"
#include "ptr.h"
namespace adt
{
using code::ptr;
template<typename VType>
class tree:/**//* Adt:Generalization binary tree */public base::adt
{
private:
int i;
typedef struct VNode
{
private:
int empty(ptr<VNode>& tree_)
{
if(tree_.isNull())
return 1;
empty(tree_().lChild);
empty(tree_().rChild);
tree_.free();
return 1;
}
public:
VType elem;
ptr<VNode> lChild;
ptr<VNode> rChild;
ptr<VNode> parent;
int extend_lChild(ptr<VNode>& lChild_=0)
{
if(lChild_.isNull())
{
lChild=new VType;
}
else
{
lChild=lChild_;
}
lChild().parent=this;
return 1;
}
int extend_rChild(ptr<VNode>& rChild_=0)
{
if(rChild_.isNull())
{
rChild=new VType;
}
else
{
rChild=rChild_;
}
rChild().parent=this;
return 1;
}
int set_value(VType& value_)
{
elem=value_;
return 1;
}
int empty_lTree()
{
empty(lChild());
return 1;
}
int empty_rTree()
{
empty(rChild());
return 1;
}
};
public:
ptr<VNode>/**//*tree root.*/ root;
int/**//*node number*/ n;
ptr<VNode> /**//* op position */pos;
tree()
{
root=new VNode;
n=1;
pos=root;
}
tree(tree & tree_)
{
*this=tree_;
}
virtual ~tree()
{
;
}
int copyFrom_(ptr<VNode> & subTree_,ptr<VNode> & newTree)
{
if(subTree_.isNull())
return 0;
if(newTree.isNull())
newTree=new VNode;
newTree().set_value(subTree_().elem);
copyFrom_(subTree_().lChild,newTree().lChild);
copyFrom_(subTree_().rChild,newTree().rChild);
return 1;
}
int operator = (tree & tree_)
{
copyFrom_(tree_.root,root);
n=tree_.n;
pos=tree_.pos;
return 1;
}
int set(VType value_)
{
pos().set_value(value_);
return 1;
}
int setLeft(VType value_)
{
if(pos().lChild.isNull()){
pos().lChild=new VNode;
++n;
}
pos().lChild().set_value(value_);
return 1;
}
int setRight(VType value_)
{
if(pos().rChild.isNull()){
pos().rChild=new VNode;
++n;
}
pos().rChild().set_value(value_);
return 1;
}
int goLeft()
{
if(pos().lChild.isNull()){
pos().lChild=new VNode;
++n;
}
pos=pos().lChild;
return 1;
}
int goLeft(VType value_)
{
goLeft();
pos().set_value(value_);
return 1;
}
int goRight()
{
if(pos().rChild.isNull()){
pos().rChild=new VNode;
++n;
}
pos=pos().rChild;
return 1;
}
int goRight(VType value_)
{
goRight();
pos().set_value(value_);
return 1;
}
int goParent()
{
if(pos().parent.isNull()){
pos().parent=new VNode;
++n;
}
pos=pos().parent;
return 1;
}
int goParent(VType value_)
{
goParent();
pos().set_value(value_);
return 1;
}
int go(int i,VType value_)
{
if(i==0)
{
goLeft(value_);
}else if(i==1)
{
goRight(value_);
}else if(i==2)
{
goParent(value_);
}
return 1;
}
int go(int i)
{
if(i==0)
{
goLeft();
}else if(i==1)
{
goRight();
}else if(i==2)
{
goParent();
}
}
int preOrder(ptr<VNode> &subTree_,VType * list)
{
if(subTree_.isNull())
return 1;
static int i=0;
list[i]=subTree_().elem;
++i;
preOrder(subTree_().lChild,list);
preOrder(subTree_().rChild,list);
return 1;
}
int inOrder(ptr<VNode> &subTree_,VType * list)
{
if(subTree_.isNull())
return 1;
inOrder(subTree_().lChild,list);
list[i]=subTree_().elem;
++i;
inOrder(subTree_().rChild,list);
return 1;
}
int postOrder(ptr<VNode> &subTree_,VType * list)
{
if(subTree_.isNull())
return 1;
postOrder(subTree_().lChild,list);
postOrder(subTree_().rChild,list);
list[i]=subTree_().elem;
++i;
return 1;
}
int travel(VType* list,int select=0)
{
i=0;
if(select==0)
preOrder(root,list);
else if(select==1)
inOrder(root,list);
else if(select==2)
postOrder(root,list);
return 1;
}
};
}
#endif
ptr<VType> 的用法:
ptr<Type> pValue = new Type[5];
set(pValue[1]);
pValue().rebirth();//第一个()用于暂时解开智能指针外壳.
SmartPtr的实现:
0 同时支持数组及单指针的功能.
1 当要调用智能指针内实体类型的方法时,可以用重载的 ( ) 直接 返回指针的值,方便调用方法.如果是数组,则用[ ].
2 引用计数,不会出现挂空.
3 删除了之前智能指针可以指向常量地址并且自动检(提高速度
/**//* ptr.h :base::code::ptr */
#ifndef PTR__
#define PTR__
#pragma warning (disable: 4244)
#include "base.h"
#ifdef PTR__CONST__
#include "runtime.h"
#endif
namespace code
{
template<typename VType,int VType_=0>
class ptr:public base::code
{
private:
VType * obj;
int *refCount;
public:
ptr()
{
obj=0;
refCount=0;
}
ptr(VType * _obj)
{
if(_obj)
{
refCount=new int(1);
obj=_obj;
}else
{
obj=0;
refCount=0;
}
}
ptr( ptr<VType> * _ptr)
{
if(_ptr.isNull())
{
obj=0;
refCount=0;
return;
}else
{
obj=_ptr.obj;
refCount=_ptr.refCount;
up();
}
}
void reset()
{
if(obj&&refCount)
*refCount=0;
}
void up()
{
if(obj&&refCount)
++*refCount;
}
void down()
{
if(obj&&refCount)
{
--*refCount;
if(*refCount==0)
{
delete obj;
delete refCount;
}
obj=0;
refCount=0;
}
}
VType *const adr()
{
return obj;
}
VType& operator () ()
{
if(!refCount)
{
#ifdef TEST_OPEN
TEST_THROW("Exception in ptr.h ptr:operator () function.")
#endif
}
return *obj;
}
VType& operator [](int i)
{
return obj[i];
}
ptr& operator = ( ptr<VType> * _ptr)
{
if(obj==_ptr.obj)return;
down();
if(!_ptr.isNull())
{
obj=_ptr.obj;
refCount=_ptr.refCount;
up();
}
return *this;
}
ptr& operator = ( VType * _ptr)
{
if(obj==_ptr)return *this;
down();
if(_ptr)
{
obj=_ptr;
refCount=new int(1);
}
return *this;
}
ptr& operator = ( VType elem)
{
down();
obj=new VType(elem);
refCount=new int(1);
return *this;
}
int isNull()
{
if(!obj)
return 1;
else
return 0;
}
~ptr()
{
down();
}
};
}
#endif
另一个case:
string buf[20];
using namespace adt;
using code::ptr;
ptr<tree<string>,1> natGramList=new tree<string>[3];
natGramList[0].set("[Expression]");
natGramList[0].setLeft("[LeftExpression]");
natGramList[0].setRight("[Op]");
natGramList[0].goLeft();
natGramList[0].setLeft("[LeftExpression]");
natGramList[0].setRight("[Right]");
natGramList[1].set("+");
natGramList[1].setLeft("1");
natGramList[1].setRight("2");
natGramList[0].travel(buf,1);//参数0,1,2代表前序，中序，后序遍历
for(int i=0;i!=natGramList[0].n;i++)
cout<<buf[i];
cout<<endl;
natGramList[1].travel(&buf[10],1);
for(int i=0;i!=natGramList[1].n;i++)
cout<<buf[i+10];
cout<<endl;
暂时保留智能指针与指针数组的兼容.