约瑟夫环.cpp

本演示程序演算约瑟夫环问题

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

//*******建立结构*******//

struct ManNode
{ 
 int Number;
 struct ManNode * Next;
 int Password;
};

void main()
{
 int m;
 int NumMan;
 struct ManNode * Head;
 void DeleteNode(int ManNumber,int number,struct ManNode * head);
 struct ManNode * CreateList(int NumOfMan);

 printf("请输入参加的人数:\n");
 scanf("%d",&NumMan);

 Head=CreateList(NumMan);
 printf("请输入刚开始任选的人数m:\n");
 scanf("%d",&m);
 DeleteNode(NumMan,m,Head);
 getchar();
 free(Head);
}

struct ManNode *CreateList (int NumOfMan)
{
 struct ManNode * head,*ManNodePtr1,*ManNodePtr2;
 int Num=1;
 head=NULL;
 ManNodePtr2=(struct ManNode *)malloc(sizeof(struct ManNode));

 //*******分配存储单元*******//
 printf("请输入用户所持有的密码:");
 scanf("%d",&ManNodePtr2->Password);
 ManNodePtr2->Number=Num;
 head=ManNodePtr2;

 while(Num!=NumOfMan)
 {
 Num++;
 ManNodePtr1=(struct ManNode *)malloc(sizeof(struct ManNode));
 printf("请输入用户所持有的密码:");
 scanf("%d",&ManNodePtr1->Password);
 ManNodePtr1->Number =Num;
 ManNodePtr2->Next =ManNodePtr1;
 ManNodePtr2=ManNodePtr1;
 }

 ManNodePtr2->Next =head;
 printf("输入结束!\n");
 return head;
}

void DeleteNode (int ManNumber,int number,struct ManNode * head)
{
 int num=1;
 struct ManNode *ManNodePtr1;
 struct ManNode *ManNodePtr2;
 ManNodePtr1=ManNodePtr2=head;

 while(ManNumber>0)
 {
  while(num!=number)
  {
   ManNodePtr2=ManNodePtr1;
   ManNodePtr1=ManNodePtr1->Next ;
   number--;
  }

  number=ManNodePtr1->Password;
  printf("出列人的编号:%d\n",ManNodePtr1->Number) ;
  ManNodePtr2->Next =ManNodePtr1->Next ;
  ManNodePtr1=ManNodePtr1->Next ;
  ManNumber--;
 }
 printf("\n运行结束!!!\n");
}