//元素类型、结点类型和指针类型
//#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
#include <MATH.H>
typedef int status;
typedef struct NodeType //结点类型，指针类型
{
float coef; //系数
int expn; //指数
NodeType *next;
}*LinkType;
typedef LinkType Polynomial; //用带头结点的有序链表表示多项式
//函数声明
void InitPolyn( Polynomial &P); //构造一个多项式
status MakeNode( Polynomial &p,float Ncoef,int Nexpn); //创建一个结点
void CreatPolyn( Polynomial &P,int m); //输入m项的系数和指数，建立表示一元多项式的有序链表P
void ClearPolyn( Polynomial &P); //将单链表清空，并释放原链表的结点空间
void DestroyPolyn( Polynomial &P); //销毁一元多项式P
void PrintPolyn( Polynomial P); //打印输出一元多项式P
int PolynLength( Polynomial P); //返回一元多项式P中的项数
void MergePolynCoef(Polynomial &Pn); //在序链表中,合并同类项
void SortPolyn(Polynomial &Pn); //根据链表的expn指数域，对链表进行降序排序
void DelZeroNode(Polynomial &Pn); //释放无用结点,即系数为0项
void AddPolyn( Polynomial Pa,Polynomial Pb,Polynomial &Pc); //完成多项式相加运算，即：Pc=Pa+Pb
void SubtractPolyn( Polynomial Pa,Polynomial Pb,Polynomial &Pc); //完成多项式相减运算，即：Pc=Pa-Pb
void MultiplyPolyn( Polynomial Pa,Polynomial Pb,Polynomial &Pc); //完成多项式相乘运算，即：Pc=Pa×Pb
void Difference(Polynomial Pa, Polynomial &Pb); //求多项式的导函数
float Evaluate(Polynomial pn, float x ); //求多项式的值
//算法如下
//构造一个多项式
void InitPolyn( Polynomial &P)
{
P=(NodeType *)malloc(sizeof(NodeType));
P->coef=0;
P->expn=0;
P->next=NULL; //初始化带头结点的单链表
}
//将单链表清空，并释放原链表的结点空间
void ClearPolyn( Polynomial &P)
{
LinkType p1, p2;
p1 = P;
p2 = p1->next;
while(p2!=NULL) //释放原链表的结点空间
{
p1->next=p2->next;
free(p2);
p2=p1->next;
}
}
//销毁一元多项式P
void DestroyPolyn(Polynomial &P)
{
LinkType q=P;
while(q!=NULL)
{
q=P->next;
free(P); //释放所有结点空间
q=P;
}
} // DestroyPolyn
//根据链表的expn指数域，对链表进行降序排序
void SortPolyn(Polynomial &Pn)
{
MergePolynCoef(Pn); //先合并同类项
LinkType p,q,r;
q=Pn->next;
Pn->next=NULL;
while(q!=NULL) //插入法排序
{
p=Pn;
while(p->next!=NULL&&p->next->expn > q->expn)
p=p->next;
r=q->next;
q->next=p->next;
p->next=q;
q=r;
}
}// SortPolyn
//在序链表中,合并同类项
void MergePolynCoef(Polynomial &Pn)
{
LinkType p,p1,p2;
p=Pn->next;
while(p!=NULL)
{
p1=p;p2=p->next;
while(p2!=NULL) //合并指数相同项
{
if(p->expn==p2->expn)
{
p->coef+=p2->coef;
p1->next=p2->next;
free(p2);
p2=p1->next;
}
else
{
p1=p2;
p2=p1->next;
}
}
p=p->next;
}
DelZeroNode(Pn); //删除合并后系数为0的结点
}
//创建一个结点
status MakeNode( Polynomial &p,float Ncoef,int Nexpn)
{
if (!(p=(LinkType)malloc(sizeof(NodeType))))
{
printf("Error,the momery is overflow");
return false;
}
p->coef=Ncoef;
p->expn=Nexpn;
p->next=NULL;
return true;
}
//输入m项的系数和指数，建立表示一元多项式的有序链表P
void CreatPolyn(Polynomial &P,int m)
{
float fcoef;
int fexpn;
NodeType *s,*q;
q=P;
printf("项数:%d\n", m);
for(int i=1;i<=m;i++) //if(m==0) 为"空表!";
{
printf("第%d项式:", i);
printf("系数，指数:");
scanf("%f %d",&fcoef, &fexpn);
s=(NodeType *)malloc(sizeof(NodeType));
s->coef=fcoef;
s->expn=fexpn;
s->next=NULL;
q->next=s;
q=s;
}
MergePolynCoef(P); //合并指数相同项
// DelZeroNode(P); //删除系数为0的结点
SortPolyn(P); //按指数域，对链表进行升序排序
}
// 稀疏多项式pa以链表作存储结构,将此链表修改成它的导函数,并释放无用结点
void Difference(Polynomial Pa, Polynomial &Pb)
{
LinkType p,q;
NodeType *s;
p=Pa->next;
q=Pb;
while(p!=NULL)
{
if(p->expn==0)
{
p=p->next;
} //常数项，导数为零，释放结点
else
{
s = (NodeType *)malloc(sizeof(NodeType));
s->coef = p->coef * p->expn;
s->expn = p->expn - 1;
s->next = NULL;
p = p->next;
q->next = s;
q = q->next;
}
}
}
//释放无用结点,即系数为0项
void DelZeroNode(Polynomial &Pn)
{
LinkType p,q;
q=Pn;
p = q->next;
while(p!=NULL)
{
if(p->coef==0)
{
q->next=p->next;
free(p);
p=q->next;
}
q = p;
p = q->next;
}
}
//求多项式的值
float Evaluate(Polynomial pn, float x)
{
LinkType p;
p=pn->next;
float result=0;
while(p!=NULL)
{
result+=(p->coef)*(float)pow(x,p->expn); //pow函数求x的n次方
p=p->next;
}
return result;
}
//完成多项式相加运算，即：Pc=Pa+Pb
void AddPolyn(Polynomial Pa,Polynomial Pb,Polynomial &Pc)
{
float x;
//LinkType p,q,r;
NodeType *p,*q,*r;
NodeType *s;
p=Pa->next;
q=Pb->next;
r=Pc;
while(p!=NULL&&q!=NULL)
{
if(p->expn==q->expn) //指数相同
{
x=p->coef+q->coef ;
if(x!=0) //指数相同，若系数相加不等于0,插入表中
{
s=(NodeType *)malloc(sizeof(NodeType));
s->coef=x;
s->expn=q->expn;
s->next=NULL;
r->next=s;
r=r->next;
}
p=p->next;
q=q->next;
}
else if(q->expn > p->expn) //指数大的插入表中
{
s=(NodeType *)malloc(sizeof(NodeType));
s->coef=q->coef;
s->expn=q->expn;
s->next=NULL;
r->next=s;r=r->next;
q=q->next;
}
else
{
s=(NodeType *)malloc(sizeof(NodeType));
s->coef=p->coef;
s->expn=p->expn;
s->next=NULL;
r->next=s;
r=r->next;
p=p->next;
}
}
//加入余下的多项式
while(p!=NULL)
{
s=(NodeType *)malloc(sizeof(NodeType));
s->coef=p->coef;
s->expn=p->expn;
s->next=NULL;
r->next=s;
r=r->next;
p=p->next;
}
while(q!=NULL)
{
s=(NodeType *)malloc(sizeof(NodeType));
s->coef=q->coef;
s->expn=q->expn;
s->next=NULL;
r->next=s;
r=r->next;
q=q->next;
}
}// AddPoly
//完成多项式相减运算，即：Pc=Pa-Pb
void SubtractPolyn( Polynomial Pa,Polynomial Pb,Polynomial &Pc)
{
float x;
LinkType p,q,r;
NodeType *s;
p=Pa->next;
q=Pb->next;
r=Pc;
while(p!=NULL&&q!=NULL)
{
if(p->expn==q->expn) //指数相同
{
x=p->coef-q->coef;
if(x!=0) //指数相同，若系数相减不等于0,插入表中
{
s=(NodeType *)malloc(sizeof(NodeType));
s->coef=x;
s->expn=q->expn;
s->next=NULL;
r->next=s;
r=r->next;
}
p=p->next;
q=q->next;
}
else if(q->expn > p->expn) //指数大的插入表中
{
s=(NodeType *)malloc(sizeof(NodeType));
s->coef=-q->coef; //减数的系数变为相反数
s->expn=q->expn;
s->next=NULL;
r->next=s;
r=r->next;
q=q->next;
}
else
{
s=(NodeType *)malloc(sizeof(NodeType));
s->coef=p->coef;
s->expn=p->expn;
s->next=NULL;
r->next=s;
r=r->next;
p=p->next;
}
}
//加入余下的多项式，减数的系数变为相反数
while(p!=NULL)
{
s=(NodeType *)malloc(sizeof(NodeType));
s->coef=p->coef;
s->expn=p->expn;
s->next=NULL;
r->next=s;
r=r->next;
p=p->next;
}
while(q!=NULL)
{
s=(NodeType *)malloc(sizeof(NodeType));
s->coef=-q->coef;
s->expn=q->expn;
s->next=NULL;
r->next=s;
r=r->next;
q=q->next;
}
}// SubtractPolyn
//完成多项式相乘运算，即：Pc=Pa×Pb
void MultiplyPolyn( Polynomial Pa,Polynomial Pb,Polynomial &Pc)
{
LinkType p,q,r;
NodeType *s;
p=Pa->next;
r=Pc;
while(p!=NULL)
{
q=Pb->next;
while(q!=NULL)
{
s=(NodeType *)malloc(sizeof(NodeType));
s->coef=p->coef*q->coef;
s->expn=p->expn+q->expn;
s->next=NULL;
r->next=s;
r=r->next;
q=q->next;
}
p=p->next;
}
MergePolynCoef(Pc); //合并指数相同项
DelZeroNode(Pc); //删除系数为0的结点
SortPolyn(Pc); //按指数域，对链表进行降序排序
}// MultiplyPolyn
void PrintPolyn(Polynomial P) {
Polynomial pCur;
pCur = P->next;
while (pCur) {
printf("%.0fX^%d ", pCur->coef, pCur->expn);
pCur = pCur->next;
}
printf("\n");
}
//主函数
int main()
{
Polynomial Pa,Pb,Pc;
float x = 2;
InitPolyn(Pa);
CreatPolyn(Pa, 3);
PrintPolyn(Pa);
InitPolyn(Pb);
CreatPolyn(Pb, 2);
PrintPolyn(Pb);
InitPolyn(Pc);
printf(" ****************欢迎使用一元多项式计算器******************\n");
printf(" **********************************************************\n");
while(1)
{
int choice;
printf(" **********************************************************\n");
printf(" ******************* 1.多项式加法 *****************\n");
printf(" ******************* 2.多项式减法 *****************\n");
printf(" ******************* 3.多项式乘法 *****************\n");
printf(" ******************* 4.求多项式A的导数 *****************\n");
printf(" ******************* 5.求多项式A的值 *****************\n");
printf(" ******************* 6.谢谢使用!再见! *****************\n");
printf(" **********************************************************\n");
printf("测试数据: A1=x+x^2+x^3 B1=1+x+x^2 \n");
printf(" A2=9+x+x^4+2x^6 B2=6x^(-3)-x+4.4x^2-1.2x^9 \n");
printf(" A3=-6x^(-3)+5.4x^2-x^2+7.8x^10 B3=7-5x^8+11x^9 \n\n");
printf("请输入操作(1-6):\n");
scanf("%d",&choice);
printf("\n");
getchar();
switch(choice)
{
case 1:
{
printf("多项式加法C=A+B\n");
AddPolyn(Pa,Pb,Pc);
PrintPolyn(Pc);
ClearPolyn(Pc);
}
break;
case 2:
{
printf("多项式减法C=A-B:\n");
SubtractPolyn(Pa,Pb,Pc);
PrintPolyn(Pc);
ClearPolyn(Pc);
}
break;
case 3:
{
printf("多项式乘法C=A*B:\n");
MultiplyPolyn(Pa,Pb,Pc);
PrintPolyn(Pc);
ClearPolyn(Pc);
}
break;
case 4:
{
printf("求多项式A的导数:\n");
Difference(Pa, Pc);
PrintPolyn(Pc);
ClearPolyn(Pc);
}
break;
case 5:
{
printf("求多项式A的值:\n");
x = 2;
float value = Evaluate(Pa, x);
printf("%f\n", value);
}
break;
case 6:
{
printf("谢谢使用!再见!\n");
exit(0);
}
break;
default:
{
printf("错误命令!\n");
}
break;
}
};
return 0;
}
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2013-6-26 17:05:33
置顶卡
千斤顶
显身卡
楼主
