一元多项式加减乘运算-数据结构-课程设计
Polyn.h
作者：Accepting!
#include
#include
#include
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
#include
#include
#include
#include
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 << "依次输入多项式的系数和指数:" <> 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 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 <coef;
//printf("%1.1f",p->coef);
if(p->expn) {
cout << "*X^" <expn;
//printf("*x^%d",p->expn);
}
if(p->next && p->next->coef > 0){
cout <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 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 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 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
#include "Polyn.h"
#include
#include
#include
using namespace std;
int main() {
PLinkList A,B,C,D,E;
int n;
//构造多项式A
cout <> n;
A = CreatePolyn(n);
cout << "A(x) = ";
PrintPolyn(A);
cout << endl << endl;
//构造多项式B
cout <> 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;
}
运行结果
作者：Accepting!
