數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告一元多項(xiàng)式的實(shí)現(xiàn)

1、<p>　　《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)</p><p>　　題 目 一元多項(xiàng)式的實(shí)現(xiàn)</p><p>　　學(xué) 號(hào) </p><p>　　學(xué)生姓名 </p><p>　　院 系 計(jì)算機(jī)</p><p>　　專 業(yè) </p

2、><p>　　指導(dǎo)教師 </p><p>　　二Ｏ一二 年 12 月 17 日</p><p><b>　　需求分析</b></p><p>　　建立一元多項(xiàng)式并按照指數(shù)降序排列輸出多項(xiàng)式，將一元多項(xiàng)式輸入并存儲(chǔ)在內(nèi)存中，能夠完成兩個(gè)多項(xiàng)式的加減運(yùn)算并輸出結(jié)果</p><p&

3、gt;<b>　　概要設(shè)計(jì)</b></p><p>　　存儲(chǔ)結(jié)構(gòu)：一元多項(xiàng)式的表示在計(jì)算機(jī)內(nèi)可以用鏈表來表示，為了節(jié)省存儲(chǔ)空間，只存儲(chǔ)多項(xiàng)式中系數(shù)非零的項(xiàng)。鏈表中的每一個(gè)結(jié)點(diǎn)存放多項(xiàng)式的一個(gè)系數(shù)非零項(xiàng)，它包含三個(gè)域，分別存放該項(xiàng)的系數(shù)、指數(shù)以及指向下一個(gè)多項(xiàng)式項(xiàng)結(jié)點(diǎn)的指針。創(chuàng)建一元多項(xiàng)式鏈表，對(duì)一元多項(xiàng)式的運(yùn)算中會(huì)出現(xiàn)的各種可能情況進(jìn)行分析，實(shí)現(xiàn)一元多項(xiàng)式的相加、相減操作。</p>

4、;<p><b>　　基本算法：</b></p><p><b>　　1、輸入輸出</b></p><p>　?。?）功能：將要進(jìn)行運(yùn)算的多項(xiàng)式輸入輸出。</p><p>　　（2）數(shù)據(jù)流入：要輸入的多項(xiàng)式的系數(shù)與指數(shù)。</p><p>　?。?）數(shù)據(jù)流出：合并同類項(xiàng)后的多項(xiàng)式。<

5、;/p><p>　?。?）程序流程圖：多項(xiàng)式輸入流程圖如圖1所示。</p><p>　?。?）測(cè)試要點(diǎn)：輸入的多項(xiàng)式是否正確，若輸入錯(cuò)誤則重新輸入</p><p><b>　　2、多項(xiàng)式的加法</b></p><p>　?。?）功能：將兩多項(xiàng)式相加。</p><p>　?。?）數(shù)據(jù)流入：輸入函數(shù)。&l

6、t;/p><p>　?。?）數(shù)據(jù)流出：多項(xiàng)式相加后的結(jié)果。</p><p>　?。?）程序流程圖：多項(xiàng)式的加法流程圖如圖2所示。</p><p>　?。?）測(cè)試要點(diǎn)：兩多項(xiàng)式是否為空，為空則提示重新輸入，否則，進(jìn)行運(yùn)算。</p><p><b>　　圖表 2</b></p><p><b>

7、　　3、多項(xiàng)式的減法</b></p><p>　?。?）功能：將兩多項(xiàng)式相減。</p><p>　?。?）數(shù)據(jù)流入：調(diào)用輸入函數(shù)。</p><p>　?。?）數(shù)據(jù)流出：多項(xiàng)式相減后的結(jié)果。</p><p>　?。?）程序流程圖：多項(xiàng)式的減法流程圖如圖3所示。</p><p>　?。?）測(cè)試要點(diǎn)：兩多項(xiàng)式是否

8、為空，為空則提示重新輸入，否則，進(jìn)行運(yùn)算。</p><p><b>　　詳細(xì)設(shè)計(jì) </b></p><p>　　#include<stdio.h></p><p>　　#include<malloc.h></p><p>　　typedef struct Polynomial{</p>

9、;<p>　　float coef;</p><p><b>　　int expn;</b></p><p>　　struct Polynomial *next;</p><p>　　}*Polyn,Polynomial; //Polyn為結(jié)點(diǎn)指針類型</p><p>　　voi

