mylist.h

约瑟夫环 约瑟夫环约瑟夫环约瑟夫环约瑟夫环约瑟夫环

#include<stdio.h>
#include<malloc.h>
#include<Conio.h>

static int node=0;/*用于记录链表中的节点数目*/
static int initpwd=0;/*用于记录每次出队的人的密码*/

struct people
{
  int num;/*链表中初始位置*/
  int pwd;/*节点中的密码*/
  struct people  * next;/*指向下一个节点的指针*/
};


/*创建链表并插入节点*/
struct people * creatList(struct people *head)
{
   int pwd;
   char c='q';
   struct people * p=NULL;
   struct people * temp=NULL; /*记录插入位置前一个节点的指针*/
   while (c!='\n')
   {
    
    p=(struct people *)malloc(sizeof(struct people));
    
    scanf("%d",&pwd);  /*用户为当前节点输入密码*/
    if(pwd<=0)
    {
      printf("The PWD must be larger than 0,The Program will exit.");
      getch();
      return -1;
    }
    p->pwd=pwd;
    p->num=node+1;  /*将当前静态变量node的值作为当前节点的位置*/
    if(node==0)     /*插入第一个节点*/
    {
     head=p;
     p->next=p;  /*新形成仅有一个节点的单链表环*/
     temp=p;
     node++;
    }
    else
    {
     p->next=head;
     temp->next=p;
     temp=p;
     node++;
    }
    c=getchar();
   }
  return head;
}

void showList(struct people *head)
{
 struct people *q;
 int recnode=node;/*记录节点数数目*/
 q=head;
 do
  {
    printf("%d||%d\t",q->num,q->pwd);
    q=q->next;
    node--;
  }while(node);
  printf("\n=====================Operation================================\n");
 node=recnode;
}


/*出队操作*/
struct people *delQuene(struct people * now)
{
  struct people *temp;
  temp=now->next;
  initpwd=temp->pwd;/*将当前删除的节点的密码保存*/
  printf("[delete:%d]\n",temp->num);
  now->next=temp->next;
  now=now->next;
  free(temp);
  return  now;
}

/*定位是实现约瑟夫环的核心*/

struct people *locate(struct people *now)
{
  struct people *prior;
  int i=1;
  int fnode=node;/*用于控制寻找指定位置的节点前驱*/
  prior=now;
  initpwd=initpwd%node;
  printf("[now->%d]\t",prior->num);
  printf("[now_pwd:%d]\t",initpwd);
  /*求余结果为零时直接将指针移向此时倒数第二个节点,以便删除倒数第一个节点*/
  if(initpwd==0)
  {
    fnode=node;
    while(i<fnode-1)
    {
      prior=prior->next;
      i++;
    }
    return prior;
  }
  /*删除当前节点，将指针定位到倒数第一个节点*/
  if(initpwd==1)
  {
    fnode=node;
    while(i<fnode)
    {
       prior=prior->next;
       i++;
    }
    return prior;
  }
  /*对于不是特殊点的定位定位到该节点前一个*/
  while(i<initpwd-1)
  {
    prior=prior->next;
    i++;
  }
  return prior;
}
void startToUse()
{
  printf("\n\n\t*************************************************\n");
  printf("\t*\t\t\t\t\t\t*\n\t*\t\t\t\t\t\t*");
  printf("\n\t*\tPlease Input Every Node's PassWords\t*\n");
  printf("\t*\t\t\t\t\t\t*\n\t*\t\t\t\t\t\t*");
  printf("\n\t*\tPress [Enter] to Finish Inputing PWD\t*\n");
  printf("\t*\t\t\t\t\t\t*\n\t*\t\t\t\t\t\t*");
  printf("\n\t*************************************************\n");
}

void Joysef()
{
  struct people * head=NULL;
  struct people * now=NULL;
  startToUse();
  getch();
  system("cls");
  head=creatList(head);
  showList(head);
  printf("Please input the initPWD :");
  scanf("%d",&initpwd);
  /*以下是出队的相关操作*/
  if(initpwd<=0)
  {
    printf("The PWD must be larger than 0,The Program will exit.");
    getch();
    return -1;
  }
  now=head;
  while(node>=0&&now)
  {
     now=locate(now);
     now=delQuene(now);
     node--;
     getch();
  }
}