ldf19870326.txt

一个没有错误的约瑟夫环问题的源代码

约瑟夫问题（Joseph）的一种描述方法是：编号为1，2，.......，n的n个人按顺时针方向围坐一个圈，每个人持人一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m的人出列。将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。
利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。


#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include<conio.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);
 getch();
 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");
}