如:M=5 N=3
则输出结果:3,1,5,2,4
如:M=3 N=6
则输出结果:3,2,1
在此谢过各位!!
小弟最近学数据结构,老师正好出了这个又叫"约瑟夫环"问题,请看小弟用双循环链表写的程序:
#include <malloc.h>
void double_list(int n)
{
struct ring
{
int num;
int password;
struct ring * next;
struct ring * prior;
};
struct ring * p,* q,* r;
int i=0,m;
r=p=q=(struct ring *)malloc(sizeof(struct ring));
p->num=1;
printf("Please input the %d password:\n",i+1);
scanf("%d",&p->password);
while(i<n-1)
{
i++;
p=(struct ring *)malloc(sizeof(struct ring));
q->next=p;
p->prior=q;
q=p;
p->num=i+1;
printf("Please input the %d password:\n",i+1);
scanf("%d",&p->password);
}
p->next=r; //尾结点的后一个位置为头结点
r->prior=p; //头结点的前一个位置为尾结点
p=r; //p指向头结点
printf("The sequence is:\n");
m=p->password; //m!=1;
if(m!=1)
{
while(p->next!=p)
{
for(i=0;i<m;i++)
{
r=p;
p=p->next;
}
printf("%d(%d) ",r->num,r->password);
r->prior->next=r->next;
r->next->prior=r->prior;
free(r);
m=r->password;
}
printf("%d(%d) ",p->num,p->password); //输出最后一个结点
free(p);
}
else
{
while(m==1)
{
printf("%d(%d) ",p->num,p->password);p=p->next;
p->prior=q;
q->next=p;
m=p->password;
}
while(p->next!=p)
{
for(i=0;i<m;i++)
{
r=p;
p=p->next;
}
printf("%d(%d) ",r->num,r->password);
r->prior->next=r->next;
r->next->prior=r->prior;
free(r);
m=r->password;
}
printf("%d(%d) ",p->num,p->password); //输出最后一个结点
free(p);
}
}
main()
{
int n;
printf("Please input the length of the list:\n");
scanf("%d",&n);
double_list(n);
}
//我用循环链表实现的,供大家参考[原创]
#include <iostream.h>
#include <malloc.h>
struct list
{
int data;
struct list *next;
};
int main()
{
int m,n,i;
struct list *h,*p,*s,*pre;
cout << "输入人数M=" ;
cin >> m ;
cout << "输入报数N=" ;
cin >> n ;
h=(list *)malloc(sizeof list); //建头节点
h->data=0;
h->next=NULL;
p=h;
for(i=1;i<=m;i++)
{
s=(list *)malloc(sizeof list);
s->data=i;
s->next=NULL;
p->next=s;
p=s;
}
s->next=h->next; //建循环链表
p=h->next;
pre=s;
while(p!=pre)
{
for(i=1;i<n;i++)
{
p=p->next; pre=pre->next;
}
cout << p->data << " " ;
pre->next=p->next;
p=pre->next;
}
cout << p->data << " " << endl;
return 0;
}