數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-一元稀疏多項式簡單計數(shù)器

1、<p>　　數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計說明書</p><p>　　題目： 一元稀疏多項式簡單計數(shù)器</p><p>　　學(xué)生姓名： </p><p>　　學(xué) 號： </p><p>　　院 （系）： 理學(xué)院 </p><p>　　數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計任務(wù)書

2、</p><p>　　題目： 一元稀疏多項式簡單計數(shù)器 </p><p>　　課程設(shè)計從 2011 年 12 月 19 日起到 2011 年 12 月 23 日</p><p>　　1、課程設(shè)計的內(nèi)容和要求（包括原始數(shù)據(jù)、技術(shù)要求、工作要求等）：</p><p>　　一元稀疏多項式簡單

3、計數(shù)器 </p><p>　?。?） 輸入并建立多項式 </p><p>　?。?） 輸出多項式，輸出形式為整數(shù)序列：n，c1，e1，c2，e2……cn </p><p>　　，en，其中n是多項式的項

4、數(shù)，ci，ei分別為第i項的系數(shù)和指數(shù)。序 </p><p>　　列按指數(shù)降序排列。 </p><p>　　（3） 多項式a和b相加，建立多項式a+b，輸出相加的多項式。 </p><p>　?。?） 多項式a和b相減，建立多項式a-b，輸出相減的多項式。 <

5、/p><p>　　用帶頭結(jié)點的單鏈表存儲多項式。 </p><p>　　2、對課程設(shè)計成果的要求〔包括圖表、實物等硬件要求〕：</p><p>　　1）根據(jù)課程設(shè)計題目要求編寫所需程序代碼 </p><p>　　要求可以實現(xiàn)多項式的建立，以及

6、兩個多項式的相加、減，并且輸出相加、減后所得的結(jié)果，同時用手算也可驗證實驗結(jié)果是否符合要求。 </p><p>　　2）提交課程設(shè)計報告 </p><p>　　按照具體要求完成課程設(shè)計報告，其中包括問題的描述、算法思想、

7、程序?qū)崿F(xiàn)結(jié)果、數(shù)據(jù)驗證和實驗總結(jié)等部分。 </p><p>　　3、課程設(shè)計工作進(jìn)度計劃：</p><p>　　指導(dǎo)教師： 日期： 2011-11-15 </p><p>　　教研室主任： 日期： </p><p><b>　　目 錄<

8、;/b></p><p>　　一、問題描述…………………………………………………………………………1</p><p>　　二、算法思想…………………………………………………………………………2</p><p>　　三、數(shù)據(jù)結(jié)構(gòu)…………………………………………………………………………3</p><p>　　四、設(shè)計模塊劃分……………………

9、………………………………………………4</p><p>　　五、源程序……………………………………………………………………………5</p><p>　　六、算法分析…………………………………………………………………………10</p><p>　　七、運行結(jié)果…………………………………………………………………………11</p><p>　　八、

10、設(shè)計總結(jié)與體會…………………………………………………………………13</p><p>　　參考文獻(xiàn) ……………………………………………………………………………14</p><p>　　1.問題描述：一元稀疏多項式簡單計數(shù)器</p><p><b>　　基本要求：</b></p><p>　　（1） 輸入并建立多項式<

11、;/p><p>　?。?） 輸出多項式，輸出形式為整數(shù)序列：n，c1，e1，c2，e2……cn，en，其中n是多項式的項數(shù)，ci，ei分別為第i項的系數(shù)和指數(shù)。序列按指數(shù)降序排列。</p><p>　?。?） 多項式a和b相加，建立多項式a+b，輸出相加的多項式。</p><p>　?。?） 多項式a和b相減，建立多項式a-b，輸出相減的多項式。</p>

12、<p>　　用帶頭結(jié)點的單鏈表存儲多項式。</p><p><b>　　測試數(shù)據(jù)：</b></p><p>　?。?）(2x+5x8-3.1x11)+(7-5x8+11x9)</p><p>　　（2）(6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2+7.8x15)</p><p>　?。?）

