C语言关键路径算法实现 - 优化项目进度

#include<stdio.h>\n#include<stdlib.h>\n\n/// 定义活动的结构体\n\t\t\t\t\t\t\t\t\t\ttypedef struct {\n\t\t\t\t\t\t\t\t\t\t\tchar name;\n\t\t\t\t\t\t\t\t\t\t\tint duration;\n\t\t\t\t\t\t\t\t\t\t\tint earliestStart;\n\t\t\t\t\t\t\t\t\t\t\tint latestStart;\n\t\t\t\t\t\t\t\t\t\t\tint critical;\n\t\t\t\t\t\t\t\t\t\t\tint numOfPredecessors;\n\t\t\t\t\t\t\t\t\t\t\tchar predecessors;\n\t\t\t\t\t\t\t\t\t} Activity;\n\n/// 计算关键路径的函数\n\t\t\t\t\t\t\t\t\t\tvoid calculateCriticalPath(Activity activities, int numActivities) {\n\t\t\t\t\t\t\t\t\t\t\tint i, j, k;\n\t\t\t\t\t\t\t\t\t\t\tint maxDuration = 0;\n\t\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t\t/// 初始化最早开始时间和最晚开始时间\n\t\t\t\t\t\t\t\t\t\t\tfor (i = 0; i < numActivities; i++) {\n\t\t\t\t\t\t\t\t\t\t\t\t\tactivities[i].earliestStart = 0;\n\t\t\t\t\t\t\t\t\t\t\t\t\tactivities[i].latestStart = INT_MAX;\n\t\t\t\t\t\t\t\t\t\t\t}\n\t\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t\t/// 计算每个活动的最早开始时间\n\t\t\t\t\t\t\t\t\t\t\tfor (i = 0; i < numActivities; i++) {\n\t\t\t\t\t\t\t\t\t\t\t\t\tfor (j = 0; j < activities[i].numOfPredecessors; j++) {\n\t\t\t\t\t\t\t\t\t\t\t\t\t\tk = activities[i].predecessors[j] - 'A';\n\t\t\t\t\t\t\t\t\t\t\t\t\t\tif (activities[k].duration + activities[k].earliestStart > activities[i].earliestStart) {\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\tactivities[i].earliestStart = activities[k].duration + activities[k].earliestStart;\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t}\n\t\t\t\t\t\t\t\t\t\t\t\t}\n\t\t\t\t\t\t\t\t\t\t\t}\n\t\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t\t/// 计算项目的最长时间\n\t\t\t\t\t\t\t\t\t\t\tfor (i = 0; i < numActivities; i++) {\n\t\t\t\t\t\t\t\t\t\t\t\t\tif (activities[i].duration + activities[i].earliestStart > maxDuration) {\n\t\t\t\t\t\t\t\t\t\t\t\t\t\tmaxDuration = activities[i].duration + activities[i].earliestStart;\n\t\t\t\t\t\t\t\t\t\t\t\t\t}\n\t\t\t\t\t\t\t\t\t\t\t}\n\t\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t\t/// 计算每个活动的最晚开始时间\n\t\t\t\t\t\t\t\t\t\t\tfor (i = numActivities - 1; i >= 0; i--) {\n\t\t\t\t\t\t\t\t\t\t\t\t\tfor (j = 0; j < activities[i].numOfPredecessors; j++) {\n\t\t\t\t\t\t\t\t\t\t\t\t\t\tk = activities[i].predecessors[j] - 'A';\n\t\t\t\t\t\t\t\t\t\t\t\t\t\tif (activities[i].latestStart - activities[i].duration < activities[k].latestStart) {\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\tactivities[k].latestStart = activities[i].latestStart - activities[i].duration;\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t}\n\t\t\t\t\t\t\t\t\t\t\t\t}\n\t\t\t\t\t\t\t\t\t\t\t}\n\t\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t\t/// 标记关键路径\n\t\t\t\t\t\t\t\t\t\t\tfor (i = 0; i < numActivities; i++) {\n\t\t\t\t\t\t\t\t\t\t\t\t\tif (activities[i].earliestStart == activities[i].latestStart) {\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\tactivities[i].critical = 1;\n\t\t\t\t\t\t\t\t\t\t\t\t\t} else {\n\t\t\t\t\t\t\t\t\t\t\t\t\t\tactivities[i].critical = 0;\n\t\t\t\t\t\t\t\t\t\t\t\t\t}\n\t\t\t\t\t\t\t\t\t\t\t}\n\t\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t\t/// 输出关键路径\n\t\t\t\t\t\t\t\t\t\t\tprintf("关键路径为：");\n\t\t\t\t\t\t\t\t\t\t\tfor (i = 0; i < numActivities; i++) {\n\t\t\t\t\t\t\t\t\t\t\t\t\tif (activities[i].critical) {\n\t\t\t\t\t\t\t\t\t\t\t\t\t\tprintf("%c ", activities[i].name);\n\t\t\t\t\t\t\t\t\t\t\t\t\t}\n\t\t\t\t\t\t\t\t\t\t\t}\n\t\t\t\t\t\t\t\t\t\t\tprintf("\n");\n\t\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t\t/// 输出项目最迟开始时间\n\t\t\t\t\t\t\t\t\t\t\tprintf("项目最迟开始时间为：%d\n", maxDuration);\n\t\t\t\t\t\t\t\t\t\t}\n\n\tint main() {\n\t\t\t\t\t\t\t\tint numActivities = 9;\n\t\t\t\t\t\t\t\tActivity activities[numActivities];\n\t\t\t\t\t\t\t\tint i; // 声明变量i\n\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t/// 初始化活动列表\n\t\t\t\t\t\t\t\tactivities[0].name = 'A';\n\t\t\t\t\t\t\t\tactivities[0].duration = 3;\n\t\t\t\t\t\t\t\tactivities[0].numOfPredecessors = 0;\n\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\tactivities[1].name = 'B';\n\t\t\t\t\t\t\t\tactivities[1].duration = 2;\n\t\t\t\t\t\t\t\tactivities[1].numOfPredecessors = 1;\n\t\t\t\t\t\t\t\tactivities[1].predecessors = (char )malloc(sizeof(char));\n\t\t\t\t\t\t\t\t(activities[1].predecessors) = 'A';\n\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\tactivities[2].name = 'C';\n\t\t\t\t\t\t\t\tactivities[2].duration = 4;\n\t\t\t\t\t\t\t\tactivities[2].numOfPredecessors = 1;\n\t\t\t\t\t\t\t\tactivities[2].predecessors = (char )malloc(sizeof(char));\n\t\t\t\t\t\t\t\t(activities[2].predecessors) = 'A';\n\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\tactivities[3].name = 'D';\n\t\t\t\t\t\t\t\tactivities[3].duration = 5;\n\t\t\t\t\t\t\t\tactivities[3].numOfPredecessors = 1;\n\t\t\t\t\t\t\t\tactivities[3].predecessors = (char )malloc(sizeof(char));\n\t\t\t\t\t\t\t\t(activities[3].predecessors) = 'B';\n\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\tactivities[4].name = 'E';\n\t\t\t\t\t\t\t\tactivities[4].duration = 8;\n\t\t\t\t\t\t\t\tactivities[4].numOfPredecessors = 1;\n\t\t\t\t\t\t\t\tactivities[4].predecessors = (char )malloc(sizeof(char));\n\t\t\t\t\t\t\t\t(activities[4].predecessors) = 'B';\n\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\tactivities[5].name = 'F';\n\t\t\t\t\t\t\t\tactivities[5].duration = 3;\n\t\t\t\t\t\t\t\tactivities[5].numOfPredecessors = 1;\n\t\t\t\t\t\t\t\tactivities[5].predecessors = (char )malloc(sizeof(char));\n\t\t\t\t\t\t\t\t(activities[5].predecessors) = 'C';\n\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\tactivities[6].name = 'G';\n\t\t\t\t\t\t\t\tactivities[6].duration = 5;\n\t\t\t\t\t\t\t\tactivities[6].numOfPredecessors = 1;\n\t\t\t\t\t\t\t\tactivities[6].predecessors = (char )malloc(sizeof(char));\n\t\t\t\t\t\t\t\t(activities[6].predecessors) = 'F';\n\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\tactivities[7].name = 'H';\n\t\t\t\t\t\t\t\tactivities[7].duration = 10;\n\t\t\t\t\t\t\t\tactivities[7].numOfPredecessors = 1;\n\t\t\t\t\t\t\t\tactivities[7].predecessors = (char )malloc(sizeof(char));\n\t\t\t\t\t\t\t\t(activities[7].predecessors) = 'E';\n\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\tactivities[8].name = 'I';\n\t\t\t\t\t\t\t\tactivities[8].duration = 2;\n\t\t\t\t\t\t\t\tactivities[8].numOfPredecessors = 3;\n\t\t\t\t\t\t\t\tactivities[8].predecessors = (char )malloc(3 * sizeof(char));\n\t\t\t\t\t\t\t\t(activities[8].predecessors) = 'D';\n\t\t\t\t\t\t\t\t(activities[8].predecessors + 1) = 'G';\n\t\t\t\t\t\t\t\t(activities[8].predecessors + 2) = 'H';\n\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\tcalculateCriticalPath(activities, numActivities);\n\t\t\t\t\t\t\t\t/// 打印关键路径\n\t\t\t\t\t\t\t\tprintf("关键路径为：");\n\t\t\t\t\t\t\t\tfor (i = 0; i < numActivities; i++) {\n\t\t\t\t\t\t\t\t\tif (activities[i].critical) {\n\t\t\t\t\t\t\t\t\tprintf("%c ", activities[i].name);\n\t\t\t\t\t\t\t\t}\n\t\t\t\t\t\t\t\t}\n\t\t\t\t\t\t\t\tprintf("\n");\n\t\t\t\t\t\t\t\treturn 0;\n\t\t\t\t\t\t\t}\n