數(shù)據(jù)結(jié)構(gòu)課程設(shè)計一元多項式的加減法運算

1、.武漢理工大學(xué)華夏學(xué)院課程設(shè)計報告書課程名稱： 數(shù)據(jù)結(jié)構(gòu)與算法分析 題 目：用C語言實現(xiàn)一元多項式的加減法運算 系 名： 信息工程系 專業(yè)班級： 物聯(lián)網(wǎng)工程1122班 姓 名： 隋明超 學(xué) 號： 10213312201 指導(dǎo)教師: 司曉梅 2014年 1 月 3 日 武漢理工大學(xué)華夏學(xué)院信息工程系課 程 設(shè) 計 任 務(wù) 書課程名稱： 數(shù)據(jù)結(jié)構(gòu)與算法分析 指導(dǎo)教師： 司曉梅 班級名稱： 物聯(lián)網(wǎng)1121-2 開課系、教研室： 信息系計算機 一、課程設(shè)計目的與任務(wù)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計是為訓(xùn)練學(xué)生的數(shù)據(jù)組織能力和提高程序設(shè)計能力而設(shè)置的增強實踐能力的課程。目的：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)課程，旨在使學(xué)生學(xué)會分析研究數(shù)據(jù)

2、對象的特性，學(xué)會數(shù)據(jù)的組織方法，以便選擇合適的數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)以及相應(yīng)操作，把現(xiàn)實世界中的問題轉(zhuǎn)換為計算機內(nèi)部的表示和處理，這就是一個良好的程序設(shè)計技能訓(xùn)練的過程。提高學(xué)生的程序設(shè)計能力、掌握基本知識、基本技能，提高算法設(shè)計質(zhì)量與程序設(shè)計素質(zhì)的培養(yǎng)就是本門課程的課程設(shè)計的目的。任務(wù)：根據(jù)題目要求，完成算法設(shè)計與程序?qū)崿F(xiàn)，并按規(guī)定寫出課程設(shè)計報告。二、課程設(shè)計的內(nèi)容與基本要求設(shè)計題目：用C語言實現(xiàn)一元多項式的加減法計算問題描述輸入并建立兩個多項式并輸出多項式設(shè)計一個程序：對兩個多項式進(jìn)行加、減法運算，建立一個新多項式并輸出。實現(xiàn)提示：選擇單鏈表存儲多項式 具體要完成的任務(wù)是： A. 編制

3、完成上述問題的C語言程序、進(jìn)行程序調(diào)試并能得出正確的運行結(jié)果。 B. 寫出規(guī)范的課程設(shè)計報告書；三、課程設(shè)計步驟及時間進(jìn)度和場地安排時間：本課程設(shè)計安排在第18周 地點：現(xiàn)代教育中心具體時間安排如下：第一天：布置題目，確定任務(wù)、查找相關(guān)資料第二天第四天：功能分析，編寫程序，調(diào)試程序、運行系統(tǒng)；第五天上午：撰寫設(shè)計報告；第五天下午：程序驗收、答辯。四、課程設(shè)計考核及評分標(biāo)準(zhǔn)課程設(shè)計考核將綜合考慮學(xué)生的系統(tǒng)設(shè)計方案、運行結(jié)果、課程設(shè)計報告書的質(zhì)量、態(tài)度、考勤、答辯情況等各因素。具體評分標(biāo)準(zhǔn)如下：（1）設(shè)計方案正確，具有可行性、創(chuàng)新性； 30分（2）系統(tǒng)開發(fā)效果較好； 20分（3）設(shè)計報告規(guī)范、課程

4、設(shè)計報告質(zhì)量高； 20分（4）課程設(shè)計答辯時，問題回答正確； 20分（5）態(tài)度認(rèn)真、刻苦鉆研、遵守紀(jì)律； 10分 按上述五項分別記分后求和，總分按五級制記載最后成績。優(yōu)秀（10090分），良好（8089分），中等（7079分），及格（6069分），不及格（059分）1. 設(shè)計題目：用C語言實現(xiàn)一元多項式的加減法運算2.開發(fā)環(huán)境、采用的語言：(1)Windows XP中文操作系統(tǒng) (2) Visual C+ 6.03.設(shè)計思想（對你的整個設(shè)計思路作出說明）：3.1問題描述：輸入并建立兩個多項式并輸出多項式，對兩個多項式進(jìn)行加、減法運算，建立一個新多項式并輸出。3.2問題思考：用C語言編寫一段程序

