數據結構課程設計-多項式計算

需求分析1該程序的功能相當于一個一元多項式計算器。它能夠實現按照指數升序排列建立并輸出多項式，并且能夠完成兩個多項式的相加，相減，相乘，求導，求積分的運算的功能。輸入是從鍵盤輸入的，輸入的內容為多項式的項數，系數和指數，為任意的數；指數為大于等于0的整數從屏幕輸出，顯示用戶輸入的多項式，并顯示運算以后的多項式的表達式。一元多項式的建立，、先輸入多項式的項數，每輸入一個多項式的項就判斷此項的指數是否與之前輸入項的指數相同，如果相同就將將兩項的系數相加；如果不相同就產生一個新的節(jié)點。當達到輸入項的項數就結束一個多項式的輸入。顯示一元多項式，如果系數是大于0的話就輸出+系數x指數的形式；如果系數是小于0的話就輸出系數X指數的形式；如果指數是0的話直接輸出系數；如果系數是1的話就直接輸出+X；如果系數是-1的話就直接輸出-X。一元多項式的加法運算，設兩指針qa與qb分別遍歷Pa與Pb,若均不空則比較當前兩項，分三種情況:其一,Pa中項的指數小，則qa后移一項；其二，兩者指數相等，若系數相加和為零，此時從和多項式Pa中將該項刪除（需事先設指針prea）,同時釋放Pb中的當前項（事先設指針preb）;若指數相等系數和不為0，則修改Pa中當前項的系數值，同時釋放Pb的當前結點；其三,Pb中指數小，則將Pb中當前項拿走，插入到Pa中當前項前邊。一元多項式的減法，設兩指針qa與qb分別遍歷Pa與Pb,若均不空則比較當前兩項，分三種情況:其一,Pa中項的指數小，則qa后移一項；其二，兩者指數相等，若系數相減差為零，此時從和多項式Pa中將該項刪除（需事先設指針prea）,同時釋放Pb中的當前項（事先設指針preb）;若指數相等系數和不為0，則修改Pa中當前項的系數值，同時釋放Pb的當前結點；其三,Pb中指數小，則將Pb中當前項拿走，插入到Pa中當前項前邊?！囗検降某朔?，使用多項式，多項式Pa和Pb相乘，多項式Pc則用于保存Pa和Pb相乘的結果。如果Pc中存在相同項的話就調用合并函數將相同項合并。一元多項式求導，根據一元多項式求導法則，在進行多項式求導時將多項式各項轉換成：系數為原系數與原指數的乘積，指數轉換成原指數減1。一元多項式求積分，根據一元多項式求積分法則，在進行多項式求導時將多項式各項轉換成：系數為原系數與原指數的商，指數轉換成原指數加1。二、概要設計抽象數據類型一元多項式的定義為如下：ADTPolynomail(數據對象：D={ai|ai^Termset,i=1,2,3,???m,mN0Termset中的每個元素包含一個表示數的實數和表示指數的整數}數據關系：R1={<ai-1,ai>|ai-1,aieD,且ai-1中的指數取值Vai中的指數值，i=1,2,…,n}基本操作：CreatPolyn(&P,m)操作結果：輸入m項的系數和指數，建立一元多項式P。MergeLikeTerm(&P)初始條件：多項式P存在操作結果：實現多項式的同類項合并。Order(&P)初始條件：多項式P存在操作結果：實現按exp域遞增排序多項式的項。AddPoly(&P1,&P2)初始條件：多項式P1和P2存在操作結果：實現多項式的相加運算，即:P3=P1+P2。SubPoly(&P1,&P2)初始條件：多項式P1和P2存在操作結果：實現多項式的相減運算，即:P3二P1-P2。MultiplyPoly(&P1,&P2)初始條件：多項式P1和P2存在操作結果：實現多項式的相乘運算，即:P3二P1*P2。Derivation_L(&P)初始條件：多項式P存在操作結果：實現多項式的求導。integralPoly(Polynomial&P)初始條件：多項式P存在操作結果：實現多項式的求導}ADTPolynomail三詳細設計3.1抽象數據類型的實現，元素類型、結點類型和指針類型typedefintLElemType;typedefintStatus;typedefstructintexpn;//系數floatcoef;//指數}term,ElemType;//類型名typedefstructLNode(ElemTypedata;structLNode*next;}LNode,*LinkList;typedefLinkListPolynomial;3.2L中存在與e指數相等的元素，則Locate返回TRUE,q指向第一個相等的元素；否則，Locate返回FALSE，StatusLocateElem(LinkListL,ElemTypee,LinkList&q,Status(*cmp)(ElemType,ElemType))(q=L; 〃找第一個指數大于等于e指數的項while(q->next!=NULL&&(*cmp)(q->next->data,e)<0)q=q->next;if(q->next!二NULL&&cmp(q->next->data,e)==0)(q=q->next;returnTRUE;}elsereturnFALSE;3.3調用帶頭結點的單鏈表的創(chuàng)建函數進行多項式的創(chuàng)建StatusCreatePolyn(Polynomial&P,intn)inti;InitList_L(P);LinkListh=P,q,s;terme;printf("請輸入%d項多項式：\n”,n);for(i=1;i<=n;++i)(scanf(〃％f%d〃，&e.coef,&e.expn);//每次先讀入e，之后插入if(!LocateElem(P,e,q,compare))(if(MakeNode(s,e))//開辟新結點InsertAfter(q,s);}elseq->data.coef+=e.coef;//系數相加}returnOK;}3.4合并同類項，合并后的項仍然是按指數升序的排列StatusMergeLikeTerm(Polynomial&P)(if(!P||!P->next)returnERROR;LNode*phead,*ptr,*prep;phead=P,ptr=P->next->next,prep=P->next;while(prep&&ptr)(if(compare(prep->data,ptr->data)<0||compare(prep->data,ptr->data)>0)(prep=prep->next;ptr=ptr->next;}else(prep->data.coef+=ptr->data.coef;prep->next=ptr->next;free(ptr);ptr=prep->next;returnOK;}3.5多項式的輸出StatusPrint_L(PolynomialP)(intj=0;P=P->next;while(P!=NULL)(if(P->data.coef==0)P=P->next;elseif(P->data.expn==0){if(P->next==NULL)printf(〃％f〃,P->data.coef);elseprintf(〃％f+〃,P->data.coef);P=P->next;j=1;}elseif(P->next==NULL){printf(〃％fX(%d)〃，P->data.coef,P->data.expn);P=P->next;j=1;}else{printf(〃％fX(%d)+〃，P->data.coef,P->data.expn);P=P->next;j=1;}}if(j==0)printf(〃0\n〃)；returnOK;}3.6多項式的排序，按指數增大的方向排序StatusOrder(LinkList&P)//按exp域遞增排序多項式的項(LNode*prep=P->next,*q,*r;if(prep)(r=prep->next;prep->next=NULL;prep二r;while(prep)(r=prep->next;q=P;while(q->next&&q->next->data.expn<prep->data.expn)q=q->next;prep->next=q->next;q->next=prep;prep=r;}}returnOK;}3.7多項式的相加StatusAddPoly(Polynomial&Pa,Polynomial&Pb)(LinkListprea=Pa,preb=Pb;LinkListqa=prea->next,qb=preb->next;doublesum;while(qa&&qb)(switch(compare(qa->data,qb->data))(case-1:prea=qa;qa=qa->next;break;//Pa中項的指數小，則qa后移一項case0:sum=qa->data.coef+qb->data.coef;//兩者指數相等，若系數相加和為零，此時從和多項式Pa中將該項刪除(需事先設指針prea),同時釋放Pb中的當前項(事先設指針preb);若指數相等系數和不為0，則修改Pa中當前項的系數值，同時釋放Pb的當前結點if(!sum)(prea->next=qa->next;free(qa);qa=prea->next;//消除qa}else(qa->data.coef二sum;prea=qa;qa=qa->next;//更改qa中的值preb->next=qb->next;free(qb);qb=preb->next;//釋放Pb的當前結點八、、break;點八、、break;1:casepreb->next=qb->next;qb->next=prea->next;prea->next=qb;prea二qb;qb二preb->next;break;//Pb中指數小，則將Pb中當前項拿走，插入到Pa中當前項前邊1:}}if(qb)(prea->next=qb;Pb->next=NULL;}free(Pb);returnOK;}3.8多項式的相減StatusSubPoly(Polynomial&Pa,Polynomial&Pb)(LinkListprea=Pa,preb=Pb;LinkListqa=prea->next,qb=preb->next;doublesum;while(qa&&qb)(switch(compare(qa->data,qb->data))(case-1:prea=qa;qa=qa->next;break;//Pa中項的指數小，則qa后移一項case0:sum=qa->data.coef-qb->data.coef;兩者指數相等，若系數相減差為0此時從和多項式Pa中將該項刪除(需事先設指針prea),同時釋放Pb中的當前項(事先設指針preb);若指數相等系數差不為0，則修改Pa中當前項的系數值,同時釋放Pb的當前結點if(!sum)(prea->next=qa->next;free(qa);qa=prea->next;//消除qa}else(qa->data.coef二sum;prea=qa;qa=qa->next;//更改qa中的值}preb->next=qb->next;free(qb);qb=preb->next;//釋放Pb的當前結break;case 1:preb->next=qb->next;qb->next=prea->next;prea->next=qb;qb->data.coef*二-1;prea=qb;qb=preb->next;break;//Pb中指數小，則將Pb中當前項拿走，插入到Pa中當前項前邊}}if(qb)(prea->next=qb;Pb->next=NULL;while(qb)(qb->data.coef*=-1;qb=qb->next;}}free(Pb);returnOK;}3.9多項式的相乘StatusMultiplyPoly(Polynomial&Pa,Polynomial&Pb,Polynomial&Pc)(LNode*pa,*pb,*rearCptr,*newCptr;Pc=(LinkList)malloc(sizeof(LNode));rearCptr=Pc;if(!Pc)returnERROR;pa=Pa->next;pb=Pb->next;while(pa)((newCptr=(LinkList)malloc(sizeof(LNode));//開辟結點newCptr->data.coef=pa->data.coef*pb->data.coef;//系數相乘newCptr->data.expn=pa->data.expn+pb->data.expn;〃指數相力口rearCptr->next=newCptr;newCptr->next=NULL;rearCptr=newCptr;pb=pb->next;}pb=Pb->next;pa=pa->next;}returnOK;}3.10多項式的求導StatusDerivation_L(Polynomial&P)(LinkListp1=P->next,p2=P;if(P==NULL)returnERROR;while(p1!=NULL)(if(p1->data.expn==0)(p2->next=p1->next;free(pl);p1=p2->next;//釋放p1此時的結點}else(p1->data.coef*=p1->data.expn;//指數乘以系數p1->data.expn--;//指數減一p1=p1->next;p2=p2->next;}}returnOK;}3.11多項式求積分StatusintegralPoly(Polynomial&P)LinkListq=P->next;while(q)(q->data.expn++;//指數加一q->data.coef/=q->data.expn;//系數除以指數q=q->next;//q后移一位}returnOK;}四運行結果4.1程序運行開始界面在程序開始運行時，會出現一個編號1-6的菜單并提示選擇，如下圖4-1所示:圖4-1最初運行界面

4.2兩個多項式相加界面選擇1,將兩個一元多項式相加，操作后結果如圖4-2所示:圖4-2兩個多項式相加界面4.3兩個多項式相減界面選擇2將兩個一