结构推理
用单链表解决约瑟夫问题。约瑟夫问题为:n个人围成一圈,从某个人开始报数1,2,…,m,数到m的人出圈,然后从出圈的下一个人(m+1)开始重复此过程,直到全部人出圈,于是得到一个新的序列,如当n=8,m=4时,若从第一个位置数起,则所得到的新的序列为4,8,5,2,1,3,7,6。
算法实现的思路为:n个人用1,2,…,n进行编号,使用不带头结点的单链表来存储,报数从1号开始,若某个人出圈,则将其打印输出,并将该结点删除,再对剩余的n-1个人重复同样的过程,直到链表中只剩下一个结点,将其输出即可。算法的具体实现如下:
【正确答案】#include"stdio.h"
#define NULL 0
typedef struct node
{ int data;
struct node *next;
}LINKLIST2;
LINKLIST2*rcreate1() /*建立不带头结点的单链表*/
{LINKLIST2*head,*last,*p;
int ch;
scanf("/%d",&ch);
p=(LINKLIST2*)malloc(sizeof(LINKLIST2));
p->data=ch;
head=p;
last=p;
p->next=NULL;
scanf("/%d",&ch);
while(ch!=-99)
{
p=(LINKLIST2*)malloc(sizeof(LINKLIST2));
p->data=ch;
last->next=p;
last=p;
p->next=NULL;
scanf("/%d",&ch);
}
return(head);
}
void josepho(LINKLIST2*head,int n,int m)
{LINKLIST2*p,*q;
int i,j;
p=head;
i=1; /*记数标志,开始报数*/
for(j=i;j<n;j++)
{ while(i!=m) /*查找出圈的号码*/
{ if(p->next!=NULL)
{ q=p; /*记录p的前一位置,为后面的删除操作做准备*/
p=p->next;
i=i+i;
}
else
{p=head;
i=i+i;
}
}
printf("/%4d,",p->data);
/*删除出圈结点*/
if(p=head) /*出圈结点是第一个结点时*/
{head=p->next;
p=p->next;
}
else if(p->next=NULL) /*出圈结点是最后一个结点时*/
{ q->next=NULL;
p=head;
}
else
{ q->next=p->next;
p=p->next;
}
i=1; /*记数标志重新赋值为1,重新开始报数*/
}
printf("/%4d",p->data);
}
main()
{LINKLIST2*head;
head=rcrearel();
josepho(head,8,4);
}
【答案解析】