PAT数据结构练习题——02-线性结构2 一元多项式的乘法与加法运算（C++实现）_用双链表实现2个一元多项式的加法和乘法c++代码

1.问题描述

2.注意事项

3.代码（C++实现）

#include<iostream>
using namespace std;

typedef struct NODE {
	int xi;
	int zhi;
	struct NODE* next;
}Node;

Node* Get() {
	int num;
	cin >> num;
	Node* node;
	Node* head;
	Node* temp;
	node = new Node;
	node->next = NULL;
	head = node;
	if (num > 0) {
		for (; num > 0; num--) {
			temp = new Node;
			cin >> temp->xi;
			cin >> temp->zhi;
			temp->next = NULL;
			head->next = temp;
			head = head->next;
		}
	}
	return node;
}

void Print(Node* node) {
	Node* p = node->next;
	if (!p) {
		cout << '0' << ' ' << '0' << endl;
	}
	else
		for (; p; p = p->next) {
			if(p->next != NULL)
				cout << p->xi << ' ' << p->zhi << ' ';
			else
				cout << p->xi << ' ' << p->zhi << endl;
		}
}

Node* Add(Node* n1, Node* n2) {
	Node* add = new Node;
	add->next = NULL;
	Node* t1 = n1->next;
	Node* t2 = n2->next;
	Node* head = add;
	Node* temp;
	while (t1 != NULL && t2 != NULL) {
		if (t1->zhi > t2->zhi) {
			temp = new Node;
			temp->next = NULL;
			temp->zhi = t1->zhi;
			temp->xi = t1->xi;
			add->next = temp;
			add = add->next;
			t1 = t1->next;
		}
		else if (t1->zhi < t2->zhi) {
			temp = new Node;
			temp->next = NULL;
			temp->zhi = t2->zhi;
			temp->xi = t2->xi;
			add->next = temp;
			add = add->next;
			t2 = t2->next;
		}
		else if (t1->zhi == t2->zhi) {
			if (t1->xi + t2->xi == 0) {
			}
			else {
				temp = new Node;
				temp->next = NULL;
				temp->zhi = t1->zhi;
				temp->xi = t1->xi + t2->xi;
				add->next = temp;
				add = add->next;
			}
			t1 = t1->next;
			t2 = t2->next;
		}
	}
	if (t2 != NULL)
		add->next = t2;
	else if (t1 != NULL)
		add->next = t1;
	return head;
}

Node* Mul(Node* n1, Node* n2) {
	Node* t1 = n1->next;
	Node* t2 = n2->next;
	Node* mul = new Node;
	mul->next = NULL;
	int i;
	if (t1 == NULL || t2 == NULL) {
		return mul;
	}
	else {
		for (i=1; t1; t1 = t1->next,i++) {
			Node* hang = new Node;
			hang->next = NULL;
			Node* headhang = hang;
			for (t2 = n2->next; t2; t2 = t2->next) {
				Node* temp = new Node;
				temp->next = NULL;
				temp->xi = t1->xi * t2->xi;
				temp->zhi = t1->zhi + t2->zhi;
				hang->next = temp;
				hang = hang->next;
			}
			mul = Add(mul, headhang);
		}
		return mul;
	}
}

int main() {

	Node* n1;
	n1 = Get();
	Node* n2;
	n2 = Get();
	Node* mul;
	mul = Mul(n1, n2);
	Print(mul);
	Node* add;
	add = Add(n1, n2);
	Print(add);

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136