算法分析與設(shè)計的課程設(shè)計(一元多項式的加法、減法、乘法的實現(xiàn))

上傳人：奔*** IP屬地：河北更新時間：2024-03-27 格式：doc 頁數(shù)：19 大?。?15.00KB 人氣指數(shù)：12 舉報 版權(quán)申訴

算法分析與設(shè)計的課程設(shè)計(一元多項式的加法、減法、乘法的實現(xiàn))_第1頁

已閱讀1頁，還剩18頁未讀，繼續(xù)免費閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領(lǐng)

文檔簡介

1、　　一元多項式的加法、減法、乘法的實現(xiàn)　　注：此表格內(nèi)容中的任務(wù)要求為指導(dǎo)教師提供的課程設(shè)計要求，主要實施步驟是指課程設(shè)計的時間安排，結(jié)論是指通過課程設(shè)計得出的有關(guān)結(jié)論及課程設(shè)計不足之處或進一步開發(fā)方向。　　目錄　　1引言4</

2、b>　　1.1課程設(shè)計目標(biāo)4　　1.2編程工具（編程環(huán)境）介紹5　　1.3實施時間及主要實施步驟5　　2需求分析5　　3系統(tǒng)總體設(shè)計6<

3、p>　　4數(shù)據(jù)結(jié)構(gòu)設(shè)計7　　5詳細設(shè)計與實現(xiàn)9　　5.1功能模塊1輸入一元多項式詳細設(shè)計10　　5.1.1詳細設(shè)計10　　5.1.2界面設(shè)計及測試結(jié)果10　　5.2功能模塊2 創(chuàng)建一元多項式詳細設(shè)計

4、10　　5.2.1詳細設(shè)計10　　5.2.2界面設(shè)計及測試結(jié)果11　　5.3功能模塊3主菜單詳細設(shè)計11　　5.3.1詳細設(shè)計11　　5.3.2界面設(shè)計及測試結(jié)果12

5、　5.4功能模塊4 順序存儲的一元多項式運算詳細設(shè)計12　　5.4.1詳細設(shè)計12　　5.4.2算法流程12　　5.4.3界面設(shè)計及測試結(jié)果13　　5.5功能模塊5順序存儲的一元多項式運算詳細設(shè)計13　　5

6、.5.1詳細設(shè)計13　　5.5.2算法流程13　　5.5.3界面設(shè)計及測試結(jié)果14　　6 算法分析……………………………………………………………………………(5)　　7 用戶手冊 …………………………………………….…………………………….(5&l

7、t;/p>　　8 結(jié)論 …………………………………………………………………………………)　　9 參考文獻……………………………………………………………………………….　　10 附錄……………………………………………………………………………………　　1

8、引言　　課程設(shè)計目標(biāo)設(shè)計一個一元多項式運算的系統(tǒng)，主要包括：加減乘法的運算。本文是關(guān)于一個一元稀疏多項式計算器的問題。內(nèi)容包括輸入并建立多項式,多項式相加，多項式求導(dǎo)，多項式求值以及輸出多項式。本文使用鏈式存儲結(jié)構(gòu)存儲一元稀疏多項式，可以方便的計算簡單的一元稀疏多項式的基本

9、運算。本課程設(shè)計運用所學(xué)的一些C++知識，構(gòu)成整個計算器的形成框架。在程序中定義了各種類型的運算的模塊，通過主程序的調(diào)用來完成他們之間的配合，進而完善了計算器。　　編程工具（編程環(huán)境）介紹　　編程工具：Microsoft Visual C++　　編程環(huán)境：Microsoft Windows xp

10、;　　實施時間及主要實施步驟　　實施時間：　　9月13日至9月25日　　基本步驟大致為：　　前期分析<p&

11、gt;　　中期編碼　　后期調(diào)試　　需求分析　　本問題描述　　本實驗要求利用帶頭結(jié)點的有序鏈表實現(xiàn)任意兩個一元實系數(shù)的加減

12、乘法運算。基本功能要求　　1．首先，根據(jù)鍵盤輸入的一元實系數(shù)多項式的系數(shù)與指數(shù)序列，對多項式進行初始化，并按未知數(shù)x的升冪形式排序。　　2．對于從鍵盤輸入的任意兩個一元多項式，正確計算它們的和，差，積多項式，并輸出結(jié)果。　　測試數(shù)據(jù)

