C++一元多項(xiàng)式計(jì)算問題-課程設(shè)計(jì)說明書.doc

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