本程序无法实现的功能就是想要头结点的数据域和其他结点的数据域类型不同，由于使用模板如果在构造函数的时候设置头结点的数据域类型,那么实例化的时候(LinkList<int>link;)其他结点数据域也要跟着变成整型，如果将头结点在构造函数中提前定义好(ListNode<int>*L=new ListNode<int>;),那么在类中封装的方法中难免会遇到头结点发生拷贝(ListNode<DataType>*temp=L;)则会因为DataType和int类型不匹配而发生错误(static_cast<ListNode<DataType>*>L也不起作用)
LinkList.hpp文件：
1 #pragma once
2 #include<iostream>
3 #include<stdexcept>
4 using std::cout;
5 using std::endl;
6 using std::cin;
7 using std::string;
8 /*
9 * DataType 数据域的类型
10 */
11
12 template<class DataType>
13 struct ListNode
14 {
15 DataType data_;
16 ListNode<DataType>* next_;
17 ListNode() :next_(nullptr){}
18 };
19
20 /*
21 * 这里面注意类中的DataType,AdressType和结构体中的DataType,AdressType无关，完全可以用其他字母，但为了将类和结构体统一所以写成一样的
22 * 因为实现不知道数据域指针域到底是什么类型所以用模板
23 */
24 template<class DataType>
25 class LinkList
26 {
27 public:
28 LinkList();//初始化
29 ~LinkList();//销毁链表，包括删除头结点和头指针
30 bool Empty();//判断链表是否为空链表，也就是头结点的指针域是否是空指针
31 void RemoveAll();//删除所有结点（除头指针，头结点）
32 int LinkSize();//判断链表的长度（首元结点及以后有几个结点）
33 DataType FindIndexData(int index);//查找链表中下标为index的元素的数据域
34 ListNode<DataType>* FindIndexAddress(int index);//查找链表中下标为index的元素的指针域
35 ListNode<DataType>* FindDataAddress(DataType data);//根据指定的数据，获取该数据所在的结点地址
36 int FindDataIndex(DataType data);//根据指定的数据，获取该数据所在的结点索引值
37 void Insert(int index, DataType data, ListNode<DataType>* newnode);//在索引值为index前插入结点,链表不能为空
38 void DeleteNode(int index);//删除结点
39 void AddNode_input(int num);//头插法创建新链表,手动输入数据
40 void AddNode(ListNode<DataType>* newnode, DataType data);//头插法创建新链表,调用函数
41 void PushBack_input(int num);//尾插法，手动输入数据
42 void PushBack(ListNode<DataType>* newnode, DataType data);//尾插法，调用函数
43
44 ListNode<DataType>* L;//头指针（根据定义头指针是指向链表头结点的指针，指向结点，因此头指针应该为结点类型）
45 int linkList_size = 0;//链表的长度
46
47 };
48
49 /*
50 * 默认构造函数
51 * 初始化链表，开辟一块堆区内存作为头结点，让头指针指向头结点
52 * L 头指针
53 */
54 template<class DataType>
55 LinkList<DataType>::LinkList()
56 {
57 L = new ListNode<DataType>;//为头结点开辟堆区内存，并将头指针指向该堆区内存
58 }
59
60 /*
61 * 析构函数
62 * 删除头结点，头指针，以及其他所有结点
63 * 方法是：首先调用RemoveAll函数删除所有结点，然后删除头结点和头指针
64 */
65 template<class DataType>
66 LinkList<DataType>::~LinkList()
67 {
68 if (L->next_==0)
69 {
70 delete L;
71 L = nullptr;
72 return;
73 }
74 RemoveAll();
75 delete L;
76 L = nullptr;
77 }
78
79 /*
80 * 判断链表是否为空的函数
81 */
82 template<class DataType>
83 bool LinkList<DataType>::Empty()
84 {
85 if (linkList_size == 0)
86 {
87 return true;
88 }
89 else
90 {
91 return false;
92 }
93 }
94
95 /*
96 * 删除除头结点头指针外的其他所有结点
97 * 方法是：首先用L_temp记录首元结点
98 *
99 * 然后将L_temp指向的首元结点的地址赋给temp
100 * 然后将下一个结点的地址赋给L_temp
101 * 并用temp去释放首元结点（当前结点），其他结点同理
102 *
103 * temp 指向当前结点，作用是释放当前结点，
104 * L_temp 指向当前结点的下一个结点
105 */
106 template<class DataType>
107 void LinkList<DataType>::RemoveAll()
108 {
109
110 ListNode<DataType>* L_temp = L->next_;
111
112 ListNode<DataType>* temp;
113 if (L->next_==nullptr)
114 {
115 cout << "The LinkList is empty" << endl;
116 return;
117 }
118 while (L_temp!=nullptr)
119 {
120 temp = L_temp;
121 L_temp = L_temp->next_;
122 delete temp;
123 }
124 temp = nullptr;
125 linkList_size = 0;//链表长度置为0
126 L->next_ = nullptr;
127 }
128
129 /*
130 * 计算链表的长度
131 */
132 template<class DataType>
133 int LinkList<DataType>::LinkSize()
134 {
135 return linkList_size;
136 }
137
138 /*
139 * 查找链表中下标为index的元素的数据域函数
140 * 注意此处返回值类型是DataType，一个未知的类型，当我进行不正当的操作的时候，比如索引越界，我们就应该终止这个函数调用
141 * 但是我没法像普通函数那样return-1;return;因为我根本就不知道返回值类型是什么，目前看来只有异常才能解决这个问题
142 * 查找链表中下标为index的元素的数据域函数
143 * 链表是顺序存储只能按顺序查找
144 * 判断num是不是我们要找的索引值（index）不是就让find指向下一个结点
145 * find 指向待判断是否是查找结点的结点
146 * num 记录find的当前指向结点的索引值
147 */
148 template<class DataType>
149 DataType LinkList<DataType>::FindIndexData(int index)
150 {
151 ListNode<DataType>* find = L->next_;
152 int num = 0;
153 try
154 {
155 if (L->next_ == nullptr)
156 {
157 throw - 1;
158 }
159 if ((index < 0) || (index > linkList_size - 1))
160 {
161 throw std::runtime_error("LinkList subscript out of range");
162 }
163 }
164 catch (std::runtime_error& err)
165 {
166 cout << "************************" << endl;
167 cout << "You meet one abnormal:" << endl;
168 cout << err.what() << endl;
169 cout << "The range of subscript is " << "[" << 0 << "," << linkList_size-1 << "]" << endl;
170 cout << "Please input the right index:" << endl;
171 int right_index;
172 cin >> right_index;
173 index = right_index;
174 }
175 catch (const int&)
176 {
177 cout << "************************" << endl;
178 cout << "You meet one abnormal:" << endl;
179 std::cerr << "This is a empty linklist" << endl;
180 std::terminate();
181 }
182 while(num!=index)
183 {
184 ++num;
185 find = find->next_;
186 }
187 return find->data_;
188 }
189
190 /*
191 * 查找链表中下标为index的元素的指针域函数(从首元结点查起)
192 */
193 template<class DataType>
194 ListNode<DataType>* LinkList<DataType>::FindIndexAddress(int index)
195 {
196 ListNode<DataType>* find = L->next_;
197 int num = 0;
198 try
199 {
200 if (L->next_==nullptr)
201 {
202 throw - 1;
203 }
204 if ((index < 0) || (index > linkList_size - 1))
205 {
206 throw std::runtime_error("LinkList subscript out of range");
207 }
208 }
209 catch (std::runtime_error& err)
210 {
211 cout << "************************" << endl;
212 cout << "You meet one abnormal:" << endl;
213 cout << err.what() << endl;
214 cout << "The range of subscript is " << "[" << 0 << "," << linkList_size-1 << "]" << endl;
215 cout << "Please input the right index:" << endl;
216 int right_index;
217 cin >> right_index;
218 index = right_index;
219 }
220 catch (const int&)
221 {
222 cout << "************************" << endl;
223 cout << "You meet one abnormal:" << endl;
224 std::cerr << "This is a empty linklist" << endl;
225 std::terminate();
226 }
227 while (num != index)
228 {
229 ++num;
230 find = find->next_;
231 }
232 return find;
233 }
234
235 /*
236 * 根据指定的数据，获取该数据所在的结点地址函数,没有找到则返回空
237 */
238 template<class DataType>
239 ListNode<DataType>* LinkList<DataType>::FindDataAddress(DataType data)
240 {
241 ListNode<DataType>* find = L->next_;
242 while ((find != nullptr)&&(find->data_!=data))
243 {
244 find = find->next_;
245 }
246 return find;
247 }
248
249 /*
250 * 根据指定的数据，获取该数据所在的结点索引值函数,没有就返回-1
251 * index 用来记录find所指结点的索引值
252 */
253 template<class DataType>
254 int LinkList<DataType>::FindDataIndex(DataType data)
255 {
256 int index=0;
257 ListNode<DataType>* find = L->next_;
258 while (find != nullptr)
259 {
260 if (find->data_ == data)
261 {
262 return index;
263 }
264 ++index;
265 find = find->next_;
266 }
267 return -1;
268 }
269
270 /*
271 * 在索引值为index前插入结点函数,支持尾插,链表不能为空
272 * 方法是：将index-1结点的指针域赋给newnode的指针域，然后将newnode的地址赋给index-1位置结点的指针域
273 * 也就是说想要在index插入实际上操作的是n-1
274 */
275 template<class DataType>
276 void LinkList<DataType>::Insert(int index, DataType data, ListNode<DataType>* newnode)
277 {
278 ListNode<DataType>* find = L;
279 int num = -1;
280 try
281 {
282 if (L->next_ == nullptr)
283 {
284 throw - 1;
285 }
286 if ((index < 0) || (index > linkList_size - 1))
287 {
288 throw std::runtime_error("LinkList subscript out of range");
289 }
290 }
291 catch (std::runtime_error& err)
292 {
293 cout << "************************" << endl;
294 cout << "You meet one abnormal:" << endl;
295 cout << err.what() << endl;
296 cout << "The range of subscript is " << "[" << 0 << "," << linkList_size-1 << "]" << endl;
297 cout << "Please input the right index:" << endl;
298 int right_index;
299 cin >> right_index;
300 index = right_index;
301 }
302 catch (const int&)
303 {
304 cout << "************************" << endl;
305 cout << "You meet one abnormal:" << endl;
306 std::cerr << "This is a empty linklist" << endl;
307 std::terminate();
308 }
309 while (num != (index-1))
310 {
311 ++num;
312 find = find->next_;
313 }
314 newnode->next_ = find->next_;
315 find->next_ = newnode;
316 newnode->data_ = data;
317 ++linkList_size;
318 }
319
320 /*
321 * 删除当前结点
322 * 方法是：将待删除结点的指针域赋给上个结点的指针域
323 */
324 /*
325 * 在索引值为index前插入结点函数,支持尾插
326 * 方法是：将index-1结点的指针域赋给newnode的指针域，然后将newnode的地址赋给index-1位置结点的指针域
327 * 也就是说想要在index插入实际上操作的是n-1
328 */
329 template<class DataType>
330 void LinkList<DataType>::DeleteNode(int index)
331 {
332 ListNode<DataType>* temp;
333 ListNode<DataType>* find = L;
334 int num = -1;
335 try
336 {
337 if (L->next_ == nullptr)
338 {
339 throw - 1;
340 }
341 if ((index < 0) || (index > linkList_size - 1))
342 {
343 throw std::runtime_error("LinkList subscript out of range");
344 }
345 }
346 catch (std::runtime_error& err)
347 {
348 cout << "************************" << endl;
349 cout << "You meet one abnormal:" << endl;
350 cout << err.what() << endl;
351 cout << "The range of subscript is " << "[" << 0 << "," << linkList_size-1 << "]" << endl;
352 cout << "Please input the right index:" << endl;
353 int right_index;
354 cin >> right_index;
355 index = right_index;
356 }
357 catch (const int&)
358 {
359 cout << "************************" << endl;
360 cout << "You meet one abnormal:" << endl;
361 std::cerr << "This is a empty linklist" << endl;
362 std::terminate();
363 }
364 while (num != (index - 1))
365 {
366 ++num;
367 find = find->next_;
368 }
369 temp = find->next_;
370 find->next_ = find->next_->next_;
371 delete temp;
372 temp = nullptr;
373 --linkList_size;
374 }
375 /*
376 * 头插法创建新链表,手动输入数据
377 * 创建一个a->b->c的链表，首先将c接入链表末尾，然后将b接入头结点和c之间，然后将a接入
378 */
379
380 template<class DataType>
381 void LinkList<DataType>::AddNode_input(int num)
382 {
383 cout << "Please creat " << num << " node" << endl;
384 for (int i = 0; i < num; ++i)
385 {
386 ListNode<DataType>* newnode = new ListNode<DataType>;
387 newnode->next_ = L->next_;
388 cout << "Please enter " << num-i << " more pieces of data " << endl;
389 cin >> newnode->data_;
390 L->next_ = newnode;
391 ++linkList_size;
392 }
393 }
394 /*
395 * 头插法创建新链表,调用函数
396 * 创建一个a->b->c的链表，首先将c接入链表末尾，然后将b接入头结点和c之间，然后将a接入
397 */
398
399 template<class DataType>
400 void LinkList<DataType>::AddNode(ListNode<DataType>*newnode,DataType data)
401 {
402 newnode->next_ = L->next_;
403 newnode->data_ = data;
404 L->next_ = newnode;
405 ++linkList_size;
406 }
407
408 /*
409 * 尾插法
410 * 方法是：将新结点的地址赋给temp的指针域，接着将temp指向该新结点,以便于后续结点插入
411 * temp 指向新结点的指针
412 */
413 template<class DataType>
414 void LinkList<DataType>::PushBack_input(int num)
415 {
416 cout << "Please creat " << num << " node" << endl;
417 ListNode<DataType>* temp = L;
418 for (int i = 0; i < num; ++i)
419 {
420 ListNode<DataType>* newnode = new ListNode<DataType>;
421 temp->next_ = newnode;
422 temp = newnode;
423 cout << "Please enter " << num - i << " more pieces of data " << endl;
424 cin >> temp->data_;
425 ++linkList_size;
426 }
427 }
428
429 /*
430 * 尾插法
431 * 方法是：将新结点的地址赋给temp的指针域，接着将temp指向该新结点,以便于后续结点插入
432 * temp 指向新结点的指针
433 */
434 template<class DataType>
435 void LinkList<DataType>::PushBack(ListNode<DataType>* newnode, DataType data)
436 {
437 //static使下次调用的时候temp依然指向上一个新的结点，不会刷新
438 //如果一个函数的第一次调用和其他调用不一样的话往往需要static
439 static ListNode<DataType>* temp = L;
440 temp->next_ = newnode;
441 temp = newnode;
442 temp->data_ = data;
443 ++linkList_size;
444 }
1 #include<iostream>
2 #include"LinkList.hpp"
3 using std::endl;
4 using std::cout;
5 using std::string;
6 /*
7 * 如果类中有运算符，那么只需要在主文件中重载这些运算符就可以使用这个类了
8 */
9 struct student
10 {
11 int age = 0;
12 string name = "";
13 };
14 std::ostream& operator<<(std::ostream& cout, const student& st) {
15 cout << st.age<< endl;
16 cout << st.name << endl;
17 return cout;
18 }
19 bool operator==(const student& st1, const student& st2) {
20 if ((st1.age == st2.age) && (st1.name == st2.name))
21 {
22 return true;
23 }
24 else
25 {
26 return false;
27 }
28 }
29 bool operator!=(const student& st1, const student& st2) {
30 if ((st1.age == st2.age) && (st1.name == st2.name))
31 {
32 return false;
33 }
34 else
35 {
36 return true;
37 }
38 }
39 int main()
40 {
41 student stu1 = { 80,"张三" };
42 student stu2 = { 90,"李四" };
43 student stu3 = { 100,"王五" };
44 ListNode<student>* node1=new ListNode<student>;
45 ListNode<student>* node2 = new ListNode<student>;
46 ListNode<student>* node3 = new ListNode<student>;
47 LinkList<student>link_student;
48 link_student.PushBack(node1, stu1);
49 link_student.PushBack(node2, stu2);
50 link_student.PushBack(node3, stu3);
51
52 int val1 = 20;
53 int val2 = 30;
54 int val3 = 40;
55 ListNode<int>* node4=new ListNode<int>;
56 ListNode<int>* node5 = new ListNode<int>;
57 ListNode<int>* node6 = new ListNode<int>;
58 LinkList<int>link_int;
59 link_int.PushBack(node4, val1);
60 link_int.PushBack(node5, val2);
61 link_int.PushBack(node6, val3);
62
63 //注意自定义类型无法通过循环加cin填加数据
64 cout << "stduent的测试————————————" << endl;
65 cout << link_student.Empty() << endl;
66 cout << "————————————————" << endl;
67 cout << link_student.FindDataAddress(stu2) << endl;
68 cout << "————————————————" << endl;
69 cout << link_student.FindIndexAddress(1) << endl;
70 cout << "————————————————" << endl;
71 cout << link_student.FindDataIndex(stu2) << endl;
72 cout << "————————————————" << endl;
73 cout << link_student.FindIndexData(1) << endl;
74 cout << "————————————————" << endl;
75 link_student.DeleteNode(1);
76 cout << link_student.FindIndexData(1) << endl;
77 cout << "————————————————" << endl;
78 //错误1：必须重新建立结点，因为原来的node2堆区已经被释放
79 //link_student.Insert(1, stu2, node2);
80 //cout << link_student.FindIndexData(1) << endl;
81 ListNode<student>* node2_2 = new ListNode<student>;
82 student stu2_2 = { 60,"赵六" };
83 link_student.Insert(1, stu2_2, node2_2);
84 cout << link_student.FindIndexData(1) << endl;
85 cout << "————————————————" << endl;
86 link_student.RemoveAll();
87 cout << link_student.LinkSize() << endl;
88 cout << link_student.linkList_size << endl;
89 cout << "————————————————" << endl;
90 //注意这样使用的话是每次在首元结点之前插入数据
91 ListNode<student>* node7 = new ListNode<student>;
92 student stu4 = { 120,"钱七" };
93 link_student.AddNode(node7, stu4);
94 cout << link_student.FindIndexData(0) << endl;
95
96 cout << "int的测试————————————" << endl;
97 cout << link_int.Empty() << endl;
98 cout << "————————————————" << endl;
99 cout << link_int.FindDataAddress(val2) << endl;
100 cout << "————————————————" << endl;
101 cout << link_int.FindIndexAddress(1) << endl;
102 cout << "————————————————" << endl;
103 cout << link_int.FindDataIndex(val2) << endl;
104 cout << "————————————————" << endl;
105 cout << link_int.FindIndexData(1) << endl;
106 cout << "————————————————" << endl;
107 link_int.DeleteNode(1);
108 cout << link_int.FindIndexData(1) << endl;
109 cout << "————————————————" << endl;
110 ListNode<int>* node5_2 = new ListNode<int>;
111 int val5_2 = 50;
112 link_int.Insert(1, val5_2, node5_2);
113 cout << link_int.FindIndexData(1) << endl;
114 cout << "————————————————" << endl;
115 link_int.RemoveAll();
116 cout << link_int.LinkSize() << endl;
117 cout << link_int.linkList_size << endl;
118 cout << "————————————————" << endl;
119 //注意这样使用的话是每次在首元结点之前插入数据
120 ListNode<int>* node8 = new ListNode<int>;
121 int val7 = 60;
122 link_int.AddNode(node8, val7);
123 cout << link_int.FindIndexData(0) << endl;
124 cout << "————————————————" << endl;
125 link_int.AddNode_input(3);
126 cout << "————————————————" << endl;
127 cout << link_int.FindIndexData(0) << endl;
128 cout << link_int.FindIndexData(1) << endl;
129 cout << link_int.FindIndexData(2) << endl;
130 //尾插和头插不能一起用
131 //link_int.PushBack_input(3);
132 //cout << link_int.linkList_size << endl;
133 ////错误2：之所以不会抛出前面所写的异常是因为判断语句中用的linklist_size，导致不会执行判断语句
134 //cout << link_int.FindIndexData(4) << endl;
135 system("pause");
136 return 0;
137 }
1 stduent的测试———————————— 2 0 3 ———————————————— 4 000001DFF6AF5DF0 5 ———————————————— 6 000001DFF6AF5DF0 7 ———————————————— 8 1 9 ———————————————— 10 90 11 李四 12 13 ———————————————— 14 100 15 王五 16 17 ———————————————— 18 60 19 赵六 20 21 ———————————————— 22 0 23 0 24 ———————————————— 25 120 26 钱七 27 28 int的测试———————————— 29 0 30 ———————————————— 31 000001DFF6B03650 32 ———————————————— 33 000001DFF6B03650 34 ———————————————— 35 1 36 ———————————————— 37 30 38 ———————————————— 39 40 40 ———————————————— 41 50 42 ———————————————— 43 0 44 0 45 ———————————————— 46 60 47 ———————————————— 48 Please creat 3 node 49 Please enter 3 more pieces of data 50 120 51 Please enter 2 more pieces of data 52 110 53 Please enter 1 more pieces of data 54 100 55 ———————————————— 56 100 57 110 58 120
错误1：
使用已经释放的堆区
错误2：(读取访问权限冲突)
往往是下标越界造成的
以上错误都是调试才能看出来
标签：index,结点,ListNode,temp,int,程序,next,链表,模板 From： https://www.cnblogs.com/Sandals-little/p/17496979.html