PAT甲级真题 1002 A+B for Polynomials
程序员文章站
2024-03-23 21:10:34
...
一、题目
二、思路
多项式加法,数据结构学习链表时的典型应用。emm不过忘得差不多了,自己用数组写了一遍。
三、代码
#include <stdio.h>
int main() {
//ak、bk、ck存储项数,ae、be、ce存储指数
int ak, bk, tmp, ae[10] = { 0 }, be[10] = { 0 }, ce[20] = { 0 },sgn = 0, ck = 0, i = 0;
float ac[1001] = { 0.0 }, bc[1001] = { 0.0 };//存储指数对应的系数
//读取多项式A
scanf("%d", &ak);
for (i = 0; i < ak; i++) {
scanf("%d",&tmp);
ae[i] = tmp;
scanf("%f", &ac[tmp]);
}
//读取多项式B
scanf("%d", &bk);
for (i = 0; i < bk; i++) {
scanf("%d", &tmp);
be[i] = tmp;
scanf("%f", &bc[tmp]);
}
//双层循环做加法,利用ac数组存储a+b的和c的系数
i = 0;//i作为指向数组a的指针,标志当前加法进行到了哪一项
while(i<ak){
if (ae[i] < be[sgn]) {//当多项式b的当前项指数大于a的时,说明a中没有这一指数级的项
ce[ck] = be[sgn];
ac[ce[ck]] = bc[ce[ck]];
sgn++; //sgn作为指向数组b的指针,标志当前加法进行到了哪一项
}
else if (ae[i] == be[sgn]) {//a和b的当前项指数相同
ce[ck] = ae[i];
ac[ce[ck]]+= bc[ae[i]];
if (ac[ce[ck]] == 0)//当两项相加系数为0时,不需要记录该项
ck--;
sgn++; i++;
}
else {//a的当前项指数大于b的当前项
ce[ck] = ae[i];
i++;
}
ck++;
if (sgn >= bk)//判断多项式b是否加完了
break;
}
if (sgn >= bk) {//说明多项式a可能还剩几项未加入
for (int j = i; j < ak; j++) {
ce[ck] = ae[j];
ck++;
}
}
else {//说明多项式b可能还剩几项未加入
for (int j = sgn; j < bk; j++) {
ce[ck] = be[j];
ac[ce[ck]] = bc[ce[ck]];
ck++;
}
}
//输出结果c
printf("%d", ck);
for (i = 0; i < ck; i++) {
printf(" %d %.1f", ce[i], ac[ce[i]]);
}
return 0;
}
四、循环链表做法
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
//结点结构体
typedef struct pnode{
float coef;
int exp;
struct pnode *next;
}polynode;
polynode* Creat(int k){
float coef;
int exp,i;
polynode *head,*s,*r;
head=(polynode*)malloc(sizeof(polynode));
head->coef=0;head->exp=-1;r=head;
for(i=0;i<k;i++){
scanf("%d %f",&exp,&cof);
s=(polynode*)malloc(sizeof(polynode));
s->coef=coef;s->exp=exp;r->next=s;r=s;
}
r->next=head;//尾插法建立循环链表
return head;
}
polynode* polyadd(polynode *pa,polynode *pb){
polynode *p,*q,*r,*s;//p、q指示a、b当先需做加法的项结点,s指示p的前驱,r指示q的后继
float x;
p=pa->next;q=pn->next;
s=pa;
while((p!=pa)&&(q!=pb)){
if(p->exp > q->exp){
s=p;p=p->next;
}
else if(p->exp < q->exp){
r=q->next;q->next=p;
s->next=q;s=q;q=r;
}
else{
x=p->coef+q->coef;
if(x!=0){
p->coef=x;
s=p;
}
else{
s->next=p->next;
free(p);
}
p=s->next;
r=q;q=q->next;
free(r);
}
}
if(q!=pb){
r=q;
while(r->next!=pb)
r=r->next;
s->next=q;
r->next=pa;
}
return pa;
}
void Output(polynode *head){
polynode *p;int k=0;
p=head->next;
while(p!=head){
k++;
p=p->next;
}
printf("%d ",&k);
p=head->next;
while(p!=head){
printf("%d %.1f",p->exp,p->coef);
p=p->next;
}
printf("\n");
}
int main(){
polynode *ha,*hb;
int a,b;
scanf("%d",&a);
ha=Creat(a);
scanf("%d",&b);
hb=Creat(b);
ha=PolyAdd(ha,hb);
Output(ha);
}
上一篇: ASP.NET 常用面试题(持续更新)
下一篇: kafka相关面试题及答案
推荐阅读
-
PAT甲级真题 1001 A+B Format
-
PAT甲级真题 1002 A+B for Polynomials
-
【PAT】A1002 A+B for Polynomials
-
PAT 甲级真题 1006 Sign In and Sign Out (25分) python实现
-
【PAT甲级】【1002】 A+B for Polynomials (25分)
-
PAT甲级——1002. A+B for Polynomials (25)(C++)
-
1002. A+B for Polynomials(25)—PAT 甲级
-
PTA甲级考试真题练习9——1009 Product of Polynomials
-
【PAT】A1002 A+B for Polynomials
-
PAT 甲级真题 1006 Sign In and Sign Out (25分) python实现