2004年下半年下午C语言设计考题

2014年1月2日 作者： 来源：

　　阅读下列函数说明和C代码，将应填入（n）处的字句写在答题纸的对应栏内。
　【说明】
　　函数int Toplogical （LinkedWDigraph G）的功能是对图G中的顶点进行拓扑排序，并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE－网，图中顶点从1～n依次编号，图G的存储结构采用邻接表表示，其数据类型定义如下：
　　typedef struct Gnode{ 　　　　/*邻接表的表结点类型*/
　　　int adjvex;　　　　　　　　/*邻接顶点编号*/
　　　int weight;　　　　　　　　/*弧上的权值*/
　　　struct Gonde*nextare;　　　 /*指示下一个弧的结点*/
　　}Gnode;
　　typedef struct Adjlist{ 　　　/*邻接表的头结点类型*/
　　　char vdata;　　　　　　　　  /*顶点的数据信息*/
　　　struct Gnode*Firstadj;　　　/*指向邻接表的第一个表结点*/
　　}Adjlist;
　　typedef struct LinkedWDigraph{ 　/*图的类型*/
　　　int n ,e;　　　　　　　　　　/*图中顶点个数和边数*/
　　　struct Adjlist head;　　　　　/*指向图中第一个顶点的邻接表的头结点*/
　　}LinkedWDigraph;
　　例如，某AOE-网如图5-1所示，其邻接表存储结构如图5-2所示。
 
 　【函数】
　　int Toplogical(LinkedWDigraph G)
　　{Gnode *p;
  　　　 int j,w,top=0;
  　　　 int Stack,ve,*indegree;
  　　　 ve=(int )mallloc(G.n+1)*sizeof(int));
  　　　 indegree=(int*)malloc((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*/
　　　　　return(5);
　　　　}　　　　　　　/*Toplogical*/