數(shù)據(jù)結(jié)構(gòu)-多項(xiàng)式-實(shí)驗(yàn)報(bào)告(共8頁)_第1頁
數(shù)據(jù)結(jié)構(gòu)-多項(xiàng)式-實(shí)驗(yàn)報(bào)告(共8頁)_第2頁
數(shù)據(jù)結(jié)構(gòu)-多項(xiàng)式-實(shí)驗(yàn)報(bào)告(共8頁)_第3頁
數(shù)據(jù)結(jié)構(gòu)-多項(xiàng)式-實(shí)驗(yàn)報(bào)告(共8頁)_第4頁
數(shù)據(jù)結(jié)構(gòu)-多項(xiàng)式-實(shí)驗(yàn)報(bào)告(共8頁)_第5頁
已閱讀5頁,還剩2頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、北京郵電大學(xué)信息與通信工程學(xué)院數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱: 實(shí)驗(yàn)一多項(xiàng)式的實(shí)現(xiàn)學(xué)生姓名: 班 級(jí): 班內(nèi)序號(hào): 學(xué) 號(hào): 日 期: 2011年10月29日1實(shí)驗(yàn)要求實(shí)驗(yàn)?zāi)康模?.熟悉C+語言的基本編程方法,掌握集成編譯環(huán)境的調(diào)試方法2.學(xué)習(xí)指針、模板類、異常處理的使用3.掌握線性表的操作的實(shí)現(xiàn)方法4.學(xué)習(xí)使用線性表解決實(shí)際問題的能力實(shí)驗(yàn)內(nèi)容: 利用線性表實(shí)現(xiàn)一個(gè)一元多項(xiàng)式Polynomialf(x) = a0 + a1x + a2x2 + a3x3 + + anxn 要求:1 能夠?qū)崿F(xiàn)一元多項(xiàng)式的輸入和輸出2 能夠進(jìn)行一元多項(xiàng)式相加3 能夠進(jìn)行一元多項(xiàng)式相減4 能夠計(jì)算一元多項(xiàng)式在x處的值5 能

2、夠計(jì)算一元多項(xiàng)式的導(dǎo)數(shù)(選作)6 能夠進(jìn)行一元多項(xiàng)式相乘(選作)7 編寫測(cè)試main()函數(shù)測(cè)試線性表的正確性2. 程序分析由于多項(xiàng)式是線性結(jié)構(gòu),故選擇線性表來實(shí)現(xiàn),在這個(gè)程序中我采用的是單鏈表結(jié)構(gòu),每個(gè)結(jié)點(diǎn)代表一個(gè)項(xiàng),多項(xiàng)式的每一項(xiàng)可以用其系數(shù)和指數(shù)唯一的表示。如果采用順序存儲(chǔ),那么對(duì)于結(jié)點(diǎn)的插入和刪除的操作會(huì)比較麻煩,而且順序表的結(jié)點(diǎn)個(gè)數(shù)固定,對(duì)于可能發(fā)生的情況無法很好的處理,而采用鏈表就會(huì)簡(jiǎn)單許多,還能自由控制鏈表的長(zhǎng)度。兩個(gè)多項(xiàng)式要進(jìn)行多次的計(jì)算,為了保護(hù)原始的數(shù)據(jù),方便進(jìn)行以后的計(jì)算,故選擇把結(jié)果存儲(chǔ)在一個(gè)新建的鏈表里。本程序完成的主要功能:1. 輸入和輸出:需要輸入的信息有多項(xiàng)式的

3、項(xiàng)數(shù),用來向系統(tǒng)動(dòng)態(tài)申請(qǐng)內(nèi)存;多項(xiàng)式各項(xiàng)的系數(shù)和指數(shù),用來構(gòu)造每個(gè)結(jié)點(diǎn),形成鏈表。輸出即是將多項(xiàng)式的內(nèi)容向屏幕輸出。2. 多項(xiàng)式相加與相減:多項(xiàng)式的加減要指數(shù)相同即是同類項(xiàng)才能實(shí)現(xiàn),所以在運(yùn)算時(shí)要注意判斷指數(shù)出現(xiàn)的各種不同的情況,分別寫出計(jì)算方法。將每項(xiàng)運(yùn)算得到的結(jié)果都插入到新的鏈表中,形成結(jié)果多項(xiàng)式。3. 多項(xiàng)式的求導(dǎo)運(yùn)算:多項(xiàng)式的求導(dǎo)根據(jù)數(shù)學(xué)知識(shí),就是將每項(xiàng)的系數(shù)乘以指數(shù),將指數(shù)減1即可,將每項(xiàng)得到的結(jié)果插入到結(jié)果多項(xiàng)式的鏈表中。4. 多項(xiàng)式在某點(diǎn)的值:由用戶輸入x的值,然后求出每項(xiàng)的值相加即可。 2.1 存儲(chǔ)結(jié)構(gòu)本程序采用的存儲(chǔ)結(jié)構(gòu)是單鏈表結(jié)構(gòu),其定義的結(jié)點(diǎn)包括三部分:系數(shù)、指數(shù)以及下一

