一元多项式相加问题实验报告

1、一元多项式相加问题一问题描述设计算法实现一元多项式的简单运算。二数据结构设计分析任意一元多项式的描述方法可知，一个一元多项式的每一个子项都由“系数-指数”两部分组成，所以可以将它抽象成一个由“系数-指数对”构成的线性表。基于这样的分析，可以采用一个带有头结点的单链表来表示一个一元多项式。具体数据类型定义为：typedef struct nodefloat cofe; /系数域int exp; /指数域struct node* next; /指针域 指向下一个子项*polynode,poly;Polynode head_a,head_b,head_c;这三个指针分别作为链表A，B和C的头指针。三

2、功能设计1.输入并建立多项式的功能模块此模块要求按照“系数-指数对”的输入格式输入各个子项，输入一个子项，通过遍历链表比较指数的大小，将新结点插在合适的位置，使多项式的指数按递增的顺序存储。当遇到输入结束标志是停止输入，而转去执行程序下面的部分。具体函数构造为：polynode creat_polynode()polynode A ,p,q,s; /建立这种类型的头指针，尾指针，遍历指针和动态指针float a;int b;A=new poly;A-next=NULL;q=A;p=A;cina;cinb;while(a!=0|b!=0)s=new poly;s-cofe=a;s-exp=b;w

