例题详解：
- 一个多项式可以表示为二元组序列{(a1,e1), (a2,e2), … (an,en)}, 其中ai表示第i项的系数（非零值）， ei表示第i项的指数。
- 编写函数建立多项式链表实现一个多项式的输入，按指数从高到低有序，返回链表的头指针。
3) 编写函数实现两个多项式相加，返回结果多项式链表的头指针。
4) 编写函数输出一个多项式的二元组序列。
5) 在main函数中分别调用上述函数，实现输入两个多项式，求出它们的和并输出结果。
6) 输入数据分2行，每行分别先给出多项式非零项的个数，再输入每一对非零项系数和指数（假设为绝对值均为不超过10000的整数）。数字间仅以
空格
分隔。
7) 为简化处理，限定系数与指数都为
整数
。
链表结点数据结构可定义为：
struct PolyNode{
int a; //系数
int e; //指数
PolyNode * next; //指向下一个结点
};
输入样例:
4 3 4 -5 2 6 1 -2 0[注]表示 3×4-5×2+6x-2
3 5 20 -7 4 3 1[注]表示 5×20-7×4+3x
输出样例:
5 20 -4 4 -5 2 9 1 -2 0
[注]表示 5×20-4×4-5×2+9x-2
算法概要：
1.建立两条链x,y（
尾插法
建立）
2.以第一条链x为基准,遍历第二条链比较相加（
双指针遍历
比较指数，称为
双夹法
之前文章中有介绍）
3.若找到相加，若找不到加到第一条链之前（
头插法
：
摘下
单独指数的链节可视为
在第二条链中删去
，以免下一次遍历重复）
4.最后进行排序（遍历测节点数，以便排序）
代码如下：
#include<stdio.h>
#include<stdlib.h>
struct PolyNode {
int a;
int e;
PolyNode *next;
};
struct PolyNode *input(int n);
struct PolyNode *add(struct PolyNode *head1,struct PolyNode *head2);
struct PolyNode *output(struct PolyNode *head);
int main() {
int n,m;
struct PolyNode *x,*y,*z;
scanf("%d",&n);
x=input(n);
scanf("%d",&m);
y=input(m);
z=add(x,y);
output(z);
}
struct PolyNode *input(int s) {
int i;
struct PolyNode *head,*p,*q;
p=(struct PolyNode*)malloc(sizeof (struct PolyNode));
scanf("%d %d",&p->a,&p->e);
q=head=p;
p->next=NULL;
for(i=1; i<s; i++) {//尾插法
p=(struct PolyNode*)malloc(sizeof (struct PolyNode));
scanf("%d %d",&p->a,&p->e);
q->next=p;
p->next=NULL;
q=q->next;
}
return (head);
}
struct PolyNode *add(struct PolyNode *head1,struct PolyNode *head2) {
struct PolyNode *p,*pf,*q,*qf;//双指针记录位置
q=head1;
p=head2;//初始化
while(p!=NULL) {
while(q!=NULL&&q->e!=p->e) {
qf=q;
q=q->next;//遍历第一条链
}
if(q==NULL) { //遍历完，未找到 ，加到1链前面
pf=p;
p=p->next;//p移到下一个
pf->next=head1;
head1=pf;//摘下p,接到1链前面
q=head1;//q重头开始
} else {//找到，相加
q->a+=p->a;
if(q->a==0) {//判断是否系数为0，为0删去
q=q->next;
qf->next=q;//跳过q
}
p=p->next;//p移到下一个
q=head1;//q重头开始
}
}
int atemp,etemp,k,i,j;
//先测有多少节点
p=head1;
while(p!=NULL) {
k++;
p=p->next;
}
//对新链进行冒泡排序,只交换数据
for(i=0; i<k-1; i++) {
p=head1;
q=head1->next;
for(j=0; j<k-i-1; j++) {
if(p->e<q->e) {
atemp=p->a;p->a=q->a;q->a=atemp;
etemp=p->e;p->e=q->e;q->e=etemp;
}
p=p->next;
q=q->next;
}
}
return (head1);
}
struct PolyNode *output(struct PolyNode *head) {
struct PolyNode *z;
for(z=head; z!=NULL; z=z->next) {
printf("%d %d ",z->a,z->e);
}
}
要点强调：
1.利用双指针记录位置便于插入与删除
2.判断系数相加为零的情况
结果：
