プライベートな連絡先の最初の情報
送料メール:
2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
リストは、C++ コンテナーの先頭の二重リンク リストです。ヘッド ノードはデータを格納しません。ヘッド ノードの前の要素は、データを格納する最後の要素に接続されます。データ。 (構造は下図に示します)
リンクリストの各ノードの構造はデータ部、フロントポインタ、バックポインタに分かれます(以下は構造図とコードです)
リンクされたリスト内のデータのタイプと前方および後方ポインターはテンプレートによって生成され、組み込みタイプおよびカスタム・タイプに適合させることができます。ここでクラスの定義に struct を使用する理由は、struct のデフォルトのメンバー変数の型が public であり、他の関数を簡単に呼び出すことができるためです。ここには、匿名変数である list_node コンストラクター T() もあります。さらに、list_node コンストラクターを呼び出すときにパラメーターが書き込まれない場合、その関数はここにデフォルト値も存在します。
リストには 2 つのメンバー変数があります。_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 を格納し、末尾ノードを見つけて末尾ノードの隣のノードに 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());
- }
Erase 関数の戻り値は削除されたデータの次の位置になるため、ここに ++ を書かないと ++ の効果が生じます。
- ~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);
- }
- }