一元稀疏多项式的加法运算(数据结构实习).doc

《一元稀疏多项式的加法运算(数据结构实习).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实习一线性表、栈和队列及其应用——一元稀疏多项式的加法运算【问题描述】设计一个实现一元稀疏多项式相加运算的演示程序。【基本要求】（1）输入并建立两个多项式；（2）多项式a与b相加，建立和多项式c；（3）输出多项式a,b,c。输出格式：比如多项式a为：A(x)=c1xe1+c2xe2+…+cmxem，其中，ci和ei分别为第i项的系数和指数，且各项按指数的升幂排列，即0≤e1＜e2＜…＜em。多项式b,c类似输出。【测试数据】（1）(1+x+x2+x3+x4+x5)+(-x3-x4)=(1+x+x2+x5)（2）(x+x100)+(x100+x200)=(x+2x100+x2

2、00)（3）(2x+5x8-3x11)+(7-5x8+11x9)=(7+2x+11x9-3x11)一．需求分析1.输入的形式和输入值的范围：输入是从键盘输入的，输入的内容为多项式的系数和指数，其中多项式的每一项分别以一个系数和指数的形式输入，不带未知数X，系数为任意的实数，指数为任意的整数。要结束该多项式的输入时，输入的指数和系数都为0.2.输出的形式从屏幕输出，显示用户输入的多项式，并显示多项式加减以后的多项式的值，并且多项式中将未知数X表示了出来.形式为：+c1X^e1+c2X^e2+…+ciX^ei+…(ci和ei分别是第i项的系数和指数，序列按指数升序排列。)当多项

3、式的某一项的系数为+1或者-1时侧该项多项式的输出形式为X^ei或-X^ei；当该项的系数为正时输出+ciX^ei,当为负数时则输出ciX^ei3.程序所能达到的功能输入并建立多项式，实现一元稀疏多项式的相加并输出。4.注意：所有多项式都必须以指数升密形式输入。5.测试数据为（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）.

4、主要算法基本思路首先定义一个多项式的结构体，存放多项式每一项的系数和指数以及next指针；然后定义两个指针，第一个指针指向第一个多项式，第二个指针指向第二个多项式。然后比较两个多项式第一项的指数的大小，如果两个多项式的指数相同，则将他们的系数相加，指数不变；如果不同则比较他们指数的大小，并将指数小的放在第一项。然后指向指数小的那一项的指针后移，它的指数去和刚才必然的那一项的指向相比较……直至两个多项式相加完。其中如果某二项的系数相加后为0，则该项不输出。相加时的程序如下：pnode*add(pnode*heada,pnode*headb)//多项式相加//{pnode*he

5、adc,*p,*q,*s,*r;floatx;p=heada;//p指针指向第一个多项式的第一项//q=headb;//q指针指向第二个多项式的第一项//headc=(pnode*)malloc(sizeof(pnode));//为两式相加的结果c申请内存//r=headc;//r指向结果//while(p!=NULL&&q!=NULL)//判断两个式子都合法//{if(p->e==q->e)//指数相同时系数相加//{x=p->c+q->c;if(x!=0){s=(pnode*)malloc(sizeof(pnode));s->c=x;s->e=p->e;r->next=

6、s;r=s;}q=q->next;p=p->next;//指向多项式的下一项//}elseif(p->e>q->e)//多项式按升幂排序//{s=(pnode*)malloc(sizeof(pnode));s->c=q->c;s->e=q->e;r->next=s;r=s;q=q->next;}else{s=(pnode*)malloc(sizeof(pnode));s->c=p->c;s->e=p->e;r->next=s;r=s;p=p->next;}}while(p!=NULL)//第一个式子不为0时的相加法则//{s=(pnode*)malloc(sizeof(pn

7、ode));s->c=p->c;s->e=p->e;r->next=s;r=s;p=p->next;}while(q!=NULL)//第二个式子不为0的相加法则//{s=(pnode*)malloc(sizeof(pnode));s->c=q->c;s->e=q->e;r->next=s;r=s;q=q->next;}r->next=NULL;headc=headc->next;//c的指向依次指向下一项//returnheadc;//返回两式相加的结果//}2.设计表示（1）函数调用关系图main->create