#include<stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR -1
#define OVERFLOW -2
typedef int Status;
typedef struct
{
//項的表示,多項式的項作為LinkList的資料元素
int coef; // 系數COEFFICIENT
int expn; // 指數EXPONENT
} term, ElemType;
typedef struct LNode //結點型別
{
ElemType data;
struct LNode *next;
} *Link, *Position;
typedef struct //鏈表型別
{
Link head, tail; //分別指向線性鏈表中的頭結點和最后一個結點
int len; //指向線性鏈表中資料元素的個數
} LinkList;
typedef LinkList polynomial; //用帶表頭結點的有序鏈表表示多項式
/* 請在這里填寫答案 */
Status InitList(Link &L)//建立結點
{
L=(struct LNode*)malloc(sizeof(struct LNode)); //生成頭結點
if(!L)
return ERROR;
L->next=NULL;
return OK;
}
Position GetHead(Link L)//回傳L中頭結點的位置
{
Link p;
p=L;
return p;
if(p==NULL)
return NULL;
}
Status SetCurElem(Link &p,ElemType e)//用e更新p所指向結點的資料元素的值
{
e=p->data;
return OK;
}
ElemType GetCurElem(Link p)//回傳p所指向的資料的值
{
return p->data;
}
Status MakeNode(Link &p,ElemType e)//建立結點
{
p=(Link)malloc(sizeof(LNode));
if(!p)
return ERROR;
p->data=https://bbs.csdn.net/topics/e;
p->next=NULL;
return OK;
}
Status InsFirst(Link &L,Link h,Link s)//將s所指結點插入到h之后
{
s->next=h->next;
h->next=s;
return OK;
}
int cmp(term a,term b)
{
if(a.expn<b.expn)//比較指數
return -1;
else if(a.expn==b.expn)
return 0;
else
return 1;
}
Status DelFirst(Link &L,Link h,Link &q)//洗掉h之后的第一個結點并以q回傳
{
q=h->next;
h->next=q->next;
free(q);
return OK;
}
void FreeNode(Link &p)//釋放結點
{
p=NULL;
}
Position NextPos(Link L,Link p)//回傳p所指向的結點的直接后繼位置
{
if(p->next!=NULL)
return p->next;
return NULL;
}
Status LocateElem(Link L,ElemType e,Position &q, Status(*compare)(ElemType,ElemType))
{
int i;
Link p;
i = 1; //i的初值為第1個元素的位序
p =L->next; //p的初值為第1個元素的存盤位置
while(p&&!(*compare)(p->data,e))
{
++i;
p=p->next;
}
if (p)
return TRUE;
else
return FALSE;
}
void CreatePolyn(Link &P, int m)
{
InitList(P);
Link h=GetHead(P);
ElemType e;
Link q,s;
e.coef=0.0;
e.expn=-1;
SetCurElem(h,e);
int i;
for(i=1; i<=m; i++)
{
scanf("%d%d",&e.coef,&e.expn);
if(!LocateElem(P,e,q,cmp))
{
if(MakeNode(s,e))
InsFirst(P,q,s);
}
}
}
Status Append(Link &L,Link s)
{
Link p;
p=L;
while(p)
{
p=p->next;
}
p->next=s;
return OK;
}
Status ListEmpty(Link L)
{
if(L==NULL)
return TRUE;
return FALSE;
}
void AddPolyn (Link &Pa,Link &Pb)
{
Link ha,hb,qa,qb;
ElemType a,b;
ElemType sum;
ha=GetHead(Pa);//ha,hb指向Pa和Pb的頭結點；
hb=GetHead(Pb);
qa=NextPos(Pa,ha);//qa,qb指向Pa和Pb的當前結點
qb=NextPos(Pb,hb);
while(qa&&qb)//均是非空
{
a=GetCurElem(qa);
b=GetCurElem(qb);
switch(cmp(a,b))
{
case -1://Pa小
ha=qa;
qa=NextPos(Pa,qa);
break;
case 0:
sum.coef=a.coef+b.coef;
sum.expn=a.expn;
if(sum.coef!=0.0)
{
SetCurElem(qa,sum);//修改Pa的系數值；
ha=qa;
}
else//洗掉結點
{
DelFirst(Pa,ha,qa);
FreeNode(qa);
}
DelFirst(Pb,hb,qb);//洗掉Pb中的結點
FreeNode(qb);
qb=NextPos(Pb,hb);
qa=NextPos(Pa,ha);
break;
case 1://pb中的指數值小
DelFirst(Pb,hb,qb);
InsFirst(Pa,ha,qb);
qb=NextPos(Pb,hb);
ha=NextPos(Pa,ha);
break;
}
if(!ListEmpty(Pb))
{
Append(Pa,qb);
}
FreeNode(hb);
}
}
int main()
{
Link Pa,Pb;
int m,n;
Position ha,hb,qa,qb;
//term a;
scanf("%d",&m);
CreatePolyn(Pa, m);
scanf("%d",&n);
CreatePolyn(Pb, n);
AddPolyn (Pa, Pb);
if(Pa==NULL)
{
printf("0\n");
return 0;
}
ha=GetHead(Pa); //ha和hb分別指向Pa和Pb的頭結點
qa=NextPos(Pa,ha);
while(qa)
{
printf("%d,%d\n",qa->data.coef,qa->data.expn);
ha=qa;
qa = NextPos(Pa,ha);
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/135710.html
標籤：C++ 語言