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

1、数据结构课程设计实习报告题目：马踏棋盘（实习题2.4）班级：计算机科学与技术2004班学号：031010151552010姓名：游尾妹日期:二OO五年七月八日指导老师：李杨老师源程序结构1 定义函数caculate（）计算各点的权值dirctions（）求出各点的最佳方向序列，即优先向权值小的方向，以使运行速度加快check（int i,int j）检查（i,j）是否在棋盘内print（）输出路径走过的序号2 程序步骤简介（1）计算各点的权值，方向（2）用户输入行数和列数（3）寻找点的八个可走方向，若所有方向都已走过，则退回前一步，并将此步 抹去，使前一步的方向发生变化。（4） 确定下一步该走

2、的方向，依次走完全部点（5） 记录每一步（6） 当步数已满时输出，根据需要可输出一条或多条路径3 源程序描述#include stdio.h #define N 8int w=0;/*第几条可走路径*/int way18=-2,-1,1,2, 2, 1,-1,-2;int way28= 1,2, 2,1,-1,-2,-2,-1;/*在(i,j)位置处的8个可能走的位置*/int chN*N=0; /*走过的相应的点的赋值*/int aN*N+13=0; /*路径所经过点的记录*/int dirNN8;/*(i,j)点的八个可能走的方向*/intst=1;/*走过的步数*/*每个点的权值*/*计

3、算各点的权值*/*求出各点的最佳方向序列，即优先向权值小的方向/*输出路径走过的序号*/*检查（i,j）是否在棋盘内*/*计算各点的权值，将权值存在weightij中*/int i,j,k;for(i=1;i=N;i+)for(j=1;j=N;j+) for(k=0;k=1&x=1&y=N)weighti-1j-1+; /*权值*/int check(int i,int j)/*检查(i,j)是否在棋盘内，在返回1，不在返回if(i8|j8)return 0;return 1;void directions()/*求出各点的最佳方向序列，即优先向权值小的方向int i,j,k,

4、m,n1,n2,x1,y1,x2,y2,way_1,way_2; for(i=0;iN;i+)0*/*/for(j=0;jN;j+)for(k=0;k8;k+)dirijk=k;for(k=0;k8;k+)for(m=k+1;mweightx2y2)到，而m方向可达到*/ | /*都可达到，但m方向权值小*/*k方向不可达dirijk=way_2;dirijm=way_1;即权值小的一步)*/*交换两个方向值， 将k走更好的一步棋void print() /*输出路径走过的序号*/int x,y;printf(n- %d answer-n,+w);for(x=1;xN+1;x+)/*输出是第w

5、条路径的序号*/printf(n);printf(n);printf(nPress n to quit ,press any other key to continue.n);c=getchar(); /*询问是否继续输出结果*/main()int x,y,way,way0; caculate();directions();printf(Please enter the row and column of the starting point.n); scanf(%d,%d,&a10,&a11);/*输入行数和列数*/getchar();y=ast1;ch(x-1)*N+y-1

6、=0; /*将这一点被走过的痕迹抹去*/ast0=ast1=ast2=0;ast-12+;/*将上一次走的点走的方向发生变化*/st-;/*步数减一*/else /*此点的八个方向未全走过，应走此方向*/way0=ast2;ast2+; /*确定下次应走的方向*/ x=ast0;y=ast1; way=dirx-1y-1way0;x=ast0+way1way;y=ast1+way2way;/*确定按这次的方向走应走到的x,y坐标*/if(x1|yN|yN|ch(x-1)*N+y-1!=0)continue; /*此点不满足要求*/ast0=x;ast1=y;ast2=0;if(st=N*N)

7、print();/*标记这一点*/*步数已满*/*输出结果*/if(c=n)break;ast0=ast1=ast2=0;ast-12+;for(y=1;y=8)break;if(ast2=8)x=ast0;/*在ch数组中对相应点赋值，即输出时用到的各点的顺序号/*出发点的八个方向都已走过， 表示所有的方法均已找出/*此点的八个方向都已走过，应该退回到上一次走的点*/*/*/ch(x-1)*N+y-1=+st;/*走到这一点*/ch(x-1)*N+y-1=0;st-;/*退回前一步*/二、 程序运行结果例如：输入数值为2，3时，并且要求输入第2条路径（只按回车键即可）Please enter the row and column of the starting point.2，3-1 answer-22954151231561753141305516113228352136461185751466360395833104275045623740194924473859449342652243367204123482562142358Press n to quit ,press any other key to continue.-2 answer-2295415123160175314130551611322835213646118