一元稀疏多項(xiàng)式計(jì)算器

1、Good is good, but better carries it.精益求精，善益求善。一元稀疏多項(xiàng)式計(jì)算器一元稀疏多項(xiàng)式計(jì)算器云南大學(xué)軟件學(xué)院 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告 （本實(shí)驗(yàn)項(xiàng)目方案受“教育部人才培養(yǎng)模式創(chuàng)新實(shí)驗(yàn)區(qū)（X3108005）”項(xiàng)目資助） 實(shí)驗(yàn)難度： A B C 序號學(xué)號姓名成績120111120220111120 指導(dǎo)教師： （簽名）學(xué)期：2012秋季學(xué)期 任課教師: 實(shí)驗(yàn)題目: 一元稀疏多項(xiàng)式計(jì)算器 小 組 長: 聯(lián)系電話: 電子郵件: 完成提交時(shí)間：2012 年 11 月 10 日云南大學(xué)軟件學(xué)院2012學(xué)年 秋季 學(xué)期數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)成績考核表學(xué)號： 20111120 姓名： 本

2、人承擔(dān)角色： 算法設(shè)計(jì) 整體流程控制 評分項(xiàng)目評分指標(biāo)分值得分實(shí)驗(yàn)構(gòu)思（10%）1. 實(shí)驗(yàn)?zāi)康拿鞔_52. 實(shí)驗(yàn)內(nèi)容理解透徹、對實(shí)驗(yàn)所涉及到的知識點(diǎn)分析到位5實(shí)驗(yàn)設(shè)計(jì)（15%）1. 有對基本數(shù)據(jù)結(jié)構(gòu)的抽象數(shù)據(jù)類型定義52. 實(shí)驗(yàn)方案設(shè)計(jì)完整，數(shù)據(jù)結(jié)構(gòu)、算法選擇合理 53.算法結(jié)構(gòu)和程序功能模塊之間邏輯清晰、有相應(yīng)的流程圖5實(shí)驗(yàn)實(shí)現(xiàn)（25%）1. 代碼編寫規(guī)范、風(fēng)格統(tǒng)一、注釋清楚易讀 52. 程序運(yùn)行正常，測試結(jié)果正確153. 界面友好、易于操作、有較強(qiáng)的容錯(cuò)性5實(shí)驗(yàn)報(bào)告撰寫（10%）1. 內(nèi)容詳實(shí)無缺漏，文字流暢、圖表清楚52. 實(shí)驗(yàn)結(jié)果分析客觀、詳細(xì)，實(shí)驗(yàn)體會真實(shí)可信，對原實(shí)驗(yàn)方案的改進(jìn)和對實(shí)

3、驗(yàn)內(nèi)容的發(fā)散性思考5個(gè)人工作量（30%）1. 個(gè)人完成工作量152. 個(gè)人技術(shù)水平103. 團(tuán)隊(duì)合作精神5實(shí)驗(yàn)運(yùn)作（10%）1. 有一定用戶群52. 應(yīng)用前景分析5綜合得分： （滿分100分）指導(dǎo)教師： 年 月 日云南大學(xué)軟件學(xué)院2010學(xué)年 秋季 學(xué)期數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)成績考核表學(xué)號： 20111120 姓名： 本人承擔(dān)角色： 函數(shù)實(shí)現(xiàn) 整體流程控制 評分項(xiàng)目評分指標(biāo)分值得分實(shí)驗(yàn)構(gòu)思（10%）1. 實(shí)驗(yàn)?zāi)康拿鞔_52. 實(shí)驗(yàn)內(nèi)容理解透徹、對實(shí)驗(yàn)所涉及到的知識點(diǎn)分析到位5實(shí)驗(yàn)設(shè)計(jì)（15%）1. 有對基本數(shù)據(jù)結(jié)構(gòu)的抽象數(shù)據(jù)類型定義52. 實(shí)驗(yàn)方案設(shè)計(jì)完整，數(shù)據(jù)結(jié)構(gòu)、算法選擇合理 53.算法結(jié)構(gòu)和程序功能

