一元稀疏多项式计算器(数据结构)

1、院系：计算机科学学院专业：软件工程年 级： 20132013 级_课程名称：数据结构姓 名：韦宜（20342034）指导教师：_宋中山_20152015 年 1212 月 1515 日题目：设计一个一元稀疏多项式简单计算器班级：软件工程1301姓名：韦宜 学号：2034完成日期：12月15日、需求分析问题描述：设计一个一元多项式加法器基本要求： 输入并建立多项式；(2)两个多项式相加；(3)输出多项式：n, c1, e1, c2, e2,cn , en,其中，n是多项式项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列。(4)计算多项式在x处的值；(5)求多项式的导函数。软件环境：W

2、indows，UNIX，Linux等不同平台下的Visual C+硬件环境：512MB内存,80Gb硬盘,Pentium4 CPU,CRT显示器。二、概要分析本程序有五个函数：PolyNode *Input（）（输入函数）；PolyNode *Deri（PolyNode *head）（求导函数） ；PolyNode * Plus（PolyNode *A,PolyNode *B）（求和函数） ；void Output（PolyNode*head）（输出函数） ；int main（）（主函数） 本程序可使用带有附加头结点的单链表来实现多项式的链表表示， 每个链表结点表示多项式 的一项，命名为nod

3、e,它包括两个数据成员：系数coef和指数exp，他们都是公共数据成员，*next为指针域，用链表来表示多项式。适用于不定的多项式，特别是对于项数再运算 过程中动态增长的多项式,不存在存储溢出的问题。其次,对于某些零系数项,在执行加法 运算后不再是零系数项, 这就需要在结果多项式中增添新的项； 对于某些非零系数项, 在执 行加法运算后可能是零系数项, 这就需要在结果多项式中删去这些项, 利用链表操作, 可以 简单的修改结点的指针以完成这种插入和删除运算 （不像在顺序方式中那样, 可能移动大量 数据项）运行效率高。三、详细设计(1)主函数：int main()PolyNode *head_a,*

4、head_b;int choice;head_a=new PolyNode;head_a-next=NULL; dosystem(cls);入公式 -|n;cout|- -2.求导- |ncout|- -3.两式求和 - |ncout|- -4.退出程序 - |ncoutchoice;if (choice=1) head_a=Input(); else if(choice=2)head_a=Deri(head_a);PolyNode* Mul(PolyNode*A,polyNode *B)-4建立以 hSad2 为头指针的空链表，p=head2q=B 的第一个接点q!=NULLYq 指冋旳接点

5、与 A 指向的接 点相乘，结果保存到 head：后面，q 指向后一接点.00：n;head=new PolyNode; /建立头接点p=head;p-next=NULL;for (;)cince; if(c=0&e=0)break; / if(c=0) continue; /if(head-next=NULL) /p-next=new PolyNode; p=p-next;p-coef=c,p-exp=e; p-next=NULL; continue;p=head;while(p-next!=NULL & enext-exp) p=p-next;于p的下一个接点，p向后指if

6、(e=p-exp) p-coef+=c;continue;去，继续循环q=new PolyNode;q-coef=c,q-exp=e;if (p-next!=NULL&ep-next-exp)的指数小于输入的指数，插入到p的当前接点之后r=p-next;p-next=q;q-next=r;continue;所有接点，接在最后一个接点之后p=p-next; p-next=NULL;return head;输出函数void Output(PolyNode*head) /输出PolyNode*p; p=head-next;if(p=NULL) cout当前没有公式或计算结果为0，请选1输入！

7、n; return;if(p!=NULL)cout计算结果：n;coutcoefXexp;p=p-next;while(p!=NULL)cout+coefXexp; p=p-next;coutendl;coutnext=q;/如果输入的值小于结束输入 从新输入，不保存 输入第一个接点/如果输入的指数小/如果相等， 直接加上/如果p的后继接点四、调试分析与操作说明（1）当程序运行时，进入主界面。如图：此时输入1-4选择操作（2）输入1后按回车出现：输入1 2 3 4 5 6 0 0后按回车之后 会出现界面：3）求导：输入2求导后按回车会出现结果：结果正确。（4）求和：如果进入图后输入3后按回车会出现界面：图求和界面输入2 2 4 4 6 6 0 0后结果会出来：图 求和结果结果正确。 此系统在得到计算结果后可以直接用计算的结果进行下一步计算，前的结果，也可按“1”重新输入公式进行下一步计算五、心得体会经过这学期的学习， 我对数据结构了解更深了一点， 因为第一次修的时候没有认真的去 修，所以没有及格， 我很惭愧，