13、(x+x2+x3)+0</p><p>　?。?）(x+x3)-(-x-x-3)</p><p><b>　　2.算法思想：</b></p><p><b>　　（1）建立多項式</b></p><p>　　一元多項式是由多個項的和組成的，將一元多項式的每個項用一結(jié)點表示，該結(jié)點中應(yīng)包括該項的系數(shù)、

14、該項的指數(shù)、指向下一項的指針，可以用線性表來依次輸入各項結(jié)點，從而完成多項式鏈表的建立，為了使原多項式各項順序不變，故采用尾插法建表。</p><p>　　（2）降冪輸出多項式</p><p>　　我們可以先設(shè)一個冪指數(shù)i為可輸入的最大冪指數(shù)，然后從首元結(jié)點開始順次查詢每一結(jié)點的指數(shù)和i，若相等則輸出該結(jié)點，否則，i--,繼續(xù)從首元結(jié)點開始查詢，重復(fù)上述過程，直到i為可輸入的最小冪指數(shù)。這

15、樣，就按指數(shù)降冪輸出了多項式。</p><p>　　多項式的項數(shù)統(tǒng)計可以通過頭結(jié)點的next來實現(xiàn)，若非空，count++,直到結(jié)點的指針域為空，這樣，count就統(tǒng)計出了項數(shù)。</p><p><b>　　多項式相加</b></p><p>　　多項式的相加過程，其實就是相同指數(shù)的項的系數(shù)相加，不同指數(shù)的項復(fù)制到和多項式中，將結(jié)果用降冪輸出函

16、數(shù)輸出。</p><p><b>　　多項式相減</b></p><p>　　多項式的相減過程，其實就是相同指數(shù)的項的系數(shù)相減，對于不同指數(shù)的項，若是被減多項式，則將該結(jié)點復(fù)制輸出，若是減多項式，則將該結(jié)點的系數(shù)變?yōu)樵禂?shù)的相反數(shù)輸出，將結(jié)果用降冪輸出函數(shù)輸出。</p><p><b>　　3.數(shù)據(jù)結(jié)構(gòu)：</b></

17、p><p>　　帶頭結(jié)點單鏈表抽象數(shù)據(jù)類型的結(jié)點結(jié)構(gòu)定義如下：</p><p>　　typedef struct Polynode //多項式結(jié)點</p><p><b>　　{</b></p><p>　　int coef; //系數(shù)</p>&

18、lt;p>　　int exp; //指數(shù)</p><p>　　Polynode *next;</p><p>　　}Polynode ,*Polylist;</p><p><b>　　4.模塊劃分：</b></p><p>　　(1) 帶頭結(jié)點的多項式的建立函數(shù)Poly

19、list Polycreate()</p><p>　　(2) 帶頭結(jié)點的多項式的降冪輸出函數(shù)void printf(Polylist poly)</p><p>　　(3) 帶頭結(jié)點的多項式的相加函數(shù)Polylist Polyadd(Polylist a,Polylist b)</p><p>　　(4) 帶頭結(jié)點的多項式的相減函數(shù)Polylist Polysu

20、b(Polylist a,Polylist b)</p><p>　　(5) 主函數(shù)void main()</p><p><b>　　5.源程序：</b></p><p>　　#include<stdio.h></p><p>　　#include<malloc.h></p>&l

21、t;p>　　typedef struct Polyomial</p><p><b>　　{</b></p><p>　　float coef;</p><p><b>　　int expn;</b></p><p>　　struct Polyomial *next;</p>&

22、lt;p>　　}*Poly,Polyomial; //Poly為結(jié)點指針類型</p><p>　　void Insert(Poly p,Poly h){ </p><p>　　if(p->coef==0) free(p); //系數(shù)為0時釋放結(jié)點</p><p><b>　　else{</b

