C++一元多項式計算問題-課程設計說明書.doc

學 院課程設計說明書題目一元多項式計算問題系(部)計算機科學與技術系專業(yè)(班級)計算機科學與技術專業(yè)姓名學號指導教師起止日期第十三、十四周課程設計任務書課程名稱：數(shù)據(jù)結構與算法設計題目：一元多項式計算問題已知技術參數(shù)和設計要求：問題描述：設計一個稀疏多項式簡單計算器基本要求：(1)輸入并分別建立多項式A和B(2)輸入輸出多項式，輸出形式為整數(shù)序列：n,c1,e1,c2,e2，其中n是多項式的項數(shù)，ci和ei是第i項的系數(shù)和指數(shù)，序列按指數(shù)降序排列(3)完成兩個多項式的相加、相減，并將結果輸出；測試數(shù)據(jù)：(1) A+B A= 3x14-8x8+6x2+2 B=2x10+4x8+-6x2 (2) A-B A=11x14+3x10+2x8+10x6+5 B=2x14+3x8+5x6+7(3) A+B A=x3+x1 B=-x3-x1(4) A+B A=0 B=x7+x5+x3+x1(5) A-B A=100x100+50x50+20x20+x B=10x100+10x50+10x20+x選作內容：（1）.多項式在x=1時的運算結果（2）求多項式A和B的乘積設計工作量：40課時工作計劃：班級：計科3班 指導教師：劉鋼欽周次星期地點設計方式13星期一1-2節(jié)A多1講授內容星期二3-4節(jié)科1608答疑星期二5-8節(jié)1403上機調試星期三1-4節(jié)科1608答疑星期四1-4節(jié)1404上機調試星期四5-8節(jié)科1608答疑1414星期二3-4節(jié)科1608答疑星期二5-8節(jié)1403上機調試星期三1-4節(jié)科1608答疑星期四1-4節(jié)1404上機調試星期四5-8節(jié)科1608答疑星期四9-10節(jié)1403答辯指導教師簽名：日期：教研室主任簽名： 日期：系主任簽名： 日期：長沙學院課程設計鑒定表姓名學號專業(yè)計算機科學與技術專業(yè)班級設計題目一元多項式計算問題指導教師指導教師意見：評定等級： 教師簽名： 日期： 答辯小組意見：評定等級：答辯小組長簽名：日期：教研室意見：教研室主任簽名： 日期： 系（部）意見：系主任簽名：日期：說明課程設計成績分“優(yōu)秀”、“良好”、“及格”、“不及格”四類；摘要本文是關于一個一元稀疏多項式計算器的問題。一元稀疏多項式計算內容包括輸入并建立多項式,多項式相加，多項式求值，多項式求乘積以及輸出多項式。本程序運用面向對象程序設計方法，使用C+語言，利用Microsoft Visual C+ 6.0開發(fā)工具，還有數(shù)據(jù)結構課中學到的鏈式存儲結構，存儲一元稀疏多項式，從而實現(xiàn)程序的基本功能。在程序中定義了各種類型的運算的模塊，通過主程序的調用來完成它們之間的配合，進而使得一元稀疏多項式計算器的順利運行。關鍵詞：數(shù)據(jù)結構；一元稀疏多項式；鏈表； C+語言目錄1 設計內容與要求 12.設計說明 1 2.1 問題描述與功能設計1 2.2 數(shù)據(jù)結構與算法1 2.3 函數(shù)定義3 2.4 界面設計4 2.5 編碼5 2.6 測試103 總結14參考文獻 15附錄A 源代碼16V設計內容與要求設計內容：設計一個稀疏多項式簡單計算器，能夠進行簡單的基本運算。如：多項式相加、多項式相減、多項式求值等等?；疽螅?1)輸入并分別建立多項式A和B(2)輸入輸出多項式，輸出形式為整數(shù)序列：n,c1,e1,c2,e2，其中n是多項式的項數(shù)，ci和ei是第i項的系數(shù)和指數(shù)，序列按指數(shù)降序排列(3)完成兩個多項式的相加、相減，并將結果輸出；創(chuàng)新要求：（1）.多項式在x=1時的運算結果（2）求多項式A和B的乘積2.設計說明2.1 問題描述與功能設計本程序要求能夠實現(xiàn)從鍵盤鍵入兩個多項式的系數(shù)、指數(shù)相關數(shù)據(jù)后，能夠進行多項式輸出、多項式相加、多項式相減、多項式求值、多項式求積的運算。2.2 數(shù)據(jù)結構與算法數(shù)據(jù)結構多項式的邏輯結構：視為線性表 p(x)=3x14-8x8+6x2+2數(shù)據(jù)元素 (coef,exp) 表示多項式項 coefXexp ，coef是該項的系數(shù)，exp是變元X的指數(shù)。為了實現(xiàn)任意多項式的運算，因此選擇單鏈表的結構體，它有一個系數(shù)，指數(shù)，下一個指針3個成員。算法多項式的輸入與建立調用CreatePolyn（）函數(shù)建立鏈表，將多項式每一項的系數(shù)與指數(shù)作為鏈表一個結點的數(shù)據(jù)，按照指示輸入每一項的系數(shù)與指數(shù)時，將調用Insert（）函數(shù)，將輸入的結點信息按指數(shù)降序排列的方式插入到之前建立的鏈表中，并合并同類項。依次輸入、建立一元多項式pa和pb。如下圖。多項式的輸出 調用PrintPolyn（）函數(shù)將多項式鏈表中的結點數(shù)據(jù)按照一元多項式的格式(如：6x5+3x3+7x+3)輸出到屏幕上。兩個多項式的加法 調用AddPolyn（）函數(shù)直接對兩個多項式的鏈表的結點成員的系數(shù)與指數(shù)按照數(shù)學中多項式相加的原則進行操作。其中要調用compare（）函數(shù)對兩個多項式的指數(shù)或是項數(shù)進行比較。相加所得的多項式存放到新建的第三個多項式中。再對第三個多項式輸出即可。兩個多項式的減法調用SubtractPolyn（）函數(shù)對兩個多項式減法運算。首先對要減的多項式的系數(shù)求反，接著調用AddPolyn（）函數(shù)對處理后的多項式相加即兩個多項式的相減。所得的多項式存放到新建的第三個多項式中，再對第三個多項式輸出即可。多項式的求值調用ValuePolyn（）函數(shù)對多項式求值。在用戶輸入X的值后，對鏈表每個結點的數(shù)據(jù)進行求值，然后求和即多項式在X為某一值的值。其中用到C語言中的數(shù)學函數(shù)：pow。其功能為計算x的y次冪，所在頭文件：math.h。兩個多項式的乘法調用MultiplyPolyn（）函數(shù)對兩個多項式進行乘法運算。根據(jù)數(shù)學知識，依次用一個多項式的每一項乘以另一個多項式的每一項，再求和、合并同類項即兩個多項式的乘積。當中用了多兩個多項式的while循環(huán)，以確保兩個多項式的每一項都得到相應的運算，每一次運算后調用Insert()函數(shù)把乘積插入到新建的鏈表中，以得到一個結點信息按指數(shù)降序排列的方式排列，并以合并同類項的鏈表。2.3 函數(shù)定義為了程序功能的順利實現(xiàn)，在本程序中定義了如下函數(shù)：函數(shù)名 功能Insert() 鏈表結點數(shù)據(jù)的插入與排序CreatePolyn() 鏈表頭結點的創(chuàng)建DestroyPolyn() 鏈表的銷毀PrintPolyn() 鏈表數(shù)據(jù)的多項式形象化輸出Compare() 兩個多項式的指數(shù)或是項數(shù)進行比較AddPolyn() 兩個多項式的加法SubtractPolyn() 兩個多項式的減法ValuePolyn() 多項式的求值MultiplyPolyn() 兩個多項式的乘法desktop() 程序界面的實現(xiàn)2.4 界面設計程序數(shù)據(jù)初始界面： 程序操作主界面：2.5 編碼鏈表建立的函數(shù),該函數(shù)在多項式信息輸入時按照指數(shù)降序排列建立鏈表，并在出現(xiàn)同類項時合并。void Insert(Polyn p,Polyn h) if(p-coe=0) delete p; /當前結點的coe成員等于0的時候刪除當前結點 elsePolyn q1,q2;q1=h;q2=h-next;while(q2&p-expexp) /查找插入位置 q1=q2;q2=q2-next;if(q2&p-exp=q2-exp) /將指數(shù)相同相合并 q2-coe+=p-coe;delete p;if(!q2-coe) q1-next=q2-next;delete q2;else/指數(shù)為新時將結點插入 p-next=q2;q1-next=p;鏈表信息按照多項式形式輸出。void PrintPolyn(Polyn P) Polyn q=P-next; int flag=1; /項數(shù)計數(shù)器if(!q) /若多項式為空，輸出0cout0; coutcoe0&flag!=1) coutcoe!=1&q-coe!=-1) /系數(shù)非1或-1的普通情況coutcoe; if(q-exp=1) coutexp) coutXexp;elseif(q-coe=1) 系數(shù)為1的特殊情況if(!q-exp) coutexp=1) coutX;/指數(shù)等于一else coutXexp;if(q-coe=-1) 系數(shù)為-1的特殊情況情況if(!q-exp) coutexp=1) cout-X; /指數(shù)等于一else cout-Xexp;q=q-next; /當前指針指向下一結點flag+;/項序數(shù)自加1coutexpb-exp) return 1;當b多項式不存在或者a多項式的指數(shù)大于b的的時候，返回1else if(!a|a-expexp) return -1; 當a多項式不存在或者b多項式的指數(shù)大于a的的時候，返回-1else return 0;/其他情況返回0else if(!a&b) return -1; /a多項式已空，但b多項式非空else return 1; /b多項式已空，但a多項式非空Polyn AddPolyn(Polyn pa,Polyn pb)Polyn qa=pa-next;Polyn qb=pb-next;Polyn headc,hc,qc;hc=new Polynomial;/建立一個新的結點hc-next=NULL;headc=hc;while(qa|qb)qc=new Polynomial;/新建一個結點switch(compare(qa,qb)/調用compare函數(shù)對兩個多項式進行比較case 1:/ a多項式的指數(shù)大于b的qc-coe=qa-coe;qc-exp=qa-exp;qa=qa-next;break;case 0:/有同類項則合并 qc-coe=qa-coe+qb-coe;qc-exp=qa-exp;qa=qa-next;qb=qb-next;break;case -1: a多項式的指數(shù)小于b的qc-coe=qb-coe;qc-exp=qb-exp;qb=qb-next;break; if(qc-coe!=0) /當相加系數(shù)不為0時qc-next=hc-next;hc-next=qc;hc=qc;else delete qc; /當相加系數(shù)為0時，釋放該結點return headc;兩個多項式的減法。兩個多項式的減法是建立在加法的的基礎上，對要減的多項式的系數(shù)求反，接著調用AddPolyn（）函數(shù)對處理后的多項式相加即兩個多項式的相減Polyn SubtractPolyn(Polyn pa,Polyn pb)Polyn h=pb;Polyn p=pb-next;/新建一個結點作為pb的后繼結點Polyn pd;while(p)/當結點存在時，對所有coe數(shù)據(jù)求反 p-coe*=-1;p=p-next;pd=AddPolyn(pa,h);/調用加法函數(shù)for(p=h-next;p;p=p-next) /恢復pb的系數(shù) p-coe*=-1;return pd;多項式求值函數(shù)。當中運用到了C語言中的數(shù)學函數(shù)：pow。其功能為計算x的y次冪，所在頭文件：math.h。float ValuePolyn(Polyn head,float x)Polyn p; p=head-next; float result=0; while(p!=NULL) /當前結點信息存在時，對其求值并累加到前驅結點的值 result+=(p-coe)*(float)pow(x,p-exp); p=p-next; return result; 兩個多項式的乘法Polyn MultiplyPolyn(Polyn pa,Polyn pb)Polyn hf,pf;/Polyn qa=pa-next; /新建一個結點作為pa的后繼結點Polyn qb=pb-next; /新建一個結點作為pb的后繼結點hf=new Polynomial;hf-next=NULL;while(qa)/使用while循環(huán)，使得多項式的每項得以運算qb=pb-next;while(qb)pf=new Polynomial;pf-coe=qa-coe*qb-coe;pf-exp=qa-exp+qb-exp;Insert(pf,hf);/調用插入函數(shù)，將新的結點插入到新建鏈表中，并合并同類項qb=qb-next;qa=qa-next;return hf;/返回所得鏈表的頭指針2.6 測試測試軟件：Microsoft Visual C+ 6.0測試的數(shù)據(jù)：(1) A+B A= 3x14-8x8+6x2+2 B=2x10+4x8+-6x2(2) A-B A=11x14+3x10+2x8+10x6+5 B=2x14+3x8+5x6+7(3) A+B A=x3+x1 B=-x3-x1(4) A+B A=0 B=x7+x5+x3+x1(5) A-B A=100x100+50x50+20x20+x B=10x100+10x50+10x20+x(6) A*B A= 5x6+4x5+3x4 B= 6x6+5x5 (7) A= 5x6+4x5+3x4 X=2測試過程與結果：(1) A= 3x14-8x8+6x2+2 B=2x10+4x8+-6x2 A+B=3x14+2x10-4x8+2 (2) A=11x14+3x10+2x8+10x6+5 B=2x14+3x8+5x6+7 A-B=9x14+3x10-x8+5x6-2 (3) A=x3+x1 B=-x3-x1A+B=0 (4) A=0 B=x7+x5+x3+x1A+B=x7+x5+x3+x (5)A=100x100+50x50+20x20+x B=10x100+10x50+10x20+xA-B=90x100+40x50+10x20 (6)A= 5x6+4x5+3x4 B= 6x6+5x5 A*B =30x12+49x11+38x10+15x9 (7)A= 5x6+4x5+3x4 X=2A=4963 總結本次課程設計中，通過對一元多項式計算問題的解決，不僅讓我對數(shù)據(jù)結構學到的知識得到溫習，而且讓我在實踐的過程中隊所學知識得到了鞏固。實驗設計的過程中，堅持“學以致用”的原則，讓我充分利用所學的理論知識進行相對復雜的應用設計，以進一步提高綜合能力和創(chuàng)新實踐能力，讓我在課堂教學中所得進一步升華。最后我要衷心的感謝所有給予我?guī)椭椭笇У睦蠋熀屯瑢W,沒有他們的幫助我的程序也不會完成得這么順利!參考文獻1 王挺，周會平，賈麗麗，許錫山. C+程序設計M. 北京：清華大學出版社，20052 嚴蔚敏，吳偉民. 數(shù)據(jù)結構（C語言版）M. 北京：清華大學出版社，2005.3 李根強. 數(shù)據(jù)結構（C+版）習題解答及實訓指導M. 北京：中國水利水電出版社，2009.附錄A 源代碼19#include#include #include typedef struct Polynomialint coe;int exp;struct Polynomial *next;*Polyn,Polynomial; void Insert(Polyn p,Polyn h) if(p-coe=0) delete p; elsePolyn q1,q2;q1=h;q2=h-next;while(q2&p-expexp) q1=q2;q2=q2-next;if(q2&p-exp=q2-exp) q2-coe+=p-coe;delete p;if(!q2-coe) q1-next=q2-next;delete q2;else p-next=q2;q1-next=p;Polyn CreatePolyn(Polyn head,int m)int i;Polyn p;p=head=new Polynomial;head-next=NULL;for(i=0;im;i+)p=new Polynomial;cout請輸入第i+1p-coe;coutp-exp;Insert(p,head);return head;void DestroyPolyn(Polyn p)Polyn t;while(p!=NULL)t=p;p=p-next;delete t;void PrintPolyn(Polyn P) Polyn q=P-next; int flag=1;if(!q) cout0; coutcoe0&flag!=1) coutcoe!=1&q-coe!=-1)coutcoe; if(q-exp=1) coutexp) coutXexp;elseif(q-coe=1)if(!q-exp) coutexp=1) coutX;else coutXexp;if(q-coe=-1)if(!q-exp) coutexp=1) cout-X; else cout-Xexp;q=q-next; flag+;coutexpb-exp) return 1;else if(!a|a-expexp) return -1;else return 0;else if(!a&b) return -1;else return 1;Polyn AddPolyn(Polyn pa,Polyn pb)Polyn qa=pa-next;Polyn qb=pb-next;Polyn headc,hc,qc;hc=new Polynomial;hc-next=NULL;headc=hc;while(qa|qb)qc=new Polynomial;switch(compare(qa,qb)case 1:qc-coe=qa-coe;qc-exp=qa-exp;qa=qa-next;break;case 0: qc-coe=qa-coe+qb-coe;qc-exp=qa-exp;qa=qa-next;qb=qb-next;break;case -1:qc-coe=qb-coe;qc-exp=qb-exp;qb=qb-next;break; if(qc-coe!=0)qc-next=hc-next;hc-next=qc;hc=qc;else delete qc;return headc;Polyn SubtractPolyn(Polyn pa,Polyn pb)Polyn h=pb;Polyn p=pb-next;Polyn pd;while(p) p-coe*=-1;p=p-next;pd=AddPolyn(pa,h);for(p=h-next;p;p=p-next) p-coe*=-1;return pd;float ValuePolyn(Polyn head,float x)Polyn p; p=head-next; float result=0; while(p!=NULL) result+=(p-coe)*(float)pow(x,p-exp); p=p-next; return result; Polyn MultiplyPolyn(Polyn pa,Polyn pb)Polyn hf,pf;Polyn qa=pa-next;Polyn qb=pb-next;hf=new Polynomial;hf-next=NULL;while(qa)qb=pb-next;while(qb)pf=new Polynomial;pf-coe=qa-coe*qb-coe;pf-exp=qa-exp+qb-exp;Insert(pf,hf);qb=qb-next;qa=qa-next;return hf;void desktop()system(cls);cout 一元多項式的計算endl;cout*endl;cout* 1.輸出多項式a和b *endl;cout* 2.建立多項式a+b *endl;cout* 3.建立多項式a-b *endl;cout* 4.計算多項式a的值 *endl;cout* 5.建立多項式a*b *endl;cout* 6.重新建立多項式a和b *endl;cout* 7.退出 *endl;cout*endl;cout執(zhí)行操作:;void main()int m,n;float x,result;c