PTA_02_线性结构2_ 一元多项式的乘法与加法运算
问题：
设计函数分别求两个一元多项式的乘积与和。
输入格式：
输入分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
//第一行是乘法的结果，第二行是加法的结果，两两一块表示结果的系数与指数
设计思路：
本题是浙大mooc数据结果中小白专场的对应练习题。
函数设计的思想，利用链表的性质实现多项式的加法与乘法
主要的函数分为：
- main函数
- Attach函数（实现将系数，指数，将当前值插入多项式的尾部）
- read函数，实现存储输入的系数与指数值，将结点串联再一起
- output函数，读取链表的结点，实现链表输出
- compare函数，比较两数的大小，返回特定值
- addploy函数，实现元素的相加运算
- mult函数，实现系数与指数的相乘运算
代码分析
头文件与初始结构
#include<stdio.h>
#include<iostream>
using namespace std;
struct Lnode
{
int coef;
int expon;
struct Lnode* link;
};
typedef struct Lnode* Psnr;
Psnr read();
void output(Psnr P);
Psnr addploy(Psnr p1, Psnr p2);
Psnr mult(Psnr p1, Psnr p2);
主函数
int main()
{
Psnr p1, p2, pp, ps;
p1 = read();
p2 = read();
//output(p1);
//output(p2);
pp = mult(p1, p2);
output(pp);
ps = addploy(p1, p2);
output(ps);
return 0;
}
Attach函数
//实现系数与指数赋值给对应的结点，并且连接到链表的末尾
void Attach(int c, int e, Psnr *rear)
{
Psnr p;
p = (Psnr)malloc(sizeof(struct Lnode));
p->coef = c;
p->expon = e;
p->link = NULL;
(*rear)->link = p;//将该结点添加到链表的末尾
*rear = p;
//动态创建一个空间，使得p指向这个空间，并且p为头节点
//对新节点赋值，并且让新节点的link指向null
//修改rear的值，使得链表的最后一个位置发生改变，再改变rear的朝向
//最后由于是*rear,所以(*rear)->link = p，实现了原来根的连接，*rear = p则只实现当前值的改变，不影响根
}
read函数
Psnr read()
{
int input_num,c,e;
std::cin >> input_num;
Psnr p, rear, t;
p = (Psnr)malloc(sizeof(struct Lnode));
p->link = NULL;//新建一个结构指针空间
rear = p;
while(input_num--)
{
cin >> c >> e;
Attach(c, e, &rear);// 将当前值插入多项式尾部
}
//释放空节点：
//用一个指向结构体的指针先指向p头结点，
//然后移动p，为下一个节点，最后释放t
t = p;
p = p->link;
free(t);
return p;
}
output函数（输出）
void output(Psnr P)
{
int flag = 0;
if (!P)
{
cout << "0 0" << endl;
return;
}
while (P)
{
if (!flag)
flag = 1;
else
cout << " ";
cout << P->coef <<" " << P->expon;
P = P->link;
}
cout << endl;
}
compare函数（比较）
int Compare(int p, int q)
{
if (p > q)
return 1;
else if (p < q)
return -1;
else
return 0;
}
addploy函数（加法函数）
Psnr addploy(Psnr p1,Psnr p2)
{
Psnr rear, p, q;
int sum;
rear = (Psnr)malloc(sizeof(struct Lnode));
rear->link = NULL;
p = rear;
while (p1 && p2)
{//主要比较p1与p2的指数，谁大谁往后移动，指数相等则系数相加，并将其添加的一个新的结点中
switch (Compare(p1->expon,p2->expon))
{
case 1:
Attach(p1->coef, p1->expon, &rear);
p1 = p1->link;
break;
case -1:
Attach(p2->coef, p2->expon, &rear);
p2 = p2->link;
break;
case 0:
sum = p1->coef + p2->coef;
if (sum)
Attach(sum, p1->expon, &rear);
p1 = p1->link;
p2 = p2->link;
break;
}
}//此时处理一行，已经结束，另一行还未结束，则将还未结束的一行全部连接进去
for (; p1; p1 = p1->link)
Attach(p1->coef, p1->expon, &rear);
for (; p2; p2 = p2->link)
Attach(p2->coef, p2->expon, &rear);
rear->link = NULL;
q= p;
p = p->link;//令front指向结果多项式第一个非零项
free(q);//释放临时空表结点
return p;
}
mult函数（乘法函数）
Psnr mult(Psnr p1, Psnr p2)
{
Psnr rear, front, t1, t2,t;
int c, e;
if (!p1 || !p2)
{
return NULL;
}
t1 = p1;
t2 = p2;//t1和t2指向p1与p2的头结点
rear = (Psnr)malloc(sizeof(struct Lnode));//新建内存空间
rear->link = NULL;
front = rear;//front指向rear头结点
//先用P1的第一下个乘以p2，得到新的rear
//先在rear中存入，以便在接下来中可以插入
while (t2)
{
Attach(t1->coef * t2->coef, t1->expon + t2->expon, &front);
t2 = t2->link;
}
t1 = t1->link;
//双重循环，使得t1每一项乘以t2每一项
while (t1)
{
t2 = p2;
front = rear;
while (t2)
{
//指数相加，系数相乘
e = t1->expon + t2->expon;
c = t1->coef * t2->coef;
//寻找插入的位置，比较指数，将当前结果按照指数递降插进结果中
while (front->link && front->link->expon > e)
{//front指向的link的
front = front->link;
}
if (front->link && front->link->expon == e)
{//front下一项指针如果等于要插入的指数，做合并
if (front->link->coef + c)
{//系数相加不得0，进行系数相加
front->link->coef += c;
}
else {//系数相加后等于0，删掉
t = front->link;
front->link = t->link;
free(t);
}
}
else {//rear的下一项指数小于要插入的指数，可以插入
t = (Psnr)malloc(sizeof(struct Lnode));
t->coef = c;
t->expon = e;
t->link = front->link;
front->link = t;
front = front->link;
}
t2 = t2->link;
}
t1 = t1->link;
}
t2 = rear;
rear = rear->link;
free(t2);
return rear;
}