C++双向链表单向链表循环链表完美版

// 单链表循环链表双向链表的简单实现.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include
#include
using namespace std;

const int ZERO_ = 0;
const int ONE_ = 1;

template
class ListNode
{
public:
ListNode *prior, *next;/*前驱指针，后驱指针*/
type data;/*存放数据*/
ListNode() { prior = NULL; next = NULL; }
ListNode(const type &val, ListNode &item = NULL)
{/* for 循环 and 单链*/
this->data = val;
this->next = item;
}/*构造函数的重载*/
ListNode(const type &val, ListNode *item_prior = NULL, ListNode *item_next = NULL)
{/*for 双向*/
this->data = val;
this->prior = item_prior;
this->next = item_next;
}
};

template
class ab_List/*基类链表*/
{
public:
ListNode *Get_Head(){ return head; }/*弹出头部*/
ListNode *Get_Next(ListNode &item);/*弹出下一个元素，类型为指针*/
ListNode *Get_Next(int index);/*函数重载 通过下标弹出下一个元素，类型为指针*/
ListNode *Find_Index(int index);/*寻找下标函数*/
ListNode *Find_Val(type val);/*通过值寻找元素*/
void Make_Empty();/*清空函数*/
type Get_Val(int index);/* 获得下标为index的数据*/
type Get_Length(){ return length; }/*获得长度*/
type Get_Size(){ return length; }/*获得长度，和上面的函数功能一样*/
bool empty(){ if (length == 0) return true; else return false; }/*判断链表是否为空*/
bool Set_Val(type val, int index);/*设置下标index 的数据为 val*/
virtual bool Insert_Mem(type val, int index) = 0;/*在index下标之前插入一个元素*/
virtual type Remove_Index(int index) = 0;/*删除下标为Index的元素，并返回值*/
virtual type Remove_Val(type val) = 0;/*删除值为val的元素并返回值*/
virtual type Pop_Back() = 0;/*删除尾部*/
virtual type Pop_Head() = 0;/*删除第一个元素*/
virtual bool Push_Back(type val) = 0;/*从尾部压入*/
virtual bool Push_Head(type val) = 0;/*从头部压入*/
protected:
int length;/*存储当前的长度*/
ListNode *head;/*指向头部的指针*/
};
/*reserved*/
template
inline ListNode *ab_List ::Get_Next(ListNode &item)
{/*为循环链表和双向链表的，但是不影响单链表*/
return item.next == head ? item.next->next : item.next;
}
/*reserved*/
template
ListNode *ab_List ::Get_Next(int index)
{
ListNode *p = Find_Index(index);
if (p == NULL)
return p;
else
return p->next == head ? p->next->next : p->next;/*如果是末端*/
}
/*reserved*/
template
ListNode *ab_List::Find_Index(int index)
{
if (index < 0 || index > length)
return NULL;
else if (index == 0)/*如果是0直接返回*/
return head;
else
{
ListNode *p = head;
for (int i = ZERO_; i < ind

ex; ++i)
{
if (p == NULL)
break;/*如果出现断链*/
else
p = p->next;
}
return p;
}
}
/*reserved*/
template
ListNode *ab_List::Find_Val(type val)
{
ListNode *p = head;
if (p == NULL)
return p;
int i = ZERO_;
for (; i < length; ++i)
{
p = p->next;
if (p->data == val)
return p;
}
return p;
}
/*reserved*/
template
void ab_List::Make_Empty()
{
ListNode *p = this->head;
if (!p)
return;
if (this->length == 0)
return;
p = p->next;
for (int i = ZERO_; i < this->length; ++i)
{
this->head->next = p->next;
delete p;
p = this->head->next;
}
length = 0;
}
/*reserved*/
template
type ab_List::Get_Val(int index)
{
ListNode *p = Find_Index(index);
assert(p && p != head);
type val_ = p->data;
return val_;
}
/*reserved*/
template
bool ab_List::Set_Val(type val, int index)
{
ListNode *p = Find_Index(index);
if (p == NULL || p == head)
return false;
p->data = val;
return true;
}

