《数据结构课程设计参考答案c组》由会员分享，可在线阅读，更多相关《数据结构课程设计参考答案c组（61页珍藏版）》请在金锄头文库上搜索。
1、/* 马的遍历及其复杂性分析*/#include #define MAX 16int step=0, count=0;/*chessMAXMAX用来表示棋盘；step是步骤数；count是运算次数；chessij=-1表示该单元格非当前棋盘的有效位置；chessij=0表示该单元格尚未经过马的遍历；chessij=1表示马遍历时经过该单元格时的步骤；*/* nextStepNum()函数用来计算(x，y)处可以跳的方向数 */int nextStepNum(int chessMAX, int x, int y) int sum=0; if(chessx-1y-2=0)sum+; if(ches
2、sx-2y+1=0)sum+; if(chessx+2y+1=0)sum+; if(chessx+2y-1=0)sum+; if(chessx-2y-1=0)sum+; if(chessx-1y+2=0)sum+; if(chessx+1y-2=0)sum+; if(chessx+1y+2=0)sum+; return(sum); /*每找到一个位置sum+，最后返回sum值就是在(x,y)处可走的位置数*/ /* jump函数测试第step步为(x,y)位置的情况下，是否可以走完棋盘，如果可以返回1，否则返回0 */ int jump(int chessMAX, int rowNum, in
3、t colNum, int x, int y)int s9, a9; int min, i, j, k; count+; step+; chessxy=step;/* 如果已经走到了rowNumcolNum的话，表示满足结束条件，返回1 */if(step=rowNum*colNum)return 1; /* 计算(x，y)处下一步的八个位置上，每个位置上可以继续进行跳跃的方向数 */s1=nextStepNum(chess, x-2, y+1);s2=nextStepNum(chess, x-1, y+2); s3=nextStepNum(chess, x+1, y+2); s4=nextS
4、tepNum(chess, x+2, y+1); s5=nextStepNum(chess, x+2, y-1); s6=nextStepNum(chess, x+1, y-2); s7=nextStepNum(chess, x-1, y-2); s8=nextStepNum(chess, x-2, y-1); /* 对下一步的八个位置上可以继续进行跳跃的方向数从小到大排序*/ s数组的下标即为方向编号，a数组中存储的即为各个方向编号for(j=1; j=8; j+) min=9; aj=1; for(i=1; i=8; i+) if(simin) min=si; aj=i;/ 将s数组的下标
5、（即方向编号）存入依次存入a数组中k=i; sk=9; / 按可以进一步跳跃方向数从小到大的顺序，决定首先跳转的方向（贪心算法的思想）/ 依次测试八个跳跃方向for(i=1; i=8; i+) switch(ai)case 1:/ 方向1可以跳跃，并且跳通了，则返回1，表示后面的方向不同再看；/ 方向1不可跳跃，或者没有跳通，则直接break，执行下一次循环测试下一个方向。if(chessx-2y+1=0 & jump(chess, rowNum, colNum, x-2, y+1)=1)return 1;break;case 2:if(chessx-1y+2=0 & jump(chess,
6、rowNum, colNum, x-1, y+2)=1)return 1;break;case 3:if(chessx+1y+2=0 & jump(chess, rowNum, colNum, x+1, y+2)=1)return 1; break;case 4:if(chessx+2y+1=0 & jump(chess, rowNum, colNum, x+2, y+1)=1)return 1;break;case 5:if(chessx+2y-1=0 & jump(chess, rowNum, colNum, x+2, y-1)=1)return 1;break;case 6:if(che
7、ssx+1y-2=0 & jump(chess, rowNum, colNum, x+1, y-2)=1)return 1;break;case 7:if(chessx-1y-2=0 & jump(chess, rowNum, colNum, x-1, y-2)=1)return 1; break;case 8:if(chessx-2y-1=0 & jump(chess, rowNum, colNum, x-2, y-1)=1)return 1; /* 如果某个位置的八个方向都无法走了，则回退到上一个位置，测试上一个位置的下一个方向是否能走通 */ step-; /* 恢复棋盘中该位置的状态为
8、0，并返回0表示该路没有走通 */ chessxy=0; return 0; void main() int chessMAXMAX;int rowNum=0, colNum=0;int i, j, row, col;while(1) printf(n*欢迎使用马的棋盘遍历系统*n);/* 初始化棋盘 */for(i=0;iMAX;i+) for(j=0;jMAX;j+)chessij=-1;/* 设置棋盘的大小 */printf(n请输入棋盘的行数和列数（均小于15，格式：行数 列数）：);scanf(%d%d, &rowNum, &colNum);for(i=1; i=rowNum; i+
9、)for(j=1; j=1 & row=1 & col=colNum)/ 判断输入是否有效 printf(遍历进行中，请稍等n);if(jump(chess, rowNum, colNum, row, col)=1)printf(马遍历该棋盘的路径如下：n);for(i=0; i=colNum; i+)printf(%4d, i);printf(n);for(i=1; i=rowNum; i+)printf(%4d, i);for(j=1; j=colNum; j+)printf(%4d, chessij);printf(n); elseprintf(马不能对该棋盘进行完整遍历，请重新输入棋盘
10、大小!n);else printf(n马的起始行列号输入错误，请重新输入!n);/* 求AOE网的关键路径*/#include #include #include #define MAX 10/顶点的个数/ 定义弧结点typedef struct ArcNode1int tailvex, headvex; /弧的尾和头顶点位置float weight;struct ArcNode1 *hlink,*tlink; /分别为弧头相同弧尾相同的弧的链域ArcNode;typedef struct typechar r3;/顶点值VertexType;typedef struct VexNodeVer
11、texType data;ArcNode *firstin, *firstout; /分别指向该顶点第一条入弧和出弧VexNode;/ 定义十字链表类型typedef structVexNode xlistMAX;/表头结点int vexnum, arcnum;/有向图的当前顶点数和弧数OLGraph;/ 确定vex顶点在图中的位置int locate(OLGraph G, VertexType vex)int i;for(i=0;iG.vexnum;i+) if(strcmp(vex.r,G.xlisti.data.r)=0) return i;return -1;/ 判断输入的AOE网中是否存在环，得到拓扑序列int topoSort(OLGraph G, int indegree, int topo) ArcNode *q;int visitedMAX;int i, flag=1, count=0;/ 初始化顶点访问数组，未输出设置为0，已输出设置为1for(i=0; iG.vexnum; i+)visitedi=
