實驗報告馬踏棋盤

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é)點的方向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);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;