数据结构(C++)之Double Linked List实践

  1 //double linked list (type int),the position starts from 0
  2 #include <iostream>
  3 using namespace std;
  4 
  5 //Class Node
  6 class Node
  7 {
  8 public:
  9     Node();
 10     Node(int val);
 11     ~Node();
 12 
 13     void setVal(int val);
 14     int getVal();
 15 
 16     Node* prior;   //指向前节点指针
 17     Node* next;   //指向后节点指针
 18 
 19 private:
 20     int val = 0;
 21 };
 22 
 23 Node::Node()
 24 {
 25 }
 26 
 27 Node::Node(int val)
 28 {
 29     this->val = val;
 30     prior = next = nullptr;
 31 }
 32 
 33 Node::~Node()
 34 {
 35 }
 36 
 37 void Node::setVal(int val)
 38 {
 39     this->val = val;
 40 }
 41 
 42 int Node::getVal()
 43 {
 44     return this->val;
 45 }
 46 
 47 //Class DoubleLinkedList
 48 class DLlist
 49 {
 50 public:
 51 
 52     DLlist(int size);
 53     ~DLlist();
 54 
 55     int getSize();
 56 
 57     void insert(int num, int pos);   //在两节点间插入，插入位置的前后节点必须都存在
 58 
 59     void deleteList(int pos);   //删除节点，删除位置的前后节点必须都存在
 60 
 61     void addFirst(int element);     //pushFront
 62 
 63     void addLast(int element);   //pushBack
 64 
 65     int removeFirst();
 66 
 67     int removeLast();
 68 
 69     int returnNth(int pos);
 70 
 71     bool isEmpty();
 72 
 73     void printList();
 74 
 75 
 76     void Clear();
 77 
 78 private:
 79     int size = 0;
 80     Node* head;  //指向头节点的指针
 81     Node* tail;     //指向尾节点的指针
 82 
 83     Node* GetPointer(int pos);   //查找节点
 84 
 85 };
 86 
 87 DLlist::DLlist(int size)
 88 {
 89     this->size = size;
 90     head = new Node;
 91     head->prior = nullptr;
 92     head->next = nullptr;
 93     tail = head;
 94     for (int i = 0; i < this->size; i++)
 95     {
 96         int v;
 97         cout << "Enter the value of No. " << i + 1 << " Node: ";
 98         cin >> v;
 99         if (i == 0)
100         {
101             head->setVal(v);
102         }
103         else
104         {
105             Node* temp = new Node;
106             temp->setVal(v);
107             temp->next = nullptr;
108             temp->prior = tail;
109             tail->next = temp;
110             tail = temp;
111         }
112     }
113 }
114 
115 DLlist::~DLlist()
116 {
117     Clear();
118 }
119 
120 int DLlist::getSize()
121 {
122     return this->size;
123 }
124 
125 void DLlist::insert(int num, int pos)
126 {
127     Node* temp = new Node;
128     Node* position;
129     temp->setVal(num);
130     position = GetPointer(pos);
131     (position->prior)->next = temp;
132     temp->next = position;
133     temp->prior = position->prior;
134     position->prior = temp;
135     size++;
136 }
137 
138 void DLlist::deleteList(int pos)
139 {
140     Node* position;
141     position = GetPointer(pos);
142     (position->prior)->next = position->next;
143     (position->next)->prior = position->prior;
144     delete position;
145     size--;
146 }
147 
148 void DLlist::addFirst(int element)
149 {
150     if (head == nullptr)
151     {
152         head->setVal(element);
153         head->prior = nullptr;
154         head->next = nullptr;
155         tail = head;
156         size++;
157     }
158     else
159     {
160         /*我们要在头结点前再插入一个结点，需要先创建一个新的结点，将头结点的值保存在新节点，然后让新节点的下
161         个结点指向头结点的下一个结点，再让新节点的prior指向头结点，这样就将新节点与原来的链表融合了，然后我
162         们将头结点的数据换成element即可*/
163 
164         Node* temp = new Node;
165         temp->setVal(head->getVal());
166         temp->next = head->next;
167         temp->prior = head;
168         if (size > 1)
169         {
170             (head->next)->prior = temp;
171         }
172         head->next = temp;
173         head->setVal(element);
174         size++;
175     }
176 }
177 
178 void DLlist::addLast(int element)
179 {
180     if (head == nullptr)
181     {
182         head->setVal(element);
183         head->prior = nullptr;
184         head->next = nullptr;
185         tail = head;
186         size++;
187     }
188     else
189     {
190         Node* temp = new Node;
191         temp->setVal(tail->getVal());
192         temp->prior = tail->prior;
193         temp->next = tail;
194         if (size - 1 != 0)
195         {
196             (tail->prior)->next = temp;
197         }
198         tail->prior = temp;
199         tail->setVal(element);
200         size++;
201     }
202 }
203 
204 int DLlist::removeFirst()
205 {
206     int v = head->getVal();
207 
208     head = head->next;
209     if (size > 1)
210     {
211         head->prior = nullptr;
212     }
213 
214     size--;
215     return v;
216 }
217 
218 int DLlist::removeLast()
219 {
220     int v = tail->getVal();
221 
222     tail = tail->prior;
223     if (size>1)
224     {
225         tail->next = nullptr;
226     }
227 
228     size--;
229     return v;
230 }
231 
232 int DLlist::returnNth(int pos)
233 {
234     return GetPointer(pos)->getVal();
235 }
236 
237 bool DLlist::isEmpty()
238 {
239     if (size == 0)
240     {
241         return true;
242     }
243     else
244     {
245         return false;
246     }
247 }
248 
249 void DLlist::printList()
250 {
251     for (int i = 0; i < size; i++)
252     {
253         cout << "No. " << i + 1 << " = " << GetPointer(i)->getVal() << endl;
254     }
255 }
256 
257 void DLlist::Clear()
258 {
259     while (head != nullptr)
260     {
261         Node * temp = head->next;
262         delete head;
263         head = temp;
264     }
265     tail = nullptr;
266     size = 0;
267 }
268 
269 Node* DLlist::GetPointer(int pos)
270 {
271     Node* pNode = nullptr;
272     if (pos<0 || pos>size - 1)
273     {
274         cout << "Out of range! " << endl;
275         return nullptr;
276     }
277     else
278     {
279         pNode = head;
280         for (int i = 0; i < pos; i++)
281         {
282             pNode = pNode->next;
283         }
284         return pNode;
285     }
286 }
287 
288 int main()
289 {
290     DLlist d(3);
291     cout << endl;
292     cout << "Size: " << d.getSize() << endl;
293     d.printList();
294     cout << endl;
295 
296     cout << "Insert 10 at position 1" << endl;
297     d.insert(10, 1);
298     cout << "Size: " << d.getSize() << endl;
299     d.printList();
300 
301     cout << endl;
302     cout << "Addfirst 100" << endl;
303     d.addFirst(100);
304     cout << "Now No.1's value= " << d.returnNth(0) << endl;
305     d.printList();
306 
307     cout << endl;
308     cout << "Remove last" << endl;
309     d.removeLast();
310     d.printList();
311 
312     cout << endl;
313     cout << "Remove first" << endl;
314     d.removeFirst();
315     d.printList();
316 
317     cout << endl;
318     d.Clear();
319     cout << "Use Clear()" << endl;
320     cout << "isEmpty: " << boolalpha << d.isEmpty() << endl;
321 
322     system("pause");
323     return 0;
324 }

