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

《数据结构课程设计参考答案c组》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、/*马的遍历及其复杂性分析*/#include#defineMAX16intstep=0,count=0;/*chess[MAX][MAX]用来表示棋盘；step是步骤数；count是运算次数；chess[i][j]==-1表示该单元格非当前棋盘的有效位置；chess[i][j]==0表示该单元格尚未经过马的遍历；chess[i][j]>=1表示马遍历时经过该单元格时的步骤；*//*nextStepNum()函数用来计算(x，y)处可以跳的方向数*/intnextStepNum(intchess[][MAX],i

2、ntx,inty){intsum=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+

3、+，最后返回sum值就是在(x,y)处可走的位置数*/}/*jump函数测试第step步为(x,y)位置的情况下，是否可以走完棋盘，如果可以返回1，否则返回0*/intjump(intchess[][MAX],introwNum,intcolNum,intx,inty){ints[9],a[9];intmin,i,j,k;count++;step++;chess[x][y]=step;/*如果已经走到了rowNum×colNum的话，表示满足结束条件，返回1*/if(step==rowNum*colNum)return1;/*计算

4、(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]=next

5、StepNum(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]

6、){switch(a[i]){case1://方向1可以跳跃，并且跳通了，则返回1，表示后面的方向不同再看；//方向1不可跳跃，或者没有跳通，则直接break，执行下一次循环测试下一个方向。if(chess[x-2][y+1]==0&&jump(chess,rowNum,colNum,x-2,y+1)==1)return1;break;case2:if(chess[x-1][y+2]==0&&jump(chess,rowNum,colNum,x-1,y+2)==1)return1;break;case3:if(chess[x+1]

7、[y+2]==0&&jump(chess,rowNum,colNum,x+1,y+2)==1)return1;break;case4:if(chess[x+2][y+1]==0&&jump(chess,rowNum,colNum,x+2,y+1)==1)return1;break;case5:if(chess[x+2][y-1]==0&&jump(chess,rowNum,colNum,x+2,y-1)==1)return1;break;case6:if(chess[x+1][y-2]==0&&jump(chess,rowNum,

8、colNum,x+1,y-2)==1)return1;break;case7:if(chess[x-1][y-2]==0&&jump(chess,rowNum,colNum,x-1,y-2)==1)return1;break;case8:if(ch