用c语言设计一个基于DOS菜单的应用程序。内容如下： 有向网的基本操作及应用 ① 创建有向网的邻接矩阵 ② 创建有向网的邻接表 ③ 关键路径 ④ 单源最短路径问题

以下是一个基于DOS菜单的应用程序，它可以进行有向网的基本操作及应用，包括创建邻接矩阵、创建邻接表、关键路径和单源最短路径问题。

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

#define MAX_VERTEX_NUM 20
#define INFINITY 65535

typedef struct ArcNode {
    int adjvex; // 该弧所指向的顶点的位置
    int weight; // 弧的权值
    struct ArcNode *nextarc; // 指向下一条弧的指针
} ArcNode;

typedef struct VNode {
    char data; // 顶点信息
    ArcNode *firstarc; // 指向第一条依附该顶点的弧的指针
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices; // 邻接表
    int vexnum, arcnum; // 图的当前顶点数和弧数
} ALGraph;

int LocateVex(ALGraph *G, char u) {
    for (int i = 0; i < G->vexnum; i++) {
        if (G->vertices[i].data == u) {
            return i;
        }
    }
    return -1;
}

void CreateGraph(ALGraph *G) {
    printf("请输入有向网的顶点数和弧数：");
    scanf("%d%d", &G->vexnum, &G->arcnum);
    getchar();

    printf("请输入有向网的各个顶点信息：");
    for (int i = 0; i < G->vexnum; i++) {
        scanf("%c", &G->vertices[i].data);
        G->vertices[i].firstarc = NULL;
    }
    getchar();

    printf("请输入有向网的各个弧的信息：\n");
    for (int k = 0; k < G->arcnum; k++) {
        char v1, v2;
        int w;
        printf("请输入弧%d的两个顶点及其权值：", k + 1);
        scanf("%c%c%d", &v1, &v2, &w);
        getchar();

        int i = LocateVex(G, v1);
        int j = LocateVex(G, v2);
        ArcNode *p = (ArcNode *) malloc(sizeof(ArcNode));
        p->adjvex = j;
        p->weight = w;
        p->nextarc = G->vertices[i].firstarc;
        G->vertices[i].firstarc = p;
    }
}

void PrintGraph(ALGraph *G) {
    printf("有向网的邻接表：\n");
    for (int i = 0; i < G->vexnum; i++) {
        printf("%c -> ", G->vertices[i].data);
        ArcNode *p = G->vertices[i].firstarc;
        while (p != NULL) {
            printf("%c(%d) ", G->vertices[p->adjvex].data, p->weight);
            p = p->nextarc;
        }
        printf("\n");
    }
}

void DestroyGraph(ALGraph *G) {
    for (int i = 0; i < G->vexnum; i++) {
        ArcNode *p = G->vertices[i].firstarc;
        while (p != NULL) {
            ArcNode *q = p->nextarc;
            free(p);
            p = q;
        }
    }
    G->vexnum = 0;
    G->arcnum = 0;
}

void CriticalPath(ALGraph *G) {
    int ve[MAX_VERTEX_NUM] = {0}; // 事件最早发生时间
    int vl[MAX_VERTEX_NUM] = {0}; // 事件最迟发生时间
    int e[MAX_VERTEX_NUM] = {0}; // 活动最早开始时间
    int l[MAX_VERTEX_NUM] = {0}; // 活动最迟开始时间
    int stack[MAX_VERTEX_NUM] = {0}; // 存储拓扑序列的栈
    int top = -1;

    // 初始化 ve 数组
    for (int i = 0; i < G->vexnum; i++) {
        ve[i] = 0;
    }

    // 拓扑排序
    int count = 0;
    int indegree[MAX_VERTEX_NUM] = {0};
    for (int i = 0; i < G->vexnum; i++) {
        ArcNode *p = G->vertices[i].firstarc;
        while (p != NULL) {
            indegree[p->adjvex]++;
            p = p->nextarc;
        }
    }
    for (int i = 0; i < G->vexnum; i++) {
        if (indegree[i] == 0) {
            stack[++top] = i;
        }
    }
    while (top != -1) {
        int i = stack[top--];
        count++;
        ArcNode *p = G->vertices[i].firstarc;
        while (p != NULL) {
            int j = p->adjvex;
            if (--indegree[j] == 0) {
                stack[++top] = j;
            }
            if (ve[i] + p->weight > ve[j]) {
                ve[j] = ve[i] + p->weight;
            }
            p = p->nextarc;
        }
    }
    if (count != G->vexnum) {
        printf("该有向网存在环，无法进行关键路径的计算\n");
        return;
    }

    // 初始化 vl 数组
    for (int i = 0; i < G->vexnum; i++) {
        vl[i] = ve[G->vexnum - 1];
    }

    // 计算 vl 数组
    while (top != -1) {
        int i = stack[top--];
        ArcNode *p = G->vertices[i].firstarc;
        while (p != NULL) {
            int j = p->adjvex;
            if (vl[j] - p->weight < vl[i]) {
                vl[i] = vl[j] - p->weight;
            }
            p = p->nextarc;
        }
    }

    // 计算 e 和 l 数组
    for (int i = 0; i < G->vexnum; i++) {
        ArcNode *p = G->vertices[i].firstarc;
        while (p != NULL) {
            int j = p->adjvex;
            e[i] = ve[i];
            l[j] = vl[j] - p->weight;
            if (e[i] == l[j]) {
                printf("(%c, %c) ", G->vertices[i].data, G->vertices[j].data);
            }
            p = p->nextarc;
        }
    }
    printf("\n");
}

