《2022年2022年关键路径C语言》由会员分享，可在线阅读，更多相关《2022年2022年关键路径C语言（23页珍藏版）》请在金锄头文库上搜索。
1、#include #include #include #define Maxname 5 #define Maxvexnum 20 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define Sinitsize 10 /栈存储空间初始分配#define Sincrement 2 /栈存储空间分配增量typedef char VertextypeMaxname; /顶点向名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - -
2、 名师精心整理 - - - - - - - 第 1 页，共 23 页 - - - - - - - - - 量typedef int Selemtype; typedef int Status; int veMaxvexnum; /*/ typedef struct Arcnode int adjvex; /该弧所指向的顶点的位置 struct Arcnode *nextarc; /指向下一条弧的指针 int weight; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共
3、23 页 - - - - - - - - - Arcnode; /表结点typedef struct Vertextype data; /顶点信息 Arcnode *firstarc; /第一个表结点的地址，指向第一条依附该顶点的弧的指针Vnode,AdjlistMaxvexnum; /头结点typedef struct Adjlist vertices; int vexnum,arcnum; Algraph; typedef struct Selemtype *base; Selemtype *top; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - -
4、 - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 23 页 - - - - - - - - - int stacksize; Sqstack; typedef Arcnode *Linklist;/定义指向单链表结点的指针是指向图的表结点的指针#define next nextarc/定义单链表结点的指针域是表结点指向下一条弧的指针域/*/ int Locatevex(Algraph G,Vertextype u) int i; for(i = 0; i G.vexnum; +i) if(strcmp(u,G.verticesi.data) = 0) 名师资料
5、总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 23 页 - - - - - - - - - return i; return -1; /*/ Status Listinsert(Linklist *L,int i,Arcnode *e)/在不带头结点的单链表L 中第i 个位置之前插入元素e int j = 1; Linklist p = *L,s; if(i next = *L; *L = s; else while(p & j next; j+; if(!p)/i值大于表长
6、+1 return ERROR; s-next = p-next; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 23 页 - - - - - - - - - p-next = s; return OK; /*/ void Creategraph(Algraph *G) int i,j,k,w; Vertextype V1,V2; Arcnode *e; printf(请输入图的顶点数， 边数(以空格作为间隔 ):n); scanf(%d%d,&G- vexnum,&G
7、- arcnum); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 23 页 - - - - - - - - - printf(请输入 %d个顶点的值 (小于%d个字符):n,G-vexnum,Maxname); for(i = 0; ivexnum; +i)/构造顶点向量并初始化 scanf(%s,G-verticesi.data); G-verticesi.firstarc = NULL; printf(请输入 %d条弧的弧尾，弧头和权值(以空格作为间隔 ):n,G
8、- arcnum); for(k = 0; k arcnum; +k) scanf(%s%s%d,V1,V2,&w); i = Locatevex(*G,V1); j = Locatevex(*G,V2); e = (Arcnode *)malloc(sizeof(struct Arcnode); /修正：为每条弧分配内存，插名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 23 页 - - - - - - - - - 入链表 e-weight = w; e-adjvex
9、= j; e-nextarc = NULL; Listinsert(&(G-verticesi.firstarc),1,e); /插在第 j 个元素的表头 /*/ void Display(Algraph *G) int i; Linklist p; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 23 页 - - - - - - - - - printf(%d个顶点 :,G-vexnum); for(i = 0; i vexnum; +i) printf(%s ,G-v
10、erticesi.data); printf(n%dn条弧:,G-arcnum); for(i = 0; i vexnum; +i) p = G-verticesi.firstarc; while(p) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 23 页 - - - - - - - - - printf(%5s%5s%5d,G-verticesi.data,G-verticesp-adjvex.data,p-weight); / p = p-nextarc; /
11、printf(n); /*/ void Findindegree(Algraph *G,int 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 23 页 - - - - - - - - - indegree) int i; Arcnode *p; for(i = 0; i vexnum; +i) indegreei = 0; for(i = 0; i vexnum; +i) p = G-verticesi.firstarc; while(p) indegreep-adj
12、vex+; p = p-nextarc; /*名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 23 页 - - - - - - - - - */ void Initstack(Sqstack *S) S-base = (Selemtype *)malloc(Sinitsize * sizeof (Selemtype); if(!(S-base) exit(OVERFLOW); S-top = S-base; S-stacksize = Sinitsize; Status
13、 Stackempty(Sqstack *S) if(S-top = S-base) return TRUE; else return ERROR; void Push(Sqstack *S,Selemtype e) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 23 页 - - - - - - - - - if(S-top - S-base = S-stacksize) S-base = (Selemtype *)realloc(S-base,(S-stacksiz
14、e + Sincrement) * sizeof(Selemtype); if(!(S-base) exit(OVERFLOW); S-top = S-base + S-stacksize; S-stacksize += Sincrement; *(S-top)+ = e; Status Pop(Sqstack *S,Selemtype *e) if(S-top = S-base) return ERROR; *e = *(-S-top); return OK; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 -
15、- - - - - - 第 14 页，共 23 页 - - - - - - - - - /*/ Status TopologicalOrder(Algraph *G, Sqstack *T) int Count=0; int N=0; int i,k,count=0; int indegreeMaxvexnum; Sqstack S; Arcnode *p; Findindegree(G,indegree); Initstack(&S); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - -
16、第 15 页，共 23 页 - - - - - - - - - for(i = 0; i vexnum; +i) if(indegreei=0) Push(&S,i); /入度为零者进栈 Count+; if(G-verticesi.firstarc=NULL) N+; printf(n); if(Count1) printf(图中有 %d个源点 , 不能找出关键路径!n,Count);return 0; else if(N1) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16
17、页，共 23 页 - - - - - - - - - printf(图中有 %d个汇点 , 不能找出关键路径!n,N); return 0; printf(n); printf(拓扑序列： ); Initstack(T); for(i = 0; i vexnum; +i) / vei = 0; while(!Stackempty(&S) Pop(&S,&i); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 23 页 - - - - - - - - - printf(%
18、s,G-verticesi.data); Push(T,i); +count; /对输出顶点计数 for(p = G-verticesi.firstarc; p; p = p-nextarc) k = p-adjvex; /对 i 号顶点的每个邻接点的入度减一 if(-indegreek = 0) Push(&S,k); if(vei + p-weight vek) vek = vei + p-weight; /for /while 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1
19、8 页，共 23 页 - - - - - - - - - if(count vexnum) printf(此有向网有回路 n); return 0; else return 1; /TopologicalOrder Status CriticalPath(Algraph *G) int sum=0; int vlMaxvexnum; Sqstack T; int i,j,k,ee,el,dut; Arcnode *p; if(!TopologicalOrder(G,&T) return 0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - -
20、- - - 名师精心整理 - - - - - - - 第 19 页，共 23 页 - - - - - - - - - j = ve0; for(i = 0; i vexnum; i+) if(vei j) j = vei; for(i = 0; i vexnum; i+) vli = j; while(!Stackempty(&T) for(Pop(&T,&j),p = G-verticesj.firstarc; p ; p = p-nextarc) k = p-adjvex; dut = p-weight; if(vlk - dut vlj) vlj = vlk - dut; /for pr
21、intf(ni vei vlin); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 23 页 - - - - - - - - - for(i = 0; i vexnum; +i) printf(%d %d %5d,i,vei,vli); if(vei = vli) printf( 关键路径经过的顶点); printf(n); printf(j k 权 值ee eln); for(j = 0; j vexnum; +j) / 求 ee,el和关键活动 for(p = G
22、-verticesj.firstarc; p ; p = p-nextarc) k = p-adjvex; dut = p-weight; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 23 页 - - - - - - - - - ee = vej; el = vlk - dut; printf(%s-%s %3d %5d %5d ,G-verticesj.data,G-verticesk.data,dut,ee,el); if(ee = el) printf(关键活
23、动 ); printf(n); /for j-; printf(路径长度为 :%d,vej); printf(n); return 1; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 22 页，共 23 页 - - - - - - - - - void main() Algraph h; Creategraph(&h); Display(&h); CriticalPath(&h); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 23 页，共 23 页 - - - - - - - - -
