数据结构——2.4应用实例之多项式

一、多项式加法运算

数据结构——2.4应用实例之多项式
那么，在计算机中是如何实现的呢？
采用不带头结点的单向链表，按照指数递减的顺序排列各项

算法思路
两个指针p1和p2分别指向这两个多项式第一个结点，不断循环：

p1->expon == p2->expon : 系数相加，若结果不为0，则作为结果多项式对应项的系数。同时p1和p2部分分别指向下一项
p1->expon > p2->expon : 将p1的当前项存入结果多项式，并使p1指向下一项
p1->expon < p2->expon : 将p2的当前项存入结果多项式，并使p2指向下一项
当某一多项式处理完时，将另一个多项式的所有结点依次复制到结果多项式中去。

数据结构——2.4应用实例之多项式


void Attach(int c, int e, Polynomial *pRear) {
	Polynomial P;
	P = (Polynomial)malloc(sizeof(struct PolyNode));
	P->coef = c;	// 对新结点赋值
	P->expon = e;
	P->link = NULL;
	(*pRear)->link = P;
	*pRear = P;		// 修改pRear值
}

Polynomial PolyAdd(Polynomial p1, Polynomial p2) {
	Polynomial front, rear, temp;
	int sum;
	rear = (Polynomial)malloc(sizeof(struct PolyNode));
	front = rear;		// 由front记录结果多项式链表头结点
	while (p1 && p2) {	// 当两个多项式都有非零项待处理时
		switch (Compare(p1->expon, p2->expon)) {
		case 1:
			Attach(p1->coef, p1->expon, &rear);
			p1 = p1->link;
			break;
		case -1:
			Attach(p2->coef, p2->expon, &rear);
			p2 = p2->link;
			break;
		case 0:
			sum = p1->coef + p2->coef;
			if (sum)
				Attach(sum, p1->expon, &rear);
			p1 = p1->link;
			p2 = p2->link;
			break;	
		}
	}
	// 将未处理完的另一个多项式的所有结点依次复制到结果多项式中去
	for (; p1; p1 = p1->link){
		Attach(p1->coef, p1->expon, &rear);
	}
	for (; p2; p2 = p2->link){
		Attach(p2->coef, p2->expon, &rear);
	}
	rear->link = NULL;
	temp = front;
	front = front->link;	// 令front指向结果多项式的第一个非零项
	free(temp);
	return front;
}