多项式加法与乘法

#include <iostream>
#include <cmath>
using namespace std;

const int FLAG = -pow(2,31);	//输入结束标志
#define MAX 10000				//数组容量
#define OK 1
#define MALLOCFAILED 0
#define ERROR 0

typedef int Status;
//数据项类型
typedef struct {
	int coef;		//系数
	int exponent;	//指数
}ElemType;

//多项式数据类型
typedef struct PNode {
	ElemType data;		//数据域
	struct PNode* next;	//指针域
}PNode, * Polynomial;

/*		函数声明		*/
void Input_Polynomial(ElemType data[], int& length);				//输入多项式各项
void Array_Qsort(ElemType data[], int low, int high);				//数组快速排序输入的多项式
int Partition(ElemType data[], int low, int high);					//放置元素
Status InitPolynomial(Polynomial& Poly);							//初始化多项式
void InsertList(Polynomial& Poly, ElemType e);						//插入多项式
Status CreatePolynomial2(Polynomial& Poly, ElemType data[], int length);//创建多项式
void CreatePolynomial1(Polynomial& Poly);							//创建多项式
Status Print_Polynomial(Polynomial& Poly);							//打印多项式
Polynomial ADD(Polynomial Poly1, Polynomial Poly2);					//多项式加法
Polynomial Multiply(Polynomial Poly1, Polynomial Poly2);			//多项式乘法
void Destory(Polynomial& Poly);										//销毁多项式

/*	主函数	*/
int main() {
	Polynomial Poly1, Poly2, Sum, Multiply_Ans;
	InitPolynomial(Poly1);			//初始化
	InitPolynomial(Poly2);
	//数组输入
	//ElemType data1[MAX];
	//Input_Polynomial(data1, length);
	//CreatePolynomial(Poly1, data1, length);

	CreatePolynomial1(Poly1);		//创建多项式F(x)
	cout << "F(x): ";
	if (!Print_Polynomial(Poly1))	//打印F(x)
		cout << "Polynomial is NULL";
	puts("\n");
	//数组输入
	//ElemType data2[MAX];
	//Input_Polynomial(data2, length);
	//CreatePolynomial(Poly2, data2, length);

	CreatePolynomial1(Poly2);			//创建多项式G(x)
	cout << "G(x): ";
	if(!Print_Polynomial(Poly2))		//打印G(x)
		cout << "Polynomial is NULL";
	puts("\n");

	Multiply_Ans = Multiply(Poly1, Poly2);	//多项式相乘
	cout << "Multiply_Sum(x) = F(x) * G(x) = ";
	if(!Print_Polynomial(Multiply_Ans))	//打印相乘结果
		cout << "Polynomial is NULL";

	puts("\n");
	Sum = ADD(Poly1, Poly2);			//多项式相加
	cout << "Sum(x) = F(x) + G(x) = ";
	if(!Print_Polynomial(Sum))			//打印相加的结果
		cout << "Polynomial is NULL";
	puts("");
	return 0;
}


void Input_Polynomial(ElemType data[], int& length) {	//输入多项式各项
	length = 1;
	while (1) {

		cout << "The " << length << "th coef is:";
		cin >> data[length].coef;
		cout << "The " << length << "th exponent is:";
		cin >> data[length].exponent;

		if (data[length].coef == FLAG && data[length].exponent == FLAG) {
			length--;									//判断输入结束
			break;
		}
		length++;
	}
	Array_Qsort(data, 1, length);		//排序
}

void Array_Qsort(ElemType data[], int low, int high) {	//快速排序
	if (low < high) {
		int Pivotloc = Partition(data, low, high);		//找到中枢点的位置
		Array_Qsort(data, low, Pivotloc - 1);			//再对左子表进行相同操作
		Array_Qsort(data, Pivotloc + 1, high);			//再对右子表进行相同操作
	}
}