取消int类型，加入模板

  1 //double linked list ,the position starts from 0
  2 #include <iostream>
  3 #include <iomanip>
  4 using namespace std;
  5 
  6 //Class Node
  7 template <typename T>
  8 class Node
  9 {
 10 public:
 11     Node();
 12     Node(T val);
 13     ~Node();
 14 
 15     void setVal(T val);
 16     T getVal();
 17 
 18     Node* prior;   //指向前节点指针
 19     Node* next;   //指向后节点指针
 20 
 21 private:
 22     T val ;
 23 };
 24 
 25 template<typename T>
 26 Node<T>::Node()
 27 {
 28     this->val = T();
 29 }
 30 
 31 template<typename T>
 32 Node<T>::Node(T val)
 33 {
 34     this->val = val;
 35     prior = next = nullptr;
 36 }
 37 
 38 
 39 template<typename T>
 40 Node<T>::~Node()
 41 {
 42 }
 43 
 44 
 45 template<typename T>
 46 void Node<T>::setVal(T val)
 47 {
 48     this->val = val;
 49 }
 50 
 51 template<typename T>
 52 T Node<T>::getVal()
 53 {
 54     return this->val;
 55 }
 56 
 57 //Class DoubleLinkedList
 58 template<typename T>
 59 class DLlist
 60 {
 61 public:
 62 
 63     DLlist(int size);
 64     ~DLlist();
 65 
 66     int getSize();
 67 
 68     void insert(T num, int pos);   //在两节点间插入，插入位置的前后节点必须都存在
 69 
 70     void deleteList(int pos);   //删除节点，删除位置的前后节点必须都存在
 71 
 72     void addFirst(T element);     //pushFront
 73 
 74     void addLast(T element);   //pushBack
 75 
 76     T removeFirst();
 77 
 78     T removeLast();
 79 
 80     T returnNth(int pos);
 81 
 82     bool isEmpty();
 83 
 84     void printList();
 85 
 86 
 87     void Clear();
 88 
 89 private:
 90     int size = 0;
 91     Node<T>* head;  //指向头节点的指针
 92     Node<T>* tail;     //指向尾节点的指针
 93 
 94     Node<T>* GetPointer(int pos);   //查找节点
 95 
 96 };
 97 
 98 template<typename T>
 99 DLlist<T>::DLlist(int size)
