阅读下列函数说明和C代码,将应填入 (n) 处的字句写在对应栏内。
[说明]
函数int Toplogical(LinkedWDigraph G)的功能是对图G中的顶点进行拓扑排序,并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE网,图中顶点从1~n依次编号,图G的存储结构采用邻接表表示,其数据类型定义如下:
typedef struct Gnode /*邻接表的表结点类型*/
int adjvex; /*邻接顶点编号*/
int weight; /*弧上的权值*/
struct Gnode*nextarc;/*指示下一个弧的结点*/
Gnode;
typedef struct Adj list /*邻接表的头结点类型*/
char vdata; /*顶点的数据信息*/
struct Gnode *Firstadj;/*指向邻接表的第一个表结点*/
Adjulist;
typedef struct LinkedWDigraph/*图的类型*/
int n,e; /*图中顶点个数和边数*/
struct Adjlist *head; /*指向图中第一个顶点的邻接表的头结点*/
LinkedWDigraph;
例如,某AOE网如图21-1所示,其邻接表存储结构如图21-2所示。
[本题函数]
int Toplogical(LinkedWDigraph G)
Gnode *p;
int j,W,top=0;
int *Stack,*ve,*indegree;
ve=(int *)malloc((G.n+1) *sizeof(int));
indegree=(int*)maZZoc((G.n+1)*sizeof(int));/*存储网中各顶点的入度*/
Stack=(int*)malloc((G.n+1)*sizeof(int));/*存储入度为0的顶点的编号*/
if(!ve||!indegree||!Stack)exit(0);
for(j=1;j<=G.n;j++)
ve[j]=0;indegree[j]=0;
/*for*/
for(j=1;j<=G.n;j++) /*求网中各顶点的入度*/
p=G.head[j].Firstadj;
while(p)
(1) ;p=p->nextarc;
/*while*/
/*for*/
for(j=1;j<=G.n;j++) /*求网中入度为0的顶点并保存其编号*/
if(!indegree[j]) stack[++top]=j;
while(top>0)
w= (2) ;
printf("%c ",G.head[w].vdata);
p=G.head[w].Firstadj;
while(p)
(3) ;
if(!indegree[p->adjvex])
Stack[++top]=p->adjvex;
if( (4) )
ve[p->adjvex]=ve[w]+p->weight;
p=p->nextarc;
/*while*/
/*while*/
return (5) ;
/*Toplogical*/
(2)处填()。