數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--多項式計算器

1、<p><b>　　《數(shù)據(jù)結(jié)構(gòu)》</b></p><p><b>　　---課程設(shè)計報告</b></p><p>　　題目： 多項式計算器</p><p>　　班級： </p><p>　　學(xué)號： </p><p>

2、;　　姓名： </p><p>　　指導(dǎo)教師： </p><p><b>　　目錄</b></p><p>　　課程設(shè)計目的………………………………………….3</p><p>　　設(shè)計內(nèi)容……………………………………………….3</p><p>　　總體設(shè)計…

3、…………………………………………….4</p><p>　　詳細(xì)設(shè)計……………………………………………….4</p><p>　　程序調(diào)試……………………………………………….8</p><p>　　六、 設(shè)計總結(jié)………………………………………………11</p><p><b>　　一、課程設(shè)計的目的</b></

4、p><p>　　課程設(shè)計是《數(shù)據(jù)結(jié)構(gòu)》必不可缺的一個重要環(huán)節(jié)，它可加深我們對該課程所學(xué)內(nèi)容的進(jìn)一步的理解與鞏固，是將計算機(jī)課程與實(shí)際問題相聯(lián)接的關(guān)鍵步驟。通過課程設(shè)計，能夠提高學(xué)生分析問題、解決問題，從而運(yùn)用所學(xué)知識解決實(shí)際問題的能力，通過課程設(shè)計將C語言與數(shù)據(jù)結(jié)構(gòu)結(jié)合在一起實(shí)際應(yīng)用。</p><p><b>　　二、設(shè)計內(nèi)容</b></p><p&g

5、t;　　設(shè)計一個稀疏多項式簡單計算器</p><p><b>　　設(shè)計要求：</b></p><p>　　◆輸入并分別建立多項式A和B</p><p>　　◆輸入輸出多項式，輸出形式為整數(shù)序列： n,c1,e1,c2,e2……，其中n是多項式的項數(shù)，ci和ei是第i項的系數(shù)和指數(shù)，</p><p>　　◆序列按指數(shù)降序排

6、列完成兩個多項式的相加、相減、相乘，并將多項式結(jié)果輸出</p><p><b>　　【問題描述】</b></p><p>　　設(shè)計一個稀疏多項式簡單計算器。用戶輸入兩個多項式的項數(shù)、系數(shù)與指數(shù)，計算加減乘除等的結(jié)果。</p><p><b>　　【功能設(shè)計】</b></p><p>　　提示用戶輸入

7、兩個多項式A和B，輸入形式為：</p><p>　　◆先輸入多項式A的項數(shù)，</p><p><b>　　◆回車，</b></p><p>　　◆輸入多項式A第一項的系數(shù)，每一項按照先輸入系數(shù)，</p><p><b>　　◆空格或回車；</b></p><p>　　◆輸入多

8、項式A第一項的指數(shù)，</p><p>　　◆繼續(xù)輸入多項式A的其他項，輸入方式與上同；</p><p>　　◆再建立多項式B，數(shù)據(jù)輸入方式與建立多項式A相同。</p><p>　　兩個多項式建立完畢后，再選擇以下功能進(jìn)行相應(yīng)的運(yùn)算。</p><p>　　1. 輸出多項式A和B </p><p>　　2. 計算多項式A+

9、B </p><p>　　3. 計算多項式A-B </p><p>　　4. 計算多項式A*B </p><p>　　5. 重新創(chuàng)建多項式</p><p><b>　　6. 退出</b></p><p><b>　　【數(shù)據(jù)結(jié)構(gòu)】</b></p><p>

10、;　　typedef struct Polynomial //結(jié)點(diǎn)類型</p><p>　　{ </p><p>　　float coef; //系數(shù)</p><p>　　int exp;

11、 //指數(shù)</p><p>　　Polynomial *next;</p><p>　　}*Polyn; //Polyn為結(jié)點(diǎn)指針類型</p><p>　　void PrintPolyn(Polyn P); //輸出多項式</p>&l

12、t;p>　　void Insert(Polyn p,Polyn head); //插入結(jié)點(diǎn)</p><p>　　Polyn CreatePolyn(Polyn head,int m) ; //創(chuàng)建多項式</p><p>　　void DestroyPolyn(Polyn p); //銷毀多項式<

