资源描述：
《数据结构马踏棋盘》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、实验二：栈和队列及其应用题目：马踏棋盘班级：姓名：学号：一、问题描述设计一个国际象棋的马踏遍棋盘的演示程序。二、基本要求将马随机放在国际象棋的8*8的棋盘Board[8][8]的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1,2，……，64依次填入一个8*8的方阵，输出之。三、概要设计1.定义头文件和预定义#include#defineMAXSIZE100#defineN82.起始坐标函数：voidIn
2、itLocation(intxi,intyi);3.探寻路径函数：intTryPath(inti,intj);4.输出路径函数：voidDisplay();5.主程序：voidmain();四、详细设计1.函数声明voidInitLocation(intxi,intyi);//马儿在棋盘上的起始位置坐标intTryPath(inti,intj);//马儿每个方向进行尝试，直到试完整个棋盘voidDisplay();//输出马儿行走的路径2.起始坐标函数模块voidInitLocation(intxi,intyi){in
3、tx,y;//定义棋盘的横纵坐标变量top++;//栈指针指向第一个栈首stack[top].i=xi;//将起始位置的横坐标进栈stack[top].j=yi;//将起始位置的纵坐标进栈stack[top].director=-1;//将起始位置的尝试方向赋初值board[xi][yi]=top+1;//标记棋盘x=stack[top].i;//将起始位置的横坐标赋给棋盘的横坐标y=stack[top].j;//将起始位置的纵坐标赋给棋盘的纵坐标if(TryPath(x,y))//调用马儿探寻函数，如果马儿探寻整个棋
4、盘返回1否则返回0Display();//输出马儿的行走路径elseprintf("无解");}3.探寻路径函数模块intTryPath(inti,intj){intfind,director,number,min;//定义几个临时变量inti1,j1,h,k,s;//定义几个临时变量inta[8],b1[8],b2[8],d[8];//定义几个临时数组while(top>-1)//栈不空时循环{for(h=0;h<8;h++)//用数组a[8]记录当前位置的下一个位置的可行路径的条数{number=0;i=stack
5、[top].i+Htry1[h];j=stack[top].j+Htry2[h];b1[h]=i;b2[h]=j;if(board[i][j]==0&&i>=0&&i<8&&j>=0&&j<8)//如果找到下一位置{for(k=0;k<8;k++){i1=b1[h]+Htry1[k];j1=b2[h]+Htry2[k];if(board[i1][j1]==0&&i1>=0&&i1<8&&j1>=0&&j1<8)//如果找到下一位置number++;//记录条数}a[h]=number;//将条数存入数组a[8]中}}f
6、or(h=0;h<8;h++)//根据可行路径条数小到大按下表排序放入数组d[8]中{min=9;for(k=0;k<8;k++)if(min>a[k]){min=a[k];d[h]=k;//将下表存入数组d[8]中s=k;}a[s]=9;}director=stack[top].director;if(top>=63)//如果走完整个棋盘返回1return(1);find=0;//表示没有找到下一个位置for(h=director+1;h<8;h++)//向八个方向进行探寻{i=stack[top].i+Htry1[
7、d[h]];j=stack[top].j+Htry2[d[h]];if(board[i][j]==0&&i>=0&&i<8&&j>=0&&j<8)//如果找到下一位置{find=1;//表示找到下一个位置break;}}if(find==1)//如果找到下一个位置进栈{stack[top].director=director;//存储栈结点的方向top++;//栈指针前移进栈stack[top].i=i;stack[top].j=j;stack[top].director=-1;//重新初始化下一栈结点的尝试方向boa
8、rd[i][j]=top+1;//标记棋盘}else//否则退栈{board[stack[top].i][stack[top].j]=0;//清除棋盘的标记top--;//栈指针前移退栈}}return(0);}4.输出路径函数模块voidDisplay(){inti,j;for(i=0;i
