//Node.H
//双链表的结点
#ifndef NODE_H
#define NODE_H
template<class DataType>
class Node//此类表示双链表中的一个结点
{
typedef Node* t_pNode;
typedef typename DataType t_Data;
typedef typename DataType* t_pData;
typedef typename DataType& t_rData;
typedef const typename DataType& t_crData;
private:
t_Data m_Data;//结点所包含的数据
t_pNode m_pLast;//指向上一个结点的指针
t_pNode m_pNext;//指向下一个结点的指针
public:
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Node()//双链表一个节点的构造函数
{
m_pLast=m_pNext=NULL;
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Node(t_crData data,const t_pNode plast=NULL,const t_pNode pnext=NULL)//双链表一个节点的构造函数
{
m_Data=data;
m_pLast=plast;
m_pNext=pnext;
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
~Node()//双链表的析构函数
{
}
public:
//////////////
//检查器
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
t_rData GetData()//得到此结点中的数据的引用
{
return m_Data;
};
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
t_pNode GetNextp()//得到指向下一个结点的指针
{
return m_pNext;
};
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
t_pNode GetLastp()//得到指向上一个结点的指针
{
return m_pLast;
};
//////////////
//修改器
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
void SetData(t_crData data)//设置结点的值，返回原来结点的值
{
m_Data=data;
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
void SetNextp(const t_pNode pnext)//设置指向后驱的指针，返回原来的值
{
m_pNext=pnext;////这里出现问题,Sometime,Maybe the pointer bug!
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
void SetLastp(const t_pNode plast)//设置指向前驱的指针，返回原来的值
{
m_pLast=plast;
}
};
#endif //NODE_H
--------------------------------------------------
//Node_test.cpp
//双链表的结点类的测试文件
#include<iostream>
#include"Data.h"
#include"Node.h"
using namespace std;
int main()
{
Data data1(10,11);
cout<<"双链表的结点类的测试"<<endl;
/////////////////////////////////
cout<<"测试1"<<endl;
Node<Data> node1;
if(node1.GetNextp()==NULL&&node1.GetLastp()==NULL)
cout<<"\tOK"<<endl;
else
cout<<"\t\tWRONG!"<<endl;
///////////////////////////////
cout<<"测试2"<<endl;
Node<Data> node2(data1);
if((node2.GetData()).GetID()==data1.GetID()
&&(node2.GetData()).GetKey()==data1.GetKey())
cout<<"\tOK"<<endl;
else
cout<<"\t\tWRONG!"<<endl;
////////////////////////////
cout<<"测试3"<<endl;
node1.SetData(data1);
if((node1.GetData()).GetID()==data1.GetID()
&&(node1.GetData()).GetKey()==data1.GetKey())
cout<<"\tOK"<<endl;
else
cout<<"\t\tWRONG!"<<endl;
////////////////////////////
cout<<"关于指针的系列操作函数没有严格测试，请在DList类中对其进行测试！"<<endl;
return 0;
}
----------------------------------------
//DList.H
//双链表
#ifndef DLIST_H
#define DLIST_H
#include<cassert>
#include "Node.h"
template<class DataType>
class DList//此类表示一个双链表
{
public:
typedef Node<DataType>* t_pNode;
typedef typename DataType t_Data;
typedef typename DataType* t_pData;
typedef typename DataType& t_rData;
typedef const typename DataType& t_crData;
private:
unsigned m_Size;//记录链表的长度(为加快链表的随机访问而设的)
t_pNode m_pHead;//指向链表的头的指针
t_pNode m_pEnd;//指向链表的尾部的指针
public:
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
DList():m_Size(0),m_pHead(NULL),m_pEnd(NULL)//双链表的构造函数
{
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
~DList()//双链表的析构函数
{
Clear();
}
public:
//////////////
//检查器
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
t_rData GetFrontData()//得到链表第一个元素的引用
{
return m_pHead->GetData();
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
t_rData GetBackData()//得到链表最后一个元素的引用
{
return m_pEnd->GetData();
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
t_pNode GetFrontp()//得到第一结点的指针
{
return m_pHead;
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
t_pNode GetBackp()//得到最后结点的指针
{
return m_pEnd;
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
t_rData GetData(const t_pNode pnode)//根据指针得到相关的数据
{
assert(pnode!=NULL&&"空指针不可以取内容");
return pnode->GetData();
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
t_pNode GetLastp(const t_pNode pnode)//得到当前指针的前驱地址，若为头节点，返回NULL
{
return pnode->GetLastp();
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
t_pNode GetNextp(const t_pNode pnode)//得到当前指针的后驱地址，若为尾节点，返回NULL
{
return pnode->GetNextp();
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
unsigned Size()//返回链表的尺寸
{
return m_Size;
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
bool Empty()//判断链表是否为空
{
if(m_Size==0)
return true;
else
return false;
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
t_pNode Find(t_crData refdata)//查找元素并返回指向包含它的结点的指针,失败返回NULL
{
for(t_pNode temp=m_pHead;temp!=m_pEnd;temp=temp->GetNextp())
{
if(temp->GetData()==refdata)
return temp;
}
if(m_pEnd->GetData()==refdata)//特殊情况的处理
return m_pEnd;
return NULL;
}
//////////////
//修改器
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
bool Erase(t_crData refdata)//删除数据区为refdata的第一个结点，若数据不存在返回false
{
t_pNode temp=Find(refdata);//得到指向元素的指针
if(temp!=NULL)//找到
{
return Erase(temp);
}
else
return false;
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
bool Erase(const t_pNode pnode)//删除指针所指结点，若pnode为空指针或指针不在链表内返回false
{
if(pnode==NULL)
return false;
if(pnode==m_pHead)
return PopFront();
else if(pnode==m_pEnd)
return PopBack();
else//在中间的
{
(pnode->GetNextp())->SetLastp(pnode->GetLastp());
(pnode->GetLastp())->SetNextp(pnode->GetNextp());
--m_Size;
delete pnode;
return true;
}
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
void Clear()//清空链表
{
t_pNode temp=m_pHead;
if(temp==NULL)
return;
for(;temp!=m_pEnd; temp=m_pHead)//这里也可以用m_Size进行计数
{
assert(temp!=NULL&&"这里的指针不应该为空");
m_pHead=m_pHead->GetNextp();
delete temp;
}
if(m_pEnd!=NULL)
delete m_pEnd;
m_Size=0;
m_pHead=m_pEnd=NULL;
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
void Insert(const t_pNode pnode,t_crData refdata)//在pnode所指的位置插入数据refdata，将原来的数据后移,传入NULL则将内容插入到表的末尾。
{
if(pnode==NULL)
{
PushBack(refdata);
return ;
}
if(pnode==m_pHead)
{
PushFront(refdata);
return ;
}
//以下为一般位置的插入
t_pNode temp=new Node<DataType>;
++m_Size;
assert(temp!=NULL&&"指针不能为空，内存分配失败");
temp->SetData(refdata);
temp->SetLastp(pnode->GetLastp());
temp->SetNextp(pnode);
pnode->SetLastp(temp);
(temp->GetLastp())->SetNextp(temp);
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
void PushBack(t_crData refdata)//将数据refdata存入链表的尾部
{
t_pNode temp=new Node<DataType>;
assert(temp!=NULL&&"指针不能为空，内存分配失败");
++m_Size;
temp->SetData(refdata);
if(m_pEnd==NULL)//链表为空！
{
m_pEnd=m_pHead=temp;
return;
}
temp->SetLastp(m_pEnd);//将新空间上连
temp->SetNextp(NULL);//新空间的封尾
m_pEnd->SetNextp(temp);//将链表的末尾下联到新空间
m_pEnd=temp;//导出链尾
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
bool PopBack()//删除最后一个结点，若链表已空返回false
{
assert(m_pEnd!=NULL&&"尾指针为空，不可进行PopBack操作");
if(m_pHead==m_pEnd)
{
delete m_pEnd;
m_pHead=m_pEnd=NULL;
m_Size=0;
return true;
}
m_pEnd=m_pEnd->GetLastp();
--m_Size;
delete m_pEnd->GetNextp();
m_pEnd->SetNextp(NULL);
return true;
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
void PushFront(t_crData refdata)//将数据refdata存入链表的顶端
{
t_pNode temp=new Node<DataType>;
assert(temp!=NULL&&"指针不能为空，内存分配失败");
++m_Size;
temp->SetData(refdata);
if(m_pHead==NULL)//链表为空！
{
m_pEnd=m_pHead=temp;
return;
}
temp->SetNextp(m_pHead);//将新空间下连
temp->SetLastp(NULL);//新空间的头为空
m_pHead->SetLastp(temp);//将链表的头上连到新空间
m_pHead=temp;//导出头指针
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
bool PopFront()//删除第一个结点，若链表已空返回false
{
assert(m_pHead!=NULL&&"头指针为空，不可进行PopFront操作");
if(m_pHead==m_pEnd)
{
delete m_pHead;
m_pHead=m_pEnd=NULL;
m_Size=0;
return true;
}
m_pHead=m_pHead->GetNextp();
--m_Size;
delete m_pHead->GetLastp();
m_pHead->SetLastp(NULL);
return true;
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
bool Swap(const t_pNode pnode1,const t_pNode pnode2)//交换两个结点的内容
//若其中有一个结点不在当前链表中返回false
{
assert(pnode1!=NULL&&pnode2!=NULL&&"空指针的内容不可操作");
t_Data data=pnode1->GetData();
pnode1->SetData(pnode2->GetData());
pnode2->SetData(data);
return true;
}
//////////////
//
//以下的函数用来调试,仅适用于内部包含类型，若要扩展，请在DataType类中重载ostream流里的操作符"<<"
//遍历打印链表的内容，用来观察链表的操作情况
#ifdef _DEBUG
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
void output()
{
t_pNode temp;
unsigned counter=0;
cout<<"以下为双链表中的内容："<<endl;
cout<<"头指针\t"<<m_pHead<<"\t尾指针\t"<<m_pEnd<<"\t元素个数\t"<<m_Size<<endl;
cout<<"_________________________________________________________________"<<endl;
cout<<"序号 前结点的指针 当前结点指针 后结点指针 结点中的内容"<<endl;
cout<<"_________________________________________________________________"<<endl;
for(temp=m_pHead; counter<m_Size; temp=temp->GetNextp(),++counter)
{
cout<<counter<<'\t'<<temp->GetLastp()<<'\t'<<temp<<'\t'<<temp->GetNextp()<<'\t'<<temp->GetData()<<endl;
}
cout<<"+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++"<<endl;
}
#endif //_DEBUG
};
#endif //DLIST_H
------------------------------------------
//DList_test.cpp
//双链表的测试文件
#include <iostream>
#include "DList.h"
#include "Data.h"
using namespace std;
int main()
{
cout<<"双链表的测试"<<endl;
cout<<"测试1"<<endl;
DList<Data> list1;
if(list1.Size()==0&&list1.Empty()==true)
cout<<"\tOK"<<endl;
else
cout<<"\t\tWROMG"<<endl;
////////////////////
cout<<"测试2"<<endl;
DList<int> list2;
list2.PushBack(3);
list2.PushBack(4);
list2.PushFront(2);
list2.PushFront(1);
if(list2.GetFrontData()!=1)cout<<"\t\tWRONG"<<endl;
if(list2.GetBackData()!=4) cout<<"\t\tWRONG"<<endl;
if(list2.Size()!=4||list2.Empty()==true)cout<<"\t\tWRONG"<<endl;
list2.PopFront();
list2.PopBack();
if(list2.Size()!=2)cout<<"\t\tWRONG"<<endl;
list2.Clear();
if(list2.Empty()==false||list2.Size()!=0)
cout<<"\t\tWRONG!"<<endl;
cout<<"\tOK"<<endl;
////////////////////////
cout<<"测试3"<<endl;
DList<char> list3;
list3.PushBack('B');
list3.PushBack('C');
list3.PushBack('E');
if(list3.GetData(list3.Find('B'))!='B'
||list3.GetData(list3.Find('C'))!='C'
||list3.GetData(list3.Find('E'))!='E'
)
cout<<"\t\tWRONG!1"<<endl;
list3.Insert(list3.GetFrontp(),'A');
if(list3.GetFrontData()!='A')
cout<<"\t\tWRONG!2"<<endl;
list3.Insert(NULL,'F');
if(list3.GetBackData()!='F')
cout<<"\t\tWRONG!3"<<endl;
list3.Insert(list3.Find('E'),'D');
if((list3.Find('D'))->GetData()!='D')
cout<<"\t\tWRONG!4"<<endl;
list3.Erase('F');
list3.Erase('A');
list3.Erase('D');
if(list3.Size()!=3
||list3.Find('F')!=NULL
||list3.Find('A')!=NULL
||list3.Find('D')!=NULL
)
cout<<"\t\tWRONG5"<<endl;
//到此为止，list3中的内容为；B，C ，E
list3.Swap(list3.GetFrontp(),list3.GetBackp());
if(list3.Size()!=3
||list3.GetFrontData()!='E'
||list3.GetBackData() !='B'
)
cout<<"\t\tWrong6"<<endl;
//到此为止，list3中的内容为；E C B
list3.Swap(list3.GetFrontp(),list3.Find('C'));
if(list3.GetFrontData()!='C')
cout<<"\t\tWrong7"<<endl;
cout<<"\tOK"<<endl;
///////////////////////
return 0;
}
---------------------------------------------
//DCList.H
//双循环链表
#ifndef DCLIST_H
#define DCLIST_H
#include"DList.h"
enum Direction//用来确定双循环链表中的行进方向
{
LAST,NEXT
};
////////////////////////////////////////////////////////////////
template<class DataType>
class DCList
{
typedef Node<DataType>* t_pNode;
typedef const typename DataType& t_crData;
private:
DList<DataType> m_List;//双向循环链表的数据存贮采用双链表
t_pNode m_pNow;//指向双向循环链表的当前位置
Direction m_DirectionFlag;
public:
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
DCList(Direction flag=NEXT):m_DirectionFlag(flag),m_pNow(NULL)//双向循环链表的构造
{
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
~DCList()//双向循环链表的析构
{
}
public:
//////////////
//检查器
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
bool Empty()//判断循环链表是否为空//利用DList的Empty函数
{
return m_List.Empty();
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
void Clear()//清空循环链表//利用Dlist的Clear函数
{
m_List.Clear();
m_pNow=NULL;
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
t_pNode GetNextp()//得到循环链表的下一个结点的指针
{
if(m_pNow==NULL)//在循环链表为空时不可以访问
return NULL;
else if(m_pNow!=m_List.GetBackp()&&Size()!=1)//正常情况
return m_List.GetNextp(m_pNow);
else//当当前指针指向存贮链表的末尾时，返回存贮链表的头指针
return m_List.GetFrontp();
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
t_pNode GetLastp()//得到循环链表的上一个结点的指针
{
if(m_pNow==NULL)
return NULL;
else if(m_pNow!=m_List.GetFrontp()&&Size()!=1)//正常情况
return m_List.GetLastp(m_pNow);
else//当前指针指向存贮链表的头部，返回存贮链表的尾指针
return m_List.GetBackp();
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
t_crData GetData()//得到循环链表当前位置的数据的引用
{
return m_List.GetData(m_pNow);
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
unsigned Size()//得到循环链表的尺寸
{
return m_List.Size();
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
void GoToLast()//将now移向Last一位
{
if(m_pNow==m_List.GetFrontp())//折回处理
{
m_pNow=m_List.GetBackp();
}
else//一般情况
{
m_pNow=m_List.GetLastp(m_pNow);
}
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
void GoToNext()//将now移向Next一位
{
if(m_pNow==m_List.GetBackp())//折回处理
{
m_pNow=m_List.GetFrontp();
}
else//一般情况
{
m_pNow=m_List.GetNextp(m_pNow);
}
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
void Go()//按照方向标志将now移动一位
{
if(m_DirectionFlag==LAST)
GoToLast();
else//m_DirectionFlag==NEXT
GoToNext();
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Direction GetDirection()//返回方向标志
{
return m_DirectionFlag;
}
//////////////的Direction所指的临位
//修改器
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
void Insert(t_crData data)//在当前位置插入数据，并将原来该为的数据移向Direction所指的方向。始终保证now指向刚才插入的新结点
{
if(m_pNow==NULL)
{
//assert(m_List.Empty()==true&&"在当前指针为空时数据区应该为空");
m_List.PushFront(data);
m_pNow=m_List.GetFrontp();
//assert(m_List.GetData(m_pNow)==data&&"必须保证当前指针始终指向刚插入的内容");
return;
}
//以下假定循环链表不为空
if(m_DirectionFlag==LAST)
{
m_pNow=GetNextp();
m_List.Insert(m_pNow,data);//将data插入到存贮链表的当前逻辑位置，将当前位置及其以后的内容后移一个位置。此时m_pNow仍然指向原来的存贮单元
m_pNow=GetLastp();
//assert(m_List.GetData(m_pNow)==data&&"必须保证当前指针始终指向刚插入的内容");
return;
}
else//m_DirectionFlag==NEXT//为默认的情况
{
m_List.Insert(m_pNow,data);
m_pNow=GetLastp();
//assert(m_List.GetData(m_pNow)==data&&"必须保证当前指针始终指向刚插入的内容");
return;
}
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
bool Erase()//删除当前结点的内容，并将now移向Direction所指的方向
{
if(m_pNow==NULL)
return false;
t_pNode temp=m_pNow;
Go();
return m_List.Erase(temp);
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
void SetDirection(const Direction direction_flag)//设置方向标志
{
m_DirectionFlag=direction_flag;
}
//////////////
//调试函数
#ifdef _DEBUG
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
void output()//用来在调试时遍历输出存贮链表的内容
{
cout<<"+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++"<<endl;
cout<<"以下为双循环链表中的内容："<<endl;
cout<<"当前指针为\t\t\t"<<m_pNow<<endl;
cout<<"当前指针所指的内容为：\t\t"<<m_pNow->GetData()<<endl;
m_List.output();
}
#endif //_DEBUG
};
#endif //DCLIST_H
----------------------------------------
//DCList_test.cpp
//双循环链表类DCList的测试文件
//////////////////////////////////////////
#include<iostream>
#include"Data.h"
#include"DCList.h"
using namespace std;
int main()
{
cout<<"双循环链表类DCList的测试"<<endl;
///////////////////////////////////////
cout<<"测试1"<<endl;
DCList<Data> list1;
if(list1.Size()!=0||list1.Empty()!=true)
cout<<"\t\tWrong"<<endl;
if(list1.GetDirection()!=NEXT)
cout<<"\t\tWrong"<<endl;
list1.SetDirection(LAST);
if(list1.GetDirection()!=LAST)
cout<<"\t\tWrong"<<endl;
DCList<Data> list12(LAST);
if(list12.GetDirection()!=LAST)
cout<<"\t\tWrong"<<endl;
cout<<"\tOK"<<endl;
///////////////////////////////////////
//#ifdef _DEBUG //引入调试“函数”，用来观察双链表的内部内容
//#define OUT() list2.output()
//#else
//#define OUT()
//#endif //_DEBUG
cout<<"测试2"<<endl;
DCList<int> list2;
list2.Insert(1);//OUT();
list2.Insert(2);//OUT();
list2.Insert(3);//OUT();
list2.Insert(4);//OUT();
if(list2.Size()!=4||list2.Empty()==true)
cout<<"\t\tWrong1"<<endl;
if(list2.GetData()!=4)
cout<<"\t\tWrong2"<<endl;
list2.Go();
if(list2.GetData()!=3)
cout<<"\t\tWrong3"<<endl;
list2.GoToLast();
list2.GoToLast();
if(list2.GetData()!=1)
cout<<"\t\tWrong4"<<endl;
list2.GoToNext();
if(list2.GetData()!=4)
cout<<"\t\tWrong5"<<endl;
cout<<"\tOK"<<endl;
//////////////////////////////////////
cout<<"测试3"<<endl;
DCList<int> list3(LAST);
list3.Insert(1);//list3.output();
list3.Insert(2);//list3.output();
list3.Insert(3);//list3.output();
list3.Insert(4);//list3.output();
if(list3.Size()!=4||list3.Empty()==true)
cout<<"\t\tWrong1"<<endl;
if(list3.GetDirection()!=LAST)
cout<<"\t\tWrong2"<<endl;
list3.SetDirection(NEXT);
if(list3.GetDirection()!=NEXT)
cout<<"\t\tWrong3"<<endl;
list3.Clear();
if(list3.Size()!=0||list3.Empty()==false)
cout<<"\t\tWrong4"<<endl;
cout<<"\tOK"<<endl;
return 0;
}
--------------------------------------
//队列-------基于双链表实现
//Queue.h
#ifndef QUEUE_H
#define QUEUE_H
#pragma once
#include "dlist.h"
template<class DataType>
class Queue:protected DList<DataType>
{
public:
Queue(void){}
~Queue(void){}
public:
//+++++++++++++++++++++++++++++++++++++++++++++++
t_rData Back()//返回队列最后一个元素的引用
{
return DList<DataType>::GetBackData();
}
//+++++++++++++++++++++++++++++++++++++++++++++++
t_rData Front()//返回队列第一个元素的引用
{
return DList<DataType>::GetFrontData();
}
//+++++++++++++++++++++++++++++++++++++++++++++++
unsigned Size()//得到队列的尺寸
{
return DList<DataType>::Size();
}
bool Empty()//查询队列是否为空
{
return DList<DataType>::Empty();
}
//+++++++++++++++++++++++++++++++++++++++++++++++
bool Pop()//从队列中删除一个元素
{
return DList<DataType>::PopFront();
}
//+++++++++++++++++++++++++++++++++++++++++++++++
void Push(t_crData data)//向队列中加入一个元素
{
DList<DataType>::PushBack(data);
}
//+++++++++++++++++++++++++++++++++++++++++++++++
void Clear()//清空队列
{
DList<DataType>::Clear();
}
};
#endif //QUEUE_H
----------------------------
//Queue队列类 的测试文件
//Queue_test.cpp
#include<iostream>
#include"Queue.h"
using namespace std;
int main()
{
Queue<int> Q;
cout<<"队列测试："<<endl;
//////////////////////////////
if(!Q.Empty()||Q.Size()!=0)
cout<<"\t\tWrong1"<<endl;
else
cout<<"OK1"<<endl;
/////////////////////////////
Q.Push(1);
Q.Push(2);
if(Q.Empty()||Q.Size()!=2)
cout<<"\t\tWrong2"<<endl;
else
cout<<"OK2"<<endl;
/////////////////////////////
if(Q.Back()!=2||Q.Front()!=1)
cout<<"\t\tWrong3"<<endl;
else
cout<<"OK3"<<endl;
////////////////////////////
Q.Pop();
if(Q.Size()!=1||Q.Empty()||Q.Size()!=1)
cout<<"\t\tWrong4"<<endl;
else
cout<<"OK4"<<endl;
/////////////////////////////
Q.Clear();
if(!Q.Empty()||Q.Size()!=0)
cout<<"\t\tWrong5"<<endl;
else
cout<<"OK5"<<endl;
return 0;
}
----------------------------------
//输入受限制的双端队列-------基于双链表实现
//deque_in_confine.h
#ifndef DEQUE_IN_CONFINE_H
#define DEQUE_IN_CONFINE_H
#pragma once
#include"DList.h"
template<class DataType>
class Deque_in_confine:protected DList<DataType>
{
public:
Deque_in_confine(void)
{
}
~Deque_in_confine(void)
{
}
public:
//+++++++++++++++++++++++++++++++++++++++++++++++
t_rData Back()//返回队列最后一个元素的引用
{
return DList<DataType>::GetBackData();
}
//+++++++++++++++++++++++++++++++++++++++++++++++
t_rData Front()//返回队列第一个元素的引用
{
return DList<DataType>::GetFrontData();
}
//+++++++++++++++++++++++++++++++++++++++++++++++
unsigned Size()//得到队列的尺寸
{
return DList<DataType>::Size();
}
bool Empty()//查询队列是否为空
{
return DList<DataType>::Empty();
}
//+++++++++++++++++++++++++++++++++++++++++++++++
bool Pop()//从队列中删除一个元素
{
return DList<DataType>::PopFront();
}
//+++++++++++++++++++++++++++++++++++++++++++++++
bool PopBack()//在队列的末尾删除元素
{
return DList<DataType>::PopBack();
}
//+++++++++++++++++++++++++++++++++++++++++++++++
void Push(t_crData data)//向队列中加入一个元素
{
DList<DataType>::PushBack(data);
}
//+++++++++++++++++++++++++++++++++++++++++++++++
void Clear()//清空队列
{
DList<DataType>::Clear();
}
};
#endif //DEQUE_IN_CONFINE_H
-------------------------
//Deque_in_confine_test.cpp
#include<iostream>
#include"deque_in_confine.h"
using namespace std;
int main()
{
Deque_in_confine<int> deque;
deque.Push(1);
if(deque.Front()!=1)
cout<<"\t\tWrong1"<<endl;
else
cout<<"OK1"<<endl;
///////////////////////////////
deque.Clear();
deque.Push(1);
deque.Push(2);
deque.Push(3);
deque.Push(4);
deque.PopBack();
if(deque.Back()!=3)
cout<<"\t\tWrong2"<<endl;
else
cout<<"OK2"<<endl;
/////////////////////////////////
if(deque.Size()!=3)
cout<<"\t\tWrong3"<<endl;
else
cout<<"OK3"<<endl;
return 0;
}
-----------------------------------
//输出受限制的双端队列-------基于双链表实现
//deque_out_confine.h
#ifndef DEQUE_OUT_CONFINE_H
#define DEQUE_OUT_CONFINE_H
#pragma once
#include"DList.h"
template<class DataType>
class Deque_out_confine :protected DList<DataType>
{
public:
Deque_out_confine(void)
{
}
~Deque_out_confine(void)
{
}
public:
//+++++++++++++++++++++++++++++++++++++++++++++++
t_rData Back()//返回队列最后一个元素的引用
{
return DList<DataType>::GetBackData();
}
//+++++++++++++++++++++++++++++++++++++++++++++++
t_rData Front()//返回队列第一个元素的引用
{
return DList<DataType>::GetFrontData();
}
//+++++++++++++++++++++++++++++++++++++++++++++++
unsigned Size()//得到队列的尺寸
{
return DList<DataType>::Size();
}
bool Empty()//查询队列是否为空
{
return DList<DataType>::Empty();
}
//+++++++++++++++++++++++++++++++++++++++++++++++
bool Pop()//从队列中删除一个元素
{
return DList<DataType>::PopFront();
}
//+++++++++++++++++++++++++++++++++++++++++++++++
void Push(t_crData data)//向队列中加入一个元素
{
DList<DataType>::PushBack(data);
}
//+++++++++++++++++++++++++++++++++++++++++++++++
void PushFront(t_crData data)//向队列前部加入元素
{
DList<DataType>::PushFront(data);
}
//+++++++++++++++++++++++++++++++++++++++++++++++
void Clear()//清空队列
{
DList<DataType>::Clear();
}
};
#endif //DEQUE_OUT_CONFINE_H
-----------------------------
//Deque_out_confine_test.cpp
#include<iostream>
#include"deque_out_confine.h"
using std::cout;
using std::cin;
using std::endl;
typedef Deque_out_confine<int> Deque;
int main()
{
Deque Q;
Q.Push(1);
Q.Pop();
if(!Q.Empty())
cout<<"\t\tWrong1"<<endl;
else
cout<<"OK1"<<endl;
////////////////////////////
Q.Push(1);
Q.Push(2);
Q.Push(3);
Q.Push(4);
cout<<"下面将输出1~4"<<endl;
do
{
cout<<Q.Front()<<" "<<Q.Size()<<endl;
}while(Q.Pop()&&!Q.Empty());
return 0;
}
--------------------------------------
//双端队列-------基于双链表实现
//deque.h
#ifndef DEQUE_H
#define DEQUE_H
#pragma once
#include"Queue.h"
template<class DataType>
class Deque:public Queue<DataType>
{
public:
Deque(void){}
~Deque(void){}
public:
//+++++++++++++++++++++++++++++++++++++++++++++++
bool PopBack()//在队列的末尾删除元素
{
return DList<DataType>::PopBack();
}
//+++++++++++++++++++++++++++++++++++++++++++++++
void PushFront(t_crData data)//向队列前部加入元素
{
DList<DataType>::PushFront(data);
}
};
#endif //DEQUE_H
------------------------------------
//Deque_test.cpp
#include<iostream>
#include"deque.h"
using namespace std;
int main()
{
Deque<int> Q;
Q.PushFront(4);
Q.PushFront(3);
if(Q.Front()!=3||Q.Back()!=4)
cout<<"\t\tWrong0"<<endl;
else
cout<<"OK0"<<endl;
///////////////////////////////
Q.PushFront(2);
Q.PushFront(1);
Q.PopBack();
if(Q.Size()!=3)
cout<<"\t\tWrong1"<<endl;
else
cout<<"OK1"<<endl;
//////////////////////////
cout<<"下面将输出1~3"<<endl;
do
{
cout<<Q.Front()<<endl;
}while(Q.Pop()&&!Q.Empty());
return 0;
}
-------------------------
//堆栈-------基于双链表实现
//Stack.h
#ifndef STACK_H
#define STACK_H
#pragma once
#include"DList.h"
template<class DataType>
class Stack : protected DList<DataType>
{
public:
Stack(void){}
~Stack(void){}
public:
//+++++++++++++++++++++++++++++++++++++++++++++++
bool Empty()//查询堆栈是否为空
{
return DList<DataType>::Empty();
}
//+++++++++++++++++++++++++++++++++++++++++++++++
void Pop()//弹栈操作
{
DList<DataType>::PopFront();
}
//+++++++++++++++++++++++++++++++++++++++++++++++
void Push(t_crData data)//压栈操作
{
DList<DataType>::PushFront(data);
}
//+++++++++++++++++++++++++++++++++++++++++++++++
unsigned Size()//得到堆栈的尺寸
{
return DList<DataType>::Size();
}
//+++++++++++++++++++++++++++++++++++++++++++++++
t_rData Top()//得到堆栈顶数据的引用
{
return DList<DataType>::GetFrontData();
}
//+++++++++++++++++++++++++++++++++++++++++++++++
void Clear()//清空堆栈
{
DList<DataType>::Clear();
}
//+++++++++++++++++++++++++++++++++++++++++++++++
};
#endif //STACK_H
-----------------------------------------
//Stack_test.cpp
#include <iostream>
#include "Stack.h"
using namespace std;
void main()
{
Stack<int> stack;
if(!stack.Empty()||stack.Size()!=0)
cout<<"\t\tWrong1"<<endl;
else
cout<<"OK1"<<endl;
stack.Push(4);
stack.Push(3);
stack.Push(2);
stack.Push(1);
cout<<"下面将输出1~4"<<endl;
for(;!stack.Empty();stack.Pop())
{
cout<<stack.Top()<<endl;
}
if(stack.Size()!=0)
cout<<"\t\tWrong2"<<endl;
else
cout<<"OK2"<<endl;
}
评论