完整版数据结构马踏棋盘

1、实验二：栈和队列及其应用题目：马踏棋盘班级： 姓名： 学号：1、 问题描述设计一个国际象棋的马踏遍棋盘的演示程序.2、 根本要求将马随机放在国际象棋的8*8的棋盘Board88的某个方格中,马按走棋规那么进行移动.要求每个方格只进入一次,走遍棋盘上全部64个方格.编制非递归程序,求出马的行走路线,并按求出的行走路线,将数字2.2, ,64依次填入一个8*8的方阵,输出之.3、 概要设计1,定义头文件和预定义#include#define MAXSIZE 100#define N 82 .起始坐标函数：void InitLocation(int xi,int yi);3 .探寻路径函数：int

2、TryPath(int i,int j);4 .输出路径函数：void Display();5 .主程序：void main();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;/st

3、acktop.director=-1; / boardxiyi=top+1; / x=stacktop.i;/y=stacktop.j;/if(TryPath(x,y) /Display.；/elseprintf(无解) 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=0&i=0&j8) /如果找到下一位置for(k=0;k=0&i1=0&j18)/number+;/如果找到下一位置 记录条数ah

4、=number;/将条数存入数组a8for(h=0;h8;h+)/根据可行路径条数小到大按下表排序 放入数组d8中(min=9;for(k=0;kak) (min=ak;dh=k; / s=k; as=9;将下表存入数组d8中director=stacktop.director;if(top=63)return (1);find=0;/如果走完整个棋盘返回1for(h=director+1;h=0&i=0&j8) 如果找到下一位置( find=1; / break;表示找到下一个位置)if(find=1) /如果找到下一个位置进栈(存储栈结点的方向栈指针前移进栈重新初始化下一栈结点的尝试标记棋

5、盘否那么退栈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;iN;i+) ( for(j=0;jN;j+) printf(t%d ,boardij); /输出马儿在棋盘上走过的路径 print

6、f(nn); ) printf(n);五、测试数据及测试结果测试数据：x=2,y=3测试结果：六、实验环境C-Free七、源程序代码#include#define MAXSIZE 100#define N 8int 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; / stackMAX

7、SIZE;/存储方向定义一个栈数组void InitLocation(int xi,int yi); / int TryPath(int i,int j);/完整个棋盘void Display.；/马儿在棋盘上的起始位置坐标 马儿每个方向进行尝试,直到试输出马儿行走的路径int top=-1;/栈指针定义棋盘的横纵坐标变量栈指针指向第一个栈首将起始位置的横坐标进栈将起始位置的纵坐标进栈将起始位置的尝试方向赋初值标记棋盘将起始位置的横坐标赋给棋盘的横坐标将起始位置的纵坐标赋给棋盘的纵坐标调用马儿探寻函数,如果马儿探寻整个棋盘返输出马儿的行走路径定义几个临时变量定义几个临时变量 定义几个临时数组

8、栈不空时循环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否那么返回0Display();/else printf(无解)int TryPath(int i,int j)int find,director,number,min; /int i1,j1,h,k,s;/int a8,b18,b28,d8; /whi

9、le(top-1)/for(h=0;h=0&i=0&j8) /如果找到下一位置(for(k=0;k=0&i1=0&j18)/ number+; ah=number;for(h=0;h8;h+)/入数组d8中(min=9;for(k=0;kak) (min=ak;如果找到下一位置/记录条数/将条数存入数组a8中根据可行路径条数小到大按下表排序放dh=k; /将下表存入数组d8中s=k; as=9;director=stacktop.director;if(top=63)/return (1);find=0;/for(h=director+1;h=0&i=0&j8)/ 如果找到下一位置find=1

10、; / 表示找到下一个位置 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;iN;i+)(for(j=0;jN;j+)printf(t%d ,boardij); /输出马儿在棋盘上走过的路径printf(nn);printf(n);int main()(int i,j;int x,y;for(i=0;iN;i+)/初始化棋盘for(j=0;jN;j+)boardij=0;for(;)(pri