mooc浙大数据结构PTA习题之一元多项式的乘法与加法运算

本文主要是介绍mooc浙大数据结构PTA习题之一元多项式的乘法与加法运算，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

设计函数分别求两个一元多项式的乘积与和。

输入格式:
输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。

输出格式:
输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。

输入样例:
4 3 4 -5 2  6 1  -2 0
3 5 20  -7 4  3 1
输出样例:
15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1
5 20 -4 4 -5 2 9 1 -2 0

struct node{
	int coef; //系数
	int expn; //指数
	node* next;
};

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct node{
	int coef; //系数
	int expn; //指数
	node* next;
};
node* creat_list(int n){ //读入链表
	node  *head, *r;
	head = new node;
	r = head; 
	int coef , expn;
	while(n--){
		scanf("%d%d",&coef,&expn);
		node* tmp = new node; //创建临时结点
		tmp->coef = coef;
		tmp->expn = expn;
		r->next = tmp; //临时结点接到链表中
		r = tmp;
	}
	r->next = NULL; //结尾设为 NULL
	return head;
}
node* add_list(node* a,node* b){
	node *r,*fans, *ans;
	node *ha,*hb; //为了防止修改指针本身的值，使用代理指针来完成操作，也就是游标。
	fans = new node;
	ans = fans; //ans 作为fans 的”游标“
	ha = a->next;
	hb = b->next;
	while(ha && hb){
		node* tmp = new node; //建立一次即可
		if(ha->expn > hb->expn){ //每次把指数（exponent）较大的加入链表fans
			tmp->coef = ha->coef;
			tmp->expn = ha->expn;
			ans->next = tmp;
			ans = tmp;
			ha = ha->next;
		}
		else if(ha->expn < hb->expn){
			tmp->coef = hb->coef;
			tmp->expn = hb->expn;
			ans->next = tmp;
			ans = tmp;
			hb = hb->next;
		}
		else{
			int mulOfcoef = (ha->coef)+(hb->coef); //如果指数相同， 就把系数求和。
			if(mulOfcoef!=0){
				tmp->coef = mulOfcoef;
				tmp->expn = ha->expn;
				ans->next = tmp;
				ans = tmp;
			}
			ha = ha->next; //注意这里 即使和为0 ，也要移动“游标”
			hb = hb->next;
		}
	}
 
	while(ha){
			node* tmp = new node;
			tmp->coef = ha->coef;
			tmp->expn = ha->expn;
			ans->next = tmp;
			ans = tmp;
			ha = ha->next;
	}
	while(hb){
			node* tmp = new node;
			tmp->coef = hb->coef;
			tmp->expn = hb->expn;
			ans->next = tmp;
			ans = tmp;
			hb = hb->next;
	}
	ans->next = NULL; //结尾设为 NULL
	return fans;
}
node* multi_list(node* a,node* b){
	node* ha, *hb;
	node* ans,*fans;
	ha = a->next;
	hb = b->next;
	fans = creat_list(0);
	if(ha == NULL || hb == NULL){
		return fans;
	}
	node* tmp;
	while(ha != NULL){
		tmp = new node;
		ans = tmp;
		hb = b->next; //每次都是从 b 的第一项开始乘；
		while(hb != NULL){
			node* ltmp = new node;
			ltmp->expn = ha->expn + hb->expn; //指数相加，系数相乘
			ltmp->coef = ha->coef * hb->coef;
			hb = hb->next;
			ans->next= ltmp;
			ans = ltmp;
		}
		ans->next = NULL;
		fans = add_list(fans,tmp); //将乘法 分解成一次次的加法
		ha = ha->next;
	}
	return fans;
}
void print_list(node* l){
	node *hc;
	int flag = 0;
	hc = l->next; //指针操作常用，用新创立的节点代替源节点操作
	if(hc == NULL){ //格式控制 。。 真坑！
		printf("0 0");
	}
	while(hc != NULL){
		if(flag)
			printf(" ");
		else
			flag = 1;
		printf("%d %d",hc->coef,hc->expn);
		hc = hc->next;
	}
}
int main(){
	int n;
	scanf("%d",&n);
	node *a = creat_list(n);
	int m;
	scanf("%d",&m);
	node* b = creat_list(m);
	node* c = add_list(a,b);
	node* d = multi_list(a,b);
	print_list(d);
	printf("\n");
	print_list(c);
	printf("\n");
	return 0;
}

这篇关于mooc浙大数据结构PTA习题之一元多项式的乘法与加法运算的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！