C++初学-模板编程的实例应用
标签搜索
侧边栏壁纸
博主昵称
hansyee

  • 累计撰写 100 篇文章
  • 累计收到 2 条评论
目录
C/C++学习笔记

C++初学-模板编程的实例应用

hansyee
hansyee
2024-10-16 / 0 评论 / 1 阅读 / 正在检测是否收录...
温馨提示：
本文最后更新于2024年10月16日，已超过173天没有更新，若内容或图片失效，请留言反馈。

背景说明

以下程序整理于<<Essential C++>>中的以template进行编程的篇章。主要实现了一个基础的二叉查找树。

类的设计

二叉树包含两个类：一个是 BinaryTree，用于存储一个指针，指向根节点；另一个是 BTnode，用来存储节点值，以及连接左右两个子节点。节点值的类型即为参数化的部分。其中 BinaryTree是提供给客户使用的类，包含以下可用操作：插入元素(insert)、移除元素(remove)、查找元素(find)、清除二叉树(clear)、打印二叉树(前序、中序、后序)。

实现

BinaryTree.h

#ifndef BINARYTREE_H_INCLUDED
#define BINARYTREE_H_INCLUDED

#include <iostream>

using uint_t = unsigned int;

// 类模板前置声明
template <class elemType>
class BinaryTree;

template <class valType>
class BTnode;

template <class valType>
class BTnode
{

    friend class BinaryTree<valType>;

public:

    // 普通构造函数，节点值为val
    BTnode(const valType &val);

    // 析构函数
    ~BTnode();

    // 插入一个新节点，节点值为val
    void insert_value(const valType &val);

    // 移除一个节点，节点值为val，父节点为prev
    void remove_value(const valType &val, BTnode * &prev);

    // 查找一个结点，节点值为val
    bool find_value(const valType &val) const;

    // 前序打印：节点本身-左子节点-右子节点
    void preorder(BTnode *pt, std::ostream &os) const;
    // 中序打印：左子节点-节点本身-右子节点
    void inorder(BTnode *pt, std::ostream &os) const;
    // 后序打印：左子节点-右子节点-节点本身
    void postorder(BTnode *pt, std::ostream &os) const;

    // 获取节点值
    const valType& value() const { return _val; }

    // 获取节点值出现次数
    uint_t occurs() const { return _cnt; }

    // 遍历subtree节点下的左子树，将leaf接为最下层的叶子节点
    static void lchild_leaf(BTnode *leaf, BTnode *subtree);

private:

    // 拷贝构造函数
    BTnode(const BTnode &rhs);

    // 赋值运算符重载函数
    BTnode& operator=(const BTnode &rhs);

    // 打印节点值
    void display_val(BTnode *pt, std::ostream &os) const;

private:

    // 节点值
    valType _val;

    // 节点值出现次数
    uint_t _cnt;

    // 指向左子节点
    BTnode *_lchild;

    // 指向右子节点
    BTnode *_rchild;

};


template <typename valType>
inline
BTnode<valType>::
BTnode(const valType& val)
    : _val(val), _cnt(1), _lchild(nullptr), _rchild(nullptr)
{
    *(BinaryTree<valType>::getOutStream()) << "调用普通构造函数BTnode<valType>::BTnode(const valType& val)" << std::endl;
}



template <typename valType>
inline
BTnode<valType>::
BTnode(const BTnode &rhs)
    : _val(rhs._val), _cnt(1), _lchild(nullptr), _rchild(nullptr)
{
    *(BinaryTree<valType>::getOutStream()) << "调用拷贝构造函数BTnode<valType>::BTnode(const BTnode &rhs)" << std::endl;
}



template <typename valType>
inline BTnode<valType>&
BTnode<valType>::
operator=(const BTnode &rhs)
{
    _val = rhs._val;
    _cnt = 1;
    _lchild = nullptr;
    _rchild = nullptr;

    *(BinaryTree<valType>::getOutStream()) << "调用赋值运算符重载函数BTnode<valType>::BTnode(const BTnode &rhs)" << std::endl;
}


template <typename valType>
inline
BTnode<valType>::
~BTnode()
{
    *(BinaryTree<valType>::getOutStream()) << "调用析构函数BTnode<valType>::~BTnode()" << std::endl;
}