template
class List:public ab_List
{
public:
List() { this ->head = new ListNode;this -> length = 0; }
List(List &item) { this->Copy_Mem(item); }
~List() { this->Make_Empty(); delete this ->head; }
List &Copy_Mem(List &item);
bool Insert_Mem(type val, int index);//插入元素
type Remove_Index(int index);//移除元素
type Remove_Val(type val);//移除元素
type Pop_Back();//删除末尾
type Pop_Head();//删除头部
bool Push_Back(type val);//从末端压入
bool Push_Head(type val);//从头部压入
List &operator =(List &item);
friend ostream &operator <<(ostream &os, List &item);
};

template
List &List::Copy_Mem(List &item)
{
ListNode *p = NULL, *pt = NULL, *temp = NULL;
this->Make_Empty();//节省空间，先把原来的清空了
this->head = NULL;
this->length = item.length;
if (!item.head)//如果目标是空的
return *this;//返回
this ->head = new ListNode;
if (!this ->head)
return *this;
this->head->data = item.head->data;
this->head->next = NULL;
p = this->head;
pt = item.head->next;
for (int i = ZERO_; i < item.length; ++i)
{
temp = new ListNode;
if (!temp)
return *this;
temp->data = pt->data;
temp->next = NULL;
p->next = temp;
p = p->next;
pt = pt->next;
}
return *this;
}

template
bool List::Insert_Mem(type val, int index)
{
ListNode *p = Find_Index(index - 1);
if (p == NULL)
return false;
ListNode *new_node = new ListNode(val,p->next);
assert(new_node);
p->next = new_node;
++length;
return true;
}

template
type List::Remove_Index(int index)
{
ListNode *p = Find_Index(index - 1);
assert(p);//这里开始可能删除head，所以拷贝函数

要考虑到
assert(p->next);/*不为空且不为最后一个*/
ListNode *temp = p->next;
p->next = temp->next;
type val_ = temp->data;
--length;
delete temp;
return val_;
}

template
type List::Remove_Val(type val)
{
ListNode *p = this->head;
ListNode *pt = NULL;
for (int i = ZERO_; i < this->length; ++i)
{
if (p->next->data == val)
break;
p = p->next;
}
assert(p->next);///p不指向尾部
pt = p;
p = p->next;
pt->next = p->next;
--length;
delete p;
return val;
}
//基于删除函数
template
type List::Pop_Back()
{
type val_ = this->Remove_Index(this ->length);
return val_;
}
/*基于删除函数*/
template
type List::Pop_Head()
{
type val_ = this->Remove_Index(ONE_);
return val_;
}
/*基于压入函数*/
template
bool List::Push_Back(type val)
{
bool ans = this->Insert_Mem(val,this->length + 1);
return ans;
}
/*基于压入函数*/
template
bool List::Push_Head(type val)
{

bool ans = this->Insert_Mem(val,ONE_);
return ans;
}

template
List &List::operator =(List &item)
{
this->Copy_Mem(item);
return *this;
}

template
ostream &operator <<(ostream &os,List &item)
{
ListNode *p = item.head;
assert(p);
p = p->next;
for (int i = ZERO_; i < item.length; ++i)
{
if (p = NULL)
break;
os << p->data << " ";
p = p->next;
}
os << endl;
return os;
}
/*循环链表*/
template
class CirList:public ab_List
{
public:
CirList();
CirList(CirList &item) { this->Copy_Mem(item); };
CirList &Copy_Mem(CirList &item);
bool Insert_Mem(type val, int index);
type Remove_Index(int index);
type Remove_Val(type val);
type Pop_Back();
type Pop_Head();
bool Push_Back(type val);
bool Push_Head(type val);
CirList &operator =(CirList &item);
friend ostream &operator <<(ostream &os,CirList &item);
private:
ListNode *tail;
};
/*构造函数 reserved*/
template
CirList ::CirList()
{
head = new ListNode;
tail = head;
tail->next = head;
length = 0;
}

