亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

EssentialC++ 以template進行編程

系統 4028 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。如果不實現泛型，

?

?

?

  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類。這顯然太麻煩。我們可以定義一個支持泛型的節點。

?

  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 加以修飾。如：

?

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

下面給出BTnode完整的定義：

  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. }??

?

  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 修飾詞。如：

?

  1. insert_value( const ?valType?&val)??

?

下面給出BinaryTree的模板實現：

?

  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. }??

?

測試：

?

  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條評論
主站蜘蛛池模板： 九九热这里都是精品 | 国产精品国产精品国产专区不卡 | 性生活视频免费 | 精品视自拍视频在线观看 | 亚洲成人免费在线 | 成人免费看毛片 | 国产片一级aaa毛片视频 | 男人的影院 | 狠狠色成人综合网图片区 | 国产尤物福利视频一区二区 | 一级黄色免费网站 | 久色视频在线观看 | 中文字幕伊人久久网 | 99视频精品全部免费免费观 | 老子不卡 | 国产成人精品男人的天堂538 | 大尺度福利视频在线观看网址 | 中文字幕久精品免费视频蜜桃视频 | 免费亚洲视频 | 欧美久久影院 | 青青国产成人精品视频 | 久久香蕉综合精品国产 | 久久色网| 污宅男666在线永久免费观看 | 中文在线不卡 | 久久精品国产一区二区三区日韩 | 欧美中文在线观看 | 天天操天 | 色综合欧美综合天天综合 | 亚洲小说春色综合另类网蜜桃 | 久久精品免费一区二区三区 | 毛片网络| 亚洲爱爱久久精品 | 中文字幕视频一区二区 | 免费看欧美一级片 | 一本久道热中字伊人 | 神马不卡| 97视频在线观看免费视频 | 免费黄色影院 | 国产成+人欧美+综合在线观看 | 国产一区二区三区影院 |