4、模塊之間邏輯清晰、有相應(yīng)的流程圖5實(shí)驗(yàn)實(shí)現(xiàn)（25%）1. 代碼編寫規(guī)范、風(fēng)格統(tǒng)一、注釋清楚易讀 52. 程序運(yùn)行正常，測試結(jié)果正確153. 界面友好、易于操作、有較強(qiáng)的容錯(cuò)性5實(shí)驗(yàn)報(bào)告撰寫（10%）1. 內(nèi)容詳實(shí)無缺漏，文字流暢、圖表清楚52. 實(shí)驗(yàn)結(jié)果分析客觀、詳細(xì)，實(shí)驗(yàn)體會真實(shí)可信，對原實(shí)驗(yàn)方案的改進(jìn)和對實(shí)驗(yàn)內(nèi)容的發(fā)散性思考5個(gè)人工作量（30%）1. 個(gè)人完成工作量152. 個(gè)人技術(shù)水平103. 團(tuán)隊(duì)合作精神5實(shí)驗(yàn)運(yùn)作（10%）1. 有一定用戶群52. 應(yīng)用前景分析5綜合得分： （滿分100分）指導(dǎo)教師： 年 月 日（下面的內(nèi)容由學(xué)生填寫，格式統(tǒng)一為，字體: 楷體, 行距: 固定行距18，

5、字號: 小四，個(gè)人報(bào)告按下面每一項(xiàng)的百分比打分。難度A滿分70分，難度B滿分90分）一、【實(shí)驗(yàn)構(gòu)思（Conceive）】(10%)多項(xiàng)式計(jì)算器的呈現(xiàn)方式是用控制臺程序呈現(xiàn)，；多項(xiàng)式的加減乘以及求導(dǎo)的函數(shù)中利用鏈表保存頭結(jié)點(diǎn)以及循環(huán)結(jié)構(gòu)保存和輸出數(shù)據(jù)；還有利用一個(gè)簡單的降序排列的函數(shù)，在輸出時(shí)更加明了。二、【實(shí)驗(yàn)設(shè)計(jì)(Design)】(20%)在頭文件中申明變量，源文件中創(chuàng)建指數(shù)和系數(shù)的指針的頭結(jié)點(diǎn)，并為此申請空間。首先考慮指數(shù)為0,1和系數(shù)為0,1時(shí)的特殊情況的表示；然后利用SORT函數(shù)對輸出時(shí)進(jìn)行降序排列；其次就是加減乘以及求導(dǎo)函數(shù)的實(shí)現(xiàn)；最后是一個(gè)輸出界面的設(shè)計(jì)。三、【實(shí)現(xiàn)描述（Imple

6、ment）】(30%)/-函數(shù)原型說明-typedef struct Nodedouble xishu;int zhishu;/數(shù)據(jù)域/int data;struct Node* pnext;/指針域Node,*pNode;pNode phead=(pNode)malloc(sizeof(Node);/創(chuàng)建頭節(jié)點(diǎn)pNode creat_list(void);創(chuàng)建鏈表void traverse_list(pNode phead);/遍歷鏈表pNode sort(pNode phead);/對鏈表進(jìn)行降序排列pNode add(pNode phead1,pNode phead2)；/兩個(gè)多項(xiàng)式相加

7、pNode hebing(pNode phead)/合并同類項(xiàng)pNode multi(pNode phead1,pNode phead2)；/多項(xiàng)式相乘pNode sub(pNode phead1,pNode phead2)；/多項(xiàng)式相減/多項(xiàng)式求導(dǎo)沒有聲明和定義函數(shù)，而是直接卸載程序里了/-關(guān)鍵操作的實(shí)現(xiàn)-1.對鏈表的聲明和定義和對創(chuàng)建函數(shù)的定義。 #include "stdafx.h"#include "cpxNum.h"typedef struct Nodedouble xishu;int zhishu;/數(shù)據(jù)域/int data;struct N

8、ode* pnext;/指針域Node,*pNode;pNode creat_list(void)int len;int i;/int val;int zhishu;double xishu;pNode phead=(pNode)malloc(sizeof(Node);/分配了一個(gè)不存在有效數(shù)據(jù)的頭結(jié)點(diǎn)pNode ptail=phead;ptail->pnext=NULL;if(phead=NULL)cout<<"分配失敗<<endl;exit(-1);cout<<"請輸入想輸入多項(xiàng)式的項(xiàng)數(shù)"<<endl;ci

9、n>>len;for(i=0;i<len;i+)cout<<"請?輸º?入¨?第̨²"<<i+1<<"個(gè)?項(xiàng)?的Ì?系¦Ì數(shù)ºy的Ì?值¦Ì"<<endl;cin>>xishu;cout<<"請?輸º?入¨?第̨²"<<i+1<<"個(gè)?項(xiàng)?的

10、Ì?指?數(shù)ºy的Ì?值¦Ì"<<endl;cin>>zhishu;pNode pnew=(pNode)malloc(sizeof(Node);if(pnew=NULL) cout<<"分¤?配?失º¡ì敗㨹"<<endl; exit(-1);pnew->xishu=xishu;pnew->zhishu=zhishu;ptail->pnext=pnew;pnew->pnex

11、t=NULL;ptail=pnew;phead->zhishu=len;return phead;2.對多項(xiàng)式遍歷，排序，同類項(xiàng)合并的定義1. 多項(xiàng)式的遍歷/將多項(xiàng)式分為第一項(xiàng)和其余項(xiàng)兩部分考慮，另外考慮指數(shù)=0，指數(shù)=1，系數(shù)=1，系數(shù)=0等情況。void traverse_list(pNode phead)pNode p=phead->pnext; if(p->zhishu=0)cout<<p->xishu;elseif(p->zhishu=1)cout<<"("<<p->xishu<<

12、")"<<"x"else if(p->xishu=1) cout<<"x"<<""<<p->zhishu; elseif(p->xishu=0)cout<<"0"elsecout<<"("<<p->xishu<<")"<<"x"<<""<<p->zhishu

13、; p=p->pnext;while(p) if(p->zhishu=0)cout<<"+"<<p->xishu;elseif(p->zhishu=1)cout<<"x+"<<"("<<p->xishu<<")"else if(p->xishu=1) cout<<"+"<<"x"<<""<<p->

14、zhishu; elseif(p->xishu=0)cout<<"+0"elsecout<<"+"<<"("<<p->xishu<<")"<<"x"<<""<<p->zhishu; p=p->pnext; cout<<endl;return;2. 排序操作。/通過冒泡排序?qū)Χ囗?xiàng)式進(jìn)行降序排列。pNode sort(pNode phead)int