13、　　見Test.txt　　系統(tǒng)總體設(shè)計　　進入界面，系統(tǒng)提示用戶輸入多項式的指數(shù)和系數(shù)并選擇存儲方式。然后出現(xiàn)操作界面，由用戶選擇相關(guān)操作以及按照升冪還是降冪輸出。　　具體實現(xiàn)見流程圖：</p&

14、gt;　　本程序包括5個模塊：　　輸入一元多項式　　該模塊主要是用戶根據(jù)提示輸入一元多項式的指數(shù)和系數(shù)　　根據(jù)輸入創(chuàng)建一元多項式并存儲并且判斷是否稀疏　　該模塊主要是將輸入的一元多項式按順序存儲方式存儲，并判斷是

15、否稀疏，如果稀疏，則轉(zhuǎn)換為鏈式方式存儲　　主菜單　　該模塊主要是顯示菜單信息，并且由用戶顯示要進行的步驟　　順序存儲的一元多項式的加減乘法并輸出結(jié)果　　該模塊主要是實現(xiàn)多項式的運算　　鏈式存儲

16、的一元多項式的加減乘法并輸出結(jié)果　　該模塊主要是實現(xiàn)多項式的運算　　數(shù)據(jù)結(jié)構(gòu)設(shè)計　　本程序主要應(yīng)用了鏈表，結(jié)構(gòu)體和類模板。用結(jié)構(gòu)體來定義多項式的結(jié)點（即每一項），它包含三個域，分別存放該項的系數(shù)、指數(shù)以及指向下一項結(jié)點的指針；用鏈表來存儲多項式，為了節(jié)省空間，只存儲多項式中系

17、數(shù)非0 的項，用多項式鏈表類來實現(xiàn)設(shè)定的程序的基本功能。　　為實現(xiàn)上述功能定義一元多項式的抽象數(shù)據(jù)類型如下：ADT Polynomial{數(shù)據(jù)對象：D={ai |aiTermSet, i=1,2,…,m, m≥10，TermSet中的元素包含一個實系數(shù)和一個表示指數(shù)的整數(shù)}數(shù)據(jù)關(guān)系：R1={<ai-1,ai> |ai-1,aiD, 且ai-1

18、中的指數(shù)值< ai中的指數(shù)值，i=2,…,n}} ADT Polynomial　　定義結(jié)構(gòu)體：　　typedef struct LNode　　{　　float ceof;

19、 ////系數(shù)　　int expn,xs; ////指數(shù) 項數(shù) 　　struct LNode *next;　　}LNode,*LinkList;　　typedef struct 　　{

20、　　float a[N];////////下標(biāo)表示指數(shù)，值表示系數(shù)//////// 　　int len,Nz;////////記錄多項式的長度，非零項////////////////　　}polynomial;　　函數(shù)功能描述：<

21、;/p>　　Menu()　　操作菜單　　cmp()　　對系數(shù)進行比較　　AddPolyn()

22、　　順序存儲的一元多項式相加　　CreatPolyn()　　創(chuàng)建鏈式存儲的一元多項式　　ADD()　　鏈式存儲的一元多項式相加　　AscendPrin

23、t( )　　升冪輸出 　　Getpoly ()　　創(chuàng)建順序存儲的一元多項式　　LAscend()　　鏈式存儲的一元多項式升冪排序

24、　　PrintPolyn()　　打印鏈式存儲的一元多項式　　詳細設(shè)計與實現(xiàn)　　一元多項式計算器各功能模塊的詳細介紹。　　功能模塊1詳細設(shè)計

25、;　　詳細設(shè)計　　1、模塊名稱：輸入一元多項式　　2、功能說明：用戶根據(jù)提示輸入一元多項式的系數(shù)和指數(shù)　　3、輸入?yún)?shù)：輸入指數(shù)和系數(shù)，系數(shù)為負數(shù)就結(jié)束　　界面設(shè)計及測試結(jié)果

26、　　功能模塊2詳細設(shè)計　　詳細設(shè)計　　模塊名稱：根據(jù)輸入創(chuàng)建一元多項式并存儲并且判斷是否稀疏　　功能說明：主要是創(chuàng)建一元多項式　　界面設(shè)計及測試結(jié)果</

