阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】对有向图进行拓扑排序的方法是: (1)初始时拓扑序列为空: (2)任意选择一个入度为0的顶点,将其放入拓扑序列中,同时从图中删除该顶点以及从该顶点出发的弧; (3)重复(2),

admin2014-11-13  27

问题 阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。
【说明】对有向图进行拓扑排序的方法是:
(1)初始时拓扑序列为空:
(2)任意选择一个入度为0的顶点,将其放入拓扑序列中,同时从图中删除该顶点以及从该顶点出发的弧;
(3)重复(2),直到不存在入度为0的顶点为止(若所有顶点都进入拓扑序列则完成拓扑排序,否则由于有向图中存在回路无法完成拓扑排序)。函数int*TopSoa(LinkedDigraphG)的功能是对有向图G中的顶点进行拓扑排序,返回拓扑序列中的顶点编号序列,若不能完成拓扑排序,则返回空指针。其中,图G中的顶点从1开始依次编号,顶点序列为v1,v2,…,vn,图G采用邻接表示,其数据类型定义如下:
#def ine NAXVNUM 50    /*最大顶点数*/
typedef structArcNode(    /*表节点类型*/
int adjvex;    /*邻接顶点编号*/
struct ArcNode*nextarc;    /*指示下一个邻接顶点*/
}ArcNode:
typedef struct Adj List(    /*头节点类型*/
char vdata;    /*顶点的数据信息*/
ArcNode*firstarc;    /*指向邻接表的第一个表节点*/
}Adj List;
typedef struct LinkedDigraph(    /*图的类型*/
int n;    /*图中顶点个数*/
AdjLiSt Vhead[MAXVNUM];    /*所有顶点的头节点数组*/
}LinkedDigraph;
例如,某有向图G如图15.3所示,其邻接表如图15-4所示。


函数T0pSon中用到了队列结构(Queue的定义省略),实现队列基本操作的函数原型如表15—2所示:

【C代码】
int  *TopSort(LinkedDigraph G)  {
ArcNode*P;    /*临时指针,指示表节点*/
Queue Q;/*临时队列,保存入度为0的顶点编号*/
int k=0;    /*临时变量,用作数组元素的下标*/
int j=0,W=0;    /*临时变量,用作顶点编号*/
int*toporder,*inDegree;
toporder=(int*)malloc((G.n+1)*Si zeof(int));  /*存储拓扑序列中的顶点编号*/
inDegree=(int*)malloc((G.n+1)*sizeof(int));    /*存储图G中各顶点的入度*/
if(!inDegree I I!toporder)return NULL;
(1);    /*构造一个空队列*/
for(j=1;J<=G.n;J++)(    /*初始化*/
toporder[J]=0;    inDegree[j]=0;
}
for(J=1;J<=G.n;J++)    /*求图G中各项点的入度*/
for(P=G.Vhead[j].firstarc;P;P=p一>nextarc)
inDegree[p一>adjvex]+=1;
for(j=1;J<=G.n;j++)    /*将图G中入度为0的顶点保存在队列中*/
i f(0==inDegree[j])EnQueue(&Q,j);
whi le(!IsEmpty(Q))(
(2)  ;    /*队头顶点出队列并用W保存该顶点的编号*/
toporder[k++]=W;
/*将顶点W的所有邻接顶点的入度减1(模拟删除顶点w及从该项点出发的弧的操作)*/
for(p=G.Vhead[w].firstarc;P;P=P一>nextarc)(
(3)一=1;
if(0==(4))EnQueue(&Q,P一>adjvex);
}/*for*/
}/*while*/
free(inDegree);
if(  (5)  )
return NULL;
return topOrder;
}/*TopSort*/
根据以上说明和C代码,填充C代码中的空(1)~(5)。

选项

答案(1)InitQueue(&Q)(2)DeQueue(&Q,&w)(3)inDegree[p.>adjvex] 或其等价形式(4)inDegree[p一>adjvex]或其等价形式(5)k
解析 本题考查数据结构和算法中的拓扑排序算法。在拓扑排序过程中,需要将入度为O的顶点临时临时存储起来。函数中用一个队列暂存入度为0且没有进入拓扑序列的顶点。显然,空(1)处应填入InitQueue(&Q)。根据注释,空(2)处应填入DeQueue(&Q,&w),实现队头元素出队列的处理。题中图采用邻接表存储结构,当指针p指向vi邻接表中的节点时,p一>adjvex表示vi的一个邻接顶点,删除Vi至顶点p一>adjvex的弧的操作实现为顶点p一>adjvex的入度减1,因此,空(3)处应填入inDegree[.p一>adIjvex],当顶点p一>adjvex的入度为0时,需要将其加入队列,因此空(4)处也应填入inDegree[p>adjvex]。空(5)处判断是否所有顶点都加入拓扑序列,算法中变量k用于对加入序列的项点计数,因此,空(5)处应填入“k
转载请注明原文地址:https://jikaoti.com/ti/U7i7FFFM
0

相关试题推荐
最新回复(0)