`
wpf814533631
  • 浏览: 191943 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

(转)EssentialC++ 以template进行编程

 
阅读更多

这一章通过讲解二叉树的template的实现过程，来讲解template的语法，以及一些需要注意的地方。

首先了解一下二叉树的一些基本操作，二叉树支持插入，删除，遍历的操作。第一个安插至空白树的值，会成为此树的根节点。接下来的每个节点按特定的规则插入。如果小于根节点，就被置于左侧指数，大于根节点就被置于右子树。string类型按照字典排序。如下图

 

 

遍历又分前序遍历，中序遍历，后序遍历。

 

按照上图，前序遍历结果： Piglet,Ek,Chris,Kanga,Roo,Pooh,Trigger. 

 

中序遍历结果：Chris Ek Kanga Piglet   Pooh Roo Trigger

 

后序遍历结果：Chris Kanga Ek Pooh Trigger Roo Piglet

 

下面先实现一个节点类型BTnode。如果不实现泛型，

 

 

 

[cpp] view plaincopyprint?
  1. class string_node {  
  2. public:  
  3.   
  4. private:  
  5.     string _val;   //节点的值  
  6.     int _cnt;      //节点计数  
  7.     string_node *_lchild;    //左节点  
  8.     string_node *_rchild;    //右节点  
  9.   
  10. };  

 

如果要实现存储int类型的节点则又要定义一个int_node类。这显然太麻烦。我们可以定义一个支持泛型的节点。

 

[cpp] view plaincopyprint?
  1. template<typename valType>  
  2. class BTnode {  
  3.     friend class BinaryTree<valType>;    //把二叉树类型BinaryTree声明为友元类，这样BinaryTree就可以访问BTnode的私有成员 _val,_cnt,_lchild,_rchild等  
  4. public:  
  5.     BTnode(){}  
  6.     BTnode(const valType &val);  
  7.     void insert_value(const valType& elem);  
  8.     void remove_value( const valType &val, BTnode *& prev);  
  9.     static void lchild_leaf( BTnode *leaf, BTnode *subtree);  
  10. private:  
  11.     valType _val;  
  12.     int     _cnt;  
  13.     BTnode *_lchild;  
  14.     BTnode *_rchild;  
  15. };  

 

为了通过class template产生实体类，我们必须在class tempalte名称之后，紧接一个尖括号，其内放置一个实际类。例如:BTnode<int> 则将valType绑定至int， BTnode<string>则讲valType绑定至string。这样我们就实现了泛型。没有必要再为

 

每个类型都定义一个节点类型了。什么情况下我们需要 模板参数列表(template parameter list)去修饰 模板类(class template）呢。 一般的规则是，在class template 以及其members的定义式中，不需要之外。其他的场合都需要以parameter list 加以修饰。如：

 

[cpp] view plaincopyprint?
  1. template<typename elemType>  
  2. class BinaryTree {  
  3. public:  
  4. ...  
  5. private:  
  6.     BTnode<strong><elemType></strong> *_root;  
  7. };  
[cpp] view plaincopyprint?
  1.   

下面给出BTnode完整的定义：

[cpp] view plaincopyprint?
  1. template<typename Type>  
  2. class BinaryTree;  
  3.   
  4. template<typename valType>  
  5. class BTnode {  
  6.     friend class BinaryTree<valType>;  
  7. public:  
  8.     BTnode(){}  
  9.     BTnode(const valType &val);  
  10.     void insert_value(const valType& elem);  
  11.     void remove_value( const valType &val, BTnode *& prev);  
  12.     static void lchild_leaf( BTnode *leaf, BTnode *subtree);  
  13. private:  
  14.     valType _val;  
  15.     int     _cnt;  
  16.     BTnode *_lchild;  
  17.     BTnode *_rchild;  
  18. };  
  19.   
  20. template<typename valType>  
  21. BTnode<valType>::BTnode(const valType &val)  
  22.         : _val(val)  
  23. {  
  24.     _cnt = 1;  
  25.     _lchild = _rchild = 0;  
  26. }  
  27.   
  28. template<typename valType>  
  29. void BTnode<valType>::insert_value(const valType &val) {  
  30.     if ( this->_val == val) {  
  31.         this->_cnt++;           
  32.         return ;  
  33.     }  
  34.   
  35.     if(this->_val > val ) {  
  36.         if(!this->_lchild)  
  37.             this->_lchild = new BTnode<valType>(val);  
  38.         else  
  39.             this->_lchild->insert_value(val);  
  40.     } else {  
  41.         if(!this->_rchild)  
  42.             this->_rchild = new BTnode<valType>(val);  
  43.         else  
  44.             this->_rchild->insert_value(val);  
  45.     }  
  46.   
  47. }  
  48.   
  49. template<typename valType>  
  50. void BTnode<valType>::remove_value( const valType &val, BTnode *& prev) {     
  51.  //找到相应的值，删除该节点。prev是起始的节点。 这里需要修改BTnode *指针本身，所以我们定义为 BTnode *& prev  
  52.   
  53.     if( val < _val ) {  
  54.         if ( !_lchild)  
  55.             return;  
  56.         else  
  57.             _lchild->remove_value(val, _lchild);  
  58.     }  
  59.     else if ( val > _val) {  
  60.         if( !_rchild)  
  61.             return;  
  62.         else  
  63.             _rchild->remove_value(val,_rchild);  
  64.     }  
  65.     else {  
  66.         if (_rchild) {  
  67.             prev = _rchild;  
  68.             if(_lchild)  
  69.                 if( !prev->_lchild)  
  70.                     prev->_lchild = _lchild;  
  71.                 else  
  72.                     BTnode<valType>::lchild_leaf(_lchild,prev->_lchild);  
  73.         }  
  74.         else  
  75.             prev = _lchild;  
  76.         delete this;  
  77.     }  
  78.   
  79. }  
  80.   
  81. template<typename valType>  
  82. inline void BTnode<valType>::lchild_leaf( BTnode *leaf, BTnode *subtree) {  
  83. //使leaf成为subtree的左子树的叶子节点  
  84.     while (subtree->_lchild)  
  85.         subtree = subtree->_lchild;  
  86.     subtree->_lchild = leaf;  
  87. }  

 

[cpp] view plaincopyprint?
  1. template<typename valType>  
  2. BTnode<valType>::BTnode(const valType &val)  
  3.         : _val(val)  
  4. {  
  5.     _cnt = 1;  
  6.     _lchild = _rchild = 0;  
  7. }  

为 什么这里第二次出现BTnode的时候不需要<valType>去修饰了呢，因为在class scope运算符出现之后 BTnode<valType>::，其后所有东西被视为位于class定义域内：还记得上面所说的规则吗在class template 以及其members的定义式中，不需要之外。其他的场合都需要以parameter list 加以修饰。

BTnode<valType>::  //在class定义域之外。

 

BTnode()    //在class定义域之内。

 

关于函数参数的规则是，若是非基本类型，则使用传址的方式(by reference)传递 ，如果这个参数确认了，在函数内是只读的则加上const 修饰词。如：

 

[cpp] view plaincopyprint?
  1. insert_value(const valType &val)  

 

下面给出BinaryTree的模板实现：

 

[cpp] view plaincopyprint?
  1. template<typename elemType>  
  2. class BinaryTree {  
  3. public:  
  4.     BinaryTree();  
  5.     BinaryTree(const BinaryTree&);  
  6.     ~BinaryTree();  
  7.     BinaryTree& operator= (const BinaryTree&);  
  8.   
  9.     void insert( const elemType &);  
  10.     bool empty() { return _root == 0;}  
  11.     void remove(const elemType &elem);  
  12.     void remove_root();  
  13.   
  14.     void clear() { if(_root) { clear(_root); _root = 0;}}  
  15.     void preorder();  
  16.     void preorder(BTnode<elemType> *node, ostream &os = cout);  
  17.     static ostream & display_val( elemType &node,ostream &os = cout);  
  18.     void pre_recursion(BTnode<elemType> *node);  
  19.     BTnode<elemType>* get_root() { return _root;}  
  20. private:  
  21.     BTnode<elemType> *_root;  
  22.     void clear(BTnode<elemType> *node);  
  23.     void copy(BTnode<elemType> *tar, BTnode<elemType> *src);  
  24. };  
  25.   
  26. template<typename elemType>  
  27. inline BinaryTree<elemType>::  
  28. BinaryTree() : _root(0) {}  
  29.   
  30. template<typename elemType>  
  31. inline BinaryTree<elemType>::BinaryTree(const BinaryTree& rhs) {  
  32.     copy(_root,rhs._root);  
  33. }  
  34.   
  35. template<typename elemType>  
  36. void BinaryTree<elemType>::insert( const elemType &elem) {  
  37.     if (!_root)  
  38.         _root = new BTnode<elemType>(elem);  
  39.     _root->insert_value(elem);  
  40. }  
  41.   
  42. template<typename elemType>  
  43. inline BinaryTree<elemType>::~BinaryTree() {  
  44.     clear();  
  45. }  
  46.   
  47. template<typename elemType>  
  48. inline BinaryTree<elemType>&  
  49. BinaryTree<elemType>::operator= (const BinaryTree &rhs) {  
  50.     if( ! this = &rhs) {  
  51.         clear();  
  52.         copy(_root,rhs._root);  
  53.     }  
  54.     return *this;  
  55. }  
  56.   
  57. template<typename elemType>  
  58. inline void BinaryTree<elemType>::remove( const elemType &elem) {  
  59.     if(_root) {  
  60.         if( _root->_val == elem)  
  61.             remove_root();  
  62.         else  
  63.             _root->remove_value(elem, _root);  
  64.     }  
  65. }  
  66.   
  67. template<typename elemType>  
  68. void BinaryTree<elemType>::  
  69. remove_root() {  
  70.     if (!_root) return;  
  71.   
  72.     BTnode<elemType> *tmp = _root;  
  73.   
  74.     if( !_root->_rchild) {  
  75.         _root = _root->_rchild;  
  76.         if(tmp->_lchild) {  
  77.             if(!_root->_lchild)  
  78.             //没有任何子树则直接接上  
  79.                 _root->_lchild = tmp->_lchild;  
  80.             else  
  81.                 BTnode<elemType>::lchild_leaf(tmp->_lchild,_root->_lchild);  
  82.         }  
  83.   
  84.     }  
  85.     else  
  86.         _root = _root->_lchild;  
  87.     delete tmp;  
  88. }  
  89. //清除所有节点  
  90. template<typename elemType>  
  91. void BinaryTree<elemType>::clear(BTnode<elemType> *node) {  
  92.     if(node) {  
  93.         clear(node->_lchild);  
  94.         clear(node->_rchild);  
  95.         delete node;  
  96.     }  
  97. }  
  98.   
  99. template<typename elemType>  
  100. void BinaryTree<elemType>::preorder() {  
  101.     pre_recursion(_root);  
  102. }  
  103.   
  104. //递归的前序遍历  
  105. template<typename elemType>  
  106. void BinaryTree<elemType>::preorder(BTnode<elemType> *node, ostream &os) {  
  107.   
  108.     if(node) {  
  109.         display_val(node->_val,os);  
  110.         preorder(node->_lchild,os);  
  111.         preorder(node->_rchild,os);  
  112.     }  
  113. }  
  114.   
  115. template<typename elemType>  
  116. ostream & BinaryTree<elemType>::display_val(elemType &node , ostream &os) {  
  117.     os << node << ' ';  
  118.     return os;  
  119. }  
  120.   
  121. //非递归实现前序遍历  
  122. template<typename elemType>  
  123. void BinaryTree<elemType>::pre_recursion (BTnode<elemType> *node) {  
  124.     stack<BTnode<elemType>*> s;   //使用先进后出栈  
  125.     s.push(node);  
  126.     while(!s.empty()) {  
  127.         BTnode<elemType>* tmp = s.top();  
  128.         s.pop();  
  129.         BinaryTree<elemType>::display_val(tmp->_val,std::cout);  
  130.         if(tmp->_rchild)  
  131.             s.push(tmp->_rchild);    //右节点先进栈 后出，后遍历  
  132.         if(tmp->_lchild)  
  133.             s.push(tmp->_lchild);    //左节点后进栈，先出，先遍历  
  134.     }  
  135. }  

 

测试：

 

[cpp] view plaincopyprint?
  1. int main()  
  2. {  
  3.     BinaryTree<string> bt;  
  4.     bt.insert("abc");  
  5.     bt.insert("agcb");  
  6.     bt.insert("kfgd");  
  7.     bt.insert("how are you");  
  8.     bt.preorder();  
  9.     //bt.remove("abc");  
  10.     //bt.preorder();  
  11.     bt.remove("kfgd");  
  12.     bt.preorder();  
  13.     return 0;  
  14. }  

本章不仅让我了解泛型编程，模板类是怎么一回事，template的语法。而且还让我重温了一次二叉排序树 这个数据结构。

分享到：
| (转)typeid详解
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

Magicbox
Global site tag (gtag.js) - Google Analytics