用单链表实现一元多项式的乘法（c++).

#include<iostream> using namespace std; struct elem //链表结点 { int coef; //系数 int exp; //指数 elem*next; }; class linklist { public: linklist(); //无参构造函数 linklist(linklist&a); // 拷贝构造函数 void creatpoly(linklist a); //构建多项式 void mulpoly(linklist&c,linklist a,linklist b); //两个多项式相乘 void printlist(linklist a); //输出多项式 private: struct elem*first; //链表指向头结点的指针 }; void main() { linklist A; //定义三个对象 linklist B; linklist C; cout<<"输入第一个多项式:\n"; A.creatpoly(A); A.printlist(A); cout<<"输入第二个多项式:\n"; B.creatpoly(B); B.printlist(B); cout<<"相乘后的多项式:\n"; C.mulpoly(C,A,B); C.printlist(C); } linklist::linklist() //初始化链表 { first=new elem; //为头指针动态分配内存 first->next=NULL; } linklist::linklist(linklist&a) { first=a.first; } void linklist::creatpoly(linklist a) { struct elem*s; struct elem*p; int coef; int exp; s=a.first; //s结点 do { cout<<"输入coef(-1结束)\n"; //输入系数，输入-1时结束 cin>>coef; if(coef==0) //当输入的系数为零重新输入 { cout<<"输入不能为零请重输!\n"; } }while(coef==0); while(coef!=-1) //当coef!=-1一直输入 { cout<<"输入exp\n"; //输入对应的指数 cin>>exp; p=new elem; //为p所指向的结点动态分配内存，并将p所指向的结点插到s后 p->coef=coef; p->exp=exp; p->next=s->next; s->next=p; s=p; //s指针往前移 do { cout<<"输入coef(-1结束)\n"; cin>>coef; if(coef==0) { cout<<"输入不能为零请重输!\n"; } }while(coef==0); } } void linklist:: mulpoly(linklist&C,linklist a,linklist b) { struct elem*p; struct elem*q; struct elem*r; struct elem*R; for(p=a.first->next;p;p=p->next) { for(q=b.first->next;q;q=q->next) { r=C.first; //r指向头指针 R=r->next; //R为r的后继指针 struct elem*s; s=new elem; s->coef=p->coef*q->coef; //相乘后修改系数和指数的值 s->exp=p->exp+q->exp; if(R==NULL) //当链表为空时将s直接插到r后 { s->next=r->next; r->next=s; } else //当链表不为空 { while(R) //当R 不为空 { if( R->exp<s->exp) { r=R; //往后移 R=R->next; if(R==NULL) //当R为空时将结点插入到链表末尾 { s->next=r->next; r->next=s; } } else if(R->exp==s->exp) //当指数相等 { R->coef=R->coef+s->coef; //系数等于两项系数的和 if(R->coef==0) //如果系数相加后为零就删除此结点 { r->next=R->next; delete R; R=r->next; } r=R; //往后移 R=R->next; } else //当R->exp>s->exp时，将s结点插到R结点前面 { r->next=s; s->next=R; } } } } } } void linklist:: printlist(linklist a) { struct elem*p; p=a.first->next; while(p) { cout<<p->coef<<"x**"<<p->exp<<"\n"; p=p->next; if(p) cout<<"+"; } }