100 {
101     this->size = size;
102     head = new Node<T>;
103     head->prior = nullptr;
104     head->next = nullptr;
105     tail = head;
106     for (int i = 0; i < this->size; i++)
107     {
108         T v;
109         cout << "Enter the value of No. " << i + 1 << " Node: ";
110         cin >> v;
111         if (i == 0)
112         {
113             head->setVal(v);
114         }
115         else
116         {
117             Node<T>* temp = new Node<T>;
118             temp->setVal(v);
119             temp->next = nullptr;
120             temp->prior = tail;
121             tail->next = temp;
122             tail = temp;
123         }
124     }
125 }
126 
127 template<typename T>
128 DLlist<T>::~DLlist()
129 {
130     Clear();
131 }
132 
133 template<typename T>
134 int DLlist<T>::getSize()
135 {
136     return this->size;
137 }
138 
139 template<typename T>
140 void DLlist<T>::insert(T num, int pos)
141 {
142     Node<T>* temp = new Node<T>;
143     Node<T>* position;
144     temp->setVal(num);
145     position = GetPointer(pos);
146     (position->prior)->next = temp;
147     temp->next = position;
148     temp->prior = position->prior;
149     position->prior = temp;
150     size++;
151 }
152 
153 template<typename T>
154 void DLlist<T>::deleteList(int pos)
155 {
156     Node<T>* position;
157     position = GetPointer(pos);
158     (position->prior)->next = position->next;
159     (position->next)->prior = position->prior;
160     delete position;
161     size--;
162 }
163 
164 template<typename T>
165 void DLlist<T>::addFirst(T element)
166 {
167     if (head == nullptr)
168     {
169         head->setVal(element);
170         head->prior = nullptr;
171         head->next = nullptr;
172         tail = head;
173         size++;
174     }
175     else
176     {
177         /*我们要在头结点前再插入一个结点，需要先创建一个新的结点，将头结点的值保存在新节点，然后让新节点的下
178         个结点指向头结点的下一个结点，再让新节点的prior指向头结点，这样就将新节点与原来的链表融合了，然后我
179         们将头结点的数据换成element即可*/
180 
181         Node<T>* temp = new Node<T>;
182         temp->setVal(head->getVal());
183         temp->next = head->next;
184         temp->prior = head;
185         if (size > 1)
186         {
187             (head->next)->prior = temp;
188         }
189         head->next = temp;
190         head->setVal(element);
191         size++;
192     }
193 }
194 
195 template<typename T>
196 void DLlist<T>::addLast(T element)
197 {
198     if (head == nullptr)
199     {
200         head->setVal(element);
201         head->prior = nullptr;
202         head->next = nullptr;
203         tail = head;
204         size++;
205     }
206     else
207     {
208         Node<T>* temp = new Node<T>;
209         temp->setVal(tail->getVal());
210         temp->prior = tail->prior;
211         temp->next = tail;
212         if (size - 1 != 0)
213         {
214             (tail->prior)->next = temp;
215         }
216         tail->prior = temp;
217         tail->setVal(element);
218         size++;
219     }
220 }
221 
222 template<typename T>
223 T DLlist<T>::removeFirst()
224 {
225     T v = head->getVal();
226 
227     head = head->next;
228     if (size > 1)
229     {
230         head->prior = nullptr;
231     }
232 
233     size--;
234     return v;
235 }
236 
237 template<typename T>
238 T DLlist<T>::removeLast()
239 {
240     T v = tail->getVal();
241 
242     tail = tail->prior;
243     if (size>1)
244     {
245         tail->next = nullptr;
246     }
247 
248     size--;
249     return v;
250 }
251 
252 template<typename T>
253 T DLlist<T>::returnNth(int pos)
254 {
255     return GetPointer(pos)->getVal();
256 }
257 
258 template<typename T>
259 bool DLlist<T>::isEmpty()
260 {
261     if (size == 0)
262     {
263         return true;
264     }
265     else
266     {
267         return false;
268     }
269 }
270 
271 template<typename T>
272 void DLlist<T>::printList()
273 {
274     for (int i = 0; i < size; i++)
275     {
276         cout << "No. " << i + 1 << " = " <<setiosflags(ios::fixed)<<setprecision(2)<<GetPointer(i)->getVal() << endl;
277     }
278 }
279 
280 template<typename T>
281 void DLlist<T>::Clear()
282 {
283     while (head != nullptr)
284     {
285         Node<T>* temp = head->next;
286         delete head;
287         head = temp;
288     }
289     tail = nullptr;
290     size = 0;
291 }
292 
293 template<typename T>
294 Node<T>* DLlist<T>::GetPointer(int pos)
295 {
296     Node<T>* pNode = nullptr;
297     if (pos<0 || pos>size - 1)
298     {
299         cout << "Out of range! " << endl;
300         return nullptr;
301     }
302     else
303     {
304         pNode = head;
305         for (int i = 0; i < pos; i++)
306         {
307             pNode = pNode->next;
308         }
309         return pNode;
310     }
311 }
312 
313 int main()
314 {
315     DLlist<double> d(3);
316     cout << endl;
317     cout << "Size: " << d.getSize() << endl;
318     d.printList();
319     cout << endl;
320 
321     cout << "Insert 10.0 at position 1" << endl;
322     d.insert(10.0, 1);
323     cout << "Size: " << d.getSize() << endl;
324     d.printList();
325 
326     cout << endl;
327     cout << "Addfirst 100.0" << endl;
328     d.addFirst(100.0);
329     cout << "Now No.1's value= " << d.returnNth(0) << endl;
330     d.printList();
331 
332     cout << endl;
333     cout << "Remove last" << endl;
334     d.removeLast();
335     d.printList();
336 
337     cout << endl;
338     cout << "Remove first" << endl;
339     d.removeFirst();
340     d.printList();
341 
342     cout << endl;
343     d.Clear();
344     cout << "Use Clear()" << endl;
345     cout << "isEmpty: " << boolalpha << d.isEmpty() << endl;
346 
347     system("pause");
348     return 0;
349 }