数据结构与算法课程设计.doc

目录一、问题描述21.1题目内容：21.2基本要求：21.3提高要求：2二、需求分析21.1软件的基本功能：21.2输入输出形式：21.3测试数据要求：2三、概要设计21.1所需的ADT及作用：21.2主程序流程：41.3模块调用关系：5四、详细设计51.1数据类型：51.2每个操作的代码：51.2.1 get_attact( )51.2.2 get_horse(chess c)61.2.3 to_attact(int a,int b)81.2.4 get_mincover(chess c)91.3主程序的代码：101.4函数调用关系图：11五、编码与调试分析111.1遇到的问题及解决办法：11六、使用说明12七、测试结果12八、课程设计心得体会14参考文献：15一、问题描述1.1题目内容：在88的国际象棋棋盘上，如果在放置若干个马以后，使得整个棋盘的任意空位置上所放置的棋子均能被这些马吃掉，则称这组放置为棋盘的一个满覆盖。若去掉满覆盖中的任意一个棋子都会使这组放置不再是满覆盖，则称这一满覆盖为极小满覆盖。1.2基本要求：求解一个极小满覆盖，按照矩阵形式给出，用特殊符号表示马。1.3提高要求：（1） 能画出棋盘的图形形式，或在其上动态第演示试探过程；（2） 程序能方便地移植到其他规格的棋盘上。二、需求分析1.1软件的基本功能：求任意棋盘规模的马的极小满覆盖的一个解。1.2输入输出形式：有键盘输入棋盘的行数M和列数N。1.3测试数据要求：8*8的矩阵。三、概要设计1.1所需的ADT及作用：ADT chessData 马为字符型，每个位置被吃掉的次数为整形Operation get_attact() 前置条件：位置在棋盘范围内 输入：无 功能：计算每个位置被马吃掉的次数 输出：无后置条件：无to_attact(int i,int j) 前置条件：位置在棋盘范围内并且该位置尚不能被马吃掉 输入：无 功能：再次计算每个位置被马吃掉的次数 输出：无 后置条件：如果放马成功，此马可能吃掉的位置赋值为-1 get_horse(chess c) 前置条件：位置在棋盘范围内 输入：无功能：计算极小满覆盖输出：马的位置，此时的覆盖情况和每个位置被马吃掉的次数后置条件：无get_mincover(chess c) 前置条件：位置在棋盘范围内输入：无 功能：判断是否达到极小满覆盖，若达到便输出 输出：极小满覆盖的一个解 后置条件：无endADT开始输入棋盘的行数M和列数N调用get_horse(chess c )函数，计算出被马吃掉次数最多的位置，在此位置放马If（int iM&int jN）If（int i2M&int j2N）调用get_attact( )函数，计算并输出初始状态每个位置被马吃掉的次数调用to_attact(int 1,int j)函数，再次计算每个位置被马吃掉的次数If(int pM&int qN)调用get_mincover(chess c)函数，求出极小满覆盖的一个解结束YNNYNY1.2主程序流程： Y 主函数void main( )调用get_attact( )函数调用get_mincover( chess c)函数调用get_horse(chess c)函数调用to_attact(int i,int j)函数1.3模块调用关系：四、详细设计1.1数据类型：马的位置为字符型二维数组：char cover100100马被吃掉的次数为整型二维数组：int attact1001001.2每个操作的代码：1.2.1 get_attact( )void chess:get_attact() /计算每个位置被马吃掉的次数 for(int i=0;iM;i+) for(int j=0;j=0&j-2=0) attacti-1j-2+;if(i-1=0&j+2=0&j-1=0) attacti-2j-1+;if(i-2=0&j+1N) attacti-2j+1+;if(i+1=0) attacti+1j-2+;if(i+1M&j+2N) attacti+1j+2+;if(i+2=0) attacti+2j-1+;if(i+2M&j+1N) attacti+2j+1+; 1.2.2 get_horse(chess c)void chess:get_horse(chess c) / 计算极小满覆盖 int max=attact00; int max_i=0,max_j=0;for(int i=0;iM;i+) for (int j=0;jmax) max=attactij;max_i=i;max_j=j; if(attactmax_imax_j=0) covermax_imax_j=*;attactmax_imax_j=-1;coutendl;cout此步马的位置是:(N*max_i+max_j)endl; cout=0 & max_j-2=0 ) attactmax_i-1max_j-2 =-1;int i = max_i-1;int j = max_j-2;c.to_attact(i,j);if(max_i-2=0 & max_j-1=0) attactmax_i-2max_j-1 =-1;int i=max_i-2;int j=max_j-1;c.to_attact(i,j);if(max_i+1= 0) attactmax_i+1max_j-2 =-1;int i=max_i+1;int j=max_j-2;c.to_attact(i,j);if(max_i+2=0) attactmax_i+2max_j-1 =-1;int i=max_i+2;int j=max_j-1;c.to_attact(i,j);if(max_i-1=0 & max_j+2=0 & max_j+1N) attactmax_i-2max_j+1=-1;int i=max_i-2;int j=max_j+1;c.to_attact(i,j);if(max_i+1M & max_j+2N) attactmax_i+1max_j+2 =-1;int i=max_i+1;int j=max_j+2;c.to_attact(i,j);if(max_i+2M & max_j+1N) attactmax_i+2max_j+1 =-1;int i=max_i+2;int j=max_j+1;c.to_attact(i,j);cout这次的覆盖情况endl;cout_endl;for(int i2=0;i2M;i2+)for(int j2=0;j2N;j2+) coutsetiosflags(ios:right)setw(0) setw(1)coveri2j2setw(0)|;/输出的为每次的覆盖情况；coutendl;cout_endl;cout每个位置被吃的次数:endl;for(int i3=0;i3M;i3+)for(int j3=0;j3N;j3+) coutsetiosflags(ios:right)setw(2)attacti3j3setw(1) ; /输出的为每次每个位置被吃的几率；cout=0&b-2=0&attacta-1b-2!=-1&attacta-1b-2!=0) attacta-1b-2-;if(a-2=0&b-1=0&attacta-2b-1!=-1 & attacta-2b-1!=0) attacta-2b-1-;if(a+1=0 & attacta+1b-2!=-1 & attacta+1b-2!=0) attacta+1b-2-;if(a+2=0&attacta+2b-1!=-1& attacta+2b-1!=0) attacta+2b-1-;if(a-1=0&b+2=0&b+1N & attacta-2b+1!=-1 & attacta-2b+1!=0)attacta-2b+1-;if(a+1M & b+2N & attacta+1b+2!=-1 & attacta+1b+2!=0) attacta+1b+2-;if(a+2M & b+1N & attacta+2b+1!=-1 & attacta+2b+1!=0) attacta+2b+1-; 1.2.4 get_mincover(chess c)void chess:get_mincover(chess c) int max_attact = 0;while(max_attact !=-1) c.get_horse(c); /循环计算最小覆盖；max_attact =-1.5;/中间变量;判断是否已完成最小覆盖的计算；for(int i=0;iM;i+) for(int j=0;j=max_attact) max_attact=attactij; 1.3主程序的代码：void main() cout请输入棋盘的行数M,列数NMN; cout棋盘的布局是:endl;int k=0; cout_endl; for(int i=0;iM;i+) for(int j=0;jN;j+) coutsetiosflags(ios:right) setw(1) setw(2)k setw(1) setw(1)|; k+; coutendl; cout_endl; chess c;c.get_attact( ); for(int p=0;pM;p+) for(int q=0;qN;q+)coutattactpq ; coutendl; c.get_mincover(c); coutendl;1.4函数调用关系图：主函数void main( )调用get_attact( )函数调用get_mincover( chess c)函数调用get_horse(chess c)函数调用to_attact(int i,int j)函数五、编码与调试分析1.1遇到的问题及解决办法： 我想要达到程序能够方便的移植到其他规模的棋盘上，此处用到二维数组，将二维数组的长度限制为100，定义整型变量M和N为全局变量，M为棋盘的行数，N为棋盘的列数，在主函数中输入M和N.int M,N;char cover100100;int attact100100; 主函数中cout请输入棋盘的行数M,列数NMN;六、使用说明 操作步骤：有键盘输入棋盘的行数M，列数N，按任意键继续，直到出现 “Press any key to continue” ，程序运行结束。七、测试结果 (1) (2)(3) (4) (5) (6) (7) (8)一直运行下去直到放置第18个马时，此时棋盘达到了极小满覆盖的情况。（9） （10）因此，图（6）为8*8棋盘的马的极小满覆盖的一个解。八、课程设计心得体会 这次的马的极小满覆盖课程设计我用了三周的时间，在这次课程设计中， 我学到了很多。 从开始学习数据结构与算法以来，我就一直不明白它与C+语言的区别和 联系，通过这次课程设计，我明白了数据结构与算法是一种思想，一种构架，是编写C+语言的前提，有了这种思想和构架后才能编写C+语言，最后是上机运行。 在课程设计中过程中通过独立解决问题，首先分析课设题目中涉及到的数据类型，在我们学习的数据结构与算法中找到相应的知识，根据数据类型设计数据节点类型，然后根据课设题目的主要任务，设计出程序大体轮廓（包括子函数和主函数），然后对每个子函数进行大体设计，过程中错误在所难免，所以要经过仔细探索，对每个函数进行改进。程序基本完成后，目的虽然达到，但是程序是否完善，还需运行测试多次，如有发现，应该对其进行改善，当然要在力所能及的前提下。 原本一直认为一个程序写的简单易懂就是好程序，课程设计之后我明白了，一个程序的好坏更重要的是要考虑到时间复杂度和空间复杂度。一个好的程序一定要选择好的结构组成，通过一系列的修改，使之时间复杂度和空间复杂度达到 最小。这样才能大大增加机器的工作效率。 还有一个体会就是在遇到不懂的地方可以参考课本也可以去图书馆查阅书籍或请教老师，当然，主要的思路有了也就简