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

1、<p><b>　　一元多項(xiàng)式的計(jì)算</b></p><p><b>　　需求分析</b></p><p>　　建立一元多項(xiàng)式并按照指數(shù)降序排列輸出多項(xiàng)式，將一元多項(xiàng)式輸入并存儲(chǔ)在內(nèi)存中，能夠完成兩個(gè)多項(xiàng)式的加減運(yùn)算并輸出結(jié)果。</p><p><b>　　概要設(shè)計(jì)</b></p>

2、;<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><p><b>　　基本算法：</b>

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

4、如圖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ù)。</p><p>　?。?）數(shù)據(jù)流出：多項(xiàng)式相加后的結(jié)

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

6、>　　（1）功能：將兩多項(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)式是否為空，為空則提示重新輸入，否則，進(jìn)行運(yùn)算。</p><

7、p><b>　　詳細(xì)設(shè)計(jì) </b></p><p>　　#include<stdio.h></p><p>　　#include<malloc.h></p><p>　　typedef struct Polynomial{</p><p>　　float coef;</p>

8、<p><b>　　int expn;</b></p><p>　　struct Polynomial *next;</p><p>　　}*Polyn,Polynomial; //Polyn為結(jié)點(diǎn)指針類型</p><p>　　void Insert(Polyn p,Polyn h){ </p

9、><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->next;</p><p>　　while(q2&am

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

11、pn==q2->expn){ //將指數(shù)相同相合并</p><p>　　q2->coef+=p->coef;</p><p><b>　　free(p);</b></p><p>　　if(!q2->coef){ //系數(shù)為0的話釋放結(jié)點(diǎn)</p><p>　　q1-

12、>next=q2->next;</p><p><b>　　free(q2);</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　else{ //指數(shù)為新時(shí)將

13、結(jié)點(diǎn)插入</p><p>　　p->next=q2;</p><p>　　q1->next=p;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}//Insert</b></

14、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><p>　　p=head=(Polyn)malloc

15、(sizeof(struct Polynomial));</p><p>　　head->next=NULL;</p><p>　　for(i=0;i<m;i++){</p><p>　　p=(Polyn)malloc(sizeof(struct Polynomial));//建立新結(jié)點(diǎn)以接收數(shù)據(jù)</p><p>　　printf

16、("請(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><p><b>　　}</b></p&

17、gt;<p>　　return head;</p><p>　　}//CreatePolyn</p><p>　　void DestroyPolyn(Polyn p){//銷毀多項(xiàng)式p</p><p>　　Polyn q1,q2;</p><p>　　q1=p->next;</p><p>　　q2

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

19、t;</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ù)器</p><p>　　if(!q) { //若多項(xiàng)式為空，輸

20、出0</p><p>　　putchar('0'); </p><p>　　printf("\n");</p><p><b>　　return;</b></p><p><b>　　} </b></p><p>　　while (q)

21、{</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><p>　　printf("%g",

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

23、t;b>　　else{</b></p><p>　　if(q->coef==1){</p><p>　　if(!q->expn) putchar('1'); </p><p>　　else if(q->expn==1) putchar('X'); </p><p>　　els

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

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

26、xt; </p><p><b>　　flag++;</b></p><p><b>　　}//while</b></p><p>　　printf("\n");</p><p>　　}//PrintPolyn</p><p>　　int compare(

27、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->expn<b->expn) return -1;</p&g

28、t;<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;//b多項(xiàng)式已空，但a多項(xiàng)式非空</p><p>　　

29、}//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><p>　　Polyn headc,hc,qc;<

30、/p><p>　　hc=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結(jié)點(diǎn)</p><p>　　hc->next=NULL;</p><p><b>　　headc=hc;</b></p><p>　　while(qa||qb){</p><p>　

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

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

33、se 0:</b></p><p><b>　　{ </b></p><p>　　qc->coef=qa->coef+qb->coef;</p><p>　　qc->expn=qa->expn;</p><p>　　qa=qa->next;</p><p

34、>　　qb=qb->next;</p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　case -1:</b></p><p><b>　　{</b></p><

35、;p>　　qc->coef=qb->coef;</p><p>　　qc->expn=qb->expn;</p><p>　　qb=qb->next;</p><p><b>　　break;</b></p><p><b>　　} </b></p>

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

37、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><p>　　}//AddPolyn</p>

38、;<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>　　Polyn pd;</b></p><p&g

39、t;　　while(p){ //將pb的系數(shù)取反</p><p>　　p->coef*=-1;</p><p>　　p=p->next;</p><p><b>　　}</b></p><p>　　pd=AddPolyn(pa,h);</p><p>　　for(p

40、=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(){</p><p>　　int m,n,flag=

41、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ù):");</p><p>　　scanf("%d&

42、quot;,&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><p>　　pb=CreatePolyn(pb,n);//建立多項(xiàng)

43、式a</p><p><b>　　//輸出菜單</b></p><p>　　printf("**********************************************\n");</p><p>　　printf("操作提示：\n\t1.輸出多項(xiàng)式a和b\n\t2.建立多項(xiàng)式a+b\n\t3.建立多

44、項(xiàng)式a-b\n");</p><p>　　printf("\t4.退出\n**********************************************\n");</p><p>　　for(;;flag=0){</p><p>　　printf("執(zhí)行操作：");</p><p&g

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

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

47、ue;</p><p><b>　　}</b></p><p>　　if(flag==3){</p><p>　　pd=SubtractPolyn(pa,pb);</p><p>　　printf("多項(xiàng)式a-b：");PrintPolyn(pd);</p><p>　　Des

48、troyPolyn(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><

49、b>　　}//for</b></p><p>　　DestroyPolyn(pa);</p><p>　　DestroyPolyn(pb);</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>&l

50、t;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)，其中m，n分別表示二個(gè)一元多項(xiàng)式的項(xiàng)數(shù)。</p><p&g