23、></p><p>　　Poly q1,q2;</p><p>　　q1=h;q2=h->next;</p><p>　　while(q2&&p->expn<q2->expn){ //查找插入位置</p><p><b>　　q1=q2;</b></p>&

24、lt;p>　　q2=q2->next;</p><p><b>　　}</b></p><p>　　if(q2&&p->expn==q2->expn){ //將指數(shù)相同相合并</p><p>　　q2->coef+=p->coef;</p><p><b&

25、gt;　　free(p);</b></p><p>　　if(!q2->coef){ //系數(shù)為0的話釋放結(jié)點</p><p>　　q1->next=q2->next;</p><p><b>　　free(q2);</b></p><p><b>　　}&

26、lt;/b></p><p><b>　　}</b></p><p>　　else{ //指數(shù)為新時將結(jié)點插入</p><p>　　p->next=q2;</p><p>　　q1->next=p;</p><p><b&g

27、t;　　}</b></p><p><b>　　}</b></p><p><b>　　}//Insert</b></p><p>　　Poly CreatePoly(Poly head,int m){//建立一個頭指針為head、項數(shù)為m的一元多項式</p><p><b>

28、　　int i;</b></p><p><b>　　Poly p;</b></p><p>　　p=head=(Poly)malloc(sizeof(struct Polyomial));</p><p>　　head->next=NULL;</p><p>　　for(i=0;i<m;i++)

29、{</p><p>　　p=(Poly)malloc(sizeof(struct Polyomial));//建立新結(jié)點以接收數(shù)據(jù)</p><p>　　printf("輸入第%d項的系數(shù)與指數(shù):",i+1);</p><p>　　scanf("%f %d",&p->coef,&p->expn);&l

30、t;/p><p>　　Insert(p,head); //調(diào)用Insert函數(shù)插入結(jié)點</p><p><b>　　}</b></p><p>　　return head;</p><p>　　}//CreatePoly</p><p>　　void DestroyPoly(Poly p){//銷

31、毀多項式p</p><p>　　Poly q1,q2;</p><p>　　q1=p->next;</p><p>　　q2=q1->next;</p><p>　　while(q1->next){</p><p><b>　　free(q1);</b></p>&

32、lt;p>　　q1=q2;//指針后移</p><p>　　q2=q2->next;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void PrintPoly(Poly P){ </p><p>　　Poly

33、 q=P->next; </p><p>　　int flag=1;//項數(shù)計數(shù)器</p><p>　　if(!q) { //若多項式為空，輸出0</p><p>　　putchar('0'); </p><p>　　printf("\n");</p><p><b>

34、;　　return;</b></p><p><b>　　} </b></p><p>　　while (q){</p><p>　　if(q->coef>0&&flag!=1) putchar('+'); //系數(shù)大于0且不是第一項</p><p>　　if(

35、q->coef!=1&&q->coef!=-1){//系數(shù)非1或-1的普通情況</p><p>　　printf("%g",q->coef); </p><p>　　if(q->expn==1) putchar('X');</p><p>　　else if(q->expn) prin

36、tf("X^%d",q->expn);</p><p><b>　　}</b></p><p><b>　　else{</b></p><p>　　if(q->coef==1){</p><p>　　if(!q->expn) putchar('1'

37、;); </p><p>　　else if(q->expn==1) putchar('X'); </p><p>　　else printf("X^%d",q->expn);</p><p><b>　　}</b></p><p>　　if(q->coef==-1)

38、{</p><p>　　if(!q->expn) printf("-1"); </p><p>　　else if(q->expn==1) printf("-X"); </p><p>　　else printf("-X^%d",q->expn);</p><p>

39、<b>　　}</b></p><p><b>　　}</b></p><p>　　q=q->next; </p><p><b>　　flag++;</b></p><p><b>　　}//while</b></p><p&g

40、t;　　printf("\n");</p><p>　　}//PrintPoly</p><p>　　int compare(Poly a,Poly b){</p><p><b>　　if(a&&b){</b></p><p>　　if(!b||a->expn>b->

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

42、-1;//a多項式已空，但b多項式非空</p><p>　　else return 1;//b多項式已空，但a多項式非空</p><p>　　}//compare</p><p>　　Poly AddPoly(Poly pa,Poly pb){//求解并建立多項式a+b，返回其頭指針</p><p>　　Poly qa=pa->next

