泛型編程-抽象鏈表模板類

出現(xiàn)的問(wèn)題：在增加、刪除結(jié)點(diǎn)時(shí)姑宽，僅僅delete了指針缴挖，但是delete p;并不意味著p=NULL;
例如以下代碼：

int *pp=new int(5);
    delete pp;
    
    cout << pp  <<","<<*pp<< endl;

運(yùn)行結(jié)果為：`00D9EA38,-572662307

所以delete之后只是告訴編譯器务热，這塊堆空間上的內(nèi)存可以回收繁成，但是并沒(méi)有讓它等于NULL吓笙，以后再new的時(shí)候可能還會(huì)申請(qǐng)到這塊地址。所以delete之后最好要加上p=NULL;

抽象鏈表模板類

#include <iostream>
#include <cstdlib>
using namespace std;
class EListEmpty{}; //鏈表為空異常
template<typename T> class ListNode; //表結(jié)點(diǎn)模板
template<typename T> class List; //鏈表模板


template<typename T> class ListNode
{
public:
    friend class List<T>; //需要讓List成為友元巾腕，否則List中的head無(wú)法訪問(wèn)data,next
    ListNode(const T &x) :data(x), next(NULL){}

private:
    T data;
    ListNode<T> *next;

};

template<typename T> class List
{
public:
    List() :head(NULL), tail(NULL){}
    virtual ~List ();
    void push_back(const T &x); //尾插入
    void push_front(const T &x);//頭插入
    void pop_back();       //尾刪除
    void pop_front();  //頭刪除
    int size();  //長(zhǎng)度
    void show(); //輸出
    void reverse(); //反向（通過(guò)建新鏈表观蓄，將舊鏈表依次加入頭部）
    
    bool IsEmpty()const { return head == 0; }
    



private:
    ListNode<T> *head; //頭指針
    ListNode<T> *tail; //尾指針
};


template<typename T> List<T>::~List()
{
    while (!IsEmpty())
    {
        pop_back();
    }
}



template<typename T> void List<T>::push_back(const T &x)
{
    ListNode<T> *p = new ListNode<T>(x);
    if (IsEmpty()) head = tail = p;
    else{
        tail->next = p;
        tail = p;
    }
    
}

template<typename T> void List<T>::push_front(const T &x)
{
    ListNode<T> *p = new ListNode<T>(x);
    if (IsEmpty()) head = tail = p;
    else{
        p->next = head;
        head = p;
    }
    
}

template<typename T> void List<T>::pop_back()
{
    if (IsEmpty()) throw EListEmpty();
    ListNode<T> *p=head;
    if (head == tail) {
        delete head;
        head = NULL;
        return;
    }
    while (p->next!=tail)
    {
        p = p->next;
    }
    tail = p;
    delete p->next;
    p->next = NULL;

}
template<typename T> void List<T>::pop_front()
{
    if (IsEmpty()) 
        throw EListEmpty();
    if (head == tail)
    {
        delete head; 
        head = NULL;
        return;
    }
    ListNode<T> *p = head;
    head = head->next;
    delete p;
}
template<typename T> int List<T>::size()
{
    int count=0;
    if (IsEmpty()) return 0;
    if (head == tail) return 1;
    ListNode<T> *p = head;
    while (p->next != tail)
    {
        p = p->next;
        ++count;
    }
    return count+1;
}
template<typename T> void List<T>::show()
{
    ListNode<T> *p = head;
    if (IsEmpty())
    {
        cout << "Empty List!" << endl; return;
    }
    else{}
    if (head == tail) cout << head->data << endl;
    
    else{
        while (p!=tail)
        {
            cout << p->data << ",";
            p = p->next;
        }
        cout << p->data << endl;
    }
}


template<typename T> void List<T>::reverse()
{
    if (head == 0 || head == tail) return;
    List<T> *a=new List<T>;
    
    ListNode<T> *p = head;
    ListNode<T> *temp;
    while (p != tail)
    {
        
        //a->push_front(p->data);
        temp = new ListNode<T>(p->data);
        if (a->head == NULL)
        {
            a->head = a->tail = temp;
        }
        else{
            temp->next = a->head;
            a->head = temp;
        }
        p = p->next;
        
    }
    a->push_front(tail->data);
    head = a->head;
    tail = a->tail;

}


int main()
{
    List<int> *p = new List<int>;
    cout<<p->size()<<endl;
    p->reverse();
    p->show();
    for (int i = 0; i < 10; i++)
        p->push_back(i);
    p->show();

    try{
        for (int i = 0; i < 7; i++)
        {
            p->pop_front();
            //cout << i << endl;
        }
            
    }
    catch ( EListEmpty &a)
    {
        cout << "鏈表已空！" << endl;
    }
    p->push_front(10);
    p->push_front(12);
    p->show();
    p->reverse();
    p->show();



    
    return 0;
}