大学职业资格刷题搜题APP
下载APP
课程
玩着学单词
题库模板
WORD模板下载
EXCEL模板下载
视频教程
创建题库
登录
创建自己的小题库
搜索
【简答题】
【说明】
本题将有向网(带权有向图)定义为类Adjacency WDigraph。类中的数据成员n表示有向网中的顶点数;a为带权邻接矩阵,用于存储有向网中每一对顶点间弧上的权值;c为二维数组,存储有向网中每一对顶点间的最短路径长度;kay为二维数组,存储最短路径,kay[i][j]=k表示顶点i到达顶点j的最短路径必须经过顶点k。类中的主要成员函数有:
Input():输入有向网的顶点数、各条弧及权值,建立带权领接矩阵a。若顶点i到顶点j有弧,则a[i][j]取弧上的权值,否则a[i][j]的值取NoEdge。
AllPairs();用弗洛伊德(Floyd)算法求有向网中每一对顶点间的最短路径长度。
OutShortestPath (int i, int j:计算顶点i到顶点j的最短路径。
outputPath(int i, int j):输出顶点i到顶点j的最短路径上的顶点。
Floyd算法的基本思想是递推地产生一个矩阵序列C
0
,C
1
,C
2
,…,C
n
,其中C
0
是已知的带权邻接矩阵,a,C
k
(i, j(0≤i,j<)表示从顶点i到顶点j的中间顶点序号不大于k的最短路径长度。如果i到j的路径没有中间顶点,则对于0≤k<n,有C
k
(i,j)=C
0
(i,j)= a[i][j]。递推地产生C
1
,C
2
,…,C
n
的过程就是逐步将可能是最短路径上的顶点作为路径上的中间顶点进行试探,直到为全部路径都找遍了所有可能成为最短路径上的中间顶点,所有的最短路径也就全部求出,算法就此结束。
【C++代码】
#include < iostream. h >
#define NoEdge 10000// 当两个顶点之间没有边相连时,在邻接矩阵中用NoEdge表示
void Make2DArray(int * * &x, int rows, int cols);
class AdjacencyWDigraph
private
int n; //有向网中的顶点数目
int* *a; //存储顶点间弧上的权值
int* *c; //存储计算出的最短路径长度
int* * kay; //存储求出的最短路径
pubic:
int Vertices( )const j return n;
void AllPairs( );
void Input( ); //输入有向网的顶点数、各条弧及权值,建立邻接矩阵a
void OutShortestPath(int i, int j); //计算顶点i到j的最短路径(试卷中未列出)
~ AdjacencyWDigraph ( ); //析构函数(试卷中未列出)
private:
void outputPath(int i, int j);
;void AdjacencyWDigraph: :AllPairs( )
int i,j,k,t1,t2,t3;
for(i=1;i<=n; k++)
for(j=1;j<=n; ++j)
c[i][j]=
(1)
; kay[i][j]=0;
for(k=1;k<=n; k++)
for(i=1;i<=n; i++)
if(i= =k) continue;
t1=c[i][k];
for(j=1;j<=n; j++)
if(j==k||j==i) continue;
t2 =c[k] [j]; t3 =c[i] [j];
if( t1 ! = NoEdge && t2! = NoEdge &&(t3==NoEdge || t1+t2<t3) )
c[i][j]=
(2)
;kay[i][j]=
(3)
;
//for
//for
void AdjacencyWDigraph:: outputPath(int i, int j)
//输出顶点i到j的最短路径上的顶点
if(i==j) return;
if(kay[i] [j]==0)cout<<j <<";
else outputPath(i,
(4)
); outputPath(
(5)
);void Adjacency WDigraph: :lnput( )
int i,j,u,v,w,E;
cout << "输入网中顶点个数:";cin> >n;
cout << "输入网中弧的个数:"; cin> >E;
Make2DArray (a, n+1, n+1);
for(i=1;i<=n; i++)
for(j=1; j<=n; j++) a[i][j]=NoEdge;
for(i=1;i< =n; i++) a[i][i]=0;
Make2DArray(c, n+1, n+1);
Make2DArray(kay, n+1, n+1)
for(i=1;i<=E; i++)
cout<<"输入弧的信息(起点终点权值); "; cin> >u> >v> >w; a[u][v] =w;
void Make2DArray(int * * &x, int rows, int cols)
int i,j;
x=new int* [rows+1];
for(i=0;i<rows+1;i ++ ) x[i]=new int [cols+1];
for(i=1;i<= rows; i ++)
for(j=1;j<=cols; j++) x[i][j]=0;
题目标签:
路径长度
成员函数
最短路径
如何将EXCEL生成题库手机刷题
手机使用
分享
复制链接
新浪微博
分享QQ
微信扫一扫
微信内点击右上角“…”即可分享
反馈
收藏
举报
参考答案:
举一反三
【单选题】若count为类Toy中的静态数据成员,obj为类Toy的一个对象,则在该类的成员函数中访问count时,错误的是( )。
A.
count
B.
obj.count
C.
Toy.count
D.
Toy::count
查看完整题目与答案
【单选题】Dijkstra算法只能求出起点到终点的最短路径,不能得到起点到其它各节点的最短路径。
A.
正确
B.
错误
查看完整题目与答案
【判断题】如果一个类的成员函数是另一个类的友元函数,则称这个成员函数为友元成员。
A.
正确
B.
错误
查看完整题目与答案
【单选题】对于类中的常成员函数f()而言,( )。
A.
f函数中没有this指针
B.
f函数只能被常对象调用
C.
f函数中可以调用非常成员函数
D.
f函数中不能修改其它成员
查看完整题目与答案
【简答题】用4个权值{3,2, 4,1}构造的哈夫曼(Huffman)树的带权路径长度是 。
查看完整题目与答案
【单选题】下面是重载为非成员函数的运算符函数原型,其中错误的是
A.
MyClassoperator*(MyClass);
B.
MyClassoperator+(MyClass,int);
C.
MyClass&operator-=(MyClass&,MyClass);
D.
MyClass&operator=(MyClass&,MyClass);
查看完整题目与答案
【简答题】由权值分别为11,8,6,2,5的叶子结点生成一棵哈夫曼树,它的带权路径长度为( ) 注意:每空只要填入一个数
查看完整题目与答案
【单选题】二叉树的前序、中序和后序遍历法最适合采用__(1)__来实现。查找树中,由根结点到所有其他结点的路径长度的总和称为__(2)__,而使上述路径长度总和达到最小的树称为__(3)__。它一定是__(4)__。在关于树的几个叙述中,只有__(5)__是正确的。空白(5)处应选择()
A.
用指针方式存储有n个结点的二叉树,至少要有n+1个指针
B.
m阶B-树中,每个非叶子结点的后继个数≥
C.
m阶B-树中,具有k个后继的结点,必含有k-1个键值
D.
平衡树一定是丰满树
查看完整题目与答案
【简答题】构建一个类Stock,含字符数组stockcode[]及整型数据成员quan、双精度型数据成员price。构造函数含3个参数:字符数组na[]及q、p。当定义Stock的类对象时,将对象的第1个字符串参数赋给数据成员stockcode,第2和第3个参数分别赋给quan、price。未设置第2和第3个参数时,quan的值为1000,price的值为8.98。成员函数print没有形参,需使用this...
查看完整题目与答案
【简答题】已知类sample 是一个抽象类,其成员函数 display 是无形参、无返回类型的纯虚函数,请完成其声明: class sample{ public: sample(){}; ______ };
查看完整题目与答案
相关题目:
【单选题】若count为类Toy中的静态数据成员,obj为类Toy的一个对象,则在该类的成员函数中访问count时,错误的是( )。
A.
count
B.
obj.count
C.
Toy.count
D.
Toy::count
查看完整题目与答案
【单选题】Dijkstra算法只能求出起点到终点的最短路径,不能得到起点到其它各节点的最短路径。
A.
正确
B.
错误
查看完整题目与答案
【判断题】如果一个类的成员函数是另一个类的友元函数,则称这个成员函数为友元成员。
A.
正确
B.
错误
查看完整题目与答案
【单选题】对于类中的常成员函数f()而言,( )。
A.
f函数中没有this指针
B.
f函数只能被常对象调用
C.
f函数中可以调用非常成员函数
D.
f函数中不能修改其它成员
查看完整题目与答案
【简答题】用4个权值{3,2, 4,1}构造的哈夫曼(Huffman)树的带权路径长度是 。
查看完整题目与答案
【单选题】下面是重载为非成员函数的运算符函数原型,其中错误的是
A.
MyClassoperator*(MyClass);
B.
MyClassoperator+(MyClass,int);
C.
MyClass&operator-=(MyClass&,MyClass);
D.
MyClass&operator=(MyClass&,MyClass);
查看完整题目与答案
【简答题】由权值分别为11,8,6,2,5的叶子结点生成一棵哈夫曼树,它的带权路径长度为( ) 注意:每空只要填入一个数
查看完整题目与答案
【单选题】二叉树的前序、中序和后序遍历法最适合采用__(1)__来实现。查找树中,由根结点到所有其他结点的路径长度的总和称为__(2)__,而使上述路径长度总和达到最小的树称为__(3)__。它一定是__(4)__。在关于树的几个叙述中,只有__(5)__是正确的。空白(5)处应选择()
A.
用指针方式存储有n个结点的二叉树,至少要有n+1个指针
B.
m阶B-树中,每个非叶子结点的后继个数≥
C.
m阶B-树中,具有k个后继的结点,必含有k-1个键值
D.
平衡树一定是丰满树
查看完整题目与答案
【简答题】构建一个类Stock,含字符数组stockcode[]及整型数据成员quan、双精度型数据成员price。构造函数含3个参数:字符数组na[]及q、p。当定义Stock的类对象时,将对象的第1个字符串参数赋给数据成员stockcode,第2和第3个参数分别赋给quan、price。未设置第2和第3个参数时,quan的值为1000,price的值为8.98。成员函数print没有形参,需使用this...
查看完整题目与答案
【简答题】已知类sample 是一个抽象类,其成员函数 display 是无形参、无返回类型的纯虚函数,请完成其声明: class sample{ public: sample(){}; ______ };
查看完整题目与答案
参考解析:
题目纠错 0
发布