- node.h
1 #pragma once2 //创建模板3 template
4 class Node5 {6 public:7 T t;//数据8 Node *pNext;//指针域9 }; - list.h
1 #pragma once 2 #include "Node.h" 3 #include
4 using namespace std; 5 6 template 7 class List 8 { 9 public:10 Node *pHead;11 12 public:13 List();14 void add(T t);//尾部插入15 void show();//显示16 Node * find(T t);//查找17 void change(Node *p, T newt);//修改18 int getnum();//获取个数19 bool deletet(T t);20 void sort();21 void deletesame();//删除相同的元素22 bool clear();23 void rev();24 25 void insert(T oldt, T newt);26 void merge(List & list);27 28 ~List();29 }; - list.cpp
1 #include "List.h" 2 3 4 template
5 List ::List() 6 { 7 this->pHead = nullptr;//设置空节点 8 cout << "链表创建" << endl; 9 10 } 11 12 13 template 14 List ::~List() 15 { 16 cout << "链表销毁" << endl; 17 18 } 19 template 20 void List ::add(T t) 21 { 22 Node *pnew = new Node ;//分配节点 23 pnew->t = t;//赋值 24 pnew->pNext = nullptr; 25 26 27 if (pHead==nullptr) 28 { 29 30 this->pHead = pnew;//头结点 31 32 } 33 else 34 { 35 Node *p = pHead;//获取头结点位置 36 while (p->pNext!=nullptr)//循环到尾部 37 { 38 p = p->pNext; 39 40 } 41 p->pNext = pnew; 42 43 } 44 45 } 46 47 48 template 49 void List ::show() 50 { 51 52 Node *p = pHead;//获取头结点位置 53 while (p!= nullptr)//循环到尾部 54 { 55 56 cout << p->t << " "; 57 p = p->pNext; 58 59 } 60 cout << endl; 61 62 } 63 64 template 65 Node * List ::find(T t) 66 { 67 Node *p = pHead;//获取头结点位置 68 while (p != nullptr)//循环到尾部 69 { 70 if (p->t==t) 71 { 72 return p; 73 } 74 75 p = p->pNext; 76 77 } 78 return nullptr; 79 80 81 } 82 83 template 84 void List ::change(Node *p, T newt) 85 { 86 if (p==nullptr) 87 { 88 return; 89 } 90 91 p->t = newt; 92 } 93 94 template 95 int List ::getnum() 96 { 97 int i = 0; 98 Node *p = pHead;//获取头结点位置 99 while (p != nullptr)//循环到尾部100 {101 102 i++;103 p = p->pNext;104 105 }106 107 return i;108 109 110 }111 template 112 bool List ::deletet(T t)113 {114 115 Node *p = this->find(t);116 if (p==nullptr)117 {118 return false;119 }120 else121 {122 123 if (p==pHead)//头结点124 {125 pHead = p->pNext;126 delete p;127 }128 else129 {130 Node *p1, *p2;131 p1 = pHead;132 p2 = p1->pNext;133 while (p2!=p)//删除一个节点，获取前一个节点134 {135 p1 = p2;136 p2 = p2->pNext;137 138 }139 140 p1->pNext = p2->pNext;//跳过p2141 delete p2;142 143 144 145 }146 return true;147 }148 }149 150 151 template 152 void List ::sort()153 {154 for (Node *p1 = pHead; p1 != NULL;p1=p1->pNext)155 {156 for (Node *p2 = pHead; p2!= NULL; p2 = p2->pNext)157 {158 if (p1->t < p2->t)159 {160 T temp;161 temp = p1->t;162 p1->t = p2->t;163 p2 -> t = temp;164 165 }166 }167 }168 }169 170 template 171 void List ::deletesame()//重新生成172 {173 174 Node *p1, *p2;175 p1 = pHead->pNext;176 p2 = pHead;177 while (p1!=nullptr)178 {179 if (p1->t==p2->t)180 {181 //cout << "=";182 p2->pNext = p1->pNext;183 delete p1;184 p1 = p2->pNext;185 }186 else187 {188 p2 =p1;189 p1 = p1->pNext;190 191 }192 }193 }194 195 template 196 bool List ::clear()197 {198 if (pHead ==nullptr)199 {200 return false;201 }202 203 204 Node *p1, *p2;205 p1 = pHead->pNext;206 while (p1!=nullptr)207 {208 p2 = p1->pNext;209 delete p1;210 p1 = p2;211 }212 delete pHead;213 pHead = nullptr;214 215 return true;216 217 218 }219 template 220 //递归221 void List ::rev()222 {223 if (pHead==nullptr || pHead->pNext==nullptr)224 {225 return;226 } 227 else228 {229 Node *p1, *p2, *p3;230 p1 = pHead;231 p2 = p1->pNext;232 233 234 while (p2!=nullptr)235 {236 p3 = p2->pNext;237 p2->pNext = p1;238 239 p1 = p2;240 p2 = p3;241 242 }243 pHead->pNext= nullptr;244 pHead = p1;245 246 247 }248 249 250 }251 template 252 void List ::insert(T oldt, T newt)253 {254 255 Node *p = find(oldt);256 if (p!=nullptr)257 {258 259 Node *p1, *p2;260 p1 = pHead;261 p2 = p1->pNext;262 while (p2 != p)263 {264 p1 = p2;265 p2 = p2->pNext;266 267 }268 Node *pnew = new Node ;269 pnew->t = newt;270 pnew->pNext = p2;271 p1->pNext = pnew;272 }273 }274 275 template 276 void List ::merge(List & list)277 {278 Node *p = pHead;//获取头结点位置279 while (p->pNext != nullptr)//循环到尾部280 {281 282 p = p->pNext;283 284 }285 p->pNext = list.pHead;286 } - main.cpp
1 #include "List.h" 2 3 4 template
5 List ::List() 6 { 7 this->pHead = nullptr;//设置空节点 8 cout << "链表创建" << endl; 9 10 } 11 12 13 template 14 List ::~List() 15 { 16 cout << "链表销毁" << endl; 17 18 } 19 template 20 void List ::add(T t) 21 { 22 Node *pnew = new Node ;//分配节点 23 pnew->t = t;//赋值 24 pnew->pNext = nullptr; 25 26 27 if (pHead==nullptr) 28 { 29 30 this->pHead = pnew;//头结点 31 32 } 33 else 34 { 35 Node *p = pHead;//获取头结点位置 36 while (p->pNext!=nullptr)//循环到尾部 37 { 38 p = p->pNext; 39 40 } 41 p->pNext = pnew; 42 43 } 44 45 } 46 47 48 template 49 void List ::show() 50 { 51 52 Node *p = pHead;//获取头结点位置 53 while (p!= nullptr)//循环到尾部 54 { 55 56 cout << p->t << " "; 57 p = p->pNext; 58 59 } 60 cout << endl; 61 62 } 63 64 template 65 Node * List ::find(T t) 66 { 67 Node *p = pHead;//获取头结点位置 68 while (p != nullptr)//循环到尾部 69 { 70 if (p->t==t) 71 { 72 return p; 73 } 74 75 p = p->pNext; 76 77 } 78 return nullptr; 79 80 81 } 82 83 template 84 void List ::change(Node *p, T newt) 85 { 86 if (p==nullptr) 87 { 88 return; 89 } 90 91 p->t = newt; 92 } 93 94 template 95 int List ::getnum() 96 { 97 int i = 0; 98 Node *p = pHead;//获取头结点位置 99 while (p != nullptr)//循环到尾部100 {101 102 i++;103 p = p->pNext;104 105 }106 107 return i;108 109 110 }111 template 112 bool List ::deletet(T t)113 {114 115 Node *p = this->find(t);116 if (p==nullptr)117 {118 return false;119 }120 else121 {122 123 if (p==pHead)//头结点124 {125 pHead = p->pNext;126 delete p;127 }128 else129 {130 Node *p1, *p2;131 p1 = pHead;132 p2 = p1->pNext;133 while (p2!=p)//删除一个节点，获取前一个节点134 {135 p1 = p2;136 p2 = p2->pNext;137 138 }139 140 p1->pNext = p2->pNext;//跳过p2141 delete p2;142 143 144 145 }146 return true;147 }148 }149 150 151 template 152 void List ::sort()153 {154 for (Node *p1 = pHead; p1 != NULL;p1=p1->pNext)155 {156 for (Node *p2 = pHead; p2!= NULL; p2 = p2->pNext)157 {158 if (p1->t < p2->t)159 {160 T temp;161 temp = p1->t;162 p1->t = p2->t;163 p2 -> t = temp;164 165 }166 }167 }168 }169 170 template 171 void List ::deletesame()//重新生成172 {173 174 Node *p1, *p2;175 p1 = pHead->pNext;176 p2 = pHead;177 while (p1!=nullptr)178 {179 if (p1->t==p2->t)180 {181 //cout << "=";182 p2->pNext = p1->pNext;183 delete p1;184 p1 = p2->pNext;185 }186 else187 {188 p2 =p1;189 p1 = p1->pNext;190 191 }192 }193 }194 195 template 196 bool List ::clear()197 {198 if (pHead ==nullptr)199 {200 return false;201 }202 203 204 Node *p1, *p2;205 p1 = pHead->pNext;206 while (p1!=nullptr)207 {208 p2 = p1->pNext;209 delete p1;210 p1 = p2;211 }212 delete pHead;213 pHead = nullptr;214 215 return true;216 217 218 }219 template 220 //递归221 void List ::rev()222 {223 if (pHead==nullptr || pHead->pNext==nullptr)224 {225 return;226 } 227 else228 {229 Node *p1, *p2, *p3;230 p1 = pHead;231 p2 = p1->pNext;232 233 234 while (p2!=nullptr)235 {236 p3 = p2->pNext;237 p2->pNext = p1;238 239 p1 = p2;240 p2 = p3;241 242 }243 pHead->pNext= nullptr;244 pHead = p1;245 246 247 }248 249 250 }251 template 252 void List ::insert(T oldt, T newt)253 {254 255 Node *p = find(oldt);256 if (p!=nullptr)257 {258 259 Node *p1, *p2;260 p1 = pHead;261 p2 = p1->pNext;262 while (p2 != p)263 {264 p1 = p2;265 p2 = p2->pNext;266 267 }268 Node *pnew = new Node ;269 pnew->t = newt;270 pnew->pNext = p2;271 p1->pNext = pnew;272 }273 }274 275 template 276 void List ::merge(List & list)277 {278 Node *p = pHead;//获取头结点位置279 while (p->pNext != nullptr)//循环到尾部280 {281 282 p = p->pNext;283 284 }285 p->pNext = list.pHead;286 }