joseph problem-c.c

用C语言解决约瑟夫环问题,约瑟夫环问题描述:设编号为1,2,…,n(n>0)个人按顺时针方向围坐一圈

#include <stdio.h>
#include <stdlib.h>


/*Joseph Problem*/
 
#include "malloc.h"

typedef struct singlecyclelink  /*单循环链表*/
{
        int data;   /*数据*/
        int index;  /*索引*/ 
        struct singlecyclelink * next;
}sclink;


sclink *createscl(int n) /*创建一个有n个元素的单循环链表*/
{
       sclink *head=NULL,*p,*q;
       int data,i;
        
        printf("Please input everyone's order:\n");
        
        for(i=1;i<=n;i++)
        {
              printf("The %dth people's order is:",i);
              scanf("%d",&data);
              
              q=(sclink *)malloc(sizeof(sclink));
              q->data=data;
              q->index=i;
              
              if(head==NULL)/*当链表为空时的将头指针指向这第一个元素*/
              {
                   head=q;
                   p=head;
                   p->next=head; /*p指向头指针指的前一个元素，以便插入下一个元素*/
              } 
              else
              {
                   p->next=q;
                   p=p->next;
                   p->next=head;/*将最后一个指针指向头结点*/ 
              } 
        
        }
        
        return head; 
  
} 


/*本函数为测试代码*/ 
void displayscl(sclink *head)/*将链表打印出来*/ 
{
     sclink *p=head;
     
     if(p==NULL) return;
     
     do
     {
          printf("The %dth people's order is:%d\n",p->index,p->data);
          p=p->next; 
     }while(p!=head); 
} 


/*本函数实现将整个链表按游戏规则打印出来*/
void leaveout(sclink *head,int m)
{
     sclink *p=head,*q;
     int i=1; 
      
     printf("The order is:\n"); 
     
     while(p!=p->next)/*循环直到，只剩一个元素时*/ 
     {
          while(i!=m)/*如果还没数到第m个，就继续往下数*/
          { 
               q=p;
               p=p->next;
               i++; 
          }
          
          i=1;
          m=p->data; 
          printf("%d ,",p->index);/*打出这个元素的索引*/
          
          q->next=p->next;
          free(p);/*释放这个节点的空间*/
          p=q->next;/*准备进入下一次循环*/ 
           
     }
     printf("%d !",p->index);/*打印最后一个元素*/
     free(p); 
      
} 



int main(int argc, char *argv[])
{
    sclink *head;
    int num,m;
     
    printf("How many people are there?\npeople number:"); 
    scanf("%d",&num); /*获取总人数*/
    
    printf("Input m's initialize data:\nm=");
    scanf("%d",&m);/*获取初始密码*/ 
    
    head=createscl(num);/*创建单循环链表*/
    leaveout(head,m); /*按规则打出结果*/ 
     
    getch();/*暂停，以便看结果*/	
    return 0;
}