在PTA上刷DS的題目，有些問題和細節(jié)，放上來和大家分享和討論
設(shè)計函數(shù)分別求兩個一元多項式的乘積與和绷耍。
輸入格式:
輸入分2行，每行分別先給出多項式非零項的個數(shù)鲜侥，再以指數(shù)遞降方式輸入一個多項式非零項系數(shù)和指數(shù)（絕對值均為不超過1000的整數(shù)）褂始。數(shù)字間以空格分隔。
輸出格式:
輸出分2行描函，分別以指數(shù)遞降方式輸出乘積多項式以及和多項式非零項的系數(shù)和指數(shù)崎苗。數(shù)字間以空格分隔，但結(jié)尾不能有多余空格舀寓。零多項式應(yīng)輸出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
解答
提交時間 | 狀態(tài) | 分數(shù) | 題目編譯器 | 耗時 | 用戶
2017/10/15 22:52:56 | 答案正確 | 20 | C (gcc) | 2 ms | 王小C
測試點 提示 結(jié)果 耗時 內(nèi)存
0 sample換個數(shù)字 答案正確 2 ms 128KB
1 同類項合并時有抵消 答案正確 2 ms 256KB
2 系數(shù)和指數(shù)取上限，結(jié)果有零多項式 答案正確 2 ms 128KB
3 輸入有零多項式和常數(shù)多項式 答案正確 2 ms 128KB
#include <stdio.h>
#include <stdlib.h>
#ifndef NULL
#define NULL 0
#endif // NULL
typedef struct node *PtrToNode;
struct node
{
int coef;
int expon;
struct node *Next;
};
typedef PtrToNode List;
List createpoly();//create polynomial according to the data from console
List multpoly(List,List);//multiple of two polynomials
void printpoly(List P);//print out a polynomial
List Addpoly(List,List);//the sum up of two polynomial
void Attach(int,int,List *P);//attach a new node to the polynomial
void InsertPoly(int,int,List PP);//insert a new node into a polynomial
int main()
{
List P1,P2,PP,PS;
P1 = createpoly();
P2 = createpoly();
PP = multpoly(P1,P2);
printpoly(PP);
PS = Addpoly(P1,P2);
printpoly(PS);
return 0;
}
List createpoly()
{
List P,ptr,*rear=NULL;
int c,e;
int N;
P = (List)malloc(sizeof(struct node));
P->Next = NULL;
ptr = P;
rear = &ptr;
scanf("%d",&N);
while(N--)
{
scanf(" %d %d",&c,&e);
Attach(c,e,rear); //不確定這里用的應(yīng)該是指針還是prt
}
ptr = P;
P = P->Next;
free(ptr);
return(P);
}
void Attach(int c,int e,List *prear)
{
List P;
P = (List)malloc(sizeof(struct node ));
P->coef = c;
P->expon = e;
P->Next = NULL;
(*prear)->Next = P;
*prear = P;
}
List Addpoly(List P1,List P2)
{
List PP,ptr,t1,t2;
PP = (List)malloc(sizeof(struct node));
PP->Next = NULL;
ptr = PP;
if(!P1&&!P2)
return NULL;
t1 = P1;t2 = P2;
while(t1&&t2)
{
if(t1->expon > t2->expon)
{
Attach(t1->coef,t1->expon,&ptr);
t1 = t1->Next;
}
else if(t2->expon > t1->expon)
{
Attach(t2->coef,t2->expon,&ptr);
t2 = t2->Next;
}
else
{
if(t1->coef + t2->coef == 0)
{
t1 = t1->Next;
t2 = t2->Next;
}
else{
Attach(t1->coef+t2->coef,t1->expon,&ptr);
t1 = t1->Next;
t2 = t2->Next;
}
}
}
while(t1)
{
Attach(t1->coef,t1->expon,&ptr);
t1 = t1->Next;
}
while(t2)
{
Attach(t2->coef,t2->expon,&ptr);
t2 = t2->Next;
}
ptr = PP;
PP = PP->Next;
free(ptr);
return PP;
}
List multpoly(List P1,List P2)
{
List PP,ptr,*prear=NULL,t1,t2;
if(P1 == NULL || P2 == NULL)
return NULL;
PP = (List)malloc(sizeof(struct node));
PP->Next = NULL;
ptr = PP;
prear = &ptr;
t1 = P1;t2 = P2;
while(t2)
{
Attach(t1->coef*t2->coef,t1->expon+t2->expon,prear);
t2 = t2->Next;
}
t1 = t1->Next;
while(t1)
{
t2 = P2;
while(t2)
{
InsertPoly(t1->coef*t2->coef,t1->expon+t2->expon,PP->Next);
t2 = t2->Next;
}
t1 = t1->Next;
}
ptr = PP;
PP = PP->Next;
free(ptr);
return PP;
}
void InsertPoly(int c,int e,List PP)
{
List ptr,P,tempP;
if(PP->expon < e)
{
P = (List)malloc(sizeof(struct node));
P->coef = c;
P->expon = e;
P->Next = PP;
PP = P;
}
else
{
ptr = PP;
while(ptr->Next)
{
if(ptr->Next->expon > e)
ptr = ptr->Next;
else
break;
}
if(ptr->Next == NULL)
{
P = (List)malloc(sizeof(struct node));
P->coef = c;
P->expon = e;
P->Next = NULL;
ptr->Next = P;
}
else if(ptr->Next->expon < e)
{
P = (List)malloc(sizeof(struct node));
P->coef = c;
P->expon = e;
P->Next = ptr->Next;
ptr->Next = P;
}
else
{
ptr->Next->coef += c;
if(ptr->Next->coef == 0)
{
tempP = ptr->Next;
ptr->Next = tempP->Next;
free(tempP);
}
}
}
}
void printpoly(List P)
{
int flag = 0;
List ptr = P;
if(!P)
{
printf("0 0\n");
return ;
}
while(ptr)
{
if(!flag)
{
printf("%d %d",ptr->coef,ptr->expon);
flag = 1;
ptr = ptr->Next;
}
else{
printf(" %d %d",ptr->coef,ptr->expon);
ptr = ptr->Next;
}
}
printf("\n");
}
