论坛 › 数据结构与算法 › 用栈来实现八王后问题

18819457941 发表于 2014-10-19 23:44:30

用栈来实现八王后问题

#include <iostream.h>
#include<math.h>

const int MaxSize = 100;
int count=0;                //已经摆放的王后个数
int sum=0;                //总的摆放个数


typedef int ElemType;

typedef struct linknode
{
        ElemType data;
        int top;
}LiStack;

void InitStack(LiStack *&s)                //初始化链栈
{
        s=new LiStack;
        s->top = -1;
}

void DestroyStack(LiStack *&s)                //销毁栈
{
       
        delete s;
}

bool StackEmpty(LiStack *s)                //判断栈是否为空
{
        return(s->top == -1);
}

bool Push(LiStack *&s,ElemType e)                //进栈
{
        if(s->top == MaxSize-1)
                return false;
        s->top++;
        s->data=e;
        return true;
}

bool Pop(LiStack *&s,ElemType &e)        //出栈
{
        if(s->top==-1)                        //栈为空
        {
                return false;
        }
        e = s->data;
        s->top--;
        return true;
}


int notDanger(LiStack *s)                //判断位置是否危险
{
        if(s->top==0)
        {
                return 1;
        }
        else
        {
        for(int i=s->top-1;i>=0;i--)
        {
                if(s->data == s->data)                        //位置在同一列
                {
                        return 0;
                }
                if(s->data==s->data-(s->top-i))                //上一个王后的位置在左上边
                {
                        return 0;
                }
                if(s->data==s->data+(s->top-i))                //上一个王后的位置在右上边
                {
                        return 0;
                }
        }
        return 1;
        }
}

void Queen(LiStack *&s,int k,int num)                //k代表第几个王后摆放，num表示总的王后数
{
        ElemType e;
        if(k>=num)
        {
                sum=sum+1;
        //        show();                                                                //输出摆放方式
        }
        else
        {
                for(int i=0;i<num;i++)                                                                //穷尽行数
                {
                        Push(s,i);
                        if(notDanger(s))                                                                //判断位置是否有危险
                        {
                                Queen(s,k+1,num);
                        }
                        else
                        {
                                Pop(s,e);
                        }
                }
        }
}

void main()
{
        int num=0;
        cout<<"请输入王后的个数:";
        cin>>num;
        LiStack *s;
        InitStack(s);
        Queen(s,1,num);
        cout<<sum;
}


理论上应该输出92种情况的，但是却一直是0，求大神帮助

大个的糖果 发表于 2014-10-30 19:33:25

查看完整版本: 用栈来实现八王后问题