4、個(gè)結(jié)點(diǎn)的地址。示意圖如下:coef1 expn1 nextcoef1 expn1 nextcoef1 expn1 next next 2.2 關(guān)鍵算法分析1. 輸入多項(xiàng)式·自然語言描述:1. 設(shè)置多項(xiàng)式的項(xiàng)數(shù)n;2. 按照多項(xiàng)式的項(xiàng)數(shù)申請(qǐng)動(dòng)態(tài)數(shù)組coef和expn存儲(chǔ)多項(xiàng)式的系數(shù)和指數(shù);3. 按照指數(shù)遞增的次序輸入各項(xiàng)的系數(shù)以及指數(shù),分別存入coef和expn;4. 再將輸入的系數(shù)以及指數(shù)賦給每一個(gè)結(jié)點(diǎn)的coef和expn域; 5. 利用頭插法將每個(gè)結(jié)點(diǎn)加入鏈表。·偽代碼:1. 輸入項(xiàng)數(shù)n;2. float* coef1=new floatn1;int* expn1=new

5、 intn1;3. 運(yùn)用for循環(huán),循環(huán)n次3.1 term* s=new term; 3.2 s->coef=coefi;3.3 s->expn=expni; 3.4 r->next=s; 3.5 r=s; 4. 運(yùn)用頭插法將結(jié)點(diǎn)插入鏈表。時(shí)間復(fù)雜度:空間復(fù)雜度:2. 輸出多項(xiàng)式·自然語言描述:1. 獲取頭結(jié)點(diǎn);2. 循環(huán)n-1次(n為多項(xiàng)式的項(xiàng)數(shù))2.1將指針的指向后移;2.2依照多項(xiàng)式的各種情況,設(shè)置輸出方式 2.2.1 系數(shù)為1且指數(shù)不為1和0,輸出xexpn+; 2.2.2 系數(shù)不為0且指數(shù)為0,輸出(coef)+; 2.2.3 系數(shù)不為0且指數(shù)為1,輸出

6、(coef)x+; 2.2.4 系數(shù)不為0和1,指數(shù)不為0和1,輸出(coef)x(expn)+; 3.將指針指向移到最后一個(gè)節(jié)點(diǎn)。重復(fù)2.2中判斷,但不輸出+號(hào)。·偽代碼描述:1. term* m=front;2. for(int i=0;i<n-1;i+)2.1 m=m->next;2.2 if(m->coef=1&&(m->expn!=1&&m->expn!=0)cout<<"x"<<m->expn<<"+"2.3 else if(m-

7、>coef=1&&m->expn=0)cout<<m->coef<<"+"2.4 else if(m->coef!=1&&m->expn=0)cout<<m->coef<<"+"2.5 else if(m->coef!=0&&m->expn=1)cout<<m->coef<<"x"<<"+"2.6 else if(m->coe

8、f=1&&m->expn=1)cout<<"x"<<"+"2.7 else if(m->coef=0)cout<<""<<"+"2.8 elsecout<<m->coef<<"x"<<m->expn<<"+"3. m=m->next;3.1 if(m->coef=1&&(m->expn!=1&&

9、;m->expn!=0)cout<<"x"<<m->expn<<""3.2 else if(m->coef=1&&m->expn=0)cout<<m->coef;3.3 else if(m->coef!=1&&m->expn=0)cout<<m->coef;3.4 else if(m->coef!=1&&m->expn=1)cout<<m->coef<<&qu

10、ot;x"<<""3.5 else if(m->coef=1&&m->expn=1)cout<<"x"3.6 else if(m->coef=0)cout<<""3.7 elsecout<<m->coef<<"x"<<m->expn<<""時(shí)間復(fù)雜度:O(n)空間復(fù)雜度:S(1)3. 多項(xiàng)式的相加相減·自然語言描述:1. 指針p和q分別指向a和b兩

11、個(gè)多項(xiàng)式的頭結(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn);2. 將結(jié)果多項(xiàng)式的項(xiàng)數(shù)置為0;3. 只有p或q非空,進(jìn)行以下循環(huán):3.1 申請(qǐng)一個(gè)term* 型的指針d,將其next域賦為NULL;進(jìn)行判斷:3.3.1 如果p和q均非空3.3.3.1 如果p和q的指數(shù)相等將d的系數(shù)賦為p、q系數(shù)之和,指數(shù)不變,將p、q指向后移;3.3.3.2 如果p->expn>q->expn復(fù)制q到結(jié)果多項(xiàng)式(減法系數(shù)為q->coef的相反數(shù))3.3.3.3 如果p->expn<q->expn復(fù)制p到結(jié)果多項(xiàng)式3.3.3.4 判斷后將項(xiàng)數(shù)+,插入新節(jié)點(diǎn)d;3.3.2 如果q為空,p仍存在,逐項(xiàng)將p

12、復(fù)制到結(jié)果多項(xiàng)式。每進(jìn)行一次,項(xiàng)數(shù)+,p后移。3.3.3 如果p為空,q仍存在,逐項(xiàng)將q復(fù)制到結(jié)果多項(xiàng)式(減法將系數(shù)變?yōu)樵瓉淼南喾磾?shù))。每進(jìn)行一次,項(xiàng)數(shù)+,q后移。3.2 返回結(jié)果多項(xiàng)式的項(xiàng)數(shù) ·偽代碼描述:1. 工作指針p、q初始化:term* p=front->next;term* q=b.front->next; 2. int nAdd=0;/加法 int nMinus=0;/減法 3. while(p|q) 3.1 term* d=new term;d->next=NULL; 3.3.1 if(p&&q) 3.3.3.1 if(p->e

13、xpn=q->expn) d->coef=p->coef+q->coef;d->expn=p->expn;p=p->next;q=q->next;/加法 d->coef=p->coef-q->coef;d->expn=p->expn;p=p->next;q=q->next;/減法 3.3.3.2 p->expn>q->expn d->coef=q->coef;d->expn=q->expn;q=q->next;/加法d->coef=-q->coe

