list.h

二叉树

//定义list模板类，


#ifndef TLIST
#define TLIST

template<class T>
class TNode {                              //define anode
public:
    T info;                                   // the datas are defined as public,so all other functions can call it
    TNode<T> *next;
    TNode(int el, TNode<T> *ptr = 0) {   //default parameter
        info = el; next = ptr;
    }
};

template<class T>
class TList {                               //define a list
public:
    TList() {
        head = tail = 0;
    }
    ~TList();
    bool isEmpty() {
        return head == 0;
    }
    TNode<T> * getHead();
    void addToHead(T);
    void addToTail(T);
    T  deleteFromHead(); // delete the head and return its info;
    T  deleteFromTail(); // delete the tail and return its info;
    void deleteNode(T);
    bool isInList(T) const;
    void printAll() const;
	//TNode* reverse();
private:
    TNode<T> *head, *tail;
};

template<class T>
TList<T>::~TList() {
    for (TNode *p; !isEmpty(); ) {
        p = head->next;
        delete head;                      //其实delete掉的是head指向的节点
        head = p;
    }
}

template<class T>
void TList<T>::addToHead(T el) {
    head = new TNode(el,head);
    if (tail == 0)
       tail = head;
}

template<class T>
void TList<T>::addToTail(T el) {
    if (tail != 0) {      // if list not empty;
         tail->next = new TNode(el);
         tail = tail->next;
    }
    else head = tail = new TNode(el);
}

template<class T>
T TList<T>::deleteFromHead() {                       //can only delete one node
    T el = head->info;
    TNode *tmp = head;
    if (head == tail)     // if only one node on the list;
         head = tail = 0;
    else head = head->next;
    delete tmp;
    return el;
}

template<class T>
T TList<T>::deleteFromTail() {                     //can only delete one node
    T el = tail->info;
    if (head == tail) {   // if only one node on the list;
         delete head;
         head = tail = 0;
    }
    else {                // if more than one node in the list,
         TNode *tmp; // find the predecessor of tail;
         for (tmp = head; tmp->next != tail; tmp = tmp->next);
         delete tail;
         tail = tmp;      // the predecessor of tail becomes tail;
         tail->next = 0;
    }
    return el;
}

template<class T>
void TList<T>::deleteNode(T el) {
    if (head != 0)                     // if non-empty list;
         if (head == tail && el == head->info) { // if only one
              delete head;                       // node on the list;
              head = tail = 0;
         }
         else if (el == head->info) {  // if more than one node on the list
              TNode *tmp = head;
              head = head->next;
              delete tmp;              // and old head is deleted;
         }
         else {                        // if more than one node in the list
              TNode *pred, *tmp;
              for (pred = head, tmp = head->next; // and a non-head node
                   tmp != 0 && !(tmp->info == el);// is deleted;
                   pred = pred->next, tmp = tmp->next);
              if (tmp != 0) {
                   pred->next = tmp->next;
                   if (tmp == tail)
                      tail = pred;
                   delete tmp;
              }
         }
}

template<class T>
bool TList<T>::isInList(T el) const {
    TNode<T> *tmp;
    for (tmp = head; tmp != 0 && !(tmp->info == el); tmp = tmp->next);
    return tmp != 0;
}

template<class T>
void TList<T>::printAll() const {
	if(head!=0)
	{
        for (TNode *tmp = head; tmp != 0; tmp = tmp->next)
            cout << tmp->info << " ";
	    cout << endl;
	}
	else
		cout<<"The list is empty!\n";
    
}


#endif