43、;</p><p>　　Poly qb=pb->next;</p><p>　　Poly headc,hc,qc;</p><p>　　hc=(Poly)malloc(sizeof(struct Polyomial));//建立頭結(jié)點</p><p>　　hc->next=NULL;</p><p><

44、;b>　　headc=hc;</b></p><p>　　while(qa||qb){</p><p>　　qc=(Poly)malloc(sizeof(struct Polyomial));</p><p>　　switch(compare(qa,qb)){</p><p><b>　　case 1:</b

45、></p><p><b>　　{</b></p><p>　　qc->coef=qa->coef;</p><p>　　qc->expn=qa->expn;</p><p>　　qa=qa->next;</p><p><b>　　break;<

46、;/b></p><p><b>　　}</b></p><p><b>　　case 0:</b></p><p><b>　　{ </b></p><p>　　qc->coef=qa->coef+qb->coef;</p><p&

47、gt;　　qc->expn=qa->expn;</p><p>　　qa=qa->next;</p><p>　　qb=qb->next;</p><p><b>　　break;</b></p><p><b>　　}</b></p><p><

48、;b>　　case -1:</b></p><p><b>　　{</b></p><p>　　qc->coef=qb->coef;</p><p>　　qc->expn=qb->expn;</p><p>　　qb=qb->next;</p><p&g

49、t;<b>　　break;</b></p><p><b>　　} </b></p><p><b>　　}//switch</b></p><p>　　if(qc->coef!=0){</p><p>　　qc->next=hc->next;</p&

50、gt;<p>　　hc->next=qc;</p><p><b>　　hc=qc;</b></p><p><b>　　}</b></p><p>　　else free(qc);//當(dāng)相加系數(shù)為0時，釋放該結(jié)點</p><p><b>　　}//while</

51、b></p><p>　　return headc;</p><p>　　}//AddPoly</p><p>　　Poly SubtractPoly(Poly pa,Poly pb)</p><p>　　{ //求解并建立多項式a+b，返回其頭指針</p><p&

52、gt;　　Poly h=pb;</p><p>　　Poly p=pb->next;</p><p><b>　　Poly pd;</b></p><p>　　while(p){ //將pb的系數(shù)取反</p><p>　　p->coef*=-1;</p><p>　

53、　p=p->next;</p><p><b>　　}</b></p><p>　　pd=AddPoly(pa,h);</p><p>　　for(p=h->next;p;p=p->next) //恢復(fù)pb的系數(shù)</p><p>　　p->coef*=-1;</p><p

54、>　　return pd;</p><p>　　}//SubtractPoly</p><p>　　int main(){</p><p>　　int m,n,flag=0;</p><p><b>　　float x;</b></p><p>　　Poly pa=0,pb=0,pc,pd,

55、pe,pf;//定義各式的頭指針，pa與pb在使用前付初值NULL</p><p>　　printf("輸入a的項數(shù):");</p><p>　　scanf("%d",&m);</p><p>　　pa=CreatePoly(pa,m);//建立多項式a</p><p>　　printf(&qu

56、ot;輸入b的項數(shù):");</p><p>　　scanf("%d",&n);</p><p>　　pb=CreatePoly(pb,n);//建立多項式b</p><p>　　for(;;flag=0){</p><p>　　printf("執(zhí)行操作");</p>&l

57、t;p>　　scanf("%d",&flag);</p><p>　　if(flag==1){</p><p>　　printf("多項式a：");PrintPoly(pa);</p><p>　　printf("多項式b：");PrintPoly(pb);continue;</p>

58、;<p><b>　　}</b></p><p>　　if(flag==2){</p><p>　　pc=AddPoly(pa,pb);</p><p>　　printf("多項式a+b：");PrintPoly(pc);</p><p>　　DestroyPoly(pc);contin

59、ue;</p><p><b>　　}</b></p><p>　　if(flag==3){</p><p>　　pd=SubtractPoly(pa,pb);</p><p>　　printf("多項式a-b：");PrintPoly(pd);</p><p>　　Destr

60、oyPoly(pd);continue;</p><p><b>　　}</b></p><p>　　if(flag==4) break;</p><p>　　if(flag<1||flag>4) printf("Error!!!\n");continue;</p><p><b&g

