1、.云南大學軟件學院 數據結構實驗報告 （本實驗項目方案受“教育部人才培養模式創新實驗區（X3108005）”項目資助） 實驗難度： A B C 序號學號姓名成績120111120220111120 指導教師： （簽名）學期：2012秋季學期 任課教師: 實驗題目: 一元稀疏多項式計算器 小 組 長: 聯系電話: 電子郵件: 完成提交時間：2012 年 11 月 10 日云南大學軟件學院2012學年 秋季 學期數據結構實驗成績考核表學號： 20111120 姓名： 本人承擔角色： 算法設計 整體流程控制 評分項目評分指標分值得分實驗構思（10%）1. 實驗目的明確52. 實驗內容理解透徹、對實驗

2、所涉及到的知識點分析到位5實驗設計（15%）1. 有對基本數據結構的抽象數據類型定義52. 實驗方案設計完整，數據結構、算法選擇合理 53.算法結構和程序功能模塊之間邏輯清晰、有相應的流程圖5實驗實現（25%）1. 代碼編寫規范、風格統一、注釋清楚易讀 52. 程序運行正常，測試結果正確153. 界面友好、易于操作、有較強的容錯性5實驗報告撰寫（10%）1. 內容詳實無缺漏，文字流暢、圖表清楚52. 實驗結果分析客觀、詳細，實驗體會真實可信，對原實驗方案的改進和對實驗內容的發散性思考5個人工作量（30%）1. 個人完成工作量152. 個人技術水平103. 團隊合作精神5實驗運作（10%）1.

3、有一定用戶群52. 應用前景分析5綜合得分： （滿分100分）指導教師： 年 月 日云南大學軟件學院2010學年 秋季 學期數據結構實驗成績考核表學號： 20111120 姓名： 本人承擔角色： 函數實現 整體流程控制 評分項目評分指標分值得分實驗構思（10%）1. 實驗目的明確52. 實驗內容理解透徹、對實驗所涉及到的知識點分析到位5實驗設計（15%）1. 有對基本數據結構的抽象數據類型定義52. 實驗方案設計完整，數據結構、算法選擇合理 53.算法結構和程序功能模塊之間邏輯清晰、有相應的流程圖5實驗實現（25%）1. 代碼編寫規范、風格統一、注釋清楚易讀 52. 程序運行正常，測試結果正確

4、153. 界面友好、易于操作、有較強的容錯性5實驗報告撰寫（10%）1. 內容詳實無缺漏，文字流暢、圖表清楚52. 實驗結果分析客觀、詳細，實驗體會真實可信，對原實驗方案的改進和對實驗內容的發散性思考5個人工作量（30%）1. 個人完成工作量152. 個人技術水平103. 團隊合作精神5實驗運作（10%）1. 有一定用戶群52. 應用前景分析5綜合得分： （滿分100分）指導教師： 年 月 日（下面的內容由學生填寫，格式統一為，字體: 楷體, 行距: 固定行距18，字號: 小四，個人報告按下面每一項的百分比打分。難度A滿分70分，難度B滿分90分）一、【實驗構思（Conceive）】(10%)

5、多項式計算器的呈現方式是用控制臺程序呈現，；多項式的加減乘以及求導的函數中利用鏈表保存頭結點以及循環結構保存和輸出數據；還有利用一個簡單的降序排列的函數，在輸出時更加明了。二、【實驗設計(Design)】(20%)在頭文件中申明變量，源文件中創建指數和系數的指針的頭結點，并為此申請空間。首先考慮指數為0,1和系數為0,1時的特殊情況的表示；然后利用SORT函數對輸出時進行降序排列；其次就是加減乘以及求導函數的實現；最后是一個輸出界面的設計。三、【實現描述（Implement）】(30%)/-函數原型說明-typedef struct Nodedouble xishu;int zhishu;/數

