数据结构报告——08.doc

院 系： 计算机科学学院 专 业： 网络工程 年 级： 2008 课程名称： 数据结构 学 号： **** 姓 名： ** 指导教师： *** 2009年 月 日 骑士周游世界 一 、 需求分析 本程序用来完成将马放在国际象棋的8×8棋盘方格中，马按走棋规则进行移动，每个方格只走一次，走遍棋盘上的全部64个方格，寻找出路线。 输入的形式及数据范围 以二维数组board[i][j]，表示棋盘上的每一格，初始时将数组初设为零，之后在程序中若此位置进入路径中，则被设置为与路径相对应的数值若数组所有的元素都被设为某一个数值，说明有一条通路，就结束了寻找，就输出整个数组，得到一条通路。 路径入口可以用户自己定义，程序的开始会提示用户输入行与列。 若存在路径，程序会输出一个8×8的数据，数据是从1到64，从入口设定为第一步，之后会一直顺着数字到64结束；若不存在路径，程序会输出英文：wrong! 说明没有这一条通路。 本程序只能输出一条通路，还需要进一步改进。 二、 详细设计 int board[n][n]={0}; stack horse[sqn];//设置栈结构，其中sqn为64 int top=0;//栈顶 int a[8]={-2,-1,1,2,2,1,-1,-2}; int b[8]={1,2,2,1,-1,-2,-2,-1};//a与对应的b组成了马走一步的八个路径 int i,j,u,v; …… horse[top].x=i; horse[top].y=j;//i与j为起始坐标 horse[top].k=0; top++; board[i][j]=top; int m=0; int flag; while(top!=0topsqn)//若栈不空且栈中数据没有到64 { i=horse[top-1].x; j=horse[top-1].y; flag=0; while(m8flag==0)//将所有的路径都试一遍 { u=i+a[m];v=j+b[m];//走向下一个位置 if(u=0unv=0vnboard[u][v]==0) //如果此位置在棋盘内且没有重复 { flag=1; board[u][v]=top+1; } else m++; } if(flag==1){ //找到了正确位置，入栈 horse[top].x=u; horse[top].y=v; horse[top].k=m; top++; m=0; } Else //没有找到正确位置 { top--; m=horse[top].k+1;//将位置设为上一个错误位置的下一个路 board[horse[top].x][horse[top].y]=0;//如果不能走，则退到前一步 } …… 三、 调试分析 程序不是很大，但是在调试时发现运行的时间较长，占用CPU比较大，若出现了死循环，则需要细心地去寻找，原因大概是在回退时没有掌握好下一步的位置，则不会有正确的结果。 保持良好的编程习惯，要在合适的时候分行，便于修改的时候查错。 可以用双斜杠将多个不同功