實驗報告 馬踏棋盤
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) 程序所能達到的功能:讓馬從任意起點出發(fā)都能夠遍歷整個8*8的棋盤。 (4) 測試數(shù)據(jù),包括正確輸入及輸出結(jié)果和含有錯誤的輸入及其輸出結(jié)果。數(shù)據(jù)可以任定,只要1<=x,y<=8就可以了。 正確的輸出結(jié)果為一個二維數(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; Point *base; int stacksize; (1)、設(shè)定棧的抽象數(shù)據(jù)類型定義: ADT Stack 數(shù)據(jù)對象:D=ai | aiElemSet,i=1,2,n,n0 數(shù)據(jù)關(guān)系:R1=<ai-1 , ai>|ai-1, aiD,i=2,n 約定an端為棧頂,ai端為棧頂。 基本操作: InitStack(&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) 初始條件:棧s存在且非空。 操作結(jié)果:刪除棧頂元素,并用e返回。 stackTraverse(s,visit() 初始條件:棧s存在且非空。 操作結(jié)果:從棧底到棧頂依次對s的每個元素調(diào)用visit()。一旦visit()失敗, 則 操作失敗。 ADT Stack本程序包含模塊: 1、 主程序模塊:void main()定義變量;接受命令;處理命令;退出;2、 起始坐標(biāo)函數(shù)模塊馬兒在棋盤上的起始位置; 3、 探尋路徑函數(shù)模塊馬兒每個方向進行嘗試,直到試完整個棋盤;4、 輸出路徑函數(shù)模塊輸出馬兒行走的路徑; 3 詳細設(shè)計1.函數(shù)聲明 Void InitLocation(int xi,int yi); /馬兒在棋盤上的起始位置標(biāo) int TryPath(int i,int j); /馬兒每個方向進行嘗試,直到試完整個棋盤 void Display(); /輸出馬兒行走的路徑 2. 起始坐標(biāo)函數(shù)模塊 void InitLocation(int xi,int yi) int x,y; /定義棋盤的橫縱坐標(biāo)變量 top+; /棧指針指向第一個棧首 stacktop.i=xi; /將起始位置的橫坐標(biāo)進棧 stacktop.j=yi; /將起始位置的縱坐標(biāo)進棧 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否則0 Display(); /輸出馬兒的行走路徑 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<8;h+) /用數(shù)組a8記錄當(dāng)前位置的下一個位置的可行路徑的條數(shù) number=0; i=stacktop.i+Htry1h; j=stacktop.j+Htry2h; b1h=i; b2h=j; if(boardij=0&&i>=0&&i<8&&j>=0&&j<8) /如果找到下一位置 for(k=0;k<8;k+) i1=b1h+Htry1k;j1=b2h+Htry2k; if(boardi1j1=0&&i1>=0&&i1<8&&j1>=0&&j1<8) /如果找到下一位置 number+; /記錄條數(shù) ah=number; /將條數(shù)存入數(shù)組a8中 for(h=0;h<8;h+) /根據(jù)可行路徑條數(shù)小到大按下表排序放d8中 min=9; for(k=0;k<8;k+) if(min>ak) min=ak; dh=k; /將下表存入數(shù)組d8中 s=k; as=9; director=stacktop.director; if(top>=63) /如果走完整個棋盤返回1 return (1); find=0; /表示沒有找到下一個位置 for(h=director+1;h<8;h+) /向八個方向進行探尋 i=stacktop.i+Htry1dh; j=stacktop.j+Htry2dh; if(boardij=0&&i>=0&&i<8&&j>=0&&j<8) /如果找到下一位置 find=1; /表示找到下一個位置 Break;if(find=1) /如果找到下一個位置進棧 stacktop.director=director; /存儲棧結(jié)點的方向 top+; /棧指針前移進棧 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ù)模塊void Display() int i,j; for(i=0;i<N;i+) for(j=0;j<N;j+) printf("t%d ",boardij); /輸出馬兒在棋盤上走過的路徑 printf("nn"); printf("n"); 四、測試數(shù)據(jù)及測試結(jié)果 測試數(shù)據(jù):x=2,y=3 測試結(jié)果如下:5 原程序代碼#include<stdio.h> #define MAXSIZE 100 #define N 8 int board88; /定義棋盤 int Htry18=1,-1,-2,2,2,1,-1,-2; /*存儲馬各個出口位置相對當(dāng)前位置行下標(biāo)的*/ 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); /馬兒每個方向進行嘗試,直到試完整個棋盤 void Display(); /輸出馬兒行走的路徑void InitLocation(int xi,int yi) int x,y; /定義棋盤的橫縱坐標(biāo)變量 top+; /棧指針指向第一個棧首 stacktop.i=xi; /將起始位置的橫坐標(biāo)進棧 stacktop.j=yi; /將起始位置的縱坐標(biāo)進棧 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否則返回0 Display(); /輸出馬兒的行走路徑 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<8;h+) /用數(shù)組a8記錄當(dāng)前位置的下一個位置的可行路徑的條數(shù) number=0; i=stacktop.i+Htry1h; j=stacktop.j+Htry2h; b1h=i; b2h=j; if(boardij=0&&i>=0&&i<8&&j>=0&&j<8) /如果找到下一位置 for(k=0;k<8;k+) i1=b1h+Htry1k; j1=b2h+Htry2k; if(boardi1j1=0&&i1>=0&&i1<8&&j1>=0&&j1<8) /如果找到下一位置 number+; /記錄條數(shù) ah=number; /將條數(shù)存入數(shù)組a8中 for(h=0;h<8;h+) /根據(jù)可行路徑條數(shù)小到大按下表排序放入數(shù)組d8中 min=9; for(k=0;k<8;k+) If(min>ak) min=ak; dh=k; /將下表存入數(shù)組d8中 s=k; as=9; director=stacktop.director; if(top>=63) /如果走完整個棋盤返回1 return (1); find=0; /表示沒有找到下一個位置 for(h=director+1;h<8;h+) /向八個方向進行探尋 i=stacktop.i+Htry1dh; j=stacktop.j+Htry2dh; if(boardij=0&&i>=0&&i<8&&j>=0&&j<8) /如果找到下一位置 find=1; /表示找到下一個位置 break; if(find=1) /如果找到下一個位置進棧 stacktop.director=director; /存儲棧結(jié)點的方向 top+; /棧指針前移進棧 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); void Display() int i,j; for(i=0;i<N;i+) for(j=0;j<N;j+) printf("t%d ",boardij); /輸出馬兒在棋盤上走過的路徑 printf("nn"); printf("n"); int main() int i,j; int x,y; for(i=0;i<N;i+) /初始化棋盤 for(j=0;j<N;j+) boardij=0; for(;) printf("Please input importpoint(1<=x<=8 and 1<=y<=8)n"); printf("Input x = "); scanf("%d",&x); /輸入起始位置的橫坐標(biāo) printf("Input y = "); scanf("%d",&y); /輸入起始位置的縱坐標(biāo) if(x>=1&&x<=8&&y>=1&&y<=8)break; printf("Your input is worng!n"); printf("begin with %d board:nn", 8*(x-1)+y); InitLocation(x-1,y-1); /調(diào)用起始坐標(biāo)函數(shù)