typedef关键的作用是什么,和define有什么区别
时间: 2024-06-04 19:11:03 浏览: 17
typedef关键字用于给一种已经存在的数据类型定义一个新的名称,以方便程序的阅读和理解。通过typedef定义的新类型名可以被作为一种数据类型来使用,而且可以被多次使用。
define关键字用于定义常量或者宏,可以用来定义数据类型、函数和其他程序元素。但是,define不能定义新的数据类型,只能用来给一个名称定义一个常量或宏。此外,define定义的常量或宏在程序中可以被直接使用,而typedef定义的新类型名必须先定义才能使用。
相关问题
c语言实现有向网的关键路径
关键路径是指在一个有向无环图中,从起点到终点的最长路径。关键路径上的每个节点都是整个图中的关键节点,这些节点的最早开始时间和最迟开始时间相等。
下面是使用 C 语言实现有向网的关键路径的一般步骤:
1. 定义有向网的数据结构,包括节点、边和权值等信息。
2. 构建有向网,读入节点、边和权值等信息,保存到数据结构中。
3. 计算每个节点的最早开始时间(EST)和最迟开始时间(LST)。
4. 计算每条边的最早开始时间(EET)和最迟开始时间(LET)。
5. 根据节点和边的计算结果,确定关键路径上的节点和边,输出关键路径和关键节点。
下面是一个简单的 C 语言示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_VERTEX_NUM 100 // 最大节点数量
typedef struct {
int adj; // 相邻节点编号
int weight; // 权值
} ArcNode;
typedef struct {
char name[20]; // 节点名称
int inDegree; // 入度
int outDegree; // 出度
int earliest; // 最早开始时间
int latest; // 最迟开始时间
ArcNode *adjList; // 相邻节点列表
} VertexNode;
typedef struct {
VertexNode vertex[MAX_VERTEX_NUM]; // 节点列表
int vertexNum; // 节点数量
} Graph;
void initGraph(Graph *G) {
memset(G, 0, sizeof(Graph));
}
int findVertex(Graph *G, char *name) {
for (int i = 0; i < G->vertexNum; i++) {
if (strcmp(G->vertex[i].name, name) == 0) {
return i;
}
}
return -1;
}
void addVertex(Graph *G, char *name) {
if (findVertex(G, name) != -1) {
return;
}
strcpy(G->vertex[G->vertexNum].name, name);
G->vertexNum++;
}
void addEdge(Graph *G, char *start, char *end, int weight) {
int i = findVertex(G, start);
int j = findVertex(G, end);
if (i == -1 || j == -1) {
return;
}
ArcNode *p = (ArcNode*)malloc(sizeof(ArcNode));
p->adj = j;
p->weight = weight;
p->next = G->vertex[i].adjList;
G->vertex[i].adjList = p;
G->vertex[j].inDegree++;
G->vertex[i].outDegree++;
}
int topologicalSort(Graph *G, int *topoSeq) {
int n = 0;
int *inDegree = (int*)malloc(sizeof(int) * G->vertexNum);
memset(inDegree, 0, sizeof(int) * G->vertexNum);
for (int i = 0; i < G->vertexNum; i++) {
inDegree[i] = G->vertex[i].inDegree;
}
int *stack = (int*)malloc(sizeof(int) * G->vertexNum);
int top = -1;
for (int i = 0; i < G->vertexNum; i++) {
if (inDegree[i] == 0) {
stack[++top] = i;
}
}
while (top != -1) {
int i = stack[top--];
topoSeq[n++] = i;
for (ArcNode *p = G->vertex[i].adjList; p; p = p->next) {
int j = p->adj;
if (--inDegree[j] == 0) {
stack[++top] = j;
}
}
}
free(inDegree);
free(stack);
if (n == G->vertexNum) {
return 1;
} else {
return 0;
}
}
int criticalPath(Graph *G) {
int *topoSeq = (int*)malloc(sizeof(int) * G->vertexNum);
if (!topologicalSort(G, topoSeq)) {
return 0;
}
for (int i = 0; i < G->vertexNum; i++) {
G->vertex[topoSeq[i]].earliest = 0;
}
for (int i = 0; i < G->vertexNum; i++) {
int j = topoSeq[i];
for (ArcNode *p = G->vertex[j].adjList; p; p = p->next) {
int k = p->adj;
int t = G->vertex[j].earliest + p->weight;
if (t > G->vertex[k].earliest) {
G->vertex[k].earliest = t;
}
}
}
int end = topoSeq[G->vertexNum - 1];
G->vertex[end].latest = G->vertex[end].earliest;
for (int i = G->vertexNum - 2; i >= 0; i--) {
int j = topoSeq[i];
G->vertex[j].latest = G->vertex[end].latest;
for (ArcNode *p = G->vertex[j].adjList; p; p = p->next) {
int k = p->adj;
int t = G->vertex[k].latest - p->weight;
if (t < G->vertex[j].latest) {
G->vertex[j].latest = t;
}
}
}
int critical = 0;
for (int i = 0; i < G->vertexNum; i++) {
for (ArcNode *p = G->vertex[i].adjList; p; p = p->next) {
int j = p->adj;
int eet = G->vertex[i].earliest;
int let = G->vertex[j].latest - p->weight;
if (eet == let) {
printf("%s -> %s is a critical edge.\n", G->vertex[i].name, G->vertex[j].name);
critical = 1;
}
}
}
free(topoSeq);
return critical;
}
int main() {
Graph G;
initGraph(&G);
addVertex(&G, "A");
addVertex(&G, "B");
addVertex(&G, "C");
addVertex(&G, "D");
addVertex(&G, "E");
addEdge(&G, "A", "B", 3);
addEdge(&G, "A", "C", 2);
addEdge(&G, "B", "D", 4);
addEdge(&G, "C", "D", 5);
addEdge(&G, "B", "E", 6);
addEdge(&G, "D", "E", 1);
if (!criticalPath(&G)) {
printf("There is no critical path.\n");
}
return 0;
}
```
上述代码实现了有向网的关键路径,包括了关键路径上的节点和边的计算,以及输出关键路径和关键节点。
使用邻接表和拓扑排序算法求关键路径
下面是一个使用邻接表和拓扑排序算法求关键路径的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100
#define INFINITY 65535
// 邻接表中的边结构体
typedef struct ArcNode {
int adjvex; // 该边指向的顶点编号
int weight; // 该边的权重
struct ArcNode *next; // 指向下一条边的指针
} ArcNode;
// 邻接表中的顶点结构体
typedef struct VertexNode {
int data; // 顶点编号
ArcNode *firstarc; // 指向第一条边的指针
} VertexNode;
// 邻接表结构体
typedef struct {
VertexNode vertices[MAX_VERTEX_NUM]; // 顶点数组
int vexnum, arcnum; // 顶点数和边数
} ALGraph;
// 拓扑排序中的栈结构体
typedef struct {
int *data; // 存储栈中的元素
int top; // 栈顶指针
int size; // 栈的最大容量
} Stack;
// 创建邻接表
void createGraph(ALGraph *G)
{
int i, j, k, weight;
ArcNode *p;
printf("请输入顶点数和边数:");
scanf("%d %d", &G->vexnum, &G->arcnum);
// 初始化邻接表
for (i = 0; i < G->vexnum; i++) {
G->vertices[i].data = i;
G->vertices[i].firstarc = NULL;
}
// 读入边的信息,建立邻接表
for (k = 0; k < G->arcnum; k++) {
printf("请输入边的起点、终点和权重:");
scanf("%d %d %d", &i, &j, &weight);
// 添加一条从i到j的边
p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = j;
p->weight = weight;
p->next = G->vertices[i].firstarc;
G->vertices[i].firstarc = p;
}
}
// 拓扑排序
int topologicalSort(ALGraph G, int ve[])
{
int i, j;
int count = 0;
int indegree[MAX_VERTEX_NUM] = {0}; // 存储每个顶点的入度
int *stack = (int *)malloc(sizeof(int) * G.vexnum); // 存储拓扑排序中的顶点
int top = -1;
// 计算每个顶点的入度
for (i = 0; i < G.vexnum; i++) {
for (ArcNode *p = G.vertices[i].firstarc; p != NULL; p = p->next) {
indegree[p->adjvex]++;
}
}
// 将入度为0的顶点入栈
for (i = 0; i < G.vexnum; i++) {
if (indegree[i] == 0) {
stack[++top] = i;
}
}
// 依次弹出栈顶顶点,更新其邻接点的入度,入度为0的顶点入栈
while (top != -1) {
i = stack[top--];
count++;
// 更新所有以i为起点的邻接点的入度
for (ArcNode *p = G.vertices[i].firstarc; p != NULL; p = p->next) {
j = p->adjvex;
if (--indegree[j] == 0) {
stack[++top] = j;
}
// 更新该邻接点的最早开始时间
if (ve[i] + p->weight > ve[j]) {
ve[j] = ve[i] + p->weight;
}
}
}
if (count != G.vexnum) {
return 0; // 有环
} else {
return 1; // 无环
}
}
// 计算关键路径
void criticalPath(ALGraph G)
{
int i, j;
int vl[MAX_VERTEX_NUM]; // 存储每个顶点的最晚开始时间
int ve[MAX_VERTEX_NUM] = {0}; // 存储每个顶点的最早开始时间
ArcNode *p;
// 计算每个顶点的最早开始时间
if (!topologicalSort(G, ve)) {
printf("该图存在环,无法计算关键路径!\n");
return;
}
// 计算每个顶点的最晚开始时间
for (i = 0; i < G.vexnum; i++) {
vl[i] = ve[G.vexnum - 1];
}
for (i = G.vexnum - 2; i >= 0; i--) {
for (p = G.vertices[i].firstarc; p != NULL; p = p->next) {
j = p->adjvex;
if (vl[j] - p->weight < vl[i]) {
vl[i] = vl[j] - p->weight;
}
}
}
// 输出关键路径
printf("关键路径为:");
for (i = 0; i < G.vexnum; i++) {
for (p = G.vertices[i].firstarc; p != NULL; p = p->next) {
j = p->adjvex;
if (ve[i] + p->weight == vl[j]) {
printf("%d->%d ", i, j);
}
}
}
printf("\n");
}
int main()
{
ALGraph G;
createGraph(&G);
criticalPath(G);
return 0;
}
```
在该示例代码中,使用拓扑排序算法计算每个顶点的最早开始时间和最晚开始时间,并根据它们的差值来找到关键路径。在实际应用中,还需要考虑多个关键路径的情况,以及如何处理并发活动等问题。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)