一元多项式求和

一元 多项式求和

处理好指针的问题。

当某A链表某项指数大于B链表某项指数时，将B项插入到A链表。

当A链表某项小于B链某项指数，将A链表指针指向下一项。

当A项等于B项时，将他们的系数相加，如果系数和为0，将A链和B链的项都删除。否则，删除该B项。

这里是将结果直接存放到A链表，如果新建一个链表来保存可能会更简单些。

/*

 * PolyAdd.c
 *
 *  Created on: 2013/07/21
 *      Author: Administrator
 */

#include <stdlib.h>
#include <stdio.h>
#include <stddef.h>

#define ELE_TYPE int

typedef struct PolyEx {
	ELE_TYPE coef;
	ELE_TYPE ex;
	struct PolyEx *next;
}PolyEx;

void init(PolyEx *elem) {
	elem->coef 	= 0;
	elem->ex 	= 0;
	elem->next	= NULL;
}

void destroy(PolyEx *elem) {
	PolyEx *p = elem->next, *temp = NULL;

	while(p) {
		temp = p;
		p = p->next;
		free(temp);
	}
}

void addElem(PolyEx *poly, int coef, int ex) {
	PolyEx *p 		= poly->next;
	PolyEx *newNode = NULL;

	if(!coef) {
		return;
	}

	newNode = (PolyEx*)malloc(sizeof(PolyEx));
	newNode->coef 	= coef;
	newNode->ex 	= ex;
	newNode->next 	= p;
	poly->next 		= newNode;
}

void printPolyEx(PolyEx *ex) {
	PolyEx *p = ex->next;

	while(p) {
		printf("(%2dX^%2d)", p->coef, p->ex);
		p = p->next;
		if(p) {
			printf (" + ");
		}
	}

	printf("\n");
}

void addMerge(PolyEx *ex1, PolyEx *ex2) {
	PolyEx *p3, *p2, *p1, *prev1, *prev2;

	p1		= ex1->next;
	p2		= ex2->next;
	p3 		= ex1;
	prev1	= ex1;
	prev2 	= ex2;

	while(p1 && p2) {
		if(p1->ex > p2->ex) {
			prev2 		= p2;
			p2 			= prev2->next;

			prev2->next	= p1->next;
			p1->next	= prev2;
		}
		else if(p1->ex < p2->ex) {
			prev1 	= p1;
			p1 		= p1->next;
		}
		else {
			if(p1->coef + p2->coef != 0) {
				p1->coef 	+= p2->coef;
				prev1		= p1;
				p1 			= p1->next;
				prev2->next = p2->next;
				free(p2);
				p2 			= prev2->next;
			}
			else {
				prev1->next = p1->next;
				free(p1);
				p1 = prev1->next;

				prev2->next = p2->next;
				free(p2);
				p2 = prev2->next;
			}
		}
	}

	if(p2) {
		prev1->next = p2;
		prev2->next = NULL;
	}
}

void subMerge(PolyEx *ex1, PolyEx *ex2) {
	PolyEx *p2 = ex2->next;

	while(p2) {
		p2->coef *= -1;
		p2 = p2->next;
	}

	addMerge(ex1, ex2);
}

int main(int argc, char* argv[]){
	PolyEx ex1, ex2;
	int i = 0;
	int n1 = 16;
	int n2 = 39;

	init(&ex1);
	init(&ex2);

	for(i = n1; i > -1; i--) {
		addElem(&ex1, i,  i);
	}
	printf("Ex1:\n");
	printPolyEx(&ex1);

	for(i = n2; i > 0; i--) {
		addElem(&ex2, i + 3,  i);
	}
	printf("Ex2:\n");
	printPolyEx(&ex2);

	addMerge(&ex1, &ex2);
	printf("After add:\n");
	printPolyEx(&ex1);

	for(i = n2; i > 1; i--) {
		addElem(&ex2, i * 3,  i);
	}
	printf("Ex2:\n");
	printPolyEx(&ex2);

	subMerge(&ex1, &ex2);
	printf("Ater sub:\n");
	printPolyEx(&ex1);

	destroy(&ex1);
	destroy(&ex2);
}