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

院 系： 计算机科学学院 专 业： 软件工程 年 级： 2013级 课程名称： 数据结构 ： 宋中山 2015年 12 月 15日 题目 需求分析 问题描述：设计一个一元多项式加法器基本要求： 输入并建立多项式；(2)两个多项式相加；(3)输出多项式：n, c1, e1, c2, e2, …cn , en, 其中，n是多项式项数，ci和ei分别是第 i 项的系数和指数，序列按指数降序排列。(4)计算多项式在x处的值；(5)求多项式的导函数。 概要分析 本程序有五个函数： PolyNode *Input()(输入函数)； PolyNode *Deri(PolyNode *head)（求导函数）； PolyNode * Plus(PolyNode *A,PolyNode *B)（求和函数）； void Output(PolyNode*head)（输出函数）； int main()（主函数） 本程序可使用带有附加头结点的单链表来实现多项式的链表表示，每个链表结点表示多项式的一项，命名为node，它包括两个数据成员：系数coef和指数exp，他们都是公共数据成员，*next为指针域，用链表来表示多项式。适用于不定的多项式，特别是对于项数再运算过程中动态增长的多项式，不存在存储溢出的问题。其次，对于某些零系数项，在执行加法运算后不再是零系数项，这就需要在结果多项式中增添新的项；对于某些非零系数项，在执行加法运算后可能是零系数项，这就需要在结果多项式中删去这些项，利用链表操作，可以简单的修改结点的指针以完成这种插入和删除运算（不像在顺序方式中那样，可能移动大量数据项）运行效率高。 详细设计 （1）主函数： int main() { PolyNode *head_a,*head_b; int choice; head_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; cout ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n; cinchoice; 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);}//求和 else if (choice==4) break; else cout输入错误，重新输入：\n; } while(choice!=5); return 0; （2）由于此程序是二人合作完成，我在此程序中主要是完成求和和求导函数的 设计。所以下面着重介绍下求和函数和求导函数。 PolyNode *Deri(PolyNode *head)（求导函数）： 流程图如下： 求导函数部分代码： PolyNode *Deri(PolyNode *head) //求导 { PolyNode *p=head; while (p-next!=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)（求和函数）： 流程图如下： 本函数用于对多项式进行加法计算，需要运用存有两个多项式的头指针，前一头指针可是前一计算的计算结果，也可是调用输入函数，后一