shaozhen.c

我自己写的一个解决约瑟夫环的小程序

#include <malloc.h>
#include <stdlib.h>
#include <bios.h>
int Getkey();
typedef struct lnode
       {int number;
        int mima;
        struct lnode *next;
        };
struct lnode *CreatList(int n)
  {int i;
   struct lnode *pt,*head;
   if((pt=(struct lnode *)malloc(sizeof(struct lnode)))==NULL)
   {
    printf("分配空间出错！！！\n");
    return pt;
   }
    head=pt;
    pt->next=head;
    for(i=1;i<n;i++)
   {
      pt->next=(struct lnode *)malloc(sizeof(struct lnode));
      if((pt->next)==NULL)
      {  printf("分配空间出错！！！\n");
         pt->next=head;
         return head;
      }
       pt=pt->next;
       pt->next=head;
    }
    return head;
 }
   main()
  {int i,j,n,m,key;
   struct lnode *head,*behind,*before;
   printf("\n\n\t\t\t      约瑟夫环问题");
   printf("\n\n\n    有设编号为1,2,3......n的n个人.按顺时针方向围坐一圈,每个人有一个密码m.以整数\n");
   printf("m做为报数上限,从第i个人开始顺时针方向顺序报数,报到m停止报数,报m的人出列,将他的密");
   printf("码作为新的m值，从他的下一个人开始重新从1报数.如此下去,直到所有人全部出列为止.\n");
   printf("\n\n让我们来模拟一下约瑟夫环出列的情况:");
sz:  printf("\n\n\t请输入总人数         n:");
   scanf("%d",&n);
   head=CreatList(n);
   for(j=1;j<=n;j++)
   {
    head->number=j;
     printf("\t请输入第%d个人的密码  m:",j);
    scanf("%d",&m);
    head->mima=m;
    before=head;
    head=head->next;
   }
   printf("\t请输入从第几个人开始 i:");
   scanf("%d",&i);
   printf("\t请输入初始的密码     m:");
   scanf("%d",&m);
   printf("\n开始模拟约瑟夫环出列:\n");
    behind=head->next;
    for(j=1;j<i;j++)
    {
     before=head;
     head=behind;
     behind=head->next;
    }

    j=1;
    while(head->next!=head)
    {
       if(j<m)
        {
          head=head->next;
          before=before->next;
          behind=head->next;
          j++;
        }

     else{
          printf("号码:%d\t",head->number);
          m=head->mima;
          j=1;
          free(head);
          head=behind;
          before->next=head;
          behind=head->next;
         }
        }
    printf("号码:%d\t",head->number);
    free(head);
    printf("\n\n\n\n\t\t\t\t\t 版权所有：计算机2002级1班:邵振\n");
    printf("重新运行：输入Enter\t");
    printf("退出：输入ESC\n");
    key=Getkey();
    if(key==13)
    {clrscr(0);
     printf("\n\n让我们重新来模拟一下约瑟夫环出列的情况:");
     goto sz;
    }
    if(key==27) exit(0);

}
  int Getkey()
 {
  int ch,low,high;
  ch=bioskey(0);
  low=ch&0x00ff;
  high=(ch&0xff00)>>8;
  return (low==0?high+256:low);
 }