13、;/p><p>　　int compare(Polyn a,Polyn b); //多項式指數(shù)比較</p><p>　　Polyn AddPolyn(Polyn pa,Polyn pb); //加法</p><p>　　Polyn SubPolyn(Polyn pa,Polyn pb); //

14、減法</p><p>　　Polyn MultiplyPolyn(Polyn pa,Polyn pb); //乘法</p><p><b>　　三、總體設(shè)計</b></p><p>　　圖1 系統(tǒng)功能模塊圖</p><p><b>　　四、詳細(xì)設(shè)計</b></p>&

15、lt;p><b>　　【結(jié)點(diǎn)結(jié)構(gòu)】</b></p><p><b>　　圖2 結(jié)點(diǎn)結(jié)構(gòu)圖</b></p><p>　　coef：系數(shù)域，存放非零項的系數(shù)；</p><p>　　exp：指數(shù)域，存放非零項的指數(shù)；</p><p>　　next：指針域，存放只想下一結(jié)點(diǎn)的指針。 </p>

16、;<p>　　【多項式的鏈接表示】</p><p>　　多項式的項采用單鏈表存儲，每一個非零項對應(yīng)單鏈表的一個結(jié)點(diǎn)，且單鏈表按照指數(shù)遞減有序排列</p><p><b>　　。</b></p><p>　　多項式的邏輯結(jié)構(gòu)：視為線性表</p><p>　　p(x)=3x14-8x8+6x2+2</p&

17、gt;<p><b>　　多項式的存儲表示</b></p><p>　　p(x)=3x14-8x8+6x2+2</p><p>　　( (3,14)，(-8,8)，(6,2)，(2,0) )</p><p>　　圖3 多項式的鏈表表示</p><p>　　【采用帶頭結(jié)點(diǎn)的單鏈表】</p>&

18、lt;p>　　設(shè)兩個工作指針pa和pb，分別指向兩個單鏈表的開始結(jié)點(diǎn)，兩個多項式求和實(shí)際上是對結(jié)點(diǎn)pa的指數(shù)域和結(jié)點(diǎn)pb的指數(shù)域進(jìn)行比較，這會出現(xiàn)下列三種情況：</p><p>　?。?）若pa->exp<pb->exp，則結(jié)點(diǎn)pa應(yīng)為結(jié)點(diǎn)中的一個結(jié)點(diǎn)，將指針pa后移；</p><p>　　（2）若pa->exp>pb->exp，則結(jié)點(diǎn)pb應(yīng)為結(jié)點(diǎn)

19、中的一個結(jié)點(diǎn)，將pb插入到第一個單鏈表中結(jié)點(diǎn)pa之前，再將指針pb后移；</p><p>　?。?）若pa->exp=pb->exp，則pa與pb所指為同類項，將pb的系數(shù)加到pa的系數(shù)上， 若相加結(jié)果不為0，則將指針pa后移，刪除結(jié)點(diǎn)pb，若相加結(jié)果為0，則表明結(jié)果中無此項，刪除結(jié)點(diǎn)pa和結(jié)點(diǎn)pb，并將指針pa和指針pb分別后移。</p><p><b>　　【

20、算法設(shè)計】</b></p><p>　　表一 算法設(shè)計簡析</p><p><b>　　【多項式相加】</b></p><p>　　圖4 多項式相加示意圖</p><p><b>　　【多項式相乘】</b></p><p>　　兩個多項式相乘時（假設(shè)第一個為m

21、項，第二個為n項）只要第一個多項式的每一項的系數(shù)乘以第二個多項式每一項的系數(shù)，指數(shù)加上第二個多項式的指數(shù)?？梢缘玫絤個新的多項式。然后把這m個多項式按照指數(shù)相同的進(jìn)行相加。合并成一個多項式即可。</p><p>　　假設(shè)有兩個一元多項式：</p><p>　　P1(X)=X^2+2X+3</p><p>　　P2(X)=3X^3+10X+6</p>&

22、lt;p><b>　　計算它們的和：</b></p><p>　　P1(X)*P2(X)=(X^2+2X+3)*(3X^3+10X+6)</p><p>　　= 3X^5+6X^4+19X^3+26X^2+42X^1+18</p><p><b>　　部分代碼描敘如下：</b></p><p>

