二级C++资料2

1、 求特殊的数

(1). 下列程序的功能是查找四位数的超级素数。超级素数的定义为：若一个素数从低位到高位依次去掉一位数后仍然是素数，则此数为超级素数。例如，数2333是素数，且233、23、2均是素数，所以2333是一个超级素数。

# include # include int prime(int n) { if(n= =1) return 0;

for(int i=2;i<=sqrt(n);i++) if(!(n%i)) return 0; ;

}

void sup_prime(int n, ) { } {

f=1;

while(n>0)

if(prime(n)) ;

else { ; break; }

void main(void)

for(int i=1001;i<10000;i+=2) { }

int f;

sup_prime(i,f);

if(f) cout<}

// return 1 int &f n/=10 f=0

2、 数组处理

(1). 以下程序的功能是：二维数组a中每列元素都是从小到大有序排列的，将一维数组b中的元素依次插入到数组a的每列中，并保持a中每列数据的有序性。

最后将执行插入操作后的数组a以矩阵形式输出。例如， 1原数组a为：483691228 数组b为： {2 7 1} 操作后的数组a为：4108367912 810# include # include

# define ROW 4 # define COL 3

void f(int a[ ][COL],int b[ ]) {

int i,j;

for( ) { for(j=ROW-1;j>0;j- - )

第 1 页 共 21 页

} { }

}

if(a[j-1][i]>b[i]) ;

else break ; ;

void main(void)

int a[ROW][COL]={1,3,2,4,6,8,8,9,10}; int b[COL]={2,7,1};

cout<<\"插入前数组中的数据依次为：\"<<'\\n'; for( int i=0;ifor(int j=0;j}

cout< ;

cout<<\"插入后数组中的数据依次为：\"<<'\\n'; for(i=0;i{ for(int j=0;j// i=0;i(2). 下面程序的功能是：重新安排数组中元素的排列顺序，使得所有的正数放在数组的前面，负数放在数组的后面，假定数组中所有元素的值均不为0。例如，数组a中原有元素的排列为：2 3 -3 -5 6 -1 9 8 7 -7 -6 11，执行以下程序后，数组a中的元素值依次为：2 3 11 7 6 8 9 -1 -5 -7 -6 -3 。

算法提示：首先使p1指向数组的第0个元素，p2指向数组的最后一个元素。

a) 若p1指向的数组元素值为正数，则使p1指向数组中的下一个元素，

直到p1指向的数组元素为负数或p1的值大于p2的值为止。

b) 若p2指向的数组元素值为负数，则使p2指向数组中的前一个元素，直到p2指向的数组元素为正数或p2的值小于p1的值为止

c) 若p1的值小于p2的值，则将p1与p2所指向的数组元素进行交换，

重复算法的第一步和第二步；否则，表明已完成数组中元素的排列，结束算法。

# include void swap(int *p,int n) {

int *p1,*p2; p1=p;

; while(p1while( ) p1++ ; while( ) p2- - ; if(p1{ int t=*p1; *p1=*p2; *p2=t; }

第 2 页 共 21 页

p1++; p2- - ;

} }

void main(void)

{ int a[ ]={2,3,-3,-5,6,-1,9,8,7,-7,-6,11}; }

// p2=p+n-1 p10 p13、 字符串处理

(1). 下面的程序功能是：将一个字符串中的单词分行输出。例如，对字符串：\"What is your name?\"，执行程序后，输出结果为： What is your name?

# include char *nextWord(char **pp) {

static char word[81];

while(**pp= =' ' ) ; char *pw=word;

while(**pp&&**pp!=' ' ) *pw++ = *(*pp)++ ; ;

const int SIZE=sizeof(a)/ ; swap(a,SIZE);

for(int k=0;kreturn ; }

void main(void) {

char s[ ]=\"What is your name?\do {

cout<}

// (*pp)++ *pw='\\0' word &ps

(2). 一个数的各位数字倒过来所得到的新数叫原数的反序数。如果一个数等于它的反序数，则称它为对称数或回文数。求10000~11000之间的二进制对称数。 算法说明：先将正整数n的二进制字符形式放在字符数组s2中，二进制字符形式的反序放在字符数组s1中。然后，比较这两个字符串，若相等，则是二进制对称数。 # include # include int func(int n,char *s1)