27、b>　　功能模塊3詳細設(shè)計　　詳細設(shè)計　　模塊名稱：主菜單　　功能說明：該模塊主要是顯示菜單信息，并且由用戶顯示要進行的步驟&l

28、t;p>　　界面設(shè)計及測試結(jié)果　　功能模塊4詳細設(shè)計　　詳細設(shè)計　　模塊名稱：順序存儲的一元多項式的加減乘法并輸出結(jié)果　　功能說明：該模塊主要是實現(xiàn)多項

29、式的運算　　算法流程　　void ADD(polynomial A,polynomial B,polynomial &M)　　{　　int la=A.len,lb=B.len,i;<

30、;/p>　　M.len=la>lb?la:lb;　　for(i=0;i<=la&&i<=lb;i++)　　{　　M.a[i]=A.a[i]+B.a[i]; ///////////此處若為稀疏式，則會浪費大量時間

31、 　　}　　while(i<=la) {M.a[i]=A.a[i];i++;}　　while(i<=lb) {M.a[i]=B.a[i];i++;}　　print(M);</

32、p>　　}　　//==================================================================　　///////M(x)=A(m)-B(n)//////　　void SUB(polynomia

33、l A,polynomial B,polynomial &M)　　{　　int la=A.len,lb=B.len,i;　　M.len=la>lb?la:lb;　　for(i=0;i<=la&&i&

34、lt;=lb;i++)　　{　　M.a[i]=A.a[i]-B.a[i];　　}　　while(i<=la) {M.a[i]=A.a[i];i++;}<p&g

35、t;　　while(i<=lb) {M.a[i]=0-B.a[i];i++;} ///////B的相反數(shù)　　print(M); 　　}　　//==========================

36、========================================　　///////M(x)=A(m)*B(n)//////　　void MUL(polynomial A,polynomial B,polynomial &M)　　{

37、　　int i,j;　　for(i=0;i<=A.len+B.len+1;i++) M.a[i]=0; ////////////////為什么要多1 　　for(i=0;i<=A.len;i++)　　for(j=0;j<=B.le

38、n;j++)　　{　　M.a[i+j]+=A.a[i]*B.a[j];　　}　　M.len=A.len+B.len;　　print(M); </p

39、>　　}　　界面設(shè)計及測試結(jié)果　　功能模塊5詳細設(shè)計　　詳細設(shè)計　　模塊名稱：鏈式存儲的一元

40、多項式的加減乘法并輸出結(jié)果　　功能說明：該模塊主要是實現(xiàn)多項式的運算　　算法流程　　Lpolynomial AddPolyn(Lpolynomial Pa,Lpolynomial Pb)　　{

41、　　float sum;　　Lpolynomial ha,hb,hc,qa,qb,qc,pc;　　if(Pa->xs>Pb->xs){　　ha=Pb; hb=Pa;　　}&

42、lt;/p>　　else {　　ha=Pa; hb=Pb; 　　}　　hc=pc=(Lpolynomial)malloc(sizeof(LNode));　　qa=ha-

43、>next; 　　qb=hb->next;　　while((qa->next!=NULL)&&(qb->next!=NULL))　　{ 　　qc=(Lpolynomial)malloc(siz

44、eof(LNode));　　qc->next=NULL;　　switch(cmp(qa->expn,qb->expn))　　{　　case -1: <

45、;p>　　qc->ceof=qa->ceof;　　qc->expn=qa->expn;　　pc->next=qc; 　　pc=qc; 　　qa=qa->next; &l

46、t;p>　　break;　　case 0: 　　sum=qa->ceof+qb->ceof;　　if(sum!=0.0)　　{</p

47、>　　qc->ceof=sum; 　　qc->expn=qa->expn; 　　pc->next=qc;　　pc=qc; 　　qa=qa->next;

48、　　qb=qb->next; 　　break;　　}　　else {free(qc); 　　qa=qa->next;

49、　qb=qb->next; 　　break;　　}　　case 1: 　　qc->ceof=qb->ceof; &

50、lt;p>　　qc->expn=qb->expn; 　　pc->next=qc; 　　pc=qc; 　　qb=qb->next; 　　break;

51、;　　}　　}　　if(qa->next!=NULL)　　{ 　　while(qa!=NULL) <

52、p>　　{ 　　qc=(Lpolynomial)malloc(sizeof(LNode));　　qc->next=NULL;　　qc->ceof=qa->ceof; qc->expn=qa->expn;<p&g

53、t;　　pc->next=qc; pc=qc; qa=qa->next; 　　}　　}　　else 　　{

54、　　while(qb!=NULL) 　　{ 　　qc=(Lpolynomial)malloc(sizeof(LNode));　　qc->next=NULL;　　qc->ceof=q

55、b->ceof; qc->expn=qb->expn; 　　pc->next=qc; pc=qc; qb=qb->next; 　　}　　}　　qc=(Lpolynom

56、ial)malloc(sizeof(LNode));　　qc->next=NULL;　　prints(hc);　　pc->next=qc;　　qc->ceof=0;　　Pa=ha; Pb=hb;

57、;　　}　　//==================================================================　　//------------------相減，構(gòu)成和多項式 hc-----------------//

