[高手赐教]约瑟夫问题：为什么我的循环链表不能生成
#include <iostream.h>
template <class T> class circlist;
template <class T> class circlistnode{
friend class circlist <T> ;
public:
circlistnode(T d,circlistnode <T> * l):data(d),link(l){}
circlistnode(T d):data(d),link(NULL){}
private:
T data;
circlistnode <T> *link;
};
template <class T> class circlist{
public:
circlist(T value){first=new circlistnode <T> (value);last=first=first-> link;current=NULL;}
void firster(){current=first-> link;}
void insert(T & value);
void remove();
void prior();
void next();
T getdata();
void J(int n,int m);
private:
circlistnode <T> *first,*current,*last,*priorer;
};
template <class T> void circlist <T> ::insert(T & value){
if(current==NULL) //原表为空
current=first-> link=new circlistnode <T> (value,first); // <T> !!!!
else
{current-> link=new circlistnode <T> (value,current-> link); //not first
current=current-> link;
}
last=current;
}
template <class T> void circlist <T> ::remove(){
if(current!=NULL){
circlistnode <T> *tempptr=current;
current=current-> link;
priorer-> link=current;
delete tempptr;
if(current==first){
last=priorer;
current=current-> link;
}
}
}
template <class T> void circlist <T> ::prior(){
priorer=current;
}
template <class T> void circlist <T> ::next(){
current=current-> link;
if(current==first) current=current-> link;
}
template <class T> T circlist <T> ::getdata(){
return current-> data;
}
template <class T> void circlist <T> ::J(int n,int m){
firster();
for(int i=0;i <n-1;i++){
for(int j=0;j <m-1;j++){
next();
if(j==m-2) prior();
}
cout < < "delete person " < <getdata() < <endl;
remove();
}
}
void main(){
circlist <int> clist(0);
int n,m;
cout < < "请分别输入人数和报数数 " < <endl;
cin> > n> > m;
cout < < "请输入链表值 " < <endl;
for(int i=1;i <=n;i++){
clist.insert(i);
}
clist.J(n,m);
}
[解决办法]
template <class T> class circlist{
public:
circlist(T value){first=new circlistnode <T> (value);last=first=first-> link;current=NULL;}
last=first=first-> link;改为 last=first-> link=first;即可生成循环链表
[解决办法]
ms 太复杂了点：
/*约瑟夫环*/
#include <stdlib.h>
#include <stdio.h>
typedef struct node
{
int data;
struct node *next;
}LNode;
main()
{
LNode* Create(int,int);
LNode* GetNode(LNode *);
int Print(LNode *,int);
LNode *p;
int n,k,m;
do
{
printf ( "输入总人数 ");
scanf ( "%d ",&n);
}
while (n <=0);
do
{
printf ( "输入开始人的序号(1~%d) ",n);
scanf ( "%d ",&k);
}
while (k <=0 || k> n);
do
{
printf ( "输入间隔数字 ");
scanf ( "%d ",&m);
}
while(m <=0);
p=Create(n,k);
Print(p,m);
return 0;
}；
LNode* Create(int n,int k)/*创建循环链表*/
{
int start=k-1;
LNode *s,*p,*L=0,*t;
if (start==0) start=n;
while (n!=0)
{
s=(LNode *)malloc(sizeof(LNode));
if (L==0) p=s;
if (n==start) t=s;
s-> data=n;
s-> next=L;
L=s;
n--;
}
p-> next=L;
return t;
}
LNode* GetNode(LNode *p)/*出队函数*/
{
LNode *q;
for (q=p;q-> next!=p;q=q-> next);
q-> next=p-> next;
free (p);
return (q);
}
Print(LNode *p,int m)/*输出函数*/
{
int i;
printf ( "出队编号:\n ");
while (p-> next!=p)
{
for (i=1;i <=m;i++)
p=p-> next;
printf ( "%d ",p-> data);
p=GetNode(p);
}
printf( "%d\n ",p-> data);
return 0;
}
[解决办法]
我觉得我这个比较清晰简单
#include <iostream>
#include <cassert>
using namespace std;
struct simplelist
{
int data;
simplelist * link;
};
void josephus(int peoplenum,int pos,int count) //pos出列位置,初值即为第一个报数人
{
simplelist *p,*r,*list;
list=NULL;
for(unsigned int i=0;i <peoplenum;i++) //创建链表
{
p=new simplelist;
assert(p!=NULL);
p-> data=i;
if(list==NULL)
list=p;
else r-> link=p;
r=p;
}
p-> link=list;
p=list; //使链表循环起来
/* 当前指针移到第一个报数人*/
for(i=0;i <pos;i++)
{
r=p;
p=p-> link;
}
/*逐个出列，直到最后一个人 */
while(p-> link!=p)
{
/*找到出列者*/
for(i=0;i <count;i++)
{
r=p;
p=p-> link;
}
/*出列*/
r-> link=p-> link;
cout < <p-> data < < " "; //打印出列序号
delete p;
p=r-> link;
}
/*最后出列者*/
cout < <p-> data < <endl;
}
void main()
{
josephus(10,1,3);
}
[解决办法]
#include <iostream>
using namespace std;
template <class T> class circlist;
template <class T> class circlistnode
{
friend class circlist <T> ;
public:
circlistnode(T d,circlistnode <T> * l):data(d),link(l){}
circlistnode(T d):data(d),link(NULL){}
private:
T data;
circlistnode <T> *link;
};
template <class T> class circlist{
public:
circlist(T value)
{
first=new circlistnode <T> (value);
last=NULL;
current=NULL;
priorer = first;
}
void firster(){current=first-> link;}
void insert(T & value);
void remove();
void prior();
void next();
T getdata();
void J(int n,int m);
private:
circlistnode <T> *first,*current,*last,*priorer;
};
template <class T> void circlist <T> ::insert(T & value)
{
if(current==NULL)
{ //原表为空
priorer = first;
current=first-> link=new circlistnode <T> (value,first-> link); // <T> !!!!
current-> link = first;
}
else
{
priorer = current;
current-> link=new circlistnode <T> (value,current-> link); //not first
current=current-> link;
current-> link = first;
}
last=current;
}
template <class T> void circlist <T> ::remove()
{
if(current!=NULL)
{
circlistnode <T> *tempptr=current;
current=current-> link;
priorer-> link=current;
delete tempptr;
if(current==first)
{
last=priorer;
current=current-> link;
}
}
}
template <class T> void circlist <T> ::next()
{
priorer = current;
current=current-> link;
if(current==first)
{
current=current-> link;
priorer = last;
}
}
template <class T> T circlist <T> ::getdata()
{
return current-> data;
}
template <class T> void circlist <T> ::J(int n,int m)
{
firster();
for(int i=0;i <n-1;i++)
{
for(int j=0;j <m-1;j++)
{
next();
}
cout < < "delete person " < <getdata() < <endl;
remove();
}
}
void main(){
circlist <int> clist(0);
int n,m;
cout < < "请分别输入人数和报数数 " < <endl;
cin> > n> > m;
cout < < "请输入链表值 " < <endl;
for(int i=1;i <=5;i++)
{
clist.insert(i);
}
clist.J(n,m);
}
我给你改了以下。应该是几个指针不对
