一元多项式加减乘运算-数据结构-课程设计

Polyn.h

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef struct polyn {
	double coef;
	int expn;
	struct polyn* next;
}PolyNode, *PLinkList;

PLinkList CreatePolyn(int n);//创建一元多项式，使一元多项式呈指数递减
void PrintPolyn(PLinkList head);//输出一元多项式
PLinkList Addition(PLinkList L1,PLinkList L2);//多项式的加法
PLinkList Subtraction(PLinkList L1,PLinkList L2);//多项式的减法
PLinkList Reverse(PLinkList head);//将生成的链表逆置，使一元多项式呈指数递增形式
PLinkList MultiplyPolyn(PLinkList L1,PLinkList L2);//多项式的乘法
void Destory(PLinkList L); //销毁 

Polyn.cpp

#include "Polyn.h"
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <iostream>
#include <cmath>
using namespace std;

PLinkList CreatePolyn(int n) {//创建一元多项式，使一元多项式呈指数递减
	PolyNode *p, *q, *s;
	PolyNode *head = NULL;
	int expn2;
	double coef2;
	head = (PLinkList)malloc(sizeof(PolyNode));//动态生成头结点
	if(!head) { exit(-2); }
	
	head->coef = 0.0;//初始化
	head->expn = 0;
	head->next = NULL;
	cout << "依次输入多项式的系数和指数:" << endl; 
	while(n--) {
		cin >> coef2;
		cin >> expn2;
		s = (PLinkList)malloc(sizeof(PolyNode));
		if(!s) { exit(-2); }
		s->expn = expn2;
		s->coef = coef2;
		q = head->next ; // 
		p = head;
		while(q && expn2 < q->expn) {
			p = q;
			q = q->next ;
		}
		if(q == NULL || expn2 > q->expn) {
			p->next = s;
			s->next = q;
		} else {
			q->coef += coef2;
		}
	}
	return head;
}
 
void PrintPolyn(PLinkList head) {//输出一元多项式
	PolyNode *p = head->next ;
	while(p) {
		cout << p->coef;
		//printf("%1.1f",p->coef);
		if(p->expn) {
			cout << "*X^" << p->expn;
			//printf("*x^%d",p->expn);
		}
		if(p->next && p->next->coef > 0){
			cout << "+";
			//printf("+");
		} 
		p = p->next ;
	}
}

//相加 
PolyNode *Addition(PLinkList L1,PLinkList L2) {
    PolyNode *head;
    head = (PLinkList)malloc(sizeof(PolyNode));  //作为返回链 
    if (!head) { exit(-2); }
    head->next = NULL;
    
	PLinkList p = L1->next, q = L2->next, r = head;
	while (p != NULL && q != NULL) {
		PLinkList base = (PLinkList)malloc(sizeof(PolyNode));
		if (!base) { exit(-2); }
		base->next = NULL;
		
		r->next = base;
		if (p->expn > q->expn) {
			base->coef = p->coef;
			base->expn = p->expn;
			p = p->next;
		} else if (p->expn < q->expn) {
			base->coef = q->coef;
			base->expn = q->expn;
			q = q->next;
		} else {
			if (p->coef + q->coef != 0) {
				base->coef = p->coef + q->coef;
				base->expn = p->expn;
			} else {
				r->next = NULL;
				free(base);
			}
			p = p->next;
			q = q->next;
		}
		if (r->next != NULL) {
			r = r->next;
		}
	}
	while (p != NULL) {
		PLinkList base = (PLinkList)malloc(sizeof(PolyNode));
		if (!base) { exit(-2); }
		base->next = NULL;
		r->next = base;
		base->coef = p->coef;
		base->expn = p->expn;
		r = r->next;
		p = p->next;
	}
	while (q != NULL) {
		PLinkList base = (PLinkList)malloc(sizeof(PolyNode));
		if (!base) { exit(-2); }
		base->next = NULL;
		r->next = base;
		base->coef = q->coef;
		base->expn = q->expn;
		r = r->next;
		q = q->next; 
	}
	
	return head;
}


