Berbagi teknologi

Implementasi yang mendasari wadah daftar C

2024-07-12

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

1. Apa itu daftar?

Daftar adalah daftar tertaut ganda berkepala dalam wadah C++. Elemen simpul kepala berikutnya adalah elemen pertama yang menyimpan data data. (Strukturnya ditunjukkan pada gambar di bawah)

Struktur setiap node pada linked list dibagi menjadi bagian data, penunjuk depan dan penunjuk belakang (berikut diagram struktur dan kodenya)

2. Daftar implementasi kode dan analisis sintaksis

2.1 Tentukan struktur node

Tipe data dan penunjuk depan dan belakang dalam daftar tertaut dihasilkan oleh templat dan dapat disesuaikan dengan tipe bawaan dan tipe kustom.Alasan mengapa struct digunakan untuk mendefinisikan kelas di sini adalah karena tipe variabel anggota default struct bersifat publik, dan fungsi lainnya dapat dipanggil dengan mudah.Di sini juga terdapat konstruktor list_node T() yang merupakan variabel anonim. Fungsinya tidak hanya digunakan untuk menyimpan data. Selain itu, jika tidak ada parameter yang ditulis saat memanggil konstruktor list_node, juga akan ada nilai default di sini.

2.2 Tentukan struktur daftar tertaut

Dalam daftar, terdapat dua variabel anggota: _node, penunjuk ke jenis node, dan _size, yang menghitung jumlah node.

  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 Tambahkan fungsi daftar tertaut (masukkan Push_back)

Kita telah mendefinisikan struktur dasar daftar, dan sekarang kita akan menambahkan beberapa fungsi dasar, seperti memasukkan data ke dalam daftar dan menggunakan iterator untuk menelusuri daftar.

Fungsi Push_back: Pertama buat node baru node baru, lalu simpan data X yang perlu disimpan di node baru, cari node ekor dan masukkan node baru ke dalam node di sebelah node ekor.

  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. };
  15.  
  16. template<class T>
  17. class list
  18. {
  19. typedef list_node<T> Node;
  20. void empty_init()
  21. {
  22.     _head = new Node;
  23.     _head -> next = _head;
  24.     _head -> prev = _head;
  25.     _size = 0;
  26. }
  27. list()
  28. {
  29.     empty_init();
  30. }
  31. void push_back(const T& x)
  32. {
  33.     Node* newnode = new Node(x);
  34.     Node* tail = _head->prev;
  35.  
  36.     tail->_next = newnode;
  37.     newnode->prev = tail;
  38.  
  39.     newnode->_next = _head;
  40.     _head->prev = newnode;
  41.     
  42.     _size++; 
  43. }
  44.     private:
  45.         Node* _node;
  46.         size_t _size;
  47. }

2.4 Tambahkan fungsi daftar tertaut (overloading operator iterator dan iterator)

Berbeda dengan daftar urutan, karena node dari daftar tertaut tidak disimpan bersama dalam ruang kontinu, ++ dan dereferensi penunjuk tidak dapat langsung memperoleh data, jadi di sini kita perlu membebani * -&gt; ++ -- dll .dll.operator.

  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. };
  15. template<class T>
  16. struct __list_iterator
  17. {
  18.     typedef list_node<T> Node;
  19.     typedef __list_iterator self;
  20.  
  21.     Node* _node;
  22.     __list_iterator(Node* node)
  23.         :_node(node)
  24.     {
  25.  
  26.     }
  27.     
  28.     T& operator *(Node * node)
  29.     {
  30.         return _node->_data;
  31.     }
  32.  
  33.     T* operator(Node * node)
  34.     {
  35.         return &_node->_data;
  36.     }
  37.     self& operator++()
  38.     {
  39.         _node = _node->next;
  40.         return *this;
  41.     }
  42.     
  43.     self& operator--()
  44.     {
  45.         _node = _node->prev;
  46.         return *this;
  47.     }
  48.  
  49.     bool operator!=(const self& s)
  50.     {
  51.         return _node != s._node;
  52.     }
  53. }
  54.  
  55. template<class T>
  56. class list
  57. {
  58. typedef list_node<T> Node;
  59. typedef __list_iterator<T> iterator;
  60.  
  61. iterator begin()
  62. {
  63.     return iterator(_head->next);
  64. }
  65.  
  66. iterator end()
  67. {
  68.     return iterator(_head);
  69. }
  70.  
  71. void empty_init()
  72. {
  73.     _head = new Node;
  74.     _head -> next = _head;
  75.     _head -> prev = _head;
  76.     _size = 0;
  77. }
  78.  
  79. list()
  80. {
  81.     empty_init();
  82. }
  83.  
  84. void push_back(const T& x)
  85. {
  86.     Node* newnode = new Node(x);
  87.     Node* tail = _head->prev;
  88.  
  89.     tail->_next = newnode;
  90.     newnode->prev = tail;
  91.  
  92.     newnode->_next = _head;
  93.     _head->prev = newnode;
  94.     
  95.     _size++; 
  96. }
  97.     private:
  98.         Node* _node;
  99.         size_t _size;
  100. }

