내 연락처 정보
우편메소피아@프로톤메일.com
2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
목록은 C++ 컨테이너의 머리가 있는 이중 연결 목록입니다. 헤드 노드의 다음 요소는 데이터를 저장하는 첫 번째 요소입니다. 데이터. (구조는 아래 그림과 같습니다)
연결리스트의 각 노드의 구조는 데이터 부분, 앞 포인터, 뒤 포인터로 나누어진다. (다음은 구조도와 코드이다)
연결된 목록의 데이터 유형과 앞/뒤 포인터는 템플릿에 의해 생성되며 내장 유형 및 사용자 정의 유형에 맞게 조정할 수 있습니다.여기서 클래스를 정의하기 위해 struct를 사용하는 이유는 struct의 기본 멤버 변수 유형이 public이고, 다른 함수를 쉽게 호출할 수 있기 때문이다.여기에는 익명 변수인 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를 구축한 다음 newnode에 저장해야 하는 데이터 X를 저장하고 tail 노드를 찾아서 tail 노드 옆에 있는 노드에 newnode를 삽입합니다.
- 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 유형 반복자의 경우 다음을 이해해야 합니다.const 유형의 반복자는 반복자가 가리키는 데이터를 수정할 수 없지만 반복자 자체는 수정할 수 없습니다.순회 작업을 수행하려면 반복자 자체가 ++, -- 및 기타 작업을 완료해야 하므로 const 유형 반복자를 작성할 때 반복자가 가리키는 내용을 반환하는 함수에 대해서만 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);
- }
- }