jose.cpp

FZU 大二 的数据结构与算法 老师出的题目的优秀作业 第2到第5章

#include"iostream.h"
#include"fstream.h"
#include"string"
class LIST//链表所需要的参数
{
public:
   int data;
   LIST * next;
};

class Josephus
{
public:
	Josephus(int n,int m);//此构造函数定义Josephus排序
    Josephus(int n);//此构造函数定义链
	~Josephus();
    int J(int n,int m);
    void list(int);
 private:
    int n,m;//n表示数的个数，m表示第M个人出列
};
Josephus::Josephus(int n,int m)
{}
Josephus::Josephus(int n)
{}
Josephus::~Josephus()
{}
LIST *h;//定义共用链表的首地址
void Josephus::list(int n)//创建链表
{  
	int y;
  LIST *p1,*p2;
    p1=new LIST;
    p1->data=1;
    h=p1;//运用共用首地址
if((y=2)<=n)
{  for(y=2;y<=n;y++)
   {
     p2=p1;
     p1=new LIST;
     p1->data=y;
     p2->next=p1;
}
{    p1->next=h;}
}
}   


int Josephus::J(int n,int m)//定义Josephus排序的算法
{ int x,y=0;
  LIST *p1,*p2;
  Josephus j2(n);
  j2.list(n);  
  LIST *p;
  p1=h;//运用共用首地址
	for(x=2;y!=n-1;x++)
	{ p=p1->next;
	  p2=p->next;
	  if(x%m==0)
	   {delete p;
        p1->next=p2;
        y=y+1; 
	   }
	   else
	   {
		p1=p;
	   }
	   if(y==(n-1))
	   {return p2->data; 
	   }

	}
    return p2->data; 
}
void main()
{
  ifstream in("input.txt");
     int n,m,k,i,j=0;
     char a[30],b[30],c[30];
     in>>n>>m;
     Josephus J1(n,m);
   if(n==0||m==0&&n>1)//当没有数输入的时候
   {   strcpy(a,"wrong");
       strcpy(b,a);
       j=0;
       goto loop;
   }
	 if(n==1)//当只有1个数出现的时候
	 {
	    in>>a;
	    j=0;
	    strcpy(b,a);
	    goto loop;
	 }
    for(k=1;k<=n;k++)
	{ if(k==J1.J(n,m))
		{in>>a;
         break;}
	  else
		 {in>>a;
	     a[0]=0;}
	}
      in.close();//关闭读取的文件
	  in.open("input.txt");//重新打开读取的文件
    for(k=1;k<=n+3;k++)
	{ if(k==n+3)
		{in>>b;
         break;}
	  else
		 {in>>b;
	     b[0]=0;}
	}
	 in.close();
	 in.open("input.txt");
   for(k=1;k<=n+2;k++)
   {   in>>c;
	   if(strcmp(c,b)==0)//对B和C进行比较的判断
	   {   i=k-2;
	       break;}
	   else
	       c[0]=0;
   }
    in.close();
	in.open("input.txt");
    in>>n;
	m=j;
	for(j=1;j>0;j++)//算出m循环
	{if(J1.J(n,j)==i)
	  break;
	}
loop:
 ofstream out("output.txt");
     out<<a<<endl;
     out<<j<<endl;
     out<<b<<endl;
}