输入格式:

输入在第一行给出第一个多项式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<stdio.h>
#include<stdlib.h>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<stdio.h>
#include<stdlib.h>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);
}

代码运行如下：