3、hile(q-next)if(q-next-expnext; /遍历链表，若指数大于原链表指数，指针后移一个elses-next=q-next;q-next=s;break; /若不是，将结点插入指针后面if(q-next=NULL)s-next=p-next;p-next=s;p=s; /q遍历到链表尾仍未插入，将结点插入最后，改变尾指针使其指向新结点q=A; /让q返回头指针处，以便下一次遍历链表cina;cinb;if(p!=NULL)p-next=NULL; return A;2.多项式相加的功能模块此模块根据在1中建立的两个多项式进行相加运算，并存放在以C为头指针的一个新链表中。可以

4、采用如下方法进行设计：设指针p,q,r分别指向描述多项式的链表A,B,C头部，比较p-exp与q-exp；若p-exp小，则做如下操作：while(p!=NULL&q!=NULL) /在两个指针不为空的情况下r=new poly;if(p-expexp)r-cofe=p-cofe;if(r-cofe=0)delete r;p=p-next;continue; /若r指向的系数为，则p前进，释放r并强制执行下一次循环r-exp=p-exp;r-next=s-next;s-next=r;s=r;p=p-next; /p指针指向的指数小，将此结点赋给r，p指针前进 若p-exp=q-exp，则：el

5、seif(p-exp=q-exp)r-cofe=p-cofe+q-cofe; /若两指针指数部分相等，则系数相加赋给rif(r-cofe=0)delete r;p=p-next;q=q-next;continue; r-exp=p-exp;r-next=s-next;s-next=r;s=r;p=p-next;q=q-next; /两指针均前进若p-expq-exp,则：elseif(p-expq-exp)r-cofe=q-cofe;if(r-cofe=0)delete r;q=q-next;continue;r-exp=q-exp;r-next=s-next;s-next=r;s=r;q=q

6、-next;在两个指针中有一个为空以后，可以进行如下操作将多项式中剩余项赋到C中：while(p=NULL&q!=NULL)r=new poly;r-cofe=q-cofe;r-exp=q-exp;r-next=s-next;s-next=r;s=r;q=q-next; /若有一个多项式已经结束则把另一个多项式的值赋给新多项式while(q=NULL&p!=NULL)r=new poly;r-cofe=p-cofe;r-exp=p-exp;r-next=s-next;s-next=r;s=r;p=p-next;if(r!=NULL)r-next=NULL;3.多项式显示的功能模块此模块用于多项

7、的显示，用“系数-指数对”的形式表示表达式：cout(cofe,expnext;四界面设计在输入多项式时，界面提示输入（0 0）表示结束输入。五编码实现/ 9u.cpp : 定义控制台应用程序的入口点。/#include stdafx.h#includeusing namespace std;typedef struct nodefloat cofe;int exp;struct node* next;*polynode,poly;polynode head_c;polynode creat_polynode()polynode A ,p,q,s; /建立这种类型的头指针，尾指针，遍历指针和动

8、态指针float a;int b;A=new poly;A-next=NULL;q=A;p=A;cina;cinb;while(a!=0|b!=0)s=new poly;s-cofe=a;s-exp=b;while(q-next)if(q-next-expnext; /遍历链表，若指数大于原链表指数，指针后移一个else if(q-next-exp=b)q-next-cofe=s-cofe+q-next-cofe;delete s;break;elses-next=q-next;q-next=s;break; /若不是，将结点插入指针后面if(q-next=NULL)s-next=p-next

9、;p-next=s;p=s; /q遍历到链表尾仍未插入，将结点插入最后，改变尾指针使其指向新结点q=A; /让q返回头指针处，以便下一次遍历链表cina;cinb;if(p!=NULL)p-next=NULL; return A;polynode creat_polynode3(polynode head_a,polynode head_b)polynode p,q,r,s;p=head_a-next;q=head_b-next;head_c=new poly;head_c-next =NULL;s=head_c;while(p!=NULL&q!=NULL) /在两个指针不为空的情况下r=ne

10、w poly;if(p-expexp)r-cofe=p-cofe;if(r-cofe=0)delete r;p=p-next;continue; /若r指向的系数为，则p前进，释放r并强制执行下一次循环r-exp=p-exp;r-next=s-next;s-next=r;s=r;p=p-next; /p指针指向的指数小，将此结点赋给r，p指针前进 elseif(p-exp=q-exp)r-cofe=p-cofe+q-cofe; /若两指针指数部分相等，则系数相加赋给rif(r-cofe=0)delete r;p=p-next;q=q-next;continue; r-exp=p-exp;r-n

11、ext=s-next;s-next=r;s=r;p=p-next;q=q-next; /两指针均前进elseif(p-expq-exp)r-cofe=q-cofe;if(r-cofe=0)delete r;q=q-next;continue;r-exp=q-exp;r-next=s-next;s-next=r;s=r;q=q-next;while(p=NULL&q!=NULL)r=new poly;r-cofe=q-cofe;r-exp=q-exp;r-next=s-next;s-next=r;s=r;q=q-next; /若有一个多项式已经结束则把另一个多项式的值赋给新多项式while(q=

12、NULL&p!=NULL)r=new poly;r-cofe=p-cofe;r-exp=p-exp;r-next=s-next;s-next=r;s=r;p=p-next;if(r!=NULL)r-next=NULL;return head_c;int main()polynode head_a,head_b;cout请输入第一个多项式(0 0结束输入）:endl;head_a=creat_polynode();cout请输入第二个多项式（结束输入）:next; polynode x,y; x=head_a-next; y=head_b-next; cout; while(x) cout(co

13、fe,expnext; cout; cout+; while(y) cout(cofe,expnext; cout=; if(n=NULL) cout0; while(n)cout(cofe,expnext; coutendl;return 0; 六运行与测试（1）(2x+5x83.1x11)+(75x8+11x9)=(3.1x11+11x9+2x+7)（2）(1+x+x2+x3+x4+x5)+(x3x4)=(1+x+x2+x5)（3）(x+x3)+(xx3)=0（4）(x+x100)+(x100+x200)=(x+2x100+x200)（5）(x+x2+x3)+0=x+x2+x3（6）(75x8+11x9)+ (2x+5x83.1x11)= (3.1x11+11x9+2x+7)（7）(x3x4)+ (1+x+x2+x3+x4+x5)= (1+x+x2+x5)（8）(xx3)+ (x+x3)=0（9）(x100+x200)+ (x+x100)= (x+2x100+x200)（10）0+(x+x2+x3)= (x+x2+x3)（11）(2x+5x83.1x11)+(75x8+11x9)=(3.1x11+11x9+2x+7)当不按递增顺序输入时，结果仍正确（12）（2x+2x）+0=4