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

1、<p>　　一元多項(xiàng)式的計(jì)算—加，減</p><p>　　摘要(題目) 一元多項(xiàng)式計(jì)算</p><p>　　任務(wù)：能夠按照指數(shù)降序排列建立并輸出多項(xiàng)式；</p><p>　　能夠完成兩個(gè)多項(xiàng)式的相加、相減，并將結(jié)果輸入；</p><p><b>　　目錄</b></p><p><

2、b>　　1.引言 </b></p><p><b>　　2.需求分析</b></p><p><b>　　3.概要設(shè)計(jì)</b></p><p><b>　　4.詳細(xì)設(shè)計(jì)</b></p><p><b>　　5.測(cè)試結(jié)果</b></p

3、><p><b>　　6.調(diào)試分析</b></p><p><b>　　7.設(shè)計(jì)體會(huì)</b></p><p><b>　　8.結(jié)束語</b></p><p><b>　　一:引言:</b></p><p>　　通過C語言使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

4、實(shí)現(xiàn)一元多項(xiàng)式加法、減法和乘法的運(yùn)算。按指數(shù)降序排列。 </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><

5、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>　　1． 單連表的抽象數(shù)據(jù)類型定義：</p>&l

6、t;p>　　ADT List{ 數(shù)據(jù)對(duì)象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0} 數(shù)據(jù)關(guān)系：R1={<ai-1,ai>| ai-1, ai∈D,i=2,…,n} </p><p><b>　　基本操作：</b></p><p>　　InitList（＆L）</p><p>　　//操作結(jié)果：構(gòu)造一個(gè)空的

7、線性表 </p><p>　　CreatPolyn(&L) </p><p>　　//操作結(jié)果：構(gòu)造一個(gè)以單連表存儲(chǔ)的多項(xiàng)試 </p><p>　　DispPolyn(L) </p><p>　　//操作結(jié)果：顯示多項(xiàng)試 </p><p>　　Polyn(&pa,&pb) </p>

8、<p>　　//操作結(jié)果：顯示兩個(gè)多項(xiàng)試相加，相減的結(jié)果 </p><p>　　} ADT List </p><p>　　2． 本程序包含模塊： typedef struct LNode //定義單鏈表 </p><p><b>　　{</b></p><p>　　}LNode,*LinkList; <

9、;/p><p>　　void InitList(LinkList &L) //定義一個(gè)空表</p><p><b>　　{ } </b></p><p>　　void CreatPolyn(LinkList &L) //用單鏈表定義一個(gè)多項(xiàng)式</p><p><b>　　{ } </b>

10、</p><p>　　void DispPolyn(LinkList L) //顯示輸入的多項(xiàng)式</p><p><b>　　{ } </b></p><p>　　void Polyn(LinkList &pa,LinkList &pb) </p><p><b>　　{} </b>

