一元多项式的乘法与加法运算

一元多项式的乘法与加法运算

#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) {
	if(c==0){return;}
  Polynomial P;
	P = (Polynomial)malloc(sizeof(struct PolyNode));
	P->coef = c;
	P->expon = e;
	P->link = NULL;
	(*pRear)->link = P;   //注意一定要加括号()
	*pRear = P;
}
Polynomial ReadPoly() {
	int N,c,e;
	Polynomial P, t, Rear;
	P = (Polynomial)malloc(sizeof(struct PolyNode));
	P->link = NULL;
	Rear = P;
	scanf("%d",&N);
	while (N--) {
		scanf("%d %d", &c, &e);
		if( c != 0) Attach(c,e,&Rear);
	}
	t = P;
	P = P->link;
	free(t);
	return P;
}
int Compare(int a,int b) {
	if (a>b) {
		return 1;
	}else if (a<b) {
		return -1;
	}
	return 0;
}
Polynomial Add(Polynomial P1, Polynomial P2) {
	Polynomial T1, T2, P,  rear, tempP;
	int sum;
	if (!P1 && !P2) { return NULL; }
	T1 = P1;
	T2 = P2;
	P = (Polynomial)malloc(sizeof(struct PolyNode));
	P->link = NULL;
	rear = P;
	while (T1 && T2) {
		switch (Compare(T1->expon, T2->expon)) {
		case 1:
			Attach(T1->coef, T1->expon, &rear);
			T1 = T1->link;
			break;
		case -1:
			Attach(T2->coef, T2->expon, &rear);
			T2 = T2->link;
			break;
		case 0:
			sum = T1->coef + T2->coef;
			if (sum) Attach(sum, T1->expon, &rear);
			T1 = T1->link;
			T2 = T2->link;
			break;
		}
	}
	for (; T1; T1 = T1->link) Attach(T1->coef, T1->expon, &rear);
	for (; T2; T2 = T2->link) Attach(T2->coef, T2->expon, &rear);
	rear->link = NULL;
	tempP = P; 
	P = P->link; 
	free(tempP);
	return P;
}
Polynomial Mult(Polynomial P1,Polynomial P2) {
	Polynomial P, T1, T2, Rear,tempP,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) {
			c = T1->coef * T2->coef;
			e = T1->expon + T2->expon;
			while (Rear->link && Rear->link->expon > e) {
				Rear = Rear->link;
			}
			if (Rear->link && Rear->link->expon == e) {
				if (Rear->link->coef + c) { //!=0时
					Rear->link->coef += c;
				}
				else {
					tempP = Rear->link;
					Rear->link = tempP->link;
					free(tempP);
				}
			}
			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;
	}
	tempP = P;
	P = P -> link;
  free(tempP);
	return P;
}
void PrintPoly(Polynomial P) {
	int flag = 0;
	if (!P) {printf("0 0\n"); return;}
	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, PP, PS;
	P1 = ReadPoly();
	P2 = ReadPoly();
	PP = Mult(P1,P2);
	PrintPoly(PP);
	PS = Add(P1, P2);
	PrintPoly(PS);
    return 0;
}
上一篇:bugku 变量1


下一篇:使用Python绘制新型冠状肺炎全国增长趋势图