int Partition(ElemType data[], int low, int high) {		//对exponent排序
	data[0] = data[low];	//data[0]作为哨兵,空出low位置
	ElemType pivotkey = data[low];
	while (low < high) {
		while (low < high && data[high].exponent >= pivotkey.exponent) {
			high--;			//从右部分中找出 data[high].exponent(指数) < 基准 放在右部分
		}
		data[low] = data[high];
		while (low < high && data[low].exponent <= pivotkey.exponent) {
			low++;			//从左部分中找出 data[low].exponent(指数) > 基准 放在左部分
		}
		data[high] = data[low];
	}
	data[low] = data[0];	//将最后空出的位置将哨兵归位
	return low;
}

void CreatePolynomial1(Polynomial& Poly) {		//创建链表
	int length = 1;
	ElemType e;
	while (1) {

		cout << "The " << length << "th coef is:";
		cin >> e.coef;
		cout << "The " << length << "th exponent is:";
		cin >> e.exponent;

		if (e.coef == FLAG && e.exponent == FLAG) {	//判断是否到达末尾
			length--;
			break;
		}
		InsertList(Poly, e);					//插入链表
		length++;
	}
}

void InsertList(Polynomial& Poly, ElemType e) {			//插入元素到有序
	Polynomial Node, rear = Poly;						//rear指针指向插入位置的末尾
	while (rear->next != NULL && e.exponent > rear->next->data.exponent) {
		rear = rear->next;								//当rear指针指向结点的后继大于输入数据时候退出循环
	}													//rear指针的后继的位置即为插入位置
	Node = new PNode;
	Node->data = e;
	Node->next = rear->next;							//rear的后继为插入位置
	rear->next = Node;
}

Status InitPolynomial(Polynomial& Poly) {	//初始化多项式
	Poly = new PNode;
	if (!Poly) {
		return MALLOCFAILED;				//空间分配失败
	}
	Poly->next = NULL;						//后继为空
	return OK;
}

Status CreatePolynomial2(Polynomial& Poly, ElemType data[], int length) {	//通过数组创建多项式
	if (length == 0) {
		return ERROR;						//多项式为空
	}
	Polynomial p = Poly;
	for (int i = 1; i <= length; i++) {
		Polynomial node = new PNode;		//分配空间
		node->data = data[i];
		node->next = NULL;
		p->next = node;
		p = p->next;
	}
	return OK;
}

Status Print_Polynomial(Polynomial& Poly) {	//打印多项式
	if (Poly->next == NULL) {
		return ERROR;
	}
	Polynomial p = Poly->next;				//先打印第一个结点，从而解决每个多项式前的符号问题
	if (p->data.exponent == 0) {			//指数为0
		printf("%d ", p->data.coef);		//打印系数
	}
	else {									//指数不为0
		if (p->data.exponent == 1) {		//指数为1，要特殊处理
			if (p->data.coef == -1)			//系数为-1
				printf("-X ");				
			//else if (p->data.coef == 0 && p->next == NULL)	//系数为0
			//	printf("0 ");
			else if (p->data.coef == 1) {	//系数为1
				printf("X ");
			}
			else {							//系数不为0,1
				printf("%dX ",p->data.coef);
			}
		}
		else {								//指数不为1
			if (p->data.coef == -1)			//系数为-1
				printf("-X^%d ", p->data.exponent);
			else if (p->data.coef == 0)		//系数为0
				printf("0 ");
			else if(p->data.coef == 1)		//系数为1
				printf("X^%d ", p->data.exponent);
			else							//系数不为0,1
				printf("%dX^%d ", p->data.coef, p->data.exponent);
		}
	}
	p = p->next;
	while (p) {								//多于一项
		if (p->data.coef < 0)
			printf("- ");
		else
			printf("+ ");
		if (p->data.exponent == 0) {		//指数为0
			printf("%d ", abs(p->data.coef));
		}
		else {								//指数不为0
			if (p->data.coef != 1 && p->data.coef != -1) {
				printf("%d", abs(p->data.coef));
			}
			if (p->data.exponent == 1) {	//指数为1
				printf("X ");
			}
			else {							//指数不为1

				printf("X^%d ", p->data.exponent);
			}
		}
		p = p->next;
	}
	return OK;
}