template <typename valType>
void
BTnode<valType>::
insert_value(const valType &val)
{
    if (val == _val)
    {
        ++_cnt;
        return;
    }
    else if (val < _val)
    {
        if (_lchild)
            _lchild->insert_value(val);
        else
            _lchild = new BTnode(val);
    }
    else
    {
        if (_rchild)
            _rchild->insert_value(val);
        else
            _rchild = new BTnode(val);
    }
}


template <typename valType>
void
BTnode<valType>::
lchild_leaf(BTnode *leaf, BTnode *subtree)
{
    while (subtree->_lchild)
        subtree = subtree->_lchild;

    subtree->_lchild = leaf;
}


template <typename valType>
void
BTnode<valType>::
remove_value(const valType &val, BTnode * &prev)
{
    // 算法：
    // 以删除节点的右子节点取代删除节点本身
    // 若无右子节点，就以左子节点取代删除节点本身
    // 搬移左子节点，使其成为右子节点的左子树的叶节点

    if (val == _val)
    {
        if (_rchild)
        {
            prev = _rchild;

            if (_lchild)
            {
                if (prev->_lchild)
                    BTnode<valType>::lchild_leaf(_lchild, prev->_lchild);
                else
                    prev->_lchild = _lchild;
            }
        }
        else
        {
            prev = _lchild;
        }

        delete this;
    }
    else if (val < _val)
    {
        if (_lchild)
            _lchild->remove_value(val, _lchild);
    }
    else
    {
        if (_rchild)
            _rchild->remove_value(val, _rchild);
    }
}


template <typename valType>
bool
BTnode<valType>::
find_value(const valType &val) const
{
    if (val == _val)
    {
        return true;
    }
    else if (val < _val)
    {
        if (_lchild)
            return _lchild->find_value(val);
        else
            return false;
    }
    else
    {
        if (_rchild)
            return _rchild->find_value(val);
        else
            return false;
    }
}


template <typename valType>
void
BTnode<valType>::
preorder(BTnode *pt, std::ostream &os) const
{
    if (pt)
    {
        // 节点本身-左子节点-右子节点
        display_val(pt, os);

        if (pt->_lchild)
            preorder(pt->_lchild, os);

        if (pt->_rchild)
            preorder(pt->_rchild, os);
    }
}


template <typename valType>
void
BTnode<valType>::
inorder(BTnode *pt, std::ostream &os) const
{
    if (pt)
    {
        // 左子节点-节点本身-右子节点
        if (pt->_lchild)
            inorder(pt->_lchild, os);

        display_val(pt, os);

        if (pt->_rchild)
            inorder(pt->_rchild, os);
    }
}


template <typename valType>
void
BTnode<valType>::
postorder(BTnode *pt, std::ostream &os) const
{
    if (pt)
    {
        // 左子节点-右子节点-节点本身
        if (pt->_lchild)
            postorder(pt->_lchild, os);

        if (pt->_rchild)
            postorder(pt->_rchild, os);

        display_val(pt, os);
    }
}

template <typename valType>
void
BTnode<valType>::
display_val(BTnode *pt, std::ostream &os) const
{
    if (pt)
    {
        os << pt->_val;

        if (pt->_cnt > 1)
            os << "(" << pt->_cnt << ") ";
        else
            os << ' ';
    }
}




template <class elemType>
class BinaryTree
{
public:

    // 默认构造函数
    BinaryTree();

    // 拷贝构造函数
    BinaryTree(const BinaryTree &rhs);

    // 赋值运算符重载函数
    BinaryTree& operator=(const BinaryTree &rhs);

    // 析构函数
    ~BinaryTree();

    // 插入新节点，节点值为elem
    void insert(const elemType& elem);

    // 移除节点，节点值为elem
    void remove(const elemType &elem);

    // 查找节点是否在二叉树，节点值为val
    bool find(const elemType &val) const;

    // 二叉树是否为空
    bool empty() { return (nullptr == _root); }

    // 清除整个二叉树
    void clear() { clear(_root); _root = nullptr; }

    // 前序打印：节点本身-左子节点-右子节点
    void preorder(std::ostream &os = *_current_os) const { _root->preorder(_root, os); os << std::endl; }
    // 中序打印：左子节点-节点本身-右子节点
    void inorder(std::ostream &os = *_current_os) const { _root->inorder(_root, os); os << std::endl; }
    // 后序打印：左子节点-右子节点-节点本身
    void postorder(std::ostream &os = *_current_os) const { _root->postorder(_root, os); os << std::endl; }

