1、.問題描述設計一個國際象棋的馬踏棋盤的演示程序?；疽髮ⅠR隨機放在國際象棋8*8 的棋盤 Board88的某個方格中， 馬按走棋規則進行移動。要求每個方格只進入一次，走遍棋盤全部的 64 個方格。編制非遞歸程序，求出馬的行走路線，并按求出的行走路線， 將數字 1，2，3 .64 一次填入一個 8*8 的方陣 輸出之測試數據可自行指定一個馬的初始位置（i,j） ,0<=i,j<=7.。實現提示一般說來，當馬位于位置（i,j）時，可以走到下列8 個位置之一（ i-2,j+1 ） ,(i-1,j+2),(i+1,j+2),(i+2,j+1),(i+2,j-1), (i+1,j-2),(

2、i-1,j-2),(i-2,j-1)但是，如果（ i ，j ）靠近棋盤的邊緣，上述有些位置可能超出棋盤范圍，成為不允許的位置。 8 個可能位置可以用一維數組 Htry10 7 和 HTry20.7 來表示：Htry101234567-2-11221-1-2Htry2012345671221-1-2-2-1位于（i,j ）的馬可以走到新位置是在棋盤范圍內的 （i+ Htry1h,j+ Htry2h ）,其中 h=0,1, .7.一需求分析1輸入的形式和輸入值的范圍；分開輸入馬的初始行坐標X 和列坐標 Y，X 和 Y 的范圍都是 0,7 。2輸出的形式；一共提供了 2 種輸出方式：（1）以數組下標

3、形式輸入，代表起始位置，i 表示行標， j 表示列標。（2）以棋盤形式輸出，每一格打印馬走的步數，這種方式比較直觀。3程序所能達到的功能；讓馬從任一起點出發都能夠歷遍整個8×8 的棋盤。;.二概要設計1設定棧的抽象數據類型定義：ADT Stack數據對象： D=ai|ai CharSet,i=1,2.,n數據關系 :R1=<ai-1,ai>|ai-1,ai D,i=2,.,n基本操作 :(這里僅列舉本題中使用的操作)InitStack(&S)操作結果 :構建一個空棧。Push(&S,e)操作結果 :在棧頂插入新的元素。Pop（&S,&e ）

4、操作結果：將棧頂元素彈出。SetTop(S,& e)操作結果：將 e 設為棧頂元素。GetTop(S, &e)操作結果：將棧頂元素取出。StackEmpty(S)判斷棧是否為空ADT Stack2本程序包含 2 個模塊(1).主程序模塊 :Void main()初始化棋盤；while(1) 接受命令；處理命令；執行 Path(x,y);(2).棧模塊實現棧抽象數據類型3探討每次選擇位置的“最佳策略”思路1）先求出每個坐標點的權值，即是該坐標下一步有幾個方向可以走2）權值越小 ,則被上一點選中的可能性就越大，下一個方向八個值的選擇順序保存 MAPXYK數組中， 0<=K&l

5、t;=7 ，例如 MAPXY0保存的是下一步優先選擇走的方向，MAPXY7就是最后才走的。邊界的點最先走，然后再走中間。4踏遍棋盤偽碼算法：While （）;.若已經走了 64 步,則打印輸出結果；否則 若該點所有方向已走完 出棧 若該點所有方向未走完 若該點未走過且在棋盤內入棧，已走步數加1否則 * 下一步方向加 1三詳細設計1棧類型struct SElemTypeint a;int b;int di;/ 方向編號int flag8;/ 訪問過的方向數;棧的順序存儲表示typedef struct SqStackSElemType *base;SElemType *top;int stack

6、size;棧基本操作：Status InitStack(SqStack *S) /* 構造一個空棧 S */(*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!(*S).base)exit(OVERFLOW); /*存儲分配失敗*/(*S).top=(*S).base;(*S).stacksize=STACK_INIT_SIZE;return OK;Status StackEmpty(SqStack S);. /* 若棧 S 為空棧，則返回 TRUE，否則返回 FALSE */ if(S.top=S.base

7、)return TRUE;elsereturn FALSE;Status GetTop(SqStack S,SElemType *e) /* 若棧不空，則用 e 返回 S 的棧頂元素， 并返回 OK ；否則返回 ERROR/ if(S.top>S.base)*e=*(S.top-1); return OK;elsereturn ERROR;Status SetTop(SqStack S,SElemType *e)if(S.top>S.base)*(S.top-1)=*e;return OK;elsereturn ERROR;Status Push(SqStack *S,SElemT

8、ype e) /* 插入元素 e 為新的棧頂元素 */if(*S).top-(*S).base>=(*S).stacksize) /* 棧滿，追加存儲空間 */ (*S).base=(SElemType*)realloc(*S).base,(*S).stacksize+STACKINCRE MENT)*sizeof(SElemType);if(!(*S).base)exit(OVERFLOW); /*存儲分配失敗*/(*S).top=(*S).base+(*S).stacksize;(*S).stacksize+=STACKINCREMENT;*(*S).top)+=e;return O

