数据结构——链表实现一元多项式的表示和加法

一元多项式的链式结构：

Typedef  struct  Lnode
{
    float coef;///系数
    int  expn;///指数
    struct  Lnode  *next;
}  PLnode, *PLinkList;

基本思想：

（1）若pa->expn小于pb->expn,则pa继续向前扫描；
  (2）若pa->expn等于pb->expn,将其系数相加，若相加结果不为0，将结果放入pa->coef中，并删除pb所指的结点，否则同时删除pa和pb所指的结点，然后pa和pb继续向前扫描；

（3）若pa->expn大于pb->expn,则将pb所指的结点插入pa所指的结点之前，然后pb继续向前扫描；
（4）重复上述过程直到pa或pb有一个为空为止，最后将剩余结点的链表接在结果链表上。

PLinklist Add(PLinklist pa,PLinklist pb)
{
    PLinklist p,q,r,s; /*两个多项式相加*/
    int cmp,x;
    p=pa->next;  /*指向pa的第一个元素*/
    q=pb->next; /*指向pb的第一个元素*/
    s=pa; /*s作为P的跟踪指针*/
    r=pb;/*r作为q的跟踪指针*/
    while(p!=NULL&&q!=NULL)
    {
        if(p->exp<q->exp)
        {
            cmp=-1;
        }
        else if(p->exp>q->exp)
        {
            cmp=1;
        }
        else///指数相等
        {
            cmp=0;
        }
        switch(cmp)
        {
        /*根据指数的比较情况进行不同的处理*/
        case -1:
        {
            s=p;
            p=p->next;///pa表指针后移，没有插入
            break;
        }
        case 0:
        {
            x=p->coef+q->coef;///指数相等，系数相加
            if(x!=0) /*系数不为0*/
            {
                p->coef=x;
                s=p;
                p=p->next;
            }/*if*/
            else///系数为0,在pa表中删除该结点
            {
                s->next=p->next;
                free(p);
                p=s->next;
            }/*else*/
            r->next=q->next;///在pb表中删除该结点
            free(q);
            q=r->next;
            break;
            } /*case0*/
        case 1:
        {
            q->next=s->next;
            s->next=q;///将pb表中的q插入到pa表中的s的后面
            r->next=q->next;
            s=q;
            q=r->next;
            break;
            } /*case1*/
        }/*switch*/
    }/*while*/
    if(q!=NULL)///当pb连表还有剩余时接入到pa连表的尾部
    {
        s->next=q;
    }
    free(pb);
    return pa;
}/* Add*/