地方志网站建设,巴中微小网站建设案例,网站建设和维护教程,书w3school网站建设教程上次讲了常用的接口#xff1a;今天就来进行模拟实现啦 文章目录 1.基本结构与文件规划2.空参构造函数#xff08;constructor)3.完善迭代器#xff08;iterator#xff09;(begin(),end())4.List Capacity#xff08;size(),empty())4.增删改查(push_back,pop_back,pop_f…上次讲了常用的接口今天就来进行模拟实现啦 文章目录 1.基本结构与文件规划2.空参构造函数constructor)3.完善迭代器iterator(begin(),end())4.List Capacitysize(),empty())4.增删改查(push_back,pop_back,pop_front,push_front,insert,erase)6.clear和swap7. 完善构造函数7.1list (size_type n, const value_type val value_type());7.2利用迭代器进行构造7.3拷贝构造 8.重载9.析构函数10.反向迭代器 1.基本结构与文件规划 list.h头文件包含类的全部(函数的声明与定义)reverseIterator.h文件进行反向迭代器的实现test.cpp源文件进行调用test函数测试和完善功能 基本结构
#pragma oncenamespace MyList
{// List的节点类templateclass Tstruct ListNode{ListNodeT* _prev;ListNodeT* _next;T _data;ListNode(const T xT()):_prev(nullptr),_next(nullptr),_data(x){}};//List的迭代器类templateclass T, class Ref, class Ptrstruct ListIterator{typedef ListNodeT Node;typedef ListIteratorT, Ref, Ptr Self;Node* _node;ListIterator(Node* node)//构造函数:_node(node){}ListIterator(const Self l)//拷贝构造函数:_node(l._node){}T operator*();T* operator-();Self operator();Self operator(int);Self operator--();Self operator--(int);bool operator!(const Self l);bool operator(const Self l);};//list类templateclass Tclass list{typedef ListNodeT Node;//默认是private 不给外面用public:typedef ListIteratorT, T, T* iterator;typedef ListIteratorT, const T, const T const_iterator;//构造函数list();list(int n, const T value T());template class Iteratorlist(Iterator first, Iterator last);//析构~list();// List Iteratoriterator begin();iterator end();const_iterator begin();const_iterator end();// List Capacitysize_t size()const;bool empty()const;// List AccessT front();const T front()const;T back();const T back()const;// List Modifyvoid push_back(const T val) { insert(end(), val); }void pop_back() { erase(--end()); }void push_front(const T val) { insert(begin(), val); }void pop_front() { erase(begin()); }// 在pos位置前插入值为val的节点iterator insert(iterator pos, const T val);// 删除pos位置的节点返回该节点的下一个位置iterator erase(iterator pos);void clear();void swap(listT l);private:Node* _head;};
};ListNode 结构体 定义了链表的节点结构包含了三个成员变量前驱指针 _prev、后继指针 _next 和数据 _data。构造函数初始化了这些成员变量允许在创建节点时指定初始值。 ListIterator 结构体 定义了链表的迭代器结构包含了指向节点的指针 _node。重载了一系列操作符如 *、-、、--、!、以便于对链表进行遍历和操作。 list 类 包含了迭代器的定义、构造函数、析构函数以及一系列的操作函数。定义了两种迭代器类型iterator 和 const_iterator分别用于可修改的迭代和只读的迭代。实现了一系列的操作函数
2.空参构造函数constructor) list(){_head new Node;//去调用Node的默认构造函数了_head-_next _head;_head-_prev _head;//带头双向循环链表是这样的}使用new动态开辟调用默认构造函数了 3.完善迭代器iterator(begin(),end())
这里为什么我们要把迭代器封装为一个类呢明明之前模拟vector和string时就直接typedef了 之前模拟vector和string时二者底层都是连续的想要到下一个可以直接想要得到里面的数据可以直接*。 但是现在对于list是不行的我们就需要重载各种运算符但是底层又是一个指针内置类型不能重载现在就只能封装进一个类里就能重载了 //List的迭代器类templateclass T, class Ref, class Ptrstruct ListIterator{typedef ListNodeT Node;typedef ListIteratorT, Ref, Ptr Self;Node* _node;ListIterator(Node* node)//构造函数:_node(node){}ListIterator(const Self l)//拷贝构造函数:_node(l._node)//这里是浅拷贝(写不写都行//新创建的迭代器和原迭代器指向相同的内存地址{}Ref operator*(){return _node-_data;}Ptr operator-(){return (_node-_data);}Self operator()//前置{_node _node-_next;//自己要更新return *this;}Self operator(int){Self s(*this);_node _node-_next;return s;}Self operator--(){_node _node-_prev;//自己要更新return *this;}Self operator--(int){Self s(*this);_node _node-_prev;return s;}bool operator!(const Self l){return _node ! l._node;}bool operator(const Self l){return _node l._node;}};//list类templateclass Tclass list{typedef ListNodeT Node;//默认是private 不给外面用public:typedef ListIteratorT, T, T* iterator;typedef ListIteratorT, const T, const T const_iterator;//构造函数list(){_head new Node;//去调用Node的默认构造函数了_head-_next _head;_head-_prev _head;//带头双向循环链表是这样的}// List Iteratoriterator begin(){return _head-_next;//隐式类型转换由单参构造函数支撑}iterator end(){return _head;}const_iterator begin(){return _head-_next;}const_iterator end(){return _head;}private:Node* _head;};
};4.List Capacitysize(),empty()) // List Capacitysize_t size()const{size_t size 0;iterator it begin();while (it ! end()){size;it;}return size;}bool empty()const{return size() 0;}4.增删改查(push_back,pop_back,pop_front,push_front,insert,erase) // List Modifyvoid push_back(const T val) //尾插{ insert(end(), val); }void pop_back() //尾删{ erase(--end());}void push_front(const T val) //头插{ insert(begin(), val);}void pop_front()//头删{ erase(begin());}// 在pos位置前插入值为val的节点iterator insert(iterator pos, const T val){Node* cur pos._node;Node* prev pos._node-_prev;Node* newnode new Node(val);//创建新节点newnode-_next cur;cur-_prev newnode;newnode-_prev prev;prev-_next cur;return newnode;//隐式类型转换}// 删除pos位置的节点返回该节点的下一个位置iterator erase(iterator pos){assert(pos ! _head);Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;prev-_next next;next-_prev prev;delete cur;return next;}使用test1函数看功能是否正常 void print(MyList::listint lt){listint::iterator it lt.begin();while (it ! lt.end()){cout *it ;it; // 更新迭代器}cout endl;}void test1(){MyList::listint lt;lt.push_back(1);lt.push_back(2);//尾插2个print(lt);lt.pop_back();//尾删一个print(lt);lt.push_front(0);//头插一个print(lt);lt.pop_front();//头删一个print(lt);}6.clear和swap void clear(){//删除除头结点(_head)以外的节点iterator it begin();while (it ! end()){it erase(it);}}void swap(listT l){std::swap(_head, l._head);}7. 完善构造函数
7.1list (size_type n, const value_type val value_type());
list(int n, const T value T())
{_head new Node;_head-_next _head;_head-_prev _head;for (int i 0; i n; i){push_back(value);}
} 7.2利用迭代器进行构造 template class Iteratorlist(Iterator first, Iterator last){while (first ! last){push_back(*first);first;}}为什么使用模版 因为可能使用其他类型的迭代器来进行初始化 7.3拷贝构造 list(const listT lt){_head new Node;_head-_next _head;_head-_prev _head;iterator it copy.begin();while (it ! copy.end()){push_back(*it);it;}}8.重载 listT lt operator(listT lt){swap(lt);return *this;}注意这里的参数不是常量引用而是按值传递的。这是因为在赋值操作符中我们会调用 swap 函数按值传递可以保证传入的参数会被复制一份避免对原对象的修改。在函数体内我们调用了 swap 函数将当前对象和传入的对象进行内容交换然后返回 *this即当前对象的引用。 9.析构函数 ~list(){clear();delete _head;_head nullptr;}调用clear函数后就只剩下头结点了 10.反向迭代器 我们再次使用封装的思想封装一个反向迭代器进去 #pragma oncetemplate class iterator,class Ref,class Pre
struct reserve_iterator
{typedef reserve_iteratoriterator, Ref, Pre self;iterator _it;reserve_iterator(iterator it):_it(it) {}self operator(){--_it;return *this;}self operator(int){self tmp *this;--_it;return tmp;}self operator--(){_it;return *this;}self operator--(int){self tmp *this;_it;return tmp;}Ref operator*(){iterator tmp _it;--tmp;return *tmp;}Pre operator-(){return (operator*());}bool operator!(const self s){return _it ! s._it;}bool operator(const self s){return _it s._it;}};此时那list类里就是这样 好啦list的内容也结束啦下次就是Stack和Queue了。感谢大家支持