//相减
PolyNode *Subtraction(PLinkList L1,PLinkList L2) {
    PolyNode *head;
    head = (PLinkList)malloc(sizeof(PolyNode));  //作为返回链 
    if (!head) { exit(-2); }
    head->next = NULL;
    
	PLinkList p = L1->next, q = L2->next, r = head;
	while (p != NULL && q != NULL) {
		PLinkList base = (PLinkList)malloc(sizeof(PolyNode));
		if (!base) { exit(-2); }
		base->next = NULL;
		r->next = base;
		if (p->expn > q->expn) {
			base->coef = p->coef;
			base->expn = p->expn;
			p = p->next;
		} else if (p->expn < q->expn) {
			base->coef = -q->coef;
			base->expn = q->expn;
			q = q->next;
		} else {
			if (p->coef != q->coef) {
				base->coef = p->coef - q->coef;
				base->expn = p->expn;
			} else {
				r->next = NULL;
				free(base);
			}
			p = p->next;
			q = q->next;
		}
		if (r->next != NULL) {
			r = r->next;
		}
	}
	while (p != NULL) {
		PLinkList base = (PLinkList)malloc(sizeof(PolyNode));
		if (!base) { exit(-2); }
		base->next = NULL;
		r->next = base;
		base->coef = p->coef;
		base->expn = p->expn;
		r = r->next; 
		p = p->next;
	}
	while (q != NULL) {		
		PLinkList base = (PLinkList)malloc(sizeof(PolyNode));
		if (!base) { exit(-2); }
		base->next = NULL;
		r->next = base;
		base->coef = -q->coef;
		base->expn = q->expn;
		r = r->next; 
		q = q->next;
	}
	
	return head;
}


//置逆 
PolyNode *Reverse(PLinkList head) {//将生成的链表逆置，使一元多项式呈指数递增形式
	PolyNode *q, *r, *p = NULL;
	q = head->next ;
	while(q) {
		r = q->next ;
		q->next = p;
		p = q;
		q = r;
	}
	head->next = p;
	return head;
}

//相乘 
PolyNode *MultiplyPolyn(PLinkList L1,PLinkList L2) {//多项式的乘法
	PolyNode *pa, *pb, *pc, *u, *head;
	int k, maxExp;
	double coef;
	head = (PLinkList)malloc(sizeof(PolyNode));
	if(!head) {
		return NULL;
	}
	head->coef = 0.0;
	head->expn = 0;
	head->next = NULL;
	
	if(L1->next != NULL && L2->next != NULL) {
		maxExp = L1->next->expn + L2->next->expn ;
	}
	else {
		return head;
	}
	
	pc = head; 
	
	L2 = Reverse(L2);
	for(k = maxExp; k >= 0; k--) {
		pa = L1->next ;
		while(pa != NULL && pa->expn > k) {
			pa = pa->next ;
		}
		
		pb = L2->next ;
		while(pb != NULL && pa != NULL && pa->expn + pb->expn < k){
			pb= pb->next ;
		}
		
		coef = 0.0;
		
		while(pa != NULL && pb != NULL) {
			if(pa->expn + pb->expn == k){
				coef += pa->coef * pb->coef ;
				pa = pa->next ;
				pb = pb->next ;
			} else if(pa->expn + pb->expn > k) {
				pa = pa->next ;
			} else {
				pb = pb->next ;
			}
		}
		if(coef != 0.0) {
			u = (PLinkList)malloc(sizeof(PolyNode));
			u->coef = coef;
			u->expn = k;
			
			u->next = pc->next ;
			pc->next = u;
			pc = u;
		}
	}
	L2 = Reverse(L2);
	return head;
}

void Destory(PLinkList L) {
	for (PLinkList base = L->next; L != NULL; base = base->next) {
		free(L);
		L = base;
	}
	return ;
}

main.cpp

#include <iostream> 
#include "Polyn.h"
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
using namespace std;

int main() {
	PLinkList A,B,C,D,E;
	int n;
	
	//构造多项式A 
	cout << "输出多项式A的项数: ";
	cin >> n; 
	A = CreatePolyn(n);
	cout << "A(x) = ";
	PrintPolyn(A);
	cout << endl << endl;
	
	//构造多项式B 
	cout << "输出多项式B的项数: ";
	cin >> n; 
	B = CreatePolyn(n);
	cout << "B(x) = ";
	PrintPolyn(B);
	cout << endl << endl;
	
	cout << "-------------------------多项式运算---------------------------\n";  
	
	//相加
	C = Addition(A, B);
	cout << "A(x) + B(x) = ";
	PrintPolyn(C);
	cout << endl << endl;
		
	
	//相减 
	D = Subtraction(A,B);
	cout << "A(x) - B(x) = ";
	PrintPolyn(D);
	cout << endl << endl;
	
	//相乘 
	E = MultiplyPolyn(A,B);
	cout << "A(x) * B(x) = ";
	PrintPolyn(E);
	cout << endl << endl;
	
	Destory(A);
	Destory(B);
	Destory(C);
	Destory(D);
	Destory(E);
	return 0;
}

运行结果