数据结构马踏棋盘

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

2、 探寻路径函数： int TryPath(int i,int j);4. 输出路径函数： void Display();5. 主程序： void main();四、详细设计马儿在棋盘上的起始位置坐标 马儿每个方向进行尝试，直到 试完整个棋盘输出马儿行走的路径1. 函数声明void InitLocation(int xi,int yi); / int TryPath(int i,int j);/void Display();/2. 起始坐标函数模块void InitLocation(int xi,int yi) top+; / stacktop.i=xi; / stacktop.j=yi; /

3、stacktop.director=-1; / boardxiyi=top+1; / x=stacktop.i; / y=stacktop.j; / if(TryPath(x,y) /Display(); /栈指针指向第一个栈首 将起始位置的横坐标进栈 将起始位置的纵坐标进栈 将起始位置的尝试方向赋初值 标记棋盘 将起始位置的横坐标赋给棋盘的横坐标 将起始位置的纵坐标赋给棋盘的纵坐标 调用马儿探寻函数， 如果马儿探寻整个棋盘 返回 1 否则返回 0 输出马儿的行走路径elseprintf（" 无解 "）; 3. 探寻路径函数模块int TryPath(int i,int j

4、)int find,director,number,min; int i1,j1,h,k,s;/int a8,b18,b28,d8;/ 定义几个临时变量 定义几个临时变量 / 定义几个临时数组 栈不空时循环for(h=0;h<8;h+) /用数组 a8 记录当前位置的下一个位置的可while(top>-1)/行路径的条数 number=0; i=stacktop.i+Htry1h; j=stacktop.j+Htry2h; b1h=i; b2h=j; if(boardij=0&&i>=0&&i<8&&j>=0&

5、;&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根据可行路径条数小到大按下表排序放入数组 d8 中for(h=0;h<8;h+) /min=9;将下表存入数组 d8 中for(k=0;k<8;k+) if(min>ak) min=

6、ak; dh=k; / s=k; as=9;director=stacktop.director; if(top>=63) / return (1);find=0; / for(h=director+1;h<8;h+) 如果走完整个棋盘返回 1/表示没有找到下一个位置向八个方向进行探寻i=stacktop.i+Htry1dh; j=stacktop.j+Htry2dh;如果找到下一if(boardij=0&&i>=0&&i<8&&j>=0&&j<8) /位置find=1; / break;表示找

7、到下一个位置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

8、(j=0;j<N;j+) printf("t%d ",boardij); / 输出马儿在棋盘上走过的 路径printf("nn");printf("n");五、测试数据及测试结果 测试数据：x=2,y=3 测试结果：u锻的文档crop 味力-&i X 6bPlease inputiiiiJortBioi int CK=x =S1 andK-y<=8>Input x - 2Inpmt y = 3begin with 11hDard :2214192429141752B120IS252B3225G23£

9、927It1321&334G£540G92t3453225744471239764455437604148523562950433BUa513b61104?4Z请技任意犍继绫.六、实验环境C-Free七、源程序代码#in clude<stdio.h>#defi ne MAXSIZE 100#defi ne N 8int board88;/定义棋盘int Htry18=1,-1,-2,2,2,1,-1,-2;/*存储马各个出口位置相对当前位置行下标的增量数组*/int Htry28=2,-2,1,1,-1,-2,2,-1;/*存储马各个出口位置相对当前位置列下标的增

10、量数组*/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

11、=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,i

12、nt j)int find,director,number,min; / int i1,j1,h,k,s; /int a8,b18,b28,d8; / while(top>-1) /定义几个临时变量定义几个临时变量 定义几个临时数组 栈不空时循环如果找到下一number+;/如果找到下一位置记录条数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&&am

13、p;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) /入数组 d8ah=number;for(h=0;h<8;h+) /中/将条数存入数组 a8 中根据可行路径条数小到大按下表排序放min=9;for(k=0;k<8;k+) if(min>ak) 将下表存入数组 d8 中min

14、=ak; dh=k; / s=k;as=9;如果走完整个棋盘返回 1表示没有找到下一个位置向八个方向进行探寻/ 如果找到下一位置 director=stacktop.director; if(top>=63) / 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; / 表示找到下一个位置

15、 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&

16、lt;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("I