一元多项式运算

题目

一元多项式运算
一．问题描述
设计一个简单的一元稀疏多项式加法运算器.
二．基本要求
一元稀疏多项式简单计算器的基本功能包括：
1．按照指数升序次序,输入并建立多项式A与B.
2．计算多项式A与B的和,即建立多项式A+B.
3．按照指数升序次序,输出多项式A、B、A+B.
三．提示与分析
1．一元n次多项式：P(x,n)=P0+P1X1+P2X2+…+PnXn,其每一个子项都是由“系数”和“指数”两部分来组成的,因此可以将它抽象成一个由“系数、指数对”构成的线性表,其中,多项式的每一项都对应于线性表中的一个数据元素.由于对多项式中系数为0的子项可以不记录它的指数值,对于这样的情况就不再付出存储空间来存放它了；基于此,可以采用一个带有头结点的单链表来表示一个一元多项式.
例如,多项式A= 3+6X3-2X8+12X20 、B= 2X-2-6X3+8X10可分别表示为：
2．数据类型定义可描述如下：
typedef struct pnode
{int coef; /*系数域*/
int exp; /*指数域*/
struct pnode *next; /*指针域,指向下一个系数不为0的子项*/
}PolyNode,*PolyLink;
PolyLink A,B,C; /*单链表存储的多项式A、B、C*/
3．基本功能分析
（1）输入多项式,建立多项式链表
首先创建带头结点的单链表；然后按照指数递增的顺序和一定的输入格式输入各个系数不为0的子项：“系数、指数对”,每输入一个子项就建立一个结点,并将其插入到多项式链表的表尾,如此重复,直至遇到输入结束标志的时候停止,最后生成按指数递增有序的链表.
（2）多项式相加
多项式加法规则：对于两个多项式中指数相同的子项,其系数相加,若系数的和非零,则构成“和多项式”中的一项；对于指数不同的项,直接构成“和多项式”中的一项.
将（1）中单链表表示的两个多项式A和B相加,运算的结果是利用原表空间生成一个新链表,表示和多项式C.运算规则如下：
设指针pa、pb分别指向多项式链表A、B的第一个结点,比较pa、pb所指两结点中的指数项：
① 若pa->exp < pb->exp,则将pa所指结点插入到“和多项式”链表中去；
② 若pa->exp > pb->exp,则将pb所指结点插入到“和多项式”链表中去；
③ 若pa->exp== pb->exp,则计算系数和pa->coef＋pb->coef,若和非零,插入到“和多项式”链表中去,删除pb所指结点；否则删除pa、pb所指结点.
继续比较下一项,重复上述过程,直至A、B中某一链表结束,此时将非空链表中剩余的结点出入到“和多项式”链表即可.
（3）多项式的输出
可以在文本界面下,采用类似于数学表达式的方式输出多项式,如多项式A可显示为：
A=3+6XÙ3-2XÙ8+12XÙ20
需要注意：
系数值为1的非零次项的输出形式中略去系数1,如子项1x8的输出形式为x8,项－1x3的输出形式为－x3.
多项式的第一项的系数符号为正时,不输出“+”,其它项要输出“+”、“-”符号.

答案

