joseph.txt

循环链表实现约瑟夫环

题目：约瑟夫（Joseph）问题的一种描述是：编号为1，2，……，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个开始重新从1报数，如此下去，直至年有人全部出列为止。试设计一个程序求出出列顺序。

源代码：

#define ERROR 0
#define ElemType peo


typedef peo{
int order;//人的编号
int password;//人的密码
peo *next;
}

ElemType *CreatClist(int n) {//创建一个大小为n的空循环链表，返回链表头指针
     int i; 
     ElemType *p,*q,*head;
     for(i=1;i<=n;i++){
	q=p;
	p=(ElemType *)malloc(sizeof(ElemType));//开辟空间
        if(i==1)head=p;                               
	   else q->next=p;
     }
     p->next=head;//实现循环链
     return (head);//返回循环链表的头指针
}


ElemType*  ClistDel(ElemType *p,int m){//删除从当前结点开始往后数第m个元素
      ElemType *q ;
      int i;
      for(i=1;i<m;i++){//查找要删除的结点，并使p指向要删除的结点，q指向要删除的结点的前面一个结点
         q=p;
         p=p->next;
      }
      q->next=p->next;//删除该结点
      return(p);返回该结点的地址
}




void main(){
   int m,i,n;
   ElemType *head,*p;
   p=NULL;
   
   printf("Please input the total num of the people:");//输入一共有多少人参加报数
   scanf("%d",&n);
   if(n<=0){//判断输入的人数是否有错
      printf("参加人数 error!!!");
      exit（ERROR）;
   }
  
   printf("please input m:\n");//输入一开始报数的上限m
   scanf("%d",&m);
   if(m<=0){
      printf("初始报数上限error!!!");
      exit(ERROR);
   }

   head=CreatClist(n);
   p=head;    
   for(i=1;i<=n;i++){
      p->order=i;
      printf("please enter the %dst password:",i);
      scanf("%d",&p->password);//赋密码
      if(p->password<=0){//判断密码是否输入错误
         printf("密码 error!!!");
         exit(ERROR);
      }
      p=p->next;
   }   
   printf("The output order is:");
   p=head;
   while(p->next!=p){
      p=ClistDel(p,m);
      m=p->password;//修改m，为下一次出列做准备
      printf("%d ",p->order);//输出出列人的编号    
      p=p->next;//结点p后移
   }
}