5、，該程序的功能相當(dāng)于一個一元多項式的計算器，能夠?qū)崿F(xiàn)按照指數(shù)降冪建立并輸出多項式，并且能夠完成多個多項式的相加、相減運算及結(jié)果輸出的功能。此程序的數(shù)據(jù)結(jié)構(gòu)是選擇用帶表頭結(jié)點的單鏈表存儲多項式。雖然一元多項式可以用順序和鏈表存儲結(jié)果表示，但順序結(jié)構(gòu)的最大長度很難確定。比如當(dāng)多項式的系數(shù)較大時，此時就會浪費存儲空間，所以應(yīng)該選用鏈表結(jié)構(gòu)來存儲一元多項式。但鏈表的結(jié)構(gòu)體可以用來存儲多項式的系數(shù)、指數(shù)、下一個指針3個元素，這樣便于實現(xiàn)任意多項式的加法、減法運算。3.3功能設(shè)計：（1）多項式建立：提示用戶輸入兩個多項式A和B，輸入形式為：1) 先輸入多項式A的項數(shù)，回車2) 輸入多項式A第一項的系數(shù)，空

6、格隔開輸入多項式A第一項的指數(shù)，3) 繼續(xù)輸入多項式A的其他項，輸入方式與上同；4) 再建立多項式B，數(shù)據(jù)輸入方式與建立多項式A相同。（2）功能項：設(shè)計一個功能項，分別為1.輸出多項式a和b 2.輸出多項式a+b 3.輸出多項式a-b 4.退出（3）執(zhí)行操作：此時用戶可以根據(jù)需要選擇功能項中四項進(jìn)行輸出。4.程序總的流程圖：通過設(shè)計思想，可設(shè)計出如圖4-1所示的一元多項式總流程圖：開始申請結(jié)點空間+num輸入多項式的項數(shù)指針數(shù)組tempi中（i=1num）輸入多項式各項的系數(shù) M, 指數(shù) N輸出已輸入的多項式 進(jìn)行多項式的輸出、加法、減法運算結(jié)束否是是否輸入正確圖4.1一元多項式總流程圖5.

7、數(shù)據(jù)結(jié)構(gòu)說明及模塊算法說明（或流程圖）：、5.1存儲結(jié)構(gòu)：一元多項式的表示在計算機內(nèi)可以用鏈表來表示，為了節(jié)省存儲空間，只存儲多項式中系數(shù)非零的項。鏈表中的每一個結(jié)點存放多項式的一個系數(shù)非零項，它包含三個域，分別存放該項的系數(shù)、指數(shù)以及指向下一個多項式項結(jié)點的指針。創(chuàng)建一元多項式鏈表，對一元多項式的運算中會出現(xiàn)的各種可能情況進(jìn)行分析，實現(xiàn)一元多項式的相加、相減操作。5.2基本算法：（1）一元多項式的建立：輸入多項式采用頭插法的方式，輸入多項式中的一個項的系數(shù)和指數(shù)，就產(chǎn)生一個新的結(jié)點，建立起它的右指針，并用頭結(jié)點指向它；為了判斷一個多項式是否輸入結(jié)束，定義一個結(jié)束標(biāo)志，當(dāng)輸入非0時就繼續(xù)；輸入

