阅读下列C++程序和程序说明，将应填入（n)处的字句写在对应栏内。

【说明】

本程序在3×3方格中填入1～N(N≥10)内的某9个互不相同的整数，使所有相邻两个方格内的两个整数之和为质数。试求出满足这个要求的所有填法。3×3方格中的每个方格按行按列(先行后列)序号排列为：0，1，2，3，4，5，6，7，8。

程序采用试探法，即从序号为0的方格开始，为当前方格寻找一个合理的可填整数，并在当前位置正确填入后，为下一方格寻找可填入的合理整数。如不能为当前方格找到一个合理的可填整数，就要回退到前一方格，调整前一方格的填入整数；直至序号为8的方格也填入合理的整数后，就找到了一个解，将该解输出。再调整序号为8的方格所填整数，继续去找下一个解。为了检查当前方格的填入整数的合理性，程序引入二维数组check Matrix，存放需要进行合理性检查的相邻方格的序号。

include ＜stdio. h＞

define N 12

int b[N+1];

int pos;

int a[9];/* 用于存储诸方格所填入的整数*/

int AllNum=0;/* 统计有多少种填法*/

int checkMatrix[][3]={ {-1},{0,-1},{1,-1},

{0,-1},{1,3,-1},{2,4,-1},

{3,-1},{4,6,-1},{5,7,-1}};

void write(int a[])

{ int i, j;

for(i=0; i＜3; i++)

{ for(j=0; j＜3; j++)

printf("%3d", a[3*i+j]);

printf("\n");

}

}

int isPrime(int m)

{ int i;

if(m==2)return 1;

if(m==1 ‖ m%2==0)return 0;

for(i=3; i*i＜m;)

{ if(m%i==0)return 0;

i+=2;

}

return 1;

}

int selectNum(int start)

{ int j;

for(j=start; j＜=N; j++)

if(b[j])return j;

return 0;

}

int check()/*检查填入pos位置的整数是否合理*/

{ int i,j;

for(i=0; (j=(1))＞=0; i++)

if(!isPrime(a[pos]+a[j]))

(2);

(3);

}

extend ()/* 为下一方格找一个尚未使用过的整数*/

{ a[(4)]=selectNum(1);

b[a[pos]]=0;

}

void change ()/*为当前方格找下一个尚未使用过的整数(找不到回溯)*/

{ int j;

while(pos ＞=0 && (j=selectNum((5)))==0)

b[a[pos--]]=1;

if(pos＜0)return;

b[a[pos]]=1; a[pos]=j; b[j]=0;

}

int find ()

{ int k=1;

pos=0; a[pos]=1; b[a[pos]]=0;

do{

if(ok)

if(pos==8)

{ write(a);

change();

AllNum++;/* 统计有多少种填法*/

}

else extend();

else change();

k=check();

}while(pos＞=0);

}

void main()

{ int i;

for(i=1; i＜=N; i++) b[i]=1;

find();

prinrf("共有%d种不同填法!/n", AllNum);

}

【说明】 应用Prim算法求解连通网络的最小生成树问题。请阅读程序后填空。

const int MaxInt＝INT MAX； //INT MAX的值在＜limits．h＞中

const int n＝6； //图的顶点数，应由用户定义

typedef int AdjMatrix[n][n]； //用二维数组作为邻接矩阵表示

typedef struct{ //生成树的边结点

int fromVex，to Vex； //边的起点与终点

int weight； //边上的权值

}TreeEdSenode；

typedef TreeEdgeNode MST[n-1]； //最小生成树定义

void PrimMST (AdjMatrix G，MST T，int rt){

//从顶点rt出发构造图G的最小生成树T，rt成为树的根结点

TreeEdgeNode e； int i，k＝0，min，minpos，v；

for(i＝0；i＜n；i++) //初始化最小生成树T

if(i!＝rt){

T[k]．fromVex＝rt；

(1)；

T[k++].weight＝G[rt][i]；

}

for(k＝0；k＜n-1；k++){ //依次求MST的候选边

(2)；

for(i＝k；i＜n-1；i++) 八遍历当前候选边集合

if(T[i].weight＜min) //选具有最小权值的候选边

{min＝T[i]．weight；(3)；}

if(min＝＝MaxInt) //图不连通，出错处理

{cerr＜＜“Graph is disconnected!”＜＜endl； exit(1)；}

e=T[minpos]；T[minpos]＝T[k]；(4)；

v=T[k].to Vex；

for(i＝k+1；i＜n-1；i++) //修改候选边集合

if(G[v][T[i].to Vex]＜T[i].weight){

T[i]．weight＝G[v][T[i].toVex]；

(5)；

}

}

}