11、</p><p>　　void main() </p><p><b>　　{ </b></p><p>　　//定義一個(gè)單連表； </p><p>　　cout<<endl<<" *****************歡迎來到一元多項(xiàng)式計(jì)算程序 </p><p>　

12、　*************** "<<endl; </p><p>　　LNode *L1,*L2;</p><p>　　Polyn(L1,L2); } </p><p>　　2.1 加，減操作模塊——實(shí)現(xiàn)加減操作</p><p>　　各模塊之間的調(diào)用關(guān)系如下：</p><p><b>

13、;　　主程序模塊 </b></p><p>　　加法操作模塊 減法操作模塊</p><p><b>　　基本算法：</b></p><p><b>　　1、輸入輸出</b></p><p>　　（1）功能：將要進(jìn)行運(yùn)算的多項(xiàng)式輸入輸出。</p><p>　?。?）

14、數(shù)據(jù)流入：要輸入的多項(xiàng)式的系數(shù)與指數(shù)。</p><p>　　（3）數(shù)據(jù)流出：合并同類項(xiàng)后的多項(xiàng)式。</p><p>　　（4）程序流程圖：多項(xiàng)式輸入流程圖如圖1所示。</p><p>　　（5）測(cè)試要點(diǎn)：輸入的多項(xiàng)式是否正確，若輸入錯(cuò)誤則重新輸入</p><p><b>　　2、多項(xiàng)式的加法</b></p>

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

16、<p><b>　　圖表 2</b></p><p><b>　　3、多項(xiàng)式的減法</b></p><p>　　（1）功能：將兩多項(xiàng)式相減。</p><p>　　（2）數(shù)據(jù)流入：調(diào)用輸入函數(shù)。</p><p>　?。?）數(shù)據(jù)流出：多項(xiàng)式相減后的結(jié)果。</p><p>

17、;　?。?）程序流程圖：多項(xiàng)式的減法流程圖如圖3所示。</p><p>　　（5）測(cè)試要點(diǎn)：兩多項(xiàng)式是否為空，為空則提示重新輸入，否則，進(jìn)行運(yùn)算。</p><p><b>　　四．詳細(xì)設(shè)計(jì)</b></p><p>　　1. 根據(jù)題目要求采用單連表存儲(chǔ)結(jié)構(gòu)</p><p>　　typedef struct LNode //

18、定義單鏈表</p><p><b>　　{</b></p><p>　　}LNode,*LinkList;</p><p>　　void InitList(LinkList &L) //定義一個(gè)空表</p><p><b>　　{ } </b></p><p>　　v

19、oid CreatPolyn(LinkList &L) //用單鏈表定義一個(gè)多項(xiàng)式</p><p><b>　　{ } </b></p><p>　　void DispPolyn(LinkList L) //顯示輸入的多項(xiàng)式 </p><p><b>　　{ }</b></p><p>　　

20、void Polyn(LinkList &pa,LinkList &pb) </p><p><b>　　{} </b></p><p>　　2．主函數(shù) main</p><p>　　void main() </p><p><b>　　{ </b></p><p

21、>　　LNode *L1,*L2; </p><p>　　Polyn(L1,L2);</p><p><b>　　} </b></p><p>　　2. 函數(shù)的調(diào)用關(guān)系層次結(jié)構(gòu)</p><p>　　多項(xiàng)式 Polyn 用單鏈表定義多項(xiàng)式 CreatPolyn 定義一個(gè)空表 InitList 顯示輸入的多項(xiàng)式 Dis

22、pPolyn</p><p><b>　　}</b></p><p><b>　　五. 調(diào)試分析</b></p><p>　　采用單連表形式按照指數(shù)降序排列建立并輸出多項(xiàng)式；在相加，相減的過程 中如果指數(shù)相同就執(zhí)行系數(shù)相加，相減，否則就把大的項(xiàng)直接寫入。完成兩個(gè)多 項(xiàng)式的相加、相減;將從新得到的單連表結(jié)果輸出；該算法的時(shí)間

23、復(fù)雜度為兩個(gè) 多項(xiàng)式的項(xiàng)式之和</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)

24、，其中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)

25、的排序函數(shù)，通過對(duì)鏈表排序后再進(jìn)行之后加減運(yùn)算。</p><p>　　七. 心得體會(huì)：一元多項(xiàng)式計(jì)算是一個(gè)的單鏈表的運(yùn)用， 通過這個(gè)程序可以測(cè)我們以前的學(xué)習(xí)情 況，看看我們是否對(duì)單鏈表真正的理解。</p><p>　　一元多項(xiàng)式計(jì)算器的基本功能定為：</p><p>　　(1) 建立多項(xiàng)式 </p><p><b>　　(2) 輸出

26、多項(xiàng)式</b></p><p>　　(3) 兩個(gè)多項(xiàng)式相加，建立并輸出和多項(xiàng)式 </p><p>　　(4) 兩 個(gè)多項(xiàng)式相減，建立并輸出差多項(xiàng)式能夠按照指數(shù)降序排列建立并輸出多項(xiàng)式；</p><p>　　能夠完成兩個(gè)多項(xiàng)式的相加、相減，并將結(jié)果輸出；</p><p><b>　　結(jié)束語：</b></p

27、><p>　　時(shí)間過的很快，在不知不覺中，課程設(shè)計(jì)也接近了尾聲.說起課程設(shè)計(jì)，我認(rèn)為最重要的就是做好設(shè)計(jì)的預(yù)習(xí)，并且認(rèn)真的去復(fù)習(xí)以前的知識(shí)和查各種資料同時(shí)認(rèn)真的研究老師給的題目，老師對(duì)題目的講解要一絲不茍的去聽去想，因?yàn)橹挥卸济靼琢?，做起設(shè)計(jì)來才會(huì)有底，有信心。課程設(shè)計(jì)是一門培養(yǎng)學(xué)生綜合運(yùn)用所學(xué)知識(shí),發(fā)現(xiàn),提出,分析和解決實(shí)際問題的學(xué)科,它能充分鍛煉我們的動(dòng)手能力，時(shí)我們實(shí)踐能力的重要環(huán)節(jié),是對(duì)學(xué)生實(shí)際工作能力的具體

