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

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

2、非零項,它包含三個域,分別存放該項的系數(shù)、指數(shù)以及指向下一個多項式項結(jié)點的指針.創(chuàng)立一元多項式鏈表,對一元多項式的運算中會出現(xiàn)的各種可能情況進(jìn)行分析,實現(xiàn)一元多項式的相加、相減操作.1 .單連表的抽象數(shù)據(jù)類型定義：ADTList數(shù)據(jù)對象：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)造一個空的線性表CreatPolyn(&L)/操作結(jié)果：構(gòu)造一個以單連表存儲的多項試DispPolyn(L)/操作結(jié)果：顯示多項試Polyn(&pa,&

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

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

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

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

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

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

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

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

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

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

14、atePolynvoidDestroyPolyn(Polynp)/銷毀多項式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;/項數(shù)計數(shù)器if(!q)/假設(shè)多項式為空,輸出0putchar('0');printf("n");return;while(q)if(q->coef>0&&flag!=1)

15、putchar('+');/系數(shù)大于0且不是第一項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多項式已空,但b多項式非空elsereturn1;/b多項式已空,但a多項式非空/comparePolynAddPolyn(Polynpa,Polynpb)/求解并建立多項式a+b,返回其頭指針Polynqa=pa->next;Polynqb=pb->next;Polynheadc,hc,qc;建立頭結(jié)點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時,釋放該結(jié)點/whilereturnheadc;/AddPolynPolynSubtractPolyn(Polynpa,Polynpb)/求解并建立多項式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("請輸入a的項數(shù):");scanf("%d",&m);pa=CreatePolyn(pa,m);/建立多項式aprintf("請輸入b的項數(shù):");scan