[数据结构与算法]数据结构 利用单链表实现多项式求和、相乘运算

问题描述：

?

利用单链表实现两个多项式【指数降次输入】的求和、相乘运算。

输入、输出样例：

样例说明：

? ? ? ?输入共分两行，每一行分别代表对应的多项式，两行的第一个数字代表该多项式的项数，之后每两个数字为一组，前者为系数，后者为指数，输入时指数降次排序。

? ? ? ?输出序列只有一行，两个数字为一组，前者为系数，后者为指数，指数同样降次排序。

#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;