姓名:冯亚玲
班级:2007050702
学号:200705070231
题目:多项式的运算——基本要求
一、 需求
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
:
1)算法要求:进行一元多项式的加、减、求导、乘法运算,多项式在某点处的函数值。
2.)输入要求:输入以系数、指数对的形式输入,表示多项式的某项的次数和系数
多项式每一项输入可以不按顺序,可以次数重复,需做合并同类项等处理
3)输出要求:计算结果是多项式的需按多项式形式输出,示例如:
输入示例:
0 2
5 -3
12 5
2 6
输出:(所表示的多项式为):f(x)=2+6 x^2 -3 x^5 + 5 x^12
二、 概要设计:
1.1) 本程序采用带头结点的线性链表类型。其中包含了几个基本的操作,比如:Status MakeNode(Link &p,ElemType e),分配由p指向的值为e的结点。
Status InitList(LinkList &L)构造一个空的线性链表,
Status DestroyList(LinkList &L)销毁线性链表L,
Status ORderInsert(LinkList &L,ElemType e ,int(*comp)(ElemType,ElemType))已知L为有序线性链表,将元素e按非降序插入在L中等。
Status InsFirst(LinkList &L,Link h,Link s)h指向L的一个结点,把h当做头结点,将s所指向结点插入在第一个结点之前
Status DelFirst(LinkList &L,Link h,Link &q)h指向L的一个结点,把h当做头结点,删除链表的第一个结点并q以返回
2)对于一元多项式项的表示作为LINKLIST的数据元素,包括系数和指数。其中的算法有:
void AddPolyn(polynomial &Pa,polynomial &Pb)多项式加法的算,
void SubtractPolyn(polynomial &Pa,polynomial &Pb)多项式减法,
void MultiplyPolyn(polynomial &Pa,polynomial &Pb)多项式乘法,
void DerivPolyn(polynomial &Pa)多项式的求导等。
2. 函数的调用关系
主函数先依次调用了CreatPolyn,建立两个一元多项式的有序链表,CreatPolyn中又调用了Initlist,初始化链表。然后再调用了AddPolyn,计算两个多项式相加,并调用了PrintPolyn,输出运算结果,在AddPolyn中,分别调用了GetHead,GetCurElem, OrderInsertMerge, DestroyPolyn,完成了对两个一元多项式的加法运算。然后主函数中又依次调用了SubtractPolyn,MultiplyPolyn,
DerivPolyn,分别对多项式进行减法,乘法和求导运算。在运算算法中,分别调用了线性链表的基本操作运算。
如下所示:
三.详细设计:
1. 1)结点类型:typedef struct LNode
{ ElemType data;
LNode *next;
}*Link,*Position;
链表类型:struct LinkList
{
Link head,tail;
int len;//数据元素的个数
};
多项式项的表示:typedef struct
{
float coef;//系数
int expn; //指数
}term,ElemType;
2)运算的基本操作:
void AddPolyn(polynomial &Pa,polynomial &Pb)//多项式加法的算法
{
取头结点并使qb指向其结点:qb=GetHead(Pb);
指向第一个结点:qb=qb->next;
循环分别对指数相同的进行系数相加合并:
while(qb)
{
b=GetCurElem(qb);
OrderInsertMerge(Pa,b,cmp);
qb=qb->next;
}
销毁Pb:
DestroyPolyn(Pb);
}
void SubtractPolyn(polynomial &Pa,polynomial &Pb)//多项式减法
{ 先对一元多项式的系数取反:Opposite(Pb);
然后调用加法运算:AddPolyn(Pa,Pb);
}
void MultiplyPolyn(polynomial &Pa,polynomial &Pb)//多项式乘法
{
while(qa)
{
主要思想:依次对多项式的每一项相乘,指数相加,系数相乘,并合并同类项。用while循环,如下:
while(qb)
{
b=GetCurElem(qb);
c.coef=a.coef*b.coef;
c.expn=a.expn+b.expn;
OrderInsertMerge(Pc,c,cmp);
qb=qb->next;
}
qa=qa->next;
}
void DerivPolyn(polynomial &Pa)
{//对一元多项式求导
对多项式求导,从头结点开始,对每一项做如下操作,系数等于原系数×指数,相应的指数减一,如下所示:
while(qa)
{
a=GetCurElem(qa);
b.coef=a.coef*a.expn;
b.expn=a.expn-1;
OrderInsertMerge(Pb,b,cmp);
qa=qa->next;
}
2.源程序:
#include
#include
#include
#include
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define DestroyPolyn DestroyList
#define PolynLength
typedef int Status;
typedef int Boolean;
typedef struct//多项式项的表示
{
float coef;//系数
int expn; //指数
}term,ElemType;
//带头结点的线性链表类型
typedef struct LNode//结点类型
{
ElemType data;
LNode *next;
}*Link,*Position;
struct LinkList //链表类型
{
Link head,tail;
int len;//数据元素的个数
};
typedef LinkList polynomial;
Status MakeNode(Link &p,ElemType e)//分配p由指向的值为e的结点
{
p=(Link)malloc(sizeof(LNode));
if(!p)
return ERROR;
p->data=e;
return OK;
}
void FreeNode(Link &p)//释放p所指向结点
{
free(p);
p=NULL;
}
Status InitList(LinkList &L)//构造一个空的线性链表
{
Link p;
p=(Link)malloc(sizeof(LNode));
if(p)
{
p->next=NULL;
L.head=L.tail=p;
L.len=0;
return OK;
}
else
return ERROR;
}
Status ClearList(LinkList &L)//将线性表L重置为空表
{
Link p,q;
if(L.head!=L.tail)
{
p=q=L.head->next;
L.head->next=NULL;
while(p!=L.tail)
{
p=q->next;
free(q);
q=p;
}
free(q);
L.tail=L.head;
L.len=0;
}
return OK;
}
Status DestroyList(LinkList &L)//销毁线性链表L
{
ClearList(L);
FreeNode(L.head);
L.tail=NULL;
L.len=0;
return OK;
}
Status InsFirst(LinkList &L,Link h,Link s)//h指向L的一个结点,把h当做头结点,将s所指向结点插入在第一个结点之前
{
s->next=h->next;
h->next=s;
if(h==L.tail)
L.tail=h->next;
L.len++;
return OK;
}
Status DelFirst(LinkList &L,Link h,Link &q)//h指向L的一个结点,把h当做头结点,删除链表的第一个结点并q以返回
{
q=h->next;
if(q)
{
h->next=q->next;
if(!h->next)
L.tail=h;
L.len--;
return OK;
}
else
return FALSE;
}
Position PriorPos(LinkList &L,Link p)//返回p所指结点的直接前驱
{
Link q;
q=L.head->next;
if(q==p)
return NULL;
else
{
while(q->next!=p)
q=q->next;
return q;
}
}
ElemType GetCurElem(Link p)//返回p所指向结点中数据元素的值
{
return p->data;
}
Status ListEmpty(LinkList L)
{
if(L.len)
return FALSE;
else
return TRUE;
}
int ListLength(LinkList L)
{
return L.len;
}
Position GetHead(LinkList L)
{
return L.head;
}
Position GetLast(LinkList L)
{
return L.tail;
}
Position NextPos(Link p)//返回p所指结点的直接后继的位置
{
return p->next;
}
Status LocatePos(LinkList L,int i,Link &p)//已知p指示线性链表L中第i个结点的位置
{
int j;
if(i<0||i>L.len)
return ERROR;
else
{
p=L.head;
for(j=1;j<=i;j++)
p=p->next;
return OK;
}
}
Position LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType))//返回线性链表中第一个与e满足函数判定关系的元素的位置
{
Link p=L.head;
do
p=p->next;
while(p&&!(compare(p->data,e)));
return p;
}
Status ListTraverse(LinkList L,void(*visit)(ElemType))//依次对L中的每个数据元素调用函数visit()
{
Link p=L.head->next;
int j;
for(j=1;j<=L.len;j++)
{
visit(p->data);
p=p->next;
}
printf("\n");
return OK;
}
Status ORderInsert(LinkList &L,ElemType e ,int(*comp)(ElemType,ElemType))//已知L为有序线性链表,将元素e按非降序插入在L中
{
Link o,p,q;
q=L.head;
p=q->next;
while(p!=NULL&&comp(p->data,e)<0)
{
q=p;
p=p->next;
}
o=(Link)malloc(sizeof(LNode));
o->data=e;
q->next=o;
o->next=p;
L.len++;
if(!p)
L.tail=o;
return OK;
}
Status LocateElem(LinkList L,ElemType e,Position &q,int(*compare)(ElemType,ElemType))
{//若升序链表L中存在与e满足判定函数compare()取值为0的元素,则q指示L中
//第一个值为e的结点的位置,并返回TRUE;否则q指示第一个与e满足判定函数
//compare取值>0的语速的前驱的位置。
Link p=L.head,pp;
do
{
pp=p;
p=p->next;
}while(p&&(compare(p->data,e)<0));
if(!p||compare(p->data,e)>0)
{
q=pp;
return FALSE;
}
else
{
q=p;
return TRUE;
}
}
Status OrderInsertMerge(LinkList &L,ElemType e,int(*compare)(term,term))
{//按有序判断函数compare()的约定,将值为e的结点插入或合并到升序链表L的适当位置
Position q,s;
if(LocateElem(L,e,q,compare))
{
q->data.coef+=e.coef;//改变当前结点系数的值
if(!q->data.coef)//系数为零
{
s=PriorPos(L,q);
if(!s)
s=L.head;
DelFirst(L,s,q);
FreeNode(q);
}
return OK;
}
else
if(MakeNode(s,e))
{
InsFirst(L,q,s);
return OK;
}
else
return ERROR;
}
int cmp(term a,term b)
{//依a的指数值<,>,=的指数值,分别返回-1,0或1
if(a.expn==b.expn)
return 0;
else
return(a.expn-b.expn)/abs(a.expn-b.expn);
}
void CreatPolyn(polynomial &P,int m)
{//输入m项的系数和指数,建立表示一元多项式的有序链表P
Position q,s;
term e;
int i;
InitList(P);
printf("请依次输入%d个系数,指数:\n",m);
for(i=1;i<=m;i++)
{//依次输入m个非零项
scanf("%f %d",&e.coef,&e.expn);
if(!LocateElem(P,e,q,cmp))
if(MakeNode(s,e))
InsFirst(P,q,s);
}
}
void PrintPolyn(polynomial P)//打印输出一元多项式
{
Link q;
q=P.head->next;
printf(" 系数 指数\n");
while(q)
{
printf("%f %d\n",q->data.coef,q->data.expn);
q=q->next;
}
}
void AddPolyn(polynomial &Pa,polynomial &Pb)//多项式加法的算法
{
Position qb;
term b;
qb=GetHead(Pb);//
qb=qb->next;
while(qb)
{
b=GetCurElem(qb);
OrderInsertMerge(Pa,b,cmp);
qb=qb->next;
}
DestroyPolyn(Pb);
}
void Opposite(polynomial Pa)//一元多项式系数取反
{
Position p;
p=Pa.head;
while(p->next)
{
p=p->next;
p->data.coef*=-1;
}
}
void SubtractPolyn(polynomial &Pa,polynomial &Pb)//多项式减法
{
Opposite(Pb);
AddPolyn(Pa,Pb);
}
void MultiplyPolyn(polynomial &Pa,polynomial &Pb)//多项式乘法
{
polynomial Pc;
Position qa,qb;
term a,b,c;
InitList(Pc);
qa=GetHead(Pa);
qa=qa->next;
while(qa)
{
a=GetCurElem(qa);
qb=GetHead(Pb);
qb=qb->next;
while(qb)
{
b=GetCurElem(qb);
c.coef=a.coef*b.coef;
c.expn=a.expn+b.expn;
OrderInsertMerge(Pc,c,cmp);
qb=qb->next;
}
qa=qa->next;
}
DestroyPolyn(Pb);
ClearList(Pa);
Pa.head=Pc.head;
Pa.tail=Pc.tail;
Pa.len=Pc.len;
}
void DerivPolyn(polynomial &Pa)
{//对一元多项式求导
polynomial Pb;
Position qa,qb;
term a,b;
InitList(Pb);
qa=GetHead(Pa);
qa=qa->next;
while(qa)
{
a=GetCurElem(qa);
b.coef=a.coef*a.expn;
b.expn=a.expn-1;
OrderInsertMerge(Pb,b,cmp);
qa=qa->next;
}
ClearList(Pa);
Pa.head=Pb.head;
Pa.tail=Pb.tail;
Pa.len=Pb.len;
}
void main()
{
polynomial p,q;
int m;
printf("请输入第一个一元多项式的非零项的个数:");
scanf("%d",&m);
CreatPolyn(p,m);
printf("请输入第二个一元多项式的非零项的个数:");
scanf("%d",&m);
CreatPolyn(q,m);
AddPolyn(p,q);
printf("两个一元多项式相加的结果:\n");
PrintPolyn(p);
printf("请输入第三个一元多项式的非零项的个数:");
scanf("%d",&m);
CreatPolyn(q,m);
SubtractPolyn(p,q);
printf("两个一元多项式相减的结果:\n");
PrintPolyn(p);
printf("请输入第四个一元多项式的非零项的个数:");
scanf("%d",&m);
CreatPolyn(q,m);
MultiplyPolyn(p,q);
printf("两个一元多项式相乘的结果:\n");
PrintPolyn(p);
DerivPolyn(p);
printf("一元多项式求导的结果:\n");
PrintPolyn(p);
DestroyPolyn(p);
}
四.测试结果
运行结果: