C++链表

1 #include<iostream> 2 #include<stdio.h> 3 using namespace std; 4 const int MAX_NUM = 5; 5 6 /** 7 *节点类 8 */ 9 template<typename T> 10 class Node { 11 public: 12 Node(T data, Node* next = NULL, Node* pre = NULL) : data(data), next(next), pre(pre) { 13 } 14 T getData() { return data; } 15 Node* getNext() { return next; } 16 Node* getPre() { return pre; } 17 void setNext(Node* next) { this->next = next; } 18 void setPre(Node* pre) { this->pre = pre; } 19 bool equal(const T& t) { return t == data; } 20 21 T data; //数据 22 Node *next; //后向指针 23 Node *pre; //前向指针 24 }; 25 26 27 /** 28 *链表类 29 */ 30 template<typename T> 31 class List { 32 public: 33 List() :size(0) { 34 head = tail = NULL; 35 } 36 int length() { return size; } 37 void pushBack(const T& t); //在尾后添加数据 38 void pushFront(const T& t); //在头前添加数据 39 T search_byIndex(int index); //根据下标获取对应元素 40 Node<T>* search_byData(const T& data); //根据数据获取对应节点 41 void list_all_element(); //遍历链表的所有元素并输出 42 Node<T>* getP_node_ByIndex(int index); //根据索引找到对应节点并返回 43 void delete_byIndex(int index); //根据索引删除对应节点 44 void delete_byData(const T& data); //按照数据查找并删除 45 46 bool empty() { return number == 0; } //判断是否为空 47 Node<T> * getHead() { return head; } //获得头指针a 48 Node<T> * getTail() { return tail; } //获得尾指针 49 int getSize() { return size; } //获得当前元素总量 50 void unique(); //去除重复元素 51 Node<T>* delete_between(Node<T>*first, Node<T>*end); //删除两节点指针之间的元素，并返回被删除节点之前的节点的指针 52 ~List() { 53 //析构时讲占用堆区的内存释放出来 54 if (size != 0) { 55 Node<T> *pre = NULL; 56 for (int i = 0; i < size; i++) { 57 pre = tail->getPre(); 58 delete[] tail; 59 tail = pre; 60 } 61 } 62 } 63 private: 64 Node<T> *head; 65 Node<T> *tail; 66 int size; 67 }; 68 69 /** 70 *在尾后添加数据 71 */ 72 template<typename T> 73 void List<T>::pushBack(const T& t) { 74 Node<T>* node = new Node<T>(t); 75 //第一次添加 76 if (size == 0) { 77 head = tail = node; 78 size++; //计数 79 } 80 else {//非第一次添加 81 tail->setNext(node); 82 node->setPre(tail); 83 tail = node; 84 size++; //计数 85 } 86 } 87 88 /** 89 *在头前添加数据 90 */ 91 template<typename T> 92 void List<T>::pushFront(const T& t) { 93 Node<T>* node = new Node<T>(t); 94 head->setPre(node); 95 node->setPre(NULL); 96 node->setNext(head); 97 head = node; 98 size++; //计数 99 } 100 101 /** 102 *根据下标获取对应元素 103 */ 104 template<typename T> 105 T List<T>::search_byIndex(int index) { 106 return this->getP_node_ByIndex(index)->getData(); 107 } 108 109 /** 110 *根据数据获取对应节点 111 */ 112 template<typename T> 113 Node<T>* List<T>::search_byData(const T& data) { 114 Node<T>* temp = head; 115 int i; 116 for (i = 0; i < size; i++) { 117 if (temp->equal(data)) { 118 break; 119 } 120 temp = temp->getNext(); 121 } 122 if (i == size) { 123 cout << "NO FOUND!!!!(return NULL)" << endl; 124 return NULL; 125 } 126 else { 127 return temp; 128 } 129 } 130 131 /** 132 *遍历链表的所有元素并输出 133 */ 134 template<typename T> 135 void List<T>::list_all_element() { 136 for (int i = 0; i < size; i++) { 137 cout.width(5); 138 cout.setf(ios::left); 139 cout << this->search_byIndex(i) << "\t"; 140 } 141 } 142 143 144 /** 145 *根据索引找到对应节点并返回 146 */ 147 template<typename T> 148 Node<T>* List<T>::getP_node_ByIndex(int index) { 149 Node<T>* target = head; 150 if (index >= size || index < 0) { 151 printf("Invalid index : The size of List is %d, the index your input is %d.", size, index); 152 getchar(); 153 exit(0); 154 } 155 else { 156 for (int i = 0; i < index; i++) { 157 target = target->getNext(); 158 } 159 } 160 return target; 161 } 162 163 164 /** 165 *根据索引删除对应节点 166 */ 167 template<typename T> 168 void List<T>::delete_byIndex(int index) { 169 if (size != 0) { 170 Node<T>* target = this->getP_node_ByIndex(index); 171 //删除非头结点 172 if (target != head) { 173 target->getPre()->setNext(target->getNext()); 174 delete[] target; 175 size--; 176 } 177 else {//删除头结点 178 head = head->getNext(); 179 delete[] target; 180 size--; 181 } 182 } 183 else { 184 cout << "The list is NULL!!" << endl; 185 } 186 } 187 188 template<typename T> 189 void List<T>::delete_byData(const T& data) { 190 if (size != 0) { 191 Node<T>* target = this->search_byData(data); 192 //删除非头结点 193 if (target != head && target != NULL) { 194 target->getPre()->setNext(target->getNext()); 195 delete[] target; 196 size--; 197 } 198 else if (target == head) {//删除头结点 199 head = head->getNext(); 200 delete[] target; 201 size--; 202 } 203 204 } 205 else { 206 cout << "The list is NULL!!" << endl; 207 } 208 } 209 210 211 template<class T> 212 void List<T>::unique() { 213 T temp; 214 Node<T>* tt = head; 215 while (tt->next) { 216 temp = tt->data; 217 for (Node<T>* n = tt->next; n != NULL; n = n->next) { 218 if (temp == n->data) 219 n = delete_between(n, n)->next; 220 if (!n) { break; } 221 } 222 tt = tt->next; 223 } 224 } 225 226 //删除两节点指针之间的元素，并返回被删除节点之前的节点的指针,删除的是头节点则返回头指针 227 template<class T> 228 Node<T>* List<T>::delete_between(Node<T>* first, Node<T>* end) { 229 //删除的节点中包括尾节点 230 if (end == tail) { 231 Node<T>* pre = first->pre; //要删除的节点之前的元素 232 Node<T>* temp; //用来记录要delete掉的节点 233 Node<T>* n = pre->next; //用来指向被delete掉的节点的下一个节点 234 for (temp = pre->next; temp->next != NULL; ) { 235 n = n->next; 236 delete[] temp; 237 temp = n; 238 size--; 239 } 240 //以上循环删除到尾节点之前 241 delete[] temp; 242 size--; 243 //将删除后的尾节点的next置为NULL 244 pre->next = NULL; 245 tail = pre; 246 return pre; 247 } 248 //删除的节点中不包括头节点 249 else if (first != head) { 250 Node<T>* pre = first->pre; 251 Node<T>* next = end->next; 252 for (Node<T>* temp = first; temp != next; ) { 253 temp = temp->next; 254 delete[] temp->pre; 255 size--; 256 } 257 pre->next = next; 258 pre->next->pre = pre; 259 return pre; 260 } 261 //删除的第一个节点是头节点 262 else { 263 Node<T>* next = end->next; 264 for (Node<T>* temp = head; temp != next; ) { 265 temp = temp->next; 266 delete[] temp->pre; 267 size--; 268 } 269 head = next; 270 if (head) { head->pre = NULL; } 271 return head; 272 } 273 } 274 275 276 277 int main() { 278 List<int> list; 279 int node_int[MAX_NUM] = {1,2,1,2,5}; 280 int a; 281 Node<int> * temp; 282 for (int i = 0; i < MAX_NUM; i++) { 283 list.pushBack(node_int[i]); 284 } 285 /*for(int i = 0; i < 5; i++){ 286 cout << list.getData(i) << endl; 287 }*/ 288 289 290 291 ////通过索引删除 292 //while(cin >> a){ 293 // list.delete_byIndex(a); 294 // list.list_all_element(); 295 //} 296 297 ////通过数据查找 298 //while(cin >> a){ 299 // temp = list.search_byData(a); 300 // if(temp != NULL){ 301 // cout << list.search_byData(a)->getData() << endl; 302 // } 303 //} 304 305 ////按照数据查找并删除 306 //while(cin >> a){ 307 // list.delete_byData(a); 308 // list.list_all_element(); 309 //} 310 311 312 ////在头前添加数据 313 //while (cin >> a) { 314 // list.pushFront(a); 315 // list.list_all_element(); 316 //} 317 318 319 //去除重复元素测试 320 list.list_all_element(); 321 list.unique(); 322 list.list_all_element(); 323 324 }

 

转载于:https://www.cnblogs.com/qjm253/p/5629765.html

相关资源：创建和遍历链表