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

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

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