polynomial多项式相加链表实现（数据结构实验报告）

把任意给定的两个一元多项式P(x) ,Q(x) 输入计算机，计算它们的和并输出计算结果。

1. 工作指针p、q初始化；

2. while（p存在且q存在）执行下列三种情形之一

   2.1 如果p->exp<q->exp，则指针p后移;

   2.2 如果p->exp>q->exp，则

      2.2.1 将结点q插入到结点p之前；

      2.2.2 指针q指向原指结点的下一个结点；

   2.3 如果p->exp=q->exp，则

         
2.3.1 p->coef =p->coef+q–>coef；

        2.3.2 如果p->coef ==0，则执行下列操作，否则，指针p后移;

          2.3.2.1 删除结点p；

          2.3.2.2 使指针p指向它原指结点的下一个结点；

      2.3.3 删除结点q；

      2.3.4 使指针q指向它原指结点的下一个结点；

     3. 如果q不为空，将结点q链接在第一个单链表的后面；

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
 typedef struct Poly
 {
     int coef;//表示系数
     int exp;//表示次数（指数）
     struct Poly *next;
 }poly;

 void createlist (poly *&l,int *a,int n)//头插法创建
 {
     poly *s;
     l=(poly*)malloc(sizeof(poly));//创建头结点
     l->next=NULL;
     for(int i=n-1;i>=0;i--)//循环建立数据结点,因为是头插法，要使数组排列顺序不变，我们逆序输入
     {
         s=(poly*)malloc(sizeof(poly));
         s->coef=a[i];
         s->exp=i;
         s->next=l->next;//头插
         l->next=s;
         
     }
 }

 void display(poly *l)//把多项式显示出来
 {
     poly *temp;//temp是临时结点，用于释放被删结点
     poly *p;//p是活动指针 
     p=l;
     while(p!=NULL&&p->next!=NULL)//删除零系数结点
      {
          if(p->next->coef==0)
          {
             temp=p->next;
             p->next=temp->next;
             free(temp);
          }
          p=p->next;

      }
     p=l->next;
     while(p!=NULL)
     {
         if(p->next==NULL||p->next->coef<0)//最后一项和负项不加+
         {
             printf("%dx^%d",p->coef,p->exp);
         }
         else
         {
             printf("%dx^%d+",p->coef,p->exp);
         }
         
         p=p->next;
     }
    
     printf("\n");
 }

 void sum(poly *&L1,poly *&L2)//多项式求和
 {
     poly *p,*q;
     poly *temp;//temp是临时结点，用于释放被删结点
     p=L1;
     q=L2;
     while(p->next!=NULL&&q->next!=NULL)
     {
         if(p->next->exp < q->next->exp)//如果次数不匹配则后移p指针
         {
             p=p->next;

         }
         if(p->next->exp > q->next->exp)//如果次数不匹配 将结点q插入到结点p之前
         {
             poly *mtemp=(poly*)malloc(sizeof(poly));//创建并复制新节点插入
             mtemp->coef=q->next->coef;
             mtemp->exp=q->next->exp;
             mtemp->next=p->next;
             p->next=mtemp;
             q=q->next;//指针q指向原指结点的下一个结点；
         }
        if(p->next->exp==q->next->exp)//如果次数一样则相加
        {
            p->next->coef=p->next->coef+q->next->coef;//加到p上
            p=p->next;
            q=q->next;
         
          }
     }
     if(q!=NULL)//如果q的某一项次数比p的所有项次数都大则衔接再后面
        {
            p=q->next;
        }
     
      while(p!=NULL && p->next!=NULL)//删除零系数结点
      {
          if(p->next->coef==0)
          {
             temp=p->next;
             p->next=temp->next;
             free(temp);
          }
        p=p->next;
      }
 }
 int main()
 {
     int n;
     printf("请输入最高次数：");
     scanf("%d",&n);
     int *p,*q;
     p=(int*)malloc(sizeof(int)*n);//创建数组p，数组下标为次数，元素为系数
     q=(int*)malloc(sizeof(int)*n);//创建数组q，数组下标为次数，元素为系数
     printf("请输入多项式p的系数：\n");
     for(int i=0;i<n;i++)
     {
         scanf("%d",&p[i]);
     }
     printf("请输入多项式q的系数：\n");
     for(int i=0;i<n;i++)
     {
         scanf("%d",&q[i]);
    }
    
     poly *l1,*l2;
     createlist(l1,p,n);
     createlist(l2,q,n);
     printf("多项式p为：\n\n");
     display(l1);
     printf("多项式q为：\n\n");
     display(l2);
     sum(l1,l2);
     printf("\n\n\n");
     printf("求和为：\n");
     display(l1);
     system("pause");
 }