题目
设计函数，分别求两个一元多项式的乘积与和。
示例
输入
输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。
4 3 4 -5 2 6 1 -2 0
3 5 20 -7 4 3 1
输出
输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。
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
题目分析
输入分析
- 第一个数字是多项式项数
- 后面的数字，分别为系数和指数
- 指数是递降的
使用链表，结点定义如下
typedef struct ListNode* poly;
struct ListNode{
int zhi; //指数
int xi; //系数
poly next; //指向下一个结点
};
结点插入
用作读取、加法和乘法的结点插入，解决链表问题的常规操作。
poly Attach(int xi, int zhi, poly p){
poly temp = malloc(sizeof(poly));
temp->xi = xi;
temp->zhi = zhi;
temp->next = NULL;
p->next = temp;
return p->next;
}
读取输入
使用变量num记录多项式项数，循环调用Attach函数，将新结点插入。
poly ReadPoly(){
poly p = malloc(sizeof(poly));
poly temp = p;
int num;
scanf("%d", &num);
int x, y;
for (int i = 0; i < num; i++){
scanf("%d %d", &x, &y);
temp = Attach(x, y, temp);
}
return p->next;
}
加法的实现
按顺序遍历两个多项式链表a和b，使用结点res和temp储存结果。
若a->zhi > b->zhi,将a储存为新节点;
若a->zhi = b->zhi,将a和b的系数加和，若系数不为0，则储存为新结点；
若a->zhi < b->zhi,将b储存为新节点。
poly add(poly a, poly b){
poly res, temp;
res = malloc(sizeof(poly));
temp = res;
while (a != NULL && b != NULL){
if (a->zhi > b->zhi){
temp = Attach(a->xi, a->zhi, temp);
a = a->next;
}else if (a->zhi == b->zhi){
int xi = a->xi + b->xi;
if (xi != 0){
temp = Attach(a->xi + b->xi, a->zhi, temp);
}
a = a->next;
b = b->next;
}else{
temp = Attach(b->xi, b->zhi, temp);
b = b->next;
}
}
if (a != NULL){
temp->next = a;
}
if (b != NULL){
temp->next = b;
}
return res->next;
}
乘法的实现
乘法的实现是本题的难点。
首先判断是否有空链表，若有，则乘法的结果必然是空链表。
没有空链表的情况，则采用化乘法为加法的方式，用p1去逐项乘以p2，再将得到的结果利用add函数加和即可。
poly mul(poly a, poly b){
if (a == NULL || b == NULL) return NULL;
poly res, temp, p1, p2;
p1 = a;
p2 = b;
res = malloc(sizeof(poly));
temp = res;
while (p2 != NULL){
temp = Attach(p1->xi * p2->xi, p1->zhi + p2->zhi, temp);
p2 = p2->next;
}
p1 = p1->next;
while (p1 != NULL){
p2 = b;
temp = res;
while (p2 != NULL){
int xi, zhi;
xi = p1->xi * p2->xi;
zhi = p1->zhi + p2->zhi;
while (temp->next != NULL && temp->next->zhi > zhi){
temp = temp->next;
}
if (temp->next != NULL && temp->next->zhi == zhi){
temp->next->xi += xi;
if (temp->next->xi == 0){
temp->next = temp->next->next;
}
}else {
poly t = malloc(sizeof(poly));
t->xi = xi;
t->zhi = zhi;
t->next = temp->next;
temp->next = t;
temp = temp->next;
}
p2 = p2->next;
}
p1 = p1->next;
}
return res->next;
}
输出函数
输出要求，输出结尾不可以有多余的空格，需要特殊处理。
利用一个标记变量flag，将其初始值设为0，循环开始后，将其置为1，之后的每次循环都输出一个空格，直到输出结束。
void PrintPoly(poly p){
int flag = 0;
if (p == NULL) printf("0 0");
while (p != NULL){
if (flag == 0) flag = 1;
else {
printf(" ");
}
printf("%d %d", p->xi, p->zhi);
p = p->next;
}
printf("\n");
}
题目解答
#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode* poly;
struct ListNode{
int zhi; //指数
int xi; //系数
poly next; //指向下一个结点
};
poly Attach(int xi, int zhi, poly p){
poly temp = malloc(sizeof(poly));
temp->xi = xi;
temp->zhi = zhi;
temp->next = NULL;
p->next = temp;
return p->next;
}
poly ReadPoly(){
poly p = malloc(sizeof(poly));
poly temp = p;
int num;
scanf("%d", &num);
int x, y;
for (int i = 0; i < num; i++){
scanf("%d %d", &x, &y);
temp = Attach(x, y, temp);
}
return p->next;
}
void PrintPoly(poly p){
int flag = 0;
if (p == NULL) printf("0 0");
while (p != NULL){
if (flag == 0) flag = 1;
else {
printf(" ");
}
printf("%d %d", p->xi, p->zhi);
p = p->next;
}
printf("\n");
}
poly add(poly a, poly b){
poly res, temp;
res = malloc(sizeof(poly));
temp = res;
while (a != NULL && b != NULL){
if (a->zhi > b->zhi){
temp = Attach(a->xi, a->zhi, temp);
a = a->next;
}else if (a->zhi == b->zhi){
int xi = a->xi + b->xi;
if (xi != 0){
temp = Attach(a->xi + b->xi, a->zhi, temp);
}
a = a->next;
b = b->next;
}else{
temp = Attach(b->xi, b->zhi, temp);
b = b->next;
}
}
if (a != NULL){
temp->next = a;
}
if (b != NULL){
temp->next = b;
}
return res->next;
}
poly mul(poly a, poly b){
if (a == NULL || b == NULL) return NULL;
poly res, temp, p1, p2;
p1 = a;
p2 = b;
res = malloc(sizeof(poly));
temp = res;
while (p2 != NULL){
temp = Attach(p1->xi * p2->xi, p1->zhi + p2->zhi, temp);
p2 = p2->next;
}
p1 = p1->next;
while (p1 != NULL){
p2 = b;
temp = res;
while (p2 != NULL){
int xi, zhi;
xi = p1->xi * p2->xi;
zhi = p1->zhi + p2->zhi;
while (temp->next != NULL && temp->next->zhi > zhi){
temp = temp->next;
}
if (temp->next != NULL && temp->next->zhi == zhi){
temp->next->xi += xi;
if (temp->next->xi == 0){
temp->next = temp->next->next;
}
}else {
poly t = malloc(sizeof(poly));
t->xi = xi;
t->zhi = zhi;
t->next = temp->next;
temp->next = t;
temp = temp->next;
}
p2 = p2->next;
}
p1 = p1->next;
}
return res->next;
}
int main(){
poly a, b, res_add, res_mul;
a = ReadPoly();
b = ReadPoly();
res_mul = mul(a, b);
PrintPoly(res_mul);
res_add = add(a, b);
PrintPoly(res_add);
return 0;
}
