数据结构课程设计马的满覆盖Word格式.docx
《数据结构课程设计马的满覆盖Word格式.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计马的满覆盖Word格式.docx（8页珍藏版）》请在冰点文库上搜索。
用一个二维数组attack[max_i][max_j]来存储在棋盘上全部都放上马时不考虑蹩腿的情况下各个位置上的马受其他马攻击的次数；
用另一字符型的二维数组cover[max_i][max_j]来表示该坐标下的马的状态:
’N’表示该位置上的马既没有，也不能被已放的马吃掉，’Y’表示该位位置上的马能被已放的马吃掉，’*’表示该位置已放马。
找出当前受攻击次数最高的，放到棋盘上，考虑蹩腿后在对棋盘上其他马受攻击的情况做一次调整，同时调整cover数组中的字符，再找出受攻击次数最高的再放，就这样一次下去直到其盘上剩余的位置都能被已放的马吃掉为止。
在程序中写了一个chess类其中的具体的数据成员和成员函数如下表所示:
类型
名称
作用
数据成员
intattack[max_h][max_s]
记录被攻击的次数
charcover[max_h][max_s]
表示棋盘上个位置当前状态
intmax
记录找出的攻击次数最高的次数
intmax_i,max_j
记录找出攻击次数最高的马的位置
成员函数
chess（）
构造函数初始化
voidget_attack（）
得到攻击次数数组
voidto_attack（inta,intb）
放置一个马都后得出受攻击次数的变化
voidget_horse（）
得到被攻击次数最多的马
voidget_cover（）
记录当前棋盘上状态
voidput_horse（）
放被攻击次数最高的马
voidprint_out（）
最后输出所得结果
程序部分代码及细节实现：
程序部分代码及细节实现如下：
chess:
:
chess（）//构造函数的实现
{
for（inti=0;
i<
max_s;
i++）{
for（intj=0;
j<
j++）{
cover[i][j]='
N'
;
//棋盘初始状态都是没放马
attack[i][j]=0;
//受攻击次数都为0
}
}
max_i=0;
//受攻击最多的马坐标（0，0）
max_j=0;
}
voidchess:
get_attack（）{//受攻击次数数组的实现
max_h;
i++）{
if（i-1>
=0&
&
j-2>
=0）{attack[i-1][j-2]++;
}//将当前位置的-1.-2方向的位置被吃次数加1；
j+2<
max_s）{attack[i-1][j+2]++;
}//将当前位置的-1.2方向的位置被吃次数加1；
if（i-2>
j-1>
=0）{attack[i-2][j-1]++;
}//将当前位置的-2.-1方向的位置被吃次数加1；
=0&
j+1<
max_s）{attack[i-2][j+1]++;
}//将当前位置的-2.1方向的位置被吃次数加1；
if（i+1<
max_h&
=0）{attack[i+1][j-2]++;
}//将当前位置的1.-2方向的位置被吃次数加1；
if（i+1<
j+2<
max_s）{attack[i+1][j+2]++;
}//将当前位置的1.2方向的位置被吃次数加1；
if（i+2<
j-1>
=0）{attack[i+2][j-1]++;
}//将当前位置的2.-1方向的位置被吃次数加1；
if（i+2<
j+1<
max_s）{attack[i+2][j+1]++;
}//将当前位置的2.1方向的位置被吃次数加1；
//坐标（a,b）上放马对攻击次数的影响
voidchess:
to_attack（inta,intb）{
if（a-1>
=0&
attack[a-1][b]!
=0）//其蹩（a-1,b）位置上的马吃（a+1,b-1）和（a+1,b+1）上的马
{if（a+1<
max_h&
b-1>
=0&
cover[a+1][b-1]=='
）attack[a+1][b-1]--;
if（a+1<
b+1<
max_s&
cover[a+1][b+1]=='
）attack[a+1][b+1]--;
if（a+1<
attack[a+1][b]!
=0）{
if（a-1>
cover[a-1][b-1]=='
）attack[a-1][b-1]--;
cover[a-1][b+1]=='
）attack[a-1][b+1]--;
if（b+1<
attack[a][b+1]!
if（a+1<
b-1>
if（b-1>
attack[a][b-1]!
if（a+1>
get_horse（）{//得到攻击次数最高的马的函数实现
max=attack[0][0];
//用Max暂时储存被吃次数最多的位置上被吃次数，中间变量
for（inti=0;
if（attack[i][j]>
max）{
max=attack[i][j];
max_i=i;
max_j=j;
}
}
put_horse（）//放马的实现
{
if（attack[max_i][max_j]>
=0）
{//用数组Attack[Max_i][Max_j]储存被吃几率最大位置上的被吃次数
cover[max_i][max_j]='
*'
//在覆盖数组中标志此位置为已放马.
attack[max_i][max_j]=0;
//不能忘记将该位置也标记已放马。
if（max_i-1>
max_j-2>
cover[max_i][max_j-1]!
='
）{
cover[max_i-1][max_j-2]='
Y'
attack[max_i-1][max_j-2]=0;
}if（max_i-1>
max_j+2<
cover[max_i][max_j+1]!
）{
cover[max_i-1][max_j+2]='
attack[max_i-1][max_j+2]=0;
if（max_i-2>
max_j+1<
cover[max_i-1][max_j]!
cover[max_i-2][max_j+1]='
attack[max_i-2][max_j+1]=0;
max_j-1>
0&
if（max_i+1<
cover[max_i+1][max_j-2]='
attack[max_i+1][max_j-2]=0;
if（max_i+1<
max_j+2<
cover[max_i+1][max_j+2]='
attack[max_i+1][max_j+2]=0;
if（max_i+2<
max_j-1>
cover[max_i+1][max_j]!
cover[max_i+2][max_j-1]='
attack[max_i+2][max_j-1]=0;
if（max_i+2<
cover[max_i+2][max_j+1]='
attack[max_i+2][max_j+1]=0;
to_attack（max_i,max_j）;
get_cover（）//得到最小覆盖函数的实现
while
（1）{
do{
get_horse（）;
if（max!
cover[max_i][max_j]!
）
return;
}while（cover[max_i][max_j]!
）;
put_horse（）;
print_out（）//输出棋盘函数的实现
cout<
<
cover[i][j]<
"
"
cout<
endl;
//主函数的实现
Voidmain（）{
Chessc;
//定义一个对象
c.get_attack（）;
//生成攻击表格
c.get_cover（）;
//完成极小覆盖的求解
c.print_out（）;
//输出棋盘
调试结果：
总结：
本题目的设计历经多次曲折，但是最终由于时间紧迫，各种实现上的小细节没有去美化。
使得程序看起来不是十分明了，界面没有什么美观可言，算是比较失败。
主要原因是由于初始没有考虑蹩腿的问题，导致用错了思路，最后不得不重新整理思路寻找新的方法；
教训：
要纵观大局，不能忽视一些重要的细节，要考虑全面后再着手，大方向不能有一点的偏差！
升级会员 