数据结构(C语言)用单链表存储一元多项式并实现两个多项式的相加运算.doc

#include#include#includetypedefintElemType;/*单项链表的声明*/typedefstructPolynNodeintcoef;/系数intexpn;/指数structPolynNode*next;PolynNode,*PolynList;/*正位序(插在表尾)输入n个元素的值，建立带表头结构的单链线性表*/*指数系数一对一对输入*/voidCreatePolyn(PolynList&L,intn)inti;PolynListp,q;L=(PolynList)malloc(sizeof(PolynNode);/生成头结点L-next=NULL;q=L;printf(成对输入%d个数据n,n);for(i=1;icoef,&p-expn);/指数和系数成对输入q-next=p;q=q-next;p-next=NULL;/初始条件：单链表L已存在/操作结果:依次对L的每个数据元素调用函数vi()。一旦vi()失败,则操作失败voidPolynTraverse(PolynListL,void(*vi)(ElemType,ElemType)PolynListp=L-next;while(p)vi(p-coef,p-expn);if(p-next)printf(+);/“+”号的输出，最后一项后面没有“+”p=p-next;printf(n);/*ListTraverse()调用的函数(类型要一致)*/voidvisit(ElemTypec,ElemTypee)if(c!=0)printf(%dX%d,c,e);/格式化输出多项式每一项/*多项式相加，原理：归并*/*参数：两个已经存在的多项式*/*返回值：归并后新的多项式的头结点*/PolynListMergeList(PolynListLa,PolynListLb)PolynListpa,pb,pc,Lc;pa=La-next;pb=Lb-next;Lc=pc=La;/用La的头结点作为Lc的头结点while(pa&pb)if(pa-expnexpn)pc-next=pa;/如果指数不相等，pc指针连上指数小的结点，pc=pa;pa=pa-next;/指向该结点的指针后移elseif(pa-expnpb-expn)pc-next=pb;/pc指针连上指数小的结点，pc=pb;pb=pb-next;/指向该结点的指针后移else/(pa-expn=pb-expn)pa-coef=pa-coef+pb-coef;/指数相等时，系数相加pc-next=pa;pc=pa;pa=pa-next;/两指针都往后移pb=pb-next;pc-next=pa?pa:pb;/插入剩余段returnLc;voidmain()PolynListha,hb,hc;printf(非递减输入多项式ha，);CreatePolyn(ha,5);/正位序输入n个元素的值printf(非递减输入多项式hb，);CreatePolyn(hb,5);/正位序输入n个元素的值printf(多项式ha:);PolynTraverse(ha,visit);printf(n);printf(多项式hb:);PolynTr