八皇后非递归加栈.doc

#includeiostream #include stdio.h #define SCALE 8// 问题的阶数，8为八皇后问题 char chessboard[SCALE][SCALE]; // 全局变量，棋盘，放置棋子为 ，否则为* int count=0; // 全局变量，记录可能结果个数 typedef struct { int data[SCALE]; int top; }SeqStack, *PSeqStack; PSeqStack InitialPseqStcak(void){ PSeqStack S; S=(PSeqStack)malloc(sizeof(SeqStack)); if(S) S-top=-1; return S; } int Empty_SeqStack(PSeqStack S) { //判断栈是否为空，入口参数：顺序栈，返回值：1表示为空，0表示非空 if (S-top== -1) return 1; else return 0; } int Push_SeqStack (PSeqStack S, int x) { //入口参数：顺序栈，返回值：1表示入栈成功，0表示失败。 if (S-top==SCALE) //栈满不能入栈 return 0; else { S-top++; S-data[S-top]=x; return 1; } } int Pop_SeqStack(PSeqStack S) { //删除栈顶元素并保存在*x， 入口参数：顺序栈，返回值：1表示出栈成功，0表示失败。 if (Empty_SeqStack ( S ) ) //栈空不能出栈 return 0; else { S-top--; return 1; } } int GetTop_SeqStack(PSeqStack S) { //取出栈顶元素， 入口参数：顺序栈，被取出的元素指针，这里用指针带出栈顶值; 返回值：1表示成功，0表示失败。 int x; if ( Empty_SeqStack ( S ) ) //栈空 return 0; else { x= S-data[S-top]; //栈顶元素存入*x中 return x; } } void Trial(PSeqStack S); int RemoveChess(int i,int j); void PrintBoard();// 输出当前棋盘的布局 int IsValidLayout();// 检验当前棋盘是否为合法布局 void Trial(PSeqStack S){ int i=0; int j=0; while(i!=-1){ if(i==SCALE) { count++; printf_s(\n number of valid layout is %d.\n,count); PrintBoard(); i--; j=GetTop_SeqStack(S)-i; RemoveChess(i,j); Pop_SeqStack(S); i--; j=GetTop_SeqStack(S)-i; RemoveChess(i,j); Pop_SeqStack(S); if(j==SCALE-1){ i--; j=GetTop_SeqStack(S)-i; RemoveChess(i,j); Pop_SeqStack(S); j++; } else j++; } else { chessboard[i][j]= ; if(1==IsValidLayout()) { Push_SeqSta