#include
#include
#define A1(a,b,c,d,e) gotoxy(a,b);printf("c%d=",d);scanf("%f",e);
#define A2(a,b,c,d,e) gotoxy(a,b);printf("e%d=",d);scanf("%f",e);
#define B1 do { printf("\n想继续吗（求函数值／求导数）(y/N)?")
#define B2 ch2=bioskey(0); printf("[%c]",ch2)
#define B3 if((ch2=='Y')||(ch2=='y')) tc(head1->next,head2->next,r); }
#define B4 while((ch2=='y')||(ch2=='Y'))
struct ma
{ float c;
float e;
struct ma *next; }
main()
{ struct ma *head1,*head2,*p,*q,*r,*rm;
float s1[100][3],s2[100][3],mid1,mid2,mid3;
int i,j,t,num1,num2;
char ch,ch1,ch2,ch11,ch21;
struct ma *add();
struct ma *mul();
void tc();
void output();
loop1: t=0; ch='y';
clrscr();
printf("请输入第一个多项式的项数:");
scanf("%d",&num1);
q=head1=(struct ma*)malloc(sizeof(struct ma));
(*q).next=NULL;
if(num1>0)
{ printf("请输入第一个多项式的系数(c) 和指数(e):");
for(i=1;ic); (*r).e=q->e; q=(*q).next;}
else if(p->ee) { (*r).c=p->c ; (*r).e=p->e; p=(*p).next; }
else { if(ch1=='+') (*r).c=(p->c)+(q->c);
else (*r).c=(p->c)-(q->c);
(*r).e=(p->e); p=(*p).next;q=(*q).next;}
}while((p!=NULL)&&(q!=NULL));
while(q!=NULL)
{ r=(struct ma*)malloc(sizeof(struct ma));
(*s).next=r; s=r;
if(ch1=='+') (*r).c=q->c ;
else (*r).c=-(q->c);(*r).e=q->e; q=(*q).next;}
while(p!=NULL)
{ r=(struct ma*)malloc(sizeof(struct ma));
(*s).next=r; s=r;
(*r).c=p->c ; (*r).e=p->e;p=(*p).next; }
(*r).next=NULL;
s=r=(*head3).next;
while(r->next!=NULL)
if(r->e==(r->next)->e)
{ r->c+=(r->next)->c; s=r->next;
r->next=(r->next)->next; free(s); s=r; }
else { r=r->next; s=s->next; }
s=r=(*head3).next;
return(r);
}
struct ma *mul(struct ma *head1,struct ma *head2)
{ struct ma *head3,*head4,*p,*q,*r,*s,*r1,*s1;
struct ma *w[100];
int t=0;
head3=r=s=(struct ma*)malloc(sizeof(struct ma));
head4=r1=s1=(struct ma*)malloc(sizeof(struct ma));
p=head1->next; q=head2->next;
while(p!=NULL)
{ s=(struct ma*)malloc(sizeof(struct ma));
s->c=(p->c)*(q->c);
s->e=(p->e)+(q->e);
r->next=s;
r=s;
p=p->next;}
s->next=NULL; s=r=head3->next; w[0]=head3;
p=head1->next; q=q->next;
while(q!=NULL)
{ while(p!=NULL)
{ s1=(struct ma*)malloc(sizeof(struct ma));
s1->c=(p->c)*(q->c);s1->e=(p->e)+(q->e);
r1->next=s1;
r1=s1;
p=p->next;
}
s1->next=NULL;r1=s1=head4->next;
t++;
w[t]=(struct ma*)malloc(sizeof(struct ma));
w[t]->next=add(w[t-1],head4,'+');
while(head3->next!=NULL) {r=r->next;free(s);head3->next=s=r;}
s=r=head3;
while(head4->next!=NULL) {r1=r1->next;free(s1);head4->next=s1=r1;}
s1=r1=head4;
p=head1->next; q=q->next;
}
return(w[t]->next);}
void tc(struct ma *p,struct ma *q, struct ma *r)
{ char ch1,ch2;
float x;
float qzhi(struct ma *head,float x);
void qdao();
printf("\n请选择多项式的序号:");
printf("\n 1--第一个;2--第二个;3--第三个");
ch1=bioskey(0);printf("[%c]",ch1);
printf("\n请输入功能代码:");
printf("\n z--求函数值,d--求导函数");
ch2=bioskey(0);printf("[%c]",ch2);
switch(ch1)
{ case '1': { if(ch2=='z')
{ printf("\n请输入自变量 x:");
scanf("%f",&x);
printf("多项式的值为:%10.4f",qzhi(p,x));}
if(ch2=='d') qdao(p); break;}
case '2': { if(ch2=='z')
{ printf("\n请输入自变量 x:");
scanf("%f",&x);
printf("多项式的值为:%10.4f",qzhi(q,x));}
if(ch2=='d') qdao(q); break;}
case '3': { if(ch2=='z')
{ printf("\n请输入自变量 x:");
scanf("%f",&x);
printf("多项式的值为:%10.4f",qzhi(r,x));}
if(ch2=='d') qdao(r); break;} } }
float qzhi(struct ma *head,float x)
{ float value=0;
while(head!=NULL)
{ value+=(head->c)*pow(x,head->e);head=head->next;}
return(value);
}
void qdao(struct ma *head)
{ struct ma *p,*q,*r,*t;
p=head;
t=r=q=(struct ma *)malloc(sizeof(struct ma));
while(p!=NULL)
{ q=(struct ma *)malloc(sizeof(struct ma));
r->next=q;r=q;
q->c=(p->c)*((p->e));q->e=(p->e)-1;
p=p->next;}
q->next=NULL;
printf("\n多项式的导数为:");
output(t->next);
p=t;
while(t!=NULL) { p=t->next;free(t);t=p;}
}
void output(struct ma *r)
{ int l=0;
struct ma *t,*s,*head;
t=r;
while(r->next!=NULL)
if(r->e==(r->next)->e)
{ r->c+=(r->next)->c; s=r->next;
r->next=(r->next)->next; free(s); s=r; }
else { r=r->next; s=s->next; }
s=r=t;
head=(struct ma*)malloc(sizeof(struct ma));
head->next=r;
s=head;
while(r!=NULL)
{ if((r->c)==0) {s->next=r->next; free(r);r=s->next;}
else { s=s->next;r=r->next;}}
s=r=head->next;
while(r!=NULL)
{ if(r->c==1) { l++;
if(r->e==1) printf("x");
else if(r->ee);
else if(r->e==0) printf("1");
else printf("x^%.0f",r->e);}
else if(r->c==-1) { l++;
if(r->e==1) printf("-x");
else if(r->ee);
else if(r->e==0) printf("-1");
else printf("-x^%.0f",r->e);}
else { l++;
if(r->e==1) printf("%4.1fx",r->c);
else if(r->ec,r->e);
else if(r->e==0) printf("%4.1f",r->c);
else printf("%4.1fx^%.0f",r->c,r->e); }
if(((*r).next!=NULL)&&((r->next)->c>0)) printf(" +");
r=r->next; }
if(l==0) printf("0");
}