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

/* 马的遍历及其复杂性分析*/#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(chessx-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, int 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=nextStepNum(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=1 /弧的尾和头顶点位置float weight;struct ArcNode1 *hlink,*tlink; /分别为弧头相同弧尾相同的弧的链域ArcNode;typedef struct typechar r3; /顶点值VertexType;typedef struct VexNodeVertexType data;ArcNode *firstin, *firstout; /分别指向该顶点第一条入弧和出弧VexNode;/ 定义十字链表类型typedef structVexNode xlistMAX; /表头结点int vexnum, arcnum; /有向图的当前顶点数和弧数OLGraph;/ 确定 vex顶点在图中的位置int locate(OLGraph G, VertexType vex)int i;for(i=0;iheadvex-;q=q-tlink;flag=1;break; / 这个 break必不可少，否则程序逻辑上将会有漏洞！else flag=0;if(counttlink;free(p);p=G.xlisti.firstout;G.vexnum=-1;G.arcnum=-1;/ 创建 AOE网的十字链表存储结构void createDG(OLGraph float weight;int vextailpoi,vexheadpoi;VertexType vertail,verhead;ArcNode *p;/ 如果输入的图不是 AOE网，则反复输入，直到输入正确为止while(1)doprintf(“分别输入顶点和弧的个数（用空格键隔开）：“);scanf(“%d%d“, if(G.vexnum10)printf(“ttAOE网的顶点数必须属于【1-10】 ，请重新输入！n“);while( (G.vexnum10) );for(i=0; itailvex=vextailpoi;p-headvex=vexheadpoi; /对弧结点赋值p-weight=weight;p-hlink=G.xlistvexheadpoi.firstin;p-tlink=G.xlistvextailpoi.firstout;G.xlistvextailpoi.firstout=p; /完成在入弧和出弧链头的插入G.xlistvexheadpoi.firstin=p;indegreevexheadpoi+; / 弧头结点的入度自增printf(“ntAOE网输入结束，十字链表存储结构创建成功！n“);/ 如果可以拓扑排序，则 break；否则，应回收该十字链表，并再次输入该 AOE网if(1=topoSort(G, indegree, topo)break;elseprintf(“n该十字链表表示的图中存在环，为其分配的内存空间已回收，请重新输入正确的 AOE网！nn“);destroy(G);/* 输出 AOE网的十字链表存储结构 */void printfOLGraph(OLGraph ArcNode *q;if(G.vexnum0)printf(“十字链表为：n“); /输出十字链表for(i=0; i%s的权值%.1f； “, G.xlistq-tailvex.data.r, G.xlistq-headvex.data.r, q-weight);q=q-tlink;printf(“n以顶点%s 为弧头的弧：“, G.xlisti.data.r); q=G.xlisti.firstin; /q指向表头结点中各结点的入弧链while(q)printf(“%s%s的权值%.1f； “, G.xlistq-tailvex.data.r, G.xlistq-headvex.data.r, q-weight);q=q-hlink;printf(“n“);elseprintf(“AOE网尚未输入，请先输入 AOE网！n“);/ 求 AOE网的关键路径并输出void searchKeyPath(OLGraph G, int topo) int i;float veMAX, vlMAX; / 顶点的最早发生时间和最晚发生时间float max, min; /活动的时间余量int