#include<stdlib.h> 
#include<stdio.h> 
#include<ctype.h> 

typedef struct term { //項的表示，多項式的項作為LinkList的數據元素 
float coef; //系數 
int expn; //指數 

struct term *next; 
}term; 

term* CreatPolyn(term *P,int m) { // 算法2.22 
// 輸入m項的系數和指數，建立表示一元多項式的有序鏈表P 
if(m <= 0) return NULL; 
term *h = P = (term*)malloc(sizeof(term)), *q; 
P->coef = 0.0; 
int i; 
printf("依次輸入%d個非零項\n",m); 
for (i = 1; i <= m; ++i) { // 依次輸入m個非零項 
scanf("%f%d",&P->coef,&P->expn); 
if(P->coef) 
q = P; 
P = P->next = (term*)malloc(sizeof(term)); 
} 
q->next = NULL; 
free(P); 
return h; 
} // CreatPolyn 

term* selsort(term *h) { 
term *g, *p, *q; 
if(!h) return NULL; 
float f; 
int i, fini = 1; 
for(g = h;g->next&&fini;g = g->next) { 
fini = 0; 
for(p = h,q = h->next;q;p = p->next,q = q->next) 
if (p->expn < q->expn) { 
f = p->coef;i = p->expn; 
p->coef = q->coef;p->expn = q->expn; 
q->coef = f;q->expn = i; 
fini = 1; 
} 
} 
for(g = h,p = g->next;p;) 
if(g->expn==p->expn) { 
g->coef += p->coef; 
g->next = p->next; 
q = p; 
p = p->next; 
free(q); 
} 
else if(g->next) { 
g = g->next; 
p = p->next; 
} 
return h; 
} 

void PrintfPoly(term *P) { 
term *q = P; 
if(!q) { 
putchar('0'); 
return; 
} 
if(q->coef!=1) { 
printf("%g",q->coef); 
if(q->expn==1) putchar('X'); 
else if(q->expn) printf("X^%d",q->expn); 
} 
else if(!q->expn) putchar('1'); 
else if(q->expn==1) putchar('X'); 
else printf("X^%d",q->expn); 
q = q->next; 
while (q) { 
if(q->coef > 0) putchar('+'); 
if(q->coef!=1) { 
printf("%g",q->coef); 
if(q->expn==1) putchar('X'); 
else if(q->expn) printf("X^%d",q->expn); 
} 
else if(!q->expn) putchar('1'); 
else if(q->expn==1) putchar('X'); 
else printf("X^%d",q->expn); 
q = q->next; 
} 
} 

Compare(term *a, term *b) { 
if (a->expn < b->expn) return -1; 
if (a->expn > b->expn) return 1; 
return 0; 
} 

term* APolyn(term *Pa, term *Pb) { // 算法2.23 
// 多項式加法：Pa = Pa＋Pb，利用兩個多項式的結點構成"和多項式"。 
term *h, *qa = Pa, *qb = Pb, *p, *q; 
float sum; 
h = p = (term*)malloc(sizeof(term)); 
p->next = NULL; 
while (qa && qb) { // Pa和Pb均非空 
switch (Compare(qa,qb)) { 
case -1: // 多項式PA中當前結點的指數值小 
p->next = qb; 
p = qb; 
qb = qb->next; 
break; 
case 0: // 兩者的指數值相等 
sum = qa->coef + qb->coef; 
if (sum != 0.0) { // 修改多項式PA中當前結點的系數值 
p->next = qa; 
qa->coef = sum; 
p = qa; 
qa = qa->next; 
} 
else { // 刪除多項式PA中當前結點 
q = qa; 
qa = qa->next; 
free(q); 
} 
q = qb; 
qb = qb->next; 
free(q); 
break; 
case 1: // 多項式PB中當前結點的指數值小 
p->next = qa; 
p = qa; 
qa = qa->next; 
break; 
} // switch 
} // while 
if (Pa) p->next = qa; // 鏈接Pa中剩余結點 
if (Pb) p->next = qb; // 鏈接Pb中剩余結點 
q = h; 
h = h->next; 
free(q); 
return h; 
} // APolyn 