    // 获取当前输出流
    static std::ostream* getOutStream() { return _current_os; }

    // 设置当前输出流
    static void setOutStream(std::ostream *os) { if (os) _current_os = os; }

private:

    // 将src指向的子树复制到tar指向的子树
    void copy(BTnode<elemType> *&tar, const BTnode<elemType> *src);

    // 清除二叉树
    void clear(BTnode<elemType> *pt);

    // 移除根节点
    void remove_root();

private:

    // 指向二叉树根节点
    BTnode<elemType> *_root;

    // 指向输出流
    static std::ostream *_current_os;


};


template <typename elemType>
inline
BinaryTree<elemType>::
BinaryTree()
    : _root(nullptr)
{
    *_current_os << "调用默认构造函数BinaryTree<elemType>::BinaryTree()" << std::endl;
}


template <typename elemType>
inline
BinaryTree<elemType>::
BinaryTree(const BinaryTree &rhs)
{
    copy(_root, rhs._root);

    *_current_os << "调用拷贝构造函数BinaryTree<elemType>::BinaryTree(const BinaryTree &rhs)" << std::endl;
}


template <typename elemType>
inline BinaryTree<elemType>&
BinaryTree<elemType>::
operator=(const BinaryTree &rhs)
{
    if (this != &rhs)
    {
        clear();
        copy(_root, rhs._root);
    }

    *_current_os << "调用赋值运算符重载函数BinaryTree<elemType>::operator=(const BinaryTree &rhs)" << std::endl;

    return *this;
}


template <typename elemType>
inline BinaryTree<elemType>::
~BinaryTree()
{
    clear();

    *_current_os << "调用析构函数BinaryTree<elemType>::~BinaryTree()" << std::endl;
}


template <typename elemType>
void
BinaryTree<elemType>::
insert(const elemType &elem)
{
    if (_root)
        _root->insert_value(elem);
    else
        _root = new BTnode<elemType>(elem);
}


template <typename elemType>
void
BinaryTree<elemType>::
remove(const elemType &elem)
{
    if (_root)
    {
        if (elem == _root->_val)
            remove_root();
        else
            _root->remove_value(elem, _root);
    }
}


template <typename elemType>
bool
BinaryTree<elemType>::
find(const elemType &elem) const
{
    if (_root)
    {
        return _root->find_value(elem);
    }
    else
    {
        return false;
    }
}


template <typename elemType>
void
BinaryTree<elemType>::
remove_root()
{
    // 算法：
    // 以删除节点的右子节点取代删除节点本身
    // 若无右子节点，就以左子节点取代删除节点本身
    // 搬移左子节点，使其成为右子节点的左子树的叶节点

    if (_root)
    {
        BTnode<elemType> * const oldroot = _root;

        if (oldroot->_rchild)
        {
            _root = oldroot->_rchild;

            BTnode<elemType> *oldlc = oldroot->_lchild;
            BTnode<elemType> *newlc = _root->_lchild;

            if (oldlc)
            {
                if (newlc)
                    BTnode<elemType>::lchild_leaf(oldlc, newlc);
                else
                    _root->_lchild = oldlc;
            }
        }
        else
        {
            _root = oldroot->_lchild;
        }

        delete oldroot;
    }
}


template <typename elemType>
void
BinaryTree<elemType>::
clear(BTnode<elemType> *pt)
{
    if (pt)
    {
        clear(pt->_lchild);
        clear(pt->_rchild);
        delete pt;
    }
}

template <typename elemType>
void
BinaryTree<elemType>::
copy(BTnode<elemType> *&tar, const BTnode<elemType> *src)
{
    if (src)
    {
        tar = new BTnode<elemType>(src->val);
        if (src->_lchild)
            copy(tar->_lchild, src->_lchild);
        if (src->_rchild)
            copy(tar->_rchild, src->_rchild);
    }
}

#endif // BINARYTREE_H_INCLUDED

main.cpp

#include "BinaryTree.h"

#include <string>
#include <fstream>

