约瑟夫环.cpp

数据结构课程设计

# include<malloc.h>
# define Len sizeof(struct node)
#include<iostream.h>
# define Null 0
struct node   /*  结点的结构定义  */ 
{ int sm;     /*  密码子域        */
  int num; 
  struct node* next;   /*  指针域         */ 
};
/*  生成约瑟夫环  */
void  creat(int length,int demand)
 { struct node* head;
   struct node* p1,* p2;
   int i;
   head=(struct node* )malloc(Len);
   cout <<"请输入第1个人的密码";
   cin>>head->sm;
   head->num=1;
   p1=p2=head;
   for(i=1;i<length;i++)
   { 
         p1=(struct node* )malloc(Len);
		 cout<<"请输入第"<<i+1<<"个人的密码";
         cin>>p1->sm;
         p1->num=i+1;
		 p2->next=p1;
	     p2=p1;
   }
         p2->next=head;
  
     int  j;
	 struct node* p,*q,*r;
     p=head;
	 cout<<"依次被删除人的号码"<<endl;
	 for(i=1;i<length;i++) 
	 { if(demand==1)
		 q=p;   
	  
	 for(j=1;j<demand;j++) 
	 {q=p;	 p=p->next;} 
	     cout<<p->num<<endl;
		 demand=p->sm;
		 q->next=p->next;
         r=p;
		 p=p->next;
		
		 free (r); 
 }
 
         cout<<p->num<<endl;
         free(p);
}
/*  主函数  */
void main()
 { 
	int length,demand;
    cout<<"请输入length和和第一个密码sm"<<endl;
    cin>>length>>demand;
    creat(length,demand);  
 }