数据结构课程设计报告

数据结构课程设计

开始开始 数据初始化 从第列开始摆放第nn个皇后 从nn列开始摆放第个皇后2 1

当前位置（n，m，） ） N 当前位置（nn，m） Y 当前位置（m 是否被占领 是否被占领是否被占领

n=n+1 n=n+1 摆放皇后，并 摆放皇后，并摆放皇后，并宣布占领宣布占领 宣布占领测试下个位置 m=m+1 0n<=8&m=8 Y N 打印

进行回溯 结果 5

数据结构课程设计

三、 详细设计

//定义数组

int a[8] //表示第i个皇后放置的列，范围为1~8。

int b[8] //表示第j行空闲，b[j]=1 表示第j行被占领，范围为1~8 int c[30] //表示第（i-j）条对角线空闲，c[i-j]=1 表示第（i-j）条对角线被占领，范围-7~7

int d[30] //表示第（i+j）条对角线空闲，d[i+j]=1 表示第（i+j）条对角线被占领，范围2~16。

//位置标明法打印 void print1() { }

//矩阵表示法打印

6

X++;

cout<<\ //每一行皇后放置的列数的第X种情况 for (k=1;k<9;k++)

cout<<\

cout<<\

数据结构课程设计

void print2() { int t,n; Y++;

cout<<\矩阵形式的第Y种情况 for (k=1;k<9;k++)

{

n=a[k]; for(t=1;t

cout<<\

cout<<\ t++; for(t;t<9;t++)

cout<<\

cout<<\ }

cout<<\

}

//回溯递归法摆放皇后

7

数据结构课程设计

void PlaceQueen1(int i) { 突

皇后

int j;

for (j=1;j<9;j++) //每个皇后都有8种可能位置 {

if ((b[j]==0) &&(c[i+j]==0)&& (d[i-j]==0))

//判断位置是否冲

{

a[i]=j; b[j]=1; c[i+j]=1; d[i-j]=1; if (i<8)

PlaceQueen1(i+1); //8个皇后没有摆完，递归摆放下一

//摆放皇后 //宣布占领第J行 //占领两个对角线

else

print1(); //完成任务，打印结果

//回溯

b[j]=0; c[i+j]=0; d[i-j]=0;

8