一、基本概念

1、多項式pn(x)可表示成: ?pn(x)=a0+a1x+a2x2+…+anxn。

listP={（a0，e0），(a1，e1)，(a2，e2)，…，(an，en) }。在這種線性表描述中，各個結點包括兩個數據域，對應的類型描述為：

typedef struct 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所指結點。

#include "stdio.h"
#include "stdlib.h"
#define OK 1
#define ERROR -1
#define FALSE 0
#define TRUE 2
typedef int Status;typedef struct
{
float coef; //系數
int expn;   //指數
}term,ElemType;typedef struct LNode
{
ElemType data;
struct LNode *next;
}*Link,*Position;typedef struct
{
Link head,tail;
int len;
}LinkList;typedef LinkList polynomial; //用帶頭結點的有序鏈表表示多項式int cmp(term a,term b)
{
if(a.expn<b.expn) return -1;
else if(a.expn==b.expn) return 0;
else return 1;
}//cmpStatus InitList(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;
}//InitListPosition GetHead(polynomial P)
{
return P.head;
}//PositionStatus SetCurElem(Position h,term e)
{
h->data=e;
return OK;
}//SetCurElemStatus LocateElem(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;}//ifelse //find it{q=p;return TRUE;}//else
}Status MakeNode(Link &p,ElemType e)
{
p=(Link)malloc(sizeof(LNode));
if(!p) return ERROR;
p->data=e;
return OK;
}//MakeNodeStatus InsFirst(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;
}//InsFirstvoid CreatPolyn(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("input the the value of m(indicate how many items)\n");
scanf("%d",&m);
printf("input (%d) ceof,expn(separated by ,)\n",m);
for(int i=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
}//CreatPolynPosition NextPos(Link p)
{
return p->next;
}//NextPosElemType GetCurElem(Link p)
{
return p->data;
}//GetCurElemStatus 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;}//ifelse return FALSE; //鏈表空}//DelFirstvoid FreeNode(Link &p)
{
free(p);
p=NULL;
}//FreeNodeStatus ListEmpty(LinkList L)
{
if(L.len)return FALSE;
else return TRUE;
}//ListEmptyStatus Append(LinkList &L,Link s)
{
int i=1;
L.tail->next=s;
while(s->next){s=s->next;i++;}//whileL.tail=s;
L.len+=i;
return OK;
}//Appendvoid 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;}//while
}//PrintPolynStatus ClearList(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;}//whilefree(q);L.tail=L.head;L.len=0;}//if
return OK;
}//ClearListStatus DestroyPolyn(LinkList &L)
{ // 銷毀線性鏈表L，L不再存在ClearList(L); // 清空鏈表FreeNode(L.head);L.tail=NULL;L.len=0;return OK;}//DestroyListvoid AddPolyn(polynomial &Pa,polynomial &Pb){ // 多項式加法:Pa=Pa+Pb,并銷毀一元多項式PbPosition 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);}elseha=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;
}