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

数据结构课程设计题 目 八皇后的问题求解 学生姓名 羊庆衍 、刘天唱 指导教师 学 院 信息学院 专业班级 信科一班 完成时间 2014年1月2日 第一章 课程设计目的本学期我们对数据结构这门课程进行了学习。这门课程是一门实践性非常强的课程，为了让大家更好地理解与运用所学知识，提高动手能力，我们进行了此次课程设计实习。这次课程设计不但要求实习者掌握数据结构中的各方面知识，还要求实习者具备一定的语言基础和编程能力。具体说来，这次课程设计主要有两大方面目的。一是让实习着通过学习掌握数据结构中的知识。对于递归算法这一课题来说，所要求掌握的数据结构知识主要有：if语句的选择结构，for语句的循环结构，函数的调用来实现。二是二是通过实习巩固并提高实习者的C语言知识，并初步了解Visual C+的知识，提高其编程能力与专业水平。第二章 课程设计内容和要求2.1课程设计内容组成员名称和分工在一个的棋盘里放置个皇后，要求每个皇后两两之间不相冲（在每一横列竖列斜列只有一个皇后）并要求用递归算法实现，输出所有棋盘状态，其中空的地方为“*”，放置皇后的地方为“”2.1.1八皇后的建立与输出 对给定的的棋盘里的八个皇后进行讨论，根据递归法，循环结构和选择结构进行建立并输出之。2.2 运行环境该程序的运行环境为Windows7系统，Microsoft Visual C+6.0版本。第三章 课程设计分析3.1数据类型规定了函数返回值类型。党执行函数体中的语句后，通常会产生一个结果，这就是函数的返回值，它可以是任何有效的类型。若函数执行后不返回值，数据类型习惯用void来表示。如果在函数定义时没有数据类型出现，则默认为函数返回值为整型值(int)。3.2 函数调用调用一个函数之前必须对该函数进行说明。函数调用由函数名和函数调用运算符( )组成，( )内有0个或多个逗号分隔的参数(称为实参)。每一个参数是一个表达式，且参数的个数与参数的类型要与被调函数定义的参数(称为形参)个数和类型匹配。当被调函数执行时，首先计算实参表达式，并将结果值传送给行参，然后执行函数体，返回的返回值被传送到调用函数。如果函数调用后有返回值，调用表达是可以用在表达式中，而无参函数的调用是一个单独的语句。3.3 选择结构if语句的基本形式可分为两种：（1） if (表达式) 语句其执行过程是，首先计算表达式的值，若不为0，条件判断为真，则执行( )后面的语句，否则，if语句中止执行，即不执行( )后面的语句。（2） if(表达式) 语句1 else 语句2其执行过程是，首先计算表达式的值，若不为0，条件判断为真，则执行( )后面的语句，否则执行语句2。3.4 循环结构for 语句的一般形式：for (表达式1；表达式2；表达式3) 语句；/循环体其执行的过程有以下几个步骤：求解表达式1；求解表达式2，若其值为真，则执行for语句中指定的循环体语句，然后执行下面的第3)步。若为假，则结束循环；求解表达式3；转回上面第2）步继续执行；循环结束，执行for语句后面的其他语句。第四章 算法（数据结构）描述4.1.1 八皇后的存储结构定义其列数，行数，主对角线，从对角线，算法的种类数，static char Queen88;static int a8;/列数static int b15; / 代表主对角线static int c15; 代表从对角线static int iQueenNum=0; /记录总的棋盘状态数void qu(int i); /参数i代表行4.1.2 初始化棋盘在确定其中八皇后棋盘中的位置时，应该初始化一个棋盘，然后再输入数据int main() int iLine,iColumn; /棋盘初始化，空格为*，放置皇后的地方为 for(iLine=0;iLine8;iLine+) aiLine=0; /列标记初始化，表示无列冲突 for(iColumn=0;iColumn8;iColumn+) QueeniLineiColumn=*; /主、从对角线标记初始化，表示没有冲突 for(iLine=0;iLine15;iLine+) biLine=ciLine=0; qu(0); return 0;4.1.3建立并输出棋盘 数组a、b、c分别用来标记冲突，a数组代表列冲突，从a0a7代表第0列到第7列，如果某列上已经有皇后，则为1，否则为0；数组b代表主对角线冲突，为bi-j+7，即从b0b14，如果某条主对角线上已经有皇后，则为1，否则为0； 数组c代表从对角线冲突，为ci+j，即从c0c14，如果某条从对角线上已经有皇后，则为1，否则为0；void qu(int i) int iColumn; for(iColumn=0;iColumn8;iColumn+) if(aiColumn=0&bi-iColumn+7=0&ci+iColumn=0) /如果无冲突 QueeniiColumn=; /放皇后 aiColumn=1; /标记，下一次该列上不能放皇后 bi-iColumn+7=1; /标记，下一次该主对角线上不能放皇后 ci+iColumn=1; /标记，下一次该从对角线上不能放皇后 if(i7) qu(i+1); /如果行还没有遍历完，进入下一行 else /否则输出 /输出棋盘状态 int iLine,iColumn;for(int i=0;i1;i+)iQueenNum+;cout第iQueenNum种算法为：endl; for(iLine=0;iLine8;iLine+) for(iColumn=0;iColumn8;iColumn+) printf(%c ,QueeniLineiColumn); printf(n); printf(nn); /如果前次的皇后放置导致后面的放置无论如何都不能满足要求，则回溯，重置 QueeniiColumn=*; aiColumn=0; bi-iColumn+7=0; ci+iColumn=0; 第五章 源代码程序 八皇后问题#include #includeusing namespace std;static char Queen88;static int a8;static int b15;static int c15;static int iQueenNum=0; /记录总的棋盘状态数void qu(int i); /参数i代表行int main() int iLine,iColumn; /棋盘初始化，空格为*，放置皇后的地方为 for(iLine=0;iLine8;iLine+) aiLine=0; /列标记初始化，表示无列冲突 for(iColumn=0;iColumn8;iColumn+) QueeniLineiColumn=*; /主、从对角线标记初始化，表示没有冲突 for(iLine=0;iLine15;iLine+) biLine=ciLine=0; qu(0); return 0;void qu(int i) int iColumn; for(iColumn=0;iColumn8;iColumn+) if(aiColumn=0&bi-iColumn+7=0&ci+iColumn=0) /如果无冲突 QueeniiColumn=; /放皇后 aiColumn=1; /标记，下一次该列上不能放皇后 bi-iColumn+7=1; /标记，下一次该主对角线上不能放皇后 ci+iColumn=1; /标记，下一次该从对角线上不能放皇后 if(i7) qu(i+1); /如果行还没有遍历完，进入下一行 else /否则输出 /输出棋盘状态 int iLine,iColumn;for(int i=0;i1;i+)iQueenNum+;cout第iQueenNum种算法为：endl; for(iLine=0;iLine8;iLine+) for(iColumn=0;iColumn8;iColumn+) printf(%c ,QueeniLineiColumn); printf(n); printf(nn); /如果前次的皇后放置导致后面的放置无论如何都不能满足要求，则回溯，重置 QueeniiColumn=*; aiColumn=0; bi-iColumn+7=0; ci+iColumn=0; 第六章 运行结果分析由于在一些冲突问题上不太熟练，而且没有玩过八皇后，所以对于一些规则不是很了解，所以在程序的编写上出现一些错误，例如for语句的循环的次数没有控制得当。八皇后问题的递归算法的运行结果：第七章 结束语转眼，为期两周的数据结构课程设计实习即将结束了。在这次实习中，自己的C语言知识和数据结构知识得到了巩固，编程能力也有了一定的提高。同时也学会了解决问题的方法。总结起来，自己主要有以下几点体会：1. 必须牢固掌握基础知识。2.必须培养严谨的科学态度。3.这次课程设计也让我充分认识到数据结构这门课的重要性。它给我们一个思想和大纲，让我们在编程时容易找到思路，不至于无章可循。同时它也有广泛的实际应用。总之，在这次实习中，自己的C语言以及数据结构知识得到提高，编程能力也得到了提高。第八章 参考文献1 于永彦，于长辉，刘作军.C+程序设计实践教学指