阅读下列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)；

}

【说明】设某城市有n个车站，并有m条公交线路连接这些车站，设这些公交车都是单向的，这n个车站被顺序编号为0至n-1。本程序，输入该城市的公交线路数、车站个数，以及各公交线路上的各站编号，求得从站0出发乘公交车至站n-1的最少换车次数。

程序利用输入信息构建一张有向图G(用邻接矩阵g表示)，有向图的顶点是车站，若有某条公交线路经i站到达j站，就在顶点i到顶点j之间设置一条权为1的有向边＜i,j＞。如果这样，从站点x至站点y的最少上车次数便对应图G中从点x到点y的最短路径长度。而程序要求的换车次数就是上车次数减1。

include ＜stdio.h＞

define M 20

define N 50

int a[N+1]； /*用于存放一条线路上的各站编号*/

int g[N][N]； /*严存储对应的邻接矩阵*/

int dist[N]； /*严存储站0到各站的最短路径*/

int m, n；

void buildG()

{ int i, j, k, sc, dd

printf(“输入公交线路数，公交站数\n”)；

scanf("%d%d"，&m，＆n)；

for (i=0；i＜n；i++) /*邻接矩阵清0*/

for(j=0；j＜n；j++)

g[i][j]=0；

for(i=0；i＜m；i++)

{ printf("沿第%d条公交线路的各站编号(0＜=编号＜=%d，-1结束)：\n)"，i+1，n-1)；

sc=0； /* 当前线路站计数器*/

while(1)

{ scanf("%d"，&dd)；

if(dd＝-1)break；

if(dd＞=0 && dd＜n) (1)；

}

a[sc]=-1；

for(k=1；a[k]＞=0；k++) /*处理第i+1条公交线路*/

for(j=0；j＜k；j++)

g (2)=1；

}

}

int minLen()

{ int j，k；

for(j=0；j＜n；j++)

dist[j]=g[0][j]；

dist[0]=1；

do{

for(k=-1，j=0；j＜n；j++) /*找下一个最少上车次数的站*/

if(dist[j]＞0 &&(k==-1｜｜dist[j]＜dist[k]))

k=j；

if(k＜0｜｜k＝=n-1)

break；

dist[k]=-dist[k]； /*设置k站已求得上车次数的标记*/

for (j=1；j＜n；j++) /*调整经过k站能到达的其余各站的上车次数*/

if((3)&& (dist[j]＝0｜｜-dist[k]+1＜dist[j]))

dist[j]=(4)；

}while(1)；

j=dist[n-1]；

return (5)；

}

void main()

{ int t；

buildG()；

if((t=minLen())＜0)

printf("无解!\n")；

else

printf(“从0号站到%d站需换车%d次\n”，n-1，t)；

}

[函数2.1说明]

下面程序的功能是计算x和y的最小公倍数。

[函数2.1]

main()

{ int m,n,d,r;

seanf("%d %d",&m,&n);

if(m＜n) {r=m;m=n;n=r;}

(1);

while (d%n! =0) (2);

printf("%d\n",d);

}

[函数2.2说明]

下述程序接收键盘输入，直到句点“.”时结束。输入的字符被原样输出，但连续的空格输入将转换成一个空格。

[函数2.2]

include ＜stdio.h＞

main()

{ char c,preChar='\0';

c = getchar();

while(c! = '.'){

if((3)) putchar(c);

else if(preChar! =' ') putchar(c);

(4);

c=(5);

}

}

【说明】[程序6说明]单源最短路径的分支限界算法。

const int MAXNUM=29999；

include＜iostream＞

include＜vector＞

include＜algorithm＞

include＜functional＞

using namespace std；

template ＜class VertexType,class EdgeType＞

class MinNode { //程序中使用的最小化堆的结点说明

friend class Graph＜VertexType,EdgeType＞

public:

MinNode (int nl, EdgeType length1)

{ VexNum=nl；

length=length1；

}

bool operator＞(const MinNode＜VertexType,EdgeType＞&p)const

{ return (1)＞p.length；

}

private:

int VexNum;

//记录源点序号，序号数组p及distance下标相一致。源点为初始扩展顶点

EdgeType length;

//记录源点到本顶点的当前最短路径的长度，源点到自身的长度为0

}

template＜class VertexType,classEdgeType＞

void Graph＜VertexType,EdgeType＞:: shortestpath(VertexType start) {

int j,k,source;//source 记录源点的序号。

EdgeType*distance=(2)；

int*p=new int[MaxNumVertex];

vector＜MinNode＜VertexType,EdgeType＞ ＞H；

for(source=0；source＜MaxNumVertex;source++)

{ if(NodeList[source]==start)break；}

if (source＞=MaxNumVertex){cout＜＜”This is error!”＜＜end1；return；}

MinNode＜VertexType,Edge Type＞(3)；

for(k=0；k＜MaxNumVertex；k++)

{ distance[k]：MAXXUM； //记录源点到本顶点k的最终的最短路径的长度

p[k]=source； //记录最短路径上的本顶点的直接前驱顶点的序号

}

distance[source]=0；p[source]=-1；//m 是源点，前一顶点不存在

vector＜MinNode＜VertexType, EdgeType＞＞::iterator q；

while(1){

for(j=0；j＜MaxNumVertex；j++)

if((AdjMatrix[E.VexNum* MaxNumVertex+j]＜MAXNUM)

&&((4)＜distance[j]))

{ distance[j]=E.length+AdjMatrix[E.VexNum* MaxNumVertex+j]；

p[j]=E. VexNum； //记录顶点j的前一顶点

MinNode＜VertexType, EdgeType＞(5)；

H．push_ back(N)；

push_heap(H. begin()，H.end()，greater＜MinNode＜VertexType，

EdgeType＞＞())；

}

if(H.empty()＝true)break； //若优先队列为空，那么算法结束

else{

pop_ heap(H.begin()，H. end()，greater＜MinNode＜VertexType，

EdgeType＞＞())；

q=H.end()-1； //从最小化堆中取路径最短的顶点

E=*q；

H.pop_ back()； //删除从最小化堆中“挤”出的顶点

}

} //end while

for(k=0；k＜MaxNumVertex；k++){

cout＜＜"Shorstest path from vertex"＜＜k＜＜"is"＜＜distance[k]＜＜end1；

j=k；cou

[说明]

下面的程序利用递归算法计算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);

}

}