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

1、一元多項(xiàng)式的計(jì)算一加,減摘要題目一元多項(xiàng)式計(jì)算任務(wù)：能夠根據(jù)指數(shù)降序排列建立并輸由多項(xiàng)式；能夠完成兩個(gè)多項(xiàng)式的相加、相減,并將結(jié)果輸入；目錄1 .引言2 .需求分析3 .概要設(shè)計(jì)4 .詳細(xì)設(shè)計(jì)5 .測(cè)試結(jié)果6 .調(diào)試分析7 .設(shè)計(jì)體會(huì)8 .結(jié)束語(yǔ)通過(guò)c語(yǔ)言使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)一元多項(xiàng)式加法、減法和乘法的運(yùn)算.按指數(shù)降序排列二：需求分析建立一元多項(xiàng)式并根據(jù)指數(shù)降序排列輸出多項(xiàng)式,將一元多項(xiàng)式輸入并存儲(chǔ)在內(nèi)存中,能夠完成兩個(gè)多項(xiàng)式的加減運(yùn)算并輸出結(jié)果三：概要設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)：一元多項(xiàng)式的表示在計(jì)算機(jī)內(nèi)可以用鏈表來(lái)表示,為了節(jié)省存儲(chǔ)空間,只存儲(chǔ)多項(xiàng)式中系數(shù)非零的項(xiàng).鏈表中的每一個(gè)結(jié)點(diǎn)存放多項(xiàng)式的一個(gè)系數(shù)