//Poly1由小到大排列，Poly2由小到大排列，得到的头结点也按照由小到大排列，所以新结点要用尾插法插入
Polynomial ADD(Polynomial Poly1, Polynomial Poly2) {
	Polynomial ans = new PNode;
	InitPolynomial(ans);					//创建结果链表
	if (Poly1 == NULL && Poly2 == NULL) {	//当两个链表为空时返回空指针
		return NULL;
	}
	else {									
		Polynomial p1 = Poly1->next, p2 = Poly2->next, p3 = ans;
		while (p1 != NULL && p2 != NULL) {
			Polynomial node = new PNode;
			if (p1->data.exponent < p2->data.exponent) {		//p1的系数小于p2的系数时，插入p1
				node->data.exponent = p1->data.exponent; node->data.coef = p1->data.coef;
				p1 = p1->next;
			}
			else if (p1->data.exponent > p2->data.exponent) {	//p1的系数大于p2的系数时，插入p2
				node->data.exponent = p2->data.exponent; node->data.coef = p2->data.coef;
				p2 = p2->next;
			}
			else {												//p1 系数 与 p2 系数相同
				node->data.exponent = p2->data.exponent;
				node->data.coef = p1->data.coef + p2->data.coef;
				p1 = p1->next; p2 = p2->next;
				if ((p1 != NULL || p2 != NULL) && node->data.coef == 0) {
					continue;				//当其中一个链表未到达末尾,且相加系数未0,则不插入结果链表中
				}
			}
			node->next = NULL;
			p3->next = node;
			p3 = p3->next;
		}
		/*当前其中一个表未到达末尾*/
		while (p1) {	
			Polynomial node = new PNode;
			node->data.exponent = p1->data.exponent;
			node->data.coef = p1->data.coef;
			node->next = NULL;
			p1 = p1->next;
			p3->next = node;
			p3 = p3->next;
		}
		while (p2) {
			Polynomial node = new PNode;
			node->data.exponent = p2->data.exponent;
			node->data.coef = p2->data.coef;
			node->next = NULL;
			p2 = p2->next;
			p3->next = node;
			p3 = p3->next;
		}
	}
	return ans;	//返回结果链表的头结点
}

//链表相乘，遍历Poly1的链表，Poly1每一项乘以Poly2的每一项
Polynomial Multiply(Polynomial Poly1, Polynomial Poly2) {	
	Polynomial p1 = Poly1->next, Sum = new PNode;
	InitPolynomial(Sum);				//存放相乘的Sum
	if (Poly1 == NULL || Poly2 == NULL || Poly1->next == NULL || Poly2->next == NULL) {
		return Sum;
	}
	else {
		while (p1) {
			Polynomial tmp;
			InitPolynomial(tmp);		//存放p1一项乘以p2所有项的结果
			Polynomial p2 = Poly2->next, p4 = tmp;
			while (p2) {
				Polynomial node = new PNode;
				node->data.coef = p2->data.coef * p1->data.coef;			//系数相乘
				node->data.exponent = p1->data.exponent + p2->data.exponent;//指数相加	
				node->next = NULL;
				p4->next = node;		//尾插法
				p4 = p4->next;
				p2 = p2->next;
			}
			p1 = p1->next;
			Sum = ADD(Sum, tmp);		//将tmp加入Sum中
			Destory(tmp);				//释放tmp的空间
		}	
		return Sum;
	}
}

void Destory(Polynomial& Poly) {		//销毁
	Polynomial p = Poly,q = NULL;
	while (p) {
		q = p;							//记录前驱结点的指针
		p = p->next;
		free(q);						//释放空间
	}	
}