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

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

2、：Windows, UNIX, LinUX等不同平台下的 ViSUal C+硬件环境：512MB内存,80Gb硬盘,Pentium4 CPU,CRT显示器。11v1.0可编辑可修改二、概要分析本程序有五个函数：PolyNode *lnput（）（输入函数）；PolyNode *Deri（PolyNode *head） （求导函数）；PolyNode * PIUS（PolyNode *A,PolyNode *B）（求和函数）；void OUtPUt（PolyNode*head）（输出函数）；int mai n（）（主函数）本程序可使用带有附加头结点的单链表来实现多项式的链表表示，每个链表结点表示

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

4、PolyNode *head_a,*head_b;int choice;head_a=new PolyNode;head_a->n ext=NULL;doSyStem("cls"); 入公式n"cout<<"2.求 导|n"cout<<"3.两式求和n"cout<<"4.退出程序|n"cin> >choice;if(ChOiCe=1) head_a= In put();(ChOiCe=2)head_a=Deri(head_a);elseif33v1.0

5、可编辑可修改44rrPolyNode_>v1.0可编辑可修改56PolyNode丄Sta建立链表head, p=head,两头指针 A将B接到P后面合并相同系数相同4A、B均后指Y将A的当前接点接到将B的当前接点接到.O0： n"v1.0可编辑可修改67head=new PoIyNode; /p=head;P->n ext=NULL;for (;)cin> >c>>e;if(c=0&&e=0) break;if(c=0) Con ti nue; / if(head-> next=NULL) 建立头接点结束输入从新输入，不保存/

6、输入第一个接点p->n ext =new PoIyNode;P=P->n ext;p->coef=c,p->exp=e;p-> next=NULL;Con ti nue;p=head;WhiIe(P->n ext!=NULL && e<=p->n ext->exp) P=P->n ext;于P的下一个接点，P向后指if (e=p->exp) p->coef+=c;C On ti nu e;去，继续循环q=new PoIyNode;q->coef=c,q->exp=e;if (p-> nex

7、t!=NULL&&e>p-> next->exp)的指数小于输入的指数，插入到 P的当前接点之后r=p->n ext;/如果输入的指数小/如果相等，直接加上/如果P的后继接点p->n ext=q;v1.0可编辑可修改q->n ext=r;Con ti nue;p->next=q;ZZ如果输入的值小于所有接点，接在最后一个接点之后P=P->n ext; p->n ext=NULL;retur n head;输出函数void Output(PoIyNodeFead) ZZ输出PoIyNode*p;p=head->n ext

8、;if(p=NULL) cout<<"当前没有公式或计算结果为0,请选1输入！ ！ n" return;if(p!=NULL)cout<<"计算结果：n"cout<<p->coef<<"X"<<p->exp;P=P->n ext;WhiIe(P!=NULL)cout<<"+"<<p->coef<<"X"<<p->exp;P=P->n ext;cout&l

9、t;<e ndl;cout<<"如果想重新输入公式，请选1输入！ ！ ！ nn"78v1.0可编辑可修改四、调试分析与操作说明口1刈(1)当程序运行时，进入主界面。如图：武"l>b(Allll÷exe"当前役有公式或计算结杲为/请选1输入I I I式寻和序 公1 人 I S H EJZ此时输入1-4选择操作(2)输入1后按回车出现:88v1.0可编辑可修改N "LDebiigVlllexe'BB当器!殳有公式益计翼结果为缶-式导和序公1入式岀嬰两退 12 3 4SrMli'S系数2扌旨数2系数日

10、拒鈿a H：输入1 2 3 4 5 6 0 0后按回车之后会出现界面:(3) 求导：输入2求导后按回车会出现结果:99v1.0可编辑可修改结果正确。(4) 求和：如果进入图后输入 3后按回车会出现界面:Gn "tbugVlll-exe"5Xr6*3X4*lX2S请选1输入I丨！式导和序公 J入式岀懐两退 -12 3 4参鏗案鼾招热系数2指数2系数H指数H图求和界面输入 2 2 4 4 6 6 0 0后结果会出来：1011v1.0可编辑可修改图求和结果结果正确。此系统在得到计算结果后可以直接用计算的结果进行下一步计算，如果不想用当前的结果，也可按“ 1”重新输入公式进行下一步计算五、心得体会经过这学期的