双向链表,下一步就是类模板参数和迭代器实现一些简单算法!!
成都创新互联是一家专业提供北辰企业网站建设,专注与成都网站设计、成都网站建设、外贸网站建设、H5页面制作、小程序制作等业务。10年已为北辰众多企业、政府机构等服务。创新互联专业网站设计公司优惠进行中。
代码量等知识储备够了再优化
异常还理解不了
#ifndef LIST_H_
#define LIST_H_
#includeusing std::underflow_error;
namespace LIST
{
//结点
templatestruct Node
{
inline Node() { this->front = nullptr, this->rear = nullptr; }
//前驱
Node* front;
//值
Ty value;
//后继
Node* rear;
};
templateclass List
{
public:
//默认
List();
//n个type
List(const int, const Type&);
//copy
List(const List&);
//析构
~List();
//赋值
void assign(const int, const Type&);
void assign(const List&);
//尾部部操作
void push_back(const Type&);
void pop_back();
//头部操作
void push_fornt(const Type&);
void pop_fornt();
//赋值
List& operator=(const List&);
//清空
void rease();
//是否为空
const bool empty();
//占用
const int size();
//迭代器
class Iterator
{
public:
Iterator()
{
this->it_begin = nullptr;
this->it_end = nullptr;
this->it_move = nullptr;
}
Iterator& operator++()
{
if (this->it_move == this->it_end->rear)
throw underflow_error("无效的访问:链表已到底");
this->it_move = this->it_move->rear;
return *this;
}
Iterator& operator--()
{
if (this->it_move ==this->it_begin)
throw underflow_error("无效的访问:链表已到头");
this->it_move = this->it_move->front;
return *this;
}
Type& operator*()
{
if (this->it_begin == this->it_end->front)
throw underflow_error("链表为空,无法访问");
return this->it_move->value;
}
Node* it_begin;
Node* it_move;
Node* it_end;
};
//返回迭代器
const Iterator begin()const
{
List::Iterator it{};
it.it_begin = this->m_forward->rear;
it.it_end = this->m_back;
it.it_move = it.it_begin;
return it;
}
const Iterator end()const
{
List::Iterator it{};
it.it_begin = this->m_forward->rear;
it.it_end = this->m_back;
it.it_move = it.it_end;
return it;
}
private:
//头结点指针
Node* m_forward;
//尾节点指针
Node* m_back;
//自由前节点指针
Node* m_freed_forward;
Node* m_freed_back;
//容器占用
int m_size;
//辅助函数
//头尾结点指针归位
inline void launch();
};
//默认构造
templateLIST::List::List() { this->launch(); }
//n个type
templateLIST::List::List(const int n, const Type&Ty)
{
this->launch();
while (n != this->m_size)
this->push_back(Ty);
}
//copy
templateLIST::List::List(const List&li)
{
this->launch();
List::Iterator it = li.begin();
for (int i = 0; i< li.m_size; ++i)
{
this->m_back->value =*it;
this->m_back = new Node;
this->m_freed_back->rear = this->m_back;
this->m_back->front = this->m_freed_back;
this->m_freed_back = this->m_back;
++this->m_size;
++it;
}
}
//析构
templateLIST::List::~List()
{
while(this->m_size!=0)
this->pop_back();
delete this->m_forward;
delete this->m_back;
}
//类赋值
templatevoid LIST::List::assign(const int n, const Type& Ty)
{
while (this->m_size != 0)
this->pop_back();
while (this->m_size != n)
this->push_back(Ty);
}
templatevoid LIST::List::assign(const List&li)
{
while(this->m_size!=0)
this->pop_back();
List::Iterator it = li.begin();
for (int i = 0; i< li.m_size; ++i)
{
this->m_back->value = *it;
this->m_back = new Node;
this->m_freed_back->rear = this->m_back;
this->m_back->front = this->m_freed_back;
this->m_freed_back = this->m_back;
++this->m_size;
++it;
}
}
templateList& LIST::List::operator=(const List&li)
{
while(this->m_size!=0)
this->pop_back();
List::Iterator it = li.begin();
for (int i = 0; i< li.m_size; ++i)
{
this->m_back->value = *it;
this->m_back = new Node;
this->m_freed_back->rear = this->m_back;
this->m_back->front = this->m_freed_back;
this->m_freed_back = this->m_back;
++this->m_size;
++it;
}
return *this;
}
//尾插
templatevoid LIST::List::push_back(const Type& Ty)
{
//存值
this->m_back->value = Ty;
//创建新的尾节点
this->m_back = new Node;
//链接
this->m_freed_back->rear = this->m_back;
this->m_back->front = this->m_freed_back;
//更新占用并归位
this->m_freed_back = this->m_back;
++this->m_size;
}
//尾删
templatevoid LIST::List::pop_back()
{
if (this->empty())
throw underflow_error("容器为空,删除失败");
//改变尾节点
this->m_back = this->m_back->front;
//清除
delete this->m_freed_back;
//更新占用,归位
this->m_freed_back = this->m_back;
--this->m_size;
}
//头插
templatevoid LIST::List::push_fornt(const Type& Ty)
{
//存值
this->m_forward->value = Ty;
//创建新的头结点
this->m_forward = new Node;
//链接
this->m_freed_forward->front = this->m_forward;
this->m_forward->rear = this->m_freed_forward;
//更新占用并归位
this->m_freed_forward = this->m_forward;
++this->m_size;
}
//头删
templatevoid LIST::List::pop_fornt()
{
if (this->empty())
throw underflow_error("容器为空,删除失败");
//改变头结点
this->m_forward = this->m_forward->rear;
//清除
delete this->m_freed_forward;
//更新占用并归位
this->m_freed_forward = this->m_forward;
--this->m_size;
}
//辅助,头尾结点归位
templatevoid LIST::List::launch()
{
//初始化指针和占用
this->m_forward = new Node;
this->m_back = new Node;
this->m_freed_forward = this->m_forward;
this->m_freed_back = this->m_back;
this->m_size = 0;
//链接
this->m_forward->rear = this->m_back;
this->m_back->front = this->m_forward;
}
//杂项函数
templateconst bool LIST::List::empty()
{
if (this->m_size)
return false;
return true;
}
templateconst int LIST::List::size()
{
return this->m_size;
}
templatevoid LIST::List::rease()
{
while(this->m_size!=0)
this->pop_back();
}
}
#endif // !LIST_H_ 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
