严蔚敏数据结构：链表实现一元多项式相加

一、基本概念

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; }

总结

以上是生活随笔为你收集整理的严蔚敏数据结构：链表实现一元多项式相加的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。