2、非零項(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)式的相加、相減操作.1 .單連表的抽象數(shù)據(jù)類型定義：ADTList數(shù)據(jù)對(duì)象：D=ai|aiElemSet,i=1,2,巾網(wǎng)>0數(shù)據(jù)關(guān)系：R1=<ai-1,ai>|ai-1,aiD,i=2,n根本操作：InitList(&L)/操作結(jié)果：構(gòu)造一個(gè)空的線性表CreatPolyn(&L)/操作結(jié)果：構(gòu)造一個(gè)以單連表存儲(chǔ)的多項(xiàng)試DispPolyn(L)/操作結(jié)果：顯示多項(xiàng)試Polyn(&pa,&

3、;pb)/操作結(jié)果：顯示兩個(gè)多項(xiàng)試相加,相減的結(jié)果ADTList2 .本程序包含模塊：typedefstructLNode/定義單鏈表LNode,*LinkList;voidInitList(LinkList&L)/voidCreatPolyn(LinkList&L)/voidDispPolyn(LinkListL)/定義一個(gè)空表用單鏈表定義一個(gè)多項(xiàng)式顯示輸入的多項(xiàng)式()voidPolyn(LinkList&pa,LinkList&pb)()voidmain()(/定義一個(gè)單連表;cout<<endl<<"*歡送來(lái)到元多項(xiàng)式計(jì)算

4、程序*<<endl;LNode*L1,*L2;Polyn(L1,L2);2.1 力口,減操作模塊一一實(shí)現(xiàn)加減操作各模塊之間的調(diào)用關(guān)系如下：主程序模塊加法操作模塊減法操作模塊根本算法：1、輸入輸出(1)功能：將要進(jìn)行運(yùn)算的多項(xiàng)式輸入輸出.(2)數(shù)據(jù)流入：要輸入的多項(xiàng)式的系數(shù)與指數(shù).(3)數(shù)據(jù)流出：合并同類項(xiàng)后的多項(xiàng)式.(4)程序流程圖：多項(xiàng)式輸入流程圖如圖1所示.(5)測(cè)試要點(diǎn)：輸入的多項(xiàng)式是否正確,假設(shè)輸入錯(cuò)誤那么重新輸入圖表1(2)(3)(4)(5) 算.2、多項(xiàng)式的加法(1)功能：將兩多項(xiàng)式相加.數(shù)據(jù)流入：輸入函數(shù).數(shù)據(jù)流出：多項(xiàng)式相加后的結(jié)果.程序流程圖：多項(xiàng)式的加法流程圖如

5、圖2所示.測(cè)試要點(diǎn)：兩多項(xiàng)式是否為空,為空那么提示重新輸入,否那么,進(jìn)行運(yùn)圖表23、多項(xiàng)式的減法(1)功能：將兩多項(xiàng)式相減.(2)(3)(4)(5) 算.數(shù)據(jù)流入：調(diào)用輸入函數(shù).數(shù)據(jù)流出：多項(xiàng)式相減后的結(jié)果.程序流程圖：多項(xiàng)式的減法流程圖如圖3所小.測(cè)試要點(diǎn)：兩多項(xiàng)式是否為空,為空那么提示重新輸入,否那么,進(jìn)行運(yùn)圖表3四.詳細(xì)設(shè)計(jì)1 .根據(jù)題目要求采用單連表存儲(chǔ)結(jié)構(gòu)typedefstructLNode/定義單鏈表(LNode,*LinkList;voidInitList(LinkList&L)/(voidCreatPolyn(LinkList&L)/(voidDispPolyn

6、(LinkListL)/(定義一個(gè)空表用單鏈表定義一個(gè)多項(xiàng)式顯示輸入的多項(xiàng)式voidPolyn(LinkList&pa,LinkList&pb)(2 .主函數(shù)mainvoidmain()(LNode*L1,*L2;Polyn(L1,L2);3 .函數(shù)的調(diào)用關(guān)系層次結(jié)構(gòu)多項(xiàng)式Polyn用單鏈表定義多項(xiàng)式CreatPolyn定義一個(gè)空表InitList顯示輸入的多項(xiàng)式DispPolyn五.調(diào)試分析采用單連表形式根據(jù)指數(shù)降序排列建立并輸出多項(xiàng)式；在相加,相減的過(guò)程中如果指數(shù)相同就執(zhí)行系數(shù)相加,相減,否那么就把大的項(xiàng)直接寫入.完成兩個(gè)多項(xiàng)式的相加、相減；將從新得到的單連表結(jié)果輸出；該算

7、法的時(shí)間復(fù)雜度為兩個(gè)多項(xiàng)式的項(xiàng)式之和六：調(diào)試結(jié)果1 .測(cè)試的數(shù)據(jù)及結(jié)果eL-AProgra»l14X15+13X14+12«a13j-56N67-15X4&H4K15+13K*14+12K13Keytocontinue2.算法的時(shí)間復(fù)雜度及改良算法的時(shí)間復(fù)雜度：一元多項(xiàng)式的加法運(yùn)算的時(shí)間復(fù)雜度為O(m+n減法運(yùn)算的時(shí)間復(fù)雜度為O(m-n),其中mn分別表示二個(gè)一元多項(xiàng)式的項(xiàng)數(shù).問(wèn)題和改良思想：在設(shè)計(jì)該算法時(shí),出現(xiàn)了一些問(wèn)題,例如在建立鏈表時(shí)頭指針的設(shè)立導(dǎo)致了之后運(yùn)用到相關(guān)的指針時(shí)沒(méi)能很好的移動(dòng)指針出現(xiàn)了數(shù)據(jù)重復(fù)輸出或是輸出系統(tǒng)缺省值,不能實(shí)現(xiàn)算法.實(shí)現(xiàn)加法時(shí)該鏈表并

8、沒(méi)有向通常那樣通過(guò)建立第三個(gè)鏈表來(lái)存放運(yùn)算結(jié)果,而是再度利用了鏈表之一來(lái)進(jìn)行節(jié)點(diǎn)的比擬插入刪除等操作.為了使輸入數(shù)據(jù)按指數(shù)降序排列,可在數(shù)據(jù)的輸入后先做一個(gè)節(jié)點(diǎn)的排序函數(shù),通過(guò)對(duì)鏈表排序后再進(jìn)行之后加減運(yùn)算.七.心、得體會(huì)：一元多項(xiàng)式計(jì)算是一個(gè)的單鏈表的運(yùn)用,通過(guò)這個(gè)程序可以測(cè)我們以前的學(xué)習(xí)情況,看看我們是否對(duì)單鏈表真正的理解.一元多項(xiàng)式計(jì)算器的根本功能定為：(1)建立多項(xiàng)式(2)輸出多項(xiàng)式(3)兩個(gè)多項(xiàng)式相加,建立并輸出和多項(xiàng)式(4)兩個(gè)多項(xiàng)式相減,建立并輸出差多項(xiàng)式能夠根據(jù)指數(shù)降序排列建立并輸出多項(xiàng)式；能夠完成兩個(gè)多項(xiàng)式的相加、相減,并將結(jié)果輸出；1Je?XIlcrosottVisualb

9、tudigUyTrojoctn一元多變式的加,注*345111234ill-發(fā)Q匕匕日匕口JL1JL11與與與數(shù)版繪46sb4S粉出1與與數(shù)致三系系系=zs系莪的的的數(shù)的的項(xiàng)項(xiàng)項(xiàng)項(xiàng)項(xiàng)項(xiàng)項(xiàng)UM-1212-目gFMRsF白HFrFk入入入入入入T-baaa式式式項(xiàng)項(xiàng)項(xiàng)出立不里式操行項(xiàng)項(xiàng)行項(xiàng)行項(xiàng)行魚/I-b-b-wV-作需作第a-5結(jié)束語(yǔ):時(shí)間過(guò)的很快,在不知不覺(jué)中,課程設(shè)計(jì)也接近了尾聲.說(shuō)起課程設(shè)計(jì),我認(rèn)為最重要的就是做好設(shè)計(jì)的預(yù)習(xí),并且認(rèn)真的去復(fù)習(xí)以前的知識(shí)和查各種資料同時(shí)認(rèn)真的研究老師給的題目,老師對(duì)題目的講解要一絲不茍的去聽去想,由于只有都明白了,做起設(shè)計(jì)來(lái)才會(huì)有底,有信心.課程設(shè)計(jì)是一門培

10、養(yǎng)學(xué)生綜合運(yùn)用所學(xué)知識(shí),發(fā)現(xiàn),提出,分析和解決實(shí)際問(wèn)題的學(xué)科,它能充分鍛煉我們的動(dòng)手水平,時(shí)我們實(shí)踐水平的重要環(huán)節(jié),是對(duì)學(xué)生實(shí)際工作水平的具體練習(xí)和考察過(guò)程.我想這次不只是一次簡(jiǎn)單的課程設(shè)計(jì),更表達(dá)了數(shù)據(jù)結(jié)構(gòu)算法和生活的緊密聯(lián)系.生活中也存在許多與數(shù)據(jù)結(jié)構(gòu)有關(guān)聯(lián)的事情,它讓人不得不深思,這一個(gè)學(xué)期的學(xué)習(xí),這兩年來(lái)的大學(xué)學(xué)習(xí)生涯,自己究竟學(xué)會(huì)了什么,掌握了多少,我也不清楚,我以前也瘋狂的玩過(guò),現(xiàn)在才知道自己時(shí)多么的缺乏知識(shí),大多數(shù)問(wèn)題自己不能解決,感覺(jué)將來(lái)自己是否能勝任以后作編譯人員的職位.我想大家都心里都有很多的感觸.對(duì)于自己,我想我已經(jīng)熟悉到了自己的缺乏,在今后的學(xué)習(xí)過(guò)程中,我一定以最好的心

11、態(tài)去對(duì)待,以最好的面貌來(lái)迎接大三的軟件專業(yè)課程,并且經(jīng)常上機(jī)調(diào)試,堅(jiān)持理論與實(shí)踐相結(jié)合.相信自己將會(huì)有很大的進(jìn)步.附錄詳細(xì)設(shè)計(jì)#include<stdio.h>#include<malloc.h>typedefstructPolynomialfloatcoef;intexpn;structPolynomial*next;*Polyn,Polynomial;/Polyn為結(jié)點(diǎn)指針類型voidInsert(Polynp,Polynh)if(p->coef=0)free(p);/系數(shù)為0的話釋放結(jié)點(diǎn)elsePolynq1,q2;q1=h;q2=h->next;wh

12、ile(q2&&p->expn<q2->expn)/查找插入位置q1=q2;q2=q2->next;if(q2&&p->expn=q2->expn)/將指數(shù)相同相合并q2->coef+=p->coef;free(p);if(!q2->coef)/系數(shù)為0的話釋放結(jié)點(diǎn)q1->next=q2->next;free(q2);else/指數(shù)為新時(shí)將結(jié)點(diǎn)插入p->next=q2;q1->next=p;/InsertPolynCreatePolyn(Polynhead,intm)/建立一個(gè)頭指針為

13、head、項(xiàng)數(shù)為m的一元多項(xiàng)式inti;Polynp;p=head=(Polyn)malloc(sizeof(structPolynomial);head->next=NULL;for(i=0;i<m;i+)p=(Polyn)malloc(sizeof(structPolynomial);/建立新結(jié)點(diǎn)以接收數(shù)據(jù)printf("請(qǐng)輸入第曲的系數(shù)與指數(shù):",i+1);scanf("%f%d",&p->coef,&p->expn);Insert(p,head);/調(diào)用Insert函數(shù)插入結(jié)點(diǎn)returnhead;/Cre

14、atePolynvoidDestroyPolyn(Polynp)/銷毀多項(xiàng)式pPolynq1,q2;q1=p->next;q2=q1->next;while(q1->next)free(q1);q1=q2;/指針后移q2=q2->next;voidPrintPolyn(PolynP)Polynq=P->next;intflag=1;/項(xiàng)數(shù)計(jì)數(shù)器if(!q)/假設(shè)多項(xiàng)式為空,輸出0putchar('0');printf("n");return;while(q)if(q->coef>0&&flag!=1)

15、putchar('+');/系數(shù)大于0且不是第一項(xiàng)if(q->coef!=1&&q->coef!=-1)/系數(shù)非1或-1的普通情況printf("%g,q->coef);if(q->expn=1)putchar('X');elseif(q->expn)printf("XA%d",q->expn);elseif(q->coef=1)if(!q->expn)putchar('1');elseif(q->expn=1)putchar('X'

16、;);elseprintf("XA%d",q->expn);)if(q->coef=-1)if(!q->expn)printf("-1");elseif(q->expn=1)printf("-X");elseprintf("-XA%d",q->expn);)q=q->next;flag+;/whileprintf("n");/PrintPolynintcompare(Polyna,Polynb)if(a&&b)if(!b|a->expn&

17、gt;b->expn)return1;elseif(!a|a->expn<b->expn)return-1;elsereturn0;elseif(!a&&b)return-1;/a多項(xiàng)式已空,但b多項(xiàng)式非空elsereturn1;/b多項(xiàng)式已空,但a多項(xiàng)式非空/comparePolynAddPolyn(Polynpa,Polynpb)/求解并建立多項(xiàng)式a+b,返回其頭指針Polynqa=pa->next;Polynqb=pb->next;Polynheadc,hc,qc;建立頭結(jié)點(diǎn)hc=(Polyn)malloc(sizeof(structP

18、olynomial);/hc->next=NULL;headc=hc;while(qa|qb)qc=(Polyn)malloc(sizeof(structPolynomial);switch(compare(qa,qb)case1:qc->coef=qa->coef;qc->expn=qa->expn;qa=qa->next;break;case0:qc->coef=qa->coef+qb->coef;qc->expn=qa->expn;qa=qa->next;qb=qb->next;break;case-1:qc-

19、>coef=qb->coef;qc->expn=qb->expn;qb=qb->next;break;/switchif(qc->coef!=0)hc->next=qc;hc=qc;)elsefree(qc);/當(dāng)相加系數(shù)為0時(shí),釋放該結(jié)點(diǎn)/whilereturnheadc;/AddPolynPolynSubtractPolyn(Polynpa,Polynpb)/求解并建立多項(xiàng)式a+b,返回其頭指針Polynh=pb;Polynp=pb->next;Polynpd;while(p)/將pb的系數(shù)取反p->coef*=-1;p=p->n

20、ext;pd=AddPolyn(pa,h);for(p=h->next;p;p=p->next)/恢復(fù)pb的系數(shù)p->coef*=-1;returnpd;/SubtractPolynintmain()intm,n,flag=0;floatx;Polynpa=0,pb=0,pc,pd,pe,pf;/定義各式的頭指針,pa與pb在使用前付初值NULLprintf("請(qǐng)輸入a的項(xiàng)數(shù):");scanf("%d",&m);pa=CreatePolyn(pa,m);/建立多項(xiàng)式aprintf("請(qǐng)輸入b的項(xiàng)數(shù):");scan