joseph.c

数据结构实验与学习指导

/* joseph.c */
#include <stdlib.h>
#include <alloc.h>
typedef struct node
{
    int number;                         /* 人的序号 */
    struct node *next;                 /* 指向下一个结点的指针 */
}Jsnode,*Jlink;
struct Jsnode *head,*ptr,*p,*s;
struct Jsnode* CreatList(int num)     /* 建立循环链表 */
{   int i;
   head=(Jsnode*)malloc(sizeof(Jsnode));
   head->number=1;
   head->next=head;   p=head;
   for(i=2;i<=num;++i)               /* 输入n个信息 */
    {
     s=(Jsnode *)malloc(sizeof(Jsnode));
     s->number=i;
     s->next=p->next;
     p->next=s;
     p=s;
   }
  p=head;
  printf("成员的编号为:\n");
  while(p->next!=head)
  { printf("  %d",p->number); p=p->next;}
  printf("  %d",p->number);
  return head;
}
void jsph( Jsnode *head,int m)
  { int i;
     p=head;
    i=1; 
    while(p->next!=p)             /* 当剩下最后一个人时，退出循环 */
    {
        if(i==m-1)
        {
            ptr=p->next;             /* ptr记录数到m的那个人的位置 */
            printf("  %d",ptr->number);
            p->next=ptr->next;     /* 让ptr从链表中脱节，将前后两个结点连接起来 */
            free(ptr);             /* 释放ptr指向的内存 */
            i=0;                 /* 将i重新置为1，从1再开始数 */
        }
        else
        {
            p=p->next;
            i++;
        }
    }/* while */
    printf("  %d\n",p->number);
    printf("编号为%d的成员获胜!\n",p->number);
    free(p);                     /* 让最后一个人也出列 */
    }/*jsph*/
main()
{
    int n,m;                     /* 人数为n */
    printf("请输入成员人数:\n");
    scanf("%d",&n);
    if (n<=0)
    { printf("输入的成员人数无效！\n");
      /*输入错误*/
      return ;}
    head=CreatList(n);
    printf("\n输入报数的最大值:\n");
    scanf("%d",&m);
    while (m<=1)
    { printf("输入的报数最大值无效！\n");                 /*输入错误*/
      printf("请重新输入:\n");    /*重新输入*/
    scanf("%d",&m); }
    printf("约瑟夫序列是:\n");
    jsph(head,m);
}