【数据结构】实现单链表(c++)

前端之家收集整理的这篇文章主要介绍了【数据结构】实现单链表(c++)前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

文件



  1. #pragma once
  2.  
  3. #include <iostream>
  4. using namespace std;
  5.  
  6. template<class Type>
  7. class List;
  8.  
  9. // 结点类
  10. template<class Type>
  11. class NodeList
  12. {
  13. friend class List<Type>;
  14. public:
  15. NodeList();
  16. NodeList(Type d,NodeList<Type> *n = NULL);
  17. private:
  18. Type data;
  19. NodeList<Type>* next;
  20. };
  21.  
  22. // 链表类
  23. template<class Type>
  24. class List
  25. {
  26. public:
  27. List();
  28. ~List();
  29. public:
  30. void show_list();
  31. void tail_insert(Type const &x);
  32. void head_insert(Type const &x);
  33. void sort();
  34. void head_delete();
  35. void tail_delete();
  36. void val_insert(Type const &x);
  37. NodeList<Type>* find(Type const &x);
  38. void val_delete(Type const &x);
  39. Type length();
  40. void reverse();
  41. void clear();
  42. void destroy();
  43. void quit_system(Type &x);
  44. protected:
  45. NodeList<Type>* BuyNode(Type x = Type())
  46. {
  47. NodeList<Type>* p = new NodeList<Type>(x);
  48. return p;
  49. }
  50. private:
  51. NodeList<Type>* first;
  52. NodeList<Type>* last;
  53. };
  54.  
  55. // 结点类的构造函数
  56. template<class Type>
  57. NodeList<Type>::NodeList()
  58. {
  59. data = Type();
  60. next = NULL;
  61. }
  62.  
  63. template<class Type>
  64. NodeList<Type>::NodeList(Type d,NodeList<Type> *n = NULL)
  65. {
  66. data = d;
  67. next = n;
  68. }
  69.  
  70. // 链表类的构造函数
  71. template<class Type>
  72. List<Type>::List()
  73. {
  74. first = last = BuyNode();
  75.  
  76. }
  77.  
  78. // 链表类的析构函数
  79. template<class Type>
  80. List<Type>::~List()
  81. {
  82. destroy();
  83. }
  84.  
  85. // 显示
  86. template<class Type>
  87. void List<Type>::show_list()
  88. {
  89. NodeList<Type> *p = first->next;
  90. while (p != NULL)
  91. {
  92. cout << p->data << "->";
  93. p = p->next;
  94. }
  95. cout << "NULL" << endl;
  96. }
  97.  
  98. // 尾插
  99. template<class Type>
  100. void List<Type>::tail_insert(Type const& x)
  101. {
  102. NodeList<Type> *p = BuyNode(x);
  103. last->next = p;
  104. last = p;
  105. first->data++;
  106. }
  107.  
  108. // 头插
  109. template<class Type>
  110. void List<Type>::head_insert(Type const &x)
  111. {
  112. NodeList<Type> *p = BuyNode(x);
  113. p->next = first->next;
  114. first->next = p;
  115. last = p;
  116. for (int i = 0; i < first->data; ++i)
  117. {
  118. last = last->next;
  119. }
  120. first->data++;
  121. }
  122.  
  123. // 排序
  124. template<class Type>
  125. void List<Type>::sort()
  126. {
  127. if (first->data == 0)
  128. {
  129. return;
  130. }
  131. if (first->data == 1)
  132. {
  133. show_list();
  134. }
  135. NodeList<Type> *t = first->next;
  136. NodeList<Type> *p = t->next;
  137. NodeList<Type> *q = NULL;
  138. t->next = NULL;
  139. last = t;
  140. first->data = 1;
  141. while (p != NULL)
  142. {
  143. val_insert(p->data);
  144. q = p;
  145. p = p->next;
  146. delete q;
  147. }
  148. }
  149.  
  150. // 头删
  151. template<class Type>
  152. void List<Type>::head_delete()
  153. {
  154. if (first->data == 0)
  155. {
  156. cout << "the list is empty,cannot delete!" << endl;
  157. return;
  158. }
  159. NodeList<Type> *p = first->next;
  160. first->next = p->next;
  161. if (first->data == 1)
  162. last = first;
  163. delete p;
  164. first->data--;
  165. }
  166.  
  167. // 尾删
  168. template<class Type>
  169. void List<Type>::tail_delete()
  170. {
  171. if (first->data == 0)
  172. {
  173. cout << "the list is empty,cannot delete!" << endl;
  174. return;
  175. }
  176. NodeList<Type> *s = first;
  177. for (int i = 0; i < first->data - 1; ++i)
  178. {
  179. s = s->next;
  180. }
  181. s->next = NULL;
  182. last = s;
  183. delete s->next;
  184. first->data--;
  185. }
  186.  
  187. // 按值插入
  188. template<class Type>
  189. void List<Type>::val_insert(Type const &x)
  190. {
  191. if (first->data == 0)
  192. {
  193. tail_insert(x);
  194. return;
  195. }
  196. NodeList<Type> *p = first;
  197. NodeList<Type> *s = BuyNode(x);
  198. while (p->next->data < x && p->next->next != NULL)
  199. {
  200. p = p->next;
  201. }
  202. if (p->next->data>x)
  203. {
  204. s->next = p->next;
  205. p->next = s;
  206. first->data++;
  207. }
  208. else
  209. {
  210. tail_insert(x);
  211. }
  212. }
  213. // 查找
  214. template<class Type>
  215. NodeList<Type>* List<Type>::find(Type const &x)
  216. {
  217. NodeList<Type> *s = first->next;
  218. while (s != NULL)
  219. {
  220. if (s->data == x)
  221. {
  222. return s;
  223. }
  224. s = s->next;
  225. }
  226. return NULL;
  227. }
  228.  
  229. // 按值删除
  230. template<class Type>
  231. void List<Type>::val_delete(Type const &x)
  232. {
  233. if (first->data == 0)
  234. {
  235. cout << "the list is empty,cannot delete!" << endl;
  236. return;
  237. }
  238. NodeList<Type> *s = find(x);
  239. if (s == NULL)
  240. {
  241. cout << "the number is not exist,can not delete!" << endl;
  242. return;
  243. }
  244. NodeList<Type> *p = first;
  245. while (p->next != s)
  246. {
  247. p = p->next;
  248. }
  249. if (s->next != NULL)
  250. {
  251. p->next = s->next;
  252. first->data--;
  253. delete s;
  254. }
  255. else
  256. {
  257. tail_delete();
  258. }
  259. }
  260.  
  261. // 求长度
  262. template<class Type>
  263. Type List<Type>::length()
  264. {
  265. return first->data;
  266. }
  267.  
  268. // 反转
  269. template<class Type>
  270. void List<Type>::reverse()
  271. {
  272. if (first->data == 0)
  273. {
  274. return;
  275. }
  276. if (first->data == 1)
  277. {
  278. show_list();
  279. }
  280. NodeList<Type> *t = first->next;
  281. NodeList<Type> *p =t->next;
  282. NodeList<Type> *q = NULL;
  283. t->next = NULL;
  284. last = t;
  285. first->data = 1;
  286. while (p != NULL)
  287. {
  288. head_insert(p->data);
  289. q = p;
  290. p = p->next;
  291. delete q;
  292. }
  293. }
  294.  
  295. // 清空
  296. template<class Type>
  297. void List<Type>::clear()
  298. {
  299. if (first->data == 0)
  300. {
  301. return;
  302. }
  303. while (first->next != NULL)
  304. {
  305. tail_delete();
  306. }
  307. }
  308.  
  309. // 摧毁
  310. template<class Type>
  311. void List<Type>::destroy()
  312. {
  313. clear();
  314. delete first;
  315. }
  316.  
  317. // 退出系统
  318. template<class Type>
  319. void List<Type>::quit_system(Type &x)
  320. {
  321. x = 0;
  322. }



