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

1.5一元稀疏多项式计算器实习报告一、需求分析1．输入并建立多项式；2．输出多项式，输出形式为整数序列：n，c1，e1，c2，e2，……，cn，en，其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列；3．多项式a和b相加，建立多项式a＋b；4．多项式a和b相减，建立多项式a—b；5．多项式a和b相乘，建立多项式a×b；6．计算多项式在x处的值；7．求多项式P的导函数P'；8.多项式的输出形式为类数学表达式；9.做出计算器的仿真界面；10.测试数据：（1）(2x+5x^8-3.1x^11)+(7-5x^8+11x^9)=(-3.1x^11+11x^9+2x+7)（2）(6x^-3-x+4.4x^2-1.2x^9+1.2x^9)-(-6x^-3+5.4x^2-x^2+7.8x^15)=(-7.8x^15-1.2x^9+12x^-3-x);（3）(1+x+x^2+x^3+x^4+x^5)+(-x^3-x^4)=(1+x+x^2+x^5);（4）(x+x^3)+(-x-x^3)=0（5）(x+x^100)+(x^100+x^200)=(x+2x^100+x^200)（6）(x+x^2+x^3)+0=x+x^2+x^3（7）互换上述测试数据中的前后两个多项式二、概要设计1.链表的抽象数据类型定义为：ADTLinkList{数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{ai-1,ai|ai-1,ai∈D,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,Links)初始条件：线性表L已存在。操作结果：s及s以后的结点链接到了原L之后，L的长度增加链上的结点数。ListEmpty(L)初始条件：线性表L已存在。操作结果：若线性链表L为空表，则返回TRUE,否则返回FALSE。GetHead(L)初始条件：线性表L已存在。操作结果：返回线性链表L中头结点的位置。NextPos(L,p)初始条件：线性表L已存在。操作结果：返回p所指结点的直接后继的位置，若没后继，则返回NULL。intcmp(a,b)初始条件：存在两个元数。操作结果：比较a，b的数值，分别返回-1，0，1。}ADTLinkList2.一元多项式的抽象数据类型定义为：ADTPolynomial{数据对象：D＝{ai|ai∈TermSet,i=1,2,...,m,m≥0TermSet中的每个元素包含一个表示系数的实数和表示指数的整数}数据关系：R1＝{ai-1,ai|ai-1,ai∈D,且ai-1中的指数值ai中的指数值，i=2，……，n}基本操作：CreatPolyn（&P，m）操作结果：输入m项的系数和指数，建立一元多项式P。DestroyPolyn（&P）初始条件：一元多项式P已存在。操作结果：销毁一元多项式P。AddPolyn（&Pa，&Pb）初始条件：一元多项式Pa和Pb已存在。操作结果：完成多项式相加运算，即：Pa=Pa+Pb，并销毁一元多项式Pb。SubtractPolyn(&Pa,&Pb)初始条件：一元多项式Pa和Pb已存在。操作结果：完成多项式相减运算，即：Pa=Pa-Pb，并销毁一元多项式Pb。MultiplyPolyn(&Pa,&Pb)初始条件：一元多项式Pa和Pb已存在。操作结果：完成多项式相乘运算，即：Pa=Pa×Pb，并销毁一元多项式Pb。DerivPolyn(&Pa)初始条件：一元多项式Pa已存在。操作结果：多项式求导。CalPolyn(Pa,x)初始条件：一元多项式Pa已存在。操作结果：求多项式在x处的值。PrintPolyn(p,m)初始条件：一元多项式p已存在，且已知多项式项数。操作结果：打印输出一元多项式p的项数、系数和指数。Expression(p,m)初始条件：一元多项式p已存在，且已知多项式项数。操作结果：打印输出一元多项式的类数学表达式。SortPolyn(&p)初始条件：一元多项式p已存在。操作结果：对多项式p进行排序}ADTPolynomial3.本程序包含4个模块：(1)主程序模块：intmain(){初始化；接受命令；while（命令！=推出）{处理命令；接受命令；}return0;}(2)一元多项式单元模块——实现一元多项式的抽象数据类型；（3）链表单元模块——实现链表的抽象数据类型；(4)结点结构单元模块——定义链表的节点结构。各模块之间的调用关系如下：主程序模块一元多项式单元模块链表单元模块结点结构单元模块三、详细设计1.设计好的数据类型：typedefstruct{//项的表示，多项式的项作为Linklist的数据元素floatcoef;//系数intexpn;//指数}term,ElemType;//两个类名：term用于本ADT，ElemType为Linklist的数据对象名typedefstructLNode{//结点类型ElemTypedata;structLNode*next;}*Link,*Position;typedefstruct{//链表类型Linkhead,tail;//分别指向线性链表中的头结点和最后一个结点intlen;//指示线性链表中数据个数}LinkList;typedefLinkListpolynomial;//基于带头结点的线性链表定义的多项式数据类型2.基于链表、结点的操作(部分伪码如下)//分配由p指向值为e的结点,并返回OK,若分配失败,则返回ERROR。StatusMakeNode(Link&p,ElemTypee);//释放p所指结点voidFreeNode(Link&p);//构造一个空的线性链表LStatusInitList(LinkList&L);{L.head=L.tail=(Link)malloc(sizeof(LNode));L.len=0;L.head-next=L.tail-next=NULL;returnOK;}//返回线性表L中头结点的位置。PositionGetHead(LinkList&L);//已知p指向线性链表L中的一个结点，返回p所指结点的直接后驱的位置//若无后继，返回NULLPositionNextpos(LinkList&L,Linkp);//已知p指向线性表L中的一个结点,返回p所指结点中数据元素的值。ElemTypeGetCurElem(Linkp);//已知p指向线性链表L中的一个结点,用e更新p所指结点中数据元素的值。StatusSetCurElem(Link&p,floate);//已知h指向线性链表的某个结点,将q所指的结点插入在h之后。StatusInsFirst(Linkh,Linkq);{s-next=h-next;h-next=s;L.len++;if(!s-next)L.tail=s;returnOK;}//已知h指向线性链表的头结点,删除线性链表第一个指结点并以q返回StatusDelFirst(Linkh,Link&q);//若线性链表L为空,则返回TRUE,否则返回FALSE。StatusListEmpty(LinkListL);{if(L.head==L.tail==NULL)returnTRUE;elsereturnFALSE;}//将指针s所指的一连串结点连接在线性表L的最后一个结点之后,并改变链表L的尾指针指向新的尾结点。StatusAppend(polynomial&L,Links);{i=0;q=s;while(s){//找到新的tail，计数s长度p=s;s=s-next;i++;}L.tail-next=q;L.tail=p;L.len+=i;returnOK;}//判断已知链表中，是否存在相同的元素e，若存在返回TURE，且q指示L中第一个与e相同的结点元素；//否则返回FALSE,并q指示L中第一个稍大于e的元素的直接前驱的位置StatusLocateElem(LinkListL,ElemTypee,Position&q);{p=L.head;while(p-next){s=p;p=p-next;m=p-data;if(cmp(e,m)==0){q=p;returnTRUE;}}q=p;returnFALSE;}//整表删除voidClearList(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;}returnOK;}//依a的指数值（或=）(或）b的指数数值，分别返回-1，0，+1intcmp(terma,termb);{if(a.expnb.expn)return-1;if(a.expn==b.expn)return0;if(a.expnb.expn)return1;}3.基于多项式的操作（部分伪码如下）//输入m项的系数和指数，建立表示一元多项式的有序链表PvoidCreatPolyn(polynomial&p,intm);{InitList(p);h=GetHead(p);e.coef=0.0;e.expn=-1;SetCurElem(h,e);for(inti=1;i=m;i++){cout请输入第i项的系数和指数（按指数降序）：;cine.coefe.expn;coutendl;if(!LocateElem(p,e,q))//当前链表中不存在该指数项if(MakeNode(s,e))InsFirst(p,q,s);//生成节点并插入链表elsereturn;else{q-data.coef+=e.coef;++c;}}m=m-c;}//销毁一元多项式PvoidDestroyPolyn(polynomial&p);{while(p.head-next!=NULL){k=p.head;p.head=p.head-next;free(k);}free(&p);}//打印输出一元多项式PvoidPrintPolyn(polynomialp);{ha=GetHead(p);coutm',';for(inti=1;i=m;i++){qa=NextPos(p,ha);e=GetCurElem(qa);coute.coef','e.expn',';ha=qa;}coutendl;}//打印输出一元多项式的类数学表达式voidExpression(polynomialp,intm);//完成多项式的相加运算，即：Pa=Pa+Pb，并销