數(shù)據(jù)結(jié)構(gòu)-多項(xiàng)式-實(shí)驗(yàn)報(bào)告

1、數(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 能夠計(jì)算一元多項(xiàng)式的導(dǎo)數(shù)（選作）

2、6 能夠進(jìn)行一元多項(xiàng)式相乘（選作）7 編寫測試main()函數(shù)測試線性表的正確性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ì)簡單許多，還能自由控制鏈表的長度。兩個(gè)多項(xiàng)式要進(jìn)行多次的計(jì)算，為了保護(hù)原始的數(shù)據(jù)，方便進(jìn)行以后的計(jì)算，故選擇把結(jié)果存儲(chǔ)在一個(gè)新建的鏈表里。本程序完成的主要功能：1. 輸入和輸出：需要輸入的信息有多項(xiàng)式的項(xiàng)數(shù)，用來向系統(tǒng)動(dòng)態(tài)申請內(nèi)存；

3、多項(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ù)以及下一個(gè)結(jié)點(diǎn)的地址。示意圖如下：co

4、ef1 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ù)申請動(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 intn1;3. 運(yùn)用for循環(huán)，循環(huán)n次3.1 t

5、erm* 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，輸出（coef）x+； 2.2.4 系數(shù)不為0和1，指數(shù)不為0和1，輸出(coef)x(exp

6、n)+； 3.將指針指向移到最后一個(gè)節(jié)點(diǎn)。重復(fù)2.2中判斷，但不輸出+號(hào)。偽代碼描述：1. term* m=front;2. for(int i=0;inext;2.2 if(m-coef=1&(m-expn!=1&m-expn!=0)coutxexpncoef=1&m-expn=0)coutcoefcoef!=1&m-expn=0)coutcoefcoef!=0&m-expn=1)coutcoefxcoef=1&m-expn=1)coutxcoef=0)cout+;2.8 elsecoutcoefxexpnnext;3.1 if(m-coef=1&(m-expn!=1&m-expn!=0)c

7、outxexpncoef=1&m-expn=0)coutcoef;3.3 else if(m-coef!=1&m-expn=0)coutcoef;3.4 else if(m-coef!=1&m-expn=1)coutcoefxcoef=1&m-expn=1)coutcoef=0)cout;3.7 elsecoutcoefxexpnexpnq-expn復(fù)制q到結(jié)果多項(xiàng)式（減法系數(shù)為q-coef的相反數(shù)）3.3.3.3 如果p-expnexpn復(fù)制p到結(jié)果多項(xiàng)式3.3.3.4 判斷后將項(xiàng)數(shù)+，插入新節(jié)點(diǎn)d；3.3.2 如果q為空，p仍存在，逐項(xiàng)將p復(fù)制到結(jié)果多項(xiàng)式。每進(jìn)行一次，項(xiàng)數(shù)+，p后移。3.

8、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-expn=q-expn) d-coef=p-coef+q-coef;d-expn=p-expn;p=p-next;

9、q=q-next;/加法 d-coef=p-coef-q-coef;d-expn=p-expn;p=p-next;q=q-next;/減法 3.3.3.2 p-expnq-expn d-coef=q-coef;d-expn=q-expn;q=q-next;/加法d-coef=-q-coef;d-expn=q-expn;q=q-next;/減法 3.3.3.3p-expnexpnd-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);/

10、加法 nMinus+;min.Insert(d);/減法 3.3.2 while(p)term* d=new term;d-coef=p-coef; 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=NU

11、LL; nAdd+;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-expn); 3.2 s=s-next; 4返回res

12、ult； 偽代碼描述：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*p-expn;指數(shù)為：p-expn-1;2.2 將新結(jié)點(diǎn)插入新鏈表；2.3 指針p后移。 偽代碼描述： 1. term* p=a.front-n

13、ext; 2. for(int i=0;iexpn) 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. 測試主函數(shù)流程：1開始進(jìn)行A-B的運(yùn)算設(shè)置多項(xiàng)式A的項(xiàng)數(shù)按照A的項(xiàng)數(shù)動(dòng)態(tài)申請coef1和expn1輸出相減的結(jié)果minus進(jìn)行對(duì)A求導(dǎo)數(shù)的運(yùn)算輸出A設(shè)置多項(xiàng)

14、式B的項(xiàng)數(shù)輸出求導(dǎo)的結(jié)果de按照B的項(xiàng)數(shù)動(dòng)態(tài)申請coef2和expn2輸入x的取值計(jì)算A在x處的取值并輸出輸出B結(jié)束進(jìn)行A+B的運(yùn)算輸出相加的結(jié)果add1測試條件：問題規(guī)模n的數(shù)量級(jí)為1A多項(xiàng)式每項(xiàng)的系數(shù)和指數(shù)分別為： B多項(xiàng)式每項(xiàng)的系數(shù)和指數(shù)分別為： X的值為：2運(yùn)行出來的結(jié)果是：測試結(jié)論：通過測試，本程序具有的功能有：多項(xiàng)式的建立、多項(xiàng)式的輸入與輸出、多項(xiàng)式的相加及相減，多項(xiàng)式求導(dǎo)以及多項(xiàng)式求值。4. 總結(jié) 1. 調(diào)試時(shí)出現(xiàn)的問題及解決的方法 輸出多項(xiàng)式的時(shí)候有些問題，但經(jīng)過查看是由于輸出時(shí)沒有將各種情況考慮全面的結(jié)果。 相加相減操作：在剛開始的時(shí)候，只考慮了p、q指針均非空的情況，計(jì)算的結(jié)果就出現(xiàn)了問題，但逐項(xiàng)的運(yùn)算后，會(huì)出現(xiàn)一個(gè)還非空但另一個(gè)已經(jīng)遍歷完畢的情況，故后又設(shè)計(jì)讓非空的鏈表繼續(xù)進(jìn)行運(yùn)算，解決了問題。 在插入結(jié)點(diǎn)的時(shí)候出現(xiàn)了一些問題，經(jīng)查看是尾插法運(yùn)用地并不熟練，后運(yùn)用頭插法將結(jié)點(diǎn)插入鏈表中，編完程序后，又仔細(xì)學(xué)習(xí)了尾