代码如下：
/*带头循环双向链表类的基本实现 */
#include<iostream>
using namespace std;
typedef int DataType;
struct ListNode
{
ListNode* next;
ListNode* prev;
DataType data;
ListNode(DataType x)
:data(x)
,next(NULL)
,prev(NULL)
{}
};
class List
{
typedef ListNode Node;
public:
List() //构造
:_head(new Node(DataType()))
{
_head->next = _head;
_head->prev = _head;
}
List(const List& l) //拷贝构造
:_head(new Node(DataType()))
{
_head->next=_head;
_head->prev=_head;
Node* stand1=_head;
Node* stand2=l._head->next;
do
{
Node* node=new Node(stand2->data);
stand1->next=node;
node->prev=stand1;
stand1=node;
stand2=stand2->next;
}
while(stand2!=l._head);
stand1->next=_head;
_head->prev=stand1;
}
List& operator=(const List& l) //运算符重载
{
Node* cur=_head->next;
Node* lcur=l._head->next;
int clen=0;
int llen=0;
if(_head->next!=_head)
{
do
{
clen++;
cur=cur->next;
}
while(cur!=_head);
}
else
clen=0;
if(l._head->next!=l._head)
{
do
{
llen++;
lcur=lcur->next;
}
while(lcur!=l._head);
}
else
llen=0;
cur=_head->next;
lcur=l._head->next;
//1.长度相等 2.长度大于 3.长度小于
if(clen==llen)
{
if(clen!=0)
{
do
{
cur->data=lcur->data;
cur=cur->next;
lcur=lcur->next;
}
while(cur!=_head);
return *this;
}
else
return *this;
}
else if(clen>llen)
{
if(llen!=0)
{
do
{
cur->data=lcur->data;
cur=cur->next;
lcur=lcur->next;
}
while(lcur!=l._head);
Node* parent=cur->prev;
while(cur!=_head)
{
Node* xx=cur;
cur= cur->next;
delete xx;
}
parent->next=_head;
_head->prev=parent;
return *this;
}
else
{
Node* stand=_head->next;
do
{
Node* xx=stand;
stand=stand->next;
delete xx;
}
while(stand!=_head);
_head->next=_head;
_head->prev=_head;
return *this;
}
}
else//clen<llen
{
if(clen!=0)
{
do
{
cur->data=lcur->data;
cur=cur->next;
lcur=lcur->next;
}
while(cur!=_head);
Node* parent=cur->prev;
do
{
Node* node =new Node(lcur->data);
parent->next=node;
node->prev=parent;
parent=node;
lcur=lcur->next;
}
while(lcur!=l._head);
parent->next=_head;
_head->prev=parent;
return *this;
}
else
{
Node* stand=_head->next;
do
{
Node* node=new Node(lcur->data);
stand->next=node;
node->prev=stand;
stand=node;
lcur=lcur->next;
}
while(lcur!=l._head);
_head->prev=stand;
stand->next=_head;
return *this;
}
}
}
~List()
{
Node* stand=_head->next;
if(stand!=_head)
{
do
{
Node* xx=stand;
stand=stand->next;
delete xx;
}
while(stand!=_head);
delete _head;
}
else
{
delete _head;
}
_head==NULL;
}
void PushBack(DataType x) //尾插
{
Node* stand=_head->prev;
Node* node(new Node(x));
// node->data=x;
stand->next=node;
node->prev=stand;
node->next=_head;
_head->prev=node;
cout<<node<<endl;
}
void PushFront(DataType x) //头插
{
Node* stand=_head->next;
Node* node(new Node(x));
//node->data=x;
_head->next=node;
node->prev=_head;
node->next=stand;
stand->prev=node;
}
void PopBack() //尾删
{
if(_head->next!=_head)
{
Node* stand=_head->prev;
stand->prev->next=_head;
_head->prev=stand->prev;
delete stand;
}
}
void PopFront() //头删
{
if(_head->next!=_head)
{
Node* stand=_head->next;
_head->next=stand->next;
stand->next->prev=_head;
delete stand;
}
}
Node* Find(DataType x)//查找
{
if(_head!=NULL)
{
Node* stand=_head;
do
{
if(stand->data==x)
return stand;
stand=stand->next;
}
while(stand!=_head);
return NULL;
}
return NULL;
}
void Insert(Node* pos, DataType x)//插入
{
Node* stand=_head->next;
do
{
if(stand==pos)
{
Node* node(new Node (x));
// node->data=x;
stand->prev->next=node;
node->prev=stand->prev;
node->next=stand;
stand->prev=node;
cout<<"插入成功"<<endl;
return;
}
stand=stand->next;
}
while(stand!=_head);
cout<<"插入失败"<<endl;
}
void Erase(Node* pos) //销毁节点
{
Node* stand=_head->next;
if(stand!=_head)
{
do
{
if(stand==pos)
{
stand->prev->next=stand->next;
stand->next->prev=stand->prev;
delete stand;
return;
}
stand=stand->next;
}
while(stand!=_head);
cout<< "欲删除的节点不存在 "<<endl;
}
cout<<"链表没有节点"<<endl;
}
void print()
{
Node* stand=_head->next;
while(stand!=_head)
{
cout<<stand->data<<endl;
stand=stand->next;
}
}
private:
Node* _head;
};
void test()
{
List l;
l.PushBack(1);
l.PushBack(2);
l.PushBack(3);
l.PushBack(4);
// l.PushFront(1);
// l.PushFront(1);
// l.PopFront();
// l.PopFront();
// l.PopBack();
// l.PopBack();
// l.Insert( (ListNode*)0x9e04028,5);
// List v(l);
// List a1;
// a1=v;
// List a2;
// a2.PushBack(1);
// a2=v;
// // List a3;
// a3.PushBack(1);
// a3.PushBack(2);
// a3.PushBack(3);
// a3.PushBack(4);
// a3.PushBack(5);
// a3=v;
cout<<l.Find(1)<<endl;
l.print();
}
int main()
{
test();
return 0;
}
/* 顺序表类的基础实现*/
//#include<iostream>
//using namespace std;
//
//typedef int DataType;
//
//class Vector
//{
// public:
// Vector()
// :_first(new DataType[10])
// ,_finish(_first)
// ,_endofstorage(&_first[10])
// {
// }
// Vector( Vector& v)
// :_first(new DataType[v.Capacity()])
// ,_finish(_first)
// ,_endofstorage(&_first[v.Capacity()])
// {
// // _first=new DataType[v.Capacity()];
// DataType* stand=_first;
// DataType* ffirst=v._first;
// DataType* ffinish=v._finish;
// while(ffirst!=ffinish)
// {
// *stand=*ffirst;
// stand++;
// ffirst++;
// }
// _finish=stand;
// _endofstorage=&_first[v.Capacity()];
//
// }
// Vector& operator=(const Vector& v);
// ~Vector()
// {
// if(_first)
// {
// cout<<".............."<<endl;
// delete[] _first;
// }
// _first=_finish=_endofstorage=NULL;
// }
// size_t Size()
// {
// return (_finish - _first);
// }
// size_t Capacity()
// {
// return (_endofstorage - _first);
// }
// void Expand(size_t n)
// {
// if(n>Capacity())
// {
// DataType* stand=new DataType[n];
// DataType* sfirst=stand;
// DataType* sfinish;
// DataType* sendofstorage;
// DataType* afirst=_first;
// size_t len=Capacity();
// while(afirst!=_finish)
// {
// *sfirst = *afirst;
// sfirst++;
// afirst++;
// }
// sfinish=sfirst;
// sendofstorage=&stand[len];
// if(_first)
// delete[] _first;
// _first=stand;
// _finish=sfinish;
// _endofstorage=&_first[n];
// }
// }
// void PushBack(DataType x)
// {
// if(_finish == _endofstorage)
// {
// cout<<">>>>>>"<<endl;
// Reserve(Capacity()*2+1);
// }
// *_finish=x;
// _finish++;
//
// }
// void Reserve(size_t n)
// {
// Expand(n);
// }
// void PopBack()
// {
// if(Size()>0)
// // cout<<"ccccccccc"<<endl;
// _finish--;
//
//
// }
//
// void Insert(size_t pos, DataType x)
// {
// if(pos<0||pos>Size())
// return;
// if(_finish==_endofstorage)
// {
// Reserve(Capacity()*2);
// }
// // DataType* stand=&_first[pos];
// // DataType* fistand=_finish;
// for(int i=Size();i>pos;i--)
// {
// _first[i]=_first[i-1];
// }
// _first[pos]=x;
// _finish++;
// }
// void Erase(size_t pos)
// {
// if(pos<0||pos>=Size())
// return;
// for(int i=pos;i<Size()-1;i++)
// {
// _first[i]=_first[i+1];
//
// }
// _finish--;
// }
// size_t Find(DataType x)
// {
// DataType* stand=_first;
// while(stand!=_finish)
// {
// if(*stand==x)
// {
// return stand - _first;
// }
// stand++;
// }
// return -1;
// }
// void print()
//
// {
// cout<<Size()<<endl;
// DataType* stand=_first;
// while(stand!=_finish)
// {
// cout<<*stand<<endl;
// stand++;
// }
// }
// private:
// DataType* _first;
// DataType* _finish;
// DataType* _endofstorage;
//};
//void test()
//{
// Vector v;
// v.PushBack(1);
// v.PushBack(2);
// v.PushBack(3);
// v.PushBack(4);
// v.PushBack(5);
// v.PushBack(6);
// v.PushBack(7);
// v.PushBack(8);
// v.PushBack(9);
// v.PushBack(10);
// v.PushBack(11);
//// v.Insert(3,21);
//// v.Insert(10,22);
//// v.Find(22);
//// cout<<v.Find(11)<<endl;
// v.Erase(8);
//// v.PopBack();
//// v.PopBack();
//// v.PopBack();
//// v.PopBack();
//// v.PopBack();
// Vector vv=v;
// v.print();
//}
//int main()
//{
// test();
// return 0;
//}