程序代码:
//结点类声明
template <class T>
class CirListNode
{
private:
CirListNode<T> *link;//指向后继结点的指针
T data;//数据域
public:
CirListNode():link(NULL){};//构造函数
CirListNode(T value):link(NULL),data(value){}
~CirListNode(){};//析构函数
CirListNode<T>* GetLink();//返回结点指针
void SetLink(CirListNode<T>* next);//设置结点指针
T& GetData();
};
//结点类实现
程序代码:
#include"CirListNode.h"
template <class T>
void CirListNode<T>::SetLink(CirListNode<T>* next)
{
link=next;//改变指针
}
template <class T>
CirListNode<T>* CirListNode<T>::GetLink()
{
return link;
}
template <class T>
T& CirListNode<T>::GetData()
{
//返回结点的数据
return
data;
}
//单循环链表声明
程序代码:
#include"CirListNode.h"
template <class T>
class CirList
{
public:
CirList();//构造函数
~CirList(){};//析构函数
bool AddTail(T value);//向单循环链表表尾加入结点
void RemoveThis();//用来删除cur指向的结点
void RemoveAll();//删除所有结点
void SetBegin();//设置cur到head处
int GetCount();//获取结点个数
CirListNode<T>* GetCur();//返回指针cur
bool IsEmpty();//判断是否为空
T GetNext();//返回cur指向结点存储的数据
private:
CirListNode<T>* head;//头指针
CirListNode<T>* tail;//尾指针
CirListNode<T>* cur;//标志指针
};
//单循环链表实现
程序代码:
#include"CirList.h"
template <class T>
CirList<T>::CirList()
{
head=tail=new CirListNode<T>;//新建结点,并初始化head与tail
cur=NULL;//初始化标志指针
head->SetLink(head);//创建初始循环
}
template <class T>
bool CirList<T>::AddTail(T value)
{
//在链表尾加入新结点
CirListNode<T> *add=new CirListNode<T>(value);//新建结点,用value初始化
tail->SetLink(add);//把新结点链入表尾
tail=tail->GetLink();//移动tail至新表尾处
tail->SetLink(head);//使表尾指针指向表头
if(tail!=NULL)
return true;
else
return false;
}
template <class T>
void CirList<T>::RemoveThis()
{
//把cur指向的结点删除
if(cur==head)
{
cur=cur->GetLink();//表头不能删除,若指向表头就把指针下移一位
}
CirListNode<T> *preCur=cur;
for(int i=0;i<this->GetCount();i++)
{ //使preCur指向cur指向的前一个结点
preCur=preCur->GetLink();
}
preCur->SetLink(cur->GetLink());//删除cur指向的结点
cur=preCur->GetLink();//删除后cur向后移动一个结点
preCur=NULL;//使preCur置空
}
template <class T>
void CirList<T>::RemoveAll()
{
//删除所有结点
SetBegin();//从第一个结点开始
int length=GetCount();//获取链表长度
for(int i=0;i<length;i++)
{
RemoveThis();
}
cur=head;//把cur置于表头
}
template <class T>
void CirList<T>::SetBegin()
{
//置cur于表头处
cur=head;
}
template <class T>
int CirList<T>::GetCount()
{
int num=0;//定义整形变脸做计数器
CirListNode<T>* here=cur;//记录当前结点位置
while(cur->GetLink()!=here)
{
//遍历记录
cur=cur->GetLink();
++num;
}
cur=cur->GetLink();//使cur回到原来位置
return
num;
}
template <class T>
CirListNode<T>* CirList<T>::GetCur()
{
//返回当前指针
return cur;
}
template <class T>
bool CirList<T>::IsEmpty()
{
//判断是否为空
return
head->GetLink()==head;
}
template <class T>
T CirList<T>::GetNext()
{
if(cur==head)
{
//跳过表头结点
cur=cur->GetLink();
}
T num=cur->GetData();//获得数据
cur=cur->GetLink();//把cur移向下个结点
return num;
}
//约瑟夫问题求解
程序代码:
[color=#0000FF]#include
"CirList.h"
#include<cstdlib>
#include<iostream>
using namespace std;
int main()
{
CirList<
int> jos;
for(
int i=
1;i<
50;i++)
{
jos.AddTail(i);
}
jos.SetBegin();
int length=jos.GetCount();
for(i=
1;i<length;i++)
{
for(
int j=
0;j<
3;j++)
jos.GetNext();
jos.RemoveThis();
}
cout<<jos.GetNext()<<endl;
return 0;
}麻烦帮我看看,谢谢,写得有点乱[/color]