1.txt

约瑟夫（Joeph）问题,利用单向循环链表存储结构模拟此过程.

#/* Joseph cycle*/
#include <stdio.h>
#include <conio.h>
#include <alloc.h>
typedef int ElemType;
typedef struct LNode
{
ElemType data;
struct LNode *next;
} LNode,*POINTER,*LinkList;
void init_linklist(LinkList *l);
void release_linklist(LinkList *l);
void clear_linklist(LinkList l);
void crt_linklist(LinkList *l);
void disp_linklist(LinkList l);
void game(LinkList l);
void exitgame(void);
void init_linklist(LinkList *l)/*对循环单链表进行初始化*/
{
(*l)=(POINTER)malloc(sizeof(struct LNode));
(*l)->data=-1;
(*l)->next=(*l);
}
void clear_linklist(LinkList l)/*对循环单链表清空*/
{
POINTER p,useless;
p=l->next;
l->next=l;
while(p!=l)
{
useless=p;
p=p->next;
free(useless);
}
}
void crt_linklist(LinkList *l)/*输入数据创建约瑟夫环表*/
{
int num;
POINTER p;
clear_linklist(*l);
printf("\n\nInput some int numbers (ending with -1) :\n");
scanf("%d",&num);
while(num!=-1)
{
p=(POINTER)malloc(sizeof(struct LNode));
p->data=num;
p->next=(*l)->next;
(*l)->next=p;
scanf("%d",&num);
}
}
void disp_linklist(LinkList l)/*显示表中元素内容*/
{ int i=1,row=1;
POINTER p=l->next;
printf("\n\n");
while(p!=l)
{
if(row==7)
{
row=1;
printf("\n");
}
printf("%5d:%-5d|",i,p->data);
i++;
row++;
p=p->next;
}
}
void game(LinkList l)/*元素依次根据密码值出圈*/
{
int m,k=0;
POINTER p=l,pre,u;
printf("\n\nCount Number m==? ");
scanf("%d",&m);
printf("\n\n\n\n%40s\n\n","GAME START");
while(p->next!=p)
{
pre=p;
p=p->next;
if(p==l) { pre=p; p=p->next;}
++k;
if(k==m) { printf(" %d",p->data);
pre->next=p->next;
u=p;
free(u);
p=pre;
k=0;
}
}
printf("\n\n%40s","GAME OVER");
}
void exitgame()
{
printf("\n\n%40s","GOOD_BYE_GOOD !!");
}
void release_linklist(LinkList *l)/*销毁循环单链表（约瑟夫环）*/
{
clear_linklist(*l);
free(*l);
}
void main()/*主控函数*/
{
int select;
LinkList list;
init_linklist(&list);
do
{
printf("%s%15s%15s%15s%15s",
"\n\n\n\n\n\n",
"1:Create",
"2:Display",
"3:Game",
"4:Exit");
printf("\n\n%33c",' ');
select=getche();
switch(select)
{
case '1': crt_linklist(&list);
disp_linklist(list);
break;
case '2': disp_linklist(list);
break;
case '3': game(list);
break;
case '4': exitgame();
break;
default: printf("\nWrong select ! Try again. ");
}/*switch*/
}while(select!='4');
release_linklist(&list);
getch();
}

【解答】算法如下：

 

typedef struct Node

{

int password;

int num;

struct Node *next;

}  Node,*Linklist;

 

void Josephus()

{

  Linklist L;

  Node *p,*r,*q;

  int m,n,C,j;

  L=(Node*)malloc(sizeof(Node));  /*初始化单向循环链表*/

  if(L==NULL) { printf("\n链表申请不到空间!");return;}

  L->next=NULL;

  r=L;      

  printf("请输入数据n的值(n>0):");

  scanf("%d",&n);

  for(j=1;j<=n;j++)                              /*建立链表*/

   {

         p=(Node*)malloc(sizeof(Node));

      if(p!=NULL)

         {

                printf("请输入第%d个人的密码:",j);

          scanf("%d",&C);

          p->password=C;

          p->num=j;

          r->next=p;

         r=p;

     }

   }

  r->next=L->next;

printf("请输入第一个报数上限值m(m>0):");

  scanf("%d",&m);

  printf("*****************************************\n");

  printf("出列的顺序为:\n");

  q=L;

  p=L->next;

  while(n!=1)                        /*计算出列的顺序*/

  {

          j=1;

       while(j<m)                    /*计算当前出列的人选p*/

       {

                 q=p;               /*q为当前结点p的前驱结点*/

              p=p->next;

              j++;

       }

       printf("%d->",p->num);

       m=p->password;                 /*获得新密码*/

       n--;                 

       q->next=p->next;    /*p出列*/

       r=p;

       p=p->next;

       free(r);

    }

   printf("%d\n",p->num);

}