14、f;d->expn=q->expn;q=q->next;/減法 3.3.3.3p->expn<q->expnd->coef=p->coef;d->expn=p->expn;p=p->next;/加法d->coef=p->coef;d->expn=p->expn;p=p->next;/減法 3.3.3.4 nAdd+;add.Insert(d);/加法 nMinus+;min.Insert(d);/減法 3.3.2 while(p)term* d=new term;d->coef=p->c

15、oef; d->expn=p->expn;d->next=NULL;nAdd+; add.Insert(d);p=p->next;/加法term* d=new term;d->coef=(p->coef); d->expn=p->expn;d->next=NULL; nMinus+;min.Insert(d);p=p->next;/減法 3.3.3 while(q) term* d=new term;d->coef=q->coef; d->expn=q->expn;d->next=NULL; nAdd+;

16、add.Insert(d);q=q->next;/加法term* d=new term;d->coef=0-(q->coef); d->expn=q->expn;d->next=NULL; nMinus+;min.Insert(d);q=q->next;/減法3.2 return nAdd; return nMinus;時(shí)間復(fù)雜度:O(n)空間復(fù)雜度:O(2)4. 求值·自然語言描述:1. 將工作指針指向多項(xiàng)式的第一項(xiàng);2. 將結(jié)果result置為0;3. 指針不為空,即進(jìn)行循環(huán):3.1 result+=s->coef*(pow(x,s

17、->expn); 3.2 s=s->next; 4返回result;· 偽代碼描述:1. term* s=front->next;2. float result=0;3. while(s)3.1 result+=s->coef*(pow(x,s->expn); 3.2 s=s->next; 4. return result;時(shí)間復(fù)雜度:O(n)空間復(fù)雜度:S(1)5. 求導(dǎo)數(shù)·自然語言描述:1. 將指針指到多項(xiàng)式的第一項(xiàng)的結(jié)點(diǎn):term* p=a.front->next;2. 循環(huán)n次2.1 每項(xiàng)求導(dǎo)的系數(shù)為:p->coef*

18、p->expn;指數(shù)為:p->expn-1;2.2 將新結(jié)點(diǎn)插入新鏈表;2.3 指針p后移。 ·偽代碼描述: 1. term* p=a.front->next; 2. for(int i=0;i<n;i+) 2.1 term* s=new term; 2.2 if(p->expn) 2.2.1 s->coef=(p->coef)*(p->expn); 2.2.2 s->expn=p->expn-1; 2.2.3p=p->next; 2.2.4 de.Insert(s); 2.3 else 2.3.1 s->coef=0;2.3.2 s->expn=0;2.3.3 p=p->next;2.3.4 de.Insert(s);時(shí)間復(fù)雜度:O(n)空間復(fù)雜度:S(1)3. 程序運(yùn)行結(jié)果1. 測(cè)試主函數(shù)流程:1開始進(jìn)行A-B的運(yùn)算設(shè)置多項(xiàng)式A的項(xiàng)數(shù)按照A的項(xiàng)數(shù)動(dòng)態(tài)申請(qǐng)coef1和expn1輸出相減的結(jié)果minus進(jìn)行對(duì)A求導(dǎo)數(shù)的運(yùn)算輸出A設(shè)置多項(xiàng)式B的項(xiàng)數(shù)輸出求導(dǎo)的結(jié)果de按照B的項(xiàng)數(shù)動(dòng)態(tài)申請(qǐng)coef2和expn2輸入x的取值計(jì)算A在x處的取值并輸出輸出B結(jié)束進(jìn)行A+B的運(yùn)算輸出相加的結(jié)果add1測(cè)試條件:?jiǎn)栴}規(guī)模n的數(shù)量級(jí)為

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論