term* A(term *Pa, term *Pb) { 
int n; 
puts("再輸入一一元多項式的項數"); 
scanf("%d",&n); 
Pb = CreatPolyn(Pb,n); 
Pb = selsort(Pb); 
PrintfPoly(Pa); 
if(Pb && Pb->coef>0) printf(" + "); 
PrintfPoly(Pb); 
Pa = APolyn(Pa,Pb); 
printf(" = "); 
Pa = selsort(Pa); 
PrintfPoly(Pa); 
return Pa; 
} 

term* BPolyn(term *Pa, term *Pb) { // 算法2.23 
// 多項式減法：Pa = Pa-Pb，利用兩個多項式的結點構成"差多項式"。 
term *p = Pb; 
while(p) { 
p->coef *= -1; 
p = p->next; 
} 
return APolyn(Pa,Pb); 
} // BPolyn 

term* B(term *Pa, term *Pb) { 
int n; 
puts("再輸入一一元多項式的項數"); 
scanf("%d",&n); 
Pb = CreatPolyn(Pb,n); 
Pb = selsort(Pb); 
PrintfPoly(Pa); 
printf(" - "); 
putchar('(');PrintfPoly(Pb);putchar(')'); 
Pa = BPolyn(Pa,Pb); 
printf(" = "); 
Pa = selsort(Pa); 
PrintfPoly(Pa); 
return Pa; 
} 

term* CPolyn(term *Pa, term *Pb) { // 算法2.23 
// 多項式乘法：Pa = Pa*Pb，利用兩個多項式的結點構成"積多項式"。 
if(!Pb) return NULL; 
term *pa = Pa, *p, *q, *r, *s, *t; 
r = p = (term*)malloc(sizeof(term)); 
while(pa) { 
p->coef = pa->coef; 
p->expn = pa->expn; 
q = p; 
p = p->next = (term*)malloc(sizeof(term)); 
pa = pa->next; 
} 
q->next = NULL; 
free(p); 
pa = Pa; 
t = s = (term*)malloc(sizeof(term)); 
while(pa) { 
q = s; 
s = s->next = (term*)malloc(sizeof(term)); 
pa = pa->next; 
} 
q->next = NULL; 
free(s); 
pa = Pa; 
while(pa) { 
pa->coef *= Pb->coef; 
pa->expn += Pb->expn; 
pa = pa->next; 
} 
Pb = Pb->next; 
while(Pb) { 
p = r; 
s = t; 
while(p) { 
s->coef = p->coef * Pb->coef; 
s->expn = p->expn + Pb->expn; 
p = p->next; 
s = s->next; 
} 
Pa = APolyn(Pa,t); 
Pb = Pb->next; 
} 
return Pa; 
} // CPolyn 

term* C(term *Pa, term *Pb) { 
int n; 
puts("再輸入一一元多項式的項數"); 
scanf("%d",&n); 
Pb = CreatPolyn(Pb,n); 
Pb = selsort(Pb); 
putchar('(');PrintfPoly(Pa);putchar(')'); 
printf(" * "); 
putchar('(');PrintfPoly(Pb);putchar(')'); 
printf(" = "); 
Pa = CPolyn(Pa,Pb); 
Pa = selsort(Pa); 
PrintfPoly(Pa); 
return Pa; 
} 

void main() { 
term *M,*N; 
char s[2]; 
int i,n; 
puts("一元多項式計算:\n輸入一一元多項式的項數"); 
scanf("%d",&n); 
M = CreatPolyn(M,n); 
M = selsort(M); 
PrintfPoly(M); 
p: puts("\n1:加\n2:減\n3:乘\n4:退出"); 
getchar(); 
q: gets(s); 
if(s[1]!='\0' || !isdigit(*s)) { 
puts("輸入有誤,請重新輸入!");goto q; 
} 
i = *s-48; 
switch(i) { 
case 1:M = A(M,N);goto p;; 
case 2:M = B(M,N);goto p;; 
case 3:M = C(M,N);goto p; 
case 4:break; 
default:puts("輸入有誤,請重新輸入!");goto q; 
} 
}