一元多项式的加法减法乘法
－－(c语言描述)线性表应用
来源：永远的北邮人
vc6.0下调试通过
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
//#define OVERFLOW -2
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;
Link tail;
int len;
};
void MakeNode(Link
&p,ElemType e)
{
p=(Link)malloc(sizeof(LNode));
if(!p)
{
exit(ERROR);
}
p->data=e;
}
void FreeNode(Link
&p)
{
free(p);
p=NULL;
}
void
InitList(LinkList &L)
{
Link p;
p=(Link)malloc(sizeof(LNode));
if(p)
{
p->next=NULL;
L.head=L.tail=p;
L.len=0;
}
else
{
exit(ERROR);
}
}
void
ClearList(LinkList &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;
}
}
void
DestroyList(LinkList &L)
{
ClearList(L);
FreeNode(L.head);
L.tail=NULL;
L.len=0;
}
void
InsFirst(LinkList &L,Link h,Link s)
{
s->next=h->next;
h->next=s;
if(h==L.tail)
{
L.tail=h->next;
}
L.len++;
}
Status
DelFirst(LinkList &L,Link h,Link
&q)
{
q=h->next;
if(q)
{
h->next=q->next;
if(!h->next)
{
L.tail=h;
}
L.len--;
return OK;
}
else
return FALSE;
}
void
Append(LinkList &L,Link s)
{
int i=1;
L.tail->next=s;
while(s->next)
{
s=s->next;
i++;
}
L.tail=s;
L.len+=i;
}
Position
PriorPos(LinkList L,Link p)
{
Link q;
q=L.head->next;
if(p==q)
{
return NULL;
}
else
{
while(q->next!=p)
{
q=q->next;
}
return q;
}
}
Status
Remove(LinkList &L,Link &q)
{
Link p=L.head;
if(L.len==0)
{
q=NULL;
return FALSE;
}
while(p->next!=L.tail)
{
p=p->next;
}
q=L.tail;
p->next=NULL;
L.tail=p;
L.len--;
return OK;
}
void
InsBefore(LinkList &L,Link &p,Link
s)
{
Link q;
q=PriorPos(L,p);
if(!q)
{
q=L.head;
}
s->next=p;
q->next=s;
p=s;
L.len++;
}
void
InsAfter(LinkList &L,Link &p,Link
s)
{
if(p==L.tail)
{
L.tail=s;
}
s->next=p->next;
p->next=s;
p=s;
L.len++;
}
void
SetCurElem(Link p,ElemType e)
{
p->data=e;
}
ElemType GetCurElem(Link 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)
{
return p->next;
}
Status
LocatePos(LinkList L,int i,Link &p)
{
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))
{
Link p=L.head;
do
p=p->next;
while(p&&!(compare(p->data,e)));
return p;
}
void
ListTraverse(LinkList L,void(*visit)(ElemType))
{
Link p=L.head->next;
int j;
for(j=1;j<=L.len;j++)
{
visit(p->data);
p=p->next;
}
printf("\n");
}
void
OrderInsert(LinkList &L,ElemType e,int
(*comp)(ElemType,ElemType))
{
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;
}
Status LocateElem(LinkList L,ElemType e,Position
&q,int (*compare)(ElemType,ElemType))
{
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;
}
}
typedef LinkList
polynomial;
#define DestroyPolyn DestroyList
#define PolyLength ListLength
void OrderInsertMerge(LinkList &L,ElemType e,int
(*compare)(term,term))
{
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);
}
}
else
{
MakeNode(s,e);
InsFirst(L,q,s);
}
}
int cmp(term
a,term b)
{
if(a.expn==b.expn)
return 0;
else
return
(a.expn-b.expn)/abs(a.expn-b.expn);
}
void
CreatPolyn(polynomial &P,int m)
{
Position q,s;
term e;
int i;
InitList(P);
printf("请依次输入%d个系数,指数:\n",m);
for(i=1;i<=m;i++)
{
scanf("%f,%d",&e.coef,&e.expn);
if(!LocateElem(P,e,q,cmp))
{
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 ha,hb,qa,qb;
term a,b;
ha=GetHead(Pa);
hb=GetHead(Pb);
qa=NextPos(ha);
qb=NextPos(hb);
while(!ListEmpty(Pa)&&!ListEmpty(Pb)&&qa)
{
a=GetCurElem(qa);
b=GetCurElem(qb);
switch(cmp(a,b))
{
case -1:ha=qa;
qa=NextPos(ha);
break;
case
0:qa->data.coef+=qb->data.coef;
if(qa->data.coef==0)
{
DelFirst(Pa,ha,qa);
FreeNode(qa);
}
else
ha=qa;
DelFirst(Pb,hb,qb);
FreeNode(qb);
qb=NextPos(hb);
qa=NextPos(ha);
break;
case 1:
DelFirst(Pb,hb,qb);
InsFirst(Pa,ha,qb);
ha=ha->next;
qb=NextPos(hb);
}
}
if(!ListEmpty(Pb))
{
Pb.tail=hb;
Append(Pa,qb);
}
DestroyList(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 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);
}
