发一个给你参考一下,跟你要求的一样,设计方式也一样.
入门的东西
[quote]
//CNode.h
template<typename T>
class CNode
{
private:
CNode<T> *next;
//指向下一节点循环指针
public:
T data;
CNode();
//construct
CNode(const T & item);
//更新表的方法
void InsertAfter(CNode<T> *p);
CNode<T>*DeleteAfter();
//保存下一节点的指针
CNode<T> *NextNode()const;
};
[\quote]
[quote]
//CNode.cpp
#include "CNode.h"
template<typename T>
CNode<T>::CNode()
{
next=this;
//下一节点为结点本身
}
//产生空表并初始化数据的构造函数
template<typename T>
CNode<T>::CNode(const T& item)
{
//将结点指向自身并初始化数据
next=this;
data=item;
}
//在当前结点之前插入结点P
template<typename T>
void CNode<T>::InsertAfter(CNode<T> * p)
{
//p指向当前结点的后继结点，当前结点指向P
p->next=next;
next=p;
}
//删除当前结点之后的结点，并返回指向其的指针
template<typename T>
CNode<T>*CNode<T>::DeleteAfter()
{
//保存指向被删除结点的指针
CNode<T> *tempPtr=next;
//若next==this ,表明没有其他结点，返回NULL
if(next==this)
return NULL;
//当前结点指向tempPtr的后继结点。
next=tempPtr->next;
//返回指向被删除结点的指针
return tempPtr;
}
template<typename T>
CNode<T>* CNode<T>::NextNode()const
{
return next;
}
[\quote]
[quote]
#include<iostream>
#include "CNode.h"
using namespace std;
void CreateList(CNode<int> *header,int n)
{
//开始往头结点插入
CNode<int>*currPtr=header,*newNodePtr;
int i;
//建立起N元循环链表
for(i=1;i<=n;i++)
{
//用数据值i申请结空间
newNodePtr=new CNode<int>( i);
//往表尾插入结点并将currPtr指针前移到表尾
currPtr->InsertAfter(newNodePtr);
currPtr=newNodePtr;
}
}
//对给定的n 元循环链表，通过每次便使第M个人出局直到最后一个末解决Josephus问题
void Josephus(CNode<int> *list,int n,int m)
{
CNode<int>*prevPtr=list,*currPtr=list->NextNode();
CNode<int> *deleteNodePtr;
//删除表中结点只到最后一个
for(int i=0;i<n-1;i++)
{
//从CURRPTR指向的当前客人开始数人，即指针前移m-1次
for(int j=0;j<m-1;j++)
{
//前移指针
prevPtr=currPtr;
currPtr=currPtr->NextNode();
//若CURRPTR指向表头，再移一次指针
if(currPtr==list)
{
prevPtr=currPtr;
currPtr=currPtr->NextNode();
}
}
cout<<"Delete person "<<currPtr->data <<endl;
//记录被删除的结点，并前移currPtr指针
deleteNodePtr=currPtr;
currPtr=currPtr->NextNode();
//从表中删除该结点
prevPtr->DeleteAfter();
delete deleteNodePtr;
//若CURRPTR为头指针，则再移一次
if(currPtr==list)
{
prevPtr=currPtr;
currPtr=currPtr->NextNode();
}
}
cout<<endl<<"Person"<<currPtr->data<<"Wins the cruise."<<endl;
//删除表中最后一个结点
deleteNodePtr=list->DeleteAfter();
delete deleteNodePtr;
}
int main()
{
CNode<int> list;
int n,m;
//n为表中人数，M为循环选择因子
cin>>n;
CreateList(&list,n);
cin>>m;
cout<<"Generated the member"<<m<<endl;
Josephus(&list,n,m);
system("pause");
return 0;
}
[\quote]
Josephus.rar
(1.53 KB)
