一元稀疏多项式计算器.docx

《一元稀疏多项式计算器.docx》由会员分享，可在线阅读，更多相关《一元稀疏多项式计算器.docx（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

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

4、d_a=new PolyNode;head_a-next=NULL;do system(cls);/清屏函数 Output(head_a); cout _n; cout|-1.输入公式-|n; cout|-2.求 导-|n; cout|-3.两式求与-|n; cout|-4.退出程序-|n; coutchoice; if (choice=1) head_a=Input(); else if (choice=2) head_a=Deri(head_a); /求导 else if (choice=3) head_b=Input();head_a=Plus(head_a,head_b);/求与 el

5、se if (choice=4) break; else coutnext!=NULL)if(p-next-exp=0) p-next=NULL; /指数为零返回else p-next-coef*=p-next-exp; /系数乘以指数p-next-exp-; /指数减一p=p-next;return head;用于对输入的多项式进行求导，求导在链表内进行计算，即运算完成链表的值改变，返回头指针。PolyNode * Plus(PolyNode *A,PolyNode *B)（求与函数）：流程图如下：startNYNYNYYNNYNYNY建立链表head，p=head，两头指针A、B均指向各自

6、的nextA、 B为空A的指数大于B的指数A、B的系数互为倒数AB指数相等B为空A为空p-next=NULL将A的当前接点接到新链表后面，A后指A、B均后指将B接到p后面合并相同系数相同项，连接到新链表后面将A接到p后面将B的当前接点接到新链表后面，B后指如果AB都为空返回头指针ENDPolyNode*Plus(PolyNode*A,PolyNode *B)本函数用于对多项式进行加法计算，需要运用存有两个多项式的头指针，前一头指针可是前一计算的计算结果，也可是调用输入函数，后一头指针是调用输入函数输入的多项式的头接点。经过计算得到一个新的链表，函数返回链表的头指针。求与函数部分代码PolyNo

7、de * Plus(PolyNode *A,PolyNode *B)/相加PolyNode *head,*p;head=new PolyNode;p=head;A=A-next;B=B-next; while(A!=NULL|B!=NULL)if(A=NULL) p-next=B; break; /如果A空，把B后面的所有接点接到p之后if(B=NULL) p-next=A; break; /如果B空，把A后面的所有接点接到p之后 if(A-exp=B-exp) /如果两指数数相等，相加if(A-coef+B-coef!=0) p-next=new PolyNode; p=p-next; p-

8、exp=A-exp; p-coef=A-coef+B-coef;A=A-next;B=B-next; continue; /如果两系数互为倒数，不保存，后指，继续循环if(A-exp B-exp) /A的指数大于B的指数p-next=new PolyNode;p=p-next;p-exp=A-exp;p-coef=A-coef;A=A-next; continue; /将A的当前接点接到新链表后面，A后指p-next=new PolyNode;p=p-next;p-exp=B-exp;p-coef=B-coef;B=B-next; /将B的当前接点接到新链表后面，B后指if (A=NULL&B

9、=NULL) /如果A B 都为空p-next=NULL;return head; /返回头指针（3）其他函数（同组的成员设计）#include #include using namespace std;typedef struct node float coef; /系数 int exp; /指数 struct node *next; /指针域 指向下一个系数不为0的子项 PolyNode;PolyNode *Input() /输入函数float c; /系数域int e; /指数域PolyNode *p,*q,*r,*head;cout请输入多项式:n;coutnext=NULL;for

10、(;)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 (e=p-exp) p-coef+=c;continue;/如果相等，直接加上去，继续循环q=new PolyNode;q-coef=c,q-ex

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

12、exp;p=p-next;while(p!=NULL)cout+coefXexp;p=p-next; coutendl;cout如果想重新输入公式，请选1输入！nn;四、 调试分析与操作说明（1）当程序运行时，进入主界面。如图：此时输入1-4选择操作（2）输入1后按回车出现：输入1 2 3 4 5 6 0 0后按回车之后 会出现界面：（3）求导：输入2求导后按回车会出现结果：结果正确。（4）求与：如果进入图4.3后输入3后按回车会出现界面： 图4.5求与界面输入2 2 4 4 6 6 0 0 后结果会出来： 图4.6 求与结果结果正确。此系统在得到计算结果后可以直接用计算的结果进行下一步计算，如果不想用当前的结果，也可按“1”重新输入公式进行下一步计算五、 心得体会 经过这学期的学习，我对数据结构了解更深了一点，因为第一次修的时候没有认真的去修，所以没有及格，我很惭愧，所以再一次的修让我觉得我该好好学习这么课程，因为对后面的学习都很有影响。通过做这次实验，我意识到，自己对C语言的掌握稍微熟练了一些； 在写程序的过程中，遇到一些问题是在所难免的，但我相信只要用心去做，就一定会有收获。第 12 页