【说明】下面是一个用C编写的快速排序算法。为了避免最坏情况，取基准记录pivot时，采用从left、right和mid=[(left+right)/2]中取中间值，并交换到right位置的办法。数组a存放待排序的一组记录，数据类型为T，left和right是待排序子区间的最左端点和最右端点。

void quicksort (int a[], int left, int right) {

int temp;

if (left＜right) {

hat pivot = median3 (a, left, right); //三者取中子程序

int i = left, j = right-1;

for(;;){

while (i ＜j && a[i] ＜ pivot) i++;

while (i ＜j && pivot ＜ a[j]) j--;

if(i＜j){

temp = a[i]; a[j] = a[i]; a[i] = temp;

i++; j--;

}

else break;

}

if (a[i] ＞ pivot)

{temp = a[i]; a[i] = a[right]; a[right] = temp;}

quicksort( (1) ); //递归排序左子区间

quieksort(a,i+1 ,right); //递归排序右子区间

}

}

void median3 (int a[], int left, int right)

{ int mid=(2);

int k = left;

if(a[mid] ＜ a[k])k = mid;

if(a[high] ＜ a[k]) k = high; //选最小记录

int temp = a[k]; a[k] = a[left]; a[left] = temp; //最小者交换到 left

if(a[mid] ＜ a[right])

{temp=a[mid]; a[mid]=a[right]; a[right]=temp;}

}

消去第二个递归调用 quicksort (a,i+1,right)。 采用循环的办法:

void quicksort (int a[], int left, int right) {

int temp; int i,j;

(3) {

int pivot = median3(a, left, right); //三者取中子程序

i = left; j = righi-1;

for (;; ){

while (i＜j && a[i] ＜ pivot)i++;

while (i＜j && pivot ＜a[j]) j--;

if(i ＜j) {

temp = a[i]; a[j]; = a[i]; a[i]=temp;

i++; j--;

}

else break;

}

if(a[i]＞pivot){(4);a[i]=pivot;}

quicksoft ((5)); //递归排序左子区间

left = i+1;

}

}

【说明】本程序从正文文件text.in中读入一篇英文短文，统计该短文中不同单词及出现次数，并按词典编辑顺序将单词及出现次数输出到正文文件word．out中。

程序用一棵有序二叉树存储这些单词及其出现的次数，边读入边建立，然后中序遍历该二叉树，将遍历经过的二叉树上的结点的内容输出。

include ＜stdio.h＞

include ＜malloc.h＞

include ＜ctype.h＞

include ＜string.h＞

define INF "text.in"

define OUTF "wotd.out"

typedef struct treenode{

char *word；

int count；

struct treenode *left，*right；

}BNODE

int getword (FILE *fpt，char *word)

{ char c；

c=fgetc (fpt)；

if ( c＝EOF)

return 0；

while(!(tolower(c)＞='a' && tolower(c)＜='z'))

{ c=fgetc (fpt)；

if ( c==EOF)

return 0；

} /*跳过单词间的所有非字母字符*/

while (tolower (c)＞='a' && tolower (c)＜='z')

{ *word++=c；

c=fgetc (fpt)；

}

*word='\0'；

return 1;

}

void binary_tree(BNODE **t，char *word)

{ BNODE *ptr，*p；int compres；

P=NULL； (1)；

while (ptr) /*寻找插入位置*/

{ compres=strcmp (word， (2) )；/*保存当前比较结果*/

if (!compres)

{ (3)；return；}

else

{ (4)；

ptr=compres＞0? ptr-＞right：ptr-＞left；

}

}

ptr= (BNODE*) malloc (sizeof (BNODE)) ;

ptr-＞left = ptr-＞right = NULL;

ptr-＞word= (char*) malloc (strlen (word) +1) ;

strcpy (ptr-＞word, word);

ptr-＞count - 1;

if (p==NULL)

(5);

else if (compres ＞ 0)

p-＞right = ptr;

else

p-＞left = ptr;

}

