八皇后问题

   求八皇后问题所有的解。
　　实例解析：
　　这是一个非常古老的问题：如何在一个8*8的棋盘上无冲突地放置8个皇后棋子，称为八皇后问题。
　　 在国际象棋中，皇后可以沿着任何直线和任何45°斜线移动吃掉别的棋子，因此，任何一个皇后所在的横线上、竖线上和两条对角线上都不能有其他皇后存在。一个完整的、无冲突的八皇后分布称为八皇后问题的一个解。本例求解八皇后的所有解。
　　很显然，棋盘的每一行都必须有且只能有一个皇后，因此我们从第一行开始，先放下一个皇后（有8个位置可以放置），然后用递归的方式调用函数本身，去放置后面的棋子，直到第八行放完，则表示找到了一个解。
　　对于每一行，可以放置皇后的位置有8个，可用循环的方式来逐个试探，若无冲突，则放置棋子，继续下一层递归调用......，若冲突，则换本行另一个位置。
　　下面为程序代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <math.h>
#include <stdio.h>
#define  MAX  8         //棋盘大小MAX*MAX
int  board[MAX];  
int  count = 0;
void  show_result()           //输出结果
{
     int  i;
     for (i = 0; i < MAX; i++)
         printf ( "(%d,%d)," , i+1, board[i]+1);   //生活中从1开始计数
     printf ( "\n" );
}
　　
int  check_cross( int  n)      //检查是否与前面已经存在的皇后冲突
{
     int  i;
     for (i = 0; i < n; i++)
         if (board[i]==board[n]||(n-i)== abs (board[i]-board[n]))
　　　　　    return  1;               //若冲突返回1
     return  0;
}
void  put_chess( int  n)           // 在第n行放棋子
{
     int  i;
     for (i = 0; i < MAX; i++)
     {    //依次对第0~7列试探有无冲突
         board[n] = i;                 // board[n]存储列号 (行号是n)
         if (!check_cross(n))
         {        //不冲突
             if (n == MAX-1)
             {          //若已经到第八行，则找到一个解
                 count++;
                 printf (“%3d: ”, count);   //输出一个解的序号
                 show_result();             //输出結果
                 if (count%24 == 0)
                 {        //每24行一屏暂停
                     getch();
                     clrscr();
                 }
             }
         else
             put_chess(n+1);    //若未到第八行，则递归调用，进入下一行
         }
     }
}
　　
int  main()
{
     clrscr();
     puts ( "The possible placements are:" );
     put_chess(0);
     puts ( "\n Press any key to quit..." );
     getch();
     return  0;
}
　　上面使用的是递归算法，还可以使用一种非递归回溯的算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#define TRUE  1
#define FALSE 0
int  nQueens_nonrecursive( int  *a,  int  n)
{
     int  top, i, j, conflict;
     if (n <= 0)
         return  FALSE;
     top = -1;
     i = 0;
     do
     {
         conflict = FALSE;
         /*判断会不会与前面已经放置的发生冲突*/
         for (j = 0; j < top+1; j++)
             if (i==a[j]||top+1-j==i-a[j]||top+1-j==a[j]-i)
                 conflict = TRUE;
         if (conflict == FALSE)
         {   //如果不冲突
             a[++top] = i;           //把当前皇后放到第i列
             if (top == n-1)
                 　　　　　　　 return  TRUE;         //问题已成功解决
             i = 0;                   //从下一行的第0列开始，继续试探
         }
         else
         {                       //如果冲突
             while (i == n-1 && top >= 0)
                 　　　　　　　i = a[top--];
             i++;
         }
     }
     while (i < n);
     return  FALSE;
}
   这里只列出了部分函数

迷宫问题
   从迷宫中找出从入口到出口的所有通道。
