设计函数分别求两个一元多项式的乘积与和。
输入格式:
输入分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
思路:
用链表存储非零项。加法运算可以看成两个有序链表的合并,注意系数为零项要忽略。乘法运算可以看成有序链表的插入,注意系数为零项要删除,同时为了节省时间可以用一个多项式的第一项乘以第二项事先构造一个有序链表。
代码:
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
int ceof;
int expon;
Node *next;
} PolyNode, *Poly;
Poly Read();
void Print(Poly);
void insert(Poly &, int, int);
Poly Add(Poly, Poly);
Poly Multiply(Poly, Poly);
int main()
{
Poly p1 = Read(), p2 = Read(), p3, p4;
p3 = Multiply(p1, p2);
p4 = Add(p1, p2);
Print(p3);
Print(p4);
return 0;
}
void insert(Poly &rear, int ceof, int expon)
{
Poly curNode = new PolyNode;
curNode->ceof = ceof;
curNode->expon = expon;
curNode->next = rear->next;
rear->next = curNode;
rear = curNode;
}
Poly Read()
{
Poly poly = (Poly)malloc(sizeof(PolyNode)), rear, headNode;
poly->next = NULL;
rear = poly;
int n, ceof, expon;
scanf("%d", &n);
while (n--)
{
scanf("%d %d", &ceof, &expon);
insert(rear, ceof, expon);
}
headNode = poly;
poly = poly->next;
delete headNode;
return poly;
}
Poly Add(Poly p1, Poly p2)
{
Poly poly = new PolyNode, rear, headNode;
poly->next = NULL;
rear = poly;
while (p1 && p2)
{
if (p1->expon > p2->expon)
{
insert(rear, p1->ceof, p1->expon);
p1 = p1->next;
}
else if (p1->expon < p2->expon)
{
insert(rear, p2->ceof, p2->expon);
p2 = p2->next;
}
else
{
if (p1->ceof + p2->ceof)
insert(rear, p1->ceof + p2->ceof, p1->expon);
p1 = p1->next;
p2 = p2->next;
}
}
while (p1)
{
insert(rear, p1->ceof, p1->expon);
p1 = p1->next;
}
while (p2)
{
insert(rear, p2->ceof, p2->expon);
p2 = p2->next;
}
headNode = poly;
poly = poly->next;
free(headNode);
return poly;
}
Poly Multiply(Poly p1, Poly p2)
{
if (!p1 || !p2)
return NULL;
Poly poly = new PolyNode, rear, headNode, delNode, t1, t2;
int ceof, expon;
poly->next = NULL;
t1 = p1, t2 = p2;
rear = poly;
while (t2)
{
ceof = t1->ceof * t2->ceof;
expon = t1->expon + t2->expon;
if (ceof)
insert(rear, ceof, expon);
t2 = t2->next;
}
t1 = t1->next;
while (t1)
{
rear = poly, t2 = p2;
while (t2)
{
ceof = t1->ceof * t2->ceof;
expon = t1->expon + t2->expon;
while (rear->next && rear->next->expon > expon)
rear = rear->next;
if (rear->next && rear->next->expon == expon)
{
if (rear->next->ceof + ceof)
rear->next->ceof += ceof;
else
{
delNode = rear->next;
rear->next = delNode->next;
delete delNode;
}
}
else
insert(rear, ceof, expon);
t2 = t2->next;
}
t1 = t1->next;
}
headNode = poly;
poly = poly->next;
free(headNode);
return poly;
}
void Print(Poly L)
{
int flag = 0;
if (L == NULL)
printf("0 0\n");
else
{
for (Poly p = L; p != NULL; p = p->next)
{
if (flag == 0)
flag = 1;
else
printf(" ");
printf("%d %d", p->ceof, p->expon);
}
printf("\n");
}
}