数据结构课程实践

《数据结构课程实践》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、——课程实践数据结构课程设计报告学校:哈尔滨理工大学学院：管理学院专业：信息管理与信息系统姓名：苏雅班级：信管11——2学号：1106040213N皇后问题一、设计要求与分析1.设计要求在一个n*n的棋盘上放置n个皇后，要求放置的n个皇后不会互相吃掉；皇后棋子可以吃掉它所在的那一行、那一列，以及那两条对角线上的任何棋子。2设计分析此问题由八皇后问题演变而来，是八皇后问题的升级版，你可以随意输入一个比4大的数字，本程序将自动求出相关的某皇后问题。回溯算法是尝试搜索算法中最为基本的一种算法，并采用了一种“走不通就掉头”的思想，当

2、发现已不满足求解条件时，就“回溯”返回，尝试跌的路径。解决8皇后的算法有多种，其中加约束条件的枚举算法拥有最好的可读性，也能从中体会到回溯的思想，但是它职能解决皇后“个数为常量”的问题，却不能解决任意的n皇后问题，因此也不是典型的回溯算法模型。非递归算法可以说是典型的回溯算法模型但是对于回溯算法，更方便的是用递归控制方式实现，用这种方法可以解决任意的n皇后问题。算法思想同样实现用深度优先搜索，并在不满足约束条件时及时回溯二、算法求精这个问题包括了行，列，两条对角线；  列：规定每一列放一个皇后，不会造成列上的冲突；  行：当

3、第i行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以i为下标的标记置为被占领状态；  对角线：对角线有两个方向。在这我把这两条对角线称为：主对角线和从对角线。在同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j)是常数。因此，当第i个皇后占领了第j列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。/*-------------------------回溯法--------------------------*///static：避免命名有冲突//棋盘初始化时，空格的地

4、方为+，放置皇后的地方为?staticcharQueen[20][20];staticinta[20];//数组a[i]：a[i]表示第i个皇后放置的列,i的范围：----8staticintb[40];//主对角线数组staticintc[40];//从对角线数组，根据程序的运行，去决定主从对角线是否放入皇后staticintiQueenNum=0;//记录总的棋盘状态数staticintNum=1;intn;voidiQueen(introw);//参数i代表行voidlocation(){introw;//横行intc

5、ow;//纵行for(row=0;row

6、row+cow]==0)//如果无冲突{Queen[row][cow]='?';//放皇后a[cow]=1;//标记，下一次该列上不能放皇后b[row-cow+n-1]=1;//标记，下一次该主对角线上不能放皇后c[row+cow]=1;//标记，下一次该从对角线上不能放皇后if(row

7、"<

8、+;cout<