8、為0時，就結(jié)束一個多項式的輸入。（2）顯示一元多項式：如果系數(shù)是大于0的話就輸出的形式；如果系數(shù)是小于0的話就輸出的形式；如果指數(shù)為0的話就直接輸出；如果指數(shù)是1的話就直接輸出；如果指數(shù)是-1的話，就直接輸出。（3）一元多項式加法運算 ：從兩個多項式的頭部開始判斷，當(dāng)兩個多項式的某一項度不為空時，假設(shè)P、Q分別指向多項式A和多項式B中當(dāng)前進(jìn)行比較的結(jié)點，然后比較兩個結(jié)點中的指數(shù)項，有三種情況：1、當(dāng)P所指結(jié)點的指數(shù)小于Q的話，就應(yīng)該復(fù)制P的結(jié)點到多項式鏈中。2、P所指結(jié)點的指數(shù)如果大于Q的指數(shù)的話，就應(yīng)該復(fù)制Q的結(jié)點到多項式鏈中。3、當(dāng)P所指結(jié)點的指數(shù)等于Q所指結(jié)點的指數(shù)時，則將兩個結(jié)點中的系

9、數(shù)相加，若和不為0，則修改P所指結(jié)點的系數(shù)值，同時釋放Q所指結(jié)點；若和為0，從多項式A的鏈表中刪除相應(yīng)結(jié)點，并釋放P、Q所指結(jié)點。加法流程圖如圖5.2-1所示：開始定義存儲結(jié)果的空鏈 r是 否輸出存儲多項式的和的鏈r結(jié)束是否同指數(shù)項系數(shù)相加后存入r中把p中各項系數(shù)改變符號后存入r中直接把q中各項存入r存儲多項式2的空鏈Q(jìng)是否為空存儲多項式1的空鏈P是否為空合并同類項圖5.2-1一元多項式加法運算流程圖（4）一元多項式的減法 從兩個多項式的頭部開始判斷，當(dāng)兩個多項式的某一項度不為空時，假設(shè)P、Q分別指向多項式A和多項式B中當(dāng)前進(jìn)行比較的結(jié)點，然后比較兩個結(jié)點中的指數(shù)項，有三種情況：1、當(dāng)P所指結(jié)

10、點的指數(shù)小于Q的話，就應(yīng)該復(fù)制P的結(jié)點到多項式鏈中。2、P所指結(jié)點的指數(shù)如果大于Q的指數(shù)的話，就應(yīng)該復(fù)制Q的結(jié)點到多項式鏈中，并將建立的結(jié)點系數(shù)變?yōu)橄喾磾?shù)。3、當(dāng)P所指結(jié)點的指數(shù)等于Q所指結(jié)點的指數(shù)時，并將Q的結(jié)點系數(shù)變?yōu)橄喾磾?shù)，并將兩個結(jié)點中的系數(shù)相加，若和不為0，則修改P所指結(jié)點的系數(shù)值，同時釋放Q所指結(jié)點；若和為0，從多項式A的鏈表中刪除相應(yīng)結(jié)點，并釋放P、Q所指結(jié)點。減法流程圖如圖5.2-2所示：開始定義存儲結(jié)果的空鏈 r是 否輸出存儲多項式的和的鏈r結(jié)束是否同指數(shù)項系數(shù)相加后存入r中把p中各項系數(shù)改變符號后存入r中直接把q中各項存入r存儲多項式2的空鏈Q(jìng)是否為空存儲多項式1的空鏈P是

11、否為空合并同類項圖5.2-2 一元多項式減法運算流程圖6. 程序運行說明及結(jié)果截圖：6.1歡迎界面：程序打開，首先顯示上的是歡迎界面，在歡迎界面下方有第一個多項式的輸入模塊。 圖 6.1歡迎界面6.2輸入界面：看到輸入界面后，輸入第一個多項式的項數(shù)，接下來輸入這個多項式第一項的系數(shù)，空格繼續(xù)輸入這個多項式的指數(shù)?；剀?yán)^續(xù)輸入下一項，輸入完后回車輸入下一個多項式 圖6.2輸入界面6.3功能選項：當(dāng)數(shù)據(jù)輸入完成后進(jìn)入功能選項，在功能選項可以選擇自己想要實現(xiàn)的功能進(jìn)行操作。圖6.3功能選項6.4多項式輸出：在執(zhí)行操作中選擇1，輸出多項式a和b。圖6.4多項式輸出6.5多項式相加：在執(zhí)行操作中選擇2，

