數(shù)據(jù)結(jié)構(gòu)課程設(shè)計一元多項式乘法

PAGEPAGE41學(xué)號數(shù)據(jù)結(jié)構(gòu)課程設(shè)計設(shè)計說明書題目一元多項式乘法起止日期：20XX年12月12日至20XX年1學(xué)生姓名班級成績指導(dǎo)教師(簽字)電子與信息工程系20XX年12月16日

天津城市建設(shè)學(xué)院課程設(shè)計任務(wù)書20XX—2012學(xué)年第1學(xué)期電子與信息工程系軟件工程專業(yè)班級課程設(shè)計名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計設(shè)計題目：一元多項式乘法完成期限：自20XX年12月12日至20XX年12月16日共1周設(shè)計依據(jù)、要求及主要內(nèi)容（可另加附頁）：目錄一、設(shè)計目的 4二、設(shè)計要求 4三、設(shè)計內(nèi)容 41)問題描述 42)基本要求 4一、需求分析 5二、問題求解 5三、總體設(shè)計 6四、詳細(xì)設(shè)計 6五、調(diào)試與測試 7六、關(guān)鍵源程序清單和執(zhí)行結(jié)果 7四、參考文獻(xiàn) 9一、設(shè)計目的熟悉各種數(shù)據(jù)結(jié)構(gòu)和運算，會使用數(shù)據(jù)結(jié)構(gòu)的基本操作解決一些實際問題。二、設(shè)計要求（1）重視課程設(shè)計環(huán)節(jié)，用嚴(yán)謹(jǐn)、科學(xué)和踏實的工作態(tài)度對待課程設(shè)計的每一項任務(wù)；（2）按照課程設(shè)計的題目要求，獨立地完成各項任務(wù)，嚴(yán)禁抄襲；凡發(fā)現(xiàn)抄襲，抄襲者與被抄襲者皆以零分計入本課程設(shè)計成績。凡發(fā)現(xiàn)實驗報告或源程序雷同，涉及的全部人員皆以零分計入本課程設(shè)計成績；（3）學(xué)生在接受設(shè)計任務(wù)后，首先要按設(shè)計任務(wù)書的要求編寫設(shè)計進(jìn)程表；（4）認(rèn)真編寫課程設(shè)計報告。三、設(shè)計內(nèi)容一元多項式乘法1)問題描述已知A(x)=a0+a1x+a2x2+……+anxn和B(x)=b0+b1x+b2x2+……+bmxm，并且在A(x)和B(x)中指數(shù)相差很多，求A(x)=A(x)*B(x)。2)基本要求(1)設(shè)計存儲結(jié)構(gòu)表示一元多項式；(2)設(shè)計算法實現(xiàn)一元多項式乘法；(3)分析算法的時間復(fù)雜度和空間復(fù)雜度。一、需求分析程序是要完成兩個一元多項式乘法的功能。要求輸入兩個多項式中每個數(shù)據(jù)項的系數(shù)和指數(shù)，從而得到一個新的多項式，這個多項式是輸入的兩個多項式的乘積。二、問題求解一元多項式的乘法是在初中學(xué)到的數(shù)學(xué)知識，我們當(dāng)時是這樣做的：用第一個數(shù)據(jù)項的每一項去乘另一個多項式，得到的結(jié)果加起來，然后合并同類項，按照升序，或者降序的方法給得到的多項式進(jìn)行排序，這樣就得到了結(jié)果。用數(shù)據(jù)結(jié)構(gòu)來解決這個問題的話，首先要設(shè)計多項式的存儲結(jié)構(gòu)，然后設(shè)計算法，這個時候要注意的就是算法的時間復(fù)雜度和空間復(fù)雜度。在本次實驗里，我用的是一維數(shù)組來表示一個一元多項式。其中數(shù)組中每個數(shù)據(jù)的下標(biāo)表示多項式中數(shù)據(jù)項的指數(shù)，數(shù)據(jù)的值來表示此數(shù)據(jù)項的系數(shù)。第一個問題就是要定義幾個數(shù)組，因為是要對兩個多項式計算乘積，所以，我定義了三個數(shù)組，兩個數(shù)組表示要計算的兩個多項式，第三個數(shù)組用來表示求得的數(shù)組。第二個問題就是怎么定義數(shù)組的長度。為了便于驗證試驗，我給要輸入的兩個數(shù)組的長度都定義為10，既它們的數(shù)據(jù)項中指數(shù)最大為9.為了節(jié)省空間，目標(biāo)數(shù)組要定義得恰到好處。通過計算兩個指數(shù)為9的數(shù)據(jù)項相乘，其結(jié)果數(shù)據(jù)項的指數(shù)為18，所以目標(biāo)多項式中出現(xiàn)的最大指數(shù)就是18，因此定義目標(biāo)數(shù)組的長度為19（0~18）。第三個問題為了美觀，系數(shù)為0的數(shù)據(jù)項就不要顯示出來了。在輸出結(jié)果時，用到一個條件結(jié)構(gòu)。只輸出系數(shù)不為0的數(shù)據(jù)項。三、總體設(shè)計9開始開始輸入a[10],b[10]C[m+n]=a[m]+b[n]輸出c[19]定義c[19],且都初始化為0.結(jié)束四、詳細(xì)設(shè)計用數(shù)組a表示第一個多項式，其中a[i]表示多項式A中的指數(shù)為i的系數(shù)，數(shù)組b表示第一個多項式，其中b[i]表示多項式B中的指數(shù)為i的系數(shù)。A中指數(shù)為m的項與B中指數(shù)為n的項相乘，結(jié)果是得到指數(shù)為m+n的項，而且這個項的系數(shù)為a[m]*b[n].把這個系數(shù)保存在數(shù)組c的c[m+n]中。五、調(diào)試與測試方案一：初始化兩個一元多項式的時候輸入幾個系數(shù)為0的數(shù)據(jù)項，檢驗程序是否正常運行。方案二：初始化數(shù)組的時候，輸入小數(shù)，負(fù)數(shù)，檢驗程序是否出現(xiàn)錯誤。六、關(guān)鍵源程序清單和執(zhí)行結(jié)果源程序：#include<iostream>usingnamespacestd;voidmain(){ inta[10],b[10],c[19];//a[i]表示多項式A中指數(shù)為i的系數(shù)。 cout<<"請輸入多項式A中依次的系數(shù)"<<endl<<endl; /*創(chuàng)建第一個多項式*/ for(inti=0;i<10;i++) cin>>a[i]; cout<<"多項式A為:"<<endl<<endl<<"A(X)="; /*打印第一個多項式*/ for(i=0;i<10;i++) { if(a[i]!=0) { cout<<a[i]<<"*X^"<<i<<"+"; } } cout<<endl<<"請輸入多項式B中依次的系數(shù)"<<endl<<endl; /*創(chuàng)建第二個多項式*/ for(intj=0;j<10;j++) {cin>>b[j];} /*打印第二個多項式*/ cout<<"多項式B為:"<<endl<<endl<<"B(X)=";for(intt=0;t<10;t++) { if(b[t]!=0) { cout<<b[t]<<"*X^"<<t<<"+"; } }/*初始化結(jié)果多項式*/ for(i=0;i<19;i++) {c[i]=0;} /*計算兩個多項式的乘積*/for(intm=0;m<10;m++) { for(intn=0;n<10;n++)c[m+n]=a[m]*b[n]+c[m+n]; }cout<<endl<<endl<<"得出的兩個多項式的乘積為:"<<endl<<endl<<"A(X)=A(X)*B(X)="<<endl; /*打印出兩個多項式的乘積*/for(intv=0;v<19;v++) { if(c[v]!=0) {cout<<c[v]<<"*X^"<<v<<"+";} } cout<<"\n";cout<<endl<<endl;}執(zhí)行結(jié)果：請輸入多項式A中依次的系數(shù)5242647896多項式A為:A(X)=5*X^0+2*X^1+4*X^2+2*X^3+6*X^4+4*X^5+7*X^6+8*X^7+9*X^8+6*X^9+請輸入多項式B中依次的系數(shù)5346100007多項式B為:B(X)=5*X^0+3*X^1+4*X^2+6*X^3+1*X^4+7*X^9+得出的兩個多項式的乘積為:A(X)=A(X)*B(X)=25*X^0+25*X^1+46*X^2+60*X^3+69*X^4+72*X^5+87*X^6+115*X