// c2-6.h 抽象数据类型Polynomial的实现见图2.45)
typedef struct // 项的表示，多项式的项作为LinkList的数据元素
{
float coef; // 系数
int expn; // 指数
}term,ElemType; // 两个类型名：term用于本ADT，ElemType为LinkList的数据对象名
图246 是根据c2-5.h 和c2-6.h 定义的多项式7.3+22X7 的存储结构。
// bo2-7.cpp 多项式存储结构由c2-6.h定义)的基本操作及算法2.22，2.23等8个)
#include"c2-5.h"
#include"bo2-6.cpp"
typedef LinkList polynomial;
#define DestroyPolyn DestroyList // 与bo2-6.cpp中的函数同义不同名
#define PolynLength ListLength // 与bo2-6.cpp中的函数同义不同名
void OrderInsertMergeLinkList &L,ElemType e,int* compare)term,term))
{ // 按有序判定函数compare)的约定，将值为e的结点插入或合并到升序链表L的适当位置
Position q,s;
ifLocateElemL,e,q,compare)) // L中存在该指数项
{
q->data.coef+=e.coef; // 改变当前结点系数的值
if!q->data.coef) // 系数为0
{ // 删除多项式L中当前结点
s=PriorPosL,q); // s为当前结点的前驱
if!s) // q无前驱
s=L.head;
DelFirstL,s,q);
FreeNodeq);
}
}
else // 生成该指数项并插入链表
{
MakeNodes,e); // 生成结点
InsFirstL,q,s);
}
}
int cmpterm a,term b) // CreatPolyn)的实参
{ // 依a的指数值<、=或>b的指数值，分别返回-1、0或+1
ifa.expn==b.expn)
return 0;
else
return a.expn-b.expn)/absa.expn-b.expn);
}
void CreatPolynpolynomial &P,int m) // 算法2.22
{ // 输入m项的系数和指数，建立表示一元多项式的有序链表P
Position q,s;
term e;
int i;
InitListP);
printf"请依次输入%d个系数，指数：
",m);
fori=1;i<=m;++i)
{ // 依次输入m个非零项可按任意顺序)
scanf"%f,%d",&e.coef,&e.expn);
if!LocateElemP,e,q,cmp)) // 当前链表中不存在该指数项，cmp是实参
{
MakeNodes,e); // 生成结点并插入链表
InsFirstP,q,s);
}
}
}
void PrintPolynpolynomial P)
{ // 打印输出一元多项式P
Link q;
q=P.head->next; // q指向第1个结点
printf" 系数指数
");
whileq)
{
printf"%f %d
",q->data.coef,q->data.expn);
q=q->next;
}
}
void AddPolynpolynomial &Pa,polynomial &Pb) // 算法2.23
{ // 多项式加法：Pa=Pa+Pb，并销毁一元多项式Pb
Position ha,hb,qa,qb;
term a,b;
ha=GetHeadPa);
hb=GetHeadPb); // ha和hb分别指向Pa和Pb的头结点
qa=NextPosha);
qb=NextPoshb); // qa和qb分别指向Pa和Pb中当前结点现为第1个结点)
while!ListEmptyPa)&&!ListEmptyPb)&&qa)
{ // Pa和Pb均非空且ha没指向尾结点qa!=0)
a=GetCurElemqa);
b=GetCurElemqb); // a和b为两表中当前比较元素
switchcmpa,b))
{
case -1:ha=qa; // 多项式Pa中当前结点的指数值小
qa=NextPosha); // ha和qa均向后移1个结点
break;
case 0: qa->data.coef+=qb->data.coef; // 两者的指数值相等，修改Pa当前结点的系数值
ifqa->data.coef==0) // 删除多项式Pa中当前结点
{
DelFirstPa,ha,qa);
FreeNodeqa);
}
else
ha=qa;
DelFirstPb,hb,qb);
FreeNodeqb);
qb=NextPoshb);
qa=NextPosha);
break;
case 1: DelFirstPb,hb,qb); // 多项式Pb中当前结点的指数值小
InsFirstPa,ha,qb);
ha=ha->next;
qb=NextPoshb);
}
}
if!ListEmptyPb))
{
Pb.tail=hb;
AppendPa,qb); // 链接Pb中剩余结点
}
DestroyPolynPb); // 销毁Pb
}
void AddPolyn1polynomial &Pa,polynomial &Pb)
{ // 另一种多项式加法的算法：Pa=Pa+Pb，并销毁一元多项式Pb
Position qb;
term b;
qb=GetHeadPb); // qb指向Pb的头结点
qb=qb->next; // qb指向Pb的第1个结点
whileqb)
{
b=GetCurElemqb);
OrderInsertMergePa,b,cmp);
qb=qb->next;
}
DestroyPolynPb); // 销毁Pb
}
void Oppositepolynomial Pa)
{ // 一元多项式Pa系数取反
Position p;
p=Pa.head;
whilep->next)
{
p=p->next;
p->data.coef*=-1;
}
}
void SubtractPolynpolynomial &Pa,polynomial &Pb)
{ // 多项式减法：Pa=Pa-Pb，并销毁一元多项式Pb
OppositePb);
AddPolynPa,Pb);
}
void MultiplyPolynpolynomial &Pa,polynomial &Pb)
{ // 多项式乘法：Pa=Pa×Pb，并销毁一元多项式Pb
polynomial Pc;
Position qa,qb;
term a,b,c;
InitListPc);
qa=GetHeadPa);
qa=qa->next;
whileqa)
{
a=GetCurElemqa);
qb=GetHeadPb);
qb=qb->next;
whileqb)
{
b=GetCurElemqb);
c.coef=a.coef*b.coef;
c.expn=a.expn+b.expn;
OrderInsertMergePc,c,cmp);
qb=qb->next;
}
qa=qa->next;
}
DestroyPolynPb); // 销毁Pb
ClearListPa); // 将Pa重置为空表
Pa.head=Pc.head;
Pa.tail=Pc.tail;
Pa.len=Pc.len;
}
// main2-7.cpp 检验bo2-7.cpp的主程序
#include"c1.h"
#include"c2-6.h"
#include"bo2-7.cpp"
void main)
{
polynomial p,q;
int m;
printf"请输入第1个一元多项式的非零项的个数：");
scanf"%d",&m);
CreatPolynp,m);
printf"请输入第2个一元多项式的非零项的个数：");
scanf"%d",&m);
CreatPolynq,m);
AddPolynp,q);
printf"2个一元多项式相加的结果：
");
PrintPolynp);
printf"请输入第3个一元多项式的非零项的个数：");
scanf"%d",&m);
CreatPolynq,m);
AddPolyn1p,q);
printf"2个一元多项式相加的结果另一种方法)：
");
PrintPolynp);
printf"请输入第4个一元多项式的非零项的个数：");
scanf"%d",&m);
CreatPolynq,m);
SubtractPolynp,q);
printf"2个一元多项式相减的结果：
");
PrintPolynp);
printf"请输入第5个一元多项式的非零项的个数：");
scanf"%d",&m);
CreatPolynq,m);
MultiplyPolynp,q);
printf"2个一元多项式相乘的结果：
");
PrintPolynp);
DestroyPolynp);
}
运行结果如下：