template
CirList &CirList ::Copy_Mem(CirList &item)
{
ListNode *p = NULL, *pt = NULL, *temp = NULL;
this->Make_Empty();
this->head = NULL;
this->tail = this->head;
this->length = item.length;
if (!item.head)
return *this; //The algorithm description：
this ->head = new ListNode; //
if (!head) //
return *this;
this->head->data = item.head->data;
this->tail = this->head;
this->tail->next =this->head;
p = this->head;
pt = item.head->next;
for (int i = ZERO_; i < item.length; ++i)
{
temp = new ListNode;
if (!temp)
return *this;
temp->data = pt->data;
temp->next = this->head;

p->next = temp;
tail = temp;
p = p->next;
pt = pt->next;
}
return *this;
}

template
bool CirList::Insert_Mem(type val, int index)
{
ListNode *p = Find_Index(index - ONE_);
if (p == NULL)
return false;
ListNode *new_node = new ListNode(val,p ->next);
if (p->next == this->head)
{
tail = new_node;
tail->next = this->head;
}
p->next = new_node;
++this->length;
return true;
}

template
type CirList::Remove_Index(int index)
{
ListNode *p = Find_Index(index - ONE_);
assert(p);
assert(p->next != head);
ListNode *temp = p->next;
p->next = temp->next;
--length;
type val_ = temp->data;
if (temp->next == head)
{
this->tail = p;
this->tail->next = this->head;
}
delete temp;
return val_;
}

template
type CirList::Remove_Val(type val)
{
ListNode *p = this->head;
ListNode *temp = NULL;
assert(p);
for (int i = ZERO_; i < this->length; ++i)
{
if (p->next->data == val)
break;
else
p = p->next;
}
assert(!(p->next->next == head && p->next->data != val));
temp = p->next;
p->next = temp->next;
if (temp->next == this->head)
{
tail = p;
tail->next = head;
}
delete temp;
--length;
return val;
}
/*waiting*/
template
type CirList::Pop_Back()
{
type val_ = this->Remove_Index(this->length);
return val_;
}

template
type CirList ::Pop_Head()
{
type val_ = this->Remove_Index(ONE_);
return val_;
}

template
bool CirList::Push_Back(type val)
{
bool ans = this->Insert_Mem(val, this->length + ONE_);
return ans;
}

template
bool CirList::Push_Head(type val)
{
bool ans = this->Insert_Mem(val, ONE_);
return ans;
}

template
CirList &CirList::operator =(CirList &item)
{
this->Copy_Mem(item);
return *this;
}

template
ostream &operator <<(ostream &os, CirList &item)
{
ListNode *p = item.head;
assert(p);
for (int i = ZERO_; i < item.length; ++i)
{
p = p->next;
if (p == NULL)
break;
os << p->data << " ";
}
os << endl;
return os;
}

template
class DouList :public ab_List
{
public:
DouList(); //构造函数
DouList(DouList &item){ this->Copy_Mem(item); }; //基于拷贝函数
~DouList(){ this->Make_Empty(); delete head; }/*先把链表删除,再把表头删除*/
DouList &Copy_Mem(DouList &item);//拷贝函数
bool Insert_Mem(type val, int index); //在下标Index之前插入
type Remove_Index(int index);//删除下标为index的元素
type Remove_Val(type val); //删除值为val的元素
type Pop_Back(); //删除末端
type Pop_Head(); //删除头部
bool Push_Back(type val); //从末端压入
bool Push_Head(type val); //从头部压入
DouList &operator =(DouList &item);

//运算符重载且为深拷贝
friend ostream &operator <<(ostream &os,DouList &item);//运算符重载
protected:
ListNode *tail;
};

