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

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

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

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

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

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

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

7、程序?qū)崿F(xiàn)結(jié)果、數(shù)據(jù)驗(yàn)證和實(shí)驗(yàn)總結(jié)等部分。 </p><p>　　3、課程設(shè)計(jì)工作進(jìn)度計(jì)劃：</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è)計(jì)模塊劃分……………………

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

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

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

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

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

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

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

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

17、p><p>　　帶頭結(jié)點(diǎn)單鏈表抽象數(shù)據(jù)類型的結(jié)點(diǎn)結(jié)構(gòu)定義如下：</p><p>　　typedef struct Polynode //多項(xiàng)式結(jié)點(diǎn)</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é)點(diǎn)的多項(xiàng)式的建立函數(shù)Poly

19、list Polycreate()</p><p>　　(2) 帶頭結(jié)點(diǎn)的多項(xiàng)式的降冪輸出函數(shù)void printf(Polylist poly)</p><p>　　(3) 帶頭結(jié)點(diǎn)的多項(xiàng)式的相加函數(shù)Polylist Polyadd(Polylist a,Polylist b)</p><p>　　(4) 帶頭結(jié)點(diǎn)的多項(xiàng)式的相減函數(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é)點(diǎn)指針類型</p><p>　　void Insert(Poly p,Poly h){ </p><p>　　if(p->coef==0) free(p); //系數(shù)為0時(shí)釋放結(jié)點(diǎn)</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é)點(diǎn)</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ù)為新時(shí)將結(jié)點(diǎn)插入</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){//建立一個(gè)頭指針為head、項(xiàng)數(shù)為m的一元多項(xiàng)式</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é)點(diǎn)以接收數(shù)據(jù)</p><p>　　printf("輸入第%d項(xiàng)的系數(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é)點(diǎn)</p><p><b>　　}</b></p><p>　　return head;</p><p>　　}//CreatePoly</p><p>　　void DestroyPoly(Poly p){//銷

31、毀多項(xiàng)式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;//項(xiàng)數(shù)計(jì)數(shù)器</p><p>　　if(!q) { //若多項(xiàng)式為空，輸出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且不是第一項(xiàng)</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多項(xiàng)式已空，但b多項(xiàng)式非空</p><p>　　else return 1;//b多項(xiàng)式已空，但a多項(xiàng)式非空</p><p>　　}//compare</p><p>　　Poly AddPoly(Poly pa,Poly pb){//求解并建立多項(xiàng)式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é)點(diǎn)</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時(shí)，釋放該結(jié)點(diǎn)</p><p><b>　　}//while</

51、b></p><p>　　return headc;</p><p>　　}//AddPoly</p><p>　　Poly SubtractPoly(Poly pa,Poly pb)</p><p>　　{ //求解并建立多項(xiàng)式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的項(xiàng)數(shù):");</p><p>　　scanf("%d",&m);</p><p>　　pa=CreatePoly(pa,m);//建立多項(xiàng)式a</p><p>　　printf(&qu

56、ot;輸入b的項(xiàng)數(shù):");</p><p>　　scanf("%d",&n);</p><p>　　pb=CreatePoly(pb,n);//建立多項(xiàng)式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("多項(xiàng)式a：");PrintPoly(pa);</p><p>　　printf("多項(xiàng)式b：");PrintPoly(pb);continue;</p>

58、;<p><b>　　}</b></p><p>　　if(flag==2){</p><p>　　pc=AddPoly(pa,pb);</p><p>　　printf("多項(xiàng)式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("多項(xiàng)式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>　　建立多項(xiàng)式的時(shí)間復(fù)雜度為O(n),降冪輸出多項(xiàng)式序列算法，由于是對指數(shù)做的循環(huán)，每次循環(huán)都需要從首元結(jié)點(diǎn)查找到表尾，假設(shè)多項(xiàng)式開始為升冪排列，如x1+x2+x3+x4+……xn,（這里n<=20）其時(shí)間復(fù)雜度為n(n+1)/2,若指數(shù)不是連續(xù)的，則其時(shí)間復(fù)雜度加上O(n),所以此算法的時(shí)間復(fù)雜度為O（n2）。假設(shè)a有M項(xiàng)，b有N項(xiàng)，則加法和減法算

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

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

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

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

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

68、運(yùn)行過程又出現(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í)好課本知識的同時(shí)努力探索課外的相關(guān)知識，并且理論與實(shí)踐結(jié)合起來，去檢驗(yàn)對理論理解的不足之處，能夠及