28、訓(xùn)練和考 察過程。我想這次不只是一次簡(jiǎn)單的課程設(shè)計(jì)，更體現(xiàn)了數(shù)據(jù)結(jié)構(gòu)算法和生活的緊密聯(lián)系。生活中也存在許多與數(shù)據(jù)結(jié)構(gòu)有關(guān)聯(lián)的事情，它讓人不得不深思，這一個(gè)學(xué)期的學(xué)習(xí)，這兩年來的大學(xué)學(xué)習(xí)生涯，自己究竟學(xué)會(huì)了什么，掌握了多少，我也不清楚，我以前也瘋狂的玩過，現(xiàn)在才知道自己時(shí)多么的缺乏知識(shí)，大多數(shù)問題自己不能解決，感覺將來自己是否能勝任以后作編譯人員的職位。我想大家都心里都有很多的感觸。對(duì)于自己，我想我已經(jīng)認(rèn)識(shí)到了自己的不足，在今后的學(xué)習(xí)過程

29、中，我一定以最好的心態(tài)去對(duì)待，以最好的面貌來迎接大三的軟件專業(yè)課程，并且經(jīng)常上機(jī)調(diào)試，堅(jiān)持理論與實(shí)踐相結(jié)合。相信自己將會(huì)有很大的進(jìn)步。</p><p><b>　　附錄詳細(xì)設(shè)計(jì) </b></p><p>　　#include<stdio.h></p><p>　　#include<malloc.h></p>

30、<p>　　typedef struct Polynomial{</p><p>　　float coef;</p><p><b>　　int expn;</b></p><p>　　struct Polynomial *next;</p><p>　　}*Polyn,Polynomial;

31、 //Polyn為結(jié)點(diǎn)指針類型</p><p>　　void 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>　　Pol

32、yn q1,q2;</p><p>　　q1=h;q2=h->next;</p><p>　　while(q2&&p->expn<q2->expn){ //查找插入位置</p><p><b>　　q1=q2;</b></p><p>　　q2=q2->next;<

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

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

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

36、t;p><b>　　}</b></p><p><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&g

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

38、　p=(Polyn)malloc(sizeof(struct Polynomial));//建立新結(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>　

39、　Insert(p,head); //調(diào)用Insert函數(shù)插入結(jié)點(diǎn)</p><p><b>　　}</b></p><p>　　return head;</p><p>　　}//CreatePolyn</p><p>　　void DestroyPolyn(Polyn p){//銷毀多項(xiàng)式p</p>

40、<p>　　Polyn q1,q2;</p><p>　　q1=p->next;</p><p>　　q2=q1->next;</p><p>　　while(q1->next){</p><p><b>　　free(q1);</b></p><p>　　q1=q2;

41、//指針后移</p><p>　　q2=q2->next;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void PrintPolyn(Polyn P){ </p><p>　　Polyn q=P->next

42、; </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>　　return;<

43、;/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(q->coef!=1

44、&&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) printf("X^%d

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

46、;<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){</p>

47、<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><b>　　}&

48、lt;/b></p><p><b>　　}</b></p><p>　　q=q->next; </p><p><b>　　flag++;</b></p><p><b>　　}//while</b></p><p>　　printf(&q

49、uot;\n");</p><p>　　}//PrintPolyn</p><p>　　int compare(Polyn a,Polyn b){</p><p><b>　　if(a&&b){</b></p><p>　　if(!b||a->expn>b->expn) ret

50、urn 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 -1;//a多項(xiàng)式已

51、空，但b多項(xiàng)式非空</p><p>　　else return 1;//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;<

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

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

54、b></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;&l

55、t;/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

56、>　　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>&l

57、t;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&

58、gt;<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

59、><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<

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

61、 p=pb->next;</p><p><b>　　Polyn pd;</b></p><p>　　while(p){ //將pb的系數(shù)取反</p><p>　　p->coef*=-1;</p><p>　　p=p->next;</p><p><b&

62、gt;　　}</b></p><p>　　pd=AddPolyn(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>　　}

63、//SubtractPolyn</p><p>　　int main(){</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</

64、p><p>　　printf("請(qǐng)輸入a的項(xiàng)數(shù):");</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

65、>　　scanf("%d",&n);</p><p>　　pb=CreatePolyn(pb,n);//建立多項(xiàng)式a</p><p><b>　　//輸出菜單</b></p><p>　　printf("**********************************************\n&

66、quot;);</p><p>　　printf("操作提示：\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>

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

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

69、tf("多項(xiàng)式a+b：");PrintPolyn(pc);</p><p>　　DestroyPolyn(pc);continue;</p><p><b>　　}</b></p><p>　　if(flag==3){</p><p>　　pd=SubtractPolyn(pa,pb);</p&

70、gt;<p>　　printf("多項(xiàng)式a-b：");PrintPolyn(pd);</p><p>　　DestroyPolyn(pd);continue;</p><p><b>　　}</b></p><p>　　if(flag==4) break;</p><p>　　if(fl

71、ag<1||flag>4) printf("Error!!!\n");continue;</p><p><b>　　}//for</b></p><p>　　DestroyPolyn(pa);</p><p>　　DestroyPolyn(pb);</p><p><b>