02-线性结构2 一元多项式的乘法与加法运算（C/C++)_02-线性结构2 一元多项式的乘法与加法运算 c++

设计函数分别求两个一元多项式的乘积与和。

输入格式:

输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。

输出格式:

输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。

输入样例:

4 3 4 -5 2 6 1 -2 0
3 5 20 -7 4 3 1

输出样例:

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

分析：

这道题可以用数组或者链表来做，两种方法的完整做法都比较复杂（长）。
链表的话要写一个创建链表函数、合并函数、乘法函数、排序函数（乘法后需再次排序）、输出函数。
后来看一个大佬的文章，他的方法十分巧妙（原博链接）。
因为题目给出了数据的范围，不超过1000，所以在每项指数均不同的情况下最多有1001项，加法最多有1001项，乘法最多有2001项，在此前提下，将数组初始为0，用数组的下标保存指数，数组数据保存系数，不仅可以保证不需要再排序就能按照指数递降的方式输出同时也大大节省了空间。

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

using namespace std;

struct Poly{
    int ex;
    int co;
}Poly[1001];

int main(){
    int A[2002]={0},B[1002]={0};//A保存乘法 B保存加法 
	int n,m;
    scanf("%d",&n);
    int temp1,temp2;//第二个多项式的系数和指数
    for(int i=0;i<n;i++){
        scanf("%d%d",&Poly[i].co,&Poly[i].ex);//Poly保存第一个多项式
        B[Poly[i].ex]+=Poly[i].co;      //指数作为下标，数组中保存系数 
    }
    scanf("%d",&m);
    for(int i=0;i<m;i++){
        scanf("%d%d",&temp1,&temp2);
        B[temp2]+=temp1;//加法运算 若指数相同则系数相加            
        for(int j=0;j<n;j++){ 
            A[temp2+Poly[j].ex]+=(temp1*Poly[j].co);//乘法运算 指数相加，系数相乘
        } 
    }   
    int isfirst=1,flag=0;//isfirst判断是否是第一个输出（保证空格正确），flag判断是否是零多项式
    for(int i=2000;i>=0;i--){
        if(A[i]!=0){
            if(!isfirst) {
               printf(" %d %d",A[i],i);
            }
            if(isfirst){
                isfirst=0;
                printf("%d %d",A[i],i);
            }   
            flag=1;   //如果执行了if语句则不是零多项式
        }
    }

    if(!flag){ //零多项式
		printf("0 0");
	} 
    flag=0;   //重置判断加法输出
    isfirst=1;     
    printf("\n");
    for(int i=1000;i>=0;i--){
        if(B[i]!=0){
            if(!isfirst){
                   printf(" %d %d",B[i],i);
            }
            if(isfirst){
                printf("%d %d",B[i],i);
                isfirst=0;
            }
            flag=1;   
        }   

    }       
    if(!flag) {
		printf("0 0");
	} 
    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

输出输出最好用C的scanf和printf，运行速度快。

一般方法：
要注意的一点是，创建链表时设置了首结点，所以在进行运算时要从首结点的下一个结点开始。
实名辱骂段错误。
经历了无数次段错误终于搞出来了，指针指向一个不存在的地址时就会出现段错误。

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

using namespace std;

typedef struct PolyNode
{
	int coef;            //系数
	int exp;			   //指数
	struct PolyNode *next;
}PolyNode;
typedef PolyNode *Polynomial;
 
 //创建多项式链表  
Polynomial CreateList() {
	int co;   //系数
	int ex;     //指数
	Polynomial p,L,s; 
	L = (Polynomial)malloc(sizeof(PolyNode));
	L->next=NULL;
	s=L; 
	int n;
	scanf("%d",&n);
	while(n--){
		p = (Polynomial)malloc(sizeof(PolyNode));
		scanf("%d%d",&co,&ex);	
		p->coef = co; 
		p->exp = ex; 
		p->next = NULL;
		s->next=p;
		s=p;
	} 
	s->next=NULL;
	return L; 
}

void attach(int c, int e, Polynomial rear)
{
	Polynomial p = (Polynomial)malloc(sizeof(PolyNode));
	p->coef = c;
	p->exp = e;
	p->next=NULL;
	rear->next = p;
	rear = p;
}

//显示
void Display(Polynomial p){
	Polynomial Pointer;
	Pointer = p;
	if (Pointer == NULL){
		printf("0 0");
	}
	int flag=0;
	while (Pointer != NULL){
		if(flag==0){
			printf("%d %d", Pointer->coef, Pointer->exp);
			Pointer = Pointer->next;
			flag=1;
		}
		else{
			printf(" %d %d", Pointer->coef, Pointer->exp);
			Pointer = Pointer->next;
		}
	} 
}


//多项式相乘
Polynomial LinkMult(Polynomial A, Polynomial B){
  	Polynomial front, rear, t, t1, t2;
	front =(Polynomial)malloc(sizeof(PolyNode));
	front->next = NULL;
	rear = front;
	int c, e;
	t1 = A->next; t2 = B->next;
	if (!t1 || !t2)
		return NULL;
	while (t2){
		c = t1->coef*t2->coef;
		e = t1->exp + t2->exp;
		attach(c, e, rear);
		rear=rear->next;
		t2 = t2->next;
	}
	t1 = t1->next;
	while (t1){
		t2 = B->next;
		rear = front;
		while (t2){
			c = t1->coef*t2->coef;
			e = t1->exp + t2->exp;
			while ((rear->next) && (rear->next->exp > e)){
				rear = rear->next;
			}
			if ((rear->next) && (rear->next->exp == e)){
				if ((rear->next->coef + c) != 0){
					rear->next->coef += c;
				}
				else{
					t = rear->next;
					rear->next = t->next;
					free(t);
				}
			}
			else{
				t = (Polynomial)malloc(sizeof(PolyNode));
				t->coef = c;
				t->exp = e;
				t->next = rear->next;
				rear->next = t;
				rear = rear->next; 
			}
			t2 = t2->next;
		}
		t1 = t1->next;
	}
	t = front;
	front = front->next;
	free(t);
	return front;
}

int compare(int a, int b){
	if (a > b)
		return 1;
	if (a < b)
		return 0;
	if (a == b)
		return -1; 
}  
//相加 
Polynomial LinkList(Polynomial A, Polynomial B){
	Polynomial front, rear, t,p1,p2;
	p1=A->next;
	p2=B->next; 
	front =(Polynomial)malloc(sizeof(PolyNode));
	front->next = NULL;
	rear = front;
	int sum = 0;
	if (!p1 && !p2)
		return NULL;
	while (p1&&p2){
		switch (compare(p1->exp, p2->exp)){
		case 1:
			attach(p1->coef, p1->exp, rear);
			rear=rear->next;
			p1 = p1->next;
			break;
		case 0:
			attach(p2->coef, p2->exp, rear);
			rear=rear->next;
			p2 = p2->next;
			break;
		case -1:
			sum = p1->coef + p2->coef;
			if (sum){
				attach(sum, p1->exp, rear);
				rear=rear->next;
			}
			p1 = p1->next;
			p2 = p2->next;
			break;
		}
	}
	for (; p1 != 0;attach(p1->coef, p1->exp, rear),	rear=rear->next, p1 = p1->next);
	for (; p2 != 0;attach(p2->coef, p2->exp, rear),	rear=rear->next, p2 = p2->next);
	t = front;
	front = front->next;
	free(t);
	return front;
}

int main(){
	Polynomial A, B, C,D;
	A = CreateList();
	B = CreateList();
	C=LinkMult(A,B);
	Display(C);
	printf("\n");
	D=LinkList(A,B);
	Display(D);
} 

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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185