Setelah menyelesaikan operasi di atas, kita dapat men-debug program seperti ini. Meskipun List bukan array, kita dapat mengakses elemen di dalam List dengan cara yang sama.Meskipun iterator melakukan iterasi pada setiap elemen kontainer dengan cara yang sama, iterator melindungi detail implementasi yang mendasarinya dan menyediakan metode akses terpadu.。

  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.  
  9.     while(it != lt.end())
  10.     {
  11.         cout << *it << " ";
  12.         ++it;
  13.     }
  14.     cout<< endl;
  15. }

2.5 Tambahkan fungsi daftar tertaut (peningkatan penyisipan() dan penghapus() penghapusan operasi penyisipan)

Pertama, kita bisa menulis fungsi insert(). Fungsi ini bisa digunakan kembali oleh fungsi lain seperti push_back dan push_front, dan juga bisa menyisipkan data di lokasi mana pun.

  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.     
  7.     prev->_next = newnode;
  8.     newnode->_prev = prev;
  9.     newnode->_next = cur;
  10.     cur->_prev = newnode;
  11.  
  12.     return newnode; 
  13. }
  14.  
  15. iterator erase(iterator pos)
  16. {
  17.     Node* cur = pos._node;
  18.     Node* prev = cur->_prev;
  19.     Node* next = cur->_next;
  20.  
  21.     delete cur;
  22.     prev->_next = next;
  23.     next->_prev = prev;
  24.  
  25.     return next;
  26. }
  27.  
  28. void push_back(const T& x)
  29. {
  30.     insert(this.end(),x);
  31. }
  32.  
  33. void push_front(const T& x)
  34. {
  35.     insert(begin(),x);
  36. }
  37.  
  38. void pop_back()
  39. {
  40.     erase(--end());
  41. }
  42.  
  43. void pop_front()
  44. {
  45.     erase(begin());
  46. }

2.6 Tambahkan fungsi daftar tertaut (hapus fungsi dan destruktor)

Karena nilai kembalian dari fungsi hapus adalah posisi selanjutnya dari data yang dihapus, jadi tidak menulis ++ disini akan menimbulkan efek ++.

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

2.7 Tambahkan fungsi daftar tertaut (menyalin konstruksi dan kelebihan tugas)

(1) Salin struktur

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

(2) Penugasan kelebihan beban

  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 Iterator tipe const

Untuk iterator tipe const, kita perlu memahami,Iterator bertipe const tidak dapat mengubah data yang ditunjuk oleh iterator, tetapi iterator itu sendiri tidak dapat diubah.Iterator itu sendiri perlu menyelesaikan operasi ++, -- dan lainnya untuk melakukan operasi traversal, jadi ketika menulis iterator tipe const, saya hanya membuat modifikasi const pada fungsi yang dikembalikan oleh iterator ke konten yang ditunjuk, dan fungsi lainnya tetap ada. tidak berubah.

  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. 	}
  12. 	
  13. 	const T& operator *()
  14. 	{
  15. 		return _node->_data;
  16. 	}
  17. 	const T* operator->()
  18. 	{
  19. 		return &_node->_data;
  20. 	}
  21. };

3. Kode lengkap

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

Profil pribadi

Ia telah mengabdikan dirinya untuk meneliti teknologi selama lebih dari 30 tahun, dan mahir dalam berbagai bahasa seperti java, linux, javascript, php, css, dll. "Saya telah memberikan banyak kontribusi di bidang dokumentasi pengembang stasiun sumber terbuka untuk berbagi beberapa masalah dalam pengembangan teknologi untuk referensi di masa mendatang. Semua orang memeriksanya

informasi kontak saya

Surat