15、i,j;float xishu;int zhishu;pNode p,q,f;f=phead;int len=phead->zhishu;for(i=0,p=phead->pnext;i<len-1;i+,p=p->pnext)for(j=i+1,q=p->pnext;j<len;j+,q=q->pnext)if(p->zhishu<q->zhishu)xishu=p->xishu;zhishu=p->zhishu ;p->xishu=q->xishu;p->zhishu=q->zhishu;q-&

16、gt;xishu=xishu; q->zhishu=zhishu;return f;3. 合并排序/通過檢查將同類型合并，在加法，減法和乘法函數(shù)中會用到pNode hebing(pNode phead)pNode r,q,p,Q;for(q=phead->pnext;q!=NULL;q=q->pnext)/合?并¡é同ª?類¤¨¤項(xiàng)?for(p=q->pnext,r=q;p!=NULL;)if(q->zhishu=p->zhishu)/指?數(shù)ºy相¨¤等Ì&#

17、168;¨ 系¦Ì數(shù)ºy相¨¤加¨® q->xishu=q->xishu+p->xishu;r->pnext=p->pnext;Q=p;p=p->pnext;delete Q;/釋º¨ª放¤?pelser=r->pnext;p=p->pnext;return phead; 3.多項(xiàng)式的加，減，乘，求導(dǎo)，x代入值的實(shí)現(xiàn)1. 多項(xiàng)式的加法/創(chuàng)建一個(gè)新鏈表存儲新的多項(xiàng)式，開始對phead1和phead2進(jìn)行掃描，指數(shù)相同就相加。pNo