23、;　　for(;qa;qa=qa->next)</p><p><b>　　{</b></p><p>　　for(qb=pb->next;qb;qb=qb->next)</p><p><b>　　{</b></p><p>　　qc=new Polynomial;</p&

24、gt;<p>　　qc->coef=qa->coef*qb->coef;</p><p>　　qc->exp=qa->exp+qb->exp;</p><p>　　InsertNode(qc,headf); </p><p><b>　　}</b></p>&l

25、t;p><b>　　}</b></p><p><b>　　【程序詳細(xì)設(shè)計】</b></p><p>　　1、 輸出多項式的函數(shù)，必須考慮到多項式所有輸出形勢的情況：</p><p>　　如果項數(shù)為零，則直接輸出“0”；</p><p>　　若某一項的系數(shù)為0，則不輸出該項，若系數(shù)為1，則“1

26、”不用輸出，直接輸出字符“X”；</p><p>　　若項的系數(shù)（或指數(shù)）大于0，則直接輸出該系數(shù)（或指數(shù)），否則需在系數(shù)（或指數(shù)）前輸出一個“—”；</p><p>　　若某一項的指數(shù)為1，則該項指數(shù)不用輸出，直接輸出系數(shù)，在后面加一個字符“X”；</p><p>　　若某一項指數(shù)為0，則只要輸出該項的系數(shù)即可；</p><p>　　當(dāng)項數(shù)

27、不為第一項而且該項系數(shù)大于0時，需在系數(shù)前輸出一個“+”；</p><p>　　2、 結(jié)點(diǎn)插入并排序的函數(shù)InsertNode(Polyn p,Polyn head) ：</p><p>　　計算完成后調(diào)用該函數(shù)，將結(jié)果按照指數(shù)降序排列，合并指數(shù)相同的項，并釋放計算后系數(shù)為0的結(jié)點(diǎn)，若后一個多項式中的項在前一個多項式中找不到與之指數(shù)相同的項，則將該項作為一個新的結(jié)點(diǎn)按照指數(shù)降序插入，合并

28、代碼如下：</p><p>　　if(q2!=NULL&&p->exp==q2-> //將指數(shù)相同的合并</p><p><b>　　{ </b></p><p>　　q2->coef+=p->coef; //系數(shù)相加</p&

29、gt;<p>　　delete p; //釋放p</p><p>　　if(!q2->coef) //釋放系數(shù)為0的結(jié)點(diǎn)</p><p>　　{q1->next=q2->next;</p><p>　　delete q2;}</p>&l

30、t;p><b>　　}</b></p><p>　　3、多項式創(chuàng)建函數(shù)Polyn CreatePolyn(Polyn head,int m)：</p><p>　　建立頭指針為head,項數(shù)為m的多項式，調(diào)用InsertNode函數(shù)插入結(jié)點(diǎn)，返回頭結(jié)點(diǎn)。</p><p>　　Polyn CreatePolyn(Polyn head,int

31、 m) //頭指針為head、項數(shù)為m</p><p><b>　　{ </b></p><p><b>　　Polyn p;</b></p><p>　　p=head=new Polynomial; //生成頭結(jié)點(diǎn)</p><p>　　h

