多项式乘法与加法运算（链表实现）

#include<iostream> 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;//这里有点小问题，按理说应该动态申请一块空间，可是加上P=new PolyNode后编译错误...也没太弄懂 P->coef = c; P->expon = e; P->link = NULL; (*pRear)->link = P; (*pRear) = P; } Polynomial Polyread(){ int N,c,e; Polynomial Rear, P,t; cin >> N; P = new PolyNode; P->link = NULL; Rear = P; while (N--){ cin >> c >> e; Attach(c, e, &Rear); } t = P; P = P->link; delete t;//删除临时生成的头结点 return P; } Polynomial Add(Polynomial P1, Polynomial P2){ Polynomial t1, t2, Rear, P; t1 = P1; t2 = P2; P = new PolyNode; P->link = NULL; Rear = P; while (t1&&t2){ if (t1->expon > t2->expon){ Attach(t1->coef, t1->expon, &Rear); t1 = t1->link; } if (t1->expon < t2->expon){ Attach(t1->coef, t2->expon, &Rear); } if (t1->expon == t2->expon){ if (t1->expon + t2->expon){ Attach(t1->coef + t2->coef, t1->expon, &Rear); t1 = t1->link; t2 = t2->link; } } } return P; } Polynomial Mult(Polynomial P1, Polynomial P2){ Polynomial t1, t2, Rear, P,t; int c, e; if (!P1 || !P2) return NULL; t1 = P1; t2 = P2; P = new 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->expon == e){ if (Rear->link->coef + c) Rear->link->coef += c; else{ t = Rear->link; Rear->link = t->link; free(t); } } else{ t = new 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->link = t2->link; delete t2; return P; } void PrintPoly(Polynomial P){ int flag = 0; if (!P) cout << 0 << 0 << endl; while (P){ if (!flag) flag = 1; else cout << " "; cout << P->coef << P->expon; P = P->link; } } int main(){ Polynomial P1, P2, PP, PS; P1 = Polyread(); P2 = Polyread(); PP = Add(P1, P2); PrintPoly(PP); PS = Mult(P1, P2); PrintPoly(PS); return 0; }

代码并没有在编译器中实现，新手渣渣还在学习中，欢迎指正…

在网上看到的正确答案：

#include <iostream> #include <algorithm> #include <vector> using namespace std; typedef struct Term{ int coe;//系数 int exp;//指数 }Term; bool compare(Term a,Term b) { return a.exp>b.exp; } /* Term Mul(Term a,Term b) { a.coe = a.coe*b.coe; a.exp = a.exp+b.exp; return a; } */ /* Term Add(Term a,Term b) { a.coe +=b.coe; return a; }*/ void print(Term a) { cout<<a.coe<<" "<<a.exp<<" "; } int main() { vector<Term> vec1; vector<Term> vec2; vector<Term> vec; vector<Term>::iterator it1,it2; int N1,N2; int coe,exp; bool flag = false; Term t; cin>>N1; while(N1--) { cin>>coe>>exp; t.coe = coe; t.exp = exp; vec1.push_back(t); } //for_each(vec1.begin(),vec1.end(),print); //system("pause"); cin>>N2; while(N2--) { cin>>coe>>exp; t.coe = coe; t.exp = exp; vec2.push_back(t); } //for_each(vec2.begin(),vec2.end(),print); //system("pause"); for (it1=vec1.begin();it1!=vec1.end();it1++) for (it2=vec2.begin();it2!=vec2.end();it2++) { t.coe = it1->coe * it2->coe; t.exp = it1->exp + it2->exp; if (t.coe!=0) vec.push_back(t); } sort(vec.begin(),vec.end(),compare); for (it1 = vec.begin();it1!=vec.end();it1=it2) { for (it2 = it1+1;it2!=vec.end() &&it1->exp==it2->exp;it2++) it1->coe += it2->coe; if (it1->coe!=0) { if (flag) cout<<" "; else flag = true; cout<<it1->coe<<" "<<it1->exp; } } if (vec1.size()==0) { cout<<"0 0"; } cout<<endl; flag = false; for (it1=vec1.begin(),it2=vec2.begin();it1!=vec1.end()&&it2!=vec2.end();) { if (it1->exp >it2->exp) { if (flag) cout<<" "; else flag = true; cout<<it1->coe<<" "<<it1->exp; it1++; } else if (it1->exp < it2->exp) { if (flag) cout<<" "; else flag = true; cout<<it2->coe<<" "<<it2->exp; it2++; } else { if ((it1->coe+it2->coe)) { if (flag) cout<<" "; else flag = true; cout<<it1->coe+it2->coe<<" "<<it1->exp; } it1++; it2++; } } if (it1==vec1.end()) { while(it2!=vec2.end()) { if (flag) cout<<" "; else flag = true; cout<<it2->coe<<" "<<it2->exp; it2++; } } if (it2==vec2.end()) { while(it1!=vec1.end()) { if (flag) cout<<" "; else flag = true; cout<<it1->coe<<" "<<it1->exp; it1++; } } if (flag==false) cout<<"0 0"; cout<<endl; //for_each(vec.begin(),vec.end(),print); //system("pause"); return 0; }