6、據域/int data;struct Node* pnext;/指針域Node,*pNode;pNode phead=(pNode)malloc(sizeof(Node);/創建頭節點pNode creat_list(void);創建鏈表void traverse_list(pNode phead);/遍歷鏈表pNode sort(pNode phead);/對鏈表進行降序排列pNode add(pNode phead1,pNode phead2)；/兩個多項式相加pNode hebing(pNode phead)/合并同類項pNode multi(pNode phead1,pNode phe

7、ad2)；/多項式相乘pNode sub(pNode phead1,pNode phead2)；/多項式相減/多項式求導沒有聲明和定義函數，而是直接卸載程序里了/-關鍵操作的實現-1.對鏈表的聲明和定義和對創建函數的定義。 #include "stdafx.h"#include "cpxNum.h"typedef struct Nodedouble xishu;int zhishu;/數據域/int data;struct Node* pnext;/指針域Node,*pNode;pNode creat_list(void)int len;int i;/i

8、nt val;int zhishu;double xishu;pNode phead=(pNode)malloc(sizeof(Node);/分配了一個不存在有效數據的頭結點pNode ptail=phead;ptail->pnext=NULL;if(phead=NULL)cout<<"分配失敗<<endl;exit(-1);cout<<"請輸入想輸入多項式的項數"<<endl;cin>>len;for(i=0;i<len;i+)cout<<"請?輸º?入

9、68;?第̨²"<<i+1<<"個?項?的Ì?系¦Ì數ºy的Ì?值¦Ì"<<endl;cin>>xishu;cout<<"請?輸º?入¨?第̨²"<<i+1<<"個?項?的Ì?指?數ºy的Ì?值¦Ì"<<endl;cin>&

10、gt;zhishu;pNode pnew=(pNode)malloc(sizeof(Node);if(pnew=NULL) cout<<"分¤?配?失º¡ì敗㨹"<<endl; exit(-1);pnew->xishu=xishu;pnew->zhishu=zhishu;ptail->pnext=pnew;pnew->pnext=NULL;ptail=pnew;phead->zhishu=len;return phead;2.對多項式遍歷，排序，同

11、類項合并的定義1. 多項式的遍歷/將多項式分為第一項和其余項兩部分考慮，另外考慮指數=0，指數=1，系數=1，系數=0等情況。void traverse_list(pNode phead)pNode p=phead->pnext; if(p->zhishu=0)cout<<p->xishu;elseif(p->zhishu=1)cout<<"("<<p->xishu<<")"<<"x"else if(p->xishu=1) cout<

12、<"x"<<""<<p->zhishu; elseif(p->xishu=0)cout<<"0"elsecout<<"("<<p->xishu<<")"<<"x"<<""<<p->zhishu; p=p->pnext;while(p) if(p->zhishu=0)cout<<"+&qu

13、ot;<<p->xishu;elseif(p->zhishu=1)cout<<"x+"<<"("<<p->xishu<<")"else if(p->xishu=1) cout<<"+"<<"x"<<""<<p->zhishu; elseif(p->xishu=0)cout<<"+0"elsecout&l

14、t;<"+"<<"("<<p->xishu<<")"<<"x"<<""<<p->zhishu; p=p->pnext; cout<<endl;return;2. 排序操作。/通過冒泡排序對多項式進行降序排列。pNode sort(pNode phead)int i,j;float xishu;int zhishu;pNode p,q,f;f=phead;int len=phead->

15、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->xishu=xishu; q->zhishu=zhishu;return f;3. 合并排序/通過檢查將同類型合并，在

16、加法，減法和乘法函數中會用到pNode hebing(pNode phead)pNode r,q,p,Q;for(q=phead->pnext;q!=NULL;q=q->pnext)/合?并¡é同ª?類¤¨¤項?for(p=q->pnext,r=q;p!=NULL;)if(q->zhishu=p->zhishu)/指?數ºy相¨¤等̨¨ 系¦Ì數ºy相¨¤加¨® q->

17、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.多項式的加，減，乘，求導，x代入值的實現1. 多項式的加法/創建一個新鏈表存儲新的多項式，開始對phead1和phead2進行掃描，指數相同就相加。pNode add(pNode phead1,pNode phead2) pNode p1,p2,pTail,pnew; pNode p

18、head3=(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->zhishu) pnew=new Node; pnew->xishu=p1->xishu+p2->xishu; pnew

19、 ->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=NULL; pTail=pnew; p1=p1->pnext; else pnew=new Node; pnew->x

20、ishu=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. 多項式的減法/道理與多項式加法相同，但是指數相同時，系數相減。pNode sub(pNode phead1,pNode phead2)/減?法¤¡§函¡&

21、#165;數º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->zhishu) if(p1->zhishu=p2->zhishu) pnew=new Node; pnew->x

22、ishu=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=NULL; pTail=pnew; p1=p1->p

23、next; 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;3. 多項式乘法/相當于加法的多次操作。進行嵌套循環解決此問題pNode multi(pNode phead1,pNod

24、e phead2)/乘?法¤¡§函¡¥數ºy int i,j;/i,j分¤?別Àe保À¡ê存ä?了¢?兩¢?個?鏈¢¡ä表À¨ª的Ì?長¡è度¨¨ pNode p1,p2,pTail; pNode phead3=(pNode)malloc(sizeof(Node); pTail=phead3; pTail->pnext=NULL; p1=ph

25、ead1->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; p2=p2->pnext; p1=p1->pnext; return pTail;4. 多項式求導/不停掃描多項式，對其

26、進行求導運算，直至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賦值求結果。 p=phead1->pnext;cout<<"請?輸º?入¨?x的Ì?值¦Ì"<<endl;cin>>x;sum=0.0;y=1.0;while(p)for(;p-

27、>zhishu>0;p->zhishu-)y=y*x;sum=sum+y*(p->xishu);p=p->pnext;y=1.0;cout<<"結¨¢果?值¦Ì為a"<<endl;cout<<sum;四、【測試結果（Testing）】(10%)加法測試：正確減法測試：正確乘法測試：正確求導測試：正確四、【實驗總結】(10%)（本部分應包括：自己在實驗中完成的任務，注意組內的任意一位同學都必須獨立完成至少一項接口的實現；對所完成實驗的經驗總結、心得）1. 實驗時，一個小組

28、的同學應該由一人操作，其他人一起來寫程序，這樣可以避免由于不同的同學的編程風格的差異而導致一些很難發現的錯誤，從而浪費很多不必要的時間2. 實驗之前一定要想好算法，不要盲目的直接就敲程序，這樣不僅會使效率低下還會使程序極易出現難以察覺的邏輯錯誤，最好在敲程序之前畫流程圖將算法分析清楚，確保無誤后再敲程序3. 同學間的交流很重要，不同小組的同學也應該多交流，這樣不僅可以大家之間互相取長補短，共同進步，還可以避免很多錯誤的出現五、【項目運作描述（Operate）】(10%)（本部分應包括：項目的成本效益分析，應用效果等的分析。）這個實驗花時間比較長，在做實驗的過程中我們也遇到了很多困難，為一個bu

29、g而糾結了很久，但是通過和同學的交流討論，我們發現并解決了問題。在克服困難的過程中，我們學到了很多的東西，也積累了很多的經驗，可以為以后的學習和實驗中打下基礎。我們的程序基本實現了實驗指導上的要求，但是對于健壯性的考慮還不夠，我們一定會在以后的實驗中，好好努力，盡最大的努力將程序完善六、【代碼】(10%)（本部分應包括：完整的代碼及充分的注釋。 注意紙質的實驗報告無需包括此部分。格式統一為，字體: Georgia , 行距: 固定行距12，字號: 小五）int main() int choose;double x,sum,y; pNode phead1=NULL; pNode phead2=N

30、ULL; pNode p,p2,phead,phead3=NULL; /pNode creat_list(void);cout<<"*"<<endl;cout<<" 歡?迎®-使º1用®?我¨°們?的Ì?多¨¤項?式º?計?算?器¡Â "<<endl;cout<<" 請?選?擇?你?想?要°a的Ì?操¨´作Á¡

31、4; "<<endl;cout<<" 1.加¨®法¤¡§運?算? 2.減?法¤¡§運?算? "<<endl;cout<<" 3.乘?法¤¡§運?算? 4.求¨®導Ì?運?算? "<<endl;cin>>choose;switch(choose) case 1: phead1=creat_list(); /phead2=creat_lis

32、t(); sort(phead1); phead2=creat_list(); sort(phead2); cout<<"整?理¤¨ª后¨®的Ì?第̨²一°?個?多¨¤項?式º?：êo"<<endl; traverse_list(phead1);cout<<"整?理¤¨ª后¨®的Ì?第̨²二t個?多

33、¨¤項?式º?：êo"<<endl; traverse_list(phead2);/add(phead1,phead2); phead1=add(phead1,phead2);/sort(phead1); phead1= hebing(phead1); cout<<"最Á?終?的Ì?結¨¢果?：êo"<<endl;traverse_list(phead1); break; case 2: phead1=creat_list(); /phea

34、d2=creat_list(); sort(phead1); phead2=creat_list(); sort(phead2); cout<<"整?理¤¨ª后¨®的Ì?第̨²一°?個?多¨¤項?式º?：êo"<<endl; traverse_list(phead1);cout<<"整?理¤¨ª后¨®的Ì?第̨

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