list&list模擬
- 1.list使用
- 2、list模擬
- 附錄
1.list使用
?list常見接口不做介紹,跟前面vector有相似之處,跟數據結構list基本一樣。
?因為list使用帶頭的雙向循環鏈表實現的,不能用小標訪問,只能用迭代器或范圍for訪問
?list有成員函數sort,來實現排序
?void unique(),去重,去重先先要排序
void test_list1()
{list<int> lt1 = { 10,2,3,3,4,5,6 };list<int> ::iterator it = lt1.begin();while (it != lt1.end()){cout << *it << " ";it++;}cout << endl;//list不支持sort//sort(lt1.begin(), lt1.end(), greater<int>());//list有自己的排序算法lt1.sort();it = lt1.begin();while (it != lt1.end()){cout << *it << " ";it++;}cout << endl;lt1.sort(greater<int>());it = lt1.begin();while (it != lt1.end()){cout << *it << " ";it++;}cout << endl;//unique 去重//先排序,在去重lt1.unique();for (auto e : lt1){cout << e << " "; //10 6 5 4 3 2}cout << endl;
}
?splice粘接
?void splice(const _iterator position,list& x);把x粘接到pos位置。
void test_list2()
{//splice:粘接std::list<int> mylist1, mylist2;std::list<int>::iterator it;// set some initial values:for (int i = 1; i <= 4; ++i)mylist1.push_back(i); // mylist1: 1 2 3 4for (int i = 1; i <= 3; ++i)mylist2.push_back(i * 10); // mylist2: 10 20 30it = mylist1.begin();++it; // points to 2mylist1.splice(it, mylist2); // mylist1: 1 10 20 30 2 3 4// mylist2 (empty)// "it" still points to 2 (the 5th element
}
void splice(const_iterator position,list& x,const_itrator i);
把list的第i個位置的數粘接到position位置.
void test_list3()
{list<int> mylist;for (int i = 1; i <= 4; i++){mylist.push_back(i); //mylist: 1 2 3 4} //想把3轉移到頭list<int>::iterator it = find(mylist.begin(), mylist.end(), 3);//void splice (const_iterator position, list& x, const_iterator i);//把list的第i個位置的數粘接到position位置mylist.splice(mylist.begin(), mylist, it);
}
2、list模擬
?先寫申請一個節點的類,把節點弄成一個類,相當與搞了一個新的數據類型。
//這是第一個類 ListNode
//所謂的類就是把成員對象和成員函數封裝在一起.
//這個全部弄成共有
//供后面存儲數據來用
template<class T>
struct ListNode
{ListNode<T>* _next;ListNode<T>* _prev;T _data;//const T& data是接受常量//不能權限放大,會報錯ListNode(const T& data = T()):_next(nullptr),_prev(nullptr),_data(data){}
};
?先寫list的大框架
template<class T>
class list
{typedef ListNode<T> Node;
public://無參構造函數就是默認構造list(){_head = new Node;_head->_prev = _head;_head->_next = _head;}void push_back(const T& data){//...}
private:Node* _head;
};
?寫push_back()先跑通框架
void push_back(const T& data)
{Node* newnode = new Node(data);Node* tail = _head->_prev;//tail newnode _headtail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;
}
?帶頭雙向循環鏈表,非常簡單,寫尾插即可,通過_head->_prev找到尾巴,尾巴,新節點,頭插入即可。
?然后把節點封裝成迭代器。把節點寫成一個類,封裝成迭代器所具有的屬性,即可。先寫·迭代器的行為,在進行封裝。
void list_test1()
{list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);list<int>::iterator it = lt1.begin();while (it != lt1.end()){cout << (*it) << " ";++it;}
}
?通過iterator it = it1.begin(),定義一個對象it,把it初始化為第一個節點的位置,然后進行以下運算符重載,!=,前置++,*就可以了。
?
template<class T>
class ListIterator
{typedef ListIterator<T> Self;typedef ListNode<T> Node;
public:ListIterator(Node* node = T()){_node = node;}//拷貝構造不要//賦值也不要T& operator*(){return _node->_data;}bool operator!=(const Self& it){return _node != it._node;}Self& operator++(){_node = _node->_next;return *this;}
public:Node* _node;
};
?const_iterator可以通過*的運算符重載的返回值+const實現,具體在增加一個模版參數即可,不過多敘述
//Ref引用
//Ptr指針
template<class T,class Ref,class Ptr>
struct ListIterator
{typedef ListNode<T> Node;typedef ListIterator<T,Ref,Ptr> Self;public:Node* _node;ListIterator(Node* node):_node(node){}//拷貝構造和賦值寫也可以,不寫也可以//這兒是淺拷貝ListIterator(const Self& it){_node = it._node;}//++itSelf& operator++(){_node = _node->_next;return *this;}Self& operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}Self& operator--(){_node = _node->_prev;return *this;}Self& operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}//T* operator->()//{// return &(_node->_data);//}Ptr operator->(){return &(_node->_data);}////這個是前置//T& operator*()//{// return _node->_data;//}//這個是前置Ref operator*(){return _node->_data;}bool operator!=(const Self& it){return _node != it._node;}bool operator==(const Self& it){return _node == it._node;}
};
?寫insert,iterator insert(iterator pos,const T& x);
在pos前面插入,返回的是x所在節點的位置
//在pos前面插入
//沒有迭代器失效
iterator insert(iterator pos, const T& x)
{Node* next = pos._node;Node* newnode = new Node(x);Node* prev = next->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = next;next->_prev = newnode;return iterator(newnode);
}
?寫erase,iterator erase(iterator pos),防止迭代器失效,返回的是pos的下一個位置
//erase后pos失效了,pos指向節點被釋放了
iterator erase(iterator pos)
{assert(pos != end());Node* cur = pos._node;Node* next = cur->_next;Node* prev = cur->_prev;prev->_next = next;next->_prev = prev;delete cur;return iterator(next);
}
?寫void clear(),清空,只剩頭結點
void clear()
{list<T>::iterator it = begin();while (it != end()){//防止迭代器失效it = erase(it);}
}
?寫~list(),先clear,在釋放頭節點
~list()
{//Node* cur = _head->_next;//while (cur != _head)//{// Node* next = cur->_next;// delete cur;// cur = next;//}//delete _head;//_head = nullptr;clear();delete _head;_head = nullptr;
}
?寫voId init_empty()保證有頭結點,在后面插入數據
void empty_init()
{_head = new Node;_head->_next = _head;_head->_prev = _head;
}
?寫拷貝構造,initializer_list< T >為參數的構造函數
//拷貝構造
//lt2(lt1)
list(const list<T>& lt)
{//引入這個是弄個頭結點empty_init();for (const auto& e : lt){push_back(e);}
}list(initializer_list<T>il)
{empty_init();for (const auto& e : il){push_back(e);}
}
//lt1 = lt3
//lt所在的
list<T>& operator= (list<T>lt)
{std :: swap(_head,lt._head);return *this;
}
?再說一下list& operator= (listlt),注意形參是拷貝構造的一份,和賦值_head,把頭地址交換即可,lt在棧楨銷毀時,就會銷毀交換的那個_head.
附錄
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <iostream>
#include <list>
#include <algorithm>
#include <assert.h>
using namespace std;namespace wyj
{//這是第一個類 ListNode//所謂的類就是把成員對象和成員函數封裝在一起.//這個全部弄成共有//供后面存儲數據來用template<class T>struct ListNode{ListNode<T>* _next;ListNode<T>* _prev;T _data;//const T& data是接受常量//不能權限放大,會報錯ListNode(const T& data = T()):_next(nullptr),_prev(nullptr),_data(data){}};//Ref引用//Ptr指針template<class T,class Ref,class Ptr>struct ListIterator{typedef ListNode<T> Node;typedef ListIterator<T,Ref,Ptr> Self;public:Node* _node;ListIterator(Node* node):_node(node){}//拷貝構造和賦值寫也可以,不寫也可以//這兒是淺拷貝ListIterator(const Self& it){_node = it._node;}//++itSelf& operator++(){_node = _node->_next;return *this;}Self& operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}Self& operator--(){_node = _node->_prev;return *this;}Self& operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}//T* operator->()//{// return &(_node->_data);//}Ptr operator->(){return &(_node->_data);}////這個是前置//T& operator*()//{// return _node->_data;//}//這個是前置Ref operator*(){return _node->_data;}bool operator!=(const Self& it){return _node != it._node;}bool operator==(const Self& it){return _node == it._node;}};//template<class T>//class ListConstIterator//{// typedef ListNode<T> Node;// typedef ListConstIterator<T> Self;// Node* _node;//public:// ListConstIterator(Node* node)// :_node(node)// {}// //拷貝構造和賦值寫也可以,不寫也可以// //這兒是淺拷貝// ListConstIterator(const Self& it)// {// _node = it._node;// }// //++it// Self& operator++()// {// _node = _node->_next;// return *this;// }// Self& operator++(int)// {// Self tmp(*this);// _node = _node->_next;// return tmp;// }// Self& operator--()// {// _node = _node->_prev;// return *this;// }// 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& it)// {// return _node != it._node;// }// bool operator==(const Self& it)// {// return _node == it._node;// }//};template<class T >class list{//封裝成私有,只能list內部用typedef ListNode<T> Node;public://ListIterator通過傳節點對節點進一步處理//typedef ListIterator<T> iterator;//typedef ListConstIterator<T> const_iterator;typedef ListIterator<T,T&,T*> iterator;typedef ListIterator<T,const T&,const T*> const_iterator;iterator begin(){//iterator it(_head->_next);//return it;//匿名對象//iterator這個類把這個節點封裝了,通過傳這個節點給iterator//調用iterator的構造函數,把節點給iterator中的_nodereturn iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator begin() const{//iterator it(_head->_next);//return it;//匿名對象return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;}list(){_head = new Node;_head->_next = _head;_head->_prev = _head;// empty_init()}//拷貝構造//lt2(lt1)list(const list<T>& lt){//引入這個是弄個頭結點empty_init();for (const auto& e : lt){push_back(e);}}list(initializer_list<T>il){empty_init();for (const auto& e : il){push_back(e);}}//lt1 = lt3//lt所在的list<T>& operator= (list<T>lt){std :: swap(_head,lt._head);return *this;}~list(){//Node* cur = _head->_next;//while (cur != _head)//{// Node* next = cur->_next;// delete cur;// cur = next;//}//delete _head;//_head = nullptr;clear();delete _head;_head = nullptr;}void clear(){list<T>::iterator it = begin();while (it != end()){//防止迭代器失效it = erase(it);}}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;insert(end(), x);}void pop_back(){erase(--end());}void push_front(const T& x){insert(begin(), x);}void pop_front(){erase(begin());}//在pos前面插入//沒有迭代器失效iterator insert(iterator pos, const T& x){Node* next = pos._node;Node* newnode = new Node(x);Node* prev = next->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = next;next->_prev = newnode;return iterator(newnode);}//erase后pos失效了,pos指向節點被釋放了iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* next = cur->_next;Node* prev = cur->_prev;prev->_next = next;next->_prev = prev;delete cur;return iterator(next);}private:Node* _head;};void func(const list<int>& lt){list<int>::const_iterator it = lt.begin();while (it != lt.end()){cout << (*it) << " ";++it;}cout << endl;}void test_list1(){list<int>l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);l1.push_back(5);//調用begin,把節點給iterator,用iterator來接受list<int>::iterator it = l1.begin();while (it != l1.end()){cout << (*it) << " ";*it += 10;++it;}cout << endl;for (auto e : l1){cout << e << " ";++it;}cout << endl;}struct Pos{Pos(int row =0,int col = 0):_row(row),_col(col){}int _row;int _col; };void test_list2(){list<Pos>lt1;lt1.push_back(Pos(100, 100));lt1.push_back(Pos(200, 200));lt1.push_back(Pos(300, 400));list<Pos>::iterator it = lt1.begin();while (it != lt1.end()){//為了可讀性,省略了一個箭頭cout << it->_row << ":"<<it->_col<<endl;//cout << it.operator->()->_row << ":" << it.operator->()->_col << endl;++it;}}void test_list3(){list<int>l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);l1.push_back(5);func(l1);cout << endl;l1.push_front(10);l1.push_front(10);l1.push_front(10);func(l1);cout << endl;l1.pop_front();l1.pop_front();func(l1);cout << endl;l1.pop_back();l1.pop_back();func(l1);cout << endl;}void test_list4(){list<int>lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);lt1.push_back(5);func(lt1);list<int> lt2(lt1);func(lt2);list<int> lt3;lt3 = lt1;func(lt2);}void test_list5(){list<int> lt1 = { 1,2,3,4,5,6 };func(lt1);}
}
#include "list.h"
#include "list1.h"
void test_list1()
{list<int> lt1 = { 10,2,3,3,4,5,6 };list<int> ::iterator it = lt1.begin();while (it != lt1.end()){cout << *it << " ";it++;}cout << endl;//list不支持sort//sort(lt1.begin(), lt1.end(), greater<int>());//list有自己的排序算法lt1.sort();it = lt1.begin();while (it != lt1.end()){cout << *it << " ";it++;}cout << endl;lt1.sort(greater<int>());it = lt1.begin();while (it != lt1.end()){cout << *it << " ";it++;}cout << endl;//unique 去重//先排序,在去重lt1.unique();for (auto e : lt1){cout << e << " "; //10 6 5 4 3 2}cout << endl;
}void test_list2()
{//splice:粘接std::list<int> mylist1, mylist2;std::list<int>::iterator it;// set some initial values:for (int i = 1; i <= 4; ++i)mylist1.push_back(i); // mylist1: 1 2 3 4for (int i = 1; i <= 3; ++i)mylist2.push_back(i * 10); // mylist2: 10 20 30it = mylist1.begin();++it; // points to 2mylist1.splice(it, mylist2); // mylist1: 1 10 20 30 2 3 4// mylist2 (empty)// "it" still points to 2 (the 5th element
}void test_list3()
{list<int> mylist;for (int i = 1; i <= 4; i++){mylist.push_back(i); //mylist: 1 2 3 4} //想把3轉移到頭list<int>::iterator it = find(mylist.begin(), mylist.end(), 3);//void splice (const_iterator position, list& x, const_iterator i);//把list的第i個位置的數粘接到position位置mylist.splice(mylist.begin(), mylist, it);
}int main()
{//wyj::test_list5();//test_list1();bit::list_test1();return 0;
}
?/*****************************************************/
?/*****************************************************/
?下來練習代碼
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <iostream>
#include <assert.h>
using namespace std;//先定義一個節點類
//所謂的類就是把成員變量和成員方法封裝在一起
//例如這個節點類
//成員變量是指定義節點的變量,方法是指操作這個節點的方法
//那么通過成員變量和成員方法把這個節點類封裝好之后,外面該怎么用呢?
//類可以理解為就是個新定義的數據類型,那么其它類使用,則在另一個類
//中定義這個類來使用
//比如:在另一個類中使用這個節點類,則在這個類中定義即可,并且你在
//這個類中定義一個節點類,會自動初始化,銷毀,這是類的一個特性namespace wyj
{template<class T>struct ListNode{//定義數據ListNode<T>* _prev;ListNode<T>* _next;T _data;//初始化ListNode(const T& data = T()):_prev(nullptr),_next(nullptr),_data(data){}//拷貝構造ListNode(const ListNode& node){_prev = node._prev;_next = node._next;_data = node._data;}//賦值ListNode& operator=(const ListNode& node){_prev = node._prev;_next = node._next;_data = node._data;return *this;}};//在這兒,把ListNode要封裝一下,符合iterator的特性template<class T,class Ref>class ListIterator{//要封裝節點,首先要把節點引進進來typedef ListNode<T> Node;typedef ListIterator<T, Ref> Self;public://ListIterator(Node* node = nullptr):_node(node){}ListIterator(const Self& iterator){_node = iterator._node;}ListIterator& operator=(const Self& iterator){_node = iterator._node;return *this;}ListIterator& operator++(){_node = _node->_next;return *this;}ListIterator operator++(int){ListIterator tmp = *this;_node = _node->_next;return tmp;}ListIterator& operator--(){_node = _node->_prev;return *this;}ListIterator operator--(int){ListIterator tmp = *this;_node = _node->_prev;return tmp;}Ref operator*() {return _node->_data;}bool operator!=(const Self& iterator){return _node != iterator._node;}bool operator==(const Self& iterator){return _node == iterator._node;}//private:public:Node* _node;};template<class T>class list{private://這兒把封裝好的ListNode重命名//ListNode可以理解為一種新的數據類型typedef ListNode<T> Node;public:typedef ListIterator<T,T&> iterator;typedef ListIterator<T,const T&> const_iterator;iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator begin() const{return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}//寫構造函數list(){//調用了Node的構造函數_head = new Node;_head->_prev = _head;_head->_next = _head;}template<class InputIterator>list(InputIterator first, InputIterator last){init_empty();while (first != last){push_back(*first);first++;}}list(initializer_list<T> il){init_empty();for (const auto& e : il){push_back(e);}}void init_empty(){_head = new Node;_head->_prev = _head;_head->_next = _head;}list(const list<T>& lt){init_empty();for (auto& e : lt){push_back(e);}}~list(){clear();delete _head;_head = nullptr;}//犯了一個錯誤,要加換了,還const//list& operator=(const list lt)list<T>& operator=(list<T> lt){swap(_head,lt._head);return *this;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}//插入void push_back(const T& data ){Node* newnode = new Node(data);Node* tail = _head->_prev;// tail newnode _headtail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;//insert(end(), data);}void pop_back(){erase(--end());}void push_front(const T& data){insert(begin(),data);}void pop_front(){erase(begin());}//在pos前面插入void insert(iterator pos, const T& data){Node* newnode = new Node(data);Node* cur = pos._node;Node* prev = cur->_prev;//prev newnode curprev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;}iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;return iterator(next);}private:Node* _head;};void list_test1(){list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);list<int>::iterator it = lt1.begin();for (auto e : lt1){cout << e << " ";}cout << endl;while (it != lt1.end()){(*it) += 10;it++;}for (auto e : lt1){cout << e << " ";}}void Func(const list<int>& lt){list<int>::const_iterator it = lt.begin();while (it != lt.end()){cout << (*it) << " ";it++;}cout << endl;}void list_test2(){list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);lt1.push_back(5);Func(lt1);lt1.push_front(10);lt1.push_front(20);lt1.push_front(30);Func(lt1);lt1.pop_front();lt1.pop_front();Func(lt1);lt1.pop_back();lt1.pop_back();Func(lt1);lt1.pop_back();lt1.pop_back();lt1.pop_back();lt1.pop_back();//lt1.pop_back();Func(lt1);}void list_test3(){//構造函數list<int> lt1 = { 1,2,3,4,5,6,7,8 };for (auto& e : lt1){cout << e << " ";}cout << endl;list<int> lt2 = lt1;for (auto& e : lt1){cout << e << " ";}cout << endl;list<int>lt3;lt3 = lt1;for (auto& e : lt1){cout << e << " ";}cout << endl;}
}
?
?
?
?