阅读下列函数说明和C代码, [说明] 所谓货郎担问题,是指给定一个无向图,并已知各边的权,在这样

Question

阅读下列函数说明和C代码，

[说明]

所谓货郎担问题，是指给定一个无向图，并已知各边的权，在这样的图中，要找一个闭合回路，使回路经过图中的每一个点，而且回路各边的权之和最小。

应用贪婪法求解该问题，程序先计算由各点构成的所有边的长度(作为边的权值)，按长度大小对各边进行排序后，按贪婪准则从排序后的各边中选择组成回路的边，贪婪准则使得边的选择按各边长度从小到大选择。

函数中使用的预定义符号如下：

define M 100

typedef struct{/*x为两端点p1、p2之间的距离，p1、p2所组成边的长度*/

float x；

int p1，p2；

}tdr；

typedef struct{/*p1、p2为和端点相联系的两个端点，n为端点的度*/

int n，p1，p2；

}tr；

typedef struct{/*给出两点坐标*/

float x，y；

}tpd；

typedef int tl[M]；

int n=10；

[函数]

float distance(tpd a，tpd b)；/*计算端点a、b之间的距离*/

void sortArr(tdr a[M]，int m)；

/*将已经计算好的距离关系表按距离大小从小到大排序形成排序表，m为边的条数*/

int isCircuit(tr r[M]，int i，int j)；

/*判断边(i，j)选入端点关系表r[M]后，是否形成回路，若形成回路返回0*/

void selected(tr r[M]，int i，int j)；/*边(i，j)选入端点关系表r*/

void course(tr r [M]，tl l[M])；/*从端点关系表r中得出回路轨迹表*/

void exchange(tdr a[M]，int m，int b)；

/*调整表排序表，b表示是否可调，即是否有长度相同的边存在*/

void travling(tpd pd [M]，int n，float dist，tl locus[M])

/*dist记录总路程*/

{

tdr dr[M]；/*距离关系表*/

tr r[M]；/*端点关系表*/

int i，j，k，h，m；/*h表示选入端点关系表中的边数*/

int b；/*标识是否有长度相等的边*/

k=0；

/*计算距离关系表中各边的长度*/

for(i=1；i＜n； i++){

for(j=i+1；J＜=n；j++){

k++;

dr[k]．x=(1);

dr[k]．pl=i;

dr[k]．p2=j;

}

}

m=k；

sortArr(dr，m)；/*按距离大小从小到大排序形成排序表*/

do{

b=1;

dist=0；

k=h=0：

do{

k++；

i=dr[k]．p1；

j=dr[k]．p2；

if((r(i]．n＜=1)&&(r[j]．n＜=1)){/*度数不能大于2*/

if (2) {

/*若边(i，j)加入r后形成回路，则不能加入*/

(3);

h++；

dist+=dr[k]．x；

}else if (4) {

/*最后一边选入r成回路，则该边必须加入且得到解*/

selected(r，i，j)；

h++：

dist+=dr[k]．x;

}

}

}while((k !=n) && (h !=n))；

if(h==n){/*最后一边选入构成回路，完成输出结果*/

course(r，locus)；

}else(/*找不到解，调整dr，交换表中边长相同的边在表中的顺序，并将b置0*/

(5);

}

}while(!b);

}

(1)

Answer 1

正确答案：distance(pd[i]pd[j])
distance(pd[i]，pd[j]) 解析：是计算各边的长度，根据函数的声明及说明，可得应填distance(pd[i],pd[j])。