注册 登录
> C++

EssentialC++ 以template进行编程

系统 2800 0

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

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

 

EssentialC++ 以template进行编程

 

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

 

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

 

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

 

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

 

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

 

 

 

[cpp] view plain copy print ?
  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 plain copy print ?
  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 plain copy print ?
  1. template < typename  elemType>  
  2. class  BinaryTree {  
  3. public :  
  4. ...  
  5. private :  
  6.     BTnode<strong><elemType></strong> *_root;  
  7. };  
[cpp] view plain copy print ?
  1.   

下面给出BTnode完整的定义：

[cpp] view plain copy print ?
  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 plain copy print ?
  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 plain copy print ?
  1. insert_value( const  valType &val)  

 

下面给出BinaryTree的模板实现：

 

[cpp] view plain copy print ?
  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 plain copy print ?
  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的语法。而且还让我重温了一次二叉排序树 这个数据结构。

EssentialC++ 以template进行编程


更多文章、技术交流、商务合作、联系博主

微信扫码或搜索：z360901061

微信扫一扫加我为好友

QQ号联系： 360901061

您的支持是博主写作最大的动力，如果您喜欢我的文章，感觉我的文章对您有帮助，请用微信扫描下面二维码支持博主2元、5元、10元、20元等您想捐的金额吧，狠狠点击下面给点支持吧，站长非常感激您！手机微信长按不能支付解决办法：请将微信支付二维码保存到相册，切换到微信，然后点击微信右上角扫一扫功能，选择支付二维码完成支付。

【本文对您有帮助就好】元

您的支持是博主写作最大的动力，如果您喜欢我的文章，感觉我的文章对您有帮助，请用微信扫描上面二维码支持博主2元、5元、10元、自定义金额等您想捐的金额吧，站长会非常 感谢您的哦！！！

发表我的评论
最新评论 总共0条评论