void midorder (FILE **fpt, BNODE *t)

{ if (t==NULL)

return;

midorder (fpt, t-＞left);

fprintf (fpt, "%s %d\n", t-＞word, t-＞count)

midorder (fpt, t-＞right);

}

void main()

{ FILE *fpt; char word[40];

BNODE *root=NULL;

if ((fpt=fopen (INF,"r")) ==NULL)

{ printf ("Can't open file %s\n", INF )

return;

}

while (getword (fpt, word) ==1 )

binary_tree (&root, word );

fclose (fpt);

fpt = fopen (OUTF, "w");

if (fpt==NULL)

{ printf ("Can't open file %s\n", OUTF)

return;

}

midorder (fpt, root);

fclose(fpt)；

}

【说明】

以下C++程序的功能是计算三角形、矩形和正方形的面积并输出。程序由4个类组成：类Triangle、Rectangle和Square分别表示三角形、矩形和正方形；抽象类Figure提供了一个纯虚拟函数getArea()，作为计算上述3种图形面积的通用接口。

include＜iostream.b＞

include＜math.h＞

class Figure{

public:

virtual double getArea0=0; //纯虚拟函数

};

class Rectangle: (1) {

protected:

double height;

double width;

public:

Rectangle(){};

Rectangle(double height, double width){

This-＞height=height;

This-＞width=width;

}

double getarea(){

return (2);

}

};

class Square: (3) {

public:

Square(double width){

(4);

}

};

class Triangle: (5) {

double la;

double lb;

double lc;

public:

Triangle(double la, double lb, double lc){

this-＞la=la; this-＞lb; this-＞lc;

}

double getArea(){

double s=(la+lb+lc)/2.0;

return sqrt(s*(s-la)**(s-lb)*(s-lc));

}

};

viod main(){

Figure* figures[3]={

new Triangle(2,3,3), new Rectangle(5,8), new Square(5));

for(int i=0;i＜3;i++){

cout＜＜"figures["＜＜i＜＜"]area="＜＜(figures[i])-＞getarea()＜＜endl;

}

}

【说明】

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

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

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

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[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 1[M]);/*从端点关系表r中得出回路轨迹表*/

void exchange(tdr a[M], int m, int b);

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

void travling(tpd pd[M], int n, float dist, t1 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].p1=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++;

&n

[说明]

下面的程序利用递归算法计算x和y的最大公约数。

[函数2.1]

main ( )

{ int x,y,k,t;

scanf(" % d% d" , &x, &y);

if(x＞y) { t=x;x=y; y=t;}

(1);

while(k! =0){

y=x;

(2);

k=y%x;

}

prinff( "% d" ,x); }

[函数2.2说明]

函数fun(char *str,char *substr的功能是计算子串sugbstr在串str中出现的次数。

[函数2.2]

fun(ehar * str, char * substr)

{ int x,y,z;

(3);

for(x=0;str[ x] ! = '\O';x + + )

for(y=x,z=0;sabstr[z] = =str[y];(4),y+ +)

if((5)= ='\0') {

num + +;

break;

}

return(num);

}

【说明】

以下C++程序的功能是计算三角形、矩形和正方形的面积并输出。程序由4个类组成：类Triangle、Rectangle和Square分别表示三角形、矩形和正方形；抽象类Figure提供了一个纯虚拟函数getArea()，作为计算上述3种图形面积的通用接口。

include＜iostream.b＞

include＜math.h＞

class Figure{

public:

virtual double getArea0=0; //纯虚拟函数

};

class Rectangle: (1) {

protected:

double height;

double width;

public:

Rectangle(){};

Rectangle(double height, double width){

This-＞height=height;

This-＞width=width;

}

double getarea(){

return (2);

}

};

class Square: (3) {

public:

Square(double width){

(4);

}

};

class Triangle: (5) {

double la;

double lb;

double lc;

public:

Triangle(double la, double lb, double lc){

this-＞la=la; this-＞lb; this-＞lc;

}

double getArea(){

double s=(la+lb+lc)/2.0;

return sqrt(s*(s-la)**(s-lb)*(s-lc));

}

};

viod main(){

Figure* figures[3]={

new Triangle(2,3,3), new Rectangle(5,8), new Square(5));

for(int i=0;i＜3;i++){

cout＜＜"figures["＜＜i＜＜"]area="＜＜(figures[i])-＞getarea()＜＜endl;

}

}

【说明】下面的程序先构造Point类，再顺序构造Ball类。由于在类Ball中不能直接存取类Point中的xCoordinate及yCoordinate属性值，Ball中的toString方法调用Point类中的toString方法输出中心点的值。在MovingBall类的toString方法中，super.toString调用父类Ball的toString方法输出类Ball中声明的属性值。

public class Point

{

private double xCoordinate;

private double yCoordinate;

public Point 0 }

public Point(ouble x, double y)

{

xCoordinate = x;

yCoordinate = y;

}

public String toString()

{

return "( + Double.toString(Coordinate)+ ","

+ Double.toString(Coordinate) + ");

}

//other methods

}