18、de add(pNode phead1,pNode phead2) pNode p1,p2,pTail,pnew; pNode phead3=(pNode)malloc(sizeof(Node); pTail=phead3; pTail->pnext=NULL; sort(phead1); sort(phead2); p1=phead1->pnext; p2=phead2->pnext; int i=0; while(p1&&p2) if(p1->zhishu>=p2->zhishu) if(p1->zhishu=p2->zhis

19、hu) pnew=new Node; pnew->xishu=p1->xishu+p2->xishu; pnew ->zhishu=p1->zhishu; pTail->pnext=pnew; pnew->pnext=NULL; pTail=pnew; p1=p1->pnext; p2=p2->pnext; else pnew=new Node; pnew->xishu=p1->xishu; pnew ->zhishu=p1->zhishu; pTail->pnext=pnew; pnew->pnext=

20、NULL; pTail=pnew; p1=p1->pnext; else pnew=new Node; pnew->xishu=p2->xishu; pnew ->zhishu=p2->zhishu; pTail->pnext=pnew; pnew->pnext=NULL; pTail=pnew;p2=p2->pnext; if(p1=NULL) pTail->pnext=p2; if(p2=NULL) pTail->pnext=p1; return phead3;2. 多項(xiàng)式的減法/道理與多項(xiàng)式加法相同，但是指數(shù)相同時(shí)，系數(shù)相減。p

21、Node sub(pNode phead1,pNode phead2)/減?法¤¡§函¡¥數(shù)ºy pNode p1,p2,pTail,pnew; pNode phead3=(pNode)malloc(sizeof(Node); pTail=phead3; pTail->pnext=NULL; sort(phead1); sort(phead2); p1=phead1->pnext; p2=phead2->pnext; while(p1&&p2) if(p1->zhishu>=p2->

22、zhishu) if(p1->zhishu=p2->zhishu) pnew=new Node; pnew->xishu=p1->xishu-p2->xishu; pnew ->zhishu=p1->zhishu; pTail->pnext=pnew; pnew->pnext=NULL; pTail=pnew; p1=p1->pnext; p2=p2->pnext; else pnew=new Node; pnew->xishu=p1->xishu; pnew ->zhishu=p1->zhishu; p

23、Tail->pnext=pnew; pnew->pnext=NULL; pTail=pnew; p1=p1->pnext; else pnew=new Node; pnew->xishu=-(p2->xishu); pnew ->zhishu=p2->zhishu; pTail->pnext=pnew; pnew->pnext=NULL; pTail=pnew; p2=p2->pnext; if(p1=NULL) pTail->pnext=p2; if(p2=NULL) pTail->pnext=p1; return ph

24、ead3;3. 多項(xiàng)式乘法/相當(dāng)于加法的多次操作。進(jìn)行嵌套循環(huán)解決此問題pNode multi(pNode phead1,pNode phead2)/乘?法¤¡§函¡¥數(shù)ºy int i,j;/i,j分¤?別Àe保À¡ê存ä?了¢?兩¢?個(gè)?鏈¢¡ä表À¨ª的Ì?長¡è度¨¨ pNode p1,p2,pTail; pNode phead3=(pNo

25、de)malloc(sizeof(Node); pTail=phead3; pTail->pnext=NULL; p1=phead1->pnext; while(p1) p2=phead2->pnext; while(p2) pNode q=(pNode)malloc(sizeof(Node); q->xishu=p1->xishu*p2->xishu; q->zhishu=p1->zhishu+p2->zhishu; q->pnext=phead3->pnext; phead3->pnext=q; phead3=q; p

26、2=p2->pnext; p1=p1->pnext; return pTail;4. 多項(xiàng)式求導(dǎo)/不停掃描多項(xiàng)式，對其進(jìn)行求導(dǎo)運(yùn)算，直至p=NULLphead=creat_list(); p=phead->pnext; while(p!=NULL) p->xishu=p->xishu*p->zhishu; p->zhishu=p->zhishu-1; p=p->pnext; 5. x賦值求結(jié)果。 p=phead1->pnext;cout<<"請?輸º?入¨?x的Ì?值¦&#

27、204;"<<endl;cin>>x;sum=0.0;y=1.0;while(p)for(;p->zhishu>0;p->zhishu-)y=y*x;sum=sum+y*(p->xishu);p=p->pnext;y=1.0;cout<<"結(jié)¨¢果?值¦Ì為a"<<endl;cout<<sum;四、【測試結(jié)果（Testing）】(10%)加法測試：正確減法測試：正確乘法測試：正確求導(dǎo)測試：正確四、【實(shí)驗(yàn)總結(jié)】(10%)（本部分應(yīng)包括：自

28、己在實(shí)驗(yàn)中完成的任務(wù)，注意組內(nèi)的任意一位同學(xué)都必須獨(dú)立完成至少一項(xiàng)接口的實(shí)現(xiàn)；對所完成實(shí)驗(yàn)的經(jīng)驗(yàn)總結(jié)、心得）1. 實(shí)驗(yàn)時(shí)，一個(gè)小組的同學(xué)應(yīng)該由一人操作，其他人一起來寫程序，這樣可以避免由于不同的同學(xué)的編程風(fēng)格的差異而導(dǎo)致一些很難發(fā)現(xiàn)的錯(cuò)誤，從而浪費(fèi)很多不必要的時(shí)間2. 實(shí)驗(yàn)之前一定要想好算法，不要盲目的直接就敲程序，這樣不僅會使效率低下還會使程序極易出現(xiàn)難以察覺的邏輯錯(cuò)誤，最好在敲程序之前畫流程圖將算法分析清楚，確保無誤后再敲程序3. 同學(xué)間的交流很重要，不同小組的同學(xué)也應(yīng)該多交流，這樣不僅可以大家之間互相取長補(bǔ)短，共同進(jìn)步，還可以避免很多錯(cuò)誤的出現(xiàn)五、【項(xiàng)目運(yùn)作描述（Operate）】(10

29、%)（本部分應(yīng)包括：項(xiàng)目的成本效益分析，應(yīng)用效果等的分析。）這個(gè)實(shí)驗(yàn)花時(shí)間比較長，在做實(shí)驗(yàn)的過程中我們也遇到了很多困難，為一個(gè)bug而糾結(jié)了很久，但是通過和同學(xué)的交流討論，我們發(fā)現(xiàn)并解決了問題。在克服困難的過程中，我們學(xué)到了很多的東西，也積累了很多的經(jīng)驗(yàn)，可以為以后的學(xué)習(xí)和實(shí)驗(yàn)中打下基礎(chǔ)。我們的程序基本實(shí)現(xiàn)了實(shí)驗(yàn)指導(dǎo)上的要求，但是對于健壯性的考慮還不夠，我們一定會在以后的實(shí)驗(yàn)中，好好努力，盡最大的努力將程序完善六、【代碼】(10%)（本部分應(yīng)包括：完整的代碼及充分的注釋。 注意紙質(zhì)的實(shí)驗(yàn)報(bào)告無需包括此部分。格式統(tǒng)一為，字體: Georgia , 行距: 固定行距12，字號: 小五）int ma

30、in() int choose;double x,sum,y; pNode phead1=NULL; pNode phead2=NULL; pNode p,p2,phead,phead3=NULL; /pNode creat_list(void);cout<<"*"<<endl;cout<<" 歡?迎®-使º1用®?我¨°們?的Ì?多¨¤項(xiàng)?式º?計(jì)?算?器¡Â "<<endl;cout<&l

31、t;" 請?選?擇?你?想?要°a的Ì?操¨´作Á¡Â "<<endl;cout<<" 1.加¨®法¤¡§運(yùn)?算? 2.減?法¤¡§運(yùn)?算? "<<endl;cout<<" 3.乘?法¤¡§運(yùn)?算? 4.求¨®導(dǎo)Ì?運(yùn)?算? "<<endl;cin>>cho

32、ose;switch(choose) case 1: phead1=creat_list(); /phead2=creat_list(); sort(phead1); phead2=creat_list(); sort(phead2); cout<<"整?理¤¨ª后¨®的Ì?第̨²一°?個(gè)?多¨¤項(xiàng)?式º?：êo"<<endl; traverse_list(phead1);cout<<"整

33、?理¤¨ª后¨®的Ì?第̨²二t個(gè)?多¨¤項(xiàng)?式º?：êo"<<endl; traverse_list(phead2);/add(phead1,phead2); phead1=add(phead1,phead2);/sort(phead1); phead1= hebing(phead1); cout<<"最Á?終?的Ì?結(jié)¨¢果?：êo"<<endl

34、;traverse_list(phead1); break; case 2: phead1=creat_list(); /phead2=creat_list(); sort(phead1); phead2=creat_list(); sort(phead2); cout<<"整?理¤¨ª后¨®的Ì?第̨²一°?個(gè)?多¨¤項(xiàng)?式º?：êo"<<endl; traverse_list(phead1);cout<

35、;<"整?理¤¨ª后¨®的Ì?第̨²二t個(gè)?多¨¤項(xiàng)?式º?：êo"<<endl; traverse_list(phead2); phead1=sub(phead1,phead2); phead1= hebing(phead1); cout<<"最Á?終?的Ì?結(jié)¨¢果?：êo"<<endl; traverse_list(phead1); break; case 3: phead1=creat_list(); /phead2=creat_list(); sort(phead1); phead2=creat_list(); sort(phead2); cout<<"整?理¤¨ª后¨®的Ì?第̨²一&#