阅读以下说明和C++代码,将应填入(n)处的字句写在答题纸的对应栏内。
(说明)
本题将有向网(带权有向图)定义为类AdjacencyWDigraph。类中的数据成员n表示有向网中的顶点数;a为带权邻接矩阵,用于存储有向网中每一对顶点间弧上的权值;c为二维数组,存储有向网中每一对顶点间的最短路径长度;kay为二维数组,存储最短路径,kay[i][j]=k表示顶点i 到达顶点j的最短路径必须经过顶点k。类中的主要成员函数有:
Input():输入有向网的顶点数、各条弧及权值,建立带权领接矩阵a。若顶点i到顶点j有弧,则a[i][j]取弧上的权值,否则a[i][j]的值取NoEdge。
A.llPairs();用弗洛伊德(Floyd)算法求有向网中每一对顶点间的最短路径长度。
OutShortestPath(int i,int j):计算顶点i到顶点j的最短路径。
outputPath(int i,int j):输出顶点i到顶点j的最短路径上的顶点。
F.loyd算法的基本思想是递推地产生一个矩阵序列C0,C1,C2,…,Cn,其中C0是已知的带权邻接矩阵,a,Ck(i,j)(0≤i,j<n)表示从顶点i到顶点j的中间顶点序号不大于k 的最短路径长度。如果i到j的路径没有中间顶点,则对于0≤k<n,有Ck(i,j)=C0(i,j)=a[i][j]。递推地产生C1,C2,…,Cn的过程就是逐步将可能是最短路径上的顶点作为路径上的中间顶点进行试探,直到为全部路径都找遍了所有可能成为最短路径上的中间顶点,所有的最短路径也就全部求出,算法就此结束。
(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 {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::Input()
{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;
}
[试题]试题六阅读以下说明和C++程序,将应填入(n)处的字句写在答题纸的对应栏内。(说明)设计一个类模板Sample用于对一个有序数组采用二分法查找元素下标。(C++程序)#include<iostream.h>#define Max 100∥最多元素个数template<class T>class Sample{T A[Max]:∥存放有序数序int n:∥实际元素个数publicSample(){}∥默认构造函数Sample(T a[],int i);∥初始化构造函数int
[试题]试题八阅读以下说明和C++程序,将应填入(n)处的字句写在答题纸的对应栏内。(说明)设计一个日期类Date包括年、月、日等私有数据成员。要求实现日期的基本运算,如某日期加上天数、某日期减去天数、两日期相差的天数等。在Date类中设计如下重载运算符函数:D.ate operator+(int days):返回某日期加上天数得到的日期。D.ate operator-(int days):返回某日期减去天数得到的日期。int operator-(Date&b):返回两日期相差的天数。(程序)#inclu
[试题]试题七阅读以下说明和C++程序,将应填入(n)处的字句写在答题纸的对应栏内。(说明)以下程序的功能是设计一个栈类stack<T>,并建立一个整数栈。(程序)#include<iostream.h>#include<stdliB.h>const int Max=20;∥栈大小template<class T>class stack{∥栈元素数组T s[Max];∥栈顶下标int top;public:stack(){top=-1;∥栈顶初始化为-1}v
[试题]试题二阅读以下说明和C代码,将应填入(n)处的字句写在答题纸的对应栏内。(说明)函数MultibaseOutput(long n,int B)的功能是:将一个无符号十进制整数n转换成B(2≤B≤16)进制数并输出。该函数先将转换过程中得到的各位数字入栈,转换结束后再把B进制数从栈中输出。有关栈操作的诸函数功能见相应函数中的注释。C代码中的符号常量及栈的类型定义如下:#define MAXSIZE 32typedef struct{int *elem;/*栈的存储区*/int max; /*栈的容量
[试题]试题四阅读以下说明和C代码,将应填入(n)处的字句写在答题纸的对应栏内。(说明)将一正整数序列{K1,K2,…,K9}重新排列成一个新的序列,新序列中,比K1小的数都在K1的前面(左面),比K1大的数都在K1的后面(右面),最后调用writeDat()函数的新序列输出到文件out.dat中。在程序中已给出了10个序列,每个序列有9个正整数,并存入数组a[10][9]中,分别求出这10个新序列。例:序列 {6,8,9,1,2,5,4,7,3}经重排后成为{3,4,5,2,1,6,8,9,7}(函数)
[试题]试题四阅读以下说明和C代码,将应填入 (n) 处的字句写在答题纸的对应栏内。[说明]函数MultibaseOutput(long n, int B)的功能是:将一个无符号十进制整数n转换成B(2≤B≤16)进制数并输出。该函数先将转换过程中得到的各位数字入栈,转换结束后再把B进制数从栈中输出。有关栈操作的诸函数功能见相应函数中的注释。C代码中的符号常量及栈的类型定义如下:#define MAXSIZE 32typedef struct {int *elem; /* 栈的存储区 */int max;
[试题]试题四阅读以下说明和C代码,将应填入(n)处的字句写在答题纸的对应栏内。(说明)该程序的功能是从文件IN.DAT中读取一篇英文文章存入到字符串数组xx中,以行为单位对行中以空格或标点符号为分隔的所有单词进行倒排。最后把已处理的字符串(应不含标点符号)仍按行重新存入字符串数组xx中,最后把结果xx输出到文件OUT6.DAT中。例如:原文:You He MeI am a student.结果:Me He Youstudent a am I原始数据文件存放的格式是:每行的宽度均小于80个字符,含标点符号
[试题]试题四阅读以下说明和C代码,将应填入(n)处的字句写在答题纸的对应栏内。(说明)从文件IN.DAT中读取一篇英文文章存入到字符串数组XX中;请编写程序,其功能是:以行为单位把字符串中所有小写字母o左边的字符串内容移到该串的右边存放,然后把小写字母o删除,余下的字符串内容移到已处理字符串的左边存放。最后把已处理的字符串仍按行重新存入字符串数组XX中,最后调用函数WRITEDAT(),把结果XX输出到文件OUT5.DAT中。例如:原文:You can create an index on any fi
[试题]试题三阅读下列说明和C代码,将应填入(n)处的字句写在答题纸的对应栏内。(说明)本题给出四个函数,它们的功能分别是:1.int push(PNODE *top,int e)是进栈函数,形参top是栈顶指针的指针,形参e是入栈元素。2.int pop(PNODE *top,int *e)是出栈函数,形参top是栈顶指针的指针,形参e作为返回出栈元素使用。3.int enQueue(PNODE *tail,int e)是入队函数,形参tail是队尾指针的指针,形参e是入队元素。4.int deQueu
[试题]阅读以下说明和C++代码,将应填入(n)处的字句写在答题纸的对应栏内。说明通常情况下,用户可以对应用系统进行配置,并将配置信息保存在配置文件中。应用系统在启动时首先将配置文件加载到内存中,这些内存配置信息应该有且仅有一份。下面的代码应用了单身模式(Singleton)以保证Configure类只能有一个实例。这样, Configure类的使用者无法定义该类的多个实例,否则会产生编译错误。C.++代码#include<iostream.h>class Configure{(1):C.onfigure