数据结构课程设计——八皇后问题.doc

发布时间：2022-06-08 发布人：admin 分类：说明书资料大小：0.32M 资料格式：doc 举报版权申诉

jh1991-3975548-4744300845394285385.doc.pdf-第1页.png

第1页 / 共9页

jh1991-3975548-4744300845394285385.doc.pdf-第2页.png

第2页 / 共9页

jh1991-3975548-4744300845394285385.doc.pdf-第3页.png

第3页 / 共9页

jh1991-3975548-4744300845394285385.doc.pdf-第4页.png

第4页 / 共9页

jh1991-3975548-4744300845394285385.doc.pdf-第5页.png

第5页 / 共9页

jh1991-3975548-4744300845394285385.doc.pdf-第6页.png

第6页 / 共9页

jh1991-3975548-4744300845394285385.doc.pdf-第7页.png

第7页 / 共9页

jh1991-3975548-4744300845394285385.doc.pdf-第8页.png

第8页 / 共9页

文本预览

成绩 09信计2010-2011（一）数据结构课程设计设计题目八皇后问题设计时间学生姓名学生学号所在班级 2011 年 1 月 2 日徐亚运 20100406241 10 信计（2）指导教师刘风华徐州工程学院数学与物理科学学院一．需求分析本次课程设计中，用到的主要知识有：递归法的运用，for 语句的灵活运用，数据结构中树知识的灵活运用、栈及数组的掌握。

二．概要设计根据问题提供问题的解决方案，实现棋盘的绘制和棋子的内摆放功能。而可以选择的存储结构为线性存储结构，逻辑结构为图形结构。实现主窗口的棋子摆放规则，可以选用线性存储结构和图形结构构造一个新的数据结构，定义在其上的功能为根据循环递归法改变中皇后的位置，并将其传递给整个棋盘的对象，使其按照要求实现棋子的摆放，直到出现正确的放置方法。本课件是用循环递归循环来实现的，分别一一测试了每一种摆法，并把它拥有的 92 种变化表现出来。在这个程序中，我的主要思路以及思想是这样的： 1）解决冲突问题：这个问题包括了行，列，两条对角线；列：规定每一列放一个皇后，不会造成列上的冲突；行：当第 I 行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以 I 为下标的标记置为被占领状态；对角线：对角线有两个方向。在这我把这两条对角线称为：主对角线和从对角线。在同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j) 是常数。因此，当第 I 个皇后占领了第 J 列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。 2）数据结构的实现而对于数据结构的实现，着重于: 数组 a[I]：a [I]表示第 I 个皇后放置的列；I 的范围：1..8; 对角线数组：b[j](主对角线),c[j]（从对角线），根据程序的运行，去决定主从对角线是否放入皇后； A、数据初始化。 B、从 n 列开始摆放第 n 个皇后（因为这样便可以符合每一竖列一个皇后的要求），先测试当前位置（n，m）是否等于 0（未被占领）。如果是，摆放第

n 个皇后，并宣布占领（记得要横列竖列斜列一起设置），接着进行递归；如果不是，测试下一个位置（n，m+1），但是如果当 n<=8，m=8 时，发现此时已无法摆放时，便要进行回溯。从问题的某一种可能出发，搜索从这种情况能出发，继续搜索，这种不断“回溯”的寻找解的方法，称为“回溯法”。 C、使用数组实现回溯法的思想。 D、当 n>8 时，便打印出结果。 E、输出函数我使用 printf 输出，运行形式为：第 m 种方法为：* * * * * * * 3）、程序框图或流程图，程序清单与调用关系

三、详细设计 #include #define NUM 8 /*定义数组的大小*/ int a[NUM+1]; int main() { int i,k,flag,not_finish=1,count=0; i=1; /*正在处理的元素下标，表示前i-1个元素已符合要求，正在处理

第i个元素*/ a[1]=1; /*为数组的第一个元素赋初值*/ printf("The possible configuration of 8 queens are:\n"); while(not_finish) /*not_finish=1:处理尚未结束*/ { while(not_finish&&i<=NUM) /*处理尚未结束且还没处理到第NUM个元素*/ { for(flag=1,k=1;flag&&k1&&a[i]==NUM)

a[i]=1; /*当a[i]为NUM时将a[i]的值置1*/ else if(i==1&&a[i]==NUM) not_finish=0; /*当第一位的值达到NUM时结束*/ else a[i]++; /*将a[i]的值取下一个值*/ } else if(a[i]==NUM) a[i]=1; else a[i]++; /*将a[i]的值取下一个值*/ } else if(++i<=NUM) if(a[i-1]==NUM) a[i]=1; /*若前一个元素的值为NUM则a[i]=1*/ else a[i]=a[i-1]+1; /*否则元素的值为前一个元素的下一个值*/ } if(not_finish) { ++count; printf((count-1)%3?" [%2d]: ":" \n[%2d]: ",count); for(k=1;k<=NUM;k++) /*输出结果*/ printf(" %d",a[k]);

if(a[NUM-1]

六、课设总结

分享到：

赞收藏

资料库

数据结构课程设计——八皇后问题.doc

相关推荐

课程资源

热门标签

最新资料