2. 计算机
  3. 阅读下列C++程序和程序说明，将应填入(n)处的字句写在对应栏内。 【说明】[程序6说明]单源最短路径的分支限界算法。 const int MAXNUM=29999； #include＜iostream＞ #include＜vector＞ #include

阅读下列C++程序和程序说明，将应填入(n)处的字句写在对应栏内。 【说明】[程序6说明]单源最短路径的分支限界算法。 const int MAXNUM=29999； #include＜iostream＞ #include＜vector＞ #include

admin2009-02-15  65
问题 阅读下列C++程序和程序说明，将应填入(n)处的字句写在对应栏内。
【说明】[程序6说明]单源最短路径的分支限界算法。
const int MAXNUM=29999；
#include＜iostream＞
#include＜vector＞
#include＜algorithm＞
#include＜functional＞
using namespace std；
template ＜class VertexType,class EdgeType＞
class MinNode {       //程序中使用的最小化堆的结点说明
friend class Graph＜VertexType,EdgeType＞
public:
MinNode (int nl, EdgeType length1)
{   VexNum=nl；
length=length1；
}
bool operator＞(const MinNode＜VertexType,EdgeType＞&p)const
{   return  (1)＞p.length；
}
private:
       int VexNum;
        //记录源点序号，序号数组p及distance下标相一致。源点为初始扩展顶点
       EdgeType length;
                //记录源点到本顶点的当前最短路径的长度，源点到自身的长度为0
}
template＜class VertexType,classEdgeType＞
void Graph＜VertexType,EdgeType＞:: shortestpath(VertexType start) {
       int j,k,source;//source  记录源点的序号。
       EdgeType*distance=(2)；
       int*p=new int[MaxNumVertex];
       vector＜MinNode＜VertexType,EdgeType＞ ＞H；
       for(source=0；source＜MaxNumVertex;source++)
       {   if(NodeList[source]==start)break；}
       if   (source＞=MaxNumVertex){cout＜＜”This is error!”＜＜end1；return；}
       MinNode＜VertexType,Edge Type＞(3)；
       for(k=0；k＜MaxNumVertex；k++)
       {    distance[k]：MAXXUM；      //记录源点到本顶点k的最终的最短路径的长度
            p[k]=source；              //记录最短路径上的本顶点的直接前驱顶点的序号
       }
       distance[source]=0；p[source]=-1；//m 是源点，前一顶点不存在
       vector＜MinNode＜VertexType, EdgeType＞＞::iterator q；
       while(1){
           for(j=0；j＜MaxNumVertex；j++)
         if((AdjMatrix[E.VexNum* MaxNumVertex+j]＜MAXNUM)
                 &&((4)＜distance[j]))
                 {    distance[j]=E.length+AdjMatrix[E.VexNum* MaxNumVertex+j]；
                      p[j]=E. VexNum；       //记录顶点j的前一顶点
                      MinNode＜VertexType, EdgeType＞(5)；
                      H．push_ back(N)；
                      push_heap(H. begin()，H.end()，greater＜MinNode＜VertexType，
                                                                      EdgeType＞＞())；
                 }
         if(H.empty()＝true)break；        //若优先队列为空，那么算法结束
         else{
                      pop_ heap(H.begin()，H. end()，greater＜MinNode＜VertexType，
                                                                      EdgeType＞＞())；
                      q=H.end()-1； //从最小化堆中取路径最短的顶点
                      E=*q；
                      H.pop_ back()；  //删除从最小化堆中“挤”出的顶点
              }
         }  //end while
         for(k=0；k＜MaxNumVertex；k++){
              cout＜＜"Shorstest path from vertex"＜＜k＜＜"is"＜＜distance[k]＜＜end1；
              j=k；cout＜＜"All vertices are："；
              while(j!=source){cout＜＜j＜＜"-＞"；j=p[j]；}
              cout＜＜source＜＜”.”＜＜end1；
         }    //打印顶点的最短路径长度和至源点的最短路径上经过的顶点序列
         return；
}
选项
答案(1)this-＞length或(*this).length (2)new EdgeType[MaxNumVertex] (3)E(source，0) (4)E.length+ AdjMatrix [E. VcxNum* MaxNumVertex+j] (5)N(j，distance[j])
解析 (1)this-＞length或(*this).length
   操作符，的成员函数，比较两个对象的最短路径的长度length，大于则返回真(1)。
(2)new EdgeType[MaxNumVertex]
   动态申请EdgeType类的对象数组distance，长度为MaxNumVertex，存放最短路径的长度。
(3)E(source，0)
   定义最小化堆模板类MinNode＜VertexType, EdgeType＞的对象E(source，0)。
(4)E.length+ AdjMatrix [E. VcxNum* MaxNumVertex+j]
   若E.length+ AdjMatrix [E.VexNum*MaxNumVertex+j]小于distance[j]，则distance[j]取这个更小值。
(5)N(j，distance[j])
   定义最小化堆模板类MinNode＜VertexType，EdgeType＞的对象N(j，distance[j])。
转载请注明原文地址:https://kaotiyun.com/show/GgDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

软件设计师下午应用技术考试

软考中级

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