C++：类模板

• 使用类模板的方式定义的双向链表

---

/*C++：类模板*/

#ifndef TEMPLATE_CLASS_H
#define TEMPLATE_CLASS_H

#include <iostream>

using namespace std;

template <typename D>
class DNode{
public:
    DNode(D data){
        next = NULL;
        prev = NULL;
        this->data = data;
        }

    D data;
    DNode<D>* next;
    DNode<D>* prev;
};

template <typename D>
class DList{
public:
    DList();
    ~DList();

    /*插入、删除*/
    void insert_next(DNode<D>* node,D data);//在结点node后插入数据data
    void insert_prev(DNode<D>* node,D data);//在结点node前插入数据data
    bool remove(DNode<D>* node);//删除node结点

    /*查找*/
    DNode<D>* Search(D data);//查找链表中数据为data的结点
    DNode<D>* Find(int ith);//查找链表中第ith个结点

    /*链表信息*/
    int list_size(){return size;}
    DNode<D>* head(){return pHead;}
    DNode<D>* tail(){return pTail;}

    /*其他*/
    void display();
private:
    size_t size;
    DNode<D>* pHead;
    DNode<D>* pTail;
};

/*****************************************************************
Function:DList
Description：
            构造函数，主要是初始化size、实例化头结点、初始化
            头指针pHead和尾指针pTail。
*****************************************************************/
template <typename D>
DList<D>::DList(){
    size = 0;
    pHead = new DNode<D>(NULL);
    pTail = pHead;
}
/*****************************************************************
Function:~DList
Description：析构函数，主要是释放链表的空间。
*****************************************************************/
template <typename D>
DList<D>::~DList(){
    while(size>0)
        remove(pHead->next);
    delete pHead;
}
/*****************************************************************
Function:insert_next
Description：在node结点后插入数据data。
*****************************************************************/
template <typename D>
void DList<D>::insert_next(DNode<D>* node,D data){
    if(node==NULL)
        return;
    DNode<D>* p = new DNode<D>(data);
    if(node->next!=NULL){//如果node不是末尾的结点
        //处理p与node->next的关系
        p->next = node->next;
        node->next->prev = p;
    }
    //处理p与node的关系
    node->next = p;
    p->prev = node;
    //如果node是pTail，那么就修改pTail
    if(node==pTail)
        pTail = node->next;
    size++;
}
/*****************************************************************
Function:insert_prev
Description：将数据data插入到结点node之前。
*****************************************************************/
template <typename D>
void DList<D>::insert_prev(DNode<D>* node,D data){
    //node为空或者在pHead前插入结点是不允许的
    if(node==NULL||node==pHead)
        return;
    DNode<D>* prev = node->prev;
    insert_next(prev,data);
}

/*****************************************************************
Function:remove
Description：从链表中删除node结点。
*****************************************************************/
template <typename D>
bool DList<D>::remove(DNode<D>* node){
    if(node==NULL||node==pHead)
        return false;
    DNode<D>* prev = node->prev;
    if(node==pTail){
        //如果node是末尾结点，直接修改前序结点，并且要修改pTail
        prev->next = NULL;
        pTail = prev;
    }else{
        prev->next = node->next;
        node->next->prev = prev;
    }
    delete node;
    size--;
    return true;
}
/*****************************************************************
Function:Search
Description：查找链表中数据为data的结点。
*****************************************************************/
template <typename D>
DNode<D>* DList<D>::Search(D data){
    DNode<D>* p = pHead->next;
    while(p!=NULL){
        if(p->data==data)
            return p;
        p = p->next;
    }
    return NULL;
}
/*****************************************************************
Function:Find
Description：查找链表中第ith个结点。
*****************************************************************/
template <typename D>
DNode<D>* DList<D>::Find(int ith){
    if(ith>size||ith<1)
        return NULL;
    DNode<D>* p = pHead;
    for(int i=0;i<ith;i++)
        p = p->next;
    return p;
}

template <typename D>
void DList<D>::display(){
    DNode<D>* p = pHead->next;
    while(p!=NULL){
        cout<<p->data<<" ";
        p = p->next;
    }
    cout<<endl;
}

#endif // TEMPLATE_CLASS_H

 

• 知识点

---

  1.  类模板中的成员函数必须同类模板在同一个文件中。在普通类的定义中，我们通常将类的声明放在头文件中，例如：List.h；而将类的实现放在源文件中，例如：List.cpp。而类模板必须定义在List.h中。

  2.  当在普通类外定义成员函数时，应该写作

DList::DList(){}

       但是在类模板中，应该写作

template <typename D>
DList<D>::DList(){}

  3.  类模板实例化后，产生模板类。例如下面的类模板实例化过程

DList<int> l1;

       它将模板实参int绑定到模板参数D上。此时，会产生一个新的类，这个类就是将类模板中的所有D替换为int的类。

  4.  不同类型的实例化，会产生不同的模板类，下面代码就产生了2种不同的模板类。

DList<int> l1;
DList<char> l2;

  5.  成员函数只有在调用时才会实例化。

  6.  可以为实例化的类模板定义别名，例如

typedef DList<int> intDList;

  7.  类模板可以定义static成员和方法，相同的模板实参共享static成员和方法。

template <typename T>
class Node{
public:
    static int num;
    static int pow(int b,int c);
}

Node<int> i1,i2,i3;//i1、i2和i3共享同一个num和pow()
Node<string> j;//j和i1、i2、i3不共享num和pow()