首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下函数说明和C代码,将C程序中(1)~(5)空缺处的语句填写完整。 [说明] 函数int Toplogical (LinkedWDigraph G)的功能是对图G中的顶点进行拓扑排序,并返回关键路径的长度。其中,图G表示一个具有n个顶点
阅读以下函数说明和C代码,将C程序中(1)~(5)空缺处的语句填写完整。 [说明] 函数int Toplogical (LinkedWDigraph G)的功能是对图G中的顶点进行拓扑排序,并返回关键路径的长度。其中,图G表示一个具有n个顶点
admin
2009-02-15
100
问题
阅读以下函数说明和C代码,将C程序中(1)~(5)空缺处的语句填写完整。
[说明]
函数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{ /* 图的类型 */
struct Adjlist head; /* 指向图中第一个顶点的邻接表的头节点 */
} LinkedWDigraph;
例如,某AOE-网如图4-14所示,其邻接表存储结构如图4-15所示。
[函数]
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>O) {
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 */
选项
答案
这是一道要求读者掌握数据结构中拓扑排序和求关键路径问题的算法分析及设计题。本题的解答思路如下。 AOE-网(Activity On Edge network,边表示活动的网)是一个带权的有向无环图,其中顶点表示事件,弧表示活动,权表示活动持续的时间。通常,AOE-网可以用来估算工程的完成时间。 在AOE-网中,入度为0的顶点为源点,出度为0的顶点为汇点。由于有些活动可以并行地执行,因此从源点到汇点的路径中,长度最长的路径称为关键路径(路径长度即指路径上各种活动持续时间之和)。表示事件的顶点存在最早、最晚发生时间。若以顶点V1表示源点、顶点V
n
表示汇点,则汇点的最早发生时间和最晚发生时间是一致的,并且等于关键路径的长度。 设顶点巧的最早发生时间用ve(j)表示,则ve(j)是指从源点V1到Vj的最长路径长度(时间)。这个时间决定了所有从Vj发出的弧所表示的活动能够开工的最早时间。 ve(j)计算方法为: [*] 其中,T是所有到达顶点j的弧的集合;dut(<i,j>)是弧<i,j>上的权值;n是网中的顶点数(即汇点的序号)。 显然,上式是一个从源点开始的递推公式。ve(j)的计算必须在V
j
的所有前驱顶点的最早发生时间全部求出后才能进行。这样必须对AOE-网进行拓扑排序,然后按拓扑有序序列逐个求出各项点事件的最早发生时间。 拓扑排序是将有向无环图中所有顶点排成一个线性序列的过程,并且该序列满足:若在有向图中从顶点V
i
到V
j
有一条路径,则在该线性序列中,顶点V
i
必然在顶点V
j
之前。可见,拓扑排序序列是由有向图中的所有顶点构成的一个线性序列,在这个序列中体现了所有顶点之间的优先关系。 对AOE-网进行拓扑排序的步骤如下: 1) 首先在-AOE网中选择—个入度为0(没有前驱)的顶点且输出它。 2) 然后从网中删除该顶点,并且删除以该顶点为始点的所有引出边。 3) 重复上述两个步骤,直至网中不存在入度为0的顶点为止。 在拓扑排序过程中,有可能同时存在多个入度为0的顶点,函数中用顺序栈Stack[]暂存入度为0且没有进入拓扑序列的顶点。 本试题所给出的算法首先申请了3块连续的地址空间,分别用来存放关键路径长度、网中各顶点的入度及入度为0的顶点编号,它们的首地址分别存放在指针变量Ve、indegree、Stack中。 算法主体是由3个for循环和3个while循环组成。第1个for循环,即for(j=1;j<=G.n;j++) {ve[j]=0; indegree[j]=0;},主要完成数组初始化的功能。 进行拓扑排序之前,应先求出网中每个顶点的入度并存入数组indegree[]中,从而将“从网中删除该顶点及其与该顶点有关的所有边”的操作转换为“相关顶点的入度减1”,一旦发现某个顶点的入度变为0,就将其编号压入堆栈。从而将选择入度为0的顶点转化为从Stack中弹出栈顶元素所代表的顶点。 题目中顶点从1开始编号,顶点Vi的编号为i,第2个for循环代码主要完成求网中各个顶点的入度的功能。 For(j=1; j<=G.n; j++) { /* 求网中各顶点的入度 */ p=G.head[j].Firstadj; while(p) { (1); p=p—>nexcarc; } /* while */ } /* for */ 在有向图中,若以V2为尾的弧有<V2,V4>且权值为30,<V2,V6>且权值为50,则其的邻接表表示形式是:V2→4,30→6,50^。 因此,扫描顶点V2的邻接表可以将邻接于V2的所有顶点的入度加1,即(1)空缺处应填入“indegree[p->adjvex]++”或其等价形式。 第3个for循环语句主要完成求网中入度为0的顶点并保存其编号的功能。以下代码实现拓扑排序并求解各个顶点时事件的最早发生时间。 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 */ 由于入度为0的顶点由栈中弹出,根据变量w在后续代码中所起的作用—存放网中没有直接前驱的顶点,并通过printf语句输出,可知(2)空缺处应填入“Stack[top--]”或其等价形式。 然后,在网中删除没有直接前驱的顶点和以该顶点为始点的所有引出边,并通过内嵌的while循环语句把这些引出边对应的终点的入度减1,即将邻接到顶点w的各个顶点(p->adjvex)的入度减1,再判断它们是否也是入度为0的顶点。因此(3)空缺处应填入“indegree[p->adjvex]--”或其等价形式。 同时,对于顶点p->adjvex而言,当删除其所有引入边之后,从源点出发到达它的最长路径长度也就计算出来了,所以每删除一条到达顶点p->adjvex的引入边,都要查看一下最长路径长度是否需要更新。因此,(4)空缺处填入“ve[w]+p->weight>ve[p->adjvex]”或其等价形式。 算法程序的最后部分,通过return语句返回该图的关键路径长度,即汇点的最早发生时间(该AOE-网的关键路径长度)。由于AOE-网中汇点未必是编号最大的顶点,但它必然是从栈中弹出的最后一个顶点,因此(5)空缺处填入“ve[w]”或其等价形式。
解析
转载请注明原文地址:https://kaotiyun.com/show/tEjZ777K
本试题收录于:
程序员下午应用技术考试题库软考初级分类
0
程序员下午应用技术考试
软考初级
相关试题推荐
Windows“回收站”中的内容只能是()。
Word“格式”菜单下的字体命令不可以设置(47)。
某商场的部门和商品两个实体之间的关系如下图所示。假设每个部门负责销售若干种商品,每种商品只能由一个部门负责销售,那么部门和商品之间存在着(14)的联系。
某地区去年粮食产量资料如下表:根据该表可以推算出,该地区去年薯类的产量为()万吨。
小王在Excel中录入某企业各部门的生产经营数据,录入完成后发现报表略超一页,为在一页中完整打印,以下______做法正确。
抽样调查是收集数据的重要方法之一。抽样调查所遵循的原则不包括______。
假设100个数据的平均值为82.31,其中有10个数据又发生了如下增减变化:+3.52,+2.87,-4.13,+5.34,-2.87,+2.50,-3.52,+4.23,-5.04,+0.10,则新的平均值变为(26)。
在统计学中,用来衡量一个样本中各个数据波动大小的量是______。
为了调查某学校3000名学生的身高,抽取了100名学生进行身高测量,以下叙述中正确的是(23)。
编译程序的作用是将高级程序语言源程序翻译为(4)。
随机试题
甲股份有限公司(以下简称“甲公司”)是一家上市公司,与股权投资有关的资料如下:(1)甲公司与乙公司均为增值税一般纳税人,适用的增值税税率为17%,适用的所得税税率均为25%,所得税均采用资产负债表债务法核算。2×16年1月1日,甲公司以定向增发普
政府及其所属部门滥用行政权力,强制经营者从事法律所禁止的排除或限制市场竞争的行为称为【】
患者,男,56岁。1周前右上腹部绞痛,伴恶心、呕吐,体温37.4℃,予以抗炎治疗后缓解。3天来,出现巩膜黄染,食欲缺乏,收入院。查体:腹软,无压痛,Murphy征(﹣),肝区轻叩痛。B超:胆囊10cm×5cm大小,其内可见多个点状回声,胆总管上段直径1.2
上消化道出血
肉眼血尿反复发作,最常见的肾小球疾病是
在项目目标动态控制的纠偏措施中,调整管理职能分工属于()。
下列行为没有违法的是()。
下列筹资方式中,没有筹资费用,但是财务风险较小,资本成本较高的筹资方式是()。
某案的两名凶手在以下五人中,经过公安部门的侦查后得知:①只有甲是凶手,乙才是凶手②只要丁不是凶手,丙就不是凶手③或乙是凶手,或丙是凶手④丁没有戊为帮凶,就不会作案⑤戊没有作案时间这件案件中的凶手是:
我国现场检查的原则是()。
最新回复
(
0
)