程序代码：

#include <stdio.h>
#include <stdlib.h>

typedef struct node PolyNode ;
typedef struct node* PtrPoly ;

struct node
{
    int coef ;
    int expon ;
    struct node* next ;    
} ;

//建立一个不带表头结点的链式多项式


int Compare( int e1,int e2 )
{
    if(e1>e2) return 2 ;
    else if(e1<e2) return 1 ;
         else return 0 ;
}



PtrPoly Create( int N)
{
    int i ;
    PtrPoly PtrCurrent,PtrPrevious ;
    PtrPoly head ;

    head=NULL;

    for(i=0 ; i<N ; i++)
    {
        PtrCurrent=(PtrPoly)malloc( sizeof(PolyNode) ) ;

        PtrCurrent->next = NULL ;
        scanf("%d" , &PtrCurrent->coef) ;
        scanf("%d" , &PtrCurrent->expon) ;

        if( head==NULL )
            head=PtrCurrent ;
        else
            PtrPrevious->next = PtrCurrent ;

           PtrPrevious = PtrCurrent ;
    }
    return head;    
}


void Attach ( int coef,int expon,PtrPoly *PtrRear )
{
    /*记录尾项位置才能将未处理完的
    另一个多项式的项依次复制到结果多项式,
    并且每次改变的都是表达式尾项的值，我们需要改变的是结点指针的地址*/
    PtrPoly p;
    
    p = (struct node*)malloc( sizeof (struct node) );
    p->coef = coef ;
    p->expon = expon ;

    // 将p指向的新结点插入到当前结果表达式尾项的后面
    (*PtrRear)->next = p ;
    // 修改PtrRear的值
    *PtrRear = p ;        
}


PtrPoly Add( PtrPoly p1,PtrPoly p2 )
{
    PtrPoly front,rear,temp;

    //为了方便链表插入，先用一个临时空结点作为结果多项式链表表头
    rear = ( PtrPoly )malloc( sizeof(PolyNode) ) ;
    front = rear ;

    while( p1&&p2 )
    {
        switch ( Compare(p1->expon,p2->expon) )
        {
            case 2 ://e1>e2
                Attach( p1->coef , p1->expon , &rear ) ;
                p1 = p1->next ;
                break ;
            case 1 ://e1<e2
                Attach( p2->coef , p2->expon , &rear ) ;
                p2 = p2->next ;
                break ;
            case 0 :
                if( (p1->coef + p2->coef) != 0 ) 
                Attach((p1->coef+p2->coef) , p1->expon , &rear ) ;
                p1 = p1->next ;
                p2 = p2->next ;
                break ;
        }
    }

    for( ; p1 ; p1=p1->next) Attach( p1->coef , p1->expon , &rear ) ;
    for( ; p2 ; p2=p2->next) Attach( p2->coef , p2->expon , &rear ) ;

    rear->next = NULL ;
    temp = front ;
    front = front->next ; //链表头结点为空，指向下一个结点即指向结果多项式第一个非0项
    free( temp ) ;

    return front ;

}


//待插入项的值插入结果多项式
PtrPoly Insert( PtrPoly Position , PtrPoly BeforePosition , PtrPoly InsertPoly , PtrPoly p3 )
{
    //新建一个结点将待插入多项式插入结果多项式

    PtrPoly      head = p3 ;
    
    InsertPoly->next = Position ;
    BeforePosition->next = InsertPoly ;
    return head ;
}


PtrPoly Mult(PtrPoly p1,PtrPoly p2)
{
    
    int sum ;
    PtrPoly Position, BeforePosition, InsertPoly ;//当前项，当前结果项的前一项，待插入项
    PtrPoly p3 ; //结果多项式头结点

    //结果多项式初始化
    //为方便插入链表表头设置为空，(当p1,p2都只有一项时)
    //并且插在第一项前面时很方便(虽然这种情况不存在)
    Position = ( PtrPoly )malloc( sizeof(PolyNode) ) ;    
    p3 = Position ;        //记录结果多项式头结点
    Position->next = ( PtrPoly )malloc( sizeof(PolyNode) ) ;//p1的第一项与p2的第一项计算结果保存在结果多项式第一项中
    Position->next->coef = p1->coef * p2->coef ;
    Position->next->expon = p1->expon + p1->expon ;
    Position->next->next = NULL ;

    Position = Position->next ;
    p2 = p2->next ; //p1的第一项与p2的第一项已经计算了

    //将p1的第k项分别与p2的各项相乘然后与结果多项式各项比较
    for( ; p1!=NULL ; p1=p1->next )    
        for( ; p2!=NULL ; p2=p2->next )
        {
            //计算待插入项
            InsertPoly = ( PtrPoly )malloc( sizeof( PolyNode ) ) ;
            InsertPoly->next = NULL ;
            InsertPoly->coef = p1->next->coef * p2->next->coef ;
            InsertPoly->expon = p1->next->expon + p2->next->expon ;

            //当新项指数比结果多项式小的话一直向前比较，直到遇到比它小的结果项或者相等的结果项(注意待插入项指数为最小时)
               do
                {
                    BeforePosition = Position ;//记录当前结果项前一个位置，方便插入，。。。。
                    Position = Position->next ;
                }
               while( ( InsertPoly->expon ) < (Position->next->expon) && Position != NULL) ;            
                
                //如果该项指数比当前结果项指数大，插入到当前结果项之前    
                //如果该项指数与当前结果项指数相同，判断系数和是否为0
                //不为0，求和后，直接将系数和赋给当前结果项
                //为0，删除当前项
               if(Position!=NULL)
               {
                    if(InsertPoly->expon > Position->expon)
                    {    
                        InsertPoly->next = Position ;
                        BeforePosition->next = InsertPoly ;
                    }
                    //    p3 = Insert( Position , BeforePosition , InsertPoly , p3 ) ;
                   
                    else
                    {  
                        sum = Position->coef + Position->coef ;
                        if( sum!=0 )
                        {
                            Position->coef = sum ;
                        }
                        else
                        {
                            BeforePosition->next = Position->next ;    
                        }
                    }
               }
               else
               { BeforePosition->next = InsertPoly ; }

            Position = p3->next ;        //重置Position，使其指向头结点
        }
            p3=p3->next ;//将不带参数的头结点删除
            return p3 ;
}


void PrintfPoly(PtrPoly poly)
{
    while( poly )
    {
        printf("%d " , poly->coef) ;
        printf("%d " , poly->expon) ;
        poly = poly->next ;
    }
    printf("\n") ;

}



int main()
{
   PtrPoly p1 , p2 , AddPoly ,MultPoly;
   int N1,N2;

   scanf("%d",&N1) ;
   scanf("%d",&N2) ;

   p1=Create(N1) ;
   p2=Create(N2) ;

   PrintfPoly(p1) ;
   PrintfPoly(p2) ;


   AddPoly = Add(p1 , p2) ;
   PrintfPoly( AddPoly ) ;

   MultPoly = Mult(p1 , p2) ;
   PrintfPoly(MultPoly) ;
}

[此贴子已经被作者于2015-11-2 20:04编辑过]