기술나눔

C 목록 컨테이너의 기본 구현

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

1. 목록이란 무엇입니까?

목록은 C++ 컨테이너의 머리가 있는 이중 연결 목록입니다. 헤드 노드의 다음 요소는 데이터를 저장하는 첫 번째 요소입니다. 데이터. (구조는 아래 그림과 같습니다)

연결리스트의 각 노드의 구조는 데이터 부분, 앞 포인터, 뒤 포인터로 나누어진다. (다음은 구조도와 코드이다)

2. 목록 코드 구현 및 구문 분석

2.1 노드의 구조 정의

연결된 목록의 데이터 유형과 앞/뒤 포인터는 템플릿에 의해 생성되며 내장 유형 및 사용자 정의 유형에 맞게 조정할 수 있습니다.여기서 클래스를 정의하기 위해 struct를 사용하는 이유는 struct의 기본 멤버 변수 유형이 public이고, 다른 함수를 쉽게 호출할 수 있기 때문이다.여기에는 익명 변수인 list_node 생성자 T()도 있습니다. 해당 기능은 데이터를 저장하는 데만 사용되는 것이 아닙니다. 또한 list_node 생성자를 호출할 때 매개변수가 작성되지 않으면 여기에도 기본값이 있습니다.

2.2 연결리스트의 구조 정의

목록에는 두 개의 멤버 변수가 있습니다. 노드 유형에 대한 포인터인 _node와 노드 수를 계산하는 _size입니다.

  1. template<class T>
  2. class list
  3. {
  4. typedef list_node<T> Node;
  5. void empty_init()
  6. {
  7. _head = new Node;
  8. _head -> next = _head;
  9. _head -> prev = _head;
  10. _size = 0;
  11. }
  12. list()
  13. {
  14. empty_init();
  15. }
  16. private:
  17. Node* _node;
  18. size_t _size;
  19. }

2.3 연결리스트 기능 추가(push_back 삽입)

목록의 기본 구조를 정의했으며 이제 목록에 데이터를 삽입하고 반복자를 사용하여 목록을 탐색하는 등 몇 가지 기본 기능을 추가하겠습니다.

Push_back 기능: 먼저 새 노드 newnode를 구축한 다음 newnode에 저장해야 하는 데이터 X를 저장하고 tail 노드를 찾아서 tail 노드 옆에 있는 노드에 newnode를 삽입합니다.

  1. template<class T>
  2. struct list_node
  3. {
  4. T _data;
  5. list_node<T>* _next;
  6. list_node<T>* _prev;
  7. list_node(const T& x=T())
  8. :_data(x)
  9. , _next(nullptr)
  10. , _prev(nullptr)
  11. {
  12. }
  13. };
  14. template<class T>
  15. class list
  16. {
  17. typedef list_node<T> Node;
  18. void empty_init()
  19. {
  20. _head = new Node;
  21. _head -> next = _head;
  22. _head -> prev = _head;
  23. _size = 0;
  24. }
  25. list()
  26. {
  27. empty_init();
  28. }
  29. void push_back(const T& x)
  30. {
  31. Node* newnode = new Node(x);
  32. Node* tail = _head->prev;
  33. tail->_next = newnode;
  34. newnode->prev = tail;
  35. newnode->_next = _head;
  36. _head->prev = newnode;
  37. _size++;
  38. }
  39. private:
  40. Node* _node;
  41. size_t _size;
  42. }

2.4 연결된 목록 기능 추가(반복자 및 반복자 연산자 오버로딩)

