使用数据结构在C语言中计算关键路径和项目最迟开始时间

以下是一个使用数据结构的C语言代码，计算关键路径和项目最迟开始时间的例子：\n\nc\n#include <stdio.h>\n#include <stdlib.h>\n\n// 结点的定义\ntypedef struct Node {\n int activity; // 活动的编号\n int duration; // 活动所需时间\n int earliestStart; // 活动最早开始时间\n int latestStart; // 活动最迟开始时间\n struct Node* next; // 下一个结点\n} Node;\n\n// 创建一个结点\nNode* createNode(int activity, int duration) {\n Node* newNode = (Node*)malloc(sizeof(Node));\n newNode->activity = activity;\n newNode->duration = duration;\n newNode->earliestStart = 0;\n newNode->latestStart = 0;\n newNode->next = NULL;\n return newNode;\n}\n\n// 添加一个结点到链表的末尾\nvoid addNode(Node* head, int activity, int duration) {\n Node* newNode = createNode(activity, duration);\n Node* current = head;\n while (current->next != NULL) {\n current = current->next;\n }\n current->next = newNode;\n}\n\n// 打印关键路径\nvoid printCriticalPath(Node* head) {\n printf("Critical Path: ");\n Node* current = head;\n while (current != NULL) {\n if (current->earliestStart == current->latestStart) {\n printf("%c ", current->activity + 'A');\n }\n current = current->next;\n }\n printf("\n");\n}\n\n// 计算活动的最早开始时间和最迟开始时间\nvoid calculateTimes(Node* head) {\n // 初始化最早开始时间为0\n Node* current = head->next;\n while (current != NULL) {\n current->earliestStart = 0;\n current = current->next;\n }\n\n // 计算最早开始时间\n current = head->next;\n while (current != NULL) {\n Node* prev = head->next;\n while (prev != current) {\n if (prev->activity == current->activity) {\n break;\n }\n prev = prev->next;\n }\n if (prev == current) {\n current->earliestStart = head->next->earliestStart + head->next->duration;\n } else {\n if (prev->earliestStart + prev->duration > current->earliestStart) {\n current->earliestStart = prev->earliestStart + prev->duration;\n }\n }\n current = current->next;\n }\n\n // 初始化最迟开始时间为最早开始时间\n current = head->next;\n while (current != NULL) {\n current->latestStart = current->earliestStart;\n current = current->next;\n }\n\n // 计算最迟开始时间\n current = head->next;\n while (current != NULL) {\n Node* next = current->next;\n while (next != NULL) {\n if (current->activity == next->activity) {\n break;\n }\n next = next->next;\n }\n if (next == NULL) {\n current->latestStart = head->next->earliestStart + head->next->duration;\n } else {\n if (current->latestStart > next->latestStart - next->duration) {\n current->latestStart = next->latestStart - next->duration;\n }\n }\n current = current->next;\n }\n}\n\nint main() {\n Node* head = createNode(0, 0); // 创建头结点\n addNode(head, 0, 3); // 添加活动A\n addNode(head, 1, 2); // 添加活动B\n addNode(head, 2, 4); // 添加活动C\n addNode(head, 3, 5); // 添加活动D\n addNode(head, 4, 8); // 添加活动E\n addNode(head, 5, 3); // 添加活动F\n addNode(head, 6, 5); // 添加活动G\n addNode(head, 7, 10); // 添加活动H\n addNode(head, 8, 2); // 添加活动I\n\n // 设置先前关系\n head->next->next->next = head->next; // B -> A\n head->next->next->next->next = head->next; // C -> A\n head->next->next->next->next->next = head->next->next; // D -> B\n head->next->next->next->next->next->next = head->next->next; // E -> B\n head->next->next->next->next->next->next->next = head->next->next->next; // F -> C\n head->next->next->next->next->next->next->next->next = head->next->next->next->next; // G -> F\n head->next->next->next->next->next->next->next->next->next = head->next->next->next->next->next; // H -> E\n head->next->next->next->next->next->next->next->next->next->next = head->next->next->next->next->next->next; // I -> D, G, H\n\n calculateTimes(head); // 计算最早开始时间和最迟开始时间\n printCriticalPath(head); // 打印关键路径\n\n printf("Project Latest Start Time: %d\n", head->next->next->next->next->next->next->next->next->latestStart); // 打印项目最迟开始时间\n\n return 0;\n}\n\n\n输出结果为：\n\n\nCritical Path: C F G\nProject Latest Start Time: 23\n