public class Ball

{

(1); //中心点

private double radius; //半径

private String colour; ///颜色

public Ball() { }

public Ball(double xValue, double yValue, double r)// 具有中心点及半径的构造方法

{

center=(2);//调用类Point 中的构造方法

radius = r;

}

public Ball(double xValue, double yValue, double r, String c)

// 具有中心点、半径及颜色的构造方法

{

(3)；//调用3个参数的构造方法

colour = c;

}

public String toString()

{

return "A ball with center" + center, toString() + ", radius"

+ Double.toString(radius) + ", colour" + colour;

}

//other methods

}

public class MovingBall. (4)

{

private double speed;

public MovingBall() { }

public MovingBall(double xValue, double yValue, double r, String e, double s)

{

(5);// 调用父类Ball中具有4个参数的构造方法

speed = s;

}

public String toString( )

{ return super, toString( ) + ", speed "+ Double.toString(speed); }

//other methods

}

public class Tester{

public static void main(String args[]){

MovingBall mb = new MovingBall(10,20,40,"green",25);

System.out.println(mb);

}

}

【说明】

C++语言本身不提供对数组下标越界的判断。为了解决这一问题，在程序6中定义了相应的类模板，使得对厂任意类型的二维数组，可以在访问数组元素的同时，对行下标和列下标进行越界判断，并给出相应的提示信息。

include＜iostream.h＞

template ＜class T＞ class Array;

template ＜class T＞ class ArrayBody {

friend (1)

T* tpBody;

int iRows, iColumns, iCurrentRow;

ArrayBody (int iRsz, int iCsz) {

tpBody =(2)

iRows = iRsz; iColumns =iCsz; iCurrentRow =-1;

}

public:

T& operator[] (int j) {

bool row_error, column_error;

row_error=column_error=false;

try{

if (iCurrentRow ＜ 0 || iCurrentRow ＞=iRows)

row_error=true;

if (j ＜ 0 || j ＞=iColumns)

column_error=true;

if ( row_error==true || column_error == true)

(3)

}

catch (char) {

if (row_error==true)

cerr ＜＜ "行下标越界[" ＜＜ iCurrentRow ＜＜ "] ";

if (column_error== true )

cerr ＜＜ "列下标越界[" ＜＜j ＜＜ "]";

cout ＜＜ "\n";

}

return tpBody[iCurrentRow * iColumns +j];

};

～ArrayBody ( ) { delete[] tpBody; }

};

template ＜class T＞ class Array {

ArrayBody＜T＞ tBody;

public:

ArrayBody＜T＞ & operator[] (int i) {

(4)

return tBody;

}

Array (int iRsz, int iCsz) :(5) {}

};

void main()

{ Array＜int＞a1(10，20)；

Array＜double＞a2(3，5)；

int b1；

double b2；

b1=a1[-5][10]； //有越界提示：行下标越界[-5]

b1=a1[10][15]； //有越界提示：行下标越界[10]

b1=a1[1][4]； //没有越界提示

b2=a2[2][6]； //有越界提示：列下标越界[6]

b2=s2[10][20]； //有越界提示：行下标越界[10]列下标越界[20]

b2=a2[1][4]； //没有越界提示

}