12、輸出多項式a+b。圖6.5多項式相加6.6多項式相減：在執(zhí)行操作中選擇3，輸出多項式a-b。圖6.6多項式相減7. 程序調(diào)試及測試過程記載： 本次課程設(shè)計中，經(jīng)過反復(fù)調(diào)試，程序已經(jīng)可以正常運行。在設(shè)計該算法時，出現(xiàn)了一些問題，例如在建立鏈表時頭指針的設(shè)立導(dǎo)致了之后運用到相關(guān)的指針時沒能很好的移動指針出現(xiàn)了數(shù)據(jù)重復(fù)輸出或是輸出系統(tǒng)缺省值，不能實現(xiàn)算法。實現(xiàn)加法時該鏈表并沒有向通常那樣通過建立第三個鏈表來存放運算結(jié)果，而是再度利用了鏈表之一來進(jìn)行節(jié)點的比較插入刪除等操作。為了使輸入數(shù)據(jù)按指數(shù)降序排列，可在數(shù)據(jù)的輸入后先做一個節(jié)點的排序函數(shù)，通過對鏈表排序后再進(jìn)行之后加減運算。8. 總結(jié)及心得體會：

13、在這次課程設(shè)計中，我遇到了不少困難，但是在我的堅持和虛心請教中都得到順利解決。在這次課程設(shè)計中，我發(fā)現(xiàn)理論必須和實踐相結(jié)合，才能真正學(xué)會程序設(shè)計，才能完成一個課題。在這次設(shè)計中我參考了不少書籍，從中學(xué)到了課堂中無法學(xué)到的許多東西，對此我感到很興奮。原來不斷的學(xué)習(xí)，不斷的探索是苦中帶著甜，雖然經(jīng)歷了不少彎路，經(jīng)歷了不少挫折，但當(dāng)程序調(diào)試成功后，當(dāng)運行能達(dá)到要求后，我感到十二分成就感。面對課題，要展現(xiàn)自信出來，這是成功的一半，在這個設(shè)計過程中，不懂的可以虛心向老師請教，與同學(xué)交流經(jīng)驗。態(tài)度是成功的基石！在我這課題中，關(guān)鍵在于對一元多項式的表示及相加的操作。這個實際問題，在學(xué)習(xí)過的知識中找到一種合適

14、的模型來模擬，數(shù)據(jù)結(jié)構(gòu)的選擇是主要，而對于編寫代碼，所涉及的并不是很復(fù)雜，對于鏈表數(shù)據(jù)存儲訪問方式，在C語言的學(xué)習(xí)過程中已經(jīng)有過很多講解，為了進(jìn)一步了解，我還閱讀了一些數(shù)據(jù)結(jié)構(gòu)中關(guān)于鏈表的敘述。對于這個課題，運用C語言簡單一點的結(jié)構(gòu)化程序設(shè)計已足能滿足要求而不至于結(jié)構(gòu)過于復(fù)雜，為了簡便的實現(xiàn)插入操作，我選擇了一個帶表頭結(jié)點的鏈表。在寫源代碼時要注意指針使用的正確性，為產(chǎn)生的新結(jié)點需及時分配存儲空間。在設(shè)計中將問題抽象化，而完成后在運行時，可以說是用抽象的數(shù)據(jù)模型來解決實際問題。我的這個課題相比較于其他同學(xué)來說，是相對簡單的一點的。在現(xiàn)實中，很多功能現(xiàn)在都沒法實現(xiàn)，還有不少操作需進(jìn)一步完善，這次

15、程序設(shè)計有很多不足處，可能是因為經(jīng)驗不足，對問題預(yù)期不夠等一些不可預(yù)見的原因所致，這些都是我以后要汲取的教訓(xùn)。9. 附錄：源代碼（注意要加上詳細(xì)的注釋）#include#includetypedef struct Polynomial float coef; int expn; struct Polynomial *next;*Polyn,Polynomial; /Polyn為結(jié)點指針類型void Insert(Polyn p,Polyn h) if(p-coef=0) free(p); /系數(shù)為0的話釋放結(jié)點 else Polyn q1,q2; q1=h;q2=h-next; while(q

