实验报告-马踏棋盘(共13页)

1、精选优质文档-倾情为你奉上2.4题马踏棋盘题目：设计一个国际象棋的马踏棋盘的演示程序班级：姓名：学号：完成日期：1 需求分析（1） 输入的形式和输入值的范围：输入马的初始行坐标X和列坐标Y，X和Y的范围都是1,8。 （2） 输出形式： 以数组下表的形式输入，i为行标，j为列标，用空格符号隔开。 以棋盘形式输出，每一格打印马走的步数，这种方式比较直观 （3） 程序所能达到的功能：让马从任意起点出发都能够遍历整个8*8的棋盘。 （4） 测试数据，包括正确输入及输出结果和含有错误的输入及其输出结果。数据可以任定

2、，只要1<=x,y<=8就可以了。 正确的输出结果为一个二维数组，每个元素的值表示马行走的第几步，若输入有错，则程序会显示：“输入有误！请重新输入”并且要求用户重新输入数据，直至输入正确为止。2 概要设计（1） 、位置的存储表示方式（2）  typedef struct                int x;      int y;

3、          int from; Point;  （2） 、栈的存储方式 #define STACKSIZE 70 #define STACKINCREASE 10 typedef struct Stack          Point *top;  &

4、#160;  Point *base;        int stacksize; （1）、设定栈的抽象数据类型定义：  ADT Stack       数据对象：D=ai | aiElemSet,i=1,2,n,n0       数据关系：R1=<ai-1 , ai>

5、;|ai-1, aiD,i=2,n                 约定an端为栈顶，ai端为栈顶。       基本操作：      InitStack(&s)     操作结果：构造一个空栈s，    

6、60;     DestroyStack(&s)          初始条件：栈s已存在。           操作结果：栈s被销毁。             ClearStack(&s)  &

7、#160;       初始条件：栈s已存在。           操作结果：栈s清为空栈。               StackEmpty(&s)          初始条件：栈

8、s已存在。     操作结果：若栈s为空栈，则返回TRUE，否则返回FALSE。               StackLength(s);           初始条件：栈s存在。          操作结果：返回s的

9、元素个数，即栈的长度。             GetTop (s,&e);          初始条件：栈s已存在且非空。           操作结果：用e返回s的栈顶元素。      &

10、#160;       Push(&s,e)  初始条件：栈s已存在。         操作结果：插入元素e为新的栈顶元素。          Pop(&s,&e)         初始条件：栈s存在且非空。

