首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列C++程序和程序说明,将应填入(n)处的字句写在对应栏内。 【说明】[程序6说明]单源最短路径的分支限界算法。 const int MAXNUM=29999; #include<iostream> #include<vector> #include
阅读下列C++程序和程序说明,将应填入(n)处的字句写在对应栏内。 【说明】[程序6说明]单源最短路径的分支限界算法。 const int MAXNUM=29999; #include<iostream> #include<vector> #include
admin
2009-02-15
78
问题
阅读下列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
软件设计师下午应用技术考试
软考中级
相关试题推荐
在汇编指令中,操作数在某寄存器中的寻址方式称为______寻址。
页式存储系统的逻辑地址是由页号和页内地址两部分组成。假定页面的大小为4K,地址变换过程如下图所示,图中逻辑地址用十进制表示。图中有效地址经过变换后,十进制物理地址a应为(18)。
在软件工程中,不属于软件定义阶段的任务是______。A.制定验收测试计划B.制定集成测试计划C.需求分析D.制定软件项目计划
网络测试不能解决的问题是______。A.连通性B.丢包C.全表扫描D.延迟
在面向对象系统中,对象的属性是()。
软件工程每一个阶段结束前,应该着重对可维护性进行复审。在系统设计阶段的复审期间,应该从(8)出发;评价软件的结构和过程。
设有学生实体Students(学号,姓名,性别,年龄,家庭住址,家庭成员,关系,联系电话),其中“家庭住址”记录了邮编、省、市、街道信息;“家庭成员,关系,联系电话”分别记录了学生亲属的姓名、与学生的关系以及联系电话。学生实体Students中的“
阅读以下说明和流程图,从供选择的答案中选出应填入流程图(n)处的字句写在答题纸的对应栏内。【说明】一个印刷电路板的布线区域可分成n×m个方格,如图3-1(a)所示,现在需要确定电路板中给定的两个方格的中心点之间的最短布线方案。电路只能沿水平或垂直
流程图中文件F的纪录格式设定为见表4形式: 其中的①、②应定义为何种数据项?简述处理2、处理3和处理4作何种处理,若有排序处理则需指明排序的键及序(升序或降序)。
随机试题
患者,男,40岁。因车祸致腰椎椎体骨折,6个月前已行钢板固定手术。患者自述S4~S5节段无感觉,也无运动功能。目前留置导尿,小便可解但不能完全排空,测定膀胱残余尿量为300ml。现可独立坐稳,亦可练习抛接球训练。平卧位下可全范围屈髋,无须辅助,然伸膝不能。
生产、销售不符合标准的医疗器械、医用卫生材料,致人死亡的,属于生产、销售伪劣农药、兽药罪中,一般以十万元为起点的是
关于照明配电箱的安装技术要求,正确的有()。
一般会计人员办理会计工作交接手续时( )负责监交。
个体进行活动的基本动力是()。
λ取何值时,方程组无解?有唯一解或有无穷多解?并在有无穷多解时写出方程组的通解.
排序是计算机程序设计中的一种重要操作,常见的排序方法有插入排序、【】和选择排序等。
有如下类声明:classSAMPLE{intn;public:SAMPLE(inti=0):n(i){}voidsetValue(intn0);};下列关于getValue成员函数的定义中,正确的是()。
WhatisJohndoingnow?
Whathaveyoutodobeforeyougettothedeparturegate?Youhavetopay______.Whatwilltheattendantaskyoutoshowher
最新回复
(
0
)