本文除了polyAdd,polyMul,mergerPoly为原创，其他为本人的老师提供的源代码。

C++单链表实现多项式加法(polyAdd)，多项式乘法(polyMul)，多项式合并同类项(mergerPoly)，多项式减法，多项式除法就不贴出来了。

1 #include
     
        2 template
      
         3 class List;  4 template
       
          5 class Node{  6    friend class List
        
         ;  7    private:  8        T coef,exp;  9        Node
         
           *next; 10 }; 11 template
          
            12 class List{ 13 private: 14 Node
           
             *first; 15 public: 16 List(){first=0;} 17 ~List(); 18 bool Empty() const{ return first==0;} 19 int Length()const; 20 int Locate(const T& c,const T& x)const; 21 bool Retrieve(int k,T& c, T& x)const; 22 List
            
             & Insert(int k,const T& c, const T& x); 23 List
             
              & Delete(int k,T& c,T& x); 24 void PrintList(); 25 List
              
               & polyAdd(List
               
                & poly2); 26 List
                
                 & polyMul(List
                 
                  & poly2,List
                  
                   & poly3); 27 List
                   
                    & mergerPoly(); 28 }; 29 template
                    
                      30 List
                     
                      ::~List() 31 { 32 Node
                      
                        *next; 33 while(first){ 34 next=first->next; 35 delete first; 36 first=next; 37 } 38 } 39 template
                       
                         40 int List
                        
                         ::Length()const 41 { 42 Node
                         
                           *current=first; 43 int len=0; 44 while(current){ 45 len++; 46 current=current->next; 47 } 48 return len; 49 } 50 template
                          
                            51 int List
                           
                            ::Locate(const T& c,const T& x)const 52 { 53 Node
                            
                              *current=first; 54 int index=1; 55 while(current&&current->coef!=c&&current->exp!=x){ 56 current=current->next; 57 index++; 58 } 59 if(current)return index; 60 return 0; 61 } 62 template
                             
                               63 bool List
                              
                               ::Retrieve(int k,T& c,T& x)const 64 { 65 if(k<1)return false; 66 Node
                               
                                 *current=first; 67 int index=1; 68 while(index
                                
                                 next; 70 index++; 71 } 72 if(current){ 73 c=current->coef; 74 x=current->exp; 75 return true; 76 } 77 return false; 78 } 79 template
                                 
                                   80 List
                                  
                                   & List
                                   
                                    ::Insert(int k,const T& c,const T& x) 81 { 82 Node
                                    
                                      *p=first; 83 for(int index=1;index
                                     
                                      next; 85 86 Node
                                      
                                        *y=new Node
                                       
                                        ; 87 y->coef=c; 88 y->exp=x; 89 if(k){ 90 y->next=p->next; 91 p->next=y; 92 } 93 else{ 94 y->next=first; 95 first=y; 96 } 97 return *this; 98 } 99 template
                                        
                                         100 List
                                         
                                          & List
                                          
                                           ::Delete(int k,T& c,T& x)101 {102 Node
                                           
                                             *p=first;103 if(k==1)104 first=first->next;105 else{106 Node
                                            
                                              *q=first;107 for(int index=1;index
                                             
                                              next;109 if(!q||!q->next) return *this;110 p=q->next;111 q->next=p->next;112 }113 x=p->exp;114 c=p->coef;115 delete p;116 return *this;117 }118 template
                                              
                                               119 void List
                                               
                                                ::PrintList( )120 {121 Node
                                                
                                                  *current;122 for(current=first;current;current=current->next)123 {124 if (current->coef>=0&&current!=first)125 {126 if (0==current->exp)127 cout<<"+"<
                                                 
                                                  coef;128 else if (1==current->exp)129 cout<<"+"<
                                                  
                                                   coef<<"x";130 else131 cout<<"+"<
                                                   
                                                    coef<<"x^"<
                                                    
                                                     exp;132 }133 else134 {135 if (0==current->exp)136 cout<
                                                     
                                                      coef;137 else if (1==current->exp)138 cout<
                                                      
                                                       coef<<"x";139 else140 cout<
                                                       
                                                        coef<<"x^"<
                                                        
                                                         exp;141 }142 }143 cout<
                                                         
                                                          146 List
                                                          
                                                           & List
                                                           
                                                            ::polyAdd(List
                                                            
                                                             & poly2)147 {148 Node
                                                             
                                                               *p=first,*q=poly2.first,*before=first;149 while(q!=0)150 {151 if (p!=0)152 {153 if (p->exp
                                                              
                                                               exp)154 {155 before=p;156 p=p->next;157 }158 else if (p->exp>q->exp) 159 {160 Insert(Locate(p->coef,p->exp),q->coef,q->exp);161 q=q->next;162 }163 else if (p->exp==q->exp)164 {165 p->coef+=q->coef;166 before=p;167 p=p->next;168 q=q->next;169 }170 }171 else172 {173 Insert(Length(),q->coef,q->exp);174 q=q->next;175 }176 }177 return *this;178 }179 template 
                                                               
                                                                180 List
                                                                
                                                                 & List
                                                                 
                                                                  ::polyMul(List
                                                                  
                                                                   & poly2,List
                                                                   
                                                                    & poly3)181 {182 Node
                                                                    
                                                                      *p=first,*q=poly2.first;183 int i=0;184 T c,x;185 while(p!=0)186 {187 while(q!=0)188 {189 c=p->coef*q->coef;190 x=p->exp+q->exp;191 q=q->next;192 poly3.Insert(i,c,x);193 i++;194 }195 p=p->next;196 q=poly2.first;197 }198 return *this;199 }200 template 
                                                                     
                                                                      201 List
                                                                      
                                                                       & List
                                                                       
                                                                        ::mergerPoly()202 {203 Node
                                                                        
                                                                          *p=first,*q=p->next,*beforeQ=first,*temp;204 while(p!=0&&p->next!=0)205 {206 while(q!=0)207 {208 if (p->exp==q->exp)209 {210 p->coef+=q->coef;211 temp=q->next;212 delete q;213 q=temp;214 beforeQ->next=q;215 }216 else217 {218 beforeQ=q;219 q=q->next;220 }221 }222 p=p->next;223 beforeQ=p;224 if (beforeQ!=0) q=p->next;225 }226 Node
                                                                         
                                                                           *beforeP=0;227 p=first;228 while(p!=0)229 {230 if (0==p->coef)231 { 232 temp=p->next;233 delete p;234 p=temp;235 if (beforeP!=0) beforeP->next=p;236 else first=p;237 }238 else239 {240 beforeP=p;241 p=p->next;242 }243 }244 return *this;245 }246 int main()247 {248 List
                                                                          
                                                                            poly1,poly2,poly3;249 int c,x;250 cout <<"输入第一个多项式，提示：输入0 0，结束多项式输入。"<
                                                                           
                                                                            >c;255 cout <<"请输入多项式的指数:" ;256 cin >>x;257 if (c!=0||x!=0)258 poly1.Insert(poly1.Length(),c,x);259 }260 c=1;261 cout <<"输入第二个多项式，提示：输入0 0，结束多项式输入。"<
                                                                            
                                                                             >c;266 cout <<"请输入多项式的指数:" ;267 cin >>x;268 if (c!=0||x!=0)269 poly2.Insert(poly2.Length(),c,x);270 }271 cout<<"A(x)=";272 poly1.PrintList();273 cout<<"B(x)=";274 poly2.PrintList();275 cout <<"请输入要做的运算，1加法，2乘法：";276 cin >>c;277 if (1==c)278 {279 poly1.polyAdd(poly2);280 poly1.mergerPoly();281 cout <<"A(x)+B(x)=";282 poly1.PrintList();283 }284 else if(2==c)285 {286 poly1.polyMul(poly2,poly3);287 poly3.mergerPoly();288 cout <<"A(x)*B(x)=";289 poly3.PrintList();290 }291 else cout<<"输入错误";292 293 return 0;294 }