欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

PAT甲级真题 1002 A+B for Polynomials

程序员文章站 2024-03-23 21:10:34
...

一、题目
PAT甲级真题 1002 A+B for Polynomials
PAT甲级真题 1002 A+B for Polynomials
二、思路
多项式加法,数据结构学习链表时的典型应用。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);
}
相关标签: PAT甲级真题