11、0;        操作结果：删除栈顶元素，并用e返回。             stackTraverse(s,visit()         初始条件：栈s存在且非空。        操作结果：从栈底到栈顶依次对s的每个元素调

12、用visit()。一旦visit()失败， 则 操作失败。 ADT Stack本程序包含模块： 1、 主程序模块：void main()定义变量；接受命令；处理命令；退出；2、 起始坐标函数模块马儿在棋盘上的起始位置； 3、 探寻路径函数模块马儿每个方向进行尝试，直到试完整个棋盘；4、 输出路径函数模块输出马儿行走的路径；  3 详细设计1.函数声明 Void InitLocation(int xi,int yi); /马儿在棋盘上的起始位置标 int TryPath(int

13、 i,int j);          /马儿每个方向进行尝试，直到试完整个棋盘 void Display();                    /输出马儿行走的路径 2. 起始坐标函数模块 void InitLo

14、cation(int xi,int yi)   int x,y;                /定义棋盘的横纵坐标变量 top+;                  /栈指针指向第一个栈首

15、  stacktop.i=xi;        /将起始位置的横坐标进栈  stacktop.j=yi;        /将起始位置的纵坐标进栈  stacktop.director=-1; /将起始位置的尝试方向赋初值  boardxiyi=top+1;    /标记棋盘  x=stac

16、ktop.i;         /将起始位置的横坐标赋给棋盘的横标  y=stacktop.j;         /将起始位置的纵坐标赋给棋盘的纵坐标 if(TryPath(x,y)       /调用马儿探寻函数，如果马儿探寻整个棋盘返回1否则0 Display();   &#

17、160;     /输出马儿的行走路径  else                     printf("无解");        3. 探寻路径函数模块int TryPath(int i

18、,int j)   int find,director,number,min;  /定义几个临时变量 int i1,j1,h,k,s;              /定义几个临时变量  int a8,b18,b28,d8;    /定义几个临时数组  while(top>-1

19、)                 /栈不空时循环    for(h=0;h<8;h+)    /用数组a8记录当前位置的下一个位置的可行路径的条数        number=0;        i=stacktop.i+

20、Htry1h;      j=stacktop.j+Htry2h; b1h=i;       b2h=j;    if(boardij=0&&i>=0&&i<8&&j>=0&&j<8)    /如果找到下一位置       

21、0;for(k=0;k<8;k+)           i1=b1h+Htry1k;j1=b2h+Htry2k;         if(boardi1j1=0&&i1>=0&&i1<8&&j1>=0&&j1<8)         

22、60;                                     /如果找到下一位置           

23、number+;              /记录条数         ah=number;                   /将条数存入数组a8中    

24、     for(h=0;h<8;h+)     /根据可行路径条数小到大按下表排序放d8中      min=9;     for(k=0;k<8;k+)      if(min>ak)           min=ak; 

25、60;       dh=k;    /将下表存入数组d8中                 s=k;            as=9;       

26、    director=stacktop.director;  if(top>=63)                 /如果走完整个棋盘返回1    return (1);   find=0;       &#

27、160;             /表示没有找到下一个位置   for(h=director+1;h<8;h+)   /向八个方向进行探寻       i=stacktop.i+Htry1dh;       j=stacktop.j+Htry2dh; 

28、if(boardij=0&&i>=0&&i<8&&j>=0&&j<8) /如果找到下一位置         find=1;       /表示找到下一个位置 Break;if(find=1)          /如果找到下一个位置进

29、栈       stacktop.director=director; /存储栈结点的方向     top+;                      /栈指针前移进栈    stacktop.i=i;

30、60;   stacktop.j=j;    stacktop.director=-1;    /重新初始化下一栈结点的尝试方向    boardij=top+1;         /标记棋盘    else          &

31、#160;                /否则退栈        boardstacktop.istacktop.j=0;  /清除棋盘的标记    top-;            &#

32、160;        /栈指针前移退栈        return (0);     4. 输出路径函数模块void Display()    int i,j;     for(i=0;i<N;i+)     f

33、or(j=0;j<N;j+)    printf("t%d  ",boardij);  /输出马儿在棋盘上走过的路径   printf("nn");    printf("n");  四、测试数据及测试结果 测试数据：x=2,y=3 测试结果如下：5 原程序代码#include<stdio.h> #define 

34、;MAXSIZE 100 #define N 8  int board88;           /定义棋盘 int Htry18=1,-1,-2,2,2,1,-1,-2;  /*存储马各个出口位置相对当前位置行下标的*/ int Htry28=2,-2,1,1,-1,-2,2,-1;      &

35、#160;                   /*存储马各个出口位置相对当前位置列下标的增量数组*/ struct Stack              /定义栈类型    int i; 

36、                 /行坐标  int j;                  /列坐标 int director;      

37、;     /存储方向 stackMAXSIZE;           /定义一个栈数组 int top=-1;                /栈指针void InitLocation(int xi,int yi);&

38、#160; /马儿在棋盘上的起始位置坐标 int TryPath(int i,int j);          /马儿每个方向进行尝试，直到试完整个棋盘 void Display();                    /输出

39、马儿行走的路径void InitLocation(int xi,int yi)   int x,y;                /定义棋盘的横纵坐标变量  top+;               

40、   /栈指针指向第一个栈首  stacktop.i=xi;        /将起始位置的横坐标进栈  stacktop.j=yi;        /将起始位置的纵坐标进栈  stacktop.director=-1; /将起始位置的尝试方向赋初值  boardxiyi=top+1;   

41、 /标记棋盘  x=stacktop.i;         /将起始位置的横坐标赋给棋盘的横坐标  y=stacktop.j;         /将起始位置的纵坐标赋给棋盘的纵坐标  if(TryPath(x,y)      /调用马儿探寻函数，如果马儿探寻整个棋盘返回1否则返回0

42、0;  Display();         /输出马儿的行走路径  else                     printf("无解");       int&#

43、160;TryPath(int i,int j)   int find,director,number,min;  /定义几个临时变量 int i1,j1,h,k,s;              /定义几个临时变量  int a8,b18,b28,d8;    /定义几个临时数组 

44、; while(top>-1)                 /栈不空时循环   for(h=0;h<8;h+)    /用数组a8记录当前位置的下一个位置的可行路径的条数       number=0;     &

45、#160;  i=stacktop.i+Htry1h;        j=stacktop.j+Htry2h;        b1h=i;        b2h=j;       if(boardij=0&&i>=0&&i<8&&j>=0&am

46、p;&j<8)    /如果找到下一位置            for(k=0;k<8;k+)         i1=b1h+Htry1k;           j1=b2h+Htry2k;     

47、    if(boardi1j1=0&&i1>=0&&i1<8&&j1>=0&&j1<8)                                

48、;                /如果找到下一位置           number+;              /记录条数      

49、   ah=number;                   /将条数存入数组a8中          for(h=0;h<8;h+)     /根据可行路径条数小到大按下表排序放入数组d8中  

50、60; min=9;       for(k=0;k<8;k+)       If(min>ak)            min=ak;         dh=k;    /将下表存入数组d8中 &

51、#160;                s=k;        as=9; director=stacktop.director;       if(top>=63)          

52、60;      /如果走完整个棋盘返回1    return (1);   find=0;                     /表示没有找到下一个位置   for(h=director+1;h<8;h+)&

53、#160;  /向八个方向进行探寻       i=stacktop.i+Htry1dh;        j=stacktop.j+Htry2dh;     if(boardij=0&&i>=0&&i<8&&j>=0&&j<8) /如果找到下一位置      &

54、#160;     find=1;       /表示找到下一个位置      break;          if(find=1)          /如果找到下一个位置进栈      stacktop.di

55、rector=director; /存储栈结点的方向     top+;                      /栈指针前移进栈    stacktop.i=i;    stacktop.j=j;    stacktop.director=-1;    /重新初始化下一栈结点的尝试方向    boardij=top+1;         /标记棋盘      else