数据结构课程设计(马踏棋盘)

页1数据结构课程设计报告姓名：康宇年级：2010学号：10061014专业：计算机科学与技术指导老师：宋中山2013年4月15日页2马踏棋盘一、需求分析1、国际象棋的马踏棋盘的功能是：将马随机放在国际象棋的N*N棋盘board[N][N]的某个方格中，马按走棋规则进行移动。要求每个方格只进一次，走遍棋盘上全部N*N个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1,2，...,N*N依次填入一个N*N的方阵，输出之。2、测试数据：N由读者指定。马开始的位置也有读者指定（x,y）,1=x=N,1=y=N.3、实现提示：下图显示了N为6，马位于方格（3,3），8个可能的移动位置。一般来说，马位于位置（x，y）时，可以走到下列8个位置之一。但是，如果（x,y）靠近棋盘的边缘，上述有些位置可能超出棋盘范围，成为不允许的位置。8个可能的位置可以用两个一维数组hi[0...7],hj[0...7]来表示：1234568172H6354二、概要设计为实现上述程序功能，应用栈Stack[Max*Max]来表示棋盘的行和列。定义棋盘的规格N,马在下一步可以走的8个位置，hi[0...7],hj[0...7],用数组board[Max][Max]来标记棋盘，top标记栈指针。用户在输入了期盼的规格和起始坐标后，程序通过八个方向的探寻，输出第一个符合要求的棋盘，棋盘上显示了马每一步的位置，每一个位置只踏了一次，且踏遍棋盘。1、元素类型(栈)：structStack{inti;//行坐标intj;//列坐标}stack[Max][Max];123456页32、建立三个全局位置数组：inthi[8]={-2,-1,1,2,2,1,-1,-2};inthj[8]={1,2,2,1,-1,-2,-2,-1};用来存放下一个可能位置的横纵坐标；intboard[Max][Max];用来标记棋盘。3、本程序包括4个模块1）主程序：Voidmain(){While(1){Input棋盘规格N;Input起始位置的x；Input起始位置的x；If(起始位置在棋盘之内)Break;}调用栈函数InitLocation(x-1,y-1)；}2）判断是否踏遍棋盘函数boolFind(inti,intj){while(栈不空){if(踏遍了棋盘){returntrue;}for(k=0;k8;k++){依次求8个方向；if(该位置存在且没走){寻找各方向的可走路径数；a[k]存放各路径数；}}把各路径数按从小到大顺序排列for(k=0;k8;k++){if(有路可走){页4find=1;break;}}if(下一步有路可走){向下走一步；}else//下一个位置无路{清除棋盘上一步的标记；倒退一步；}}returnfalse;}3)输出函数voidPrint(){for(i=0;iN;i++){for(j=0;jN;j++){printf(%4d,board[i][j]);}printf(\n);}}4）初始化栈函数voidInitLocation(inti,intj){初始化栈；If(找到了踏遍棋盘的路)调用输出函数Print();}三、详细设计#includestdio.h#defineMax20inthi[8]={-2,-1,1,2,2,1,-1,-2};inthj[8]={1,2,2,1,-1,-2,-2,-1};intN;intboard[Max][Max];//标记棋盘inttop=0;//标记栈指针页5structStack{inti;intj;}stack[Max*Max];boolFind(inti,intj)//是否能踏遍棋盘{//find标记是否找到下一个位置，number标记8个位置的路径数，min标记最少的路径intfind,number,min;intxi,yj,k,m;inta[8],b[8];//a[]标记各位置的路径数，b[]标记由小到大的路径数对应的下标while(top-1){if(top==N*N-1)//踏遍了棋盘{returntrue;}for(k=0;k8;k++){number=0;i=stack[top].i+hi[k];j=stack[top].j+hj[k];if(board[i][j]==0&&i=0&&iN&&j=0&&jN){for(m=0;m8;m++)//寻找各方向的路径数{xi=i+hi[m];yj=j+hj[m];if(board[xi][yj]==0&&xi=0&&xiN&&yj=0&&yjN)number++;}a[k]=number;}}for(k=0;k8;k++)//把各路径数按从小到大顺序排列{min=9;for(m=0;m8;m++){if(a[m]min){页6min=a[m];b[k]=m;}}a[b[k]]=9;}find=0;for(k=0;k8;k++){i=stack[top].i+hi[b[k]];j=stack[top].j+hj[b[k]];if(board[i][j]==0&&i=0&&iN&&j=0&&jN){find=1;break;}}if(find)//下一步有路可走{top++;stack[top].i=i;stack[top].j=j;board[i][j]=top+1;}else//下一个位置无路{board[stack[top].i][stack[top].j]=0;//清除棋盘的标记top--;//倒退一步}}returnfalse;}voidPrint()//输出棋盘{inti,j;for(i=0;iN;i++){for(j=0;jN;j++){printf(%4d,board[i][j]);}页7printf(\n);}printf(\n);}voidInitLocation(inti,intj)//初始化栈并判断输出{stack[top].i=i;stack[top].j=j;board[i][j]=top+1;if(Find(i,j))Print();}intmain(){intx,y;inti,j;printf(InputN(N*N棋盘):);scanf(%d,&N);for(i=0;iN;i++)//初始化棋盘for(j=0;jN;j++)board[i][j]=0;while(1){printf(Inputx(1x=N):);scanf(%d,&x);printf(Inputy(1y=N):);scanf(%d,&y);if(x=1&&x=N&&y=1&&y=N)break;printf(Yourinputiswrong!!!\n);}printf(beginwith%drow,%drolonboard:\n\n,x,y);InitLocation(x-1,y-1);return0;}四、调试分析1.本次作业比较简单，只有一个核心算法，即求下一步该怎么走，以及是否有路可走，所以总的调试比较顺利。在调试Find算法时，遇到两个问题：一是没有考虑到马的这一步失败后的回溯，另一个是避免重复以前走过的路。2.本程序模块简洁，在main()函数里得到充分体现；3.用户可灵活控制棋盘的规模大小以及马踏的起始位置，本程序具有一定的通用性。页8五、用户手册1.本程序运行环境为Windows操作系统，执行文件为：mata.exe2.进入演示程序后显示的界面：六、测试结果页9