32、ead->next=NULL;</p><p>　　for(int i=0;i<m;i++)</p><p>　　{p=new Polynomial; //建立新結(jié)點(diǎn)</p><p>　　printf("請輸入第%d項的系數(shù)與指數(shù)(空格或回車隔開):",i+1);</p><

33、p>　　scanf("%f%d",&p->coef,&p->exp);</p><p>　　InsertNode(p,head); //調(diào)用InsertNode函數(shù)插入結(jié)點(diǎn)</p><p>　　}return head;</p><p><b>　　}</b>

34、;</p><p>　　4、兩個多項式在指數(shù)比較函數(shù)int Compare(Polyn a,Polyn b)：</p><p>　　根據(jù)多項式A的指數(shù)值<、=或>多項式B的指數(shù)值，分別返回-1、0或1。在此，還要考慮到多項式A或B項數(shù)為0的情況。</p><p>　　int Compare(Polyn a,Polyn b)//依a的指數(shù)值<、=或&

35、gt;b的指數(shù)值，分別返回-1、0或1</p><p><b>　　{</b></p><p><b>　　if(a&&b)</b></p><p><b>　　{</b></p><p>　　if(!b||a->exp>b->exp)

36、 return 1;</p><p>　　else if(!a||a->exp<b->exp) return -1;</p><p>　　else return 0;</p><p><b>　　}</b></p><p>　　else if(!a&&b) </p&g

37、t;<p>　　return -1; //a多項式為空，但b多項式非空</p><p><b>　　else </b></p><p>　　return 1; //b多項式為空，但a多項式非空</p><p><b>　　}<

38、;/b></p><p>　　5、多項式的銷毀函數(shù)void DestroyPolyn(Polyn p)：</p><p>　　運(yùn)算完成后，需銷毀建立的多項式。</p><p>　　void DestroyPolyn(Polyn p) //銷毀多項式p</p><p><b>　　{ &l

39、t;/b></p><p>　　Polyn q1,q2;</p><p>　　q1=p->next;</p><p>　　if(q1==NULL) //結(jié)果系數(shù)為0的情況</p><p><b>　　return ;</b></p><p>　

40、　q2=q1->next;</p><p>　　while(q1->next)</p><p><b>　　{</b></p><p>　　delete q1;</p><p>　　q1=q2; //指針后移</p><p>　　q2=

41、q2->next;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　【初步完成程序】</b></p><p>　　由上述的加法和乘法的算法可以設(shè)計出多項式的一元稀疏運(yùn)算器，結(jié)合上述結(jié)構(gòu)體以及指針的設(shè)計可以初步設(shè)計

42、出程序，尤其在設(shè)計程序時要考慮全面，適當(dāng)例證自己的算法，否則系統(tǒng)讓你容易崩潰。</p><p><b>　　【界面設(shè)計】</b></p><p>　　程序運(yùn)行之后，首先顯示本程序的功能提示，以及提示用戶輸入：</p><p>　　圖5 系統(tǒng)簡單界面</p><p>　　當(dāng)用戶根據(jù)提示輸入完成后，兩個多項式建立完畢，然后

43、根據(jù)輸入對應(yīng)的數(shù)字，選擇相應(yīng)的功能，完成計算并輸出。</p><p><b>　　圖6 多項式的輸出</b></p><p><b>　　五、程序調(diào)試</b></p><p><b>　　測試數(shù)據(jù)：</b></p><p>　?。?） A=3X^3-5X^2+

44、X+2</p><p>　　B=2X^3+5X^2-6</p><p><b>　　輸入：</b></p><p>　　表二 待輸入的多項式</p><p><b>　　預(yù)期結(jié)果：</b></p><p>　　A+B=：5X^3+X-4</p><p&g

45、t;　　A-B=：X^3-10X^2+X+8</p><p>　　A*B=：6X^6+5X^5-23X^4-9X^3+40X^2-6X-12</p><p><b>　　輸入顯示</b></p><p><b>　　圖7 多項式輸入圖</b></p><p><b>　　測試結(jié)果：<

46、/b></p><p>　　圖8 多項式計算結(jié)果</p><p>　　預(yù)期結(jié)果與測試結(jié)果相同，相加算法正確！</p><p><b>　　六、設(shè)計總結(jié)</b></p><p>　　1、設(shè)計過程的感受與體會</p><p>　　雖然數(shù)據(jù)結(jié)構(gòu)是一門公認(rèn)的比較難的課程，自己學(xué)起來也覺得有些吃力，但

47、在本次課程設(shè)計之前，我系統(tǒng)地把教科書復(fù)習(xí)了一遍，大大加深了對各種數(shù)據(jù)結(jié)構(gòu)的理解，運(yùn)用起來更 加自如。不斷地翻閱各種參考書，以及在老師和同學(xué)的幫助下，基本上考慮到了所有的邊界情況，反復(fù)測試各種類型的數(shù)據(jù)，強(qiáng)化程序的健壯性，最終順利完成了本次課程設(shè)計。</p><p>　　2、遇到的問題與解決方法</p><p>　　在本次課程設(shè)計中，遇到的最大問題就是線性表的操作，特別是很多臨界條件的判斷問