Mi información de contacto
Correo[email protected]
2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
La lista es una lista doblemente enlazada en un contenedor de C++. El nodo principal no almacena datos. El siguiente elemento del nodo principal es el primer elemento que almacena datos. datos. (La estructura se muestra en la siguiente figura)
La estructura de cada nodo en la lista vinculada se divide en parte de datos, puntero frontal y puntero posterior (el siguiente es el diagrama de estructura y el código)
Los tipos de datos y los punteros frontal y posterior en la lista vinculada se generan mediante plantillas y se pueden adaptar a tipos integrados y tipos personalizados.La razón por la que se usa struct para definir la clase aquí es que los tipos de variables miembro predeterminadas de struct son públicos y se pueden llamar fácilmente otras funciones.También hay un constructor list_node T (), que es una variable anónima. Su función no solo se usa para almacenar datos. Además, si no se escriben parámetros al llamar al constructor list_node, también habrá un valor predeterminado.
En la lista, hay dos variables miembro: _node, un puntero al tipo de nodo, y _size, que calcula el número de nodos.
- template<class T>
- class list
- {
- typedef list_node<T> Node;
- void empty_init()
- {
- _head = new Node;
- _head -> next = _head;
- _head -> prev = _head;
- _size = 0;
- }
- list()
- {
- empty_init();
- }
- private:
- Node* _node;
- size_t _size;
- }
Hemos definido la estructura básica de la lista y ahora agregaremos algunas funciones básicas, como insertar datos en la lista y usar iteradores para recorrer la lista.
Función push_back: primero cree un nuevo nodo nuevo, luego almacene los datos X que deben almacenarse en el nodo nuevo, busque el nodo de cola e inserte el nodo nuevo en el nodo al lado del nodo de cola.
- template<class T>
- struct list_node
- {
- T _data;
- list_node<T>* _next;
- list_node<T>* _prev;
- list_node(const T& x=T())
- :_data(x)
- , _next(nullptr)
- , _prev(nullptr)
- {
-
- }
- };
-
- template<class T>
- class list
- {
- typedef list_node<T> Node;
- void empty_init()
- {
- _head = new Node;
- _head -> next = _head;
- _head -> prev = _head;
- _size = 0;
- }
- list()
- {
- empty_init();
- }
- void push_back(const T& x)
- {
- Node* newnode = new Node(x);
- Node* tail = _head->prev;
-
- tail->_next = newnode;
- newnode->prev = tail;
-
- newnode->_next = _head;
- _head->prev = newnode;
-
- _size++;
- }
- private:
- Node* _node;
- size_t _size;
- }
A diferencia de la lista de secuencia, debido a que los nodos de la lista vinculada no se almacenan juntos en un espacio continuo, ++ y la desreferencia del puntero no pueden obtener los datos directamente, por lo que aquí debemos sobrecargar * -> ++ - etc. etc. operador.
- template<class T>
- struct list_node
- {
- T _data;
- list_node<T>* _next;
- list_node<T>* _prev;
- list_node(const T& x=T())
- :_data(x)
- , _next(nullptr)
- , _prev(nullptr)
- {
-
- }
- };
- template<class T>
- struct __list_iterator
- {
- typedef list_node<T> Node;
- typedef __list_iterator self;
-
- Node* _node;
- __list_iterator(Node* node)
- :_node(node)
- {
-
- }
-
- T& operator *(Node * node)
- {
- return _node->_data;
- }
-
- T* operator(Node * node)
- {
- return &_node->_data;
- }
- self& operator++()
- {
- _node = _node->next;
- return *this;
- }
-
- self& operator--()
- {
- _node = _node->prev;
- return *this;
- }
-
- bool operator!=(const self& s)
- {
- return _node != s._node;
- }
- }
-
- template<class T>
- class list
- {
- typedef list_node<T> Node;
- typedef __list_iterator<T> iterator;
-
- iterator begin()
- {
- return iterator(_head->next);
- }
-
- iterator end()
- {
- return iterator(_head);
- }
-
- void empty_init()
- {
- _head = new Node;
- _head -> next = _head;
- _head -> prev = _head;
- _size = 0;
- }
-
- list()
- {
- empty_init();
- }
-
- void push_back(const T& x)
- {
- Node* newnode = new Node(x);
- Node* tail = _head->prev;
-
- tail->_next = newnode;
- newnode->prev = tail;
-
- newnode->_next = _head;
- _head->prev = newnode;
-
- _size++;
- }
- private:
- Node* _node;
- size_t _size;
- }
Después de completar las operaciones anteriores, podemos depurar el programa de esta manera. Aunque List no es una matriz, podemos acceder a los elementos dentro de List de manera similar.Aunque los iteradores iteran sobre cada elemento del contenedor de la misma manera, protegen los detalles de implementación subyacentes y proporcionan un método de acceso unificado.。
- test_list()
- {
- list<int> lt;
- lt.push_back(1);
- lt.push_back(2);
- lt.push_back(3);
- list<int>::iterator it = lt.begin();
-
- while(it != lt.end())
- {
- cout << *it << " ";
- ++it;
- }
- cout<< endl;
- }
Primero, podemos escribir una función insert(). Esta función puede ser reutilizada por otras funciones como push_back y push_front, y también puede insertar datos en cualquier ubicación.
- iterator insert(iterator pos , const T& x)
- {
- Node* newnode = new Node(x);
- Node* cur = pos._node;
- Node* prev = cur ->_prev;
-
- prev->_next = newnode;
- newnode->_prev = prev;
- newnode->_next = cur;
- cur->_prev = newnode;
-
- return newnode;
- }
-
- iterator erase(iterator pos)
- {
- Node* cur = pos._node;
- Node* prev = cur->_prev;
- Node* next = cur->_next;
-
- delete cur;
- prev->_next = next;
- next->_prev = prev;
-
- return next;
- }
-
- void push_back(const T& x)
- {
- insert(this.end(),x);
- }
-
- void push_front(const T& x)
- {
- insert(begin(),x);
- }
-
- void pop_back()
- {
- erase(--end());
- }
-
- void pop_front()
- {
- erase(begin());
- }
Debido a que el valor de retorno de la función de borrado es la siguiente posición de los datos eliminados, no escribir ++ aquí tendrá el efecto de ++.
- ~list()
- {
- clear();
- delete _head;
- _head = nullpre;
- }
-
- void clear()
- {
- iterator it = begin();
- while(it != end())
- {
- it = erase(*it);
- }
- }
(1) Copiar estructura
- list( list<int> lt )
- {
- empty_init();
- for(auto e : lt)
- {
- this.push_back(e);
- }
- }
(2) Sobrecarga de tareas
- void swap(list<T>& lt)
- {
- std::swap(_head, lt._head);
- std::swap(_size, lt._size);
- }
- list<int>& operator=(list<int> lt)
- {
- swap(lt);
- return *this;
- }
Para iteradores de tipo constante, debemos entender,Los iteradores de tipo constante no pueden modificar los datos señalados por el iterador, pero el iterador en sí no se puede modificar.El iterador en sí necesita completar ++, -- y otras operaciones para realizar operaciones transversales, por lo que cuando escribo un iterador de tipo constante, solo hago modificaciones constantes a la función que el iterador devuelve al contenido señalado, y las otras funciones permanecen sin alterar.
- template<class T>
- struct __list_const_iterator
- {
- typedef list_node<T> Node;
- typedef __list_const_iterator<T> self;
- Node* _node;
- __list_const_iterator(Node* node)
- :_node(node)
- {
-
- }
-
- const T& operator *()
- {
- return _node->_data;
- }
- const T* operator->()
- {
- return &_node->_data;
- }
- };
- #pragma once
- #include<iostream>
- using namespace std;
- namespace hjy
- {
- template<class T>
- struct list_node
- {
- T _data;
- list_node<T>* _next;
- list_node<T>* _prev;
- list_node(const T& x=T())
- :_data(x)
- , _next(nullptr)
- , _prev(nullptr)
- {
-
- }
- };
- template<class T,class Ref,class Ptr>
- struct __list_iterator
- {
- typedef list_node<T> Node;
- typedef __list_iterator<T,Ref,Ptr> self;
- Node* _node;
- __list_iterator(Node* node)
- :_node(node)
- {
-
- }
- self& operator ++()
- {
- _node = _node->_next;
- return *this;
- }
- self& operator --()
- {
- _node = _node->_prev;
- return *this;
- }
- self operator ++(int)
- {
- self tmp(*this);
- _node = _node->_next;
- return tmp;
- }
- self operator --(int)
- {
- self tmp(*this);
- _node = _node->_prev;
- return tmp;
- }
- Ref operator *()
- {
- return _node->_data;
- }
- Ptr operator->()
- {
- return &_node->_data;
- }
- bool operator!=(const self& s)
- {
- return _node != s._node;
- }
- };
- /*template<class T>
- struct __list_const_iterator
- {
- typedef list_node<T> Node;
- typedef __list_const_iterator<T> self;
- Node* _node;
- __list_const_iterator(Node* node)
- :_node(node)
- {
- }
- self& operator ++()
- {
- _node = _node->_next;
- return *this;
- }
- self& operator --()
- {
- _node = _node->_prev;
- return *this;
- }
- self operator ++(int)
- {
- self tmp(*this);
- _node = _node->_next;
- return tmp;
- }
- self operator --(int)
- {
- self tmp(*this);
- _node = _node->_prev;
- return tmp;
- }
- const T& operator *()
- {
- return _node->_data;
- }
- const T* operator->()
- {
- return &_node->_data;
- }
- bool operator!=(const self& s)
- {
- return _node != s._node;
- }
- };*/
- template<class T>
- class list
- {
- typedef list_node<T> Node;
- public:
- typedef __list_iterator<T,T&,T*> iterator;
- typedef __list_iterator<T, const T&, const T*> const_iterator;
- //typedef __list_const_iterator<T> const_iterator;
-
- const_iterator begin()const
- {
- return const_iterator(_head->_next);
- }
- const_iterator end()const
- {
- return const_iterator(_head);
- }
-
- iterator begin()
- {
- return _head->_next;
- }
- iterator end()
- {
- return _head;
- }
- void empty_init()
- {
- _head = new Node;
- _head->_next = _head;
- _head->_prev = _head;
- _size = 0;
- }
- list()
- {
- empty_init();
- }
- //list<int>& operator=(const list<int>& lt) 传统写法
- //{
- // if (this != <)
- // clear();
- // for (auto e : lt)
- // {
- // push_back(e);
- // }
- // return *this;
- //}
- void swap(list<T>& lt)
- {
- std::swap(_head, lt._head);
- std::swap(_size, lt._size);
- }
- list<int>& operator=(list<int> lt)
- {
- swap(lt);
- return *this;
- }
- ~list()
- {
- clear();
- delete _head;
- _head = nullptr;
- }
- //list(const list<T>& lt)//没有const迭代器所以这样写不行
- //{
- // empty_init();
- // for (auto e : lt)
- // {
- // push_back(e);
- // }
- //}
- list( list<T>& lt)
- {
- empty_init();
- for (auto e : lt)
- {
- push_back(e);
- }
- }
- void push_back(const T& x)
- {
- insert(end(), x);
- }
- void push_front(const T& x)
- {
- insert(begin(), x);
- }
- void pop_front()
- {
- erase(begin());
- }
- void pop_back()
- {
- erase(end()--);
- }
- void clear()
- {
- iterator it = begin();
- while (it != end())
- {
- it = erase(it);
- }
- }
- iterator insert(iterator pos, const T& val)
- {
- Node* cur = pos._node;
- Node* newnode = new Node(val);
- Node* prev = cur->_prev;
- prev->_next = newnode;
- newnode->_prev = prev;
- newnode->_next = cur;
- cur->_prev = newnode;
- ++_size;
- return iterator(newnode);
- }
- iterator erase(iterator pos)
- {
- Node* cur = pos._node;
- Node* prev = cur->_prev;
- Node* next = cur->_next;
- delete cur;
- prev->_next = next;
- next->_prev = prev;
- --_size;
- return iterator(next);
- }
- size_t size()
- {
- return _size;
- }
- private:
- Node* _head;
- size_t _size;
- };
- void test_list1()
- {
- list<int>lt;
- lt.push_back(1);
- lt.push_back(2);
- lt.push_back(3);
- lt.push_back(4);
- lt.push_back(5);
- for (auto e : lt)
- cout << e << " ";
- cout << endl;
-
- list<int>lt1 = lt;
- for (auto e : lt1)
- cout << e << " ";
- cout << endl;
-
- }
- /*void print_list(const list<int>& lt)
- {
- list<int>::const_iterator it = lt.begin();
- while (it != lt.end())
- {
- cout << *it << " ";
- ++it;
- }
- cout << endl;
- for (auto e : lt)
- {
- cout << e << " ";
- }
- cout << endl;
- }*/
- template<typename T>
- void print_list(const list<T>& lt)
- {
- typename list<T>::const_iterator it = lt.begin();
- while (it != lt.end())
- {
- cout << *it << " ";
- ++it;
- }
- cout << endl;
- }
- void test_list2()
- {
- list<string>lt;
- lt.push_back("111");
- lt.push_back("111");
- lt.push_back("111");
- print_list(lt);
- }
- }