实验报告-马踏棋盘(共13页).docx
精选优质文档-倾情为你奉上2.4题马踏棋盘题目：设计一个国际象棋的马踏棋盘的演示程序班级：姓名：学号：完成日期：一 需求分析（1） 输入的形式和输入值的范围：输入马的初始行坐标X和列坐标Y，X和Y的范围都是1,8。 （2） 输出形式： 以数组下表的形式输入，i为行标，j为列标，用空格符号隔开。 以棋盘形式输出，每一格打印马走的步数，这种方式比较直观 （3） 程序所能达到的功能：让马从任意起点出发都能够遍历整个8*8的棋盘。 （4） 测试数据，包括正确输入及输出结果和含有错误的输入及其输出结果。数据可以任定，只要1<=x,y<=8就可以了。 正确的输出结果为一个二维数组，每个元素的值表示马行走的第几步，若输入有错，则程序会显示：“输入有误！请重新输入”并且要求用户重新输入数据，直至输入正确为止。二 概要设计（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）、设定栈的抽象数据类型定义： ADT Stack 数据对象：D=ai | aiElemSet,i=1,2,n,n0 数据关系：R1=<ai-1 , ai>|ai-1, aiD,i=2,n 约定an端为栈顶，ai端为栈顶。 基本操作： InitStack(&s) 操作结果：构造一个空栈s， DestroyStack(&s) 初始条件：栈s已存在。 操作结果：栈s被销毁。 ClearStack(&s) 初始条件：栈s已存在。 操作结果：栈s清为空栈。 StackEmpty(&s) 初始条件：栈s已存在。 操作结果：若栈s为空栈，则返回TRUE，否则返回FALSE。 StackLength(s); 初始条件：栈s存在。 操作结果：返回s的元素个数，即栈的长度。 GetTop (s,&e); 初始条件：栈s已存在且非空。 操作结果：用e返回s的栈顶元素。 Push(&s,e) 初始条件：栈s已存在。 操作结果：插入元素e为新的栈顶元素。 Pop(&s,&e) 初始条件：栈s存在且非空。 操作结果：删除栈顶元素，并用e返回。 stackTraverse(s,visit() 初始条件：栈s存在且非空。 操作结果：从栈底到栈顶依次对s的每个元素调用visit()。一旦visit()失败， 则 操作失败。 ADT Stack本程序包含模块： 1、 主程序模块：void main()定义变量；接受命令；处理命令；退出；2、 起始坐标函数模块马儿在棋盘上的起始位置； 3、 探寻路径函数模块马儿每个方向进行尝试，直到试完整个棋盘；4、 输出路径函数模块输出马儿行走的路径； 三 详细设计1.函数声明 Void InitLocation(int xi,int yi); /马儿在棋盘上的起始位置标 int TryPath(int i,int j); /马儿每个方向进行尝试，直到试完整个棋盘 void Display(); /输出马儿行走的路径 2. 起始坐标函数模块 void InitLocation(int xi,int yi) int x,y; /定义棋盘的横纵坐标变量 top+; /栈指针指向第一个栈首 stacktop.i=xi; /将起始位置的横坐标进栈 stacktop.j=yi; /将起始位置的纵坐标进栈 stacktop.director=-1; /将起始位置的尝试方向赋初值 boardxiyi=top+1; /标记棋盘 x=stacktop.i; /将起始位置的横坐标赋给棋盘的横标 y=stacktop.j; /将起始位置的纵坐标赋给棋盘的纵坐标 if(TryPath(x,y) /调用马儿探寻函数，如果马儿探寻整个棋盘返回1否则0 Display(); /输出马儿的行走路径 else printf("无解"); 3. 探寻路径函数模块int TryPath(int i,int j) int find,director,number,min; /定义几个临时变量 int i1,j1,h,k,s; /定义几个临时变量 int a8,b18,b28,d8; /定义几个临时数组 while(top>-1) /栈不空时循环 for(h=0;h<8;h+) /用数组a8记录当前位置的下一个位置的可行路径的条数 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+; /记录条数 ah=number; /将条数存入数组a8中 for(h=0;h<8;h+) /根据可行路径条数小到大按下表排序放d8中 min=9; for(k=0;k<8;k+) if(min>ak) min=ak; dh=k; /将下表存入数组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; /存储栈结点的方向 top+; /栈指针前移进栈 stacktop.i=i; stacktop.j=j; stacktop.director=-1; /重新初始化下一栈结点的尝试方向 boardij=top+1; /标记棋盘 else /否则退栈 boardstacktop.istacktop.j=0; /清除棋盘的标记 top-; /栈指针前移退栈 return (0); 4. 输出路径函数模块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"); 四、测试数据及测试结果 测试数据：x=2,y=3 测试结果如下：五 原程序代码#include<stdio.h> #define 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; /*存储马各个出口位置相对当前位置列下标的增量数组*/ struct Stack /定义栈类型 int i; /行坐标 int j; /列坐标 int director; /存储方向 stackMAXSIZE; /定义一个栈数组 int top=-1; /栈指针void InitLocation(int xi,int yi); /马儿在棋盘上的起始位置坐标 int TryPath(int i,int j); /马儿每个方向进行尝试，直到试完整个棋盘 void Display(); /输出马儿行走的路径void InitLocation(int xi,int yi) int x,y; /定义棋盘的横纵坐标变量 top+; /栈指针指向第一个栈首 stacktop.i=xi; /将起始位置的横坐标进栈 stacktop.j=yi; /将起始位置的纵坐标进栈 stacktop.director=-1; /将起始位置的尝试方向赋初值 boardxiyi=top+1; /标记棋盘 x=stacktop.i; /将起始位置的横坐标赋给棋盘的横坐标 y=stacktop.j; /将起始位置的纵坐标赋给棋盘的纵坐标 if(TryPath(x,y) /调用马儿探寻函数，如果马儿探寻整个棋盘返回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; /定义几个临时数组 while(top>-1) /栈不空时循环 for(h=0;h<8;h+) /用数组a8记录当前位置的下一个位置的可行路径的条数 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+; /记录条数 ah=number; /将条数存入数组a8中 for(h=0;h<8;h+) /根据可行路径条数小到大按下表排序放入数组d8中 min=9; for(k=0;k<8;k+) If(min>ak) min=ak; dh=k; /将下表存入数组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; /存储栈结点的方向 top+; /栈指针前移进栈 stacktop.i=i; stacktop.j=j; stacktop.director=-1; /重新初始化下一栈结点的尝试方向 boardij=top+1; /标记棋盘 else /否则退栈 boardstacktop.istacktop.j=0; /清除棋盘的标记 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); /输入起始位置的横坐标 printf("Input y = "); scanf("%d",&y); /输入起始位置的纵坐标 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); /调用起始坐标函数 专心-专注-专业
