《数据结构课程设计报告-8皇后问题.》由会员分享，可在线阅读，更多相关《数据结构课程设计报告-8皇后问题.（10页珍藏版）》请在金锄头文库上搜索。
1、1 数据结构课程设计 选题：选题： 八皇后问题八皇后问题 姓姓 名：名： 学学 号：号： 指导老师：指导老师： 目 录 一.选题概述- -3 2 2.设计要求与分析- -3 3.数据结构与定义- -4 1.结构体定义 2.函数定义 3.函数之间的定义 4.程序段与分析- -5 5.完整程序代码及运行结果截图- 7 6.心得体会- -10 7.参考文献- -10 3 一选题概述：一选题概述： 在实际应用中，有相当一类问题需要找出它的解集合，或者要求找 出某些约束条件下的最优解。求解时经常使用一种称为回溯的方法 来解决。所谓回溯就是走回头路，该方法是在一定的约束条件下试 探地搜索前进，若前进中受阻
2、，则回头另择通路继续搜索。为了能 够沿着原路逆序回退，需用栈来保存曾经到达的每一个状态，栈顶 的状态即为回退的第一站，因此回溯法均可利用栈来实现。而解决 八皇后问题就是利用回溯法和栈来实现的。 二设计要求与分析二设计要求与分析 八皇后问题是在 8x8 的国际象棋棋盘上，安放 8 个皇后，要求 没有一个皇后能够“吃掉”任何其他一个皇后，即没有两个或两个 以上的皇后占据棋盘上的同一行、同一列或同一条对角线。 八皇后在棋盘上分布的各种可能的格局，其数目非常大，约等 于 232 种，但是，可以将一些明显不满足问题要求的格局排除掉。 由于任意两个皇后不能同行，即每一行只能放置一个皇后，因此将 第 i 个
3、皇后放置在第 i 行上。这样在放置第 i 个皇后时，只要考虑 它与前 i 一 1 个皇后处于不同列和不同对角线位置上即可。因此， 其算法基本思想如下： 从第 1 行起逐行放置皇后，每放置一个皇后均需要依次对第 1，2，8 列进行试探，并尽可能取小的列数。若当前试探的列 4 位置是安全的，即不与已放置的其他皇后冲突，则将该行的列位置 保存在栈中，然后继续在下一行上寻找安全位置；若当前试探的列 位置不安全，则用下一列进行试探，当 8 列位置试探完毕都未找到 安全位置时，就退栈回溯到上一行，修改栈顶保存的皇后位置，然 后继续试探。 该算法抽象描述如下： （1)置当前行当前列均为 1; （2）whil
4、e(当前行号8) （3） 检查当前行，从当前列起逐列试探，寻找安全列号； （4）if（找到安全列号） （5）放置皇后，将列号记入栈中，并将下一行置成当前行， 第 1 列置为当前列； （6）else （7）退栈回溯到上一行，移去该行已放置的皇后，以该皇后 所在列的下一列作为 当前列； （8） 结束程序。 3数据结构与定义数据结构与定义 1.结构体定义结构体定义 typedef struct int colMaxSize; /coli存放第 i 个皇后的列号 int top; /栈顶指针 5 Type; 2.函数定义函数定义 bool place(Type st,int i,int j) /测试(
5、i,j)是否与 1i-1 皇后有冲突 void queen(int n) /求解皇后问题 void main() /主函数 3.函数之间的调用关系函数之间的调用关系 main queen place 4程序块与分析程序块与分析 bool place(Type st,int i,int j)/测试(i,j)是否与 1i-1 皇后有冲突 int k=1; if(i=1) return true;/存放第一个皇后时没有冲突 while(k=i-1)/j=1 到 k-1 是已经放置了皇后的列 if(st.colk=j)|(abs(j-st.colk)=abs(k-i) return false; k+
6、; return true; （k，st.colk） （k，st.colk） j-st.colk j-st.colk (i,j) i-k i-k (i,j) 6 /测试(i,j)位置是否与已经放好的第 1 个到第 i1 皇后有冲突。已经 放置好的第 1 个到第 1i-1 个皇后已放置在 st 栈中。St 栈用的是顺 序栈，栈顶指针从 1 开始，st.colk用于存放第 k（1=i0)/栈不空时循环 i=st.top;/当前皇后为第 i 个皇后 if(st.top=n)/所有皇后都放置好了，输出一个解 printf(“第%d 个解：“,+count); for(k=1;k=st.top;k+)
7、printf(“(%d,%d)“,k,st.colk); printf(“n“); find=false; for(j=1;j0) if(st.colst.top=n)/本行也没有可放的位置，则退栈 st.top-; for(j=st.colst.top+1;jn)/当前皇后在本行没有可放的位置 st.top-;/退栈 else/本行找到一个位置后，推出回溯 break; void main() /主函数 int n; printf(“请输入皇后个数 n=“); scanf(“%d“, printf(“%d 皇后问题求解如下:n“,n); queen(n); printf(“n“); 8 5.
8、完整程序代码及运行结果截图完整程序代码及运行结果截图 #include #include #define MaxSize 100 typedef struct int colMaxSize;/coli存放第 i 个皇后的列号 int top;/栈顶指针 StType;/定义顺序栈类型 int count=0; bool place(StType st,int i,int j)/测试(i,j)是否与 1i-1 皇后有冲突 int k=1; if(i=1) return true;/存放第一个皇后时没有冲突 while(k0)/栈不空时循环 i=st.top;/当前皇后为第 i 个皇后 if(st
9、.top=n)/所有皇后都放置好了，输出一个解 printf(“第%d 个解：“,+count); for(k=1;k=st.top;k+) printf(“(%d,%d)“,k,st.colk); printf(“n“); find=false; for(j=1;j0) if(st.colst.top=n)/本行也没有可放的位置，则退栈 st.top-; for(j=st.colst.top+1;jn)/当前皇后在本行没有可放的位置 st.top-;/退栈 else/本行找到一个位置后，推出回溯 break; void main() int n; printf(“请输入皇后个数 n=“);
10、scanf(“%d“, printf(“%d 皇后问题求解如下:n“,n); queen(n); printf(“n“); 10 6.心得体会心得体会 1.善于学习别人,多请教牛人,才会更快提高自己。有些问题也许就是 自己在某一点想不通，想法转不过来，这就消耗了很多时间。而经 过牛人的点拨问题就解决了，牛人们也会更直接，更清晰的教导一 些技术，通过向他们学习，才会更快的提高自己的技能。 2.多找一些题目来练习，多敲代码，才会更有感觉。在练习的过程 中找出规则，形成编程思想。 3.小组合作形成共同进步。小组成员的讨论过程中，将各自的想法 提出来，分析优缺点，这过程中每个成员也可以学习到其他成员的 解题思想，也可以审视自己的解题思想，获得提升。 7.参考文献参考文献 1.数据结构（C 语言版）严蔚敏，吴伟民 清华大学出版 社 2.C 语言程序设计 何钦铭，颜晖 高等教育出版社 11 3.数据结构教程 李春葆 清华大学出版社
