37、一元多项式的表示和相加
一、基本概念
1、多项式pn(x)可表示成: pn(x)=a0+a1x+a2x2+…+anxn。
listP={（a0，e0），(a1，e1)，(a2，e2)，…，(an，en) }。在这种线性表描述中，各个结点包括两个数据域，对应的类型描述为：
typedefstruct node
{double coef; //系数为双精度型
int expn; //指数为正整型
struct node *next; //指针域
}polynode;
二、算法思想
对两个一元多项式进行相加操作的运算规则是：假设指针qa和qb分别指向多项式A(x)和B(x)中当前进行比较的某个结点，则需比较两个结点数据域的指数项，有三种情况：
(1) 指针qa所指结点的指数值＜指针qb所指结点的指数值时，则保留qa指针所指向的结点，qa指针后移；
(2) 指针qa所指结点的指数值＞指针qb所指结点的指数值时，则将qb指针所指向的结点插入到qa所指结点前，qb指针后移；
(3) 指针qa所指结点的指数值＝指针qb所指结点的指数值时，将两个结点中的系数相加。若和不为零，则修改qa所指结点的系数值，同时释放qb所指结点；反之，从多项式A(x)的链表中删除相应结点，并释放指针qa和qb所指结点。
三、C语言描述
四、C语言实现
#include"stdio.h"
#include"stdlib.h"
#define OK 1
#define ERROR -1
#define FALSE 0
#define TRUE 2
typedef intStatus;
typedef struct
{
float coef; //系数
int expn; //指数
}term,ElemType;
typedef structLNode
{
ElemType data;
struct LNode*next;
}*Link,*Position;
typedef struct
{
Link head,tail;
int len;
}LinkList;
typedef LinkListpolynomial; //用带头结点的有序链表表示多项式
int cmp(terma,term b)
{
if(a.expn<b.expn)return -1;
elseif(a.expn==b.expn) return 0;
else return 1;
}//cmp
StatusInitList(polynomial &P)
{//构造一下空的线性链表
Link p;
p=(Link)malloc(sizeof(LNode));//生成头结点
if(p)
{
p->next=NULL;
P.head=P.tail=p;
P.len=0;
return OK;
}//
else return ERROR;
}//InitList
PositionGetHead(polynomial P)
{
return P.head;
}//Position
StatusSetCurElem(Position h,term e)
{
h->data=e;
return OK;
}//SetCurElem
StatusLocateElem(LinkList P,ElemType e,Position &q,int(*cmp)(ElemType,ElemType))
{
Link p=P.head,pp;
do
{
pp=p;
p=p->next;
}while(p&&(cmp(p->data,e)<0));
if(!p||cmp(p->data,e)>0)
{
q=pp;
return FALSE;
}//if
else //find it
{
q=p;
return TRUE;
}//else
}
StatusMakeNode(Link &p,ElemType e)
{
p=(Link)malloc(sizeof(LNode));
if(!p) returnERROR;
p->data=e;
return OK;
}//MakeNode
StatusInsFirst(LinkList &P,Link h,Link s)
{
s->next=h->next;
h->next=s;
if(h==P.tail)
P.tail=h->next;
++P.len;
return OK;
}//InsFirst
voidCreatPolyn(polynomial &P,int m)
{//输入m项的指数及系数，建立表示一元多项式的有序链表P
InitList(P);
Position h,q,s;
h=GetHead(P); //h指向P的头结点
term e;
e.coef=0.0;
e.expn=-1;
SetCurElem(h,e);//设置头结点的数据元素
printf("inputthe the value of m(indicate how many items)\n");
scanf("%d",&m);
printf("input(%d) ceof,expn(separated by ,)\n",m);
for(inti=1;i<=m;++i)
{
scanf("%f,%d",&e.coef,&e.expn);
if(!LocateElem(P,e,q,cmp))
{
if(MakeNode(s,e)) InsFirst(P,q,s);
}//if不存在，则生成新结点并插入
}//for
}//CreatPolyn
PositionNextPos(Link p)
{
return p->next;
}//NextPos
ElemTypeGetCurElem(Link p)
{
return p->data;
}//GetCurElem
StatusDelFirst(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;
}//if
else return FALSE;//链表空
}//DelFirst
void FreeNode(Link&p)
{
free(p);
p=NULL;
}//FreeNode
StatusListEmpty(LinkList L)
{
if(L.len)
return FALSE;
else return TRUE;
}//ListEmpty
StatusAppend(LinkList &L,Link s)
{
int i=1;
L.tail->next=s;
while(s->next)
{
s=s->next;
i++;
}//while
L.tail=s;
L.len+=i;
return OK;
}//Append
voidPrintPolyn(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;
}//while
}//PrintPolyn
StatusClearList(LinkList &L)
{
Link q,p;
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;
}//while
free(q);
L.tail=L.head;
L.len=0;
}//if
return OK;
}//ClearList
StatusDestroyPolyn(LinkList &L)
{ // 销毁线性链表L，L不再存在
ClearList(L); // 清空链表
FreeNode(L.head);
L.tail=NULL;
L.len=0;
return OK;
}//DestroyList
void AddPolyn(polynomial &Pa,polynomial&Pb)
{ // 多项式加法:Pa=Pa+Pb,并销毁一元多项式Pb
Position ha,hb,qa,qb;
term a,b;
ha=GetHead(Pa);
hb=GetHead(Pb); // ha和hb分别指向Pa和Pb的头结点
qa=NextPos(ha);
qb=NextPos(hb); // qa和qb分别指向Pa和Pb中当前结点（现为第一个结点）
while(qa&&qb)
{ // Pa和Pb均非空且ha没指向尾结点(qa!=0)
a=GetCurElem(qa);
b=GetCurElem(qb); // a和b为两表中当前比较元素
switch(cmp(a,b))
{
case -1:ha=qa; // 多项式Pa中当前结点的指数值小
qa=NextPos(ha); // ha和qa均向后移一个结点
break;
case 0: qa->data.coef+=qb->data.coef;
// 两者的指数值相等,修改Pa当前结点的系数值
if(qa->data.coef==0) // 删除多项式Pa中当前结点
{
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); // 多项式Pb中当前结点的指数值小
InsFirst(Pa,ha,qb);
ha=ha->next;
qb=NextPos(hb);
}
}
if(!ListEmpty(Pb))
{
Pb.tail=hb;
Append(Pa,qb); // 链接Pb中剩余结点
}
DestroyPolyn(Pb); // 销毁Pb
}
int main()
{
polynomial Pa,Pb;
int m;
CreatPolyn(Pa,m);
PrintPolyn(Pa);
printf("Pa.len:%d\n",Pa.len);
CreatPolyn(Pb,m);
PrintPolyn(Pb);
printf("Pb.len:%d\n",Pb.len);
AddPolyn(Pa,Pb);
PrintPolyn(Pa);
printf("Pa.len:%d\n",Pa.len);
return 1;
}
五、一元多项式相乘
六、线性表的两种存储结构：顺序表和链表。
1、基于空间的考虑
顺序表存储空间一般不会被完全使用，存在存储空间浪费。链表的存储空间根据需要而分配，无存储空间浪费。线性表长度基本固定时，采用顺序表，否则采用链表。
2、基于时间的考虑
顺序表是随机存取结构，存取任一结点的时间复杂度为O（1）。链表是顺序存取结构，时间复杂度为O(n)。
顺序表插入和删除运算可能要移动大量元素（平均接近一半）。链表插入和删除运算修改指针就可实现，无需移动元素。