joseph.c

刚开始学数据结构时做的一个约瑟夫环,有点复杂,,但总是可以运行,

#include<stdio.h>
#include<malloc.h>
#define LEN sizeof(struct joseph)

struct joseph
{
 int num;
 int password;
 struct joseph *next;
 };

 struct joseph *creat(int n)          /*创建一个无头结点的循环链表*/
 { struct joseph *head;
   struct joseph *p1,*p2;
   int i;

     head=p1=( struct joseph * )malloc(LEN);/*第一个结点*/
     p1=head;
     printf("input the password of 1:");
     scanf("%d",&p1->password);
     p1->num=1;
     p2=p1;
     
   for(i=2;i<=n;i++){                      /*其余结点*/

     p1=( struct joseph * )malloc(LEN);

     printf("input the password of %d:",i);
     scanf("%d",&p1->password);
     p1->num=i;
     p2->next=p1;
     p2=p1;

     }
   p2->next=head;/*尾结点附于头结点.完成循环链表*/
   return(p2);/*最尾结点传给主函数*/


}




void joseph(int n,int m, struct joseph *p,struct joseph *q)
 {
   
   int i,j;

  for(i=1;i<=n;i++)
     {
        if(m==0)/*如果要删除的是第零个结点,不合题意,出错,跳出*/
         {
           printf("error");
           break;
          }

	 for(j=1;j<m;j++){q=q->next;p=p->next;}/*找到要删除的结点*/

	 printf("%d   ",p->num);
	 m=p->password;
	 q->next=p->next;/*删除指点结点*/
	 free(p);p=q->next;


    }
}

void main()
{
   int m,n;
   struct joseph *p,*q;

   printf("input the n:");/*输入要循环数n和第一个m*/
   scanf("%d",&n);
   printf("input the first m:");
   scanf("%d",&m);

   q=creat(n);
   p=q->next;/*取得第一个结点和最后一个结点*/
   
   joseph(n,m,p,q);/*将第一个结点和最后一个结点传给调用的函数*/

   
}