9、K;Status Pop(SqStack *S,SElemType *e) /* 若棧不空，則刪除 S 的棧頂元素，用 e 返回其值，并返回 OK ；否則返回 ERROR */if(*S).top=(*S).base);.return ERROR;*e=*-(*S).top;return OK;2求最佳策略算法求各點權值 :可走的方向數越少 ,則被上一點選中的可能性越大int num(int x1,int y1)int count1=0;for(int j=0;j<8;j+)int x2=x1+Htry1j;int y2=y1+Htry2j;if(Pass(x2,y2)count1+;r

10、eturn count1;主要程序：#include <stdio.h>#include<malloc.h>#include<string.h>#define STACK_INIT_SIZE 10#define STACKINCREMENT 2int board88=0; /棋盤初始化int Htry18=-2,-1,1,2,2,1,-1,-2;int Htry28=1,2,2,1,-1,-2,-2,-1;struct SElemTypeint a;int b;int di;int flag8;typedef struct SqStackSElemType

11、*base;SElemType *top;int stacksize;void InitStack(SqStack &S)S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);.if(!S.base) exit(0);S.top=S.base;S.stacksize=STACK_INIT_SIZE;int StackEmpty(SqStack &S)if(S.base=S.top)return 1;elsereturn 0;void Push(SqStack &S,SElemType &e)if

12、(S.top-S.base>=S.stacksize)S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S.base) exit(0);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;int Pop(SqStack &S,SElemType &e)if(S.top=S.base) return 0;e=*-S.top;return 1;int Pass(int i,int j

13、)if(i>=0&&i<=7&&j>=0&&j<=7&&boardij=0)return 1;elsereturn 0;/ 判斷該方向是否能夠通過int num(int x1,int y1)int count1=0;for(int j=0;j<8;j+)int x2=x1+Htry1j;int y2=y1+Htry2j;if(Pass(x2,y2)count1+;.return count1;SElemType NextPos(SElemType e)int x1,y1;int i,j;int x=e

14、.a;int y=e.b;int p=0;int di_num=0;int di_min=8;for(i=0;i<8;i+)if(e.flagi!=0) continue;/判斷該方向是否走過x1=x+Htry1i;y1=y+Htry2i;if(Pass(x1,y1)di_num=num(x1,y1);if(di_num<di_min)/ 判斷該方向是否有最少的可通過方向e.a=x1;e.b=y1;di_min=di_num;p=i;e.flagp=1;return e;int search(int x,int y,SqStack &S)SElemType e,curpos

15、;int count=0;memset(curpos.flag,0,sizeof(curpos.flag);/ 將結構體中的flag 賦 0curpos.a=x;curpos.b=y;while(count<64)x=curpos.a;y=curpos.b;if(Pass(x,y) 若找到下一個點，則將該點壓入棧中count+;./printf("count=%d n", count);boardxy=count;e.di=0;e=curpos;Push(S,e);curpos=NextPos(e);memset(curpos.flag,0,sizeof(curpos

16、.flag);elseif(!StackEmpty(S)Pop(S,e);elsereturn 0;count-;while(e.di=7&&!StackEmpty(S)若 8 個方向都不能通過，則從棧中彈出上一個點boarde.ae.b=0;Pop(S,e);count-;if(e.di<7) 若該點的還有方向沒有訪問過，則換下一個方向e.di+;Push(S,e);count+;curpos=NextPos(e);memset(curpos.flag,0,sizeof(curpos.flag);return 1;void display()/ 將馬的軌跡輸出int i,j;for(i=0;i<8;i+)for(j=0;j<8;j+)printf("%2d",boardij);printf("n");int main()/ 主函數int x,y;.SqStack S;InitStack(S);printf(" 輸入馬的初始位置：n");scanf("%d%d",&x,&y);s