實驗報告 馬踏棋盤

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ù)