数据结构课程设计参考答案c组.docVIP

/* 马的遍历及其复杂性分析 */ #include stdio.h #define MAX 16 int step=0, count=0; /* chess[MAX][MAX]用来表示棋盘；step是步骤数；count是运算次数； chess[i][j]==-1表示该单元格非当前棋盘的有效位置； chess[i][j]==0表示该单元格尚未经过马的遍历； chess[i][j]=1表示马遍历时经过该单元格时的步骤； */ /* nextStepNum()函数用来计算(x，y)处可以跳的方向数 */ int nextStepNum(int chess[][MAX], int x, int y) { int sum=0; if(chess[x-1][y-2]==0) sum++; if(chess[x-2][y+1]==0) sum++; if(chess[x+2][y+1]==0) sum++; if(chess[x+2][y-1]==0) sum++; if(chess[x-2][y-1]==0) sum++; if(chess[x-1][y+2]==0) sum++; if(chess[x+1][y-2]==0) sum++; if(chess[x+1][y+2]==0) sum++; return(sum); /*每找到一个位置sum++，最后返回sum值就是在(x,y)处可走的位置数*/ } /* jump函数测试第step步为(x,y)位置的情况下，是否可以走完棋盘，如果可以返回1，否则返回0 */ int jump(int chess[][MAX], int rowNum, int colNum, int x, int y) { int s[9], a[9]; int min, i, j, k; count++; step++; chess[x][y]=step; /* 如果已经走到了rowNum×colNum的话，表示满足结束条件，返回1 */ if(step==rowNum*colNum) return 1; /* 计算(x，y)处下一步的八个位置上，每个位置上可以继续进行跳跃的方向数 */ s[1]=nextStepNum(chess, x-2, y+1); s[2]=nextStepNum(chess, x-1, y+2); s[3]=nextStepNum(chess, x+1, y+2); s[4]=nextStepNum(chess, x+2, y+1); s[5]=nextStepNum(chess, x+2, y-1); s[6]=nextStepNum(chess, x+1, y-2); s[7]=nextStepNum(chess, x-1, y-2); s[8]=nextStepNum(chess, x-2, y-1); /* 对下一步的八个位置上可以继续进行跳跃的方向数从小到大排序*/ // s数组的下标即为方向编号，a数组中存储的即为各个方向编号 for(j=1; j=8; j++) { min=9; a[j]=1; for(i=1; i=8; i++) if(s[i]min) { min=s[i]; a[j]=i; // 将s数组的下标（即方向编号）存入依次存入a数组中 k=i; } s[k]=9; } // 按可以进一步跳跃方向数从小到大的顺序，决定首先跳转的方向（贪心算法的思想） // 依次测试八个跳跃方向 for(i=1; i=8; i++) { switch(a[i]) { case 1: // 方向1可以跳跃，并且跳通了，则返回1，表示后面的方向不同再看； // 方向1不可跳跃，或者没有跳通，则直接break，执行下一次循环测试下一个方向。 if(chess[x-2][y+1]==0 jump(chess, rowNum, colNum, x-2, y+1)==1) return 1; break; case 2: if(chess[x-1][y+2]==0 jump(chess, rowNum, colNum, x-1, y+2)==1) return 1; break; case 3: if(chess[x+1][y+2]==0 jump(