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

//链式结构堆栈类的类模板实现及用堆栈类求解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(); }//程序结束