joseph.cpp

数据结构课程设计

#include  <stdio.h>
#include <stdlib.h>
typedef struct node             /*  结点的结构定义  */
   {  int  num;              /* 编号  */
      int  sm;               /* 密码  */
      struct node *link;        /*指针域 */
   }JOS;
/*  生成约瑟夫环  */
JOS  *creat(int n)
{  int  i=0,j, mi;
   JOS  *neww, *pre, *h;
   h=(JOS *)malloc(sizeof(JOS));
   h->link=h;
   pre=h;

 for (j=0;j<n;j++)
   {
     printf("输入第%d个人的密码:",j+1);  scanf("%d",&mi);
	  neww=(JOS *)malloc(sizeof(JOS));
      i++;
	  neww->num=i;
	  neww->sm=mi;              /*  结点送值   */
      neww->link=h;
      pre->link=neww;
      pre=neww;                                  /*  形成循环链表   */
        }
   pre->link=h->link; free(h);                      /*  删除头结点h */
   h=pre->link;  return(h);     /* 头指针指向第一个数据元素结点 */
}

void outs(JOS  *h, int m)
{
   int i;   JOS *q=h,*p;
   while (q->link!=q)
   {
	 for(i=1;i<m;i++){ p=q; q=q->link;} /*  报数到第m个人 */
     m=q->sm;        /*修改值m为第m个人的密码*/
	 printf("%6d",q->num);        /*  输出第m个人的编号  */
     p->link=q->link;  free(q);             /*  第m个人出列  */
     q=p->link;
   }
  printf("%6d\n",q->num);
  free(q);
} /* outs  */


/*  主函数  */
void main()
{
    int  m,n;  JOS  *h;
     printf("enter the number of people,n="); scanf("%d",&n);
   h=creat(n);
   printf("enter the begin secret code, m="); scanf("%d",&m);
   printf("the out order is:\n ");
      outs(h, m);
}  /* main  */