[线性表](6)一元多项式相加表示
符号多项式的操作，已经成为表处理的典型用例，在数学上，一个一元多项式Pn(x)可按升幂写成：
Pn(x)=p0+p1x+p2x²+...+Pnx^n
它由n+1个系数惟一确定。因此，在计算机里，它可用一个线性表P来表示：
P=(p0，p1，p2，.....，pn)
每一项的指数i隐含在其系数pi的序号里。
假设Qm(x)是一元m次多项式，同样可用线性表Q来表示
Q=(q0，q1，q2，....，qm)
不失一般性，设m<n，则两个多项式相加的结果 Rn(x)=Pn(x)+Qm(x) 可用线性表R表示：
R=(p0+q0，p1+q1，p2+q2，...，pm+qm，p(m+1)，...，pn)
显然，我们可以对P、Q和R采用顺序存储结构，是的多项式相加的算法定义十分简单。至此，一元多项式的表示及相加问题似乎已经解决，但是，在通常的应用中，多项式的次数可能很高且变化很大，使得顺序存储结构的最大长度很难确定。特别是在处理形如：
S(x)=1+3x^10000+2x^20000
的多项式时，就要用一长度为20001的线性表来表示，表中仅有3个非零元素，这种对内存空间的浪费是应当避免的，但是如果只存储非零系数项，则显然必须同时存储相应的指数。
一般情况下的一元n次多项式可写为：
Pn(x)=p1x^e1+p2x^e2+...+pmx^em
其中，pi是指数为ei的项的非零系数，且满足：
0<=e1<e2<...<em=n
若用一个长度为m且每个元素有两个数据项(系数项和指数项)的线性表
((p1,e1),(p2,e2),...,(pm,em))
便可惟一确定多项式pn(x)。在最坏情况下，n+1(=m)个系数都不为零，则比只存储每项系数的方案要多存储一倍的数据。但是，对于S(x)类的多项式，这种表示大大节省空间。
对于线性表的两种存储结构，对上述一元多项式也可以有两种存储方法，在实际的应用程序中取用哪一种，则要视多项式作何种运算而定
若只对多项式进行“求值”等不改变多项式的系数和指数的运算，则采用类似于顺序表的顺序存储结构即可，否则应采用链式存储表示。
抽象数据类型一元多项式的定义如下：
ADT Polynomial
{
数据对象：D = {ai | ai属于TermSet，i = 1,2，...，m，m >= 0}
TermSet中的每个元素包含一个表示系数的实数和表示指数的整数
数据关系：1 = {<a(i - 1)，ai> | a(i - 1)，ai属于D，且a(i - 1)中的指数值 < ai中的指数值，i = 2,...，n}
基本操作：
CreaPolyn(&P,m)
操作结果：输入m项的系数和指数，建立一元多项式P
DestroyPolyn(&P)
初始条件：P已存在
操作结果：销毁一元多项式P
PrintPolyn(P)
初始条件：P已存在
操作结果：打印输出一元多项式P
PolynLength(p)
初始条件：P已存在
操作结果：返回一元多项式P中的项数
AddPolyn(&Pa， & Pb)
初始条件：一元多项式Pa和Pb已存在
操作结果：完成多项式相加运算，即：Pa = Pa + Pb， 并销毁一元多项式Pb
SubtractPolyn(&Pa,&Pb)
初始条件：一元多项式Pa和Pb已存在。
操作结果：完成多项式相减运算，即：Pa = Pa - Pb，并销毁一元多项式Pb
MultiplyPolyn(&Pa,&Pb)
初始条件：一元多项式Pa和Pb已存在
操作结果：完成多项式相乘运算，即：Pa=Pa*Pb，并销毁一元多项式Pb
}实现上述定义的一元多项式，显然应采用链式存储结构，如下图所示
图一：表示一元多项式A17（x）=7+3x+9x^8+5x^17
图二：表示一元多项式B8（8）=8x+22x^7-9x^8.
根据一元多项式相加的运算规则：
- 对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”中的一项
- 对于两个一元多项式中所有指数不相同的项，则分别复制到“和多项式中去”
在此，按照上述抽象数据类型Polynomial中基本操作的定义，“和多项式”链表中的结点无需另生成，而应该从两个多项式的链表中摘取。
其运算规则如下：
假设指针qa和qb分别指向多项式A和多项式B中当前进行比较的某个结点，则比较两个结点中的指数项，有下列三种情况
指针qa所指结点的指数值 < 指针pb所指结点的指数值
- 则应该摘取qa指针所指结点插入到“和多项式”链表中去
指针qa所指结点的指数值 > 指针pb所指结点的指数值
- 则应该摘取pb指针所指结点插入到“和多项式”链表中去
指针qa所指结点的指数值 = 指针pb所指结点的指数值
- 则将两个结点中的系数相加，若和数不为零，则修改qa所指结点的系数值，同时释放qb所指结点
- 反之，从多项式A的链表中删除相应结点，并释放指针qa和qb所指结点。
例如上述两个多项式相加得到“和多项式”如下图所示，图中长方框表示已被释放的结点：
上述多项式的相加过程和上一节讨论的归并两个有序表的过程极其类似，不同之处仅在于，后者在比较数据元素时只出现两种情况，因此，多项式相加的过程也可以完全利用线性链表的基本操作来完成。
需要注意的是，在之前我们所定义的线性链表类型适用于一般的线性表，而表示一元多项式的应该是有序链表，有序链表的基本操作定义与线性表有两处不同。
- LocateElem的职能不同
- 需增加按有序关系进行插入的操作OrderInsert
两操作抽象说明如下：
Status LocateElem(LinkList L, ElemType e, Position& q, int(*compare)(ElemType, ElemType))
//若有序链表L中存在与e满足判定函数compare()取值为0的元素，则q指示L中第一个
//值为e的结点的位置，并返回TRUE，否则q指示第一个与e满足判定函数compare()取值
//>0的元素的前驱的位置，并返回FALSE
Status OrderInsert(LinkList& L, ElemType e, int(*compare)(ElemeType, ElemType))
//按有序判定函数compare()的约定，将值为e的结点插入到有序链表L的适当位置上抽象数据类型Polynomial的实现
typedef struct
{//项的表示，多项式的项作为LinkList的数据元素
float coef;//系数
int expn;//指数
}trem,ElemType;//两个类型名：trem用于本ADT，ElemType为LinkList的数据对象名
typedef LinkList polynomial;//用带表头结点的有序链表表示多项式
/*基本操作的函数原型说明*/
void CreatPolyn(polynomial& P, int m);
//输入m项的系数和指数，建立表示一元多项式的有序链表P
void DestroyPolyn(polynomial& P);
//销毁一元多项式P
void PrintPolyn(polynomial P);
//打印出一元多项式P
int PolynLength(polynomial P);
//返回一元多项式P的项数
void AddPolyn(polynomial& Pa, polynomial& Pb);
//完成多项式相加运算，即：Pa=Pa+Pb，并销毁一元多项式Pb
void SubtractPolyn(polynomial& Pa, polynomial& Pb);
//完成多项式相减运算，即：Pa=Pa-Pb，并销毁一元多项式Pb
void MultiplyPolyn(polynomial& Pa, polynomial& Pb);
//完成多项式相乘运算，即：Pa=Pa*Pb,并销毁一元多项式Pb
/*基本操作的算法描述(部分)*/
int cmp(term a, term b);
//依a的指数值<(或=)(或>)b的指数值，分别返回-1、0和+1
void CreatPolyn(polynomial& P, int m)
//输入m项的系数和指数，建立表示一元多项式的有序链表P
{
InitList(P);
h = GetHead(P);
e.coef = 0.0;
e.expn = -1;
SetCurElem(h, e);//设置头结点的数据元素
for (i = 1; i <= m; i++)
{
scanf(e.coef, e.expn);
if (!LocateElem)(P, e, q, (*cmp)())
{
if (MakeNode(s, e));//当前链表中不存在该指数项
InsFirst(q, s);//生成结点并插入链表
}
}
}上述需要注意的就是多项式的运算：加减乘除等，这里我就拿多项式的加法做讲解！
多项式加法的算法描述如下：
void AddPolyn(polynomial& Pa, polynomial& Pb)
//多项式加法：Pa=Pa+Pb，利用两个多项式的结点构成“和多项式”
{
ha = GetHead(Pa);
hb = GetHead(Pb);
//ha和hb分别指向Pa和Pb的头结点
qa = NextPos(Pa, ha);
qb = NextPos(Pb, hb);
//qa和qb分别指向Pa和Pb中当前结点。
while (qa && qb)
//qa和qb均非空
{
a = GetCurElem(qa);
b = GetCurElem(qb);//a和b为两表中当前比较元素
switch (*cmp(a, b))
{
case -1://多项式PA中当前结点的指数值小
{
ha = qa;
qa = NextPos(qa, qb);
break;
}
case 0:
{
sum = a.coef + b.coef;
if (sum != 0)//修改多项式PA中当前结点的系数值
{
SetCurElem(qa, sum);
ha = qa;
}
else//删除多项式PA中的结点
{
DelFirst(ha, qa);
FreeNode(qa);
}
DelFirst(hb, qb);
FreeNode(qb);
qb = NextPos(Pb, hb);
qa = NextPos(Pa, ha);
break;
}
case 1://多项式PB中当前结点的指数值小
{
DelFirst(ha, qb);
InsFirst(ha, qb);
qb = NextPos(Pb, hb);
ha = NextPos(Pa, ha);
break;
}
}
}
if (ListEmpty(Pb))//链接Pb中剩余结点
{
Append(Pa, qb);
}
FreeNode(hb);//释放Pb的头结点
}C语言实现代码：
void AddElem(Link A, Link B)
{
Link qa, qb, ha, hb;
ha = A;
hb = B;
qa = A->next;
qb = B->next;
while (qb && qa)
{
if (qa->expn < qb->expn)
{
ha = qa;
qa = qa->next;
}
if (qa->expn > qb->expn)
{
ha->next = qb;
ha = ha->next;
qb = qb->next;
}
if (qa->expn == qb->expn)
{
float sum = qa->coef + qb->coef;
if (sum == 0)
{
ha->next = qa->next;
qa->next = NULL;
qa = ha->next;
qb = qb->next;
ha = qa;
}
else
{
qa->coef = sum;
ha = qa;
qa = qa->next;
qb = qb->next;
}
}
}
free(hb);
}两个一元多项式相乘的算法，可以利用两个一元多项式相加的算法来实现，因为乘法运算可以分解为一系列的加法运算。
void MuitlList(LinkList La, LinkList Lb)
{
LinkList ha, hb, pa, pb;
if (!La->next || !Lb->next)
{
printf("为空");
exit(0);
}
ha = La;
hb = Lb;
pb = Lb->next;
while (pb)
{
pa = La->next;
while (pa)
{
node = (LinkList)malloc(sizeof(LNode));
node->next = NULL;
node->coef = pa->coef * pb->coef;
node->expn = pa->expn + pb->expn;
pa = pa->next;
hb->next = node;
hb = hb->next;
}
pb = pb->next;
}
free(ha);
LinkList p1, s1;
p = Lb->next;
p1 = p;
while (p)
{
s = p->next;
s1 = s;
while (s)
{
if (p->expn == s->expn)
{
if (p->coef == 0)
{
p1->next = p->next;
free(p);
p = p1;
s1->next = s->next;
free(s);
s = s1;
continue;
}
else
{
p->coef = s->coef + p->coef;
s1->next = s->next;
free(s);
s = s1;
continue;
}
}
s1 = s;
s = s->next;
}
p1 = p;
p = p->next;
}
p = Lb->next;
while (p != NULL)
{
printf("%.f^%d ", p->coef, p->expn);
p = p->next;
}
}完整C语言测试代码如下：乘法
#include<stdio.h>
#include<stdlib.h>
typedef struct LNode
{
float coef;
int expn;
struct LNode* next;
}LNode, * LinkList;
LinkList La, Lb, node, p, s;
void MuitlList(LinkList, LinkList);
void InitElem(LinkList);
int main()
{
La = (LinkList)malloc(sizeof(LNode));
if (La == NULL)
{
printf("错误：La失败");
exit(0);
}
La->next = NULL;
Lb = (LinkList)malloc(sizeof(LNode));
if (Lb == NULL)
{
printf("错误：Lb失败");
exit(0);
}
Lb->next = NULL;
int m, n;
printf("请输入多项式A的项数：");
scanf("%d", &m);
while (m)
{
InitElem(La);
m--;
}
p = La->next;
printf("请输入多项式B的项数：");
scanf("%d", &n);
while (n)
{
InitElem(Lb);
n--;
}
MuitlList(La, Lb);
system("pause");
return 0;
}
void InitElem(LinkList L)
{
node = (LinkList)malloc(sizeof(LNode));
scanf("%f %d", &node->coef, &node->expn);
if (L->next == NULL)
{
L->next = node;
node->next = NULL;
}
else
{
p = L;
while (p->next != NULL)
{
p = p->next;
}
p->next = node;
node->next = NULL;
}
}
void MuitlList(LinkList La, LinkList Lb)
{
LinkList ha, hb, pa, pb;
if (!La->next || !Lb->next)
{
printf("为空");
exit(0);
}
ha = La;
hb = Lb;
pb = Lb->next;
while (pb)
{
pa = La->next;
while (pa)
{
node = (LinkList)malloc(sizeof(LNode));
node->next = NULL;
node->coef = pa->coef * pb->coef;
node->expn = pa->expn + pb->expn;
pa = pa->next;
hb->next = node;
hb = hb->next;
}
pb = pb->next;
}
free(ha);
LinkList p1, s1;
p = Lb->next;
p1 = p;
while (p)
{
s = p->next;
s1 = s;
while (s)
{
if (p->expn == s->expn)
{
if (p->coef == 0)
{
p1->next = p->next;
free(p);
p = p1;
s1->next = s->next;
free(s);
s = s1;
continue;
}
else
{
p->coef = s->coef + p->coef;
s1->next = s->next;
free(s);
s = s1;
continue;
}
}
s1 = s;
s = s->next;
}
p1 = p;
p = p->next;
}
p = Lb->next;
while (p != NULL)
{
printf("%.f^%d ", p->coef, p->expn);
p = p->next;
}
}掌握了这个例子，对于单链的操作基本已经掌握了！利用多项式相加，相乘，相减，相除的数学运算法则，来对存放数据的链表进行操作 。指针在这里起到了很大的用途
怎么说呢.....上述的加法和乘法我看教程一脸懵，抽象的代码太难看了，还要完善很多函数，所幸就暴力起指针了，难以想象，乘法我起了四个指针进行逐次遍历来更新链表。
时间复杂度还待完善！