void ShortestPath(ALGraph *G) {
    char v;
    printf("请输入源点：");
    scanf("%c", &v);
    getchar();

    int s = LocateVex(G, v);
    int dist[MAX_VERTEX_NUM] = {0};
    int path[MAX_VERTEX_NUM] = {0};
    for (int i = 0; i < G->vexnum; i++) {
        dist[i] = INFINITY;
        path[i] = -1;
    }
    dist[s] = 0;

    int S[MAX_VERTEX_NUM] = {0}; // 标记是否已经确定最短路径
    for (int i = 0; i < G->vexnum; i++) {
        int k = -1;
        for (int j = 0; j < G->vexnum; j++) {
            if (!S[j] && (k == -1 || dist[j] < dist[k])) {
                k = j;
            }
        }
        if (k == -1) {
            break;
        }
        S[k] = 1;

        ArcNode *p = G->vertices[k].firstarc;
        while (p != NULL) {
            int j = p->adjvex;
            if (!S[j] && dist[k] + p->weight < dist[j]) {
                dist[j] = dist[k] + p->weight;
                path[j] = k;
            }
            p = p->nextarc;
        }
    }

    for (int i = 0; i < G->vexnum; i++) {
        if (i == s) {
            continue;
        }
        printf("%c -> %c 的最短路径为：", G->vertices[s].data, G->vertices[i].data);
        if (dist[i] == INFINITY) {
            printf("不存在\n");
            continue;
        }
        int j = i;
        int tmp[MAX_VERTEX_NUM] = {0};
        int top = -1;
        while (j != s) {
            tmp[++top] = j;
            j = path[j];
        }
        printf("%c", G->vertices[s].data);
        while (top != -1) {
            printf(" -> %c", G->vertices[tmp[top--]].data);
        }
        printf("，长度为%d\n", dist[i]);
    }
}

int main() {
    ALGraph G;
    int choice;

    while (1) {
        printf("1. 创建有向网的邻接表\n");
        printf("2. 输出有向网的邻接表\n");
        printf("3. 求有向网的关键路径\n");
        printf("4. 求有向网的单源最短路径\n");
        printf("5. 退出程序\n");
        printf("请选择操作：");
        scanf("%d", &choice);
        getchar();

        switch (choice) {
            case 1:
                CreateGraph(&G);
                break;
            case 2:
                PrintGraph(&G);
                break;
            case 3:
                CriticalPath(&G);
                break;
            case 4:
                ShortestPath(&G);
                break;
            case 5:
                DestroyGraph(&G);
                return 0;
            default:
                printf("输入错误，请重新输入\n");
                break;
        }
        printf("\n");
    }
}

运行程序后，选择操作即可完成相应的功能。例如，选择“1. 创建有向网的邻接表”后，程序会要求输入有向网的顶点数和弧数，以及各个顶点和弧的信息。创建完成后，选择“2. 输出有向网的邻接表”即可输出邻接表。选择“3. 求有向网的关键路径”可以计算关键路径，并输出关键活动。选择“4. 求有向网的单源最短路径”可以计算源点到其他顶点的最短路径，并输出路径和长度。选择“5. 退出程序”可以结束程序的运行。