第 3 页 共 21 页

{

char ch,s2[33],*p,*q; p=s1; q=s2+32;

*q- - = ; while(n)

{ ch= ; }

*p=0; q++;

if( ) return true; else return false;

n/=2;

*p++ = ch;

*q- - = ch;

}

void main(void) {

char s[33]={0}; int count=0; cout<<\"二进制对称数如下：\\n\";

for(int n=10000;n<11000;n++) { if( ) { cout<<\"n=\"<}

count++;

}

cout<<\"对称数的个数为：\"<}

// '\\0' n%2+'0' strcmp(s1,q)= =0 func(n,s)

4、 链表

(1). 在以下程序中，函数CreateLink( )根据键盘输入的整数建立一条单向无序链表，

链表上的每一个结点包含一个整数；函数SortLink( )通过改变结点在链表中的位置将链表调整为一条有序链表；：函数PrintLink( )将链表上的整数依次输出；函数DeleteLink( )将链表删除。

# include

struct node { int data; node *next; }; node *CreateLink(void) //创建无序链表 { }

node *p1,*p2,*head=0; int a;

cout<<\"产生一条无序链表，请输入数据，以-1结束：\"; cin>>a;

while(a!=-1)

{ p1=new node ; p1->data=a; }

p2->next=0; return (head);

if(head= =0) { head=p1; p2=p1; } else { ; p2=p1; } cout<<\"请输入数据，以-1结束：\"; cin>>a;

第 4 页 共 21 页

void SortLink(node *&head) //通过移动每个结点的指针来完成链表排序 {

node *q,*tq,*p,*tp; int flag=0; if(!head) return;

for(q=head,tq=0; q ; q=q->next )

{ for(tp=q,p=q->next; p ; tp=p,p=p->next )

if(q->data >= p->data )

{ //将p和q指向的两个结点所处位置互换 }

;

p->next=q; q=p; p=tp;

if(!tq) head=q; else tq->next=q; tq=q;

} }

void PrintLink(node *head) //打印链表 {

node *p=head;

cout<<\"链表上各结点的数据为：\\n\";

while( p!=NULL ) { cout<data<<'\'; ; } cout<<\"\\n\";

}

void DeleteLink(node *head) //删除链表

{ node *p1; while(head) { p1=head; head=head->next; ; } }

void main(void) { }

node *head=0;

head=CreateLink( ); PrintLink(head); SortLink(head); PrintLink(head); DeleteLink(head);

// p2->next=p1 tp->next=p->next p=p->next delete p1 (2). 下面程序先建立一条单向链表，其中每一个结点包含产品名称和产品类别。然后对链表中的结点按产品类别进行分类，将同类别产品的结点放在一起。具体实现过程为：依次从已建立的单向链表上取下一个结点，根据该结点的产品类别值插入到新的链表中。插入过程为：若新链表上已有该产品类别的结点，则将结点插入到同类别结点的最后一个结点的后面；否则，将该结点插入到新链表的最后一个结点的后面。最后，输出分类后链表上各个结点的信息。 # include # include

struct node { char product[20]; // 产品名称 };

char category[10]; // 产品类别 node *next;

第 5 页 共 21 页

node *create(void) // 创建链表 {

node temp,*p2=&temp;

char product[20],category[10]; while(1)

{ cout<<\"输入产品名称和类别，当输入产品名称为end时表示结束：\"; }

; return temp.next;

cin>>product>>category;

if(strcmp(product,\"end\")= =0) break;

p2->next=new node; p2=p2->next;

strcpy(p2->product,product); strcpy(p2->category,category);

}

void print(node *h) // 输出链表h {

while(h)

{ cout<product<<'\'<category<next; }

cout<void deletechain(node *h) // 删除链表h {

node *p;

while( ) { h=h->next; delete p; }

}

node *insertascategory(node *h,node *p) // 按类别插入结点 {

node *p2=0,*p1=h;

if(h= =0) { p->next=0; return p; }

while(p1&&strcmp(p1->category,p->category) ) //找同类结点

{ p2=p1; p1=p1->next; }

while(p1&&strcmp(p1->category,p->category)= =0) //定位在同类结点后 { p2=p1; p1=p1->next; }

p->next=p1; ; // 插入在p1、p2结点之间

return h; }

node *classify(node *h) // 按类别分类 { node *h2=0,*p; }

void main(void) { node *h;

h=create( ); print(h); h=classify(h); print(h);

while(h) { p=h; ; h2=insertascategory(h2,p); }

return h2;

deletechain(h); }

// p2->next=0 (p=h)!=0 p2->next=p h=h->next

第 6 页 共 21 页

五、上机改错题

1、 常见语法错误

cin.getline(str); # define M=4 # define N 4;

n<2&&n>MAX num=new; 'a'<=s[i]<='z' array(data[10][10],n); void find(int a[4][ ]); for(int i=0;s[i]!=\"\\0\";i++) if(s[i]=' ') ... for(i=0;n>0;i++,n/=10) s[i]=char(n%10); cin>>n; double a[n]; char s2[ ]; 使用strlen,strcpy等，但未包含string.h 使用sqrt,exp,pow,fabs等，但未包含math.h 使用setw，但未包含iomanip.h 使用exit,abort，但未包含stdlib.h 变量未定义或重复定义 类型匹配错误：

void f(char a,int &n) { ... return a; } 调用 char s[80];int k; cout<(1). 数的处理：判别素数、求反序数、整数位循环移位 // 求反序数

int invert(long x)

{ for(long s=0;x>0;x/=10) s=s*10+x%10; return s; } // 整数位循环移位

int nextnum(int x) // x为正整数，向左循环移一位

{ for(int s=1;x/s>=10;s*=10); return x/s+x%s*10; }

例子：以下程序的功能是：求用1~9这9个数字组成3个三位数(三个数各位数字均互不相同)，要求第一个三位数是第三个三位数的3倍，而第二个三位数是第三个三位数的2倍。找出所有符合要求的3个三位数。该程序正确运行的结果为：

No.1:576,384,192 No.2:657,438,219 No.3:819,546,273 No.4:981,654,327

含错误的源程序如下： # include void f(int t,int *z) {

for(int i=0;i<3;i++) { z++=t%10; t/=10; // *z++=t%10; t/=10; }

}

int ok(int *z,int n) { // 判断z指向的n个数组元素是否都不同且无0

for(int i=0;ifor(int j=i;j第 7 页 共 21 页

return 1;

}

void main( ) { int n,count=0; int a[9];

for(n=123;n<333;n++) { }

f(n,a[0]); // f(n,&a[0]); f(2*n,a[3]); // f(2*n,&a[3]); f(3*n,a[6]); // f(3*n,&a[6]); if(!ok(a,9)) // if ( ok(a,9) )

cout<<\"No.\"<<++count<<\":\"<<3*n<<','<<2*n<<','<}

(2). 一维数组处理：求最大值、数组逆序、排序、循环移位、折半查找、求均值

// 求均值

double average(double x[ ],int n) {

double sum=0; int k=n; while(k- ->0) sum+=x[k]; return sum/n;

}

例子：以下程序的功能是：生成一个数列的前n项（2例如，数列的前10项为：

2 3 6 1 8 8 6 4 2 4 含错误的源程序如下： # include

const int MAX=100;

int sum(int n,int *pa) //生成数列前n项，存入pa所指数组，返回数列前n项之和 {

int k=2,sum1=5,temp; *pa=2;

*(++pa)=3; //目前数列已有前两项 while ( ++ktemp=(*pa-1)*(*pa); // (*(pa-1))*(*pa) if ( temp<10 ) { sum1+=temp; }

else { *(++pa)=temp/10; sum1+=*pa;

第 8 页 共 21 页

*(++pa)=temp;

}

}

if ( kk++;

*(++pa)=temp%10; sum1+=*pa;

} {

return sum1;

void main( )

int n,*num; do {

cout<<\"Input N ( 2>n;

} while ( n<2 && n>MAX ); // n<=2 | | n>=MAX num=new ; // num=new int[n]; cout<<\"sum(\"<delete [ ] num; num=0; }

(3). 二维数组处理：特殊矩阵生成(折叠方阵、魔方阵、螺旋阵)、方阵旋转90º、

找鞍点 // 生成折叠方阵

void create(int a[ ][20] ,int n,int start=1) { int num=start; a[0][0]=num; for(int k=1;k{ }

int i=0,j=k; a[i][j]=++num; while(i0) a[i][--j]=++num;

}

// 生成魔方阵

void magic(int a[ ][20] ,int n) {

int i,j,k,i1,j1;

for(i=0;ia[i][j]=k++;

i1=(i+n-1)%n; j1=(j+1)%n;

if(a[i1][j1]) { i1=(i+1)%n; j1=j; } i=i1; j=j1;

第 9 页 共 21 页

}

}

// 方阵旋转90º

# define N 4

void rotateleft(int a[ ][N]) // 4×4矩阵左转90º {

int i,j; int t[N][N];

for(i=0;ifor(i=0;ia[i][j]=t[i][j];

}

// 找二维数组的鞍点 void find(int a[ ][4],int n) { int i,j,k,maxj,flag=0;

for(i=0;i{ int max=a[i][0]; maxj=0;

for(j=1;j<4;j++) if(a[i][j]>max) { max=a[i][j]; maxj=j; } for(k=0;kif(max>a[k][maxj]) break; if(k>=n)

{ cout<<\"a[\"<例子：一个二维数组的每行元素的逆序变换是指将该二维数组每行元素的次序

1颠倒。例如，二维数组592610371148 经过每行元素逆序变换后的数组为1248123711261015 。 9 下列程序实现了二维数组每行元素的逆序变换。在该程序中，将二维数组

首行地址传递给函数inverse的参数p，其中参数n为所传递的二维数组的列数。

函数print可以打印二维数组，其中二维数组以一维数组的形式传递给指针p,m和n分别表示二维数组的行数和列数。 含有错误的源程序如下： # include void inverse(int *p,int n) {

int *p1=p,*p2=p1+n; // *p2=p1+n-1; while(p1第 10 页 共 21 页

*p1=*p2; *p2=t;

p1++; p2- -; } }

void print(int *p,int m,int n) { }

int *p1=p,*p2=p1+m*n-1; while(p1<=p2) { }

int count; // int count=0; while(count++void main( ) { int a[3][4];

for(int i=0;i<3;i++) for(int j=0;j<4;j++) a[i][j]=i*4+j+1;

for(i=0;i<3;i++) inverse(a,4); // inverse(a[i],4); print(a,3,4); // print(&a[0][0],3,4); }

(4). 字符串处理：找子串(带通配符)、统计数串、找最长单词、找字符、删除字符、 追加字符、字符串加密、数串转换

// 查找子串

int at(char *s1,char *s2) { for(int i=0;s1[i];i++) { for(int j=0;s2[j];j++) { if(!s1[i+j]) break; if(s1[i+j]!=s2[j]) break; }

}

if(!s2[j]) return i ;

return strlen(s1); }

// 统计数串

int select(char a[ ], int b[ ])

{ int i=0,count=0,n=strlen(a);

while(i{ while(!(a[i]>='0'&&a[i]<='9')) { i++; if(i>=n) break; } }

if(i>=n) break;

b[count]=a[i]-'0'; i++;

while(a[i]>='0'&&a[i]<='9') { b[count]=b[count]*10+a[i]-'0'; i++;} count++;

return count;

}

// 找最长单词 # include # include

第 11 页 共 21 页

int longest(char string[ ]) {

int len=0,length=0,flag=1,place=0,point; for(int i=0;i<=strlen(string);i++) if(isalpha(string[i])) if(flag) { point=i; flag=0; len=1;} else len++; else

{

flag=1; if(len>length) { length=len; place=point; len=0; } }

return place;

}

// 找字符、删除字符、追加字符 char *search(char *s,char ch)

{ while(*s) if(*s++= =ch) return s-1; return 0; } void dele(char *s,char ch) {

char *p1=search(s,ch),*p2=p1+1; if(!p1) return; while(*p2) *p1++=*p2++; *p1='\\0';

}

void add(char *s,char ch)

{ while(*s) s++; *s++=ch; *s='\\0'; } // 字符串加密

char *fun(char *str,int *p,int n) // 字符依次反复加上p[0],p[1],...,p[n-1] {

char *p1=str; int *p2=p;

while(*p1)

{ *p1+=*p2++; if(p2= =p+n) p2=p; p1++; }

return str;

}

// 数串转换

void itoa(int n,char *s) // int转换成十进制数串 {

for(int i=0;n!=0;i++) { s[i]='0'+n%10; n=n/10; } s[i]='\\0';

for(int j=0;j例子： 下列程序的功能是：查询一个带通配符\"?\"的字符串sub在另一个字符串str中出现的次数，其中通配符可以代替任何一个字符。例如，字符串\"a?c\"在\"abcdadceascac\"中出现了3次(下划线部分)，\"a?a\"在\"abacadca\"中出现了2次，\"a?\"在\"abaca\"出现了2次。 含有错误的源程序如下： # include

void fun(char *str,char *sub) // int fun(char *str, char *sub) {

int n=0;

while( *str ) { char *p1=str,*p2=sub;

第 12 页 共 21 页

}

while(*p1= =*p2&&*p2= ='?' ) { // while(*p1= =*p2| |*p2= ='?') } str++;

if(*(p2+1)= ='\\0'&&*p1) { n++; continue; // break; }

p1++; p2++;

return n;

}

void main( ) {

}

六、上机编程题

1、 数的处理：判别素数、求反序数、求最大公约数、质因数分解、牛顿迭代求m、

求级数和、梯形法求定积分 //质因数分解

void decomp(int x,int a[ ],int &n) { }

for(int k=0,i=2;i<=x; ) if(x%i= =0) { a[k++]=i; x/=i; } else i++; n=k;

char str[80],sub[10];

cout<<\"请输入被查询的字符：\\n\"; cin.getline(str,79);

cout<<\"请输入要查询的字符：\\n\";

cin.getline(sub,9);

int k=fun(&str,&sub); // int k=fun(str,sub); if(k) cout<<\"出现了\"<//牛顿迭代求m double sqareroot(double m) { if(m<0) return -1; }

242n-6

//求级数和：cosx1xx(1)nx ，直到最后一项值<10。

if(m<1e-10) return 0;

for(double x=m;fabs(x*x-m)>1e-6; ) x=(x+m/x)/2; return x;

2!4!(2n)!double cosine(double x)

{ double c=1,t=1; int n=0;

第 13 页 共 21 页

}

while(fabs(t)>=1e-6 ) { n++; t*= -x*x/((2*n-1)*2*n); c+=t; } return c;

x2//梯形法求定积分：const int n=1000; double f(double x)

x1f(x)dxh(f(x1)f(x2)2n1i1f(x1ih)),hx2x1n

{ return 4*x*x+7*x+12; }

double integral(double x1,double x2) {

double h=(x2-x1)/n,y=(f(x1)+f(x2))/2; for(int i=1;i}

例子：定义一个类Array，求一个二维数组所有元素的平均值(精确到小数点后三位数)，并将该平均值的整数和小数部分分别逆序后输出(如平均值为342.083，则将其整数和小数部分分别逆序后变为243.380)。类Array的具体要求如下： (1) 私有数据成员。 ● int a[3][4]。

● float ave1,ave2：ave1、ave2分别存放数组a中所有元素的平均值及其逆序值。 (2) 公有成员函数

● Array(int t[ ][4],int n)：对私有成员a初始化。

● void average( )：计算ave1的值。

● void invert( )：按题目要求对ave1进行逆序处理，得到ave2。 ● void print( )：输出所有成员数据。

在主函数中对该类进行测试。使用如下二维数组作为测试数据：

112 524

211 362

630 651 710

200 322 54

369 60 程序如下：

# include class Array { int a[3][4]; float ave1,ave2; public: };

void Array::invert( ) {

Array(int t[ ][4],int n) { for(int i=0;i{ ave1=0; for(int i=0;i<3;i++) for(int j=0;j<4;j++) ave1+=a[i][j]; ave1/=12; } void invert( ); void print( );

float t=ave1; if(t<0) t=-t; int k1=t,k2=0; t=t-k1;

while(k1) { k2=k2*10+k1%10; k1/=10; }

第 14 页 共 21 页

k1=t*1000+0.5; ave2=0;

while(k1) { ave2=ave2*10+k1%10; k1/=10; } ave2=k2+ave2/1000; if(ave1<0) ave2=-ave2; }

void Array::print( ) {

for(int i=0;i<3;i++,cout<}

void main( ) {

int a[3][4]={{112,211,630,200},{524,362,651,322},{369,60,710,54}}; Array ob(a,3);

ob.average( ); ob.invert( ); ob.print( );

}

2、 一维数组处理：排序、循环移位、有序插入、求均值、线性变换、升序数组无重复

归并、集合求交、元素关于%封闭测试 //线性变换：a[0],...,a[n-1]作变换b[j]new_min(a[j]min)new_maxnew_minmaxmin

void transform(double a[ ],int n,double b[ ],double new_max,double new_min) { double max,min,t; int i;

for(max=min=a[0],i=1;iif(a[i]>max) max=a[i];

else if(a[i]//升序数组无重复归并

void combine(double a[ ],int n1,double b[ ],int n2,double c[ ],int &m) {

for(int i=0,j=0,k=0;i}

//集合求交

void intersect(double a[ ],int n1,double b[ ],int n2,double c[ ],int &m) {

for(int i=0,k=0;iif(a[i]= =b[j]) { c[k++]=a[i]; break; }

m=k;

}

//元素关于%封闭测试 int closure(int a[ ],int n)

第 15 页 共 21 页

{

for(int i=0;ifor(int j=i+1;j{ int m1=a[i]%a[j],m2=a[j]%a[i],count=0; for(int k=0;k}

if(count<2) return 0;

if(a[k]= =m2) count++;

return 1;

}

例子：试定义一个类LARRAY，将一维数组a中的数据线性变换成指定的数值范围内的数据，并存放到一维数组b中。假设一维数组a中元素的最大值为max，最小值为min。当指定b中数据的取值范围为[new_min,new_max]时，将数组a中的元素a[j]线性变换为数组b中的元素b[j]的变换公式为： b[j]new_min(a[j]min)具体要求如下：

(1) 私有数据成员

● double a[10],b[10]; a存放原始数据，b存放线性变换后的数据。

● double new_max,new_min; 分别为线性变换结果的上、下限。 (2) 公有成员函数

● LARRAY(double a1[ ],double x,double y); 构造函数，用a1初始化数组a;数组b中的元素都初始化为0；用x和y分别初始化new_min和new_max 。 ● double getMax( ); 返回数组a中值最大的元素值。 ● double getMin( ); 返回数组a中值最小的元素值。

● void fun( ); 按给定的变换公式求出数组b的每一个元素值，要求利用函数 getMax( )和getMin( )。

● void print( ); 输出数组b的所有元素。 (3) 在主函数中完成对该类的测试。

输入/输出示例(下划线部分为键盘输入)：

请输入10个数：0 1 2 3 4 5 请输入变换后数据的下限和上限：0 1 变换后的数据为：0

0.8888 1

6

7

8

9

new_maxnew_minmaxmin

0.111111 0.222222 0.333333 0.444444 0.555556

0.666667 0.777778 程序如下：

# include class LARRAY {

double a[10],b[10];

double new_max,new_min;

public: LARRAY(double a1[ ],double x,double y); double getMax( );

第 16 页 共 21 页

double getMin( );

void fun( ); void print( ); };

LARRAY::LARRAY(double a1[ ],double x,double y) {

for(int i=0;i<10;i++) { a[i]=a1[i]; b[i]=0; } new_min=x; new_max=y; } double LARRAY::getMax( )

{ double max=a[0]; for(int i=1;i<10;i++) if(a[i]>max) max=a[i]; return max; } double LARRAY::getMin( )

{ double min=a[0]; for(int i=1;i<10;i++) if(a[i]{ double min=getMin( ),t=(new_max-new_min)/(getMax( )-min); }

for(int j=0;j<10;j++) b[j]=new_min+(a[j]-min)*t;

void LARRAY::print( )

{ cout<<\"变换后的数据为：\"; for(int i=0;i<10;i++) cout<{ double a[10],max,min; cout<<\"请输入10个数：\";

for(int i=0;i<10;i++) cin>>a[i];

cout<<\"请输入变换后数据的下限和上限：\";

cin>>min>>max; LARRAY ob(a,min,max); ob.fun( ); ob.print( ); }

3、 二维数组处理：求最大值、行列扩展、生成特殊矩阵(杨辉三角、乘法表)、对称阵

压缩

//求最大值

double max(double a[ ][20],int m,int n) { double maximun=a[0][0];

for(int i=0;imaximum) maximum=a[i][j]; return maximum;

}

//行列扩展：循环扩展矩阵的4边 void extend(int a[5][5],int x[7][7])

{ for(int i=0;i<7;i++) for(int j=0;j<7;j++)

{ }

int i1=(i-1+5)%5,j1=(j-1+5)%5; x[i][j]=a[i1][j1];

}

//生成特殊矩阵：生成n阶杨辉三角

void yang(int a[20][20],int n)

{ for(int i=0;i<20;i++) for(int j=0;j<20;j++) a[i][j]=0; for(a[0][0]=1,i=1;i<=n;i++)

第 17 页 共 21 页

{ a[i][0]=1;

for(int j=i;j>0;j- -) a[i][j]=a[i-1][j-1]+a[i-1][j]; } }

//对称阵压缩：按行将下三角部分压缩到一维数组中 void compress(double a[ ][20],int n,double b[ ],int &m) {

for(int k=0,i=0;im=k; }

例子：由一个已知二维数组生成另一个二维数组的规则如下：新数组的每一个元素等于原数组对应位置的元素及其上下左右四个元素(共5个元素)的平均值。其中最左(右)一列元素的左(右)邻元素为最右(左)一列的同行元素，最上(下)一行的上(下)邻元素为最下(上)一行的同列元素。例如，由下列数组a生成的矩阵中，第1行第5列的元素为：(5+4+1+25+10)/5=9，第5行第4列的元素为：(24+23+25+19+4)/5=19。 算法要求：先将数组a按如下方式进行扩展(设扩展后的数组为x )：

127121722381318234914192451015202505211611162112227121722223381318233244914192442551015202550161116210

6111621 101520250

即数组x比数组a增加了两行两列，将a复制到x的中心位置，同时将a的第一行(列)的元素复制到x的最后一行(列)，a的最后一行(列)复制到x的第一行(列)，数组x第一行和最后行的其他元素置0。然后通过扩展后的数组按上述规则生成新数组。

试建立一个类ARRAY，实现上述功能。具体要求如下： (1) 私有数据成员

● int a[5][5]; 存放原数组。

● double b[5][5]; 存放由数组a按生成规则生成的数据。 (2) 公有成员函数

● ARRAY(int x[5][5]); 构造函数。用参数x初始化成员a，同时将b的所有元素初始化为0。

● void extend(int x[7][7]); 对数组a进行扩展，扩展的数组存放在参数x中。 ● void process( ); 根据生成规则，由数组a生成数组b。要求先调用函数extend( )对数组a进行扩展，然后利用扩展后的数组生成数组b。 ● void show( ); 输出数组a和b的所有元素。

(3) 在主函数中完成对该类的测试。假设原数组为上述数组a。 输入/输出示例： 原数组为：

16111621271217223813182349141924510152025

第 18 页 共 21 页

生成数组为：

77121717771217178813181914191999141919

程序如下：

# include class ARRAY {

int a[5][5]; double b[5][5]; public:

ARRAY(int x[5][5]) { for(int i=0;i<5;i++) for(int j=0;j<5;j++) a[i][j]=x[i][j]; } void extend(int x[7][7]); void process( ); void show( );

};

void ARRAY::extend(int x[7][7])

{ for(int i=0;i<7;i++) for(int j=0;j<7;j++)

x[i][j]=a[(i-1+5)%5][(j-1+5)%5]; x[0][0]=x[0][6]=x[6][0]=x[6][6]=0;

}

void ARRAY::process( )

{ int (*x)[7]=new int[7][7]; extend(x);

for(int i=1;i<=5;i++) for(int j=1;j<=5;j++) b[i-1][j-1]=(x[i-1][j]+x[i][j]+x[i+1][j]+x[i][j-1]+x[i][j+1])/5.0;

delete [ ]x; }

void ARRAY::show( )

{ int i,j; cout<<\"原数组为：\\n\"; }

void main( )

{ int a[5][5]={{1,2,3,4,5},{6,7,8,9,10},{11,12,13,14,15},

{16,17,18,19,20},{21,22,23,24,25}};

ARRAY ob(a); ob.process( ); ob.show( ); for(i=0;i<5;i++,cout<for(i=0;i<5;i++,cout<}

4、 字符串处理：查找字符、删除字符、数串转换、统计单词数、子串替换

//统计单词数：空格间隔

第 19 页 共 21 页

int numberOfWords(char *s) {

int n=0; while(*s)

{ while(*s= =' ') s++; if(*s= ='\\0') break; }

n++; while(*s&&*s!=' ') s++;

return n; }

//子串替换

char *strsub(char *str,char *sub) { while(*str)

{ }

for(char *p1=str,*p2=sub;*p2&&*p1= =*p2;p1++,p2++); if(*p2= ='\\0') return str; str++;

return 0; }

void exchange(char *str,char *sold,char *snew) {

char *p=new char[strlen(str)+(strlen(str)/strlen(sold)+1)*strlen(snew)+1]; for(char *q=p,*p1=str,*p2=strsub(p1,sold);p2; )

{ while(p1strcpy(q,p1); strcpy(str,p); delete[ ]p;

}

例子：设一个二进制序列中每4位表示一个信息单元，为了检测信息是否正确，在每个信息单元后增加一个奇偶校验位，即如果某信息单元中1的个数为奇数，则增加的奇偶校验位的值为1，否则为0。例如，原二进制序列为

0100 1011 1110 1010 0101 1000

为每个信息单元增加一个奇偶校验位后的二进制序列为(下划线部分为增加的奇偶校验位)

01001 10111 11101 10100 01010 10001 试定义一个类Com实现上述功能，具体要求如下：

(1) 私有数据成员 ● int n： 指针s1指向内存空间的大小，其值由原始信息序列的长度(n1)和要插入的校验位的个数确定，计算公式为：n=n1+n1/4+1 。

● char *s1：指向原始二进制序列。假设原始二进制序列的长度为4的倍数。 (2) 公有成员函数

● Com(char *str)：用二进制序列str初始化s1，并根据str的长度初始化n(考虑插入奇偶校验位后的长度)。

● void fun( )：根据要求在s1中插入奇偶校验位。提示：可以使用一个临时数组或指针。

● void print( )：输出二进制序列。

第 20 页 共 21 页

● ~Com( )：释放动态内存空间。

在主函数中给定二进制序列\"010010111110101001011000\"，利用该序列生成类Com的对象并完成对类Com对象的测试。要求输出原始二进制序列和插入奇偶校验位后的二进制序列。 # include # include class Com

{ int n; char *s1; public:

Com(char *str) { n=strlen(str); n=n+n/4+1; s1=new char[n]; strcpy(s1,str); } void fun( );

void print( ) { cout<~Com( ) { delete[ ]s1; } };

void Com::fun( )

{ char *p=new char[n];

for(char *p1=s1,*p2=p;*p1; )

{ for(int k=0,i=0;i<4;i++,p1++,p2++) if((*p2=*p1)= ='1') k++; *p2++='0'+k%2; }

*p2='\\0'; strcpy(s1,p); delete[ ]p;

}

void main( )

{ char *p=\"010010111110101001011000\"; Com ob(p); ob.print( ); ob.fun( ); ob.print( ); }

第 21 页 共 21 页