设计函数分别求两个一元多项式的乘积与和。
输入格式:
输入分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; }