EssentialC++ 以template进行编程

2024-02-29 23:48

本文主要是介绍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。如果不实现泛型,


class string_node {
public:private:string _val;   //节点的值int _cnt;      //节点计数string_node *_lchild;    //左节点string_node *_rchild;    //右节点};

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

template<typename valType>
class BTnode {friend class BinaryTree<valType>;    //把二叉树类型BinaryTree声明为友元类,这样BinaryTree就可以访问BTnode的私有成员 _val,_cnt,_lchild,_rchild等
public:BTnode(){}BTnode(const valType &val);void insert_value(const valType& elem);void remove_value( const valType &val, BTnode *& prev);static void lchild_leaf( BTnode *leaf, BTnode *subtree);
private:valType _val;int     _cnt;BTnode *_lchild;BTnode *_rchild;
};

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

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

template<typename elemType>
class BinaryTree {
public:
...
private:BTnode<elemType> *_root;
};
下面给出BTnode完整的定义:

template<typename Type>
class BinaryTree;template<typename valType>
class BTnode {friend class BinaryTree<valType>;
public:BTnode(){}BTnode(const valType &val);void insert_value(const valType& elem);void remove_value( const valType &val, BTnode *& prev);static void lchild_leaf( BTnode *leaf, BTnode *subtree);
private:valType _val;int     _cnt;BTnode *_lchild;BTnode *_rchild;
};template<typename valType>
BTnode<valType>::BTnode(const valType &val): _val(val)
{_cnt = 1;_lchild = _rchild = 0;
}template<typename valType>
void BTnode<valType>::insert_value(const valType &val) {if ( this->_val == val) {this->_cnt++;         return ;}if(this->_val > val ) {if(!this->_lchild)this->_lchild = new BTnode<valType>(val);elsethis->_lchild->insert_value(val);} else {if(!this->_rchild)this->_rchild = new BTnode<valType>(val);elsethis->_rchild->insert_value(val);}}template<typename valType>
void BTnode<valType>::remove_value( const valType &val, BTnode *& prev) {   //找到相应的值,删除该节点。prev是起始的节点。 这里需要修改BTnode *指针本身,所以我们定义为 BTnode *& previf( val < _val ) {if ( !_lchild)return;else_lchild->remove_value(val, _lchild);}else if ( val > _val) {if( !_rchild)return;else_rchild->remove_value(val,_rchild);}else {if (_rchild) {prev = _rchild;if(_lchild)if( !prev->_lchild)prev->_lchild = _lchild;elseBTnode<valType>::lchild_leaf(_lchild,prev->_lchild);}elseprev = _lchild;delete this;}}template<typename valType>
inline void BTnode<valType>::lchild_leaf( BTnode *leaf, BTnode *subtree) {
//使leaf成为subtree的左子树的叶子节点while (subtree->_lchild)subtree = subtree->_lchild;subtree->_lchild = leaf;
}

template<typename valType>
BTnode<valType>::BTnode(const valType &val): _val(val)
{_cnt = 1;_lchild = _rchild = 0;
}
为什么这里第二次出现BTnode的时候不需要<valType>去修饰了呢,因为在class scope运算符出现之后 BTnode<valType>::,其后所有东西被视为位于class定义域内:还记得上面所说的规则吗在class template 以及其members的定义式中,不需要之外。其他的场合都需要以parameter list 加以修饰。

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

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

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

insert_value(const valType &val)

下面给出BinaryTree的模板实现:

template<typename elemType>
class BinaryTree {
public:BinaryTree();BinaryTree(const BinaryTree&);~BinaryTree();BinaryTree& operator= (const BinaryTree&);void insert( const elemType &);bool empty() { return _root == 0;}void remove(const elemType &elem);void remove_root();void clear() { if(_root) { clear(_root); _root = 0;}}void preorder();void preorder(BTnode<elemType> *node, ostream &os = cout);static ostream & display_val( elemType &node,ostream &os = cout);void pre_recursion(BTnode<elemType> *node);BTnode<elemType>* get_root() { return _root;}
private:BTnode<elemType> *_root;void clear(BTnode<elemType> *node);void copy(BTnode<elemType> *tar, BTnode<elemType> *src);
};template<typename elemType>
inline BinaryTree<elemType>::
BinaryTree() : _root(0) {}template<typename elemType>
inline BinaryTree<elemType>::BinaryTree(const BinaryTree& rhs) {copy(_root,rhs._root);
}template<typename elemType>
void BinaryTree<elemType>::insert( const elemType &elem) {if (!_root)_root = new BTnode<elemType>(elem);_root->insert_value(elem);
}template<typename elemType>
inline BinaryTree<elemType>::~BinaryTree() {clear();
}template<typename elemType>
inline BinaryTree<elemType>&
BinaryTree<elemType>::operator= (const BinaryTree &rhs) {if( ! this = &rhs) {clear();copy(_root,rhs._root);}return *this;
}template<typename elemType>
inline void BinaryTree<elemType>::remove( const elemType &elem) {if(_root) {if( _root->_val == elem)remove_root();else_root->remove_value(elem, _root);}
}template<typename elemType>
void BinaryTree<elemType>::
remove_root() {if (!_root) return;BTnode<elemType> *tmp = _root;if( !_root->_rchild) {_root = _root->_rchild;if(tmp->_lchild) {if(!_root->_lchild)//没有任何子树则直接接上_root->_lchild = tmp->_lchild;elseBTnode<elemType>::lchild_leaf(tmp->_lchild,_root->_lchild);}}else_root = _root->_lchild;delete tmp;
}
//清除所有节点
template<typename elemType>
void BinaryTree<elemType>::clear(BTnode<elemType> *node) {if(node) {clear(node->_lchild);clear(node->_rchild);delete node;}
}template<typename elemType>
void BinaryTree<elemType>::preorder() {pre_recursion(_root);
}//递归的前序遍历
template<typename elemType>
void BinaryTree<elemType>::preorder(BTnode<elemType> *node, ostream &os) {if(node) {display_val(node->_val,os);preorder(node->_lchild,os);preorder(node->_rchild,os);}
}template<typename elemType>
ostream & BinaryTree<elemType>::display_val(elemType &node , ostream &os) {os << node << ' ';return os;
}//非递归实现前序遍历
template<typename elemType>
void BinaryTree<elemType>::pre_recursion (BTnode<elemType> *node) {stack<BTnode<elemType>*> s;   //使用先进后出栈s.push(node);while(!s.empty()) {BTnode<elemType>* tmp = s.top();s.pop();BinaryTree<elemType>::display_val(tmp->_val,std::cout);if(tmp->_rchild)s.push(tmp->_rchild);    //右节点先进栈 后出,后遍历if(tmp->_lchild)s.push(tmp->_lchild);    //左节点后进栈,先出,先遍历}
}

测试:

int main()
{BinaryTree<string> bt;bt.insert("abc");bt.insert("agcb");bt.insert("kfgd");bt.insert("how are you");bt.preorder();//bt.remove("abc");//bt.preorder();bt.remove("kfgd");bt.preorder();return 0;
}
本章不仅让我了解泛型编程,模板类是怎么一回事,template的语法。而且还让我重温了一次二叉排序树 这个数据结构。


参考文献:

《Eseential C++》


这篇关于EssentialC++ 以template进行编程的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/760500

相关文章

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

Linux 网络编程 --- 应用层

一、自定义协议和序列化反序列化 代码: 序列化反序列化实现网络版本计算器 二、HTTP协议 1、谈两个简单的预备知识 https://www.baidu.com/ --- 域名 --- 域名解析 --- IP地址 http的端口号为80端口,https的端口号为443 url为统一资源定位符。CSDNhttps://mp.csdn.net/mp_blog/creation/editor

【Python编程】Linux创建虚拟环境并配置与notebook相连接

1.创建 使用 venv 创建虚拟环境。例如,在当前目录下创建一个名为 myenv 的虚拟环境: python3 -m venv myenv 2.激活 激活虚拟环境使其成为当前终端会话的活动环境。运行: source myenv/bin/activate 3.与notebook连接 在虚拟环境中,使用 pip 安装 Jupyter 和 ipykernel: pip instal

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获:包含零个或者多个捕获符的逗号分隔列表 模板形参:用于泛型lambda提供个模板形参的名

业务中14个需要进行A/B测试的时刻[信息图]

在本指南中,我们将全面了解有关 A/B测试 的所有内容。 我们将介绍不同类型的A/B测试,如何有效地规划和启动测试,如何评估测试是否成功,您应该关注哪些指标,多年来我们发现的常见错误等等。 什么是A/B测试? A/B测试(有时称为“分割测试”)是一种实验类型,其中您创建两种或多种内容变体——如登录页面、电子邮件或广告——并将它们显示给不同的受众群体,以查看哪一种效果最好。 本质上,A/B测

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)