函数


  1. // 用c++实现单链表
  2.  
  3. #include "List.h"
  4.  
  5. int main()
  6. {
  7. List<int> mylist;
  8. int input = 1;
  9. int insert;
  10. while (input)
  11. {
  12. cout << "*********************************************************************" << endl;
  13. cout << "* [1] show_list [2] tail_insert *" << endl;
  14. cout << "* [3] head_insert [4] sort *" << endl;
  15. cout << "* [5] head_delete [6] tail_delete *" << endl;
  16. cout << "* [7] val_insert           [8] find *" << endl;
  17. cout << "* [9] val_delete [10] length *" << endl;
  18. cout << "* [11] reverse [12] clear *" << endl;
  19. cout << "* [13] destroy [14] quit_system *" << endl;
  20. cout << "*********************************************************************" << endl;
  21. cout << "please choose:";
  22. cin >> input;
  23. switch (input)
  24. {
  25. case 1:
  26. mylist.show_list();
  27. break;
  28. case 2:
  29. cout << "please enter the number want to insert(-1 end):";
  30. while (cin >> insert,insert != -1)
  31. {
  32. mylist.tail_insert(insert);
  33. }
  34. break;
  35. case 3:
  36. cout << "please enter the number want to insert(-1 end):";
  37. while (cin >> insert,insert != -1)
  38. {
  39. mylist.head_insert(insert);
  40. }
  41. break;
  42. case 4:
  43. mylist.sort();
  44. break;
  45. case 5:
  46. mylist.head_delete();
  47. break;
  48. case 6:
  49. mylist.tail_delete();
  50. break;
  51. case 7:
  52. cout << "please enter the number want to insert:";
  53. cin >> insert;
  54. mylist.val_insert(insert);
  55. break;
  56. case 8:
  57. cout << "please enter the number want to find:";
  58. cin >> insert;
  59. if (mylist.find(insert) == NULL)
  60. {
  61. cout << "the number is not exist!" << endl;
  62. }
  63. else
  64. {
  65. cout << "the number at the " << mylist.find(insert) << endl;
  66. }
  67. break;
  68. case 9:
  69. cout << "please enter the number want to delete:";
  70. cin >> insert;
  71. mylist.val_delete(insert);
  72. break;
  73. case 10:
  74. cout << "the length is" << " " << mylist.length() << endl;
  75. break;
  76. case 11:
  77. mylist.reverse();
  78. break;
  79. case 12:
  80. mylist.clear();
  81. break;
  82. case 13:
  83. mylist.destroy();
  84. break;
  85. case 14:
  86. mylist.quit_system(input);
  87. break;
  88. default:
  89. break;
  90. }
  91. }
  92. return 0;
  93. }


清除:







查找:





头删:







头插:








求长度:






退出系统:





反转:








排序:









尾删:









尾插:









按值删除









按值插入:





猜你在找的数据结构相关文章