奇小才 发表于 2016-10-16 21:15:32

小甲鱼数据结构三十四讲八皇后代码解释

我们从主函数开始分析:
        首先定义了一个8X8的棋盘(也就是我们的二维数组),定义了i(行),j(列)两个变量,用一个for循环语句初始化棋盘,此时棋盘每一个数都是0。之后调用我们所写好的EightQueen(0,8,chess)函数

        于是我们再去看EightQueen函数的部分,它有三个参数(起始行,列数,一个名为chess的指向棋盘每一行的指针),首先函数初始化了一个棋盘,这个棋盘是形参定义的棋盘,然后用for的双循环将实参所产生的棋盘的每一项赋值(即形参棋盘每一项也都初始化为0)。
        之后执行if/else语句,如果起始行row的值为0,那么我们再次用for循环打印出一幅棋盘。
        如果row的值不是8,(我们放置皇后需要一行一行放置嘛,所以row不是8,说明一种情况还没完成嘛,就是一个棋盘上的8个皇后还没放置完)



核心部分:
        那么程序执行else下的语句:语句中用for循环,参数是我们的列数(因为每一行都要一列一列判断是否能放置嘛),之后遇到了我们的notdange(row,j,chess)函数,这个相信大家应该能看懂,就是看看此时我们所判断的位置是否安全,每个皇后的横纵坐标与其他任何一个皇后相同,也不能与任何一个皇后在一条对角线上,(检验如果皇后放置此时的位置是否与之前放好的皇后有冲突),如果有危险,那么j+1,判断下一列,如果没有危险,那么很幸运,继续往下执行:先把这一行所有位置都赋值为0,然后再把我们那个不危险的位置赋值为1就好啦。
        之后又调用了一次EightQueen函数,为了方便解释,我们把它叫做EightQueen2吧
        EightQueen2函数中(row为1,因为row初始化为0):首先在原来放好一行(此时已经放好一个皇后)的棋盘上再把棋盘初始化,(注意:调用EightQueen1的参数是row+1,n,chess2,所以是在原来放好一个皇后的基础上),同理,再次执行else语句:放置好第二个皇后,调用EightQueen2(row+1,n,chess2)

        EightQueen3函数中(row为2)函数中:则在原来放好两行的基础上初始化,再次执行else语句,放好第三个皇后,调用EightQueen4,此时row是3
..............................
..............................

        EightQueen8函数中(此时row是7):则在原来放好八行的基础上初始化,再次执行else语句,放好第8个皇后,此时row终于变成8了,然后我们调用了EightQueen9。

        EightQueen9函数中(此时row是8):初始化后,我们的函数终于执行了if语句下的内容,打印出了一副棋盘,那么之后呢?
        我们所用的方法是递归,递归递归,归去来兮,所以嘛:一定是要返回的,此时我们回想是EightQueen8调用的EightQueen9,现在EightQueen9已经执行完了,那么我们的EightQueen8中的else中的for语句是不是还没有执行完呢?因为我们此时在判断第八行的不危险位置,已经放置好一种第八行的皇后,还需要看看第八行的其他位置,于是EightQueen8中else语句中的for继续执行(j++,直到 j加到8,最后一个位置为止)每次遇到合适的,都会再次调用EightQueen9打印出一种不同的棋盘。。。
        那么直到j++加到8,我们已经找出第八行放置皇后的所有情况,并打印出了,也就是说我们的EightQueen8函数已经结束了,那么然后呢?
        同理,相信朋友们可以想到了,EightQueen8是被EightQueen7调用出来的,也就是说,其实我们是在第七行的一种合适情况下打印出了第八行可选的所有情况,那么EightQueen7的else语句中的for继续循环,判断第七行的其他情况下,再对应第八行的各种情况,又打印出其他情况:也就是说:EightQueen7函数在第七行选好一个位置后调用EightQueen8,EightQueen8选好一个位置后又调用EightQueen9打印出来
说到这里,大家应该明白了吧?第七行匹配第八行的所有情况打印出来后,又会改变第六行,再通过第六行匹配第七行匹配第八行和合适情况再打印。。。。。。。。就这样一直返回,打印直到最早的EightQueen(),输出所有的92种情况



            

暴力书生 发表于 2016-10-26 20:09:19

赞楼主
页: [1]
查看完整版本: 小甲鱼数据结构三十四讲八皇后代码解释