一元稀疏多项式计算器实现(完整实现版-详细源码).doc

1.5一元稀疏多项式计算器实习报告一、 需求分析 1输入并建立多项式；2输出多项式，输出形式为整数序列：n，c1，e1，c2，e2，cn，en，其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列；3多项式a和b相加，建立多项式ab；4多项式a和b相减，建立多项式ab；5多项式a和b相乘，建立多项式ab；6计算多项式在x处的值；7求多项式P的导函数P；8.多项式的输出形式为类数学表达式；9.做出计算器的仿真界面；10. 测试数据：（1） (2x+5x8-3.1x11)+(7-5x8+11x9)=(-3.1x11+11x9+2x+7)（2） (6x-3-x+4.4x2-1.2x9+1.2x9)-(-6x-3+5.4x2-x2+7.8x15 )=(-7.8x15-1.2x9+12x-3-x);（3）(1+x+x2+x3+x4+x5)+(-x3-x4)=(1+x+x2+x5);（4）(x+x3)+(-x-x3)=0（5）(x+x100)+(x100+x200)=(x+2x100+x200)（6）(x+x2+x3)+0=x+x2+x3（7）互换上述测试数据中的前后两个多项式二、 概要设计1. 链表的抽象数据类型定义为：ADT LinkList 数据对象：D ai | aiElemSet, i=1,2,.,n, n0 数据关系：R1 |ai-1, aiD, i=2,.,n 基本操作： InitList(&L) 操作结果：构造一个空的线性表L。 DestroyList(&L) 初始条件：线性表L已存在。 操作结果：销毁线性表L。ClearList(*L) 初始条件：线性表L已存在。 操作结果：将线性表L重置为空表。 LocateElem(L, e, cmp() 初始条件：线性表L已存在，compare()是元素判定函数。 操作结果：返回L中第1个与e满足关系cmp()的元素的位序。 若这样的元素不存在，则返回值为0。 SetCurElem(&p, e) 初始条件：线性表L已存在，且非空。操作结果：用元数e更新p所指结点中元数的值。GetCurElem(p)初始条件：线性表L已存在，且非空。操作结果：返回p所指结点中数据元数的值。InsFirst (&L, h, s) 初始条件：线性表L已存在，h结点在L中。 操作结果：在L的s所指结点插入在h结点之后，L的长度加1。 DelFirst (&L, h, q) 初始条件：线性表L已存在且非空，q结点在L中且不是尾结点 操作结果：删除链表L中的h结点之后的结点q，L的长度减1。 MakeNode(&p, e)操作结果：创建了一个结点p，其data部分为e。FreeNode(&p)初始条件：结点p存在且非空。操作结果：释放结点p空间。Append(LinkList &L,Link s)初始条件：线性表L已存在。操作结果：s及s以后的结点链接到了原L之后，L的长度增加链上的结点数。ListEmpty(L)初始条件：线性表L已存在。操作结果：若线性链表L为空表，则返回TRUE,否则返回FALSE。GetHead(L)初始条件：线性表L已存在。操作结果：返回线性链表L中头结点的位置。NextPos(L, p)初始条件：线性表L已存在。操作结果：返回p所指结点的直接后继的位置，若没后继，则返回NULL。int cmp(a, b)初始条件：存在两个元数。操作结果：比较a，b的数值，分别返回-1，0，1。 ADT LinkList2.一元多项式的抽象数据类型定义为：ADT Polynomial数据对象：D ai | aiTermSet, i=1,2,.,m, m0 TermSet中的每个元素包含一个表示系数的实数和表示指数的整数数据关系：R1 |ai-1, aiD, 且ai-1中的指数值next=L.tail-next=NULL; return OK;/ 返回线性表L中头结点的位置。Position GetHead(LinkList &L);/已知p指向线性链表L中的一个结点，返回p所指结点的直接后驱的位置/若无后继，返回NULLPosition Nextpos(LinkList &L,Link p);/已知p指向线性表L中的一个结点,返回p所指结点中数据元素的值。ElemType GetCurElem(Link p);/已知p指向线性链表L中的一个结点,用e更新p所指结点中数据元素的值。Status SetCurElem(Link &p,float e); /已知h指向线性链表的某个结点,将q所指的结点插入在h之后。Status InsFirst(Link h,Link q); s-next=h-next; h-next=s; L.len+; if(!s-next) L.tail=s; return OK;/已知h指向线性链表的头结点,删除线性链表第一个指结点并以q返回Status DelFirst(Link h,Link &q);/若线性链表L为空,则返回TRUE,否则返回FALSE。Status ListEmpty(LinkList L); if(L.head=L.tail=NULL) return TRUE; else return FALSE;/将指针s所指的一连串结点连接在线性表L的最后一个结点之后,并改变链表L的尾指针指向新的尾结点。Status Append(polynomial &L,Link s); i=0; q=s; while(s) /找到新的tail，计数s长度 p=s; s=s-next; i+; L.tail-next=q; L.tail=p; L.len+=i; return OK;/判断已知链表中，是否存在相同的元素e，若存在返回TURE，且q指示L中第一个与e相同的结点元素；/否则返回FALSE,并q指示L中第一个稍大于e的元素的直接前驱的位置Status LocateElem(LinkList L,ElemType e,Position &q); p=L.head; while(p-next) s=p; p=p-next; m=p-data; if(cmp(e,m )=0) q=p; return TRUE; q=p; return FALSE;/整表删除void ClearList(LinkList &L); if(L.head!=L.tail) p=q=L.head-next; L.head-next=NULL; while(p!=L.tail) p=q-next; free(q); q=p; free(q); L.tail=L.head; L.len=0; return OK;/依a的指数值）b的指数数值，分别返回-1，0，+1int cmp(term a, term b) ; if(a.expnb.expn) return 1;3.基于多项式的操作（部分伪码如下）/输入m项的系数和指数，建立表示一元多项式的有序链表Pvoid CreatPolyn(polynomial &p,int m);InitList(p);h=GetHead(p);e.coef=0.0;e.expn=-1;SetCurElem(h,e);for(int i=1;i=m;i+) cout请输入第ie.coefe.expn; coutdata.coef+=e.coef; +c; m=m-c;/销毁一元多项式Pvoid DestroyPolyn(polynomial &p); while(p.head -next!=NULL) k=p.head; p.head =p.head -next; free(k); free(&p);/打印输出一元多项式Pvoid PrintPolyn(polynomial p);ha=GetHead(p);coutm, ; for(int i=1;i=m;i+) qa=NextPos(p,ha); e=GetCurElem(qa); coute.coef,e.expn, ; ha=qa; coutnext; hc=GetHead(Pc); while(qa) a=GetCurElem(qa); qb=GetHead(Pb); qb=qb-next; while(qb) b=GetCurElem(qb); c.coef=a.coef*b.coef; c.expn=a.expn+b.expn; MakeNode(qc,c); InsFirst(Pc,hc,qc); hc=NextPos(Pc,hc); qc=NextPos(Pc,qc); qb=qb-next; qa=qa-next; DestroyPolyn(Pb); ClearList(Pa); Pa.head=Pc.head; Pa.tail=Pc.tail; Pa.len=Pc.len;/计算多项式在x处的值double Evaluation(double x, polynomial p);/计算多项式P的导函数Pvoid Derivative( polynomial &p ); InitList(Pb); qa=GetHead(Pa); qa=qa-next; hb=GetHead(Pb); while(qa) a=GetCurElem(qa); b.coef=a.coef*a.expn; b.expn=a.expn-1; MakeNode(qb,b); InsFirst(Pb,hb,qb); hb=NextPos(Pb,hb); qb=NextPos(Pb,qb); qa=qa-next; qb=NULL; ClearList(Pa); Pa.head=Pb.head; Pa.tail=Pb.tail; Pa.len=Pb.len;4.主函数和其他函数的伪码算法int main() Initialization();ReadCommand(cmd);while (cmd != q & cmd != Q)Interpret(cmd);display();ReadCommand(cmd); return 0;void Initialization()pre_cmd = ;cmd = ;InitList(La);InitList(Lb);void display()system(cls); /清屏在屏幕上方显示操作命令清单：CreatePolynomial_a -1 CreatePolynomial_b -2 a+b - a-b a*b -* Derivation of a -d Calculate a in x -c Quit -q 在屏幕下方显示操作命令提示框：Enter a operation code(1,2,+,_,*,c,d OR q): ;void ReadCommand(char &cmd)/读入操作命令符 显示检入操作命令符的提示信息；dodisplay();cin cmd; while (!strchr(cmdsets, cmd);void Interpret(char cmd) /解释执行操作命令cmdswitch (cmd)case 1:ClearList(La);cout n; cout endl;CreatPolyn(La, n);/输入多项式SortPolyn(La);break;case 2:ClearList(Lb);cout endl m; cout endl;CreatPolyn(Lb, m);/输入多项式SortPolyn(Lb);break;case +:cout endl 两多项式相加的结果：;AddPolyn(La, Lb);PrintPolyn(La, La.len);Expression(La,La.len);getchar();getchar();break;case -:cout endl 两多项式相减的结果：;SubtractPolyn(La, Lb);PrintPolyn(La, La.len);Expression(La,La.len);getchar();getchar();break;case *:cout endl 两多项式相乘的结果：;MultiplyPolyn(La, Lb);PrintPolyn(La, La.len);Expression(La,La.len);getchar();getchar();break;case c:case C:cout 请输入x的值 x;cout 多项式a在 x 处的值为 CalPolyn(La, x);getchar();getchar();break;case d:case D:DerivPolyn(La);cout 求导结果为;PrintPolyn(La, La.len);Expression(La,La.len);getchar();getchar();default:cout 输入错误 endl; 5.函数的调用关系图反映了演示程序的层次结构四、 调试分析1. 一开始写求导部分代码时没有考虑常数项求导变零的情况，结果输出后常数项以系数为0指数为-1的形式输出，不符合规范。调试后加入if判断语句让常数项求导之后的结果不显示出来。2. 加减法操作出现多项式Pb若有几项的指数比Pa中任一项都小，则那几项在运算过后被漏掉的现象。调试后发现在把Pb剩余结点链接到Pa时出了问题，把Pb的数据链上去了之后没有把Pb的长度减掉，而且Pb的头指针也不见了，所以后面读取的时候会出错。修改了小函数Append以及加减法部分代码之后，解决了这个问题。3. 类数学表达式输出时会出现“1x”以及“x1”现象。通过加上if语句区别处理后解决的问题。4. 本程序的模块划分比较合理，且尽可能将指针的操作封装在结点和链表两个模块中，致使链表模块的调试比较顺利。5. 算法的时空分析（1） 由于链表采用带头结点的单链表，并增设尾指针和表的长度两个标识，各种操作的算法时间复杂度比较合理。InitList,ListEmpty等函数都是O(1)，Append，LocateElem及确定链表中间结点的位置等则是O（n）的，n为链表长度。（2） 基于单链表实现的一元多项式的各种运算和操作的时间复杂度：加法：O(maxPa.len,Pb.len)减法：O(maxPa.len,Pb.len)乘法：O(Pa.len*Pb.len)求导：O(n)求x处的值：O(n)输出类数学表达式：O(n) n为链表长度。6.本实习作业采用数据抽象的程序设计方法，讲程序划分为四个层次的结构：主程序模块、一元多项式单元模块、链表单元模块、结点结构单元模块，使得设计时思路清晰，实现时调试顺利，各模块具有较好的可重用性，确实得到了一次良好的程序设计训练。五、 用户手册1. 本程序的运行环境为DOS操作系统，执行文件为：POLYNOMIAL.exe。2. 进入演示程序后即显示文本方式的用户界面：操作提示信息显示多项式键入操作命令符操作命令清单3. 进入“构造多项式a（CreatePolynomial_a）”和构造多项式b（CreatePolynomial_b）”的命令后，即提示键入多项式项数、系数、指数，结束符为“回车符”。4. 接受其他命令后即执行相应运算和显示相应结果。六、 测试结果七、 附录源程序文件名清单：Base.h /宏定义说明LNode.h /链表实现单元Polynomial.h /一元多项式实现单元main.cpp /主程序