求助高手 数据结构课程设计约瑟夫环问题

内容2：约瑟夫（Joseph）环问题
【问题描述】
约瑟夫问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈,从1起报到k则出圈，下一个人再从1报起，如此下去直到圈中只有一人为止。求最后剩下的人的编号。
【说明】
1） 建议用循环链表存储方式，设计循环链表类和约瑟夫类。
2） 问题改进：在人数n、k及起始报数人确定的情况下，最后剩下的人的编号事前是可以确定的。若每人有一个密码Ki（整数），留作其出圈后的报到Ki后出圈。密码Ki可用随机数产生。这样事前无法确定谁是最后一人。
【选做内容】
1） 约瑟夫问题的改进算法。
2） 约瑟夫问题的报数方法若采用顺时针报数和逆时针报数交替进行，则如何设计数据结构？
【实现提示】
//结点结构和单循环链表类定义
enum ResultCode{Error,NoMemory,OutOfBounds,Underflow,Overflow};
template
struct Node
{ Node(){ link=NULL;}
Node(T e,Node*next)
{ data=e;
link=next;
}
T data;
Node*link;
};
template
class LinkList
{ private:
int n; //表长
Node *current,*front;
public:
LinkList(int mSize); //构造函数,不带表头结点单循环链表
~LinkList(); //析构函数
T RemoveCurrent(); //删除操作
void movenext(int n); //current后移n次
int CurrentPassword(){return current->password;}
T CurrentData(){return current->data;}
void toLocatioin(T &t); //将current指向元素为t的结点
void Output() const ; //输出链表
}; // Class LinkList
//单循环链表类部分成员函数实现
template
LinkList::LinkList(int mSize) //构造函数
{ int i;
Node *p;
current=new Node;
current->data=n=mSize;
front=current;
for(i=mSize-1;i>0;i--)
{ p=new Node(i, current);
current=p;
}
front->link=current;
}
// Joseph类定义
template
class Joseph
{ private:
int numOfBoy;
int startPosition;
int Interval;
public:
Joseph(int boys=10,int start=1,int m=3)
{
numOfBoy=boys;
startPosition=start;
Interval=m;
}
void GetWinner();
};// Joseph类
// Joseph类实现
template
void Joseph::GetWinner()
{
LinkList boys(numOfBoy);
boys.movenext(startPosition-1); //??
boys.Output();
cout< for(int i=1;i {
boys.movenext(interval-1);
cout< }
cout<<"\nThe winner is "<}
//主函数main
void main()
{ try
{ time_t time1=time(NULL);
struct tm *t;
t=localtime(&time1);
srand(t->tm_sec*t->tm_min+t->tm_hour);
cout<<"请输入初始数据：小孩数，间隔数，起始小孩号码：\n";
int total,interv,startboy;
cin>>total>>interv>>startboy;
Joseph jose(total,startboy,interv);
jose.GetWinner();
}
catch(enum ResultCode err)
{ switch(err)
{
case Error:cout<<"Location Error!\n";
case DeleteError:cout<<"Delete Error!\n";
}
}
}

#include
template
struct listnode{
T data;
int code;
listnode* link;
};

template
class list
{
public:
list(); //构造函数
list(const int );
~list(); //析构函数

T Delete(listnode* ); //删除单链表第i个数据结点，并返回该数据结点的取值
int Joseph(int );
void Print(); //输出单链表长度

private:
listnode* first; //头结点为空
listnode* first1;
int count; //存储链表长度，不算头结点
};

template
list::list() //构造函数
{

first=first1=NULL;
count=0;
}

template
list::list(const int count) //构造函数
{

listnode* q=first;
if(count==1)
{
first1=first=new listnode();

first->data=1; //输入data值
cout<<"请输入密码:"< cin>>first->code;
first->link=first;

}
else
{
first1=first=new listnode();

first->data=1; //输入data值
cout<<"请依次输入各个密码:"< cin>>first->code;

q=first;
for(int i=1;i {
listnode* p=new listnode();

p->data=i+1; //输入data值，有Bug!

cin>>p->code;
q->link=p;
q=p;
}
q->link=first;

}
this->count=count;
}

template
list::~list()
{
/*
if(first!=NULL)
{
listnode* q=first,*p;

for(int i=0;i{
p=q;
q=q->link;
delete p;
}
count=0;
}
*/

}

template
T list::Delete(listnode* a) //有Bug!! 忽略找不到的情况
{

if(a!=NULL)
{
if(count==1)
return first->data;
if(first==a)
{
listnode* q=first;
while(q->link!=first)
{
q=q->link;
}
T value=first->data;
q->link=first->link;
first=first->link;
return value;
}

listnode* q=first;
while(q->link!=a)
{
q=q->link;
}
T value=a->data;

q->link=a->link;

delete a;
count--;

return value;
}
}

template
void list::Print()
{
listnode* q=first;
while(q->link!=first) //for(int i=0;i{
cout<data<<" ";
q=q->link;
}
cout<data<<" ";
}

template
int list::Joseph(int m)
{

if(m<=0)
cout<<"不合理!"<
else
{

listnode *q;

for(int i=1;i {
first1=first1->link;
}

int a=first1->code;
q=first1;

if(first1->link!=first1) //
{
first1=first1->link;

}
else
{

Print(); //对最后节点的处理
return 0;
}

cout<
Joseph(a);

}

}

void main()
{
int num,code;
cout<<"请输入Joseph环的元素个数: ";
cin>>num;

list a(num); //整型数测试

cout<<"请输入第一个上限数: ";
cin>>code;

cout<<"出列顺序:"<a.Joseph(code);

}

#include
#include
#define NULL 0

typedef struct Node
{
int m;//密码
int n;//序号
struct Node *next;
}Node,*Linklist;

Linklist create(int z) //生成循环单链表并返回,z为总人数
{
int i,m;
Linklist H,r,s;
H=NULL;
printf("Output the code:");
for(i=1;i<=z;i++)
{
printf("\nInput m=");
scanf("%d",&m);
s=(Linklist)malloc(sizeof(Node));
s->n=i;
s->m=0;
printf("%d",s->m);
if(H==NULL)//从链表的第一个节点插入
{
H=s;
r=H;
}
else//链表的其余节点插入
{
r->next=s;
r=s;//r后移
}
}//for结束
r->next=H;/*生成循环单链表*/
return H;
}

void search(Linklist H,int m0,int z)//用循环链表实现报数问题
{ int count=1;//count为累计报数人数计数器
int num=0;//num为标记出列人数计数器
Linklist pre,p;
p=H;
printf("Output the order:");
while(num{
do{
count++;
pre=p;
p=p->next;
}while(count pre->next=p->next;
printf("%d ",p->n);
m0=p->m;
free(p);
p=pre->next;

num++;
}//while结束
}

void main()
{
int m0,z;
Linklist H;
printf("Input z:");//z为总人数
scanf("%d",&z);
H=create(z);//函数调用
printf("\nInput the start code m0=");
scanf("%d",&m0);
search(H,m0,z);
}

#include "malloc.h"
#include "stdio.h"
#define MAX 100
#define ERROR 0
#define OK 0
typedef int ElemType;
typedef struct LNode
{
int num;
ElemType data;
struct LNode *next;
}LNode;
LNode *head,*this,*new;
int str[MAX];
new_code(int a);
delete_code(int a,int b);
main()
{
int m,n,i;
printf("Enter the first code (m):");
scanf("%d",&m);
printf("\nEnter the people number (n):");
scanf("%d",&n);
getchar();
printf("\n");
new_code(n);
if(head!=NULL)
delete_code(n,m);
else
{
printf("list is empty\n");
exit();
}
for(i=0;iprintf("%-3d",str[i]);
printf("\n");
}
new_code(int a)
{
int i=1;
char numstr[10];
new=(LNode *)malloc(sizeof(LNode));
if(new==NULL)
return ERROR;
if(head==NULL)
head=new;
this=head;
while(--a!=0)
{
this->num=i;
printf("enter the %d code(data):",i);
gets(numstr);
this->data=atoi(numstr);
new=(LNode *)malloc(sizeof(LNode));
this->next=new;
this=new;
i++;
}
this->num=i;
printf("enter the %d code(data):",i);
gets(numstr);
this->data=atoi(numstr);
this->next=head;
return OK;
}
delete_code(int a,int b)
{
int i;
int j=0;
LNode *p;
while((a--)!=1)
{
for(i=1;i<=b;i++)
{
p=this;
this=this->next;
}
b=this->data;
str[j]=this->num;
p->next=this->next;
free(this);
j++;
}
str[j]=this->next->num;
return OK;
}