　　实例解析：
　　迷宫可用图17-6所示的方块来表示，每个方块或为通道(以空白方块表示)或为墙(以带阴影的方块表示)。要求找到一条从入口到出口的简单路径，即在求得的路径上不能重复出现同一通道块。
　　求解迷宫问题的简单方法是：从入口出发，沿某一方向进行搜索，若能走通，则继续向前走；否则沿原路返回，换一方向再进行搜索，直到所有可能的通路都搜索到为止。
　　在计算机中可用图17-7所示的二维数组maze[m][n]来表示，数组中元素为0表示通道，为1表示墙。对其中的任一点maze[i][j]，可能的运动方向有4个。回溯法求迷宫问题解的过程要用一个栈来保存搜索的路径。
　　核心代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <stdio.h>
#include <stdlib.h>
#define M 8         // maze数组的行数
#define N 11        // maze数组的列数
typedef  struct
{
     int  x,y,d;
}DataType;
struct   SeqStack
{   //顺序栈类型定义
     int  MAXNUM;
     int   t;          // t<MAXNUM，指示栈顶位置，而不是元素个数
     DataType  *s;
};
         　　
typedef   struct  SeqStack  *PSeqStack;  //顺序栈类型的指针类型
PSeqStack CreateEmptyStack_seq( int   n);
void   push_seq( PSeqStack pastack, DataType x );
void   pop_seq( PSeqStack pastack );
int  isEmptyStack_seq(PSeqStack pastack);
DataType  top_seq( PSeqStack pastack );
/*下面函数求从入口maze[x1][y1]到出口maze[x2][y2]的一条路径，其中 1<=x1, x2<=M-2 , 1<=y1, y2<=N-2 */
void  mazePath( int ** maze,  int  direction[4][2], int  x1, int  y1, int  x2, int  y2, int  m, int  n)
{
     int  i,j,k;
     int  g,h;
     PSeqStack  st;
     DataType element;
     st = CreateEmptyStack_seq(m*n);
         if (st == NULL)
             return ;
     maze[x1][y1] = 2;          //从入口开始进入, 作标记
     element.x = x1;
     element.y = y1;
     element.d = -1;
     push_seq(st,element);               //入口点进栈
     while (!isEmptyStack_seq(st))
     {     //走不通时, 一步步回退
         element = top_seq(st);
         pop_seq(st);
         i = element.x;
         j = element.y;
         k = element.d + 1;
         while (k <= 3)
         {                    //依次试探每个方向
             g = i + direction[k][0];
             h = j + direction[k][1];
             if (g==x2 && h==y2 && maze[g][h]==0)
             {  //走到出口点
                 printf ( "The revers path is:\n" );   //打印路径上的每一点
                 printf ( "the node is: %d %d \n" ,g,h);
                 printf ( "the node is: %d %d \n" ,i,j);
                 while (!isEmptyStack_seq(st))
                 {
                     element = top_seq(st);
                     pop_seq(st);
                     printf ( "the node is: %d %d \n" ,element.x,element.y);
                 }
                 free (st->s);
                 free (st);
                 return ;
             }
             if (maze[g][h] == 0)
             {    //走到没走过的点
                 maze[g][h] = 2;      //作标记
                 element.x = i;
                 element.y = j;
                 element.d = k;
                 push_seq(st,element);   //进栈
                 i = g;      //下一点转换成当前点
                 j = h;
                 k = -1;
             }
             k = k + 1;
         }
     }
     printf ( "The path has not been found.\n" );
         free (st->s);
     free (st);
}
　　
int  main()
{
     int  maze[M][N] ={
                     {1,1,1,1,1,1,1,1,1,1,1},
                     {1,0,1,0,0,1,1,1,0,0,1},
                     {1,0,0,0,0,0,1,0,0,1,1},
                     {1,0,1,1,1,0,0,0,1,1,1},
                     {1,0,0,0,1,0,1,1,0,1,1},
                     {1,1,0,0,1,0,1,1,0,0,1},
                     {1,1,1,0,0,0,0,0,0,0,1},
                     {1,1,1,1,1,1,1,1,1,1,1},
                     };
     int  direction[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
     mazePath(maze,direction,1,1,6,9,M,N);
     return  0;
}

表达式计算
　　　对于键盘输入的表达式，判断是否合法，如果合法，输出运算结果。
　　说明：
　　　（1）表达式不能为空
　　　（2）可以出现在表达式中的字符有：
　　　运算符“+”、“-”、“*”、“\”；
　　　左右括号“(”、“)”；
　　　整数（可以是多位的）；
　　　空格和制表符。
　　例如：若输入的表达式为“20 + (3*(4+1) - 5)/2 - 3”，则应输出22。
　　　实例解析：
　　　使用栈先将中缀表达式转化为后缀表达式，再来求后缀表达式的值。
　　　1、转化为后缀表达式步骤如下：
建一个空栈作为运算符栈，顺序扫描中缀表达式。
　　①若读到其他字符：忽略。其他字符包括‘  ’、 ‘ \t’等。
   ②若读到数字：输出（指：写入数组）
   ③若读到左括号：入栈
   ④若读到右括号：不断将栈中元素弹出、输出，直到遇到左括号，将其弹出但不输出。
    ⑤若读到加或减：反复检查，若栈不空且栈顶为加、减、乘或除时，弹出并输出栈顶元素。读入的运算符(加或减)入栈。
   ⑥若读到乘或除：若栈不空且栈顶为乘或除时，弹出并输出栈顶元素。读入的运算符(乘或除)入栈
缀表达式扫描完毕后，将栈中剩余元素弹出、输出。
　　　2、计算后缀表达式值步骤如下：
   创建一个空栈，顺序扫描后缀表达式
   ①若读到数字：入栈。
   ②若读到其他字符：忽略。其他字符包括‘  ’、 ‘ \t’等。
   ③若读到运算符：从栈中弹出两个元素进行计算，将结果入栈。
   后缀表达式扫描完毕后，栈顶元素即为结果。
   程序如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
#include <stdio.h>
#include <malloc.h>
#define DataType char
#define TRUE  1
#define FALSE 0
#define MAX_SEQSTACK 100
struct   SeqStack
  {     //顺序栈类型定义
     int  MAXNUM;
     int   t;            // t<MAXNUM，指示栈顶位置，而不是元素个数
     DataType  *s;
};
     　　
typedef   struct  SeqStack  *PSeqStack;  //顺序栈类型的指针类型
/以下5个函数的实现见本章实例13
PSeqStack CreateEmptyStack_seq();
void   push_seq(PSeqStack pastack, DataType x);
void   pop_seq(PSeqStack pastack);
int  isEmptyStack_seq(PSeqStack pastack);
DataType  top_seq(PSeqStack pastack);
//下面代码将中缀表达式转换为后缀表达式，如成功返回TRUE
int  infixtoSuffix( char  *infix,  char  *suffix)
{
     int  state_int = FALSE;
     /*记录状态，TRUE表示刚读入的是数字，FALSE表示刚读入的不是数字。  设置这个变量的目的是每输出一个整数后输出一个空格，以免连续输出的两个整数混在一起。*/
     char  c, c2;
     int  i, j = 0;
     PSeqStack ps = CreateEmptyStack_seq();
     　　  if (ps == NULL)
         　　    return  FALSE;      
     if (infix[0] ==  '\0' )
     {
         free (ps->s);
         free (ps);
         return  FALSE;
     }
     for (i = 0; infix[i] !=  '\0' ; i++)
     {
         c = infix[i];
         switch (c){
         case  ' ' :
             case  '\t' :
             case  '\n' :
                 if (state_int == TRUE)  //从TRUE到FALSE时，输出空格
                     suffix[j++] =  ' ' ;
             　　  state_int = FALSE;
             break ;
         case  '0' :
             case  '1' :
             case  '2' :
             case  '3' :
             case  '4' :
         case  '5' :
             case  '6' :
             case  '7' :
             case  '8' :
             case  '9' :
                 state_int = TRUE;
                 suffix[j++] = c;       //遇到数字，输出
             break ;
         case  '(' :
             if (state_int == TRUE)
                 suffix[j++] =  ' ' ;
             state_int = FALSE;
             push_seq(ps, c);
             break ;
         case  ')' :
             if (state_int == TRUE)
                 suffix[j++] =  ' ' ;
             state_int = FALSE;
             c2 =  ')' ;
             while (!isEmptyStack_seq(ps))
             {
                 c2 = top_seq(ps);
                 pop_seq(ps);
                 if (c2 ==  '(' )
                     break ;
                 suffix[j++] = c2;
             }    //读入右括号，弹出输出，直到遇到左括号，弹出不输出
             if (c2 !=  '(' )
             {
                 free (ps->s);
                 free (ps);
                 suffix[j++] =  '\0' ;
                 return  FALSE;   //找不到左括号，非法
             }
             break ;
         case  '+' :
             case  '-' :
             if (state_int == TRUE)
                 suffix[j++] =  ' ' ;
             state_int = FALSE;
             while (!isEmptyStack_seq(ps))
             {
                 c2 = top_seq(ps);
                 if (c2== '+'  || c2== '-'  || c2== '*'  || c2== '/' )
                 {
                     pop_seq(ps);
                     suffix[j++] = c2;
                 }         //栈顶为加减乘除时，弹出栈顶元素并输出
                 else
                     break ;
             }
             push_seq(ps,c);
             break ;
         case  '*' :
             case  '/' :
             if (state_int == TRUE)
                 suffix[j++] =  ' ' ;
             state_int = FALSE;
             while (!isEmptyStack_seq(ps))
             {
                 c2 = top_seq(ps);
                 if (c2 ==  '*'  || c2 ==  '/'  )
                 {
                     pop_seq(ps);
                     suffix[j++] = c2;
                 }    //栈顶为加减乘除时，弹出栈顶元素并输出
                 else
                     break ;
             }
             push_seq(ps,c);
             break ;
         default :              //出现其他非法字符
             free (ps->s);
             free (ps);
             suffix[j++] =  '\0' ;
             return  FALSE;
         }
     }
     if (state_int == TRUE)
         suffix[j++] =  ' ' ;
     while (!isEmptyStack_seq(ps))
     {
         c2 = top_seq(ps);
         pop_seq(ps);
         if (c2 ==  '(' )
         {
             free (ps->s);
             free (ps);
             suffix[j++] =  '\0' ;
             return  FALSE;
         }
         suffix[j++] = c2;
     }
     free (ps->s);
     　　　 free (ps);
     suffix[j++] =  '\0' ;
     return  TRUE;
}
/*下面函数用于计算后缀表达式的值，若非法返回FALSE；否则返回TRUE，且*presult存放计算结果*/
int  calculateSuffix( char  *suffix,  int  *presult)
{
     int  state_int = FALSE;
     int  num = 0, num1, num2;
     int  i;
     char  c;
     PSeqStack ps = CreateEmptyStack_seq();
     if (ps == NULL)
         return  FALSE;     
     for (i = 0; suffix[i] !=  '\0' ; i++)
     {
         c = suffix[i];
         switch (c)
         {
             case  '0' :
             case  '1' :
             case  '2' :
             case  '3' :
             case  '4' :
             case  '5' :
             case  '6' :
             case  '7' :
             case  '8' :
             case  '9' :
             if (state_int == TRUE)
                 num = num*10 + c -  '0' ;
             else
                 num = c - '0' ;
             state_int = TRUE;
             break ;
         case  ' ' :
         case  '\t' :
         case  '\n' :
             if (state_int == TRUE)
             {
                 push_seq(ps, num);
                 state_int = FALSE;
             }
             break ;
         case  '+' :
         case  '-' :
         case  '*' :
         case  '/' :
             if (state_int == TRUE)
             {
                 push_seq(ps, num);
                 state_int = FALSE;
             }
             if (isEmptyStack_seq(ps))
             {
                 free (ps->s);
                 free (ps);
                 return  FALSE;
             }
             num2 = top_seq(ps);
             pop_seq(ps);
             if (isEmptyStack_seq(ps))
             {
                 free (ps->s);
                 free (ps);
                 return  FALSE;
             }
             num1 = top_seq(ps);
             pop_seq(ps);
             if (c ==  '+' )
                 push_seq(ps, num1+num2);
             if (c ==  '-' )
                 push_seq(ps, num1-num2);
             if (c ==  '*' )
                 push_seq(ps, num1*num2);
             if (c ==  '/' )
             {
                 if (num2 == 0)
                 {     //除数为0返回FALSE
                     free (ps->s);
                     free (ps);
                     return  FALSE;
                 }
                 push_seq(ps, num1/num2);
             }
             break ;
         default :               //出现其他非法字符
             free (ps->s);
                 free (ps);
             return  FALSE;
         }
     }
     *presult = top_seq(ps);
     pop_seq(ps);
     if (!isEmptyStack_seq(ps))    //栈中还有其他字符，非法
     {
         free (ps->s);
         free (ps);
         return  FALSE;
     }
     free (ps->s);
         free (ps);
         return  TRUE;
}
　　
int  main()
{
     char  infix[80] =  "20+(3*(4+1)-5)/2-3" ;
     char  suffix[80];
     int  result;
     if (infixtoSuffix(infix,suffix) == TRUE)
     {
         if (calculateSuffix(suffix,&result) == TRUE)
             printf ( "The Reuslt is: %3d\n" , result);
         else
             printf ( "Error!\n" );
     }
     else
         printf ( "Input Error!\n" );
     return  0;
}