58、　　Lpolynomial SubtractPolyn(Lpolynomial Pa,Lpolynomial Pb)　　{　　float result;　　Lpolynomial ha,hb,hc,qa,qb,qc,pc;　　if(

59、Pa->xs>Pb->xs){ha=Pb; hb=Pa;}　　else {ha=Pa; hb=Pb; }　　qa=ha->next; qb=hb->next;hc=pc=(Lpolynomial)malloc(sizeof(LNode));　　while((qa->next!

60、=NULL)&&(qb->next!=NULL))　　{ 　　qc=(Lpolynomial)malloc(sizeof(LNode));　　qc->next=NULL;　　switch(cmp(qa-&g

61、t;expn,qb->expn))　　{　　case -1: qc->ceof=qa->ceof; qc->expn=qa->expn;　　pc->next=qc; pc=qc; qa=qa->next; break;</p&g

62、t;　　case 0: result=qa->ceof-qb->ceof;　　if(result!=0.0)　　{　　qc->ceof=result; qc->expn=qa->expn; pc->next=qc

63、;　　pc=qc; qa=qa->next; qb=qb->next; break;　　}　　else free(qc); qa=qa->next; qb=qb->next; break;　　case 1:

64、qc->ceof=0-qb->ceof; qc->expn=qb->expn;　　pc->next=qc; pc=qc; qb=qb->next; break; 　　}　　}</p&

65、gt;　　if(qa->next!=NULL)　　{ 　　while(qa!=NULL) 　　{ 　　qc=(Lpolynomial)malloc(sizeof(LNo

66、de));　　qc->next=NULL;　　qc->ceof=qa->ceof; qc->expn=qa->expn; pc->next=qc; pc=qc; qa=qa->next; 　　}

67、;　　}　　else 　　{ 　　while(qb!=NULL) 　　{

68、qc=(Lpolynomial)malloc(sizeof(LNode));　　qc->next=NULL;　　qc->ceof=0-qb->ceof; 　　qc->expn=qb->expn;　　cout<<qc->ceo

69、f;　　pc->next=qc; pc=qc; qb=qb->next; 　　}　　}　　if(Pa->xs>Pb->xs) {for(qc=hc;qc->ne

70、xt!=NULL;qc=qc->next) qc->ceof=0-qc->ceof; qc->ceof=0-qc->ceof; cout<<qc->ceof;}　　prints(hc);　　Pa=ha; Pb=hb;　　}<

71、;/p>　　Lpolynomial MultiplyPolyn(Lpolynomial Pa,Lpolynomial Pb)/////////////相乘，Pa構(gòu)成積多項式hc　　{　　Lpolynomial s,hc,q,p,r,ha,hb;

72、ha=Pa; hb=Pb;　　hc=(Lpolynomial)malloc(sizeof(LNode));　　r=hc;　　for(p=Pa->next;p!=NULL;p=p->next)　　for(q=Pb->n

73、ext;q!=NULL;q=q->next)　　{ s=(Lpolynomial)malloc(sizeof(LNode));　　s->ceof=p->ceof*q->ceof;　　s->expn=p->expn+q->expn;

74、　　r->next=s;　　r=s;　　}　　r->next=NULL;　　for(int i=20; i!=0;i--)

75、;　　{　　for(q=hc;q->next!=NULL;q=q->next)//合并同類項　　for(p=q->next;p!=NULL&&p->next!=NULL;p=p->next)　　if(q->expn==p-&

76、gt;next->expn)　　{ q->ceof=q->ceof+p->next->ceof;　　r=p->next;　　p->next=p->next->next; free(r);　　}<

