问题描述:
利用单链表实现两个多项式【指数降次输入】的求和、相乘运算。
输入、输出样例:
样例说明:
输入共分两行,每一行分别代表对应的多项式,两行的第一个数字代表该多项式的项数,之后每两个数字为一组,前者为系数,后者为指数,输入时指数降次排序。
输出序列只有一行,两个数字为一组,前者为系数,后者为指数,指数同样降次排序。
#include<stdio.h>
#include<stdlib.h>
typedef struct PolyNode *Polynomial;
struct PolyNode{
int coef;
int expon;
Polynomial link;
};//数据结构定义
/*
两个指针P1和P2分别指向这两个多项式第一个结点,不断循环:
P1->expon == P2->expon: 系数相加,若结果不为0,则作为结果多项式对应项的系数。同时,P1和P2都分别指向下一项;
P1->expon > P2->expon:将P1的当前项存入结果多项式,并使P1指向下一项;
P1->expon < P2->expon:将P2的当前项存入结果多项式,并使P2指向下一项;
当某一多项式处理完时,将另一个多项式的所有结点依次复制到结果多项式中去。
*/
void Attach(int c,int e,Polynomial *pRear){//系数,指数,polynomial类型的指针 (当前最后结果指针位置)
Polynomial P;
P=(Polynomial)malloc(sizeof(struct PolyNode));//申请节点
P->coef=c;//对新节点赋值
P->expon=e;
P->link=NULL;
(*pRear)->link=P;
*pRear=P;//把新申请的节点P插到rear后
}//定义attach函数
int Compare(int e1, int e2)//定义compare函数
{
if (e1==e2) return 0;
else if (e1 > e2) return 1;
else return -1;
}
Polynomial ReadPoly(){
Polynomial P,Rear,t;
int c,e,N;
scanf("%d",&N);//读入整个多项式的项数N
P=(Polynomial)malloc(sizeof(struct PolyNode));
P->link=NULL;//定义一个空节点
Rear=P;//rear指向空节点
while(N--){
scanf("%d%d",&c,&e);
Attach(c,e,&Rear);//rear指针代表当前结果多项式最后一项,
}//读入系数、指数,按照指数递减顺序读入,将读入的新节点插在上一个节点之后
t=P;P=P->link;free(t);//删掉空节点
return P;
}//读入多项式
Polynomial Polyadd(Polynomial P1,Polynomial P2){//P1,P2两个指针指向两个多项式
Polynomial front,rear,temp;//两个指针指向结果多项式的首、尾
int sum;
rear=(Polynomial)malloc(sizeof(struct PolyNode));//内存中申请一个空节点
front=rear;
while (P1&&P2)
switch (Compare(P1->expon,P2->expon)){//用compare函数比较P1,P2所指向的当前项的指数大小, 若P1>P2则返回1,相等返回0;否则返回-1
case 1:
Attach(P1->coef,P1->expon,&rear);//要拷贝的这一项的系数、指数
P1=P1->link;//P1往后移
break;
case -1:
Attach(P2->coef,P2->expon,&rear);
P2=P2->link;
break;
case 0:
sum=P1->coef+P2->coef;//该项系数相加
if(sum) Attach(sum,P1->expon,&rear);
P1=P1->link;
P2=P2->link;
break;
}
for(;P1;P1=P1->link)Attach(P1->coef,P1->expon,&rear);//处理P1不空的情况,把P1剩下的所有项全部拷贝到rear后
for(;P2;P2=P2->link)Attach(P2->coef,P2->expon,&rear);
rear->link=NULL;
temp=front;
front=front->link;//令front指向结果多项式第一个非零项
free(temp);//释放临时空表头结点
return front;
}
Polynomial Mult(Polynomial P1,Polynomial P2){
Polynomial P,Rear,t1,t2,t;
int c,e;
if(!P1||!P2) return NULL;
t1=P1;t2=P2;
P=(Polynomial)malloc(sizeof(struct PolyNode));
P->link=NULL;
Rear=P;
while(t2){
Attach(t1->coef*t2->coef,t1->expon+t2->expon,&Rear);
t2=t2->link;
}
t1=t1->link;
while(t1){
t2=P2;Rear=P;
while(t2){
e=t1->expon+t2->expon;
c=t1->coef*t2->coef;
while(Rear->link&&Rear->link->expon >e){
Rear=Rear->link;}
if(Rear->link&&Rear->link->expon==e){
if(Rear->link->coef+c){
Rear->link->coef+=c;
}else{
t=Rear->link;
Rear->link=t->link;
free(t);
}
}
else{
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;
}t2=P;P=P->link;free(t2);
return P;
}
void PrintPoly(Polynomial P){
int flag=0;
if(!P){printf("0 0\n");return;}//如果多项式是空的,输出00
if(P->expon==P->link->expon){
P->coef+=P->link->coef;
P->link=P->link->link;
P->link=NULL;
}
while(P){
if(!flag)
flag=1;
else
printf(" ");
printf("%d %d",P->coef,P->expon);
P=P->link; //对链表遍历
}printf("\n");
}
int main(){
Polynomial P1,P2,Ps,PP;
printf("请输入多项式1的项数与多项式1每一项的系数与指数:\n");
P1=ReadPoly();//读入多项式1
printf("请输入多项式2的项数与多项式2每一项的系数与指数:\n");
P2=ReadPoly();//读入多项式2
Ps=Polyadd(P1,P2);//多项式求和
printf("多项式1与多项式2的和为:\n");
PrintPoly(Ps);//多项式输出
PP=Mult(P1,P2);
printf("多项式1与多项式2的积为:\n");
PrintPoly(PP);//多项式输出
return 0;