|
3鱼币
本帖最后由 番茄 于 2012-6-8 14:21 编辑
顺序结构,,动态链表结构下的一元多项式的加、减、乘法的实现
设有一元多项式Am(x)和Bn(x).
Am(x)=A0+A1x1+A2x2+A3x3+…+Amxm
Bn(x)=B0+B1x1+B2x2+B3x3+…+Bnxn
请实现求M(x)=Am(x)+Bn(x)、M(x)=Am(x)-Bn(x)和M(x)=Am(x)×Bn(x)。
要求:
1)首先判定多项式是否稀疏
2)分别采用顺序和动态存储结构实现;
3)结果M(x)中无重复阶项和无零系数项;
4)要求输出结果的升幂和降幂两种排列情况
代码:
#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;
}
}
|
|