参考7-2 一元多项式的乘法与加法运算 (20分)
这道题半写半看ppt写出来的，这个链表真的有些难写；
抄完ppt后还是掉了后面两个测试点，然后找个了个老哥的答案对了一下；
问题是乘法的系数相加为零的情况 和 输出p点为NULL情况：
if(rear->next->coef+coef){
rear->next->coef += coef;
}
else{ //系数相加为0，是零多项式
rear->next->coef=0;
rear->next->expon=0;
// temp = rear->next;
// rear->next = temp->next;
// free(temp);
}
void PrintPoly(Polynomial p)
{
int flag = 1;
if(!p)printf("0 0");
// 下面是省略号
// 。。。。。。
然后代码如下，
#include<bits/stdc++.h>
using namespace std;
typedef struct a *Polynomial;
struct a{
int coef;
int expon;
Polynomial next;
};
void Attach( int coef, int expon, Polynomial *Prear);//系数， 指数， 尾指针；
Polynomial ReadPoly();
Polynomial Poly_Muti(Polynomial a, Polynomial b);
Polynomial Poly_Add(Polynomial a, Polynomial b);
void PrintPoly(Polynomial tmp);
Polynomial ReadPoly()
{
int n, coef, expon;
Polynomial t, p, rear = (Polynomial)malloc(sizeof(struct a));
p = rear;
scanf("%d", &n);
while(n--)
{
scanf("%d %d", &coef, &expon);
Attach(coef, expon, &rear);
}
t = p; p = p->next; free(t);
return p;
}
void Attach( int coef, int expon, Polynomial *Prear) //输入系数， 指数， 尾指针，创建节点，后接，后移
{
Polynomial p;
p = (Polynomial)malloc(sizeof(struct a)); //新建节点；
p->coef = coef; //赋值；
p->expon = expon;
p->next = NULL;
(*Prear)->next = p; //节点接到尾指针后；
*Prear = p; //尾指针后移，指向后接节点；
}
Polynomial Poly_Muti(Polynomial a, Polynomial b)
{
int coef, expon;
Polynomial temp, t1 = a, t2 = b, rear, p = (Polynomial)malloc(sizeof(struct a));
p->next = NULL;
rear = p;
if(!a||!b) return NULL;
while(t2)
{
if(t1->coef*t2->coef)
Attach(t1->coef*t2->coef, t1->expon+t2->expon, &rear);
t2 = t2->next;
}
t1 =t1->next;
while(t1)
{
t2 = b; rear =p;
while(t2)
{
coef = (t1->coef) * (t2->coef);
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->coef+coef){
rear->next->coef += coef;
}
else{ //系数相加为0，是零多项式
rear->next->coef=0;
rear->next->expon=0;
// temp = rear->next;
// rear->next = temp->next;
// free(temp);
}
}
else
{
temp =(Polynomial)malloc(sizeof(struct a));
temp->coef = coef;temp->expon = expon;
temp->next = rear->next;
rear->next = temp;rear = rear->next;
}
t2 = t2->next;
}
t1= t1->next;
}
t2 = p; p= p->next;free(t2);
return p;
}
Polynomial Poly_Add(Polynomial a, Polynomial b)
{
Polynomial t, phead, t1, t2, rear;
t1=a,t2=b;
phead = (Polynomial)malloc(sizeof(struct a)); phead->next = NULL;
rear = phead;
while(t1&&t2)
{
if(t1->expon > t2->expon)
{
Attach(t1->coef, t1->expon, &rear);
t1 = t1->next;
}
else if(t2->expon > t1->expon)
{
Attach(t2->coef, t2->expon, &rear);
t2 = t2->next;
}
else{
int coefSum=t1->coef+t2->coef;
if(coefSum!=0){
Attach(coefSum, t1->expon, &rear);
}
t1=t1->next;
t2=t2->next;
}
}
while(t1)
{
Attach(t1->coef, t1->expon, &rear);
t1 = t1->next;
}
while(t2)
{
Attach(t2->coef, t2->expon, &rear);
t2 = t2->next;
}
t = phead;
phead = phead->next;
free(t); //去头节点；
return phead;
}
void PrintPoly(Polynomial p)
{
int flag = 1;
if(!p)printf("0 0");
while(p)
{
if(flag)
flag = 0;
else printf(" ");
printf("%d %d",p->coef,p->expon);
p=p->next;
}
printf("\n");
}
int main(void)
{
Polynomial a, b, mc, ac, p, pp;
a = ReadPoly();
b = ReadPoly();
mc = Poly_Muti(a, b);
PrintPoly(mc);
ac = Poly_Add(a, b);
PrintPoly(ac);
}