數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-多項式計算

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

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