数据结构课程设计参考答案.doc

1、/* 马的遍历及其复杂性分析 */ #include #define MAX 16 int 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(chess

2、x-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

3、*/ int jump(int chessMAX, int rowNum, int colNum, int x, int y) int s9, a9; int min, i, j, k; count+; step+; chessxy=step; /* 如果已经走到了 rowNum colNum 的话，表示满足结束条件，返回 1 */ if(step=rowNum*colNum) return 1; /* 计算 (x， y)处下一步的八个位置上，每个位置上可以继续进行跳跃的方向数 */ s1=nextStepNum(chess, x-2, y+1); s2=nextStepNum(chess,

4、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 /弧的尾和头顶点位

5、置 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; /有向图的当前顶点数和弧数 O

6、LGraph; / 确定 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

7、,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=weigh

8、t; 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) brea

9、k; 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

10、 为弧头的弧： “, 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（弧尾顶点的最早发生时间 +弧长） / 如果没有以该顶点为弧头的弧，则该顶点的最早发生时间为 0 for(i=0; itailvex+p-weight; p=p-hlink; while(p)