《實驗報告 馬踏棋盤》由會員分享,可在線閱讀,更多相關(guā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á)到的功能:讓馬從任意起點出發(fā)都能夠遍歷整個8*8的棋盤。(4)測試數(shù)據(jù),包括正確輸入及輸出結(jié)果和含有錯誤的輸入及其輸出結(jié)果。數(shù)據(jù)可以任定,只要1=x,y=8就可以了。正確的輸出結(jié)果為一個二維數(shù)組,每個元素的值表示馬行走的第幾步,若輸入有錯,則程序會顯示:“輸入有誤!請重
2、新輸入”并且要求用戶重新輸入數(shù)據(jù),直至輸入正確為止。2 概要設(shè)計(1) 、位置的存儲表示方式(2) typedefstruct intx; inty; intfrom;Point;(2) 、棧的存儲方式#defineSTACKSIZE70#defineSTACKINCREASE10typedefstructStack Point*top; Point*base;intstacksize;(1)、設(shè)定棧的抽象數(shù)據(jù)類型定義:ADTStack數(shù)據(jù)對象:D=ai|aiElemSet,i=1,2,n,n0 數(shù)據(jù)關(guān)系:R1=|ai-1,aiD,i=2,n 約定an端為棧頂,ai端為棧頂。 基本操作:Ini
3、tStack(&s)操作結(jié)果:構(gòu)造一個空棧s,DestroyStack(&s)初始條件:棧s已存在。 操作結(jié)果:棧s被銷毀。 ClearStack(&s)初始條件:棧s已存在。 操作結(jié)果:棧s清為空棧。 StackEmpty(&s)初始條件:棧s已存在。 操作結(jié)果:若棧s為空棧,則返回TRUE,否則返回FALSE。 StackLength(s); 初始條件:棧s存在。操作結(jié)果:返回s的元素個數(shù),即棧的長度。GetTop(s,&e);初始條件:棧s已存在且非空。 操作結(jié)果:用e返回s的棧頂元素。Push(&s,e) 初始條件:棧s已存在。操作結(jié)果:插入元素e為新的棧頂元素。Pop(&s,&e)初
4、始條件:棧s存在且非空。操作結(jié)果:刪除棧頂元素,并用e返回。stackTraverse(s,visit() 初始條件:棧s存在且非空。操作結(jié)果:從棧底到棧頂依次對s的每個元素調(diào)用visit()。一旦visit()失敗, 則 操作失敗。ADTStack本程序包含模塊:1、 主程序模塊:voidmain()定義變量;接受命令;處理命令;退出;2、 起始坐標(biāo)函數(shù)模塊馬兒在棋盤上的起始位置;3、 探尋路徑函數(shù)模塊馬兒每個方向進(jìn)行嘗試,直到試完整個棋盤;4、 輸出路徑函數(shù)模塊輸出馬兒行走的路徑;3 詳細(xì)設(shè)計1.函數(shù)聲明Void InitLocation(int xi,intyi);/馬兒在棋盤上的起始位
5、置標(biāo)intTryPath(inti,intj);/馬兒每個方向進(jìn)行嘗試,直到試完整個棋盤voidDisplay();/輸出馬兒行走的路徑2.起始坐標(biāo)函數(shù)模塊voidInitLocation(intxi,intyi)intx,y;/定義棋盤的橫縱坐標(biāo)變量top+;/棧指針指向第一個棧首stacktop.i=xi;/將起始位置的橫坐標(biāo)進(jìn)棧stacktop.j=yi;/將起始位置的縱坐標(biāo)進(jìn)棧stacktop.director=-1;/將起始位置的嘗試方向賦初值boardxiyi=top+1;/標(biāo)記棋盤x=stacktop.i;/將起始位置的橫坐標(biāo)賦給棋盤的橫標(biāo)y=stacktop.j;/將起始位置的
6、縱坐標(biāo)賦給棋盤的縱坐標(biāo)if(TryPath(x,y)/調(diào)用馬兒探尋函數(shù),如果馬兒探尋整個棋盤返回1否則0Display();/輸出馬兒的行走路徑elseprintf(無解);3.探尋路徑函數(shù)模塊intTryPath(inti,intj)intfind,director,number,min;/定義幾個臨時變量inti1,j1,h,k,s;/定義幾個臨時變量inta8,b18,b28,d8;/定義幾個臨時數(shù)組while(top-1)/棧不空時循環(huán) for(h=0;h=0&i=0&j8)/如果找到下一位置for(k=0;k=0&i1=0&j18)/如果找到下一位置number+;/記錄條數(shù) ah=
7、number;/將條數(shù)存入數(shù)組a8中 for(h=0;h8;h+)/根據(jù)可行路徑條數(shù)小到大按下表排序放d8中 min=9;for(k=0;kak)min=ak;dh=k;/將下表存入數(shù)組d8中s=k; as=9;director=stacktop.director;if(top=63)/如果走完整個棋盤返回1return(1);find=0;/表示沒有找到下一個位置for(h=director+1;h=0&i=0&j8)/如果找到下一位置find=1;/表示找到下一個位置Break;if(find=1)/如果找到下一個位置進(jìn)棧stacktop.director=director;/存儲棧結(jié)點的
8、方向top+;/棧指針前移進(jìn)棧stacktop.i=i;stacktop.j=j;stacktop.director=-1;/重新初始化下一棧結(jié)點的嘗試方向boardij=top+1;/標(biāo)記棋盤 else/否則退棧 boardstacktop.istacktop.j=0;/清除棋盤的標(biāo)記top-;/棧指針前移退棧 return(0);4.輸出路徑函數(shù)模塊voidDisplay()inti,j;for(i=0;iN;i+)for(j=0;jN;j+)printf(t%d,boardij);/輸出馬兒在棋盤上走過的路徑printf(nn);printf(n);四、測試數(shù)據(jù)及測試結(jié)果測試數(shù)據(jù):x=2
9、,y=3測試結(jié)果如下:5 原程序代碼#include#defineMAXSIZE100#defineN8intboard88;/定義棋盤intHtry18=1,-1,-2,2,2,1,-1,-2;/*存儲馬各個出口位置相對當(dāng)前位置行下標(biāo)的*/intHtry28=2,-2,1,1,-1,-2,2,-1;/*存儲馬各個出口位置相對當(dāng)前位置列下標(biāo)的增量數(shù)組*/structStack/定義棧類型inti;/行坐標(biāo)intj;/列坐標(biāo)intdirector;/存儲方向stackMAXSIZE;/定義一個棧數(shù)組inttop=-1;/棧指針voidInitLocation(intxi,intyi);/馬兒在棋
10、盤上的起始位置坐標(biāo)intTryPath(inti,intj);/馬兒每個方向進(jìn)行嘗試,直到試完整個棋盤voidDisplay();/輸出馬兒行走的路徑voidInitLocation(intxi,intyi)intx,y;/定義棋盤的橫縱坐標(biāo)變量top+;/棧指針指向第一個棧首stacktop.i=xi;/將起始位置的橫坐標(biāo)進(jìn)棧stacktop.j=yi;/將起始位置的縱坐標(biāo)進(jìn)棧stacktop.director=-1;/將起始位置的嘗試方向賦初值boardxiyi=top+1;/標(biāo)記棋盤x=stacktop.i;/將起始位置的橫坐標(biāo)賦給棋盤的橫坐標(biāo)y=stacktop.j;/將起始位置的縱坐
11、標(biāo)賦給棋盤的縱坐標(biāo)if(TryPath(x,y)/調(diào)用馬兒探尋函數(shù),如果馬兒探尋整個棋盤返回1否則返回0Display();/輸出馬兒的行走路徑elseprintf(無解);intTryPath(inti,intj)intfind,director,number,min;/定義幾個臨時變量inti1,j1,h,k,s;/定義幾個臨時變量inta8,b18,b28,d8;/定義幾個臨時數(shù)組while(top-1)/棧不空時循環(huán)for(h=0;h=0&i=0&j8)/如果找到下一位置 for(k=0;k=0&i1=0&j18) /如果找到下一位置number+;/記錄條數(shù)ah=number;/將條
12、數(shù)存入數(shù)組a8中for(h=0;h8;h+)/根據(jù)可行路徑條數(shù)小到大按下表排序放入數(shù)組d8中min=9;for(k=0;kak) min=ak;dh=k;/將下表存入數(shù)組d8中s=k; as=9;director=stacktop.director;if(top=63)/如果走完整個棋盤返回1return(1);find=0;/表示沒有找到下一個位置for(h=director+1;h=0&i=0&j8)/如果找到下一位置 find=1;/表示找到下一個位置 break; if(find=1)/如果找到下一個位置進(jìn)棧 stacktop.director=director;/存儲棧結(jié)點的方向to
13、p+;/棧指針前移進(jìn)棧stacktop.i=i;stacktop.j=j;stacktop.director=-1;/重新初始化下一棧結(jié)點的嘗試方向boardij=top+1;/標(biāo)記棋盤else/否則退棧boardstacktop.istacktop.j=0;/清除棋盤的標(biāo)記top-;/棧指針前移退棧 return(0);voidDisplay() inti,j; for(i=0;iN;i+) for(j=0;jN;j+)printf(t%d,boardij);/輸出馬兒在棋盤上走過的路徑printf(nn); printf(n);intmain()inti,j;intx,y;for(i=0;iN;i+)/初始化棋盤for(j=0;jN;j+)boardij=0;for(;)printf(Pleaseinputimportpoint(1=x=8and1=y=1&x=1&y=8)break;printf(Yourinputisworng!n);printf(beginwith%dboard:nn,8*(x-1)+y);InitLocation(x-1,y-1);/調(diào)用起始坐標(biāo)函數(shù)