моя контактная информация
Почтамезофия@protonmail.com
2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Список — это двусвязный список с заголовком в контейнере C++. Головной узел не хранит данные. Следующий элемент головного узла — это первый элемент, в котором хранятся данные. Предыдущий элемент головного узла соединен с последним элементом, в котором хранятся данные. данные. (Структура показана на рисунке ниже)
Структура каждого узла в связанном списке разделена на часть данных, передний указатель и задний указатель (ниже приведена структурная диаграмма и код).
Типы данных, а также передние и задние указатели в связанном списке генерируются шаблонами и могут быть адаптированы к встроенным и пользовательским типам.Причина, по которой здесь для определения класса используется struct, заключается в том, что типы переменных-членов структуры по умолчанию являются общедоступными, и можно легко вызывать другие функции.Здесь также есть конструктор list_node T(), который является анонимной переменной. Его функция используется не только для хранения данных. Кроме того, если при вызове конструктора list_node не записываются параметры, здесь также будет значение по умолчанию.
В списке есть две переменные-члена: _node, указатель на тип узла, и _size, который вычисляет количество узлов.
- 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;
- }
Мы определили базовую структуру списка и теперь собираемся добавить некоторые базовые функции, такие как вставка данных в список и использование итераторов для обхода списка.
Функция Push_back: сначала создайте новый узел newnode, затем сохраните данные X, которые необходимо сохранить в новом узле, найдите хвостовой узел и вставьте новый узел в узел рядом с хвостовым узлом.
- 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;
- }
В отличие от списка последовательностей, поскольку узлы связанного списка не хранятся вместе в непрерывном пространстве, ++ и разыменование указателя не могут напрямую получить данные, поэтому здесь нам нужно перегрузить * -> ++ -- и т. д. . и т.п. оператор.
- 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;
- }
После выполнения вышеуказанных операций мы можем отладить программу следующим образом. Хотя List не является массивом, мы можем получить доступ к элементам внутри List аналогичным образом.Хотя итераторы обходят каждый элемент контейнера одинаковым образом, они скрывают детали базовой реализации и предоставляют унифицированный метод доступа.。
- 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;
- }
Во-первых, мы можем написать функцию Insert(). Эту функцию можно повторно использовать другими функциями, такими как push_back и push_front, а также вставлять данные в любое место.
- 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());
- }
Поскольку возвращаемое значение функции стирания — это следующая позиция удаленных данных, поэтому отсутствие записи ++ здесь будет иметь эффект ++.
- ~list()
- {
- clear();
- delete _head;
- _head = nullpre;
- }
-
- void clear()
- {
- iterator it = begin();
- while(it != end())
- {
- it = erase(*it);
- }
- }
(1) Копировать структуру
- list( list<int> lt )
- {
- empty_init();
- for(auto e : lt)
- {
- this.push_back(e);
- }
- }
(2) Перегрузка назначения
- 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;
- }
Для итераторов константного типа нам необходимо понимать:Итераторы типа const не могут изменять данные, на которые указывает итератор, но сам итератор не может быть изменен.Сам итератор должен выполнять ++, -- и другие операции для выполнения операций обхода, поэтому при написании итератора константного типа я вношу только константные изменения в функцию, которую итератор возвращает к содержимому, на которое указывает, а другие функции остаются без изменений.
- 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);
- }
- }