结构推理 用单链表解决约瑟夫问题。约瑟夫问题为: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);
   }
【答案解析】