數(shù)據(jù)結(jié)構(gòu)馬踏棋盤演示程序設(shè)計

.實驗二：棧和隊列及其應(yīng)用題目：馬踏棋盤班級： 姓名： 學(xué)號：一、 問題描述 設(shè)計一個國際象棋的馬踏遍棋盤的演示程序。二、 基本要求 將馬隨機(jī)放在國際象棋的8*8的棋盤Board88的某個方格中，馬按走棋規(guī)則進(jìn)行移動。要求每個方格只進(jìn)入一次，走遍棋盤上全部64個方格。編制非遞歸程序，求出馬的行走路線，并按求出的行走路線，將數(shù)字1,2，64依次填入一個8*8的方陣，輸出之。三、 概要設(shè)計1. 定義頭文件和預(yù)定義 #include#define MAXSIZE 100#define N 82. 起始坐標(biāo)函數(shù)：void InitLocation(int xi,int yi); 3. 探尋路徑函數(shù)：int TryPath(int i,int j); 4. 輸出路徑函數(shù)：void Display();5. 主程序：void main();四、 詳細(xì)設(shè)計1.函數(shù)聲明 void InitLocation(int xi,int yi); /馬兒在棋盤上的起始位置坐標(biāo)int 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+; /棧指針指向第一個棧首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; /將起始位置的縱坐標(biāo)賦給棋盤的縱坐標(biāo)if(TryPath(x,y) /調(diào)用馬兒探尋函數(shù)，如果馬兒探尋整個棋盤返回1否則返回0Display(); /輸出馬兒的行走路徑else printf(無解); 3. 探尋路徑函數(shù)模塊int TryPath(int i,int j)int find,director,number,min; /定義幾個臨時變量int i1,j1,h,k,s; /定義幾個臨時變量int a8,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; /將條數(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é)點(diǎn)的方向 top+; /棧指針前移進(jìn)棧stacktop.i=i;stacktop.j=j;stacktop.director=-1; /重新初始化下一棧結(jié)點(diǎn)的嘗試方向boardij=top+1; /標(biāo)記棋盤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); /輸出馬兒在棋盤上走過的路徑printf(nn);printf(n);五、測試數(shù)據(jù)及測試結(jié)果測試數(shù)據(jù)：x=2,y=3測試結(jié)果：六、實驗環(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; /存儲方向stackMAXSIZE; /定義一個棧數(shù)組int top=-1; /棧指針void InitLocation(int xi,int yi); /馬兒在棋盤上的起始位置坐標(biāo)int TryPath(int i,int j); /馬兒每個方向進(jìn)行嘗試，直到試完整個棋盤void Display(); /輸出馬兒行走的路徑void InitLocation(int xi,int yi)int x,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; /將起始位置的縱坐標(biāo)賦給棋盤的縱坐標(biāo)if(TryPath(x,y) /調(diào)用馬兒探尋函數(shù)，如果馬兒探尋整個棋盤返回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; /定義幾個臨時數(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; /將條數(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é)點(diǎn)的方向 top+; /棧指針前移進(jìn)棧stacktop.i=i;stacktop.j=j;stacktop.director=-1; /重新初始化下一棧結(jié)點(diǎn)的嘗試方向boardij=top+1; /標(biāo)記棋盤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;f