61、t;　　}//for</b></p><p>　　DestroyPoly(pa);</p><p>　　DestroyPoly(pb);</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p><b&g

62、t;　　6.算法分析</b></p><p>　　建立多項式的時間復(fù)雜度為O(n),降冪輸出多項式序列算法，由于是對指數(shù)做的循環(huán)，每次循環(huán)都需要從首元結(jié)點查找到表尾，假設(shè)多項式開始為升冪排列，如x1+x2+x3+x4+……xn,（這里n<=20）其時間復(fù)雜度為n(n+1)/2,若指數(shù)不是連續(xù)的，則其時間復(fù)雜度加上O(n),所以此算法的時間復(fù)雜度為O（n2）。假設(shè)a有M項，b有N項，則加法和減法算

63、法的時間復(fù)雜度度為M+N，算法中兩多項式相加和相減時，a,b均需按升冪順序輸入結(jié)點。</p><p><b>　　7.運行結(jié)果：</b></p><p>　　（1）(2x+5x8-3.1x11)+(7-5x8+11x9)</p><p><b>　　程序運行結(jié)果為：</b></p><p>　?。?

64、）(6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2+7.8x15)</p><p><b>　　程序運行結(jié)果為：</b></p><p>　?。?）(x+x2+x3)+0</p><p><b>　　程序運行結(jié)果為：</b></p><p>　　(4) (x+x3)-(-x-x-3

65、)</p><p><b>　　程序運行結(jié)果為：</b></p><p><b>　　8.設(shè)計體會與總結(jié)</b></p><p>　　本次程序設(shè)計的總體思路明確，易懂，能夠清楚的分辨出各模塊的功能，利于用戶的閱讀、了解程序，該程序的執(zhí)行過程是相當(dāng)?shù)囊子谧x者使用，它會在每一步都提示用戶接下來的輸入數(shù)據(jù)。當(dāng)然，本次課程設(shè)計還有

66、許多的不足之處，在以后的不斷學(xué)習(xí)當(dāng)中我還會繼續(xù)完善這個程序。</p><p>　　在課程設(shè)計的過程中，深深地體會到了有算法思想和將此算法寫成可執(zhí)行程序，還是有一段距離的，程序出現(xiàn)錯誤并不可怕，只要我們肯耐心的去調(diào)試，去改進(jìn)，最后一定會設(shè)計出一個比較好的程序。拿到課題后，我們首先要對要實現(xiàn)的功能以及數(shù)據(jù)結(jié)構(gòu)有一個初步的規(guī)劃，這樣后邊的工作才會順利進(jìn)行。若是在編寫或執(zhí)行程序的過程中遇到了確實解決不了的問題，需要多和同

67、學(xué)交流。</p><p>　　通過做本次課程設(shè)計，使我收獲了很多東西，知識這方面說起，以前覺得不管什么樣的題還是編程，只要了解算法的思想就行了，到時候用的時候自然就會發(fā)揮出來，可這次的課程設(shè)計卻告訴我并不是這樣的，我在此次課程設(shè)計的編程的時候就遇到了這樣的問題。覺得自己了解算法思想就一定能編出來，可是事實卻不得不又拿起書來繼續(xù)研究，繼續(xù)查找一些相關(guān)的資料，與同學(xué)老師之間交流，互相學(xué)習(xí)之后，才將程序基本編寫出來，但

68、運行過程又出現(xiàn)了一些問題，需要不斷調(diào)試，在老師和同學(xué)的幫助下，程序最終無誤執(zhí)行出來了。 </p><p>　　總體來說，這次數(shù)據(jù)結(jié)構(gòu)課設(shè)讓我的編程能力有了進(jìn)一步提高，我會繼續(xù)努力提升自己的素養(yǎng)，為自己的未來做更多的積淀。</p><p>　　當(dāng)然，在以后的學(xué)習(xí)過程中我也會吸取前面的教訓(xùn)，在學(xué)習(xí)好課本知識的同時努力探索課外的相關(guān)知識，并且理論與實踐結(jié)合起來，去檢驗對理論理解的不足之處，能夠及