(说明)用克鲁斯卡尔算法求解给定图的最小生成树。
include ＜stdio. h＞
include ＜stdlib. h＞
define MAXN 30
typedef struct
{ int v1,v2; /*一条边依附的两个顶点*/
int weight; /*边上的权值*/
}EDGE;
typedef struct
{ int Vnum; /*图中的顶点数目*/
E．DGE e[MAXN*(MAXN-1)/2]; /*图中的边*/
}Graph;
typedef struct node{ /*用链表存储同一个连通分量的顶点*/
int v;
struct node *next;
}Alist;
void heapadjust(EDGE data[], int s, int m)
{ /*将元素序列data[s..m]调整为小顶堆, 堆顶元素(最小元素)为data[s]*/
int j;
E．DGE t;
t=data[s]; /*备份元素data[s], 为其找到适当位置后再插入*/
for(j=2*s+1; j＜=m; j=j*2+1){/*沿值较小的子结点向下筛选*/
if(j＜m &&(1)) ++j;
if(!(t. weight＞data[j]. weight)) break;
data[s]=data[j];s=j; /*用s记录待插入元素的位置(下标)*/
}/*for*/
data[s]=t; /*将备份元素插入由s所指出的插入位置*/
}/*heapadjust*/
int creat_graph(Graph *p) /*输入图中的顶点及边, 返回图中边的数目*/
{ int k=0; /*记录图中边的数目*/
int n;
int v1,v2;
int w;
printf("vertex number of the graph:");
scanf("%d", &n); /*输入图中的顶点数目*/
if(n＜1) return 0;
p-＞Vnum=n;
do{ printf("edge(vertex1,vertex2,weight):");
scanf("%d %d %d", &V1, &v2, &w);
if(v1＞=0 && v1＜n && v2＞=0 && v2＜n){
p-＞e[k]. v1=v1; p-＞e[k]. v2=v2; p-＞e[k]. weight=w;
k++;
}/*if*/
}while(!( (2) ));
return k; /*返回图中边的数目*/
}/*creat_graph*/
int kruskal(Graph G, int enumber, int tree[][3])
{ /*用kruskal算法求无向连通图G的最小生成树, 图中边所得数目为enumber, */
/*数组tree[][3]中存放生成树中边的顶点和边上的权值, 函数返回生成树的代价*/
int i, k, m, c=0;
int v1, v2;
A．list *p, *q, *a[MAXN];
for(i=0; i＜
G．Vnum; ++i){ /*将每个连通分量中的顶点存放在一个单链表中*/
a[i]=(Alist*)malloc(sizeof(Alist));
if(!a[i]) {
printf("/n mernory allocation error!");
exit(0);
}/*if*/
a[i]-＞v=i; a[i]-＞next=NULL;
}/*for*/
for(i=enumber-1; i＞=0; --i)/*按照边上的权值建立小顶堆*/
heapadjust( (3) );
k=G. Vnum; /*k用于计算图中的连通分量数目*/
m=enumber-1;
i=0;
do{
v1=G. e[0]. v1; v2=G. e[0]. v2;
p=a[v1];
while(p && p-＞v!=v2){ /*判断当前选择的边的顶点是否在一个连通分量中*/
q=p; p=p-＞next;
}
if(!p){ /*当前边的顶点不在一个连通分量中*/
p=q;
p-＞next=a[G. e[0]. v2];
&nb
[试题]阅读以下说明和C程序，将应填入(n)处的字句写在答题纸的对应栏内。(说明)假设需要将N个任务分配给N个工人同时去完成，每个人都能承担这N个任务，但费用不同。下面的程序用回溯法计算总费用最小的一种工作分配方案，在该方案中，为每个人分配1个不同的任务。程序中，N个任务从0开始依次编号，N个工人也从0开始依次编号，主要的变量说明如下：c[i][j]：将任务i分配给工人j的费用；task[i]：值为0表示任务i未分配，值为j表示任务i分配给工人j；worker[k]：值为0表示工人k未分配任务，值为1表示
[试题]阅读以下说明和C++程序代码，将应填入(n)处的字句写在答题纸的对应栏内。(说明)在下面的C++代码中，类SalesTicket能够完成打印票据正文的功能，类HeadDec- orator与FootDecorator分别能够完成打印票据的台头和脚注的功能。已知该程序运行后的输出结果如下所示，请填补该程序代码中的空缺。这是票据的台头!这是票据正文!这是票据的脚注!---------------这是票据的台头!这是票据的脚注!(C++程序代码)#includeusing namespace std;c
[试题]试题五阅读下列程序说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。(程序5说明)著名的四色定理指出任何平面区域图均可用四种颜色着色，使相邻区域着不同的颜色。本程序对给定的区域图找出所有可能的不超过四种颜色的着色方案。程序中用1~4表示四种颜色。要着色的N个区域用0~N-1编号，区域相邻关系用adj［］［］矩阵表示，矩阵的i行j列的元素为1，表示区域i与区域j相邻；矩阵的i行j列的元素为0，表示区域i与区域j不相邻。数组color［］用来存储着色结果，color［i］的值为区域i所着颜色。
[试题]试题三阅读下列程序说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。(说明)下面的程序功能的功能是以行为单位对字符串按下面的条件进行排序。排序条件为：从字符串中间一分为二，右边部分按字符的ASCⅡ值降序排序，排序后左边部分与右边部分进行交换。如果原字符串长度为奇数，则最中间的字符不参加排序，字符仍放在原位置上例如：位置：0 1 2 3 4 5 6 7源字符串：h g f e a b c d则处理后字符串：d c b a h g f e函数ReadDat()实现从文件in．dat中读取数据(
[试题]试题四阅读下列程序说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。(说明)本程序从若干个原始文件合并成的合并文件中恢复出其中一个或全部原始文件。所有文件均作为二进制文件进行处理。合并文件中先顺序存储各原始文件，然后顺序存储各原始文件的控制信息，即文件名、文件长度和在合并文件中的位置(偏移量 )。其结构为：typedef struct{char fname ［256］/*原始文件名*/long length；/*原始文件长度(字节数)*/long offset；/*原始文件在合并文件中的位
[试题]试题四阅读下列程序说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。(程序4．1说明)"背包问题"的基本描述是：有一个背包，能盛放的物品总重量为S，设有N件物品，其重量分别为w1，w2，．．，wn，希望从N件物品中选择若干件物品，所选物品的重量之和恰能放入该背包，即所选物品的重量之和等于S。如下程序均能求得"背包问题"的一组解，其中程序4．1是"背包问题"的递归解法，而程序4．2是"背包问题"的非递归解法。(程序4．1)#include<stdio．h>#def
[试题]试题五阅读下列程序说明和C代码,将应填入(n)处的字句写在答题纸的对应栏内。(程序5说明)设M叉树采用列表法表示，即每棵子树对应一个列表，列表的结构为：子树根结点的值部分(设为一个字符)和用"()"括起来的各子树的列表(如有子树的话)，各子列表间用"，"分隔。例如下面的三叉树可用列表a(b(c，d)，e，f(g，h，i))表示。本程序输入列表，生成一棵M叉树，并由M叉树输出列表。假定输入无错误。(程序5)#include<stdio.h>#include<stdliB．h
[试题]阅读以下说明和C++代码，将应填入(n)处的字句写在答题纸的对应栏内。说明通常情况下，用户可以对应用系统进行配置，并将配置信息保存在配置文件中。应用系统在启动时首先将配置文件加载到内存中，这些内存配置信息应该有且仅有一份。下面的代码应用了单身模式(Singleton)以保证Configure类只能有一个实例。这样， Configure类的使用者无法定义该类的多个实例，否则会产生编译错误。C．++代码#include＜iostream．h＞class Configure{(1)：C．onfigure
[试题]阅读下列程序说明和C代码，将应填入(n)处的字句写在对应栏内。(程序说明)著名的四色定理指出任何平面区域图均可用4种颜色着色，使相邻区域着不同的颜色。本程序对给定的区域图找出所有可能的不超过4种颜色的着色方案。程序中用1～4表示4种颜色。要着色的N个区域用0～N-1编号，区域相邻关系用adj[][]矩阵表示，矩阵的i行j列的元素为1，表示区域i与区域j相邻：矩阵的i行j列的元素为0，表示区域i与区域j不相邻。数组color[]用来存储着色结果，color[i]的值为区域i所着颜色。(程序)incl
[案例分析题] 阅读下列说明和C++代码，将应填入（n）处的字句写在答题纸的对应栏内。说明：某大型商场内安装了多个简易的纸巾售卖机，自动售出2元钱一包的纸巾，且每次仅售出一包纸巾。纸巾售卖机的状态如图10.35所示。采用状态（State）模式来实现该纸巾售卖机，得到如图10.36所示的类图。其中类State为抽象类，定义了投币、退币、出纸巾等方法接口。类SoldState、SoldOutState、NoQuarterState和HasQuarterState分别对应图10.35中纸巾售卖机的4种状态：售出