【动手敲代码】：双向链表（C++）

  1 #include<iostream>
  2 
  3 template<class T> class Bi_Linklist;
  4 
  5 template<class T>
  6 class Node
  7 {
  8     private:
  9     Node<T> *pre;
 10     Node<T> *next;
 11     T data;
 12     public:
 13     Node():pre(NULL),next(NULL){}
 14     Node(const T item , Node<T> *p = NULL, Node<T> *n = NULL):data(item), pre(p), next(n){};
 15     friend class Bi_Linklist<T>;    
 16     Node<T>* Getpre() const
 17     {   return pre;    }
 18     void Setpre(Node<T> *p)
 19     {   pre = p;    }
 20     Node<T>* Getnext() const
 21     {   return next;    }
 22     void Setnext(Node<T> *n)
 23     {   next = n;    }
 24     T Getdata() const
 25     {   return data;    }
 26     void Setdata(T d)
 27     {   data = d;    }
 28     
 29 };
 30 
 31 
 32 
 33 template<class T>
 34 class Bi_Linklist
 35 {
 36     private:
 37     Node<T>* head;
 38     Node<T>* rear;
 39     public:
 40     Bi_Linklist()
 41     {
 42         Node<T>* p = new Node<T>();
 43         if(!p) std::cout << "memoryAllocationError" << std::endl;
 44         head = p;
 45         rear = head;
 46     }
 47     ~Bi_Linklist()
 48     {   destorylist();  }
 49     void HeadInsert(const T d)
 50     {
 51         Node<T>* node = new Node<T>(d, head, head->next);
 52         if(node == NULL)
 53             std::cout << "memoryAllocationError" << std::endl;
 54         if(head->next == NULL)
 55         {
 56         rear = node;
 57         head->next = node;
 58         }
 59         else
 60         {
 61         head->next = node;
 62         node->next->pre = node; 
 63         }
 64     }
 65     void RearInsert(const T d)
 66     {
 67         Node<T>* node = new Node<T>(d, rear);
 68         if(node == NULL)
 69             std::cout << "memoryAllocationError" << std::endl;
 70         rear->next = node;
 71         rear = node;
 72     }
 73     void CurrInsert(const Node<T>* node,const T d)
 74     {
 75         Node<T>* item = new Node<T>(d, node, node->next);
 76         if(node == NULL)
 77             std::cout << "memoryAllocationError" << std::endl;
 78             node->next = item;
 79         if(node == rear)
 80         rear = item;
 81         else
 82         item->next->pre = item;
 83     }
 84 
 85     Node<T>* Finddata(const T d)
 86     {
 87         Node<T>* search = head->next;
 88         while(search->data != d)
 89         {
 90         search = search->next;
 91         }
 92         return search;
 93     }   
 94     Node<T>* Find(int n=0)
 95     {
 96         Node<T>* search = head->next;
 97         int i = 0;
 98         for(; i < n; i++)
 99         search = search->next;
100         return search;
101     }
102     void disp() const
103     {
104         Node<T>* p = head->next;
105         while(p != NULL)
106         {
107         std::cout << p->data << std::endl;
108         p = p->next;
109         }
110     }
111     void deleteNode(Node<T>* p)
112     {
113         if(!p)
114         std::cout << "node does not exist" << std::endl;
115         p->pre->next = p->next;
116         p->next->pre = p->pre;
117         p->next = NULL;
118         p->pre = NULL;
119         delete p;
120     }
121 
122     void destorylist()
123     {
124         Node<T>* del = head->next;
125         Node<T>* p = del->next;
126         while(p != NULL)
127         {
128         deleteNode(del);
129         del = p;
130         p = p->next;
131         }
132         deleteNode(head);
133     }
134 
135 
136     Node<T>* Gethead() const
137     {
138         return head;
139     }
140     Node<T>* Getrear() const
141     {
142         return rear;
143     }
144 };