數(shù)據(jù)結(jié)構(gòu)課程報告

PAGE16數(shù)據(jù)結(jié)構(gòu)課程報告姓名：周濤學(xué)號：201313040322問題描述與功能設(shè)計本程序要求能夠?qū)崿F(xiàn)從鍵盤鍵入兩個多項式的系數(shù)、指數(shù)相關(guān)數(shù)據(jù)后，能夠進行多項式輸出、多項式相加、多項式相減的運算。數(shù)據(jù)結(jié)構(gòu)與算法多項式的邏輯結(jié)構(gòu)：視為線性表p(x)=3x14-8x8+6x2+2數(shù)據(jù)元素(coef,exp)表示多項式項coef·Xexp，coef是該項的系數(shù)，exp是變元X的指數(shù)。coeexp*next算法多項式的輸入與建立調(diào)用CreatePolyn（）函數(shù)建立鏈表，將多項式每一項的系數(shù)與指數(shù)作為鏈表一個結(jié)點的數(shù)據(jù)，按照指示輸入每一項的系數(shù)與指數(shù)時，將調(diào)用Insert（）函數(shù)，將輸入的結(jié)點信息按指數(shù)降序排列的方式插入到之前建立的鏈表中，并合并同類項。依次輸入、建立一元多項式pa和pb。如下圖。多項式的輸出調(diào)用PrintPolyn（）函數(shù)將多項式鏈表中的結(jié)點數(shù)據(jù)按照一元多項式的格式(如：6x^5+3x^3+7x+3)輸出到屏幕上。兩個多項式的加法調(diào)用AddPolyn（）函數(shù)直接對兩個多項式的鏈表的結(jié)點成員的系數(shù)與指數(shù)按照數(shù)學(xué)中多項式相加的原則進行操作。其中要調(diào)用compare（）函數(shù)對兩個多項式的指數(shù)或是項數(shù)進行比較。相加所得的多項式存放到新建的第三個多項式中。再對第三個多項式輸出即可。兩個多項式的減法調(diào)用SubtractPolyn（）函數(shù)對兩個多項式減法運算。首先對要減的多項式的系數(shù)求反，接著調(diào)用AddPolyn（）函數(shù)對處理后的多項式相加即兩個多項式的相減。所得的多項式存放到新建的第三個多項式中，再對第三個多項式輸出即可。函數(shù)定義為了程序功能的順利實現(xiàn)，在本程序中定義了如下函數(shù)：函數(shù)名功能Insert()鏈表結(jié)點數(shù)據(jù)的插入與排序CreatePolyn()鏈表頭結(jié)點的創(chuàng)建DestroyPolyn()鏈表的銷毀PrintPolyn()鏈表數(shù)據(jù)的多項式形象化輸出Compare()兩個多項式的指數(shù)或是項數(shù)進行比較AddPolyn()兩個多項式的加法SubtractPolyn()兩個多項式的減法desktop()程序界面的實現(xiàn)編碼鏈表建立的函數(shù),該函數(shù)在多項式信息輸入時按照指數(shù)降序排列建立鏈表，并在出現(xiàn)同類項時合并。voidInsert(Polynp,Polynh){ if(p->coe==0)deletep;//當(dāng)前結(jié)點的coe成員等于0的時候刪除當(dāng)前結(jié)點 else{ Polynq1,q2; q1=h;q2=h->next; while(q2&&p->exp<q2->exp)//查找插入位置 { q1=q2; q2=q2->next; } if(q2&&p->exp==q2->exp)//將指數(shù)相同相合并 { q2->coe+=p->coe; deletep; if(!q2->coe) { q1->next=q2->next; deleteq2; } } else//指數(shù)為新時將結(jié)點插入 { p->next=q2; q1->next=p; } }}鏈表信息按照多項式形式輸出。voidPrintPolyn(PolynP){ Polynq=P->next; intflag=1;//項數(shù)計數(shù)器 if(!q) {//若多項式為空，輸出0 cout<<"0"; cout<<endl; return; } while(q) { if(q->coe>0&&flag!=1)cout<<"+";//系數(shù)大于0且不是第一項時就輸出+ if(q->coe!=1&&q->coe!=-1)//系數(shù)非1或-1的普通情況 { cout<<q->coe; if(q->exp==1)cout<<"X";//當(dāng)前結(jié)點exp為1時 elseif(q->exp)cout<<"X^"<<q->exp; } else { if(q->coe==1)系數(shù)為1的特殊情況 { if(!q->exp)cout<<"1";//指數(shù)不存在 elseif(q->exp==1)cout<<"X";/指數(shù)等于一 elsecout<<"X^"<<q->exp; } if(q->coe==-1)系數(shù)為-1的特殊情況情況 { if(!q->exp)cout<<"-1";//指數(shù)不存在 elseif(q->exp==1)cout<<"-X";//指數(shù)等于一 elsecout<<"-X^"<<q->exp; } } q=q->next;//當(dāng)前指針指向下一結(jié)點 flag++;//項序數(shù)自加1 } cout<<endl;}兩個多項式的加法。intcompare(Polyna,Polynb)//對兩個多項式的系數(shù)或項數(shù)進行比較{ if(a&&b){//兩個多項式都存在 if(!b||a->exp>b->exp)return1;當(dāng)b多項式不存在或者a多項式的指數(shù)大于b的的時候，返回1 elseif(!a||a->exp<b->exp)return-1;當(dāng)a多項式不存在或者b多項式的指數(shù)大于a的的時候，返回-1 elsereturn0;//其他情況返回0 } elseif(!a&&b)return-1;//a多項式已空，但b多項式非空 elsereturn1;//b多項式已空，但a多項式非空}PolynAddPolyn(Polynpa,Polynpb){ Polynqa=pa->next; Polynqb=pb->next; Polynheadc,hc,qc; hc=newPolynomial;//建立一個新的結(jié)點 hc->next=NULL; headc=hc; while(qa||qb){ qc=newPolynomial;//新建一個結(jié)點 switch(compare(qa,qb)){//調(diào)用compare函數(shù)對兩個多項式進行比較 case1://a多項式的指數(shù)大于b的 { qc->coe=qa->coe; qc->exp=qa->exp; qa=qa->next; break; } case0://有同類項則合并 { qc->coe=qa->coe+qb->coe; qc->exp=qa->exp; qa=qa->next; qb=qb->next; break; } case-1:a多項式的指數(shù)小于b的 { qc->coe=qb->coe; qc->exp=qb->exp; qb=qb->next; break; } } if(qc->coe!=0){//當(dāng)相加系數(shù)不為0時 qc->next=hc->next; hc->next=qc; hc=qc; } elsedeleteqc;//當(dāng)相加系數(shù)為0時，釋放該結(jié)點 } returnheadc;}兩個多項式的減法。兩個多項式的減法是建立在加法的的基礎(chǔ)上，對要減的多項式的系數(shù)求反，接著調(diào)用AddPolyn（）函數(shù)對處理后的多項式相加即兩個多項式的相減PolynSubtractPolyn(Polynpa,Polynpb){ Polynh=pb; Polynp=pb->next;//新建一個結(jié)點作為pb的后繼結(jié)點 Polynpd; while(p)//當(dāng)結(jié)點存在時，對所有coe數(shù)據(jù)求反 { p->coe*=-1; p=p->next; } pd=AddPolyn(pa,h);//調(diào)用加法函數(shù) for(p=h->next;p;p=p->next)//恢復(fù)pb的系數(shù) p->coe*=-1; returnpd;}測試及結(jié)果測試的數(shù)據(jù)：(1)A+BA=3x14-8x8+6x2+2B=2x10+4x8+-6x2(2)A-BA=11x14+3x10+2x8+10x6+5B=2x14+3x8+5x6+7思考通過這個一元多項市的設(shè)計,熟悉了數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)之間的存儲,自己的程序還有一些bug，一些數(shù)據(jù)的限制還不夠完善，對于乘法的設(shè)計也沒有完成，，，在程序做完一組數(shù)據(jù)后，若要重新輸入多項市的參數(shù)，只能退出后在進入，返回沒有實現(xiàn)，本來想有一個goto的，沒搞好。返回搞好了，但是測試圖沒有重新弄。還有就是數(shù)據(jù)測試的事例還太少，一些邊際的數(shù)據(jù)還沒測試。下次努力更好。附錄源代碼#include<iostream>#include<stdlib.h>#include<math.h>usingnamespacestd;typedefstructPolynomial{intcoe;intexp;structPolynomial*next;}*Polyn,Polynomial;voidInsert(Polynp,Polynh)//在多項式信息輸入時按照指數(shù)降序排列建立鏈表，實現(xiàn)同類項時合并。{if(p->coe==0)deletep;else{Polynq1,q2;q1=h;q2=h->next;while(q2&&p->exp<q2->exp){q1=q2;q2=q2->next;}if(q2&&p->exp==q2->exp){q2->coe+=p->coe;deletep;if(!q2->coe){q1->next=q2->next;deleteq2;}}else{p->next=q2;q1->next=p;}}}PolynCreatePolyn(Polynhead,intm)//鏈表頭結(jié)點的創(chuàng)建{inti;Polynp;p=head=newPolynomial;head->next=NULL;for(i=0;i<m;i++){p=newPolynomial;;cout<<"請輸入第"<<i+1<<"項的系數(shù):";cin>>p->coe;cout<<"指數(shù):";cin>>p->exp;Insert(p,head);}returnhead;}voidDestroyPolyn(Polynp)//鏈表的銷毀{Polynt;while(p!=NULL){t=p;p=p->next;deletet;}}voidPrintPolyn(PolynP)//鏈表數(shù)據(jù)的多項式輸出{Polynq=P->next;intflag=1;if(!q){cout<<"0";cout<<endl;return;}while(q){if(q->coe>0&&flag!=1)cout<<"+";if(q->coe!=1&&q->coe!=-1){cout<<q->coe;if(q->exp==1)cout<<"X";elseif(q->exp)cout<<"X^"<<q->exp;}else{if(q->coe==1){if(!q->exp)cout<<"1";elseif(q->exp==1)cout<<"X";elsecout<<"X^"<<q->exp;}if(q->coe==-1){if(!q->exp)cout<<"-1";elseif(q->exp==1)cout<<"-X";elsecout<<"-X^"<<q->exp;}}q=q->next;flag++;}cout<<endl;}intcompare(Polyna,Polynb)//兩個多項式的指數(shù),項數(shù)進行比較{if(a&&b){if(!b||a->exp>b->exp)return1;elseif(!a||a->exp<b->exp)return-1;elsereturn0;}elseif(!a&&b)return-1;elsereturn1;}PolynAddPolyn(Polynpa,Polynpb)//兩個多項式的加法{Polynqa=pa->next;Polynqb=pb->next;Polynheadc,hc,qc;hc=newPolynomial;hc->next=NULL;headc=hc;while(qa||qb){qc=newPolynomial;switch(compare(qa,qb)){case1:{qc->coe=qa->coe;qc->exp=qa->exp;qa=qa->next;break;}case0:{qc->coe=qa->coe+qb->coe;qc->exp=qa->exp;qa=qa->next;qb=qb->next;break;}case-1:{qc->coe=qb->coe;qc->exp=qb->exp;qb=qb->next;break;}}if(qc->coe!=0){qc->next=hc->next;hc->next=qc;hc=qc;}elsedeleteqc;}returnheadc;}PolynSubtractPolyn(Polynpa,Polynpb)//兩個多項式的減法{Polynh=pb;Polynp=pb->next;Polynpd;while(p){p->coe*=-1;p=p->next;}pd=AddPolyn(pa,h);for(p=h->next;p;p=p->next)p->coe*=-1;returnpd;}voiddesktop(){system("cls");cout<<"一元多項式的計算"<<endl;cout<<"**********************************************"<<endl;cout<<"**1.輸出多項式a和b**"<<endl;cout<<"**2.建立多項式a+b**"<<endl;cout<<"**3.建立多項式a-b**"<<endl;cout<<"**4.返回重新輸入?yún)?shù)**"<<endl;cout<<"**********************************************"<<endl;cout<<"執(zhí)行操作:";}intmain(){intm,n;floatx,result;charkey;Polynpa,pb,pc,pd,pf;r1:cout<<"歡迎"<<endl;cout<<"請輸入多項式A的項數(shù):";cin>>m;pa=CreatePolyn(pa,m);cout<<endl;cout<<"請輸入多項式B的項數(shù):";cin>>n;pb=CreatePolyn(pb,n);system("pause");system("cls");while(key){desktop();cin>>key;