给出一个关键路径的案例例题并运用数据结构知识编写一个C语言代码要求有输入。
案例例题: 假设某公司要完成一个项目,项目包括以下几个任务:
- 任务A:设计产品原型,需要2天时间完成。
- 任务B:编写代码,需要4天时间完成。
- 任务C:测试产品,需要3天时间完成。
- 任务D:市场推广,需要5天时间完成。
- 任务E:产品发布,需要2天时间完成。
任务之间存在如下的依赖关系:
- 任务A必须在任务B之前完成。
- 任务B必须在任务C之前完成。
- 任务C必须在任务D之前完成。
- 任务D必须在任务E之前完成。
要求:
- 根据上述任务和依赖关系,确定关键路径。
- 使用C语言编写一个程序,可以输入任务和依赖关系的信息,然后计算关键路径并输出。
C语言代码示例:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_TASKS 10
typedef struct {
char name[10];
int duration;
int earliestStart;
int earliestFinish;
int latestStart;
int latestFinish;
} Task;
typedef struct {
int taskCount;
Task tasks[MAX_TASKS];
int dependencyMatrix[MAX_TASKS][MAX_TASKS];
} Project;
void initialize(Project *project) {
project->taskCount = 0;
memset(project->dependencyMatrix, 0, sizeof(project->dependencyMatrix));
}
void addTask(Project *project, char *name, int duration) {
if (project->taskCount >= MAX_TASKS) {
printf("Maximum number of tasks exceeded.\n");
return;
}
Task newTask;
strcpy(newTask.name, name);
newTask.duration = duration;
project->tasks[project->taskCount] = newTask;
project->taskCount++;
}
void addDependency(Project *project, int fromIndex, int toIndex) {
if (fromIndex < 0 || fromIndex >= project->taskCount || toIndex < 0 || toIndex >= project->taskCount) {
printf("Invalid task index.\n");
return;
}
project->dependencyMatrix[fromIndex][toIndex] = 1;
}
void calculateEarliestTimes(Project *project) {
for (int i = 0; i < project->taskCount; i++) {
Task *task = &project->tasks[i];
task->earliestStart = 0;
for (int j = 0; j < project->taskCount; j++) {
if (project->dependencyMatrix[j][i] == 1) {
int totalTime = project->tasks[j].earliestFinish;
if (totalTime > task->earliestStart) {
task->earliestStart = totalTime;
}
}
}
task->earliestFinish = task->earliestStart + task->duration;
}
}
void calculateLatestTimes(Project *project) {
project->tasks[project->taskCount - 1].latestFinish = project->tasks[project->taskCount - 1].earliestFinish;
project->tasks[project->taskCount - 1].latestStart = project->tasks[project->taskCount - 1].latestFinish - project->tasks[project->taskCount - 1].duration;
for (int i = project->taskCount - 2; i >= 0; i--) {
Task *task = &project->tasks[i];
task->latestFinish = project->tasks[project->taskCount - 1].latestStart;
task->latestStart = task->latestFinish - task->duration;
for (int j = i + 1; j < project->taskCount; j++) {
if (project->dependencyMatrix[i][j] == 1) {
int totalTime = project->tasks[j].latestStart;
if (totalTime < task->latestFinish) {
task->latestFinish = totalTime;
task->latestStart = task->latestFinish - task->duration;
}
}
}
}
}
void printCriticalPath(Project *project) {
printf("Critical path:\n");
for (int i = 0; i < project->taskCount; i++) {
Task *task = &project->tasks[i];
if (task->earliestStart == task->latestStart && task->earliestFinish == task->latestFinish) {
printf("%s ", task->name);
}
}
printf("\n");
}
int main() {
Project project;
initialize(&project);
addTask(&project, "A", 2);
addTask(&project, "B", 4);
addTask(&project, "C", 3);
addTask(&project, "D", 5);
addTask(&project, "E", 2);
addDependency(&project, 0, 1);
addDependency(&project, 1, 2);
addDependency(&project, 2, 3);
addDependency(&project, 3, 4);
calculateEarliestTimes(&project);
calculateLatestTimes(&project);
printCriticalPath(&project);
return 0;
}
运行以上代码,将输出关键路径:"A B C D E"。你也可以根据需要修改任务和依赖关系的信息,然后重新运行程序进行计算
原文地址: http://www.cveoy.top/t/topic/hWJq 著作权归作者所有。请勿转载和采集!