/*--------------------------------------*
问题：设计一个一元多项式简单的计算器
要求：一元多项式计算器的基本功能定为
(1) 建立多项式
(2) 输出多项式
(3) 两个多项式相加，建立并输出和多项式
(4) 两个多项式相减，建立并输出差多项式
实现提示：可选择带头结点的单向循环链表
或单链表存储多项式，头结点可存放多项式
的参数，如项数等。
*---------------------------------------*/
#include<stdio.h>
#include<stdlib.h>
typedef
struct term
{
short expn; /*幂次*/
double coef; /*系数*/
struct term* next;
}
Term;
/*为了说明问题以下仅演示两个固定多项式
f(x)=3x^3-2x^2+x-1.5
g(x)=4x^4-3x^3+x+0.5
的加法与减法
*/
int main()
{
Term* create(int,double[]);
Term* chains(Term*,Term*,char);
void output(Term*);
void Free(Term*);
double fx[]={ 3,-2,1,-1.5};
double gx[]={4,-3, 0,1, 0.5};
Term *hf,*hg,*hsum,*hdif;
/*首先为f(x),g(x)建立链表*/
hf=create(3,fx);
hg=create(4,gx);
/*调用多项式"加法"*/
hsum=chains(hf,hg,'+');
/*遍历hsum输出"和式"*/
output(hsum);
Free(hsum);
/*调用多项式"减法"*/
hdif=chains(hf,hg,'-');
/*遍历hdif输出"差式"*/
output(hdif);
Free(hdif);
return 0;
}
Term *create(int expmax,double f[])
{
int i;
Term *p,*q,*head=NULL;
for(i=0;i<=expmax;i++)
if(f[i]!=0.0)
{ p=(Term*)malloc(sizeof(Term));
p->coef=f[i];
p->expn=expmax-i;
if(head==NULL)head=p;
else q->next=p;
q=p;
}
q->next=NULL;
return head;
}
/*两链表pb,pg合并。合并原则:运算符op*/
Term *chains(Term*p1,Term*p2,char op)
{ int sgn=+1;
Term Q,*head,*p,*q=&Q;
head=q;q->next=NULL;/*虚结点*/
if(p1==NULL && p2==NULL)
return NULL;
/*
链表1与链表2合并的主要步骤
1.定义3个指针:p指向总表头,p1,p2分别指向链表1,2.令sgn=+1
2.在链表1,2都未"读完"的前提下,比较p1,p2当前结点"幂次"的高低:
如果p1->expn大于p2->expn,则3.
如果p1->expn等于p2->expn,则4.
如果p1->expn小于p2->expn,则:交换p1,p2(sgn异号)后返回2.
3.为总表申请1个新结点p,把p1结点的数据复制到p,善后处理
访问p1的下一个结点,返回2.
4.计算表达式p1->coef±p2->coef的值.
如果非零,则为总表申请1个新结点p,将该值复制到p->coef,善后处理;
否则(等于零)就什么也不做.
令p1,p2分别指向下一个结点,返回2.
5.如果p1,p2至少有1个"读完"则区分下列3种情况:
p1,p2同时"读完":此时总表实际上已经构造成功
p1"未读完":(从逻辑上分析这种情况并不会发生)
p2"未读完":将p2表余下的结点复制后链接到总表
*/
#define EXP1 p1->expn
#define EXP2 p2->expn
while(p1!=NULL && p2!=NULL)
{
if(EXP1>EXP2)
{
p=(Term*)malloc(sizeof(Term));
p->expn=EXP1;
p->coef=p1->coef*(op=='-'?sgn:1);
p->next=NULL;
q=q->next=p;
p1=p1->next;
}
else if(EXP1==EXP2)
{
double temp;
if(op=='+')temp= p1->coef+p2->coef;
else if(op=='-')temp=(p1->coef-p2->coef)*sgn;
else {printf("Invalid op...\n");exit(1);}
if(temp)
{
p=(Term*)malloc(sizeof(Term));
p->expn=EXP2;
p->coef=temp;
p->next=NULL;
q=q->next=p;
}
p1=p1->next;
p2=p2->next;
}
else /*EXP1<EXP2*/
{
Term*pt=p1;p1=p2;p2=pt;sgn=-sgn;
}
}
while(p2!=NULL)
{
p=(Term*)malloc(sizeof(Term));
p->expn=EXP2;
p->coef=p2->coef;
p->next=NULL;
q=q->next=p;
}
return head->next;
}
void output(Term* head)
{ Term *p =head;
while(p!=NULL)
{
if(p->coef==+1 && p->expn)printf("+");
else if(p->coef==-1 && p->expn)printf("-");
else if(p==head)printf( "%.2lf",p->coef);
else printf("%+.2lf",p->coef);
if(p->expn==1)printf("x");
if(p->expn>=2)printf("x^%d",p->expn);
p=p->next;
}
printf("\n");
}
void Free(Term*q)
{ while(q!=NULL)
{
Term*p=q->next;
free(q);
q=p;
}
}