16、2&p-expnexpn) /查找插入位置 q1=q2; q2=q2-next; if(q2&p-expn=q2-expn) /將指數(shù)相同相項合并 q2-coef+=p-coef; free(p); if(!q2-coef) /系數(shù)為0的話釋放結(jié)點 q1-next=q2-next; free(q2); else /指數(shù)為新時將結(jié)點插入 p-next=q2; q1-next=p; /InsertPolyn CreatePolyn(Polyn head,int m)/建立一個頭指針為head、項數(shù)為m的一元多項式 int i; Polyn p; p=head=(Polyn)malloc(sizeo

17、f(struct Polynomial); head-next=NULL; for(i=0;icoef,&p-expn); Insert(p,head); /調(diào)用Insert函數(shù)插入結(jié)點 return head;/CreatePolynvoid DestroyPolyn(Polyn p)/銷毀多項式p Polyn q1,q2; q1=p-next; q2=q1-next; while(q1-next) free(q1); q1=q2;/指針后移 q2=q2-next; void PrintPolyn(Polyn P) Polyn q=P-next; int flag=1;/項數(shù)計數(shù)器 if(!

18、q) /若多項式為空，輸出0 putchar(0); printf(n); return; while (q) if(q-coef0&flag!=1) putchar(+); /系數(shù)大于0且不是第一項 if(q-coef!=1&q-coef!=-1)/系數(shù)非1或-1的普通情況 printf(%g,q-coef); if(q-expn=1) putchar(X); else if(q-expn) printf(X%d,q-expn); else if(q-coef=1) if(!q-expn) putchar(1); else if(q-expn=1) putchar(X); else prin

19、tf(X%d,q-expn); if(q-coef=-1) if(!q-expn) printf(-1); else if(q-expn=1) printf(-X); else printf(-X%d,q-expn); q=q-next; flag+; /while printf(n);/PrintPolynint compare(Polyn a,Polyn b) if(a&b) if(!b|a-expnb-expn) return 1; else if(!a|a-expnexpn) return -1; else return 0; else if(!a&b) return -1;/a多項式

20、已空，但b多項式非空 else return 1;/b多項式已空，但a多項式非空/comparePolyn AddPolyn(Polyn pa,Polyn pb)/求解并建立多項式a+b，返回其頭指針 Polyn qa=pa-next; Polyn qb=pb-next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial);/建立頭結(jié)點 hc-next=NULL; headc=hc; while(qa|qb) qc=(Polyn)malloc(sizeof(struct Polynomial); switch(compar

21、e(qa,qb) case 1: qc-coef=qa-coef; qc-expn=qa-expn; qa=qa-next; break; case 0: qc-coef=qa-coef+qb-coef; qc-expn=qa-expn; qa=qa-next; qb=qb-next; break; case -1: qc-coef=qb-coef; qc-expn=qb-expn; qb=qb-next; break; /switch if(qc-coef!=0) qc-next=hc-next; hc-next=qc; hc=qc; else free(qc);/當(dāng)相加系數(shù)為0時，釋放該結(jié)

22、點 /while return headc;/AddPolynPolyn SubtractPolyn(Polyn pa,Polyn pb)/求解并建立多項式a+b，返回其頭指針 Polyn h=pb; Polyn p=pb-next; Polyn pd; while(p) /將pb的系數(shù)取反 p-coef*=-1; p=p-next; pd=AddPolyn(pa,h); for(p=h-next;p;p=p-next) /恢復(fù)pb的系數(shù) p-coef*=-1; return pd;/SubtractPolynint main() int m,n,flag=0; float x; Polyn pa=0,pb=0,pc,pd,pe,pf;/定義各式的頭指針，pa與pb在使用前付初值NULL printf(*歡迎您的使用*n); printf(請輸入多項式a的項數(shù):); scanf(%d,&m); pa=CreatePolyn(pa,m);/建立多項式a printf(*n); printf(請輸入多項式b的項數(shù):); scanf(%d,&n); pb=CreatePolyn(pb,n);/建立多項式b /輸出菜單 printf(*n); printf(功能項：nt