链式结构堆栈类的类模板实现及用堆栈类求解n皇后问题.cpp

链式结构堆栈类的类模板实现及用堆栈类求解N皇后问题

//链式结构堆栈类的类模板实现及用堆栈类求解N皇后问题　编写：089906－36　刘爱贵　　
#include "iostream.h"
#include "math.h"
#define  TRUE     1
#define  FALSE    0
#define  ERROR   -1
typedef int Status;
//用模板实现的链式结构堆栈类
template <class T>
class stack{
	private:
	struct link{
		T data;                 //结点数据域
		link *next;             //下一结点指针
		link(T Data,link* Next){//结构体构造函数
        	data=Data;
	        next=Next;
		}
	}*head;                    //堆栈顶指针
	public:
		stack();               //构造函数(初始化栈)
	   ~stack();               //析构函数(销毁栈)
	    void  push(T Data);    //压栈操作
		T gettop()const;       //取栈顶元素
		T pop();               //出栈操作
		T getvalue(int index); //返回栈底开始第INDEX个栈中值
		void  traverse(int n); //遍历栈 N个数换行
		int   empty();         //判断栈是否为空，1是，0非
		int   sizeofstack();   //返回栈的大小
		void  clear();         //清空栈
};
//N皇后类
class queen{
private:
	stack<int>* qStack;            // 求解中所用数据结构:堆栈
public:  
	queen();                       //构造函数
       ~queen();                       //析构函数
	Status Place(int k);           // 判断当前行K列是否可以可以放置皇后
	Status Queen(int n);           //求出所有解
};
//类模板成员函数的实现
template<class T> stack<T>::stack()//构造函数
{
	head=0;
}
template<class T> stack<T>::~stack()//析构函数
{ 
	link* cursor=head;
	while(head)
	{
		cursor=cursor->next;
		delete head;
		head=cursor;
	}
}
template<class T>void stack<T>::push(T Data)//压栈操作
{
	head=new link(Data,head);
}
template<class T>T stack<T>::gettop()const//取栈顶元素
{
	return head->data;
}
template<class T>T stack<T>::pop()//出栈操作
{
	if(head==0)return 0;
	T result=head->data;
	link* oldhead=head;
	head=head->next;
	delete oldhead;
	return result;
}
template <class T>T stack<T>::getvalue(int index)//返回栈底开始第INDEX个栈中值
{
    link *cursor=head;
	int i=1;
	int stacklen=sizeofstack();
	if(index<=0||index>stacklen)return 0;
    while(i<=(stacklen-index))
	{
		cursor=cursor->next;
		i++;
	}
	return cursor->data;
}
template <class T> void stack<T>::traverse(int n)//遍历栈
{
	link * cursor=head;
	int iEnterSign=1;//换行标识
	while(cursor)
	{
		cout<<cursor->data<<"  "; 
		if(iEnterSign%n==0)cout<<endl;
		cursor=cursor->next;
		iEnterSign++;
	}
    if((iEnterSign-1)%n!=0)cout<<endl;
}
template <class T>int stack<T>::empty()         //判断栈是否为空，1是，0非
{
	return head==0?1:0;
}
template <class T>int stack<T>::sizeofstack()   //返回栈的大小
{
	int size=0;
	link *cursor=head;
	while(cursor)
	{
		cursor=cursor->next;
		size++;
	}
	return size;
}
template<class T> void stack<T>:: clear()         //清空栈
{
	link *cursor=head;
	while(cursor&&cursor->next)
	{
        cursor=cursor->next;
		delete head;
		head=cursor;
	}
}
//N皇后类成员函数的实现
queen::queen()                       //构造函数
{
   qStack=new(stack<int>);
}
queen:: ~queen()                     //析构函数
{
	delete qStack;
}
Status queen::Place(int k)           // 判断当前行K列是否可以可以放置皇后
{
  int i=1,j,e;
  j=qStack->sizeofstack()+1;
  while(i<j)
   {
     e=qStack->getvalue(i);
     if((k==e)||(abs(i-j)==abs(e-k))) return FALSE;
     i++;
   }
  return TRUE;
}
Status queen::Queen(int n)           //回溯法求出N皇后所有解
{
  int k,m=0,e;
  if(n<4)return ERROR;
  k=1;
  while(!qStack->empty()||k<=n)
      {
	while((k<=n)&&(!Place(k)))k++;
	if(k<=n)
	  {
	    qStack->push(k);
	    if(qStack->sizeofstack()==n)
	    {
		  m++;
		  qStack->traverse(n);
		  e=qStack->pop();
		  k=e;
		  k++;
	    }
	    else k=1;
	  }
	else
	 {
	   e=qStack->pop();
	   k=e;
	   k++;
	 }
  }
  cout<<"There are "<<m<<" ways"<<endl;
  return TRUE;
}
void main(void)//程序入口函数
{
	//堆栈操作示例
	cout<<"堆栈操作示例："<<endl;
	stack<int> *sample=new(stack<int>);
	sample->empty()==1?cout<<"Stack is empty!"<<endl:cout<<"Stack is not empty!"<<endl;
    int i;

	for(i=1;i<=10;++i)sample->push(i);
    sample->traverse(10);
	sample->empty()==1?cout<<"Stack is empty!"<<endl:cout<<"Stack is not empty!"<<endl;
    cout<<"Size of the Stack is:"<<sample->sizeofstack()<<endl;
	cout<<"Top of stack is:"<<sample->gettop()<<endl;

	for(i=1;i<=5;++i)sample->pop();
	sample->traverse(10);
	sample->empty()==1?cout<<"Stack is empty!"<<endl:cout<<"Stack is not empty!"<<endl;
    cout<<"Size of the Stack is:"<<sample->sizeofstack()<<endl;
	cout<<"Top of stack is:"<<sample->gettop()<<endl;
	//用堆栈回溯实现的八皇后问题求解
	cout<<"八皇后问题解:"<<endl;
	queen eightqueen;
	eightqueen.Queen(8);
	cout<<"链式结构堆栈类的类模板实现及用堆栈类求解八皇后问题"<<endl;
	cout<<"编写：089906－36　刘爱贵   2002年10月12日完成";
	cin.get();
}//程序结束