完整版數(shù)據(jù)結(jié)構(gòu)馬踏棋盤

1、實(shí)驗(yàn)二：棧和隊(duì)列及其應(yīng)用題目：馬踏棋盤班級： 姓名： 學(xué)號：1、 問題描述設(shè)計(jì)一個國際象棋的馬踏遍棋盤的演示程序.2、 根本要求將馬隨機(jī)放在國際象棋的8*8的棋盤Board88的某個方格中,馬按走棋規(guī)那么進(jìn)行移動.要求每個方格只進(jìn)入一次,走遍棋盤上全部64個方格.編制非遞歸程序,求出馬的行走路線,并按求出的行走路線,將數(shù)字2.2, ,64依次填入一個8*8的方陣,輸出之.3、 概要設(shè)計(jì)1,定義頭文件和預(yù)定義#include#define MAXSIZE 100#define N 82 .起始坐標(biāo)函數(shù)：void InitLocation(int xi,int yi);3 .探尋路徑函數(shù)：int

2、TryPath(int i,int j);4 .輸出路徑函數(shù)：void Display();5 .主程序：void main();4、 詳細(xì)設(shè)計(jì)1 .函數(shù)聲明void InitLocation(int xi,int yi); /int TryPath(int i,int j);/void Display();/2.起始坐標(biāo)函數(shù)模塊void InitLocation(int xi,int yi)(int x,y;/馬兒在棋盤上的起始位置坐標(biāo) 馬兒每個方向進(jìn)行嘗試,直到 試完整個棋盤輸出馬兒行走的路徑定義棋盤的橫縱坐標(biāo)變量top+;/stacktop.i=xi;/stacktop.j=yi;/st

3、acktop.director=-1; / boardxiyi=top+1; / x=stacktop.i;/y=stacktop.j;/if(TryPath(x,y) /Display.；/elseprintf(無解) 3.探尋路徑函數(shù)模塊 int TryPath(int i,int j) int find,director,number,min;int i1,j1,h,k,s;/int a8,b18,b28,d8; while(top-1)/for(h=0;h=0&i=0&j8) /如果找到下一位置for(k=0;k=0&i1=0&j18)/number+;/如果找到下一位置 記錄條數(shù)ah

4、=number;/將條數(shù)存入數(shù)組a8for(h=0;h8;h+)/根據(jù)可行路徑條數(shù)小到大按下表排序 放入數(shù)組d8中(min=9;for(k=0;kak) (min=ak;dh=k; / s=k; as=9;將下表存入數(shù)組d8中director=stacktop.director;if(top=63)return (1);find=0;/如果走完整個棋盤返回1for(h=director+1;h=0&i=0&j8) 如果找到下一位置( find=1; / break;表示找到下一個位置)if(find=1) /如果找到下一個位置進(jìn)棧(存儲棧結(jié)點(diǎn)的方向棧指針前移進(jìn)棧重新初始化下一棧結(jié)點(diǎn)的嘗試標(biāo)記棋

5、盤否那么退棧stacktop.director=director; / top+;/stacktop.i=i; stacktop.j=j; stacktop.director=-1; / 方向 boardij=top+1; / ) else/(boardstacktop.istacktop.j=0; /去除棋盤的標(biāo)記top-;/棧指針前移退棧) ) return (0); ) 4.輸出路徑函數(shù)模塊 void Display. ( int i,j; for(i=0;iN;i+) ( for(j=0;jN;j+) printf(t%d ,boardij); /輸出馬兒在棋盤上走過的路徑 print

6、f(nn); ) printf(n);五、測試數(shù)據(jù)及測試結(jié)果測試數(shù)據(jù)：x=2,y=3測試結(jié)果：六、實(shí)驗(yàn)環(huán)境C-Free七、源程序代碼#include#define MAXSIZE 100#define N 8int board88;/定義棋盤int Htry18=1,-1,-2,2,2,1,-1,-2;/*存儲馬各個出口位置相對當(dāng)前位置行下標(biāo)的增量數(shù)組*/int Htry28=2,-2,1,1,-1,-2,2,-1;/*存儲馬各個出口位置相對當(dāng)前位置列下標(biāo)的增量數(shù)組*/struct Stack /定義棧類型int i;/行坐標(biāo)int j;/列坐標(biāo)int director; / stackMAX

7、SIZE;/存儲方向定義一個棧數(shù)組void InitLocation(int xi,int yi); / int TryPath(int i,int j);/完整個棋盤void Display.；/馬兒在棋盤上的起始位置坐標(biāo) 馬兒每個方向進(jìn)行嘗試,直到試輸出馬兒行走的路徑int top=-1;/棧指針定義棋盤的橫縱坐標(biāo)變量棧指針指向第一個棧首將起始位置的橫坐標(biāo)進(jìn)棧將起始位置的縱坐標(biāo)進(jìn)棧將起始位置的嘗試方向賦初值標(biāo)記棋盤將起始位置的橫坐標(biāo)賦給棋盤的橫坐標(biāo)將起始位置的縱坐標(biāo)賦給棋盤的縱坐標(biāo)調(diào)用馬兒探尋函數(shù),如果馬兒探尋整個棋盤返輸出馬兒的行走路徑定義幾個臨時變量定義幾個臨時變量 定義幾個臨時數(shù)組

8、棧不空時循環(huán)void InitLocation(int xi,int yi) int x,y;/top+;/stacktop.i=xi;/stacktop.j=yi;/stacktop.director=-1; / boardxiyi=top+1; / x=stacktop.i;/y=stacktop.j;/if(TryPath(x,y)/回1否那么返回0Display();/else printf(無解)int TryPath(int i,int j)int find,director,number,min; /int i1,j1,h,k,s;/int a8,b18,b28,d8; /whi

9、le(top-1)/for(h=0;h=0&i=0&j8) /如果找到下一位置(for(k=0;k=0&i1=0&j18)/ number+; ah=number;for(h=0;h8;h+)/入數(shù)組d8中(min=9;for(k=0;kak) (min=ak;如果找到下一位置/記錄條數(shù)/將條數(shù)存入數(shù)組a8中根據(jù)可行路徑條數(shù)小到大按下表排序放dh=k; /將下表存入數(shù)組d8中s=k; as=9;director=stacktop.director;if(top=63)/return (1);find=0;/for(h=director+1;h=0&i=0&j8)/ 如果找到下一位置find=1

10、; / 表示找到下一個位置 break;)if(find=1) /如果找到下一個位置進(jìn)棧stacktop.director=director; / top+;/stacktop.i=i; stacktop.j=j; stacktop.director=-1; /向boardij=top+1; /) else/ boardstacktop.istacktop.j=0; /去除棋盤的標(biāo)記top-;/棧指針前移退棧)return (0);void Display()(int i,j;for(i=0;iN;i+)(for(j=0;jN;j+)printf(t%d ,boardij); /輸出馬兒在棋盤上走過的路徑printf(nn);printf(n);int main()(int i,j;int x,y;for(i=0;iN;i+)/初始化棋盤for(j=0;jN;j+)boardij=0;for(;)(pri