链表实现一元多项式加法和乘法

输入：4 3 4 -5 2  6 1  -2 0（4为系数和指数的总对数）
3 5 20  -7 4  3 1（3为系数和指数的总对数）

输出：
15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1
5 20 -4 4 -5 2 9 1 -2 0

#include<iostream>
using namespace std;
typedef struct node {
	int x;
	int z;
	node* next;
}*list;

list read();
void attach(int xx, int zz, list* prear);
list mutiply(list l1, list l2);
list add(list l1, list l2);
void print(list p);

list read() {
	list p, rear, temp;                //头结点 ，尾结点，虚空头结点
	p = new node;
	p->next = NULL;    //创建一个新的空链表（有一个空结点）便于插入
	rear = p;
	int n, xx, zz;
	cin >> n;
	while (n--) {
		cin >> xx >> zz;
		attach(xx, zz, &rear);          
	}
	temp = p;
	p = p->next;
	delete temp;
	return p;
}

//参数里面包含了一个指针的指针指向链表的尾部
void attach(int xx, int zz, list* prear){                    
	list p;              //新增一个结点
	p = new node;
	p->x = xx;
	p->z = zz;
	p->next = NULL;
	(*prear)->next = p;
	*prear = p;
}

list mutiply(list l1, list l2) {
	list tem1, tem2, p, rear, temp;
	int c, e;
	tem1 = l1;
	tem2 = l2;
	p = new node;
	p->next=NULL;
	rear = p;
	if (!l1 || !l2)
		return NULL;
	while (tem2) {                                    //构造l1的第一项和l2的每一项相乘的一个链表为基础进行比较插入
		c = tem1->x * tem2->x;
		e = tem1->z + tem2->z;
		if (c != 0) {
			attach(c, e, &rear);
			tem2 = tem2->next;
		}
	}
	tem1 = tem1->next;                        //从l1的第二项相乘开始比较
	while (tem1) {
		tem2 = l2; 
		rear = p;                                //在从头结点开始比较
		while (tem2) {
			c = tem1->x * tem2->x;
			e = tem1->z + tem2->z;
			if (c != 0) {
				while (rear->next && rear->next->z > e)               //找位置插入，发现比其小的后继位置停止
					rear = rear->next;
				if (rear->next && rear->next->z == e) {
					if (rear->next->x + c)
						rear->next->x += c;
					else {
						temp = rear->next;                           //若系数相加为0 删除后一个结点
						rear->next = temp->next;
						delete temp;
					}
				}
				else {                                             //后继结点小于现有结点的指数  插到其前面
					temp = new node;
					temp->x = c;
					temp->z = e;
					temp->next = rear->next;
					rear->next = temp;
					rear = rear->next;
				}
				tem2 = tem2->next;
			}
		}
		tem1 = tem1->next;
	}
	temp = p;                                //删除虚空头结点
	p = p->next;
	delete temp;
	return p;
}

list add(list l1, list l2) {
	list p, tem1, tem2, rear, temp;
	if (!l1 && !l2) {
		if (!l1)
			return l2;
		else
			return l1;
	}
	p = new node;
	p->next = NULL;
	rear = p;
	tem1 = l1;
	tem2 = l2;
	while (tem1 && tem2) {
		if (tem1->z > tem2->z) {
			if (tem1->x) {
				attach(tem1->x, tem1->z, &rear);
			}
			tem1 = tem1->next;
		}
		else if (tem1->z == tem2->z) {
			if (tem1->x + tem2->x) {
				attach(tem1->x + tem2->x, tem1->z, &rear);
			}
			tem1 = tem1->next;
			tem2 = tem2->next;
		}
		else {
			if (tem2->x) {
				attach(tem2->x, tem2->z, &rear);
			}
			tem2 = tem2->next;
		}
	}
	while (tem1) {
		attach(tem1->x, tem1->z, &rear);
		tem1 = tem1->next;
	}	
	while (tem2) {
		attach(tem2->x, tem2->z, &rear);
		tem2 = tem2->next;
	}
	temp = p;
	p = p->next;                     //删除虚空头结点
	delete temp;
	return p;
}

void print(list p) {
	int flag = 0;
	if (!p) {
		cout << "0 0" << endl;
	}
	while (p) {
		if (!flag)
			flag = 1;
		else
			cout << " ";
		cout << p->x<<ends<< p->z;
		p = p->next;
	}
	cout << endl;
}

int main()
{
	list p1, p2, pp, ps;
	p1 = read();
	p2 = read();
	pp = mutiply(p1, p2);
	print(pp);
	ps = add(p1,p2);
	print(ps);
	return 0;
}