#include "stdio.h"
#include "malloc.h"

struct  polyNode
{   float coef;       //系数   
     int exp;       //指数
     struct polyNode  *next;        
};
PolyNode,*PolynList;
//在此定义 CreatePoly（）
void CreatePoly（PolynList &L,int n）
{int i;
PolynList p,q;
L=(Polynlist)
}











void copyNode(polyNode* &u, polyNode* &pC,  polyNode* &v)
{    polyNode* w;
    w=(polyNode*)malloc(sizeof(polyNode) );
    w->coef=u->coef;    w->exp=u->exp;
    w->next=NULL;
    v->next=w;
    v=w;
    u=u->next;
}
void AddPoly( polyNode* polyA, polyNode* polyB, polyNode* &polyC)            
{  //方法一：生成一个新链表polyC,然后将polyA,polyB的项复制到polyC
    polyNode *p, *q, *r, *t;
    polyC=(polyNode*)malloc(sizeof(polyNode) );
    polyC->next=NULL;
    p=polyA->next;   q=polyB->next;   r=polyC;
    while(p && q)
    {    if(p->exp > q->exp)
            copyNode(p, polyC, r);
        else if(p->exp < q->exp)
            copyNode(q, polyC, r);
        else
        {    float c;
            c=p->coef+ q->coef;
            if(c ==0)
            {    p=p->next;
                q=q->next;
            }
            else
            {    p->coef=p->coef+q->coef;
                copyNode(p, polyC, r);
                t=q;
                q=q->next;
                free(t);               
            }
        }
    }
    while( p)
        copyNode(p, polyC, r);
    while(q)
        copyNode(q, polyC, r);
   
    //方法二：以链表polyA为基础,将polyB的结点并到polyA。
    polyNode *p, *q, *r, *t;

    polyC=polyA;

    r=polyC;
    p=polyA->next;    q=polyB->next;
    while(q!=NULL)
    {    if(p==NULL)
        {    r->next=q;
            free(polyB);
            break;
        }
        else
        {    if(p->exp > q->exp)
            {    r=p;
                p=p->next;
            }
            else if(p->exp < q->exp)
            {    t=q;
                q=q->next;
                t->next=p;
                r->next=t;
                r=t;
            }
            else
            {    float d;
                d=p->coef +q->coef;
                if(d==0)
                {    t=p;
                    p=p->next;
                    r->next=p;
                    free(t);                    
                }
                else
                {    p->coef=d;
                    r->next=p;
                    p=p->next;

                }
                t=q;
                q=q->next;
                free(t);
            }//end if
        }//end if
    }//end while
   
   
    //方法三：将polyA与polyB平等相待，从二者头部并行往后，依指数大小先后接入polyC
    polyNode *p, *q, *r, *t;

    polyC=polyA;

    r=polyC;
    p=polyA->next;    q=polyB->next;

    while(p!=NULL && q!=NULL)
    {    if(p->exp > q->exp)
        {    r->next=p;
            r=p;
            p=p->next;
        }
        else if(p->exp < q->exp)
        {    r->next=q;
            r=q;
            q=q->next;
        }
        else
        {    float d;
            d=p->coef +q->coef;
            if(d==0)
            {    t=p;
                p=p->next;
                free(t);                    
            }
            else
            {    p->coef=d;
                r->next=p;
                r=p;
                p=p->next;
            }
            t=q;
            q=q->next;
            free(t);
        }//end if
    }//end while
    if( p!=NULL)
        r->next=p;
    if(q!=NULL)
        r->next=q;
    free(polyB);
   
    //方法四（教材算法2.23）：
    //该方法综合方法三和方法四，即没有完全以A为主，将B并入A；同时又偏重于以A为主
    polyNode *p, *q, *r, *t;
    int k;
    float s;

    polyC=polyA;
    r=polyC;
    p=polyA->next;    q=polyB->next;   
   
    while(  p!=NULL  && q!=NULL )               
    {
        k=p->exp - q->exp;
        if( k>0) k=1;
        else if( k<0) k=-1;
   
        switch( k)
        {   case 1: r=p;  p=p->next;     break;     
        
            case 0: s=p->coef+q->coef;
                    if( s!=0)
                    {    p->coef=s;
                        r=p;
                    }
                    else                           
                    {    r->next=p->next;  
                        free (p);
                    }   
                    p=r->next;
                    t=q;    q=q->next;   free(t);  
                                        break;
            case -1: t=q;    q=q->next;            
                    t->next=p;  r->next=t;
                    r=t;
        }
    }
    if( q!=NULL)
    {    r->next=q;   
        free(polyB);
    }
}

void print( polyNode *L)        
{
    polyNode *p;
    p=L->next;
    while( p!=NULL)
    {
        printf("(%.2f,%d),",p->coef,p->exp);
        p=p->next;
    }
    printf("\b \n");
}
void main()
{   
    polyNode  *polyA, *polyB, *polyC;
    int n;
    printf("请输入A表的长度:");
    scanf("%d",&n);
    CreatePoly(polyA,n);
    printf("表A=");     print(polyA);
    printf("请输入B表的长度:");   
    scanf("%d",&n);   CreatePoly(polyB,n);  
    printf("表B=");      print(polyB);
    AddPoly(polyA, polyB,polyC);   
    printf("表C=");      print(polyC);   
}