Manchester- 数据结构-一元多项式加法

解题思路:
①：创建两个多项式链表a，b（思路a=a+b，多项式和的结果存在a中），让ha指向a多项式链表的头结点，让hb指向b多项式链表的头结点，

       头结点的下一个结点才是多项式的第一个项

②：ha->next的项的指数与hb->next的项的指数比较

1. 若ha->next->expn小于hb->next->expn  ,则把hb->next所指向的结点插到ha->next所指向结点前面，

   把hb->next指向结点从b中移除，在让ha=ha->next,ha指向下一个操作项的前一个；

2. 若ha->next->expn等于hb->next->expn  ,把两项的conf相加，赋值给sum，若sum等于0，

   把ha->next和hb->next所指向结点删除，否则ha->next->conf=sum即赋值给当前项，再把把hb->next指向结点从b中移除，在让ha=ha->next,ha指向下一个操作项的前一个；

3. 若ha->next->expn大于hb->next->expn ，我们要找到a中满足指数小于等于hb->next->expn的项，

   然后进行1 或者2 操作，所以让ha=ha->next,进行下一轮比较就可以；

④：把相加后的多项式的头结点返回，也就是ha；

⑤：输出结果，当两个多项式相加结果为0时，可以不输出0，直接换行，或者输出0再换行提交都正确；

参考代码：

#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include <stdlib.h>
typedef struct Node_ {
    double    conf; /*见题目中sum=0.0我以为系数有小数，所以就设置为double*/
    int    expn;

    struct Node_* next;
}*node, Node;
/*======================================*/
node Creat_LS( char x[] );

node Add_F( node ha, node hb );

int Compare_( node a, node b );

void Out_put( node ha );

void free_space( node ha );


/*======================================*/
int main()
{
    char    a[201], b[201];
    node    ha, hb;
    while ( gets( a ) != NULL )/*此处不能用EOF*/
    {
        gets( b );

        /*创建多项式链表a，b*/
        ha    = Creat_LS( a );
        hb    = Creat_LS( b );
        /*实现多项式加*/
        ha = Add_F( ha, hb );
        /*输出结果*/
        Out_put( ha );
    }

    return(0);
}


/*======================================*/
node Creat_LS( char x[] )
{
    node    head    = (node) malloc( sizeof(Node) );
    node    q    = head;
    head->next = NULL;
    int length_ = strlen( x );

    int    i = 0, d = 0;
    char    cNum[100], eNum[100];

    while ( i < length_ )
    {
        d = 0; /*初始化下标*/
        node p = (node) malloc( sizeof(Node) );
        /*======================================求conf*/
        /*找到第一个数字字符*/
        while ( x[i] == ' ' && i < length_ )
            i++;
        /*把第一个数放入cNum[100]*/
        while ( x[i] != ' ' && i < length_ )
            cNum[d++] = x[i++];
        /*cNum末尾插入\0*/
        cNum[d] = '\0';
        /*将字符串转化为数字*/
        p->conf = atof( cNum );

        /*======================================求expn*/
        d = 0;
        /*找到第一个数字字符*/
        while ( x[i] == ' ' && i < length_ )
            i++;
        /*把第一个数放入num[100]*/
        while ( x[i] != ' ' && i < length_ )
            eNum[d++] = x[i++];
        /*num末尾插入\0*/
        eNum[d] = '\0';
        /*将字符串转化为数字*/
        p->expn = atoi( eNum );

        /*后插法插入结点*/
        q->next = p;
        p->next = NULL;
        q    = q->next;

        /*到此一个数据项结点创建完毕*/
    }
    return(head);
}


/*======================================*/
node Add_F( node ha, node hb )
{
    int    c;
    double    sum;
    node    HA, term, term1, term2;
    HA = ha; /*用于返回加法结束后结果多项式的头结点*/


    /*这里ha，hb从头结点开始，总是指向待处理结点的前面一个，ha->next就是待处理结点，
     * 所以结束条件为ha->next!=NULL&&hb->next!=NULL，*/
    while ( ha->next != NULL && hb->next != NULL )
    {
        c = Compare_( ha->next, hb->next );
        switch ( c )
        {
        case 0: {       /*把hb->next所指向的结点插入到ha->next指向的结点前面*/
                    /*脱离hb->next指向的结点*/
            term        = hb->next;
            hb->next    = hb->next->next;

            /*插入term到ha->next指向的结点前面*/
            term->next    = ha->next;
            ha->next    = term;

            /*让ha->next，指向下一个处理的项,term的next*/
            ha = ha->next;

            /*hb不用移动，它的next就是下一个待处理的结点项*/
            break;
        }

        case 1: {       /*指数相同，项相加*/
            sum = ha->next->conf + hb->next->conf;
            /*
             * printf("ha_conf=%.0lf\n",ha->next->conf);
             * printf("hb_conf=%.0lf\n",hb->next->conf);
             */
            /*若果系数的和为0，删除a式,b式中当前这两项*/
            if ( sum == 0.0 )
            {
                term1    = ha->next;
                term2    = hb->next;

                ha->next    = ha->next->next;
                hb->next    = hb->next->next;
                free( term1 );
                free( term2 );
                /*此时ha->next,hb->next无需移动*/
            }else  {
                /*ha->next指向结点赋值sum*/
                ha->next->conf = sum;
                /*删除hb->next*/
                term2        = hb->next;
                hb->next    = hb->next->next;
                free( term2 );

                /*使ha指向当前结点，即ha->next指向下一个待处理的项的结点*/
                ha = ha->next;
            }
            break;
        }

        case 2: {       /*当hb->next所指向结点指数小于ha->next所指向结点指数时，
                 * 让 ha=ha->next,开始下一轮比较直到找到小于等于hb->next结点的为止
                 * 就会进行0或1操作，否则直到遍历结束也没找到的话，循环结束后会自己把
                 * hb->next所指向结点加到a末尾*/

                  ha=ha->next;
            break;
        }
        }
    }

    if ( hb->next == NULL )
    /*说明b式加完，没有剩余的项，返回HA*/
    {
        return(HA);
    } else{
        /*把b式中剩余的项加到a式末尾*/
        ha->next = hb->next;
        /*删除b式链表头结点*/
        free( hb );
        return(HA);
    }
}


/*======================================*/
int Compare_( node a, node b )
{
    if ( a->expn < b->expn )
        return(0);
    else
    if ( a->expn == b->expn )
        return(1);
    else
        return(2);
}


/*======================================*/
void Out_put( node ha )
{
    node p = ha->next;


    /*if(p==NULL)
     * printf("0 ");
     * else*/
    /*这个判断可以加也可以不加，提交都正确，也就是两个多项式之和为0，可以输出0，也可以直接不输出换行*/
    {
        while ( p != NULL )
        {
            printf( "%0.lf %d ", p->conf, p->expn );
            p = p->next;
        }
    }
    printf( "\n" );
}


/*======================================*/
void free_space( node ha )
{
/*释放空间*/
    node p = ha, d = NULL;

    while ( p->next != NULL )
    {
        d    = p->next;
        p->next = p->next->next;
        free( d );
    }
    free( ha );
}

别忘点赞哦-.-