template
DouList ::DouList()
{
this->head = new ListNode;
tail = this->head;
tail->prior = this->head;
tail->next = this->head;
this->length = 0;
}

template
DouList &DouList::Copy_Mem(DouList &item)
{
ListNode *p = NULL, *pt = NULL, *temp = NULL;
if (this->length != 0)
this->Make_Empty();
this->length = item.length;/*先把长度复制过来*/
this->head = NULL;/*刚开始都先赋值一下*/
this->tail = NULL;/*头指针和尾指针都指向头部*/
if (!item.head)/*如果item是空的*/
return *this;
this->head = new ListNode;
if(!head)
return *this;
this->head->data = (item.head)->data;/*把表头的数据赋值过来*/
this->tail = this->head;
this->tail->next = this->head;
this->tail->prior = this->head;
p = this->head;
pt = item.head->next;
for (int i = ZERO_; i < item.length; ++i)
{
temp = new ListNode;
if (!temp)
return *this;
temp->data = pt->data;
temp->next = this->head;
temp->prior = p;/*前驱变成p*/
p->next = temp;/*前驱的下一个变成临时的temp*/
this->tail = temp;
p = p->next;
pt = pt->next;
}
return *this;
}

template
bool DouList ::Insert_Mem(type val, int index)
{
ListNode *p = Find_Index(index - ONE_);/*寻找之前一个元素*/
if (p == NULL)/*如果指针不合理*/
return false;
ListNode *new_node = new ListNode(val,p->next);
if (!new_node)/*如果分配失败*/
return false;
if (p->next == this->head)/*如果p为末端元素*/
{
tail = new_node;
tail->next = this->head;
this->head->prior = new_node;
}
new_node->prior = p;
p->next->prior = new_node;
p->next = new_node;/*前驱指针，后驱指针都要修改*/
++length;/*增加长度*/
return true;
}

template
type DouList::Remove_Index(int index)
{
ListNode *p = Find_Index(index - ONE_);
ListNode *temp = NULL;
assert(p != NULL);
if(((p->next) != (this->head)))/*p不为空，P不为末端*/
{
temp = p->next;
p->next = temp->next;
temp->next->prior = p;
if (temp->next == this->head)
{
tail = p;
tail->next = this->head;
this->head->prior = p;
}
}
else
{
temp = p;
p = p->prior;
this->tail = p;
tail->next = this->head;
this->head->prior = p;
}
type val_ = temp->data;
delete temp;
--length;
return val_;
}

template
type DouList::Remove_Val(type val)
{
ListNode *p = this->head;
ListNode *temp = NULL;
assert(p);
for (int i = ZERO_; i < this->length; ++i)
{
if (p->next->data == val)
break;
else
p = p->next;
}
assert(!(p->next == head && p->data != val));
temp = p->next;
p->next = temp->next;
t

emp->next->prior = p;
if (temp ->next == this->head)
{
tail = p;
tail->next = this->head;
this->head->prior = p;
}
delete temp;
--length;
return val;
}

template
type DouList::Pop_Back()
{
type val_ = this->Remove_Index(this->length);
return val_;
}

template
type DouList::Pop_Head()
{
type val_ = this->Remove_Index(ONE_);
return val_;
}

template
bool DouList::Push_Back(type val)
{
bool ans = this->Insert_Mem(val, this->length + ONE_);
return ans;
}

template
bool DouList::Push_Head(type val)
{
bool ans = this->Insert_Mem(val, ONE_);
return ans;
}

template
DouList &DouList ::operator =(DouList &item)
{
this->Copy_Mem(item);
return *this;
}

template /*输出函数的运算符重载*/
ostream &operator <<(ostream &os,DouList &item)
{
ListNode *p = item.head;
assert(p);
for (int i = ZERO_; i < item.length; ++i)
{
os << p->next->data << " ";
p = p->next;
}
os << endl;
return os;
}

int _tmain(int argc, _TCHAR* argv[])
{
DouList ans;
system("pause");
return 0;
}