}
return0;
}
2、旋转数字（本题100分）
（rotation.cpp）
【题目描述】
编写程序打印n行如下菱形图形（1≤n≤99），图形有n行n列个整数，图形从第1行的中间开始，数字分别是1，2，……n*n-1，n*n，并且顺时针向中间转入，如果1个数据项宽度不足n*n位，用0补足到n*n位。
提醒：
图案中没有数字的地方用空格填满，每行最后一个数字后面没有多余的空格。
【输入】
输入文件rotation.in包含1个整数n。
【输出】
输出文件rotation.out是一个菱形图形，图形从第1行的中间开始，数字分别是n*n，n*n-1，n*n-2，……1，并且顺时针向中间转入。
【输入输出样例1】
例如n=7，输出：
01
2402
232503
22402604
2139412705
203848422806
19374749432907
183646443008
1735453109
16343210
153311
1412
13
【限制】
1≤n≤99
【提示】
m=4
i=15;.
printf（"%0*d",m,i）; //这里用*表示系数待定，m即为指定的宽度
//上面语句输出“0015”，数据宽度为4，不足4位，前补0
printf（"%*c",m,‘‘）; //左边语句输出“”，即输出4个空格
#include"stdio.h"
constintN0=2*100-1+10;
inta[N0][N0]={0};
structnode
{introw,col;
}dir[4]={{1,1},{1,-1},{-1,-1},{-1,1}};
intmain（）
{
inti,j,n;
introw,col,row1,col1,d,m=0;
freopen（"rotation.in","r",stdin）;
freopen（"rotation.out","w",stdout）;
scanf（"%d",&n）;
row=1;
col=n;
d=0;
intt=n*n;
while（t!
=0）
{m++;
t/=10;
}
for（i=1;i<=n*n;i++）
{a[row][col]=i;
row1=row+dir[d].row;
col1=col+dir[d].col;
if（row1<1||col1<1||row1>2*n-1||col1>2*n-1
||a[row1][col1]!
=0）
{d=（d+1）%4;
row1=row+dir[d].row;
col1=col+dir[d].col;
}
row=row1;
col=col1;
}
for（i=1;i<=2*n-1;i++）
{for（j=1;j<=2*n-1;j++）
if（a[i][j]!
=0）
printf（"%0*d",m,a[i][j]）;
else
if（i<=n&&jn&&j<3*n-i）printf（"%*c",m,''）;
printf（"\n"）;
}
return0;
}
3、求和（本题100分）
（total.cpp）
【问题描述】
有1个n×n的矩阵，从左上到右下称为主斜线（倾角135º），从右上到左下称为次斜线（倾角45º），在主斜线上最大，次斜线上最小的元素称为该矩阵的斜线鞍点，求出该矩阵所有斜线鞍点的和。
如5×5的矩阵：
3259810
44121128
676145719
122133563
3536789019
次斜线主斜线
元素7为上面矩阵的一个斜线鞍点,元素10和19也是上面矩阵的斜线鞍点。
【输入】
输入文件total.in第一行是一个整数n（（1≤n≤100）），接下去是n行×n列的矩阵，矩阵的每个元素都是整数。
【输出】
输出文件total.out也只有1个整数，即该矩阵所有斜线鞍点的和（0≤和≤1010）。
【输入输出样例1】
total.in
total.out
5
3259810
44121128
676145719
122133563
3536789019
36
【输入输出样例2】
total.in
total.out
4
121713
1015169
188195
117910
0
#include
#defineNO100
intmain（）
{
freopen（"total.in","r",stdin）;
freopen（"total.out","w",stdout）;
inti,j,x,y,max,min,n=0,sum=0;
scanf（"%d",&n）;
int**a=newint*[n];
i=-1;
while（++i{
a[i]=newint[n];
j=-1;
while（++j}
i=-1;
while（++i{
j=-1;
while（++j{
x=i,y=j;
max=1,min=1;
while（x>0&&y>0）{x--;y--;}
while（x{
if（a[x][y]>a[i][j]）
{
max=0;
break;
}
x++;y++;
}
x=i,y=j;
while（x>0&&ywhile（x=0）
{
if（a[x][y]{
min=0;
break;
}
x++,y--;
}
if（!
max||!
min）continue;
elsesum+=a[i][j];
}
}
printf（"%d\n",sum）;
i=-1;
while（++idelete[]a;
return0;
}
4、多项式相乘
（conv.cpp/c）
【题目描述】
编程实现若干个多项式相乘。
多项式的输入输出格式为：
系数在前，指数在后，各项按指数递增排列，每个多项式输入时以两个0结束。
系数为0的项不输出。
例如：
1+4X3-9X5输入格式为：
1001024304-9500或者1043-9500，其输出只能是：
1043-95
【输入】
输入文件conv.in每行为一个多项式，多项式输入时以两个0结束。
数据为若干行的多项式，例如：
101100
10-1100
101200
表示（1+x）（1-x）（1+x2）
【输出】
输出文件conv.out包含1行,为上述多项式相乘结果。
上例的输出为：
10-14
表示1-x4
【输入输出样例1】
conv.in
conv.out
101100
10-1100
101200
10-14
【数据限制】
所有系数、指数均为整数（int类型）
#include"stdio.h"
typedefstructnode
{
intc,e;
structnode*next;
}ND;
ND*createLink（）
{ND*head,*p;
head=p=newND;
intc,e;
while（true）
{
if（scanf（"%d%d",&c,&e）!
=2）break;
if（c==0&&e==0）break;
p->next=newND;
p=p->next;
p->c=c;
p->e=e;
}
p->next=NULL;
returnhead;
}
voidprintLink（ND*head）
{ND*p=head->next;
while（p）
{
printf（"%d%d",p->c,p->e）;
p=p->next;
}
printf（"\n"）;
}
voidfreeLink（ND*head）
{
ND*p;
while（head）
{p=head;
head=head->next;
deletep;
}
}
ND*addPoly（ND*ha,ND*hb）
{ND*hc,*pc,*pa=ha->next,*pb=hb->next;
hc=pc=newND;
intc,e;
while（pa||pb）
{
if（pa&&（pb==NULL||pa->ee））
{c=pa->c;
e=pa->e;
pa=pa->next;
}
elseif（pb&&（pa==NULL||pb->ee））
{c=pb->c;
e=pb->e;
pb=pb->next;
}
else
{c=pa->c+pb->c;
e=pa->e;
pa=pa->next;
pb=pb->next;
}
if（c）
{pc->next=newND;
pc=pc->next;
pc->c=c;
pc->e=e;
}
}
pc->next=NULL;
returnhc;
}
ND*oneXmulty（ND*pa,ND*hb）
{ND*hc,*pc,*pb=hb->next;
hc=pc=newND;
while（pb）
{
pc->next=newND;
pc=pc->next;
pc->c=pa->c*pb->c;
pc->e=pa->e+pb->e;
pb=pb->next;
}
pc->next=NULL;
returnhc;
}
ND*multyXmulty（ND*ha,ND*hb）
{ND*hc,*ht,*pa=ha->next;
hc=newND;
hc->next=NULL;
while（pa）
{
ht=oneXmulty（pa,hb）;
hc=addPoly（hc,ht）;
freeLink（ht）;
pa=pa->next;
}
returnhc;
}
intmain（）
{ND*ha,*hc;
freopen（"conv.in","r",stdin）;
//freopen（"conv.out","w",stdout）;
hc=createLink（）;
while（true）
{
ha=createLink（）;
if（ha->next==NULL）break;
hc=multyXmulty（hc,ha）;
freeLink（ha）;
}
printLink（hc）;
freeLink（hc）;
return0;
}
5、二叉树
（bTree.cpp/c）
【题目描述】
已知二叉树的先序遍历序列和中序遍历序列，输出其后序遍历序列和层次序遍历序列。
【输入】
输入文件bTree.in有二行，分别是二叉树的先序遍历序列和中序遍历序列。
【输出】
输出文件bTree.out包含二行,分别是上述二叉树的后序遍历序列和层次序遍历序列。
【输入输出样例1】
bTree.in
bTree.out
abdeijfcgh
dijefbghca
jifedhgcba
abdcegifhj
【数据限制】
所有序列字串长度<=100
#include"stdio.h"
#include"string.h"
constintN0=100;
structnode
{chardata;
intlch,rch;
}tree[N0+1];
introot=1;
voidcreateTree（introot,char*pri,char*mid）
{char*p;
intk;
if（root==0||*pri=='\0'||*mid=='\0'）return;
tree[root].data=*pri;
p=strchr（mid,*pri）;
*p='\0';//中序：
mid
（1）p+1
（2）
k=strlen（mid）;//先序：
pri+1
（1）,pri+k+1
（2）
if（k>0）
{tree[root].lch=root+1;
createTree（root+1,pri+1,mid）;
}
if（strlen（p+1）>0）
{tree[root].rch=root+k+1;
createTree（root+k+1,pri+k+1,p+1）;
}
}
voidpostOrder（introot）
{if（root）
{
postOrder（tree[root].lch）;
postOrder（tree[root].rch）;
printf（"%c",tree[root].data）;
}
}
voidlayerOrder（introot）
{intqu[N0+5],f=0,r=0;
intt;
if（root==0）return;
qu[r++]=root;
while（r!
=f）
{t=qu[f++];
printf（"%c",tree[t].data）;
if（tree[t].lch）
qu[r++]=tree[t].lch;
if（tree[t].rch）
qu[r++]=tree[t].rch;
}
}
voidshowTree（introot,inttab,charch）
{if（root==0）return;
inti;
for（i=1;iprintf（""）;
printf（"%c（%c）\n",tree[root].data,ch）;
if（tree[root].lch）
showTree（tree[root].lch,tab+6,'L'）;
if（tree[root].rch）
showTree（tree[root].rch,tab+6,'R'）;
}
inthigh（introot）
{if（root==0）return0;
intlh,rh;
lh=high（tree[root].lch）;
rh=high（tree[root].rch）;
return1+（lh>rh?
lh:
rh）;
}
intleafNumber（introot）
{
if（root==0）return0;
if（tree[root].lch==0&&tree[root].rch==0）
return1;
returnleafNumber（tree[root].lch）+leafNumber（tree[root].rch）;
}
intmain（）
{charpri[N0+1],mid[N0+1];
freopen（"Btree.in","r",stdin）;
//freopen（"Btree.out","w",stdout）;
gets（pri）;
gets（mid）;
createTree（root,pri,mid）;
postOrder（root）;
printf（"\n"）;
layerOrder（root）;
printf（"\n"）;
showTree（root,1,'T'）;
printf（"%d\n",high（root））;
printf（"%d\n",leafNumber（root））;
return0;
}
方法二：
#include
#include
structNode
{
charch;
Node*lch;
Node*rch;
}*root;
charpri[105],mid[105];
Node*buildTree（char*pri,char*mid）
{
char*pos=strchr（mid,*pri）;
if（pos）
{
Node*temp=newNode;
temp->ch=*pos;
temp->lch=temp->rch=NULL;
*pos='\0';
intk=strlen（mid）;
if（*（pri+1））
temp->lch=buildTree（pri+1,mid）;
if（*（pos+1））
temp->rch=buildTree（pri+k+1,1+pos）;
returntemp;
}
returnNULL;
}
voidaftShowTree（Node*root）
{
if（root!
=NULL）
{
aftShowTree（root->lch）;
aftShowTree（root->rch）;
putchar（root->ch）;
}
}
voidlevShowTree（Node*root）
{
Node*arr[105]={0},*p;
inttop=0,tail=0;
arr[++tail]=root;
while（tail!
=top）
{
p=arr[++top];
if（p->lch）
arr[++tail]=p->lch;
if（p->rch）
arr[++tail]=p->rch;
putchar（p->ch）;
}
}
voidfree（Node*root）
{
if（root）
{
if（root->rch）
free（root->rch）;
if（root->lch）
free（root->lch）;
deleteroot;
}
}
intmain（void）
{
gets（pri）;
gets（mid）;
root=buildTree（pri,mid）;
aftShowTree（root）;puts（""）;
levShowTree（root）;puts（""）;
free（root）;
return0;
}
6、二叉树1
（bTree1.cpp/c）
【题目描述】
已知一颗二叉树的先序遍历序列和中序遍历序列，输出该树的高度和该树的叶子数。
【输入】
输入文件bTree1.in有二行，分别是一颗二叉树的先序遍历序列和中序遍历序列。
【输出】
输出文件bTree1.out只有一行，包含两个整数，分别是该树的高度和叶子数，两个整数之间用一个空格隔开。
【输入输出样例1】
bTree1.in
bTree1.out
abdeijfcgh
dijefbghca
63
【数据限制】
1<=所有序列字串长度<=100
#include"stdio.h"
#include"string.h"
structTr
{
charda;
Tr*lchild,*rchild;
};
Tr*Renew（char*bch,char*mch,intlen）
{
Tr*root;
intl;
char*temp;
if（len<=0）
{
root=NULL;
returnNULL;
}
root=newTr;
root->da=*bch;
for（temp=mch;temp
升级会员 