定义模板,同时将类定义与类实现分离(C++,以栈为例)

一 问题背景:

        在以往单独实现树或栈时,只需要在开始使用typedef定义ElemType,后文便不必再考虑数据类型.

        但是,在实现二叉树非递归遍历时,需要借助额外的栈,树内数据类型为ElemType,但是栈内的数据类型为树节点,或者说指向树的指针,c++自带<stack>库,可以通过下列代码实现:

#include<iostream>
#include<stack>
using namespace std;
typedef int ElemType;
typedef struct TNode{
    ElemType data;
    TNode *lchild,*rchild;
}TNode,*BiTree;//定义树节点

void NLEnoRecursion(BiTree T){
    stack<BiTree> S;//使用stack库生成栈

        我们可以看到,<stack>库在生成栈时就用到了模板的知识.在定义Class类时,可以先不指定元素的数据类型,或者说可以用T来代替数据类型:

template <typename T>
typedef struct SNode{
        T data;
        struct SNode* next;
    }SNode,*pStack;

        使用<stack>库很方便快捷,并且已经足够解决遍历树的问题.但是为了更深入地学习,下面我们尝试自己编写stack模板.但是在单个文件内同时实现树与栈各种定义会很杂,而且很不好维护,所以我们考虑编写Stack类,并将类定义与实现分离.

二 Stack类的编写(不使用模板)

        为防止混淆,我们先不管模板,先把类定义搞清楚.

        class可以将类定义与类实现分离.需要注意的是,我们先将元素类型T用int来表示,待调试无误之后再扩展为模板,以下为代码,需要注意的地方都写在注释里:

#include<iostream>
using namespace std;

//template <typename T>
typedef int T;
typedef struct SNode{
        T data;
        struct SNode* next;
    }SNode,*pStack;


class Stack{
public:
    pStack pTop= new SNode;;//SNnode是我们自己创建的新数据类型,与int,float地位一致
    Stack();
    /*使用Stack()为无参构造函数,用于初始化数据域
    构造函数名字必须与类名相同,构造函数前面不需要void等返回类型
    下方Stack(pStack)同样为构造函数,用pStack将Stack初始化,即当输入一个栈时,S即指向该栈.
    */
    Stack(pStack);
    bool empty();
    bool push(T);
    bool pop();
    int length();
    T top();
};

//类可以将定义与实现分离,以上class定义类,以下代码实现class的各种操作
Stack::Stack(){
    pTop->next = NULL;
}
Stack::Stack(pStack NewStack){
    pTop = NewStack;
}
//这里用带头节点的链表来定义栈,故第一个元素为S->next,为NULL则栈空,pop失败
bool Stack::empty(){
    if (pTop->next == NULL)return true;
    else return false;
}
bool Stack::push(T n){
    SNode* temp = new SNode;
    temp->data = n;
    temp->next = pTop->next;
    pTop->next = temp;
    return true;
}
bool Stack::pop(){
    if(pTop->next == NULL){
        return false;
    }
    SNode* temp = new SNode;
    temp = pTop->next;
    pTop = temp;
    free(temp);
    return true;
}
T Stack::top(){
    T temp;
    temp = pTop->next->data;
    return temp;
}


//template <typename T>
int main(){
    Stack S;
    S.push(114);
    cout << S.pTop->next->data <<endl;
    S.top();
    cout << S.pTop->next->data <<endl;
    S.pop();
    cout << S.pTop->next->data <<endl;
    return 0;
}

三 Stack类的编写(使用模板)

参考链接:https://www.cnblogs.com/0-lingdu/p/12269554.html

        需要更改的地方不多,

1.将开头typedef int T一句移去,在class前添加template <typename T>,T即为未定义的数据类型.注意不加分号.

由于SNode的定义也用到了T,所以我们把该定义也移到class内(这里我存疑,在class内定义typedef我不确定会不会出什么问题,但至少代码不会报错):

template<typename T>
class Stack{
public:
    typedef struct SNode{
            T data;
            struct SNode* next;
        }SNode,*pStack;
    pStack pTop= new SNode;;//SNnode是我们自己创建的新数据类型,与int,float地位一致
    Stack();
    /*使用Stack()为无参构造函数,用于初始化数据域
    构造函数名字必须与类名相同,构造函数前面不需要void等返回类型
    下方Stack(pStack)同样为构造函数,用pStack将Stack初始化,即当输入一个栈时,S即指向该栈.
    */
    Stack(pStack);
    bool empty();
    bool push(T);
    bool pop();
    int length();
    T top();
};

2.在类实现每一句前面都要加template <typename T>,随后在Stack::的::加上<T>,注意是每一句

Stack<T>::Stack(pStack NewStack){
    pTop = NewStack;
}
//这里用带头节点的链表来定义栈,故第一个元素为S->next,为NULL则栈空,pop失败

template <typename T>
bool Stack<T>::empty(){
    if (pTop->next == NULL)return true;
    else return false;
}

至此完成,可以运行下列main函数:

int main(){
    Stack<int> S;
    S.push(114);
    cout << S.pTop->next->data <<endl;
    S.top();
    cout << S.pTop->next->data <<endl;
    S.pop();
    cout << S.pTop->next->data <<endl;
    return 0;
}

        第二行Stack<int>中,"int"可换为任意数据类型,可以回到这偏偏文章开头,我们编写的Stack函数与c++<stack>库使用方法完全相同.本文主要内容到此为止.更进一步,可以将Stack.h头文件与Stack.cpp文件拆开,以供其它文件调用,那些难度不大,也不方便在一篇文章内说明,这里就不展开.

        本人还在学习C++,难免有错误或疏漏,各位佬轻喷(狗头保命)

        感谢阅读,以下是完整代码.

//参考链接:https://www.cnblogs.com/0-lingdu/p/12269554.html
#include<iostream>
using namespace std;

template<typename T>
class Stack{
public:
    typedef struct SNode{
            T data;
            struct SNode* next;
        }SNode,*pStack;
    pStack pTop= new SNode;;//SNnode是我们自己创建的新数据类型,与int,float地位一致
    Stack();
    /*使用Stack()为无参构造函数,用于初始化数据域
    构造函数名字必须与类名相同,构造函数前面不需要void等返回类型
    下方Stack(pStack)同样为构造函数,用pStack将Stack初始化,即当输入一个栈时,S即指向该栈.
    */
    Stack(pStack);
    bool empty();
    bool push(T);
    bool pop();
    int length();
    T top();
};

//类可以将定义与实现分离,以上class定义类,以下代码实现class的各种操作
template <typename T>
Stack<T>::Stack(){
    pTop->next = NULL;
}

template <typename T>
Stack<T>::Stack(pStack NewStack){
    pTop = NewStack;
}
//这里用带头节点的链表来定义栈,故第一个元素为S->next,为NULL则栈空,pop失败

template <typename T>
bool Stack<T>::empty(){
    if (pTop->next == NULL)return true;
    else return false;
}

template <typename T>
bool Stack<T>::push(T n){
    SNode* temp = new SNode;
    temp->data = n;
    temp->next = pTop->next;
    pTop->next = temp;
    return true;
}

template <typename T>
bool Stack<T>::pop(){
    if(pTop->next == NULL){
        return false;
    }
    SNode* temp = new SNode;
    temp = pTop->next;
    pTop = temp;
    free(temp);
    return true;
}

template <typename T>
T Stack<T>::top(){
    T temp;
    temp = pTop->next->data;
    return temp;
}


//template <typename T>
int main(){
    Stack<int> S;
    S.push(114);
    cout << S.pTop->next->data <<endl;
    S.top();
    cout << S.pTop->next->data <<endl;
    S.pop();
    cout << S.pTop->next->data <<endl;
    return 0;
}