시퀀스 목록과 달리 연결 목록의 노드는 연속된 공간에 함께 저장되지 않기 때문에 포인터의 ++ 및 역참조로는 데이터를 직접 얻을 수 없으므로 여기서는 * -&gt; ++ -- 등을 오버로드해야 합니다. .등 연산자.

  1. template<class T>
  2. struct list_node
  3. {
  4. T _data;
  5. list_node<T>* _next;
  6. list_node<T>* _prev;
  7. list_node(const T& x=T())
  8. :_data(x)
  9. , _next(nullptr)
  10. , _prev(nullptr)
  11. {
  12. }
  13. };
  14. template<class T>
  15. struct __list_iterator
  16. {
  17. typedef list_node<T> Node;
  18. typedef __list_iterator self;
  19. Node* _node;
  20. __list_iterator(Node* node)
  21. :_node(node)
  22. {
  23. }
  24. T& operator *(Node * node)
  25. {
  26. return _node->_data;
  27. }
  28. T* operator(Node * node)
  29. {
  30. return &_node->_data;
  31. }
  32. self& operator++()
  33. {
  34. _node = _node->next;
  35. return *this;
  36. }
  37. self& operator--()
  38. {
  39. _node = _node->prev;
  40. return *this;
  41. }
  42. bool operator!=(const self& s)
  43. {
  44. return _node != s._node;
  45. }
  46. }
  47. template<class T>
  48. class list
  49. {
  50. typedef list_node<T> Node;
  51. typedef __list_iterator<T> iterator;
  52. iterator begin()
  53. {
  54. return iterator(_head->next);
  55. }
  56. iterator end()
  57. {
  58. return iterator(_head);
  59. }
  60. void empty_init()
  61. {
  62. _head = new Node;
  63. _head -> next = _head;
  64. _head -> prev = _head;
  65. _size = 0;
  66. }
  67. list()
  68. {
  69. empty_init();
  70. }
  71. void push_back(const T& x)
  72. {
  73. Node* newnode = new Node(x);
  74. Node* tail = _head->prev;
  75. tail->_next = newnode;
  76. newnode->prev = tail;
  77. newnode->_next = _head;
  78. _head->prev = newnode;
  79. _size++;
  80. }
  81. private:
  82. Node* _node;
  83. size_t _size;
  84. }

위의 작업을 완료한 후 다음과 같이 프로그램을 디버깅할 수 있습니다. List는 배열이 아니지만 비슷한 방식으로 List 내부의 요소에 액세스할 수 있습니다.반복자는 동일한 방식으로 컨테이너의 각 요소를 반복하지만 기본 구현 세부 정보를 보호하고 통합 액세스 방법을 제공합니다.

  1. test_list()
  2. {
  3. list<int> lt;
  4. lt.push_back(1);
  5. lt.push_back(2);
  6. lt.push_back(3);
  7. list<int>::iterator it = lt.begin();
  8. while(it != lt.end())
  9. {
  10. cout << *it << " ";
  11. ++it;
  12. }
  13. cout<< endl;
  14. }

2.5 연결리스트 기능 추가 (삽입 작업의 insert() 및 erar() 삭제 업그레이드)

먼저 insert() 함수를 작성할 수 있습니다. 이 함수는 push_back 및 push_front와 같은 다른 함수에서 재사용할 수 있으며 어떤 위치에든 데이터를 삽입할 수도 있습니다.

  1. iterator insert(iterator pos , const T& x)
  2. {
  3. Node* newnode = new Node(x);
  4. Node* cur = pos._node;
  5. Node* prev = cur ->_prev;
  6. prev->_next = newnode;
  7. newnode->_prev = prev;
  8. newnode->_next = cur;
  9. cur->_prev = newnode;
  10. return newnode;
  11. }
  12. iterator erase(iterator pos)
  13. {
  14. Node* cur = pos._node;
  15. Node* prev = cur->_prev;
  16. Node* next = cur->_next;
  17. delete cur;
  18. prev->_next = next;
  19. next->_prev = prev;
  20. return next;
  21. }
  22. void push_back(const T& x)
  23. {
  24. insert(this.end(),x);
  25. }
  26. void push_front(const T& x)
  27. {
  28. insert(begin(),x);
  29. }
  30. void pop_back()
  31. {
  32. erase(--end());
  33. }
  34. void pop_front()
  35. {
  36. erase(begin());
  37. }

2.6 연결리스트 기능 추가(함수 및 소멸자 지우기)

삭제 함수의 반환 값은 삭제된 데이터의 다음 위치이므로 여기에 ++를 쓰지 않으면 ++의 효과가 발생합니다.

  1. ~list()
  2. {
  3. clear();
  4. delete _head;
  5. _head = nullpre;
  6. }
  7. void clear()
  8. {
  9. iterator it = begin();
  10. while(it != end())
  11. {
  12. it = erase(*it);
  13. }
  14. }

2.7 연결리스트 기능 추가(복사 생성 및 할당 오버로딩)

(1) 구조 복사

  1. list( list<int> lt )
  2. {
  3. empty_init();
  4. for(auto e : lt)
  5. {
  6. this.push_back(e);
  7. }
  8. }