77、;/b>　　}　　LAscend(hc);　　prints(hc); 　　Pa=ha; Pb=hb;　　}

78、　　計算多項式加減，其算法思想是相同的。以多項式加法為例，先對兩多項式排序，再將兩多項式的每一項逐項相加，在相加之前，先比較兩項的指數(shù)是否相等，若相等則將系數(shù)相加，再判斷系數(shù)是否為零，若為零則刪除，否則存儲在和多項式中。若兩項指數(shù)不相等，當(dāng)多項式pa指數(shù)大于多項式pb指數(shù)時，則將pa結(jié)點副本插入到和多項式PolyC尾部；當(dāng)pa指數(shù)小于pb指數(shù)時，則將pb結(jié)點副本插入到和多項式PolyC尾部，最后插入剩余結(jié)點。&l

79、t;p>　　（8）計算多項式乘法時，先判斷兩多項式是否為空，若為空，則返回乘多項式，否則要先對兩多項式進行合并排序，先將兩多項式的第一項相乘，即系數(shù)相乘，指數(shù)相加，其值作為乘多項式的第一結(jié)點，其后使用雙重循環(huán)將一多項式的每一項與另一多項式的每一項分別相乘，結(jié)果存到乘多項式中。　　界面設(shè)計及測試結(jié)果<b&g

80、t;　　算法分析　　主要的算法是對多項式的計算，分別有　　1、A+B：用了一個循環(huán)，循環(huán)n次，即T=O(n)　　2、A-B：A-B即為A+（-B），即T=O(n)　　3、A*B：用了兩個循環(huán)來完成計算，第二個循環(huán)嵌套在第一個循環(huán)里面，即時間復(fù)雜度T=O

81、(n2)　　結(jié)論　　課程設(shè)計終于做完了，雖然有些疲勞和困倦，但帶給我很多的收獲。數(shù)絕結(jié)構(gòu)已經(jīng)學(xué)了一個學(xué)期，大概三個多月了，有許多知識都存在似懂非懂的現(xiàn)象，這種現(xiàn)象通過實際的上機操作，實際應(yīng)用，已經(jīng)減少了許多。對這些知識也有了更深的理解和很好的掌握。許多困惑，有許多已經(jīng)通過實際操作解決了，并能夠深刻認識，但也有很多沒有

82、明白。通過課程設(shè)計，明白到了原來開發(fā)一個小小的實用系統(tǒng)，是需要考慮到很多方面的問題的，這些都是要在實踐中摸索的，這與平時做練習(xí)是不同的，但也因為平時有許多的練習(xí)基礎(chǔ)，會使你做起程序來，更加得心應(yīng)手。另外就是要把錯誤總結(jié)，有許多錯誤或者陷阱是平時自己陷進去的，因此很深刻，但也有些錯誤或者陷阱是自己還沒有接觸或者犯過的，這就應(yīng)該看多些別人的總結(jié)，使自己不犯這些錯誤。不讓自己掉進這些陷阱。這樣長期總結(jié)，會對自己有很大的幫助。主要

83、內(nèi)容是對一元多項式存儲結(jié)構(gòu)的選擇，輸入多項式采用頭插法的方式，輸入多項式中一個項的系數(shù)和指數(shù)，就產(chǎn)生一個新的節(jié)點，建立起它的右指針，并用頭節(jié)點指向它；雖然一元多項式可以用順序和鏈式兩種存儲結(jié)構(gòu)表示，但順序結(jié)構(gòu)的最大長度很難確定。比如當(dāng)多項式的系數(shù)較大時，此時就會　　8參考文獻　　[1]嚴蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)（C語

眾賞文庫> 全部分類> 畢業(yè)設(shè)計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

算法分析與設(shè)計的課程設(shè)計(一元多項式的加法、減法、乘法的實現(xiàn))

文檔簡介

溫馨提示

最新文檔

評論

算法分析與設(shè)計的課程設(shè)計(一元多項式的加法、減法、乘法的實現(xiàn))

文檔簡介

溫馨提示

最新文檔

評論

免費下載

算法分析與設(shè)計的課程設(shè)計(一元多項式的加法、減法、乘法的實現(xiàn))