网站做的文字乱码,怎么查询网站是谁做的,内网网站如何建设,计算机网站开发实现总结 作者简介#xff1a;დ旧言~#xff0c;目前大二#xff0c;现在学习Java#xff0c;c#xff0c;c#xff0c;Python等 座右铭#xff1a;松树千年终是朽#xff0c;槿花一日自为荣。 目标#xff1a;能手撕list模拟 毒鸡汤#xff1a;不为模糊… 作者简介დ旧言~目前大二现在学习JavaccPython等 座右铭松树千年终是朽槿花一日自为荣。 目标能手撕list模拟 毒鸡汤不为模糊不清的未来过分担忧只为清清楚楚的现在奋发图强。 望小伙伴们点赞收藏✨加关注哟 前言 前面我们已经学习了list的相关知识点必然我们要简单的模拟一下模拟list类比较复杂里面掺杂了我们学习双链表的知识点对模板的使用更加复杂还有对c类和对象的知识点使用起来更杂。对上面知识点忘了的小伙伴们大家先去巩固巩固学习list那就更加轻松那咱们走起。 ⭐主体
这里我们就不分解成三文件啦这里就创建两个文件List.h头文件Test.c测试代码文件 list基本框架结构
list为任意位置插入删除的容器底层为带头双向循环链表 模拟实现list要实现下列三个类 ①、模拟实现结点类 ②、模拟实现迭代器的类 ③、模拟list主要功能的类 list的结点的实现 list为任意位置插入删除的容器底层为带头双向循环链表所以每个结点都需有以下成员 前驱指针后继指针data值存放数据 结点类本质上是一个初始化函数在list类中只需要一个构造函数就行。 // 初始化结点类
templateclass T // 模板
struct ListNode
{// 定义两个指针ListNodeT* _next; // 前驱指针 ListNodeT* _prev; // 后驱指针// 存储节点值T _data; // 初始化列表(构造函数)ListNode(const T x T()):_next(nullptr),_prev(nullptr),_data(x){}
}; 问题解剖为什么是ListNodeT 首先C中用struct定义时可不加struct重点是这里用了一个类模板类模板的类名不是真正的类型且类模板不支持自动推类型即ListNode不是真正的类型定义变量时ListNodeT这种才是真正的类型也就是用类模板定义变量时必须 指定对应的类型 。 注结构体模板或类模板在定义时可以不加 T但使用时必须加 T。 list的迭代器类的实现 链表的物理空间是不连续的是通过结点的指针顺次链接。不能像先前的string和vector一样直接解引用去访问其数据结点的指针解引用还是结点结点指针还是结点指针在string和vector的物理空间是连续的所以这俩不需要实现迭代器类可以直接使用。 为了能让list像vector一样解引用后访问对应节点中的值访问到下一个数据我们需要单独写一个迭代器类的接口实现在其内部进行封装补齐相应的功能而这就要借助运算符重载来完成。
基本框架 框架结构 templateclass T,class Ref,class Ptr
struct __list_iterator
{typedef __list_nodeT Node;typedef __list_iteratorT, Ref, Ptr Self;Node* _node;
} ①、迭代器类模板为什么有三个参数 普通迭代器的话一个class T参数就够了由于const迭代器原因需要加两个参数两个参数名Refreference:引用和Ptrpointer:指针 ②、迭代器类是什么 迭代器类就一个节点的指针变量_node但是因为我们要运算符重载等一系列操作不得不把list的迭代器写成类完成那些操作list的迭代器才能正确的到下一位置解引用访问节点的值 ③、节点指针和迭代器的区别 Node* cur节点指针 和 iterator it迭代器它们指向同一个节点它们的物理地址是一样的但是它们的类型不同。*cur是一个指针的解引用取到的值是节点。*it是去调用迭代器的operator*返回值是节点中存的值。类型决定了对空间的解释权。 构造函数 迭代器的构造函数只需要一个指针构造就行 // 构造函数初始化
_list_iterator(Node* x):_node(x)
{} operator* *it调用的是函数返回节点中的值 // *it返回节点的值
Ref operator*()
{return _node-_data;
} 问题解剖返回值为什么是 Ref ??? Ref是模板参数因为迭代器类的模板参数Ref传入的要么是T要么是const T为了const迭代器和普通迭代器的同时实现意义就是一个只读一个可读可写 注比如之前讲的vector的迭代器*it假设it是迭代器变量就是拿到对应的值那么list的迭代器也要同理解引用迭代器就是为了访问对应位置的值那么list只要通过迭代器返回对应节点的值就好了*it我们是就想要对应的值 operator- // 返回节点值
Ptr operator-()
{return _node-data;
} 问题解剖为什么需要operator- list存了个自定义类型的Date类程序错误因为我们并没有重载Date类的operator 若是内置类型的话才可以正常输出那写一个operator重载吗不因为你无法确定要用哪些类也不能每个类都写operator那怎么办我们访问Date类本质是想访问它内置类型int的_year、_month和_day吧那我们不妨写个专属于自定义类型的operator-因为内置类型只需要*it就可以直接输出了但自定义类型不可以直接输出 利用operator-直接访问类的成员变量而内置类型可以直接输出 故从根源上解决问题 在迭代器中实现个operator- Ptr是迭代器的模板参数我们用来作为T*或const T*的 operator前置--与后置-- 代码实现 // it
self operator()
{_node _node-_next;// 返回节点return *this;
}
// it
self operator(int)
{// 拷贝self tmp(*this);// 向后走一个节点_node _node-_next;// 返回return tmp;
}// --it
self operator--()
{_node _node-_prev;// 返回节点return *this;
}
// it--
self operator--(int)
{// 拷贝self tmp(*this);// 向前走一个节点_node _node-prev;// 返回return tmp;
} 问题解剖迭代器对于list是什么意思 迭代器的意思就是想让其指向下一个节点--正好相反为了区分前置和后置--我们会用函数重载也就是多一个没用的参数int这个参数没什么用只是为了区分与-- operator和operator! 代码实现 // 判断
bool operator!(const self s)
{return _node ! s._node;
}
// 判断
bool operator(const self s)
{return _node s._node;
} 问题解剖两个迭代器怎么比较的 迭代器中就一个成员变量_node节点指针只要比较当前的节点指针是否相同即可这个操作在判断迭代器是否走到头有用比如 it ! s.end() 问题迭代器的拷贝构造和赋值和析构函数需我们自己实现吗 答不需要 因为迭代器存的就是一个节点指针而节点是属于链表list的那么它的释放应由list来实现那么迭代器的析构也无需我们自己写了。拷贝构造和赋值就是节点指针的拷贝和赋值即使指向同一节点了迭代器也不会析构而list的析构到时候只会释放这个节点一次不存在什么问题即我们无需深拷贝使用系统提供的浅拷贝即可。 list类的实现 在结点类和迭代器类都实现的前提下就可实现list主要功能增删等操作的实现。
基本框架 框架结构 //3、链表类
templateclass T
class list
{typedef __list_nodeT Node;
public:typedef __list_iteratorT,T,T* iterator;typedef __list_iteratorT,const T,const T* const_iterator;private:Node* _head;//头结点
} 问题解剖const_iterator(const迭代器的介绍) 我们知道const_iterator在begin()和end()中的返回值是需要用到的其主要作用就是当迭代器只读时使用普通迭代器和const迭代器的实现区别仅仅在于内部成员函数的返回值不同一个是引用class RefT或const T一个是指针class PtrT*或const T*当Ref时const T就是const迭代器的调用当Ref时T 时就是普通迭代器的调用 构造函数 框架结构 // 初始化函数
void empty_init()
{_head new Node;_head-_next _head;_head-_prev _head;
}// 构造函数
list() // 1.
{empty_init();
} 解释我们开辟一个头结点这里就是一个循环双向链表。 begin和end 代码实现 // 找头,这里有哨兵位
iterator begin()
{return _head-_next;
}
// 找尾哨兵位就是尾
iterator end()
{return _head;
}//const类
const_iterator begin() const
{return _head-_next;
}
const_iterator end() const
{return _head;
} 拷贝构造 代码实现 传统写法 //拷贝构造传统写法
list(const listT lt)
{_head new Node;//开辟一样的头结点_head-_next _head;_head-_prev _head;//1、用迭代器遍历/*const_iterator it lt.begin();while (it ! lt.end()){push_back(*it);it;}*///2、范围for遍历//遍历lt1把lt1的元素push_back到lt2里头for (auto e : lt){push_back(e);//自动开辟新空间完成深拷贝}
} 解释list的拷贝构造跟vector不同它的拷贝是拷贝一个个节点因为不连续的物理空间 那么我们可以用迭代器拿到list的一个个节点【上面是传统写法】 现代写法 templateclass InputIterator
list(InputIterator first, InputIterator last) {_head new Node();_head-_next _head;_head-_prev _head;while (first ! last) {push_back(*first);first;}
}
/* 拷贝构造现代写法L2(L1) */
list(const listT L) {_head new Node();_head-_next _head;_head-_prev _head;listT tmp(L.begin(), L.end());swap(_head, tmp._head); // 交换两个结点的指针
} clear函数 代码实现 // 销毁函数
void clear()
{// 找头iterator it begin();// 循环while (it ! end()){it erase(it);}
} 问题解剖it erase(it)什么意思 防止迭代器失效因为erase返回的是被删除位置的下一位置比如删除pos位置的pos位置被删除后这个位置的迭代器就失效了那就无法通过找到后面的位置了所以我们通过erase返回值来更新一下迭代器位置即更新到被删除位置的下一位置 operator 代码实现 //赋值运算符重载传统写法//lt1 lt3//listT operator(const listT lt)//{// if (this ! lt)// {// clear();//先释放lt1// for (auto e : lt)// push_back(e);// }// return *this;//}//赋值运算符重载现代写法// 赋值运算重载listT operator(listT lt){swap(lt);return *this;} 注释套用传值传参拷贝构造完成深拷贝 析构函数 代码实现 // 析构函数
~list()
{clear();delete _head;//删除除头结点以外的节点_head nullptr;//删去哨兵位头结点} insert函数 代码实现 // insert插入函数
iterator insert(iterator pos, const T x)
{Node* cur pos._node; // 迭代器pos处的结点指针Node* prev cur-_prev;Node* newnode new Node(x); // 创建新的结点 // prev newnode curprev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;//return iterator(newnode);return newnode;
} 问题解剖返回参数为什么是iterator本质是为了防止迭代器失效问题 注insert指的是插入到指定位置的前面 push_back 和 push_front 代码实现 // 调用插入函数尾插
void push_back(const T x)
{insert(end(), x);
}
// 调用插入函数头插
void push_front(const T x)
{insert(begin(), x);
} 这里的尾插和头插直接调用插入函数就可以了。 erase函数 代码实现 //erase
iterator erase(iterator pos)
{assert(pos ! end());Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;//prev cur next//链接prev和nextprev-_next next;next-_prev prev;//delete删去结点,因为每一个节点都是动态开辟出来的delete cur;//返回被删除元素后一个元素的迭代器位置//return next;return iterator(next);
} 问题剖析返回值问题 erase的返回值返回的是被删除位置的下一位置库里面这么规定的本质是因为删除元素一定会导致此位置的迭代器失效故返回被删除位置的下一次位置可以更新迭代器。 pop_back 和 pop_front 代码实现 // 调用删除函数尾删
void pop_back()
{erase(--end());
}
// 调用删除函数头删
void pop_front()
{erase(begin());
} 完整源代码
list.h:
#pragma once#includeassert.h
#includeiostreamnamespace lyk
{// 初始化templateclass T // 模板struct ListNode{// 定义两个指针ListNodeT* _next; // 前驱指针 ListNodeT* _prev; // 后驱指针// 存储节点值T _data; // 初始化列表(构造函数)ListNode(const T x T()):_next(nullptr),_prev(nullptr),_data(x){}};// list迭代器templateclass T,class Ref,class Ptr // 第二个参数是引用第三个参数是指针防止迭代器失效struct _list_iterator{typedef ListNodeT Node;typedef _list_iteratorT, Ref, Ptr self;Node* _node; // 定义节点// 构造函数初始化_list_iterator(Node* x):_node(x){}// itself operator(){_node _node-_next;// 返回节点return *this;}// itself operator(int){// 拷贝self tmp(*this);// 向后走一个节点_node _node-_next;// 返回return tmp;}// --itself operator--(){_node _node-_prev;// 返回节点return *this;}// it--self operator--(int){// 拷贝self tmp(*this);// 向前走一个节点_node _node-prev;// 返回return tmp;}// *it返回节点的值Ref operator*(){return _node-_data;}// 返回节点值Ptr operator-(){return _node-data;}// 判断bool operator!(const self s){return _node ! s._node;}// 判断bool operator(const self s){return _node s._node;}};// list的实现包含各种函数实现templateclass Tclass list{typedef ListNodeT Node;public:typedef _list_iteratorT, T, T* iterator;typedef _list_iteratorT, const T, const T* const_iterator;// 找头,这里有哨兵位iterator begin(){return _head-_next;}// 找尾哨兵位就是尾iterator end(){return _head;}//const类const_iterator begin() const{return _head-_next;}const_iterator end() const{return _head;}// 初始化函数void empty_init(){_head new Node;_head-_next _head;_head-_prev _head;}// 构造函数list() // 1.{empty_init();}list(listT It) // 2.拷贝构造 传统写法{empty_init();// 尾插for (const auto x : It){push_back(x);}}/* 拷贝构造现代写法L2(L1) */list(const listT L) {_head new Node();_head-_next _head;_head-_prev _head;listT tmp(L.begin(), L.end());swap(_head, tmp._head); // 交换两个结点的指针}// 销毁函数void clear(){// 找头iterator it begin();// 循环while (it ! end()){it erase(it);}}// 析构函数~list(){clear();delete _head;_head nullptr;}// 交换void swap(listT tmp){std::swap(_head, tmp._head);}// 赋值运算重载listT operator(listT lt){swap(lt);return *this;}// 调用插入函数尾插void push_back(const T x){insert(end(), x);}// 调用插入函数头插void push_front(const T x){insert(begin(), x);}// 调用删除函数尾删void pop_back(){erase(--end());}// 调用删除函数头删void pop_front(){erase(begin());}// insert插入函数iterator insert(iterator pos, const T x){Node* cur pos._node;Node* prev cur-_prev;Node* newnode new Node(x);// prev newnode curprev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;//return iterator(newnode);return newnode;}// erase删除函数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 next;}private:Node* _head; // 头节点};void test_list1(){listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);listint::iterator it lt.begin();while (it ! lt.end()){//*it 10;cout *it ;it;}cout endl;for (auto e : lt){cout e ;}cout endl;}void test_list2(){listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for (auto e : lt){cout e ;}cout endl;lt.push_back(5);lt.push_front(0);for (auto e : lt){cout e ;}cout endl;lt.pop_back();lt.pop_front();for (auto e : lt){cout e ;}cout endl;lt.clear();for (auto e : lt){cout e ;}cout endl;lt.push_back(10);lt.push_back(20);for (auto e : lt){cout e ;}cout endl;}void test_list3(){listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for (auto e : lt){cout e ;}cout endl;listint copy(lt);for (auto e : copy){cout e ;}cout endl;listint lt1;lt1.push_back(10);lt1.push_back(20);lt1.push_back(30);lt1.push_back(40);lt lt1;for (auto e : copy){cout e ;}cout endl;}void print_list(const listint lt){listint::const_iterator it lt.begin();while (it ! lt.end()){//*it 10;cout *it ;it;}cout endl;for (auto e : lt){cout e ;}cout endl;}void test_list4(){listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);print_list(lt);listint::iterator it lt.begin();while (it ! lt.end()){*it 10;cout *it ;it;}cout endl;}
} test.cpp:
#define _CRT_SECURE_NO_WARNINGS 1// 包含头文件
#includeiostream
#includelist
#includevector
#includealgorithm
using namespace std;#includeList.hint main()
{lyk::test_list4();return 0;
} 结束语 今天内容就到这里啦时间过得很快大家沉下心来好好学习会有一定的收获的大家多多坚持嘻嘻成功路上注定孤独因为坚持的人不多。那请大家举起自己的小手给博主一键三连有你们的支持是我最大的动力回见。
