《實(shí)驗(yàn)報告 馬踏棋盤》由會員分享，可在線閱讀，更多相關(guān)《實(shí)驗(yàn)報告 馬踏棋盤（8頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、2.4題 馬踏棋盤
題目：設(shè)計一個國際象棋的馬踏棋盤的演示程序
班級： 姓名： 學(xué)號： 完成日期：
1． 需求分析
（1）?輸入的形式和輸入值的范圍：輸入馬的初始行坐標(biāo)X和列坐標(biāo)Y，
X和Y的范圍都是[1,8]。?
（2）?輸出形式：?
以數(shù)組下表的形式輸入，i為行標(biāo)，j為列標(biāo)，用空格符號隔開。?以棋盤形式輸出，每一格打印馬走的步數(shù)，這種方式比較直觀?
（3）?程序所能達(dá)到的功能：讓馬從任意起點(diǎn)出發(fā)都能夠遍歷整個8*8的
棋盤。?
（4）?測試數(shù)據(jù)，包括正確輸入及輸出結(jié)果和含有錯誤的輸入及其輸出結(jié)
果。數(shù)據(jù)可以任定，只要1<=x,y<=8就可以了。?
正確的輸出結(jié)果為一
2、個二維數(shù)組，每個元素的值表示馬行走的第幾步，若輸入有錯，則程序會顯示：“輸入有誤！請重新輸入……”并且要求用戶重新輸入數(shù)據(jù)，直至輸入正確為止。
2． 概要設(shè)計
（1） 、位置的存儲表示方式
（2） ?typedef?struct??????{?
??????? ?int?x;?????
int?y;??????
?? ?int?from;
?}Point;??
（2） 、棧的存儲方式?
#define?STACKSIZE?70?
#define?STACKINCREASE?10?
typedef?struct?Stack?{?
??????? Point?*top
3、;????
Point?*base;?????
???int?stacksize;
?};
（1）、設(shè)定棧的抽象數(shù)據(jù)類型定義：??ADT?Stack?{?
?????數(shù)據(jù)對象：D=｛ai?|?ai∈ElemSet,i=1,2,?,n,n≥0｝???
??? 數(shù)據(jù)關(guān)系：R1={|ai-1,?ai∈D,i=2,?,n}???????????????
? 約定an端為棧頂，ai端為棧頂。??????
基本操作：?
???? ?InitStack(&s)?
????操作結(jié)果：構(gòu)造一個空棧s，??????????
DestroyStack(&s)??
4、????????
初始條件：棧s已存在。?????????
? 操作結(jié)果：棧s被銷毀。????????????
ClearStack(&s)?
?????????初始條件：棧s已存在。??????????
操作結(jié)果：棧s清為空棧。?????????????
? StackEmpty(&s)?
?????????初始條件：棧s已存在。?
??? 操作結(jié)果：若棧s為空棧，則返回TRUE，否則返回FALSE。????????????
?? StackLength(s);?????????
? 初始條件：棧s存在。?
?????????操作結(jié)果：返回s
5、的元素個數(shù)，即棧的長度。?????????
????GetTop?(s,&e);?
?????????初始條件：棧s已存在且非空。?????????
? 操作結(jié)果：用e返回s的棧頂元素。???????????
???Push(&s,e)?
初始條件：棧s已存在。?
????????操作結(jié)果：插入元素e為新的棧頂元素。???????
???Pop(&s,&e)?
????????初始條件：棧s存在且非空。?
????????操作結(jié)果：刪除棧頂元素，并用e返回。????????????
?stackTraverse(s,visit())??????
??初
6、始條件：棧s存在且非空。?
???????操作結(jié)果：從棧底到棧頂依次對s的每個元素調(diào)用visit()。一旦visit()失敗， 則 操作失敗。?
}ADT?Stack
本程序包含模塊：?
1、 主程序模塊：void?main(){定義變量；接受命令；處理命令；退出；}
2、 起始坐標(biāo)函數(shù)模塊——馬兒在棋盤上的起始位置；?
3、 探尋路徑函數(shù)模塊——馬兒每個方向進(jìn)行嘗試，直到試完整個棋盤；
4、 輸出路徑函數(shù)模塊——輸出馬兒行走的路徑；??
3． 詳細(xì)設(shè)計
1.函數(shù)聲明?
Void InitLocation(int xi,int?yi);?//馬兒在棋盤上的起始位置標(biāo)?i
7、nt?TryPath(int?i,int?j);??????????//馬兒每個方向進(jìn)行嘗試，直到試完整個棋盤?
void?Display();????????????????????//輸出馬兒行走的路徑?2.?起始坐標(biāo)函數(shù)模塊?
void?InitLocation(int?xi,int?yi)?{?
?int?x,y;????????????????//定義棋盤的橫縱坐標(biāo)變量
?top++;??????????????????//棧指針指向第一個棧首??
stack[top].i=xi;????????//將起始位置的橫坐標(biāo)進(jìn)棧??
stack[top].j=yi;??????
8、??//將起始位置的縱坐標(biāo)進(jìn)棧?
?stack[top].director=-1;?//將起始位置的嘗試方向賦初值??
board[xi][yi]=top+1;????//標(biāo)記棋盤?
?x=stack[top].i;?????????//將起始位置的橫坐標(biāo)賦給棋盤的橫標(biāo)??
y=stack[top].j;?????????//將起始位置的縱坐標(biāo)賦給棋盤的縱坐標(biāo)?
if(TryPath(x,y))???????//調(diào)用馬兒探尋函數(shù)，如果馬兒探尋整個棋盤返回1否則0?
Display();?????????//輸出馬兒的行走路徑??else????????????????????
?
9、printf("無解");?????
?}?
?3.?探尋路徑函數(shù)模塊
int?TryPath(int?i,int?j)?{?
?int?find,director,number,min;??//定義幾個臨時變量?
int?i1,j1,h,k,s;??????????????//定義幾個臨時變量??
int?a[8],b1[8],b2[8],d[8];????//定義幾個臨時數(shù)組??
while(top>-1)?????????????????//棧不空時循環(huán)?
?{?
for(h=0;h<8;h++)????//用數(shù)組a[8]記錄當(dāng)前位置的下一個位置的可行路徑的條數(shù)?
10、?? {???
number=0;?
????? ?i=stack[top].i+Htry1[h];??????
j=stack[top].j+Htry2[h];?
b1[h]=i;???????
b2[h]=j;?
??if(board[i][j]==0&&i>=0&&i<8&&j>=0&&j<8)????//如果找到下一位置?
{???
????for(k=0;k<8;k++)???
? ?{????
i1=b1[h]+Htry1[k];
j1=b2[h]+Htry2[k];????????
?if(board[i1][j1]==0&&i1>=0&&
11、i1<8&&j1>=0&&j1<8)??????????????????????????????????????????????? //如果找到下一位置?
??????????number++;??????????????//記錄條數(shù)????
}?
???a[h]=number;???????????????????//將條數(shù)存入數(shù)組a[8]中?
?}???
}?
for(h=0;h<8;h++)?????//根據(jù)可行路徑條數(shù)小到大按下表排序放d[8]中
{????
min=9;?????
for(k=0;k<8;k++)
12、??????
if(min>a[k])??????
{?????
min=a[k];?
???????? d[h]=k;????//將下表存入數(shù)組d[8]中?
????????????????s=k;?????
}?
??? ?a[s]=9;?
??}?
???????director=stack[top].director;?
?if(top>=63)?????????????????//如果走完整個棋盤返回1????
return?(1);?
??find=0;?????????????????????//表示沒有找到下一個位置??
?for(h=di
13、rector+1;h<8;h++)???//向八個方向進(jìn)行探尋??
?{????i=stack[top].i+Htry1[d[h]];?
??????j=stack[top].j+Htry2[d[h]];?
if(board[i][j]==0&&i>=0&&i<8&&j>=0&&j<8)?//如果找到下一位置?
?? ?{?????
find=1;???????//表示找到下一個位置?
Break;
}
}
if(find==1)??????????//如果找到下一個位置進(jìn)棧?
??{???
?stack[top].director=director;?//存儲棧結(jié)
14、點(diǎn)的方向???
?? top++;??????????????????????//棧指針前移進(jìn)棧???
? stack[top].i=i;??
?? stack[top].j=j;?
? ??stack[top].director=-1;????//重新初始化下一棧結(jié)點(diǎn)的嘗試方向?
?? ?board[i][j]=top+1;?????????//標(biāo)記棋盤?
??}
else???????????????????????????//否則退棧???
{????
board[stack[top].i][stack[top].j]=0;??//清除棋盤的標(biāo)記?
?? ?to
15、p--;?????????????????????//棧指針前移退棧?
?? }?
?}?
?return?(0);???
}?
?4.?輸出路徑函數(shù)模塊
void?Display()?
{?
?? int?i,j;?
???? for(i=0;i
16、果如下：
5． 原程序代碼
#include?
#define?MAXSIZE?100?
#define?N?8??
int?board[8][8];???????????//定義棋盤?
int?Htry1[8]={1,-1,-2,2,2,1,-1,-2};?
?/*存儲馬各個出口位置相對當(dāng)前位置行下標(biāo)的*/?
int?Htry2[8]={2,-2,1,1,-1,-2,2,-1};?
?????????????????????????/*存儲馬各個出口位置相對當(dāng)前位置列下標(biāo)的增量數(shù)組*/?
struct?Stack{??????????????//定義
17、棧類型???
?int?i;??????????????????//行坐標(biāo)??
int?j;??????????????????//列坐標(biāo)
?int?director;???????????//存儲方向
?}stack[MAXSIZE];???????????//定義一個棧數(shù)組
?int?top=-1;????????????????//棧指針
void?InitLocation(int?xi,int?yi);??//馬兒在棋盤上的起始位置坐標(biāo)?
int?TryPath(int?i,int?j);??????????//馬兒每個方向進(jìn)行嘗試，直到試完整個棋盤?
void?Dis
18、play();????????????????????//輸出馬兒行走的路徑
void?InitLocation(int?xi,int?yi)
?{?
?int?x,y;????????????????//定義棋盤的橫縱坐標(biāo)變量??
top++;??????????????????//棧指針指向第一個棧首?
?stack[top].i=xi;????????//將起始位置的橫坐標(biāo)進(jìn)棧??
stack[top].j=yi;????????//將起始位置的縱坐標(biāo)進(jìn)棧?
?stack[top].director=-1;?//將起始位置的嘗試方向賦初值??
board[xi][yi
19、]=top+1;????//標(biāo)記棋盤?
?x=stack[top].i;?????????//將起始位置的橫坐標(biāo)賦給棋盤的橫坐標(biāo)??
y=stack[top].j;?????????//將起始位置的縱坐標(biāo)賦給棋盤的縱坐標(biāo)?
?if(TryPath(x,y))??????//調(diào)用馬兒探尋函數(shù)，如果馬兒探尋整個棋盤返回1否則返回0?
??Display();?????????//輸出馬兒的行走路徑??
else????????????????????
?printf("無解");??????
}?
int?TryPath(int?i,int?j)?{?
?int?find,d
20、irector,number,min;??//定義幾個臨時變量?
int?i1,j1,h,k,s;??????????????//定義幾個臨時變量
??int?a[8],b1[8],b2[8],d[8];????//定義幾個臨時數(shù)組??
while(top>-1)?????????????????//棧不空時循環(huán)
{?
??for(h=0;h<8;h++)????//用數(shù)組a[8]記錄當(dāng)前位置的下一個位置的可行路徑的條數(shù)?
??{????
number=0;?
????? ?i=stack[top].i+Htry1[h];????
?? ?j=stack[top].j+Ht
21、ry2[h];??????
? b1[h]=i;???????
b2[h]=j;?
??????if(board[i][j]==0&&i>=0&&i<8&&j>=0&&j<8)????//如果找到下一位置?
??? {???
???? for(k=0;k<8;k++)
{???????
i1=b1[h]+Htry1[k];?
??????????j1=b2[h]+Htry2[k];?
????????if(board[i1][j1]==0&&i1>=0&&i1<8&&j1>=0&&j1<8)?????????????????????????????
22、?????????????????? //如果找到下一位置?
??????????number++;??????????????//記錄條數(shù)???
??}?
???a[h]=number;???????????????????//將條數(shù)存入數(shù)組a[8]中?
?}?
?}????
??for(h=0;h<8;h++)?????//根據(jù)可行路徑條數(shù)小到大按下表排序放
入數(shù)組d[8]中
{????
min=9;??????
?for(k=0;k<8;k++)??
??? ?If(min>a[
23、k])?????
? {?????
min=a[k];?
??????? ?d[h]=k;????//將下表存入數(shù)組d[8]中?
?????????????????s=k;?
}?
???? a[s]=9;?
}
director=stack[top].director;?????
??if(top>=63)?????????????????//如果走完整個棋盤返回1????
return?(1);?
??find=0;?????????????????????//表示沒有找到下一個位置???
for(h=director+1;h<8;h++)???//向
24、八個方向進(jìn)行探尋???
{????
i=stack[top].i+Htry1[d[h]];?
?????? j=stack[top].j+Htry2[d[h]];?
?? ?if(board[i][j]==0&&i>=0&&i<8&&j>=0&&j<8)?//如果找到下一位置??
? ?{???
? ?find=1;???????//表示找到下一個位置?????
break;?
}?
?}???
??if(find==1)??????????//如果找到下一個位置進(jìn)棧?
{????
stack[top].director=director;?//存
25、儲棧結(jié)點(diǎn)的方向????
?top++;??????????????????????//棧指針前移進(jìn)棧????
stack[top].i=i;???
?stack[top].j=j;?
? ??stack[top].director=-1;????//重新初始化下一棧結(jié)點(diǎn)的嘗試方向?
? ??board[i][j]=top+1;?????????//標(biāo)記棋盤?
??}?
??else???????????????????????????//否則退棧??
?{???
? board[stack[top].i][stack[top].j]=0;??//清除棋盤的標(biāo)記??
? ?t
26、op--;?????????????????????//棧指針前移退棧?
??}?
}?
return?(0);???
}?
void?Display()
?{?
?? int?i,j;?
for(i=0;i
27、,y;?
? for(i=0;i=1&&x<=8&&y>=1&&y<=8)break;??
?printf("Your?input?is?worng!!!\n");?
?}?
?printf("begin?with?%d?board:\n\n",?8*(x-1)+y);??InitLocation(x-1,y-1);??????//調(diào)用起始坐標(biāo)函數(shù)
?}
實(shí)驗(yàn)報告 馬踏棋盤
