数据结构课程设计-八皇后问题

安徽省巢湖学院计算机与信息工程学院课程设计报告课程名称《数据结构》课题名称八皇后问题专业计算机科学与技术班级10计本2班学号10012096姓名吴宏联系方式15156576700指导教师蔡敏2011年12月30日目录1、数据结构课程设计任务书..............................................................................................１1.1、题目.....................................................................................................................１1.2、要求.....................................................................................................................１2、总体设计.......................................................................................................................１2.1、功能模块设计......................................................................................................１2.2、所有功能模块的流程图........................................................................................１3、详细设计.......................................................................................................................２3.1、程序中所采用的存储结构的说明..........................................................................２3.2、算法的设计思想...................................................................................................２4、源程序清单和执行结果...................................................................................................35、C程序设计总结..............................................................................................................56、致谢................................................................................................................................57、参考文献.........................................................................................................................5第１页1、数据结构课程设计任务书1.1、题目八皇后1.2、要求设计程序解决八皇后问题，设计要求如下：1：依次输出各种成功的放置方法；2：画出棋盘的图形界面，并在其上动态地标注行走的过程；3：程序能方便地移植到其他规格的棋盘上。:2、总体设计2.1、功能模块设计顾名思义，穷举法就是通过把需要解决问题的所有可能情况逐一试验来找出符合条件的解的方法，对于许多毫无规律的问题而言，穷举法用时间上的牺牲换来了解的全面性保证，尤其是随着计算机运算速度的飞速发展，穷举法的形象已经不再是最低等和原始的无奈之举，比如经常有黑客在几乎没有任何已知信息的情况下利用穷举法来破译密码，足见这种方法还是有其适用的领域的。可是，在实际生活中，只有很少的一些问题是真正意义上的“毫无规律”，其余的大多数仍有内在规律可循，对于这些问题，使用穷举法在效率上就显得比较低下，而在一些对速度要求较高的区域和规模较大的问题上，效率的低下往往是致命的。2.2、所有功能模块的流程图第２页图4算法流程图3、详细设计3.1、程序中所采用的存储结构的说明当前行和列分别用i和j表示，用数组s[1…8]表示顺序栈，栈空间的下表值表示皇后所在的行号，栈的内容表示皇后所在的列号。若皇后放在位置(i,j)上，则将j加入栈中。位于同一条”/”方向的对角线上的方格，其行、列坐标之和i+j是相等的，这种方向的对角线有15条，其行、列之和分别为2~16，因此用b[2…16]标记该方向的对角线上有无皇后，b[k]为真时表示该方向的第条对角线上无皇后。行、列之差相等的方格在同一条”\”方向的对角线上，该类的对角线有15条，其行、列之差分别是-7~7，因为C语言的下标是从0开始的，所以用c[2…16]标记这种方向的对角线上有无皇后,c[k]为真时表示该方向的第k条对角线上有无皇后。3.2、算法的设计思想从第一行起逐行放置皇后，每放置一个皇后均需要依次对第1,2，…8列进行试探，并尽可能取小的列数。若当前试探的列位置是安全的，即不与已放置的其他皇后冲突，则将该行的列位置保存在栈中，然后继续在下一行上寻找安全位置；若当前试探的列位置不安全，则用下一列进行试探，当8列位置试探完毕都未找到安全位置时，就退栈回溯到上一行，就修改栈顶保存的皇后位置，然后继续试探。第３页4、源程序清单和执行结果：#includeiostream#includecstdlibusingnamespacestd;#definetru1#definefals0inta[9],s[9],b[17],c[17];voidprint(){inti;cout行D号?：êo12345678endl;cout列¢D号?;for(i=1;i=8;i++){couts[i];}}voidmovequeen(inti,intj){a[i]=tru;b[i+j]=tru;c[i-j+9]=tru;}voideightqueen(){inti,j;for(i=2;i=16;i++){if(i=2&&i=9)a[i-1]=tru;b[i]=c[i]=tru;}//初?始º?棋?盘¨¬i=j=1;while(i=1){while(j=8){if(a[j]&&b[i+j]&&c[i-j+9])break;j++;}//找¨°到Ì?安ã2全¨?位?置?}if(j=8){s[i]=j;a[j]=fals;b[i+j]=fals;c[i-j+9]=fals;//设¦¨¨置?皇¨º后¨®第４页if(i==8){print();movequeen(i,j);i--;j=s[i];movequeen(i,j);j++;//当Ì¡À排?列¢D完ª¨º成¨¦时º¡À输º?出?一°?种?排?列¢D方¤?式º?}else{i++;j=1;//否¤?则¨°设¦¨¨置?下?一°?列¢D皇¨º后¨®}}else{i--;if(i=1){j=s[i];movequeen(i,j);j++;}//输º?出?所¨´有®D的Ì?排?列¢D方¤?式º?}}intmain(){eightqueen();system(pause);return0;}执行结果：第５页7、C程序设计总结本程序在刚开始调试时有许多错误，但在我的努力及同学的帮助下都被一一克服，现在在操作本程序时可根据提示进行相关操作，能正确输出结果。在刚开始的几次调试中曾经出现过不能运行、不能产生十以内随机数字、不能随机出现加减、不会正确输出结果、不能进行循环练习等等问题。经过我的努力及同学的帮助，这些问题得到克服，并且使程序的功能也得到了一定的完善。现在它能对出错的题目发出报警声，并且给出正确答案。最后还能分别输出对错的题数及所得分数。在这次设计过程中，不仅复习课本上所学知识，还通过查资料、问同学学到了课本上没有的知识。从而启发我，要想写好程序，在写好课本知识的同时还需要多读和专业有关的一些书籍，同时还需要多动脑子，尽量把所学的知识综合起来应用，力争写出完美的程序。除此之外，我还得到了一些有用的教训：写程序时必须要细心，不能输错一个字符标点，就连全角半角也得注意。在修改时要有耐心，编译出错后必须逐个错误去改正，绝不能心急浮躁，否则修改之后还会有新的错误。8、致谢能够完成这次课程设计必须感谢C语言课程老师他帮我修改了几处重要错误，同时启发我完善了该程序的功能。9、参考文献[1]C++语言程序设计（第四版）郑莉著清华大学出版社[2]