cpp1.cpp

图论课程设计：在无向完全图中寻找边不重复的汉密尔顿回路

  #include<iostream.h>
  class queue{             //定义一个整型队列类
	int q[51];           //用数组q来存放队列中的各个元素
	int sloc,rloc;       //sloc表示队列尾，rloc表示队列头
   public:
	queue();             //声明构造函数
	void qput(int i);    //往队列中增加元素并排序的函数
	void qout();
  }a;
  queue::queue()
  { 
	sloc=1;
	rloc=0;         //给队列中的两个私有变量赋初值
 }
  void queue::qput(int i)
  {   
	for(int j=1;j<=i;j++){
		q[sloc]=j;
		sloc++;              //按顺序向队列增加元素
		if(sloc==51){        //若sloc为51，表示队列已满，提示增加队列  长度
		cout<<"please enlarge queue\n";
		return;
	}
	}
    a.qout();
	cout<<q[1];              //按初始顺序输出队列中的各元素
	cout<<"\n";
    if(i<=4){}               //i=4时，只有一种排序方式，不操作
	else if(i%2==1){         //检验i为偶数时
		for(int j=1;j<=(i-1)/2;j++){
			 int temp0=q[2];             //保存q[2]副本
			  int temp1=q[i];            //保存q[i]副本
		 for(int k=1;k<=(i-3)/2;k++){
			 q[2*k]=q[2*k+2];}
		 for(int m=(i-3)/2;m>=1;m--){
			 q[2*m+3]=q[2*m+1];}
		 q[3]=temp0;
		 q[i-1]=temp1;
         a.qout();
		 cout<<q[1];
		 cout<<"\n";
		}
	}
	else if(i%2==0){         //检验i为奇数时  
		for(int j=1;j<=i/2-1;j++){
			 int temp0=q[3];             //保存q[3]副本
			 q[3]=q[2];
			 q[2]=q[5];
			 for(int k=1;k<=(i-6)/2;k++){
				 q[2*k+3]=q[2*k+5];}
			 q[i-1]=q[i];
			 if(i<=6){q[6]=temp0;}
			 else{
				 for(int k=i/2;k>=4;k--){
					 q[2*k]=q[2*k-2];}
					 q[6]=temp0;
			 }
             a.qout();                  //输出排序后的次序
			 cout<<q[1];                //与结点1构成回路
			 cout<<"\n";
		}
	}
	}
  void queue::qout()
  { for(int m=1;m<sloc;m++){
	cout<<q[m]<<" ";}
  }
  main()
  {
	cout<<"******************************\n";
	cout<<"**  边不重复的汉密尔顿回路  **\n";
	cout<<"**-------------------------**\n";
	cout<<"** 程序提示：              **\n";
	cout<<"1.使用之前,请将图中结点从1开始连续编号.\n";
	cout<<"2.接点个数上限为50.\n";
	cout<<"3.接点个数上限可在源程序中修改.\n";
	cout<<"**-------------------------**\n";
	cout<<"**输入图中接点个数n(0<n<51)：**\n";   //绘制程序界面
	int n;      
	cin>>n;                          //接受用户输入的结点个数
	cout<<"-------------------------------------\n";
	a.qput(n);                       //调用排序函数并输出结果
	cout<<"-------------------------------------\n";
	cout<<"只有最后一行排序出现相邻结点的重复\n";
	cout<<"所以边不重复的汉密尔顿回路个数为："<<(n-1)/2<<"\n";   //给出符合要求的汉密尔顿回路个数
	return 1;
  }