链表实现多项式相加

女爷i 2022-06-01 12:38 214阅读 0赞

全文参看：[这里写链接内容][Link 1]  
**一、题目要求**  
使用链表实现多项式的相加，最终输出相加的多项式。默认链表的指数为递增。输入时依次输入系数和指数，以0 0 作为结束标志。  
比如：  
多项式A：1+2\*x-4\*x^4  
多项式B：2-2\*x+5^x^4

输入：  
0 1 2 1 -4 4 0 0  
2 0 -2 1 5 4 0 0

输出：3-4\*x^3+5\*x^4

**二、题目分析**

我们先要解决的问题是多项式的存储问题，即它在计算机中的表现形式，很明显我们只需要存储了多项式的系数和指数即可以开始后面加法计算。这里我们又两种存储方式，一种是线性存储，另一种是链式存储。

线性存储，比如我们采用数组来存储这些数据，理论来说是可以的，但是由于我们的多项式的项数是不确定的，但数组必须在刚开始就必须  
先给定一个初始的大小，这个初始大小我们不好确定，分配少了，没法存储全部多项式，分配多了，会造成空间浪费，所以我们在这里采用链表来存储多项式，每次输入一个多项式节点，我们就分配一个链表的节点，这样便可以合理的节约空间。  
如图中所示，我们准备了A、B两个链表  
链表A表示的多项式: 7 \* X^1 + 2 \* X^2 + 8 \* X^5  
链表B表示的多项式: 2 \* X^1 + (-2 \* X^2) + 2 \* X^3  
链表C是我们最终的和链表

这里我们按照这样的步骤进行处理:

1 . 我们规定三个头指针,分别指向三个链表的头,然后再规定三个移动指针,分别指向当前三个链表中正在处理的那个节点

2 . 我们让A、B、C的移动指针刚开始也处于头指针的位置,然后,我们拿A第一个节点中的指数和B第一个节点中的指数进行比较,这个时候有三种情况:

a情况 . A中当前的节点指数 < B中当前的节点指数 —— 我们将A中的当前节点插入C中,然后向后移动A和C的指针(因为A中当前节点已经处理了)

b情况 . A中当前的节点指数 > B中当前的节点指数 —— 我们将B中的当前节点插入C中,然后向后移动B和C的指针(因为B中当前节点已经处理了) 即图中⑧的情况。

c情况 . A中当前的节点指数 > B中当前的节点指数 —— 此时A和B当前节点指数相同,可以进行系数相加,这时候也会出现两种情况:

情况1 . 系数之和不为0 —— 我们此时将系数之和放到A中的当前节点的系数域,然后将A中的该节点插入C中,然后向后移动C的指针(记住,我们这里不是产生一个新的节点,而是直接更改A的系数域,然后将A的当前节点插入C中),即图中的①和②产生③的过程。

情况2 . 系数之和为0 —— 此时我们不能将系数和为0的项放入链表C中,理论来说我们什么都不用做,但是这里有一个小问题,因为按照情况1来看,我们在系数和不为0时是将A节点直接插到C中,我们假设我们在系数和为0后什么都不做,继续处理A中后续节点,后面遇到一个系数和不为0的情况,我们将后面遇到的这个系数不为0的节点插入C中,那其实也将前面那个系数为0的项也一并插入C中了,以为前面那个系数为0的节点和其他后面的节点一直保持联系。所以我们此时必须在系数和为0时,将A中的当前节点删除了。即图中的④和⑤产生⑥的过程。

无论上面是情况1还是情况2,总之我们都同时处理了节点A和节点B,所以，我们还需要同时将节点A和B的移动指针向后移动。

这里还有一个情况,我们的A、B链表可能长度不是一致的，那么就有可能其中一个链表的移动指针已经移动到了末尾,那么此时,我们就不需要继续移动了,我们只需要将另一个链表中未处理的数据直接接在当前已经生产的C链表的后面即可。

第三步:  
打印输出最终计算所得的和链表表达式

**三、代码的实现**

#include<stdio.h>
    #include<stdlib.h>
    typedef struct Node
    {
        int coef;//coefficient:系数
        int index;//index:指数
        struct Node *next; 
    }node;
    
    node *creat()
    {
        int coef,index;
        node *head,*p;
        head=(node *)malloc(sizeof(node));
        p=head;
        while(1)//系数和指数都为0，作为结束标识 
        {
            scanf("%d",&coef);
            scanf("%d",&index);
            if(coef==0&&index==0)
                break;
            p->next=(node *)malloc(sizeof(node));
            p=p->next;
            p->coef=coef;
            p->index=index;
        }
        p->next=NULL;
        return head;
    } 
    
    node *addpolylist(node *la,node *lb)//polynomial:多项式
    {
        int temp;
        node *lc;
        node *pa,*pb,*pc;
        lc=la;
        pa=la->next;
        pb=lb->next;
        pc=lc;
        while(pa&&pb)
        {
            if(pa->index<pb->index)
            {
                pc->next=pa;
                pa=pa->next;
                pc=pc->next;
            } 
            else if(pa->index==pb->index)
            {
                temp=pa->coef+pb->coef;
                if(temp)
                {
                    pa->coef=temp;
                    pc->next=pa;
                    pa=pa->next;
                    pb=pb->next;
                    pc=pc->next;
                }
                else
                {
                    pa=pa->next;
                    pb=pb->next;
                }
            }
            else
            {
                pc->next=pb;
                pb=pb->next;
                pc=pc->next;
            }
        }
        pc->next=(pa?pa:pb);
        return lc;
    } 
    
    void pri(node *head)
    {
        node *p;
        p=head->next;
        while(p)
        {
            printf("+%d*x^%d ",p->coef,p->index);
            p=p->next;
        }
        printf("\n");
    }
    
    void main()
    {
        node *creat();
        node *addpolylist(node *la,node *lb);
        void pri(node *head);
        node *la,*lb,*lc;
        printf("输入多项式la,以0 0作为结束标识："); 
        la=creat();
        pri(la);
        printf("输入多项式lb,以0 0作为结束标识：");
        lb=creat();
        pri(lb);
        printf("输入两多项式lc：");
        lc=addpolylist(la,lb);
        pri(lc);
    }

**四、代码运行验证**  
略，上传不上去。  
为啥我复制的格式都这么难看

[Link 1]: http://blog.csdn.net/bingjianit/article/details/60779641#