minhas informações de contato
Correspondência[email protected]
2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Lista é uma lista duplamente encadeada em um contêiner C++. O nó principal não armazena dados. O próximo elemento do nó principal é o primeiro elemento que armazena dados. dados. (A estrutura é mostrada na figura abaixo)
A estrutura de cada nó na lista vinculada é dividida em parte de dados, ponteiro frontal e ponteiro traseiro (a seguir está o diagrama de estrutura e o código)
Os tipos de dados e ponteiros frontais e traseiros na lista vinculada são gerados por modelos e podem ser adaptados para tipos integrados e personalizados.A razão pela qual struct é usado para definir a classe aqui é que os tipos de variáveis de membro padrão de struct são públicos e outras funções podem ser facilmente chamadas.Há também um construtor list_node T() aqui, que é uma variável anônima. Sua função não é usada apenas para armazenar dados. Além disso, se nenhum parâmetro for escrito ao chamar o construtor list_node, também haverá um valor padrão aqui.
Na lista, há duas variáveis de membro: _node, um ponteiro para o tipo de nó, e _size, que calcula o número de nós.
- 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;
- }
Definimos a estrutura básica da lista e agora adicionaremos algumas funções básicas, como inserir dados na lista e usar iteradores para percorrer a lista.
Função push_back: primeiro construa um novo nó newnode, em seguida, armazene os dados X que precisam ser armazenados no newnode, encontre o nó final e insira o newnode no nó próximo ao nó final.
- 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;
- }
Diferente da lista de sequência, porque os nós da lista vinculada não são armazenados juntos em um espaço contínuo, o ++ e a desreferência do ponteiro não podem obter os dados diretamente, então aqui precisamos sobrecarregar * -> ++ - 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;
- }
Depois de concluir as operações acima, podemos depurar o programa assim. Embora List não seja um array, podemos acessar os elementos dentro de List de maneira semelhante.Embora os iteradores iterem cada elemento do contêiner da mesma maneira, os iteradores protegem os detalhes de implementação subjacentes e fornecem um método de acesso 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;
- }
Primeiro, podemos escrever uma função insert(). Esta função pode ser reutilizada por outras funções, como push_back e push_front, e também pode inserir dados em qualquer local.
- 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());
- }
Como o valor de retorno da função apagar é a próxima posição dos dados excluídos, não escrever ++ aqui terá o efeito de ++.
- ~list()
- {
- clear();
- delete _head;
- _head = nullpre;
- }
-
- void clear()
- {
- iterator it = begin();
- while(it != end())
- {
- it = erase(*it);
- }
- }
(1) Copiar estrutura
- list( list<int> lt )
- {
- empty_init();
- for(auto e : lt)
- {
- this.push_back(e);
- }
- }
(2) Sobrecarga de tarefas
- 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 do tipo const, precisamos entender,Iteradores do tipo const não podem modificar os dados apontados pelo iterador, mas o próprio iterador não pode ser modificado.O próprio iterador precisa completar ++, -- e outras operações para realizar operações de travessia, portanto, ao escrever um iterador do tipo const, eu apenas faço modificações const na função que o iterador retorna ao conteúdo apontado, e as outras funções permanecem inalterado.
- 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);
- }
- }