template<typename elemType>
std::ostream *BinaryTree<elemType>::_current_os = &std::cout;

const std::string log_file = "logfile.txt";

int main()
{
    std::ofstream log(log_file);
    if (!log)
    {
        std::cerr << "错误：无法打开文件[" << log_file << "]" << std::endl;

        return -1;
    }
    else
    {
        BinaryTree<std::string>::setOutStream(&log);
    }

    BinaryTree<std::string> bt;

    if (bt.empty())
    {
        log << "二叉树为空" << std::endl;
    }
    else
    {
        log << "二叉树不为空" << std::endl;
        log << "前序: ";
        bt.preorder(log);
        log << "中序: ";
        bt.inorder(log);
        log << "后序: ";
        bt.postorder(log);
    }

    bt.insert("Piglet");
    bt.insert("Eeyore");
    bt.insert("Roo");
    bt.insert("Tigger");
    bt.insert("Chris");
    bt.insert("Chris");
    bt.insert("Chris");
    bt.insert("Pooh");
    bt.insert("Kanga");

    log << "前序: ";
    bt.preorder(log);
    log << "中序: ";
    bt.inorder(log);
    log << "后序: ";
    bt.postorder(log);

    bt.remove("Piglet");
    log << "前序: ";
    bt.preorder(log);
    log << "中序: ";
    bt.inorder(log);
    log << "后序: ";
    bt.postorder(log);

    bt.remove("Roo");
    log << "前序: ";
    bt.preorder(log);
    log << "中序: ";
    bt.inorder(log);
    log << "后序: ";
    bt.postorder(log);

    if (bt.find("Kanga"))
    {
        log << "存在Kanga" << std::endl;
    }
    else
    {
        log << "不存在Kanga" << std::endl;
    }

    if (bt.find("hsy"))
    {
        log << "存在hsy" << std::endl;
    }
    else
    {
        log << "不存在hsy" << std::endl;
    }

    bt.clear();
    if (bt.empty())
    {
        log << "二叉树为空" << std::endl;
    }
    else
    {
        log << "二叉树不为空" << std::endl;
        bt.preorder(log);
        bt.inorder(log);
        bt.postorder(log);
    }


    return 0;
}

运行结果如下

调用默认构造函数BinaryTree<elemType>::BinaryTree()
二叉树为空
调用普通构造函数BTnode<valType>::BTnode(const valType& val)
调用普通构造函数BTnode<valType>::BTnode(const valType& val)
调用普通构造函数BTnode<valType>::BTnode(const valType& val)
调用普通构造函数BTnode<valType>::BTnode(const valType& val)
调用普通构造函数BTnode<valType>::BTnode(const valType& val)
调用普通构造函数BTnode<valType>::BTnode(const valType& val)
调用普通构造函数BTnode<valType>::BTnode(const valType& val)
前序: Piglet Eeyore Chris(3) Kanga Roo Pooh Tigger 
中序: Chris(3) Eeyore Kanga Piglet Pooh Roo Tigger 
后序: Chris(3) Kanga Eeyore Pooh Tigger Roo Piglet 
调用析构函数BTnode<valType>::~BTnode()
前序: Roo Pooh Eeyore Chris(3) Kanga Tigger 
中序: Chris(3) Eeyore Kanga Pooh Roo Tigger 
后序: Chris(3) Kanga Eeyore Pooh Tigger Roo 
调用析构函数BTnode<valType>::~BTnode()
前序: Tigger Pooh Eeyore Chris(3) Kanga 
中序: Chris(3) Eeyore Kanga Pooh Tigger 
后序: Chris(3) Kanga Eeyore Pooh Tigger 
存在Kanga
不存在hsy
调用析构函数BTnode<valType>::~BTnode()
调用析构函数BTnode<valType>::~BTnode()
调用析构函数BTnode<valType>::~BTnode()
调用析构函数BTnode<valType>::~BTnode()
调用析构函数BTnode<valType>::~BTnode()
二叉树为空
调用析构函数BinaryTree<elemType>::~BinaryTree()
0
暂无标签
版权属于： hansyee
本文链接： https://17zturn.com/archives/1198.html
作品采用： 《 署名—非商业性使用—相同方式共享 4.0 协议国际版 (CC BY-NC-SA 4.0) 》许可协议授权

评论 (0)

取消