案例例题: 假设某公司要完成一个项目,项目包括以下几个任务:

  1. 任务A:设计产品原型,需要2天时间完成。
  2. 任务B:编写代码,需要4天时间完成。
  3. 任务C:测试产品,需要3天时间完成。
  4. 任务D:市场推广,需要5天时间完成。
  5. 任务E:产品发布,需要2天时间完成。

任务之间存在如下的依赖关系:

  1. 任务A必须在任务B之前完成。
  2. 任务B必须在任务C之前完成。
  3. 任务C必须在任务D之前完成。
  4. 任务D必须在任务E之前完成。

要求:

  1. 根据上述任务和依赖关系,确定关键路径。
  2. 使用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"。你也可以根据需要修改任务和依赖关系的信息,然后重新运行程序进行计算

给出一个关键路径的案例例题并运用数据结构知识编写一个C语言代码要求有输入。

原文地址: http://www.cveoy.top/t/topic/hWJq 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录