数据结构：用链表表示多项式，并实现多项式的加法运算（C语言）

输入格式:

输入在第一行给出第一个多项式POLYA的系数和指数，并以0,0 结束第一个多项式的输入；

在第二行出第一个多项式POLYB的系数和指数，并以0,0 结束第一个多项式的输入。

输出格式:

对每一组输入，在一行中输出POLYA+POLYB和多项式的系数和指数。

输入样例:

5,0 2,1 1,6 8,15 0,0
-2,1 3,6 4,8 0,0

输出样例:

5,0 4,6 4,8 8,15 

---

分析 首先要进行头文件的说明和结构体的定义 

#include
#include

typedef struct Node
{
    float ratio; //系数
    int index; //指数
    struct Node *next; //下一个指针域
}*PNode,*linkList;

 实现链表的构造和创建

linkList Create_link()
{
    linkList head;
    PNode p,q;
    float ratio;//系数
    int index;//指数

    //创建空链表
    head=(struct Node*)malloc(sizeof(struct Node));
    head->next=NULL;

    q=head;
    scanf("%f %d",&ratio,&index);
    while(ratio!=0 || index!=0)//结束条件是系数和指数同时为0
    {
        p=(struct Node*)malloc(sizeof(struct Node));//给新结点分配空间
        p->next=NULL;
        //采用尾插法的方式插入新的结点
        q->next=p;
        q=p;
        p->index=index;
        p->ratio=ratio;
        scanf("%f %d",&ratio,&index);
    }
    return head;
}

对链表根据指数从小到大进行排序，便于后续的相加操作

void Sort_link(linkList head)
{
    PNode p,q;
    //定义中间变量进行数据的交换
    float temp1;
    int temp2;
    //进行冒泡排序
    for(p=head->next;p!=NULL;p=p->next)
        for(q=p->next;q!=NULL;q=q->next)
        {
            if(q->index > p->index)
            {
                temp1=q->ratio;
                q->ratio=p->ratio;
                p->ratio=temp1;
                temp2=q->index;
                q->index=p->index;
                p->index=temp2;
            }
        }

}

关键函数：两个多项式相加函数

       将两个多项式的每一个结点的指数进行一一比较（以llist1为最终输出链表）

1. llist2的指数 < llist1的指数：将llist2的结点插入到llist1结点的前面
2. llist2的指数 > llist1的指数：继续遍历链表
3. llist2的指数 = llist1的指数：将llist2该结点的系数与llist1该结点的系数相加

•           系数和为0：删除该结点
•           系数和不为0：改变该结点的系数

void Add_List(linkList llist1,linkList llist2)
{
    PNode p,q,pre,temp;
    p=llist1->next;
    q=llist2->next;
    pre=llist1;//始终用pre表示p的前一个结点
    while(p&&q)
    {
        if(q->index < p->index)//进行前插
        {
        temp=q->next;//防止llist2的丢失
        q->next = p;
        pre->next = q;
        pre=q;
        q=temp;
        }
        else if(q->index > p->index)//继续遍历
             {
                 pre=p;
                 p=p->next;
             }
             else
             {
                  if(q->ratio + p->ratio == 0)//相加系数为0，进行删除
                  {
                      pre->next=p->next;
                      free(p);
                  }
                  else
                  {
                      p->ratio=p->ratio+q->ratio;
                      pre=p;
                  }
                  p=pre->next;
                  temp=q;
                  q=q->next;
                  free(temp);
             }
    }
    if(q)//如果q中仍有结点，直接插入到llist1的末尾即可
    {
        pre->next=q;
    }
    free(llist2);
}

最后进行链表的输出操作

void print(linkList head)
{
    PNode p;
    for(p=head->next;p!=NULL;p=p->next)
    {
        printf("%.0f %d ",p->ratio,p->index);
    }
}

主函数

int main()
{
    linkList llist1=Create_link();
    linkList llist2=Create_link();
    Sort_link(llist1);
    Sort_link(llist2);
    Add_List(llist1,llist2);
    print(llist1);
}

---

代码整合如下：

#include
#include

typedef struct Node
{
    float ratio; //系数
    int index; //指数
    struct Node *next; //下一个指针域
}*PNode,*linkList;

linkList Create_link()
{
    linkList head;
    PNode p,q;
    float ratio;//系数
    int index;//指数

    //创建空链表
    head=(struct Node*)malloc(sizeof(struct Node));
    head->next=NULL;

    q=head;
    scanf("%f %d",&ratio,&index);
    while(ratio!=0 || index!=0)//结束条件是系数和指数同时为0
    {
        p=(struct Node*)malloc(sizeof(struct Node));//给新结点分配空间
        p->next=NULL;
        //采用尾插法的方式插入新的结点
        q->next=p;
        q=p;
        p->index=index;
        p->ratio=ratio;
        scanf("%f %d",&ratio,&index);
    }
    return head;
}

void Sort_link(linkList head)
{
    PNode p,q;
    //定义中间变量进行数据的交换
    float temp1;
    int temp2;
    //进行冒泡排序
    for(p=head->next;p!=NULL;p=p->next)
        for(q=p->next;q!=NULL;q=q->next)
        {
            if(q->index < p->index)
            {
                temp1=q->ratio;
                q->ratio=p->ratio;
                p->ratio=temp1;
                temp2=q->index;
                q->index=p->index;
                p->index=temp2;
            }
        }

}

void Add_List(linkList llist1,linkList llist2)
{
    PNode p,q,pre,temp;
    p=llist1->next;
    q=llist2->next;
    pre=llist1;//始终用pre表示p的前一个结点
    while(p&&q)
    {
        if(q->index < p->index)//进行前插
        {
        temp=q->next;//防止llist2的丢失
        q->next = p;
        pre->next = q;
        pre=q;
        q=temp;
        }
        else if(q->index > p->index)//继续遍历
             {
                 pre=p;
                 p=p->next;
             }
             else
             {
                  if(q->ratio + p->ratio == 0)//相加系数为0，进行删除
                  {
                      pre->next=p->next;
                      free(p);
                  }
                  else
                  {
                      p->ratio=p->ratio+q->ratio;
                      pre=p;
                  }
                  p=pre->next;
                  temp=q;
                  q=q->next;
                  free(temp);
             }
    }
    if(q)//如果q中仍有结点，直接插入到llist1的末尾即可
    {
        pre->next=q;
    }
    free(llist2);
}

void print(linkList head)
{
    PNode p;
    for(p=head->next;p!=NULL;p=p->next)
    {
        printf("%.0f %d ",p->ratio,p->index);
    }
}

int main()
{
    linkList llist1=Create_link();
    linkList llist2=Create_link();
    Sort_link(llist1);
    Sort_link(llist2);
    Add_List(llist1,llist2);
    print(llist1);
}

代码运行如下：