c语言——链表——多项式相加

例题详解：

1.    一个多项式可以表示为二元组序列{(a1,e1), (a2,e2), … (an,en)}, 其中ai表示第i项的系数（非零值），  ei表示第i项的指数。
2.    编写函数建立多项式链表实现一个多项式的输入，按指数从高到低有序，返回链表的头指针。

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

[注]表示 3x4-5x2+6x-2

3  5 20 -7 4 3 1

[注]表示 5x20-7x4+3x

输出样例:

5 20 -4 4 -5 2 9 1 -2 0

 [注]表示 5x20-4x4-5x2+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.判断系数相加为零的情况

结果：