/* 马的遍历及其复杂性分析*/#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 type char r3;/顶点值VertexType;typedef struct VexNode VertexType data;ArcNode *firstin, *firstout; /分别指向该顶点第一条入弧 和出弧VexNode;/ 定义十字链表类型typedef struct VexNode 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) do printf(“分别输入顶点和弧的个数（用空格键隔开）：“);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; else printf(“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“); else printf(“AOE 网尚未输入，请先输入 AOE 网！n“);/ 求 AOE 网的关键路径并输出void searchKeyPath(OLGraph G, int topo) int i; float veMAX, vlMAX;/ 顶点的最早发生时间和最晚发生时间 float max, min;/活动的时间余量int arcHeadPoi, arcRearPoi; ArcNode *p;if(G.vexnum0) / 顶点的最早发生时间=max（弧尾顶点的最早发生时间+弧长） / 如果没有以该顶点为弧头的弧，则该顶点的最早发生时间为 0for(i=0; itailvex+p-weight; p=p-hlink;while(p) if(max tailvex+p-weight) max=vep-tailvex+p-weight;p=p-hlink; vearcHeadPoi=max; else vearcHeadPoi=0; / 顶点的最晚发生时间=min（弧头顶点的最晚发生时间-弧长） / 如果没有以该顶点为弧尾的弧，则该顶点的最晚发生时间即为其最早发生时间for(i=G.vexnum-1; i=0; i-) arcRearPoi=topoi;p=G.xlistarcRearPoi.firstout;if(p) min=vlp-headvex-p-weight; p=p-tlink;while(p) if(min vlp-headvex-p-weight) min = vlp-headvex-p-weight;p=p-tlink; vlarcRearPoi=min; else vlarcRearPoi=vearcRearPoi; / 输出所有顶点的最早和最晚发生时间for(i=0; itailvex; arcHeadPoi=p-headvex;/ 找到一个符合条件的弧结点，则输出该弧if( vearcRearPoi+p-weight = vlarcHeadPoi ) printf(“%c%cn“, G.xlistarcRearPoi.data, G.xlistarcHeadPoi.data);p=p-tlink;/ p 指向同弧尾的下一个弧结点 else printf(“AOE 网尚未输入，请先输入 AOE 网！n“);/ 菜单void menu() printf(“ntt 求 AOE 网的关键路径 “);printf(“ntt*“); printf(“ntt* 1 输入 AOE 网 *“); printf(“ntt* 2 输出 AOE 网的十字链表存储结构 *“); printf(“ntt* 3 求 AOE 网的关键路径并输出 *“); printf(“ntt* 0 退出程序 *“);printf(“ntt*“); void main() OLGraph G; int select; int indegreeMAX; int topoMAX;/ 初始化 AOE 网的十字链表结构G.vexnum=-1;while(1) menu();printf(“ntt 请选择菜单号(0-3): “);scanf(“%d“, switch(select) case 1: createDG(G, indegree, topo); break; case 2: printfOLGraph(G); break; case