10、d Insert(Polyn p,Polyn h){ </p><p>　　if(p->coef==0) free(p); //系數(shù)為0的話釋放結(jié)點(diǎn)</p><p><b>　　else{</b></p><p>　　Polyn q1,q2;</p><p>　　q1=h;q2=h->ne

11、xt;</p><p>　　while(q2&&p->expn<q2->expn){ //查找插入位置</p><p><b>　　q1=q2;</b></p><p>　　q2=q2->next;</p><p><b>　　}</b></p>

12、;<p>　　if(q2&&p->expn==q2->expn){ //將指數(shù)相同相合并</p><p>　　q2->coef+=p->coef;</p><p><b>　　free(p);</b></p><p>　　if(!q2->coef){ /

13、/系數(shù)為0的話釋放結(jié)點(diǎn)</p><p>　　q1->next=q2->next;</p><p><b>　　free(q2);</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　el

14、se{ //指數(shù)為新時(shí)將結(jié)點(diǎn)插入</p><p>　　p->next=q2;</p><p>　　q1->next=p;</p><p><b>　　}</b></p><p><b>　　}</b></p><p&g

15、t;<b>　　}//Insert</b></p><p>　　Polyn CreatePolyn(Polyn head,int m){//建立一個(gè)頭指針為head、項(xiàng)數(shù)為m的一元多項(xiàng)式</p><p><b>　　int i;</b></p><p><b>　　Polyn p;</b></p

16、><p>　　p=head=(Polyn)malloc(sizeof(struct Polynomial));</p><p>　　head->next=NULL;</p><p>　　for(i=0;i<m;i++){</p><p>　　p=(Polyn)malloc(sizeof(struct Polynomial));//建立

17、新結(jié)點(diǎn)以接收數(shù)據(jù)</p><p>　　printf("請(qǐng)輸入第%d項(xiàng)的系數(shù)與指數(shù):",i+1);</p><p>　　scanf("%f %d",&p->coef,&p->expn);</p><p>　　Insert(p,head); //調(diào)用Insert函數(shù)插入結(jié)點(diǎn)</p>&

18、lt;p><b>　　}</b></p><p>　　return head;</p><p>　　}//CreatePolyn</p><p>　　void DestroyPolyn(Polyn p){//銷毀多項(xiàng)式p</p><p>　　Polyn q1,q2;</p><p>　　q1

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

20、/p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void PrintPolyn(Polyn P){ </p><p>　　Polyn q=P->next; </p><p>　　int flag=1;//項(xiàng)數(shù)計(jì)數(shù)器</

21、p><p>　　if(!q) { //若多項(xiàng)式為空，輸出0</p><p>　　putchar('0'); </p><p>　　printf("\n");</p><p><b>　　return;</b></p><p><b>　　} </

22、b></p><p>　　while (q){</p><p>　　if(q->coef>0&&flag!=1) putchar('+'); //系數(shù)大于0且不是第一項(xiàng)</p><p>　　if(q->coef!=1&&q->coef!=-1){//系數(shù)非1或-1的普通情況</p&g

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

24、;　　}</b></p><p><b>　　else{</b></p><p>　　if(q->coef==1){</p><p>　　if(!q->expn) putchar('1'); </p><p>　　else if(q->expn==1) putchar(

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

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

27、></p><p>　　q=q->next; </p><p><b>　　flag++;</b></p><p><b>　　}//while</b></p><p>　　printf("\n");</p><p>　　}//PrintPol

28、yn</p><p>　　int compare(Polyn a,Polyn b){</p><p><b>　　if(a&&b){</b></p><p>　　if(!b||a->expn>b->expn) return 1;</p><p>　　else if(!a||a->e

29、xpn<b->expn) return -1;</p><p>　　else return 0;</p><p><b>　　}</b></p><p>　　else if(!a&&b) return -1;//a多項(xiàng)式已空，但b多項(xiàng)式非空</p><p>　　else return 1;//

30、b多項(xiàng)式已空，但a多項(xiàng)式非空</p><p>　　}//compare</p><p>　　Polyn AddPolyn(Polyn pa,Polyn pb){//求解并建立多項(xiàng)式a+b，返回其頭指針</p><p>　　Polyn qa=pa->next;</p><p>　　Polyn qb=pb->next;</p&g

31、t;<p>　　Polyn headc,hc,qc;</p><p>　　hc=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結(jié)點(diǎn)</p><p>　　hc->next=NULL;</p><p><b>　　headc=hc;</b></p><p>　

32、　while(qa||qb){</p><p>　　qc=(Polyn)malloc(sizeof(struct Polynomial));</p><p>　　switch(compare(qa,qb)){</p><p><b>　　case 1:</b></p><p><b>　　{</b>

33、</p><p>　　qc->coef=qa->coef;</p><p>　　qc->expn=qa->expn;</p><p>　　qa=qa->next;</p><p><b>　　break;</b></p><p><b>　　}</b&

34、gt;</p><p><b>　　case 0:</b></p><p><b>　　{ </b></p><p>　　qc->coef=qa->coef+qb->coef;</p><p>　　qc->expn=qa->expn;</p><p&

35、gt;　　qa=qa->next;</p><p>　　qb=qb->next;</p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　case -1:</b></p><p>

36、<b>　　{</b></p><p>　　qc->coef=qb->coef;</p><p>　　qc->expn=qb->expn;</p><p>　　qb=qb->next;</p><p><b>　　break;</b></p><p&

37、gt;<b>　　} </b></p><p><b>　　}//switch</b></p><p>　　if(qc->coef!=0){</p><p>　　qc->next=hc->next;</p><p>　　hc->next=qc;</p><

38、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</b></p><p>　　return headc;</p

39、><p>　　}//AddPolyn</p><p>　　Polyn SubtractPolyn(Polyn pa,Polyn pb){//求解并建立多項(xiàng)式a+b，返回其頭指針</p><p>　　Polyn h=pb;</p><p>　　Polyn p=pb->next;</p><p><b>　　P

40、olyn pd;</b></p><p>　　while(p){ //將pb的系數(shù)取反</p><p>　　p->coef*=-1;</p><p>　　p=p->next;</p><p><b>　　}</b></p><p>　　pd=AddPol

41、yn(pa,h);</p><p>　　for(p=h->next;p;p=p->next) //恢復(fù)pb的系數(shù)</p><p>　　p->coef*=-1;</p><p>　　return pd;</p><p>　　}//SubtractPolyn</p><p>　　int main()

42、{</p><p>　　int m,n,flag=0;</p><p><b>　　float x;</b></p><p>　　Polyn pa=0,pb=0,pc,pd,pe,pf;//定義各式的頭指針，pa與pb在使用前付初值NULL</p><p>　　printf("請(qǐng)輸入a的項(xiàng)數(shù):");&

43、lt;/p><p>　　scanf("%d",&m);</p><p>　　pa=CreatePolyn(pa,m);//建立多項(xiàng)式a</p><p>　　printf("請(qǐng)輸入b的項(xiàng)數(shù):");</p><p>　　scanf("%d",&n);</p>&

44、lt;p>　　pb=CreatePolyn(pb,n);//建立多項(xiàng)式a</p><p><b>　　//輸出菜單</b></p><p>　　printf("**********************************************\n");</p><p>　　printf("操作提示：

45、\n\t1.輸出多項(xiàng)式a和b\n\t2.建立多項(xiàng)式a+b\n\t3.建立多項(xiàng)式a-b\n");</p><p>　　printf("\t4.退出\n**********************************************\n");</p><p>　　for(;;flag=0){</p><p>　　printf(&

46、quot;執(zhí)行操作：");</p><p>　　scanf("%d",&flag);</p><p>　　if(flag==1){</p><p>　　printf("多項(xiàng)式a：");PrintPolyn(pa);</p><p>　　printf("多項(xiàng)式b：")

47、;PrintPolyn(pb);continue;</p><p><b>　　}</b></p><p>　　if(flag==2){</p><p>　　pc=AddPolyn(pa,pb);</p><p>　　printf("多項(xiàng)式a+b：");PrintPolyn(pc);</p>

48、;<p>　　DestroyPolyn(pc);continue;</p><p><b>　　}</b></p><p>　　if(flag==3){</p><p>　　pd=SubtractPolyn(pa,pb);</p><p>　　printf("多項(xiàng)式a-b：");Prin

49、tPolyn(pd);</p><p>　　DestroyPolyn(pd);continue;</p><p><b>　　}</b></p><p>　　if(flag==4) break;</p><p>　　if(flag<1||flag>4) printf("Error!!!\n"

50、;);continue;</p><p><b>　　}//for</b></p><p>　　DestroyPolyn(pa);</p><p>　　DestroyPolyn(pb);</p><p><b>　　return 0;</b></p><p><b>

51、;　　}</b></p><p><b>　　調(diào)試結(jié)果</b></p><p><b>　　測(cè)試的數(shù)據(jù)及結(jié)果</b></p><p>　　算法的時(shí)間復(fù)雜度及改進(jìn)</p><p>　　算法的時(shí)間復(fù)雜度：一元多項(xiàng)式的加法運(yùn)算的時(shí)間復(fù)雜度為O(m+n）,減法運(yùn)算的時(shí)間復(fù)雜度為O(m-n)，其中

52、m，n分別表示二個(gè)一元多項(xiàng)式的項(xiàng)數(shù)。</p><p>　　問題和改進(jìn)思想：在設(shè)計(jì)該算法時(shí)，出現(xiàn)了一些問題，例如在建立鏈表時(shí)頭指針的設(shè)立導(dǎo)致了之后運(yùn)用到相關(guān)的指針時(shí)沒能很好的移動(dòng)指針出現(xiàn)了數(shù)據(jù)重復(fù)輸出或是輸出系統(tǒng)缺省值，不能實(shí)現(xiàn)算法。實(shí)現(xiàn)加法時(shí)該鏈表并沒有向通常那樣通過建立第三個(gè)鏈表來存放運(yùn)算結(jié)果，而是再度利用了鏈表之一來進(jìn)行節(jié)點(diǎn)的比較插入刪除等操作。為了使輸入數(shù)據(jù)按指數(shù)降序排列，可在數(shù)據(jù)的輸入后先做一個(gè)節(jié)點(diǎn)的排序