一元稀疏多项式的加法运算.doc

《一元稀疏多项式的加法运算.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、一元稀疏多项式的加法运算一、需求分析1、要求用带头结点的单链表存储两个多项式，然后进行多项式加法运算，存入另一个单链表中。2、从键盘输入多项式a的项数，然后分别输入每项的系数和指数；类此输入多项式b。3、测试数据：（1）、(1+x+x2+x3+x4+x5)+(-x3-x4)=(1+x+x2+x5)（2）、(x+x100)+(x100+x200)=(x+2x100+x200)（3）、(2x+5x8-3x11)+(7-5x8+11x9)=(7+2x+11x9-3x11)二、设计1、设计思想（1）、存储结构：带头结点的单链表（2）、主要算法基本思想先输入多项式的项数j，建立一个循环，分别进行链表的

2、插入操作，插入时就是建立空结点存入系数和指数后再插入链表中。在插入的同时要比较与原链表中指数项的大小，从而建立由低次方到高次方的存储链表。在多项式相加时，将多项式a先存入多项式c中，此时c中的指数是升序排列，再将b中系数与指数存入，存入的方法是：指数比较寻找插入结点，指数相等时，进行系数相加操作，其他是建立一个空结点，存入b的系数与指数载插入c中。至于输入过程，多项式a、b、c均可输出，由于存储的按指数升序存的，所以不必进行查找了，只需要按一个个结点顺序输出即可。#include#include#includetypedefstruc

3、t{floatcoef;intexpn;}count;typedefstructNode{floatcoef;//系数intexpn;//指数structNode*next;}LinkList;voidListInitiate(LinkList**head)//链表初始化{if((*head=(LinkList*)malloc(sizeof(LinkList)))==NULL)exit(0);(*head)->next=NULL;}voidListInsert(LinkList*head,countL)//链表插入操作{LinkList*p,*q;p=head;while(p->next!=

4、NULL)//从系数由小到大排序的角度寻找插入结点{if(p->next->expn>L.expn)break;p=p->next;}if((q=(LinkList*)malloc(sizeof(LinkList)))==NULL)exit(0);q->coef=L.coef;q->expn=L.expn;q->next=p->next;p->next=q;}intprint(LinkList*head)//输出{LinkList*p;p=head->next;if(p==NULL)//多项式为零时直接输出{printf("0");exit(0);}while(p->coef==1&&p

5、->expn>0)//指数不为零时系数为1时的输出{printf("x^%d",p->expn);p=p->next;if(p==NULL)return0;elseprintf("+");}while(p->next){printf("%gx^%d",p->coef,p->expn);p=p->next;if(p->coef>0)printf("+");}printf("%gx^%d",p->coef,p->expn);return1;}voidAdd(LinkList*a,LinkList*b,LinkList*c)//多项式a、b相加等于多项式c{LinkList*p,*q,*s,*k;

6、s=c;p=a->next;while(p!=NULL)//先将a存入c中{if((q=(LinkList*)malloc(sizeof(LinkList)))==NULL)exit(0);q->coef=p->coef;q->expn=p->expn;q->next=NULL;c->next=q;c=c->next;p=p->next;}c=s;p=b->next;while(p!=NULL)//将b存入c中{while((c->next!=NULL)&&(p->expn)>((c->next)->expn))//寻找插入结点{c=c->next;}if(c->next==NULL)//从

7、最后插入{if((q=(LinkList*)malloc(sizeof(LinkList)))==NULL)exit(0);q->coef=p->coef;q->expn=p->expn;q->next=c->next;c->next=q;}elseif(p->expn==c->next->expn)//指数相等时系数相加{s=c;c=c->next;c->coef=c->coef+p->coef;if(c-