(2) 할당 과부하

  1. void swap(list<T>& lt)
  2. {
  3. std::swap(_head, lt._head);
  4. std::swap(_size, lt._size);
  5. }
  6. list<int>& operator=(list<int> lt)
  7. {
  8. swap(lt);
  9. return *this;
  10. }

2.8 const 유형의 반복자

const 유형 반복자의 경우 다음을 이해해야 합니다.const 유형의 반복자는 반복자가 가리키는 데이터를 수정할 수 없지만 반복자 자체는 수정할 수 없습니다.순회 작업을 수행하려면 반복자 자체가 ++, -- 및 기타 작업을 완료해야 하므로 const 유형 반복자를 작성할 때 반복자가 가리키는 내용을 반환하는 함수에 대해서만 const 수정을 하고 다른 함수는 그대로 유지됩니다. 변하지 않은.

  1. template<class T>
  2. struct __list_const_iterator
  3. {
  4. typedef list_node<T> Node;
  5. typedef __list_const_iterator<T> self;
  6. Node* _node;
  7. __list_const_iterator(Node* node)
  8. :_node(node)
  9. {
  10. }
  11. const T& operator *()
  12. {
  13. return _node->_data;
  14. }
  15. const T* operator->()
  16. {
  17. return &_node->_data;
  18. }
  19. };

