数据结构课程设计实习报告-马踏棋盘.docVIP

数据结构课程设计实习报告 题目：马踏棋盘（实习题2.4） 班级：计算机科学与技术2004班 学号：031010151552010 姓名：游尾妹 日期 ：二○○五年七月八日 指导老师：李杨老师 源程序结构 定义函数 caculate() 计算各点的权值 dirctions() 求出各点的最佳方向序列，即优先向权值小的方向，以使运行速度加快 check(int i,int j) 检查（i,j）是否在棋盘内 print() 输出路径走过的序号 程序步骤简介 计算各点的权值，方向 用户输入行数和列数 寻找点的八个可走方向，若所有方向都已走过，则退回前一步，并将此步抹去，使前一步的方向发生变化。 确定下一步该走的方向，依次走完全部点 记录每一步 当步数已满时输出，根据需要可输出一条或多条路径 源程序描述 #include stdio.h #define N 8 int w=0;　　　/*第几条可走路径*/ int way1[8]={-2,-1,1,2, 2, 1,-1,-2}; int way2[8]={ 1,2, 2,1,-1,-2,-2,-1};　/*在（i,j）位置处的8个可能走的位置*/ int ch[N*N]={0};　　/*走过的相应的点的赋值*/ int a[N*N+1][3]={0};　　　/*路径所经过点的记录*/ int dir[N][N][8];　　　　/*（i,j）点的八个可能走的方向*/ int st=1;　　/*走过的步数*/ char c=y;　 int weight[N][N];　　　/*每个点的权值*/ void caculate();　　　　　/*计算各点的权值*/ void dirctions();　　　　/*求出各点的最佳方向序列，即优先向权值小的方向*/ void print();　　　　/*输出路径走过的序号*/ int check(int i,int j);　　/*检查(i,j)是否在棋盘内*/ void caculate()　　　　/*计算各点的权值，将权值存在weight[i][j]中*/ { int i,j,k; for(i=1;i=N;i++) for(j=1;j=N;j++) for(k=0;kN;k++) { int x,y; x=i+way1[k]; y=j+way2[k];　　　/*下一步走的点*/ if(x=1x=Ny=1y=N) weight[i-1][j-1]++;　　/*权值*/ } } int check(int i,int j)　　　/*检查(i,j)是否在棋盘内，在返回1，不在返回0*/ { if(i1||i8||j1||j8) return 0;return 1; } void directions()　　　/*求出各点的最佳方向序列，即优先向权值小的方向*/ { int i,j,k,m,n1,n2,x1,y1,x2,y2,way_1,way_2; for(i=0;iN;i++) for(j=0;jN;j++) { for(k=0;k8;k++)dir[i][j][k]=k; for(k=0;k8;k++) { for(m=k+1;m8;m++) /*对每个方向考察看有没有更好的*/ { way_1=dir[i][j][k]; x1=i+way1[way_1]; y1=j+way2[way_1];　　　/*k方向时的下一个点*/ way_2=dir[i][j][m]; x2=i+way1[way_2]; y2=j+way2[way_2];　　　/*m方向时的下一个点*/ n1=check(x1+1,y1+1); n2=check(x2+1,y2+1);　　/*判断n1,n2是否在棋盘内*/　 if(( n1==0 n2)||( n1 n2weight[x1][y1]weight[x2][y2]))　　/*k方向不可达到，而m方向可达到*/　||　　/*都可达到，但m方向权值小*/ { dir[i][j][k]=way_2;dir[i][j][m]=way_1;　　/*交换两个方向值，将k走更好的一步棋（即权值小的一步）*/ } } } } } void print()　　/*输出路径走过的序号*/ { int x,y; printf(\n------%d answer----\n,+