02-线性结构2 一元多项式的乘法与加法运算 (20分)数据结构与算法shenbossed的博客-

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

输入格式:
输入分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 

首先是多项式的表示，如果给出多项式个数的确定，我们可以用动态数组来解析这道题目，但是用链表更能锻炼大家的能力。
所以这道题目用的是链表。

首先关于多项式的表示
我们来用结构体表示。

#include<stdio.h> #include<stdlib.h> typedef struct PolyNode *Polynomial; struct PolyNode {  int coef;//多项式系数  int expon;//多项式指数  Polynomial link;//连接下一个结构体的指针 }; 

然后就是程序框架的搭建

int main() { 读入多项式1； 读入多项式2； 乘法预算并输出； 加法运算并输出； return 0； } 

所以要实现的函数就有
读一个多项式；
两多项式相乘；
两多项式相加；
输出多项式；

主函数代码如下:

int main() {   Polynomial P1,P2,PP, PS; P1=ReadPoly(); P2=ReadPoly(); PP=Mult(P1,P2); PS = Add(P1,P2); Print(PP); Print(PS); return 0; } 

读入多项式

Polynomial ReadPoly (void)//读入多项式 {   Polynomial P,Rear,t;   int n,c,e; scanf("%d", &n); P = (Polynomial)malloc(sizeof(struct PolyNode)); P->link = NULL;   Rear = P; while(n--) { scanf("%d %d", &c, &e); Attach(c, e, &Rear); }   t = P; P = P->link; free(t);//去除头结点 return P; } 

插入结点:

void Attach(int c, int e, Polynomial* pRear)//插入函数 {   Polynomial P; P = (Polynomial)malloc(sizeof(struct PolyNode)); P->coef = c; P->expon = e; P->link = NULL; (*pRear)->link = P; *pRear = P; } 

多项式的相乘:

Polynomial Mult(Polynomial P1, Polynomial P2)//多项式相乘 {   Polynomial t1,t2,P,Rear,t;   int e;   int c; if(!P1||!P2) return NULL;//如果p1或者p2任意一个为零多项式，则返回   t1 = P1;   t2 = P2; P = (Polynomial)malloc(sizeof(struct PolyNode)); P->link = NULL;  Rear=P; while(t2)//先将t1的第一项与t2的每一项相乘 { Attach(t1->coef*t2->coef,t1->expon+t2->expon,&Rear);     t2 = t2->link; }   t1 = t1->link; while(t1)//t1的下一项循环与t2相乘 {     Rear = P;//每次都指向p，为了方便排序     t2 = P2; while(t2) {       c = t1->coef*t2->coef;       e = t1->expon+t2->expon; while(Rear->link&&Rear->link->expon>e) Rear=Rear->link;//如果rear的下一个结点大于e，则继续到下一个结点 if(Rear->link &&Rear->link->expon==e)//如果下一个结点存在而且指数相等 { if(Rear->link->coef+c) Rear->link->coef+=c;//系数相加不为0 else{//系数相加为0，则删除这个节点           t = Rear->link;           Rear->link = t->link; free(t); } } else{//rear的下个节点的指数比e小,创造个新结点插到rear后面         t = (Polynomial)malloc(sizeof(struct PolyNode));         t->coef = c;         t->expon=e;         t->link = Rear->link;         Rear->link =t;         Rear = Rear->link;//? }       t2 = t2->link; }     t1 = t1->link; }   t = P; P = P->link; free(t);//删除头结点 return P; } 

多相似的相加:

Polynomial Add(Polynomial P1, Polynomial P2) {   Polynomial t1,t2,P,Rear,t;   int e;   int c; if(!P1&&!P2) return NULL;   t1 = P1;   t2 = P2; P=(Polynomial)malloc(sizeof(struct PolyNode));   Rear = P; while(t1 && t2) { if(t1 -> expon == t2 -> expon)//指数相等,系数相加 { if(t1 -> coef != -(t2 -> coef)) Attach(t1 -> coef + t2 -> coef, t1 -> expon, &Rear);//系数相加不为0       t1 = t1 -> link;       t2 = t2 -> link; } else if(t1 -> expon > t2 -> expon){ Attach(t1 -> coef, t1 -> expon, &Rear);       t1 = t1 -> link; } else { Attach(t2 -> coef, t2 -> expon, &Rear);       t2 = t2 -> link; } }   Rear -> link = t1 ? t1 : t2;//t1为空就传t2，t2为空就传t1   t = P; P = P->link; free(t);//删除头结点 return P; } 

打印链表中的值

void Print(Polynomial P)//打印链表 {   int flag = 0; if (!P) {printf("0 0n"); return;} while(P) { if(!flag) flag = 1; else{ printf(" "); } printf("%d %d", P->coef ,P->expon ); P = P->link; } printf("n"); } 

总的函数如下:

#include<stdio.h> #include<stdlib.h>   typedef struct PolyNode *Polynomial; struct PolyNode {   int coef;   int expon;   Polynomial link; }; void Attach(int c, int e, Polynomial* pRear)//插入函数 {   Polynomial P; P = (Polynomial)malloc(sizeof(struct PolyNode)); P->coef = c; P->expon = e; P->link = NULL; (*pRear)->link = P; *pRear = P; }  Polynomial ReadPoly (void)//读入多项式 {   Polynomial P,Rear,t;   int n,c,e; scanf("%d", &n); P = (Polynomial)malloc(sizeof(struct PolyNode)); P->link = NULL;   Rear = P; while(n--) { scanf("%d %d", &c, &e); Attach(c, e, &Rear); }   t = P; P = P->link; free(t);//去除头结点 return P; }  Polynomial Mult(Polynomial P1, Polynomial P2)//多项式相乘 {   Polynomial t1,t2,P,Rear,t;   int e;   int c; if(!P1||!P2) return NULL;//如果p1或者p2任意一个为零多项式，则返回   t1 = P1;   t2 = P2; P = (Polynomial)malloc(sizeof(struct PolyNode)); P->link = NULL;  Rear=P; while(t2)//先将t1的第一项与t2的每一项相乘 { Attach(t1->coef*t2->coef,t1->expon+t2->expon,&Rear);     t2 = t2->link; }   t1 = t1->link; while(t1)//t1的下一项循环与t2相乘 {     Rear = P;//每次都指向p，为了方便排序     t2 = P2; while(t2) {       c = t1->coef*t2->coef;       e = t1->expon+t2->expon; while(Rear->link&&Rear->link->expon>e) Rear=Rear->link;//如果rear的下一个结点大于e，则继续到下一个结点 if(Rear->link &&Rear->link->expon==e)//如果下一个结点存在而且指数相等 { if(Rear->link->coef+c) Rear->link->coef+=c;//系数相加不为0 else{//系数相加为0，则删除这个节点           t = Rear->link;           Rear->link = t->link; free(t); } } else{//rear的下个节点的指数比e小,创造个新结点插到rear后面         t = (Polynomial)malloc(sizeof(struct PolyNode));         t->coef = c;         t->expon=e;         t->link = Rear->link;         Rear->link =t;         Rear = Rear->link;//? }       t2 = t2->link; }     t1 = t1->link; }   t = P; P = P->link; free(t);//删除头结点 return P; } void Print(Polynomial P)//打印链表 {   int flag = 0; if (!P) {printf("0 0n"); return;} while(P) { if(!flag) flag = 1; else{ printf(" "); } printf("%d %d", P->coef ,P->expon ); P = P->link; } printf("n"); } Polynomial Add(Polynomial P1, Polynomial P2) {   Polynomial t1,t2,P,Rear,t;   int e;   int c; if(!P1&&!P2) return NULL;   t1 = P1;   t2 = P2; P=(Polynomial)malloc(sizeof(struct PolyNode));   Rear = P; while(t1 && t2) { if(t1 -> expon == t2 -> expon)//指数相等,系数相加 { if(t1 -> coef != -(t2 -> coef)) Attach(t1 -> coef + t2 -> coef, t1 -> expon, &Rear);//系数相加不为0       t1 = t1 -> link;       t2 = t2 -> link; } else if(t1 -> expon > t2 -> expon){ Attach(t1 -> coef, t1 -> expon, &Rear);       t1 = t1 -> link; } else { Attach(t2 -> coef, t2 -> expon, &Rear);       t2 = t2 -> link; } }   Rear -> link = t1 ? t1 : t2;//t1为空就传t2，t2为空就传t1   t = P; P = P->link; free(t);//删除头结点 return P; }  int main() {   Polynomial P1,P2,PP, PS; P1=ReadPoly(); P2=ReadPoly(); PP=Mult(P1,P2); PS = Add(P1,P2); Print(PP); Print(PS); return 0; } 

希望大家对链表有更深刻的理解，不要直接抄代码，而是认真分析再抄或者自己动手去写,希望大家能够进步!