#include <iostream>
#include<string>
using namespace std;
typedef struct PolyNode* Polynomial;
struct PolyNode {
int coef;//系数
int expon;//指数
Polynomial link;
};
void Attach(int c, int e, Polynomial* pRear) {
Polynomial P = (Polynomial)malloc(sizeof(struct PolyNode));
P->coef = c;
P->expon = e;
P->link = NULL;
(*pRear)->link = P;
*pRear = P;
}
Polynomial Reverse(Polynomial P) {
Polynomial p, q;
Polynomial H = (Polynomial)malloc(sizeof(struct PolyNode));
H->link = P;
p = H->link;
H->link = NULL;
//头指针位置一直没有变，所以才导致第一个项位置没有变
while (p != NULL) {
q = p->link;
p->link = H->link;
H->link = p;
p = q;
}
return H;
}
Polynomial Read() {
int n;//几个数
int c, e;//系数和指数
Polynomial P, Rear, t;
cin >> n;
P = (Polynomial)malloc(sizeof(struct PolyNode));
P->link = NULL;
Rear = P;
while (n--) {
cin >> c >> e;
Attach(c, e, &Rear);
}
t = P;
P = P->link;
free(t);
return P;
}
Polynomial ReadSub() {
int n;//几个数
int c, e;//系数和指数
Polynomial P, Rear, t;
cin >> n;
P = (Polynomial)malloc(sizeof(struct PolyNode));
P->link = NULL;
Rear = P;
while (n--) {
cin >> c >> e;
Attach(-c, e, &Rear);
}
t = P;
P = P->link;
free(t);
return P;
}
Polynomial PrintOr(Polynomial P) {
string result;
int flag = 0;
if (!P) {
cout << '0' << endl;
return 0;//空多项式直接输出0
}
while (P) {
if (!flag)
flag = 1;
else
cout << '\0';
if (P->coef > 0 && P->expon != 1)//系数大于0，指数不等于1,正常写
result = result + "+" + to_string(P->coef) + "x^" + to_string(P->expon);
else if (P->coef > 0 && P->expon == 1)//系数大于0，指数等于1，省略指数
result = result + "+" + to_string(P->coef) + "x";
else if (P->coef < 0 && P->expon != 1 && P->expon != 0)
result = result + to_string(P->coef) + "x^" + to_string(P->expon);
else if (P->coef < 0 && P->expon == 1)
result = result + to_string(P->coef) + "x";
else if (P->coef != 0 && P->expon == 0)
result = result + to_string(P->coef);
P = P->link;
}
if (result[0] == '+') {
result[0] = '\0';
cout << "结果多项式是" << endl;
cout << result << endl;
}
else {
cout << "结果多项式是" << endl;
cout << result << endl;
}
}
Polynomial PrintR(Polynomial P) {
string result;P = P->link;
int flag = 0;
if (!P) {
cout << '0' << endl;
return 0;//空多项式直接输出0
}
while (P) {
if (!flag)
flag = 1;
else
cout << '\0';
if (P->coef > 0 && P->expon != 1)//系数大于0，指数不等于1,正常写
result = result + "+" + to_string(P->coef) + "x^" + to_string(P->expon);
else if (P->coef > 0 && P->expon == 1)//系数大于0，指数等于1，省略指数
result = result + "+" + to_string(P->coef) + "x";
else if (P->coef < 0 && P->expon != 1 && P->expon != 0)
result = result + to_string(P->coef) + "x^" + to_string(P->expon);
else if (P->coef < 0 && P->expon == 1)
result = result + to_string(P->coef) + "x";
else if (P->coef != 0 && P->expon == 0)
result = result + to_string(P->coef);
P = P->link;
}
if (result[0] == '+'){
result[0] = '\0';
cout << "结果多项式是" << endl;
cout << result<<endl;
}
else {
cout << "结果多项式是" << endl;
cout << result<<endl;
}
}
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;
}
Polynomial Add(Polynomial P1, Polynomial P2) {
Polynomial t1, t2, Rear, P;
t1 = P1;
t2 = P2;
P = (Polynomial)malloc(sizeof(struct PolyNode));
Rear = P;
while (t1 && t2) {
if (t1->expon == t2->expon) {
if ((t1->coef + t2->coef) != 0) {
Attach(t1->coef + t2->coef, t1->expon, &Rear);
t1 = t1->link;
t2 = t2->link;
}
else {
t1 = t1->link;
t2 = t2->link;
}
}
else if (t1->expon > t2->expon) {
Attach(t1->coef, t1->expon, &Rear);
t1 = t1->link;
}
else {
Attach(t2->coef, t2->expon, &Rear);
t2 = t2->link;
}
}
while (t1) {
Attach(t1->coef, t1->expon, &Rear);
t1 = t1->link;
}
while (t2) {
Attach(t2->coef, t2->expon, &Rear);
t2 = t2->link;
}
Polynomial t;
t = P; P = P->link; free(t);
return P;
}
void Menu() {
cout << "--------多项式计算--------" << endl;
cout << "-----------------------------" << endl;
cout << "--------按1计算加法-------" << endl;
cout << "--------按2计算减法-------" << endl;
cout << "--------按3计算乘法-------" << endl;
cout << "--------按0退出------------" << endl;
cout << "-----------------------------" << endl;
int n;
Polynomial P1, P2, PP;
cin >> n;
if (n == 0)
exit(0);
cout << "请输入两个多项式" << endl;
cout << "先给出多项式非零项的个数" << endl;
cout << "再以指数递降方式输入一个多项式非零项系数和指数" << endl;
cout << "数字间以空格分隔" << endl;
switch (n) {
case 1:
P1 = Read();
P2 = Read();
PP = Add(P1, P2);
PrintOr(PP);
PP = Reverse(PP);
PrintR(PP);
case 2:
P1 = Read();
P2 = ReadSub();
PP = Add(P1, P2);
PrintOr(PP);
PP = Reverse(PP);
PrintR(PP);
case 3:
P1 = Read();
P2 = Read();
PP = Mult(P1, P2);
PrintOr(PP);
PP = Reverse(PP);
PrintR(PP);
}
}
int main() {
Menu();
return 0;
}