3. 완전한 코드

  1. #pragma once
  2. #include<iostream>
  3. using namespace std;
  4. namespace hjy
  5. {
  6. template<class T>
  7. struct list_node
  8. {
  9. T _data;
  10. list_node<T>* _next;
  11. list_node<T>* _prev;
  12. list_node(const T& x=T())
  13. :_data(x)
  14. , _next(nullptr)
  15. , _prev(nullptr)
  16. {
  17. }
  18. };
  19. template<class T,class Ref,class Ptr>
  20. struct __list_iterator
  21. {
  22. typedef list_node<T> Node;
  23. typedef __list_iterator<T,Ref,Ptr> self;
  24. Node* _node;
  25. __list_iterator(Node* node)
  26. :_node(node)
  27. {
  28. }
  29. self& operator ++()
  30. {
  31. _node = _node->_next;
  32. return *this;
  33. }
  34. self& operator --()
  35. {
  36. _node = _node->_prev;
  37. return *this;
  38. }
  39. self operator ++(int)
  40. {
  41. self tmp(*this);
  42. _node = _node->_next;
  43. return tmp;
  44. }
  45. self operator --(int)
  46. {
  47. self tmp(*this);
  48. _node = _node->_prev;
  49. return tmp;
  50. }
  51. Ref operator *()
  52. {
  53. return _node->_data;
  54. }
  55. Ptr operator->()
  56. {
  57. return &_node->_data;
  58. }
  59. bool operator!=(const self& s)
  60. {
  61. return _node != s._node;
  62. }
  63. };
  64. /*template<class T>
  65. struct __list_const_iterator
  66. {
  67. typedef list_node<T> Node;
  68. typedef __list_const_iterator<T> self;
  69. Node* _node;
  70. __list_const_iterator(Node* node)
  71. :_node(node)
  72. {
  73. }
  74. self& operator ++()
  75. {
  76. _node = _node->_next;
  77. return *this;
  78. }
  79. self& operator --()
  80. {
  81. _node = _node->_prev;
  82. return *this;
  83. }
  84. self operator ++(int)
  85. {
  86. self tmp(*this);
  87. _node = _node->_next;
  88. return tmp;
  89. }
  90. self operator --(int)
  91. {
  92. self tmp(*this);
  93. _node = _node->_prev;
  94. return tmp;
  95. }
  96. const T& operator *()
  97. {
  98. return _node->_data;
  99. }
  100. const T* operator->()
  101. {
  102. return &_node->_data;
  103. }
  104. bool operator!=(const self& s)
  105. {
  106. return _node != s._node;
  107. }
  108. };*/
  109. template<class T>
  110. class list
  111. {
  112. typedef list_node<T> Node;
  113. public:
  114. typedef __list_iterator<T,T&,T*> iterator;
  115. typedef __list_iterator<T, const T&, const T*> const_iterator;
  116. //typedef __list_const_iterator<T> const_iterator;
  117. const_iterator begin()const
  118. {
  119. return const_iterator(_head->_next);
  120. }
  121. const_iterator end()const
  122. {
  123. return const_iterator(_head);
  124. }
  125. iterator begin()
  126. {
  127. return _head->_next;
  128. }
  129. iterator end()
  130. {
  131. return _head;
  132. }
  133. void empty_init()
  134. {
  135. _head = new Node;
  136. _head->_next = _head;
  137. _head->_prev = _head;
  138. _size = 0;
  139. }
  140. list()
  141. {
  142. empty_init();
  143. }
  144. //list<int>& operator=(const list<int>& lt) 传统写法
  145. //{
  146. // if (this != &lt)
  147. // clear();
  148. // for (auto e : lt)
  149. // {
  150. // push_back(e);
  151. // }
  152. // return *this;
  153. //}
  154. void swap(list<T>& lt)
  155. {
  156. std::swap(_head, lt._head);
  157. std::swap(_size, lt._size);
  158. }
  159. list<int>& operator=(list<int> lt)
  160. {
  161. swap(lt);
  162. return *this;
  163. }
  164. ~list()
  165. {
  166. clear();
  167. delete _head;
  168. _head = nullptr;
  169. }
  170. //list(const list<T>& lt)//没有const迭代器所以这样写不行
  171. //{
  172. // empty_init();
  173. // for (auto e : lt)
  174. // {
  175. // push_back(e);
  176. // }
  177. //}
  178. list( list<T>& lt)
  179. {
  180. empty_init();
  181. for (auto e : lt)
  182. {
  183. push_back(e);
  184. }
  185. }
  186. void push_back(const T& x)
  187. {
  188. insert(end(), x);
  189. }
  190. void push_front(const T& x)
  191. {
  192. insert(begin(), x);
  193. }
  194. void pop_front()
  195. {
  196. erase(begin());
  197. }
  198. void pop_back()
  199. {
  200. erase(end()--);
  201. }
  202. void clear()
  203. {
  204. iterator it = begin();
  205. while (it != end())
  206. {
  207. it = erase(it);
  208. }
  209. }
  210. iterator insert(iterator pos, const T& val)
  211. {
  212. Node* cur = pos._node;
  213. Node* newnode = new Node(val);
  214. Node* prev = cur->_prev;
  215. prev->_next = newnode;
  216. newnode->_prev = prev;
  217. newnode->_next = cur;
  218. cur->_prev = newnode;
  219. ++_size;
  220. return iterator(newnode);
  221. }
  222. iterator erase(iterator pos)
  223. {
  224. Node* cur = pos._node;
  225. Node* prev = cur->_prev;
  226. Node* next = cur->_next;
  227. delete cur;
  228. prev->_next = next;
  229. next->_prev = prev;
  230. --_size;
  231. return iterator(next);
  232. }
  233. size_t size()
  234. {
  235. return _size;
  236. }
  237. private:
  238. Node* _head;
  239. size_t _size;
  240. };
  241. void test_list1()
  242. {
  243. list<int>lt;
  244. lt.push_back(1);
  245. lt.push_back(2);
  246. lt.push_back(3);
  247. lt.push_back(4);
  248. lt.push_back(5);
  249. for (auto e : lt)
  250. cout << e << " ";
  251. cout << endl;
  252. list<int>lt1 = lt;
  253. for (auto e : lt1)
  254. cout << e << " ";
  255. cout << endl;
  256. }
  257. /*void print_list(const list<int>& lt)
  258. {
  259. list<int>::const_iterator it = lt.begin();
  260. while (it != lt.end())
  261. {
  262. cout << *it << " ";
  263. ++it;
  264. }
  265. cout << endl;
  266. for (auto e : lt)
  267. {
  268. cout << e << " ";
  269. }
  270. cout << endl;
  271. }*/
  272. template<typename T>
  273. void print_list(const list<T>& lt)
  274. {
  275. typename list<T>::const_iterator it = lt.begin();
  276. while (it != lt.end())
  277. {
  278. cout << *it << " ";
  279. ++it;
  280. }
  281. cout << endl;
  282. }
  283. void test_list2()
  284. {
  285. list<string>lt;
  286. lt.push_back("111");
  287. lt.push_back("111");
  288. lt.push_back("111");
  289. print_list(lt);
  290. }
  291. }