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

1、數(shù) 據(jù) 結(jié) 構(gòu) 課 程 設(shè) 計(jì) 報(bào) 告 一元多項(xiàng)式加法器專業(yè): 班 級: 學(xué) 號: 姓 名: 指導(dǎo)老師: 目錄1.序言31.1關(guān)于數(shù)據(jù)結(jié)構(gòu)31.2數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)的目的32 需求分析42.1題目要求42.2題目分析43 概要設(shè)計(jì)53.1總體解決方案53.2總體功能流程圖64 詳細(xì)設(shè)計(jì)與實(shí)現(xiàn)64.1系統(tǒng)主要函數(shù)組成64.2基本函數(shù)實(shí)現(xiàn)流程75 代碼與解析126 調(diào)試與操作說明186.1操作說明186.2調(diào)試結(jié)果19總 結(jié)20參 考 文 獻(xiàn)201.序 言1.1關(guān)于數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是一門理論性強(qiáng)、思維抽象、難度較大的課程，是基礎(chǔ)課和專業(yè)課之間的橋梁。該課程的先行課程是計(jì)算機(jī)基礎(chǔ)、程序設(shè)計(jì)語言、離散數(shù)

2、學(xué)等，后續(xù)課程有操作系統(tǒng)、編譯原理、數(shù)據(jù)庫原理、軟件工程等。 通過本門課程的學(xué)習(xí)，我們應(yīng)該能透徹地理解各種數(shù)據(jù)對象的特點(diǎn)，學(xué)會數(shù)據(jù)的組織方法和實(shí)現(xiàn)方法，并進(jìn)一步培養(yǎng)良好的程序設(shè)計(jì)能力和解決實(shí)際問題的能力，而且該課程的研究方法對我們學(xué)生在校和離校后的學(xué)習(xí)和工作，也有著重要的意義。數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的一門核心專業(yè)基礎(chǔ)課程，在該專業(yè)的課程體系中起著承上啟下的作用，學(xué)好數(shù)據(jù)結(jié)構(gòu)對于提高理論認(rèn)知水平和實(shí)踐能力有著極為重要的作用。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的最終目的是為了獲得求解問題的能力。對于現(xiàn)實(shí)世界中的問題，應(yīng)該能從中抽象出一個適當(dāng)?shù)臄?shù)學(xué)模型，該數(shù)學(xué)模型在計(jì)算機(jī)內(nèi)部用相應(yīng)的數(shù)據(jù)結(jié)構(gòu)來表示，然后設(shè)計(jì)一個解

3、此數(shù)學(xué)模型的算法，再進(jìn)行編程調(diào)試，最后獲得問題的解答?；诖嗽?，我們開設(shè)了數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)。針對數(shù)據(jù)結(jié)構(gòu)課程的特點(diǎn)，著眼于培養(yǎng)我們的實(shí)踐能力。實(shí)習(xí)課程是為了加強(qiáng)編程能力的培養(yǎng)，鼓勵學(xué)生使用新興的編程語言。相信通過數(shù)據(jù)結(jié)構(gòu)課程實(shí)踐，無論是理論知識，還是實(shí)踐動手能力，同學(xué)們都會有不同程度上的提高。1.2數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)的目的通過課程設(shè)計(jì)題目的練習(xí)，強(qiáng)化學(xué)生對所學(xué)知識的掌握及對問題分析和任務(wù)定義的理解，對每到題目作出了相應(yīng)的邏輯分析和數(shù)據(jù)結(jié)構(gòu)的選擇，通過對任務(wù)的分析，為操作對象定義相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，以過程化程序設(shè)計(jì)的思想方法為原則劃分各個模塊，定義數(shù)據(jù)的抽象數(shù)據(jù)類型。分模塊對題目進(jìn)行設(shè)計(jì)，強(qiáng)化學(xué)生對

4、c語言的掌握和對數(shù)據(jù)結(jié)構(gòu)的選擇及掌握。通過程序的編譯掌握對程序的調(diào)試方法及思想，并且讓學(xué)生學(xué)會使用一些編程技巧。促使學(xué)生養(yǎng)成良好的編程習(xí)慣， 以及讓學(xué)生對書本上的知識進(jìn)行了實(shí)踐。算法與數(shù)據(jù)結(jié)構(gòu)這門課是計(jì)算機(jī)科學(xué)中一門綜合性的專業(yè)基礎(chǔ)課。它不僅是計(jì)算機(jī)學(xué)科的核心課程，而且已成為其它理工專業(yè)的熱門選修課。它又是操作系統(tǒng)、編譯原理、數(shù)據(jù)庫原理、算法分析、人工智能、圖象處理等專業(yè)課程的前導(dǎo)課。具有承上啟下的作用。數(shù)據(jù)結(jié)構(gòu)的研究不僅涉及到計(jì)算機(jī)硬件的研究范圍，而且和計(jì)算機(jī)軟件的研究有著密切的關(guān)系。計(jì)算機(jī)科學(xué)各領(lǐng)域及有關(guān)的應(yīng)用軟件都要用到數(shù)據(jù)結(jié)構(gòu)。該課程的目的就是介紹一些最常用的數(shù)據(jù)結(jié)構(gòu)，闡明數(shù)據(jù)結(jié)構(gòu)內(nèi)在

5、的邏輯關(guān)系，討論它們在計(jì)算機(jī)中的存儲表示，并結(jié)合各種典型應(yīng)用說明它們在進(jìn)行各種運(yùn)算時的動態(tài)性質(zhì)及實(shí)際的執(zhí)行算法。2. 需求分析2.1題目要求一元多項(xiàng)式加法器【問題描述】 設(shè)計(jì)一個一元多項(xiàng)式加法器?！净疽蟆?1) 輸入并建立多項(xiàng)式；(2)兩個多項(xiàng)式相加；(3)輸出多項(xiàng)式：n, c1, e1, c2, e2, cn , en, 其中，n是多項(xiàng)式項(xiàng)數(shù)，ci和ei分別是第 i 項(xiàng)的系數(shù)和指數(shù)，序列按指數(shù)降序排列。(4)計(jì)算多項(xiàng)式在x處的值；(5)求多項(xiàng)式的導(dǎo)函數(shù)。2.2題目分析在數(shù)學(xué)上，一個一元多項(xiàng)式pn(x)可按降冪寫成：pn(x)=a0+a1 x+a2 x2 +an xn-1 .它由n+1個系

6、數(shù)惟一確定，因此，在計(jì)算機(jī)里，它可用一個線性表p來表示：pn=(a0,a1,a2,an)每一項(xiàng)的指數(shù)i隱含在其系數(shù)ai的序號里。題中只要求我們求兩個多項(xiàng)式的加法，求值，求導(dǎo)和輸入輸出功能，只要掌握其規(guī)律，運(yùn)用單鏈表的基本操作就能有效解決。3.概要設(shè)計(jì)3.1總體解決方案1、任務(wù)思路與方法1) 定義線性表的動態(tài)分配順序存儲結(jié)構(gòu);2) 建立多項(xiàng)式存儲結(jié)構(gòu)，定義指針*next利用鏈表實(shí)現(xiàn)隊(duì)列的構(gòu)造;3) 每次輸入一項(xiàng)的系數(shù)和指數(shù)，可以輸出構(gòu)造的一元多項(xiàng)式;4) 要解決多項(xiàng)式相加，必須要有多項(xiàng)式，所以必須首先建立兩個多項(xiàng)式，在這里采用鏈表的方式存儲鏈表，所以我將結(jié)點(diǎn)結(jié)構(gòu)體定義為系數(shù)coef指數(shù)expn指

7、針域next運(yùn)用尾插法建立兩條單鏈表，以單鏈表polyn p和polyn h分別表示兩個一元多項(xiàng)式a和b，a+b的求和運(yùn)算等同于單鏈表的插入問題（將單鏈表polyn p中的結(jié)點(diǎn)插入到單鏈表polyn h中），因此“和多項(xiàng)式”中的結(jié)點(diǎn)無須另生成。2.相關(guān)算法： 1）元素類型、結(jié)點(diǎn)類型和指針類型：typedef struct polynomial float coef; /系數(shù) int expn; /指數(shù) struct polynomial *next;*polyn,polynomial;2）建立一個頭指針為head、項(xiàng)數(shù)為m的一元多項(xiàng)式, 建立新結(jié)點(diǎn)以接收數(shù)據(jù), 調(diào)用insert函數(shù)插入結(jié)點(diǎn):

8、polyn createpolyn(polyn head,int m) int i; polyn p; p=head=(polyn)malloc(sizeof(struct polynomial); head-next=null; for(i=0;icoef,&p-expn); insert(p,head); return head;3.2總體功能流程圖求一元多項(xiàng)式的加法（a+b）求一元多項(xiàng)式的導(dǎo)函數(shù) 開 始輸入多項(xiàng)式根據(jù)輸入創(chuàng)建一元多項(xiàng)式并開始存儲輸出一元多項(xiàng)式并輸入x的值，求一元多項(xiàng)式的值 結(jié) 束4. 詳細(xì)設(shè)計(jì)與實(shí)現(xiàn)4.1系統(tǒng)的主要函數(shù)組成1.main()函數(shù)main函數(shù)用來實(shí)現(xiàn)提示使用者

9、輸入、顯示功能列表、調(diào)用其他運(yùn)算函數(shù)實(shí)現(xiàn)運(yùn)算功能。在main()函數(shù)中，定義m、n用來保存兩個多項(xiàng)式的項(xiàng)數(shù)，pa、pb、pc、pd、pf定義程序所需鏈表的頭指針。在程序開始要求輸入兩個多項(xiàng)式的項(xiàng)數(shù)，隨后根據(jù)項(xiàng)數(shù)創(chuàng)建兩個鏈表以保存多項(xiàng)式，再顯示出功能列表后通過if語句來實(shí)現(xiàn)功能的選擇，從而對整個程序流程進(jìn)行控制。2. polyn createpolyn(polyn head,int m)該函數(shù)功能是創(chuàng)建新的多項(xiàng)式鏈表。int m保存的多項(xiàng)式的項(xiàng)數(shù)，使用for語句，控制輸入多項(xiàng)式的每一項(xiàng)。當(dāng)創(chuàng)建的鏈表長度為m時，將不再提示用戶繼續(xù)輸入多項(xiàng)式的系數(shù)和指數(shù)。在該函數(shù)中要用到分配空間的函數(shù)malloc(

10、)為新建鏈表分配空間。3. void destroypolyn(polyn p)該函數(shù)的功能是銷毀掉創(chuàng)建的兩個鏈表，釋放內(nèi)存。以輔助退出程序。4. void insert(polyn p,polyn h)該函數(shù)功能：將新的節(jié)點(diǎn)p插入到現(xiàn)有鏈表的后面，并確保多項(xiàng)式的指數(shù)exp是升序。將s節(jié)點(diǎn)插入到head所指向的鏈表。在該函數(shù)的操作中，要注意指針是如何移動的。5. polyn addpolyn(polyn pa,polyn pb)該函數(shù)功能：實(shí)現(xiàn)兩個多項(xiàng)式pa、pb相加，并將計(jì)算結(jié)果存儲于新建立的pc中，它的原理是將指數(shù)相同的單項(xiàng)式相加，系數(shù)相加后為0，則pa、pb的指針都后移。在加法計(jì)算中要求

11、pa,與pb的冪次序都是升序，否則可能得到錯誤的結(jié)果。該函數(shù)調(diào)用了int compare(polyn a,polyn b)的結(jié)果，用來判斷多項(xiàng)式在同一指數(shù)下a、b是否有為系數(shù)為0。同樣也使用了malloc()關(guān)鍵字，為新鏈表創(chuàng)建空間。6. int compare(polyn a,polyn b)該函數(shù)功能：判斷兩個多項(xiàng)式在同一指數(shù)下是否有其中一個為系數(shù)為0。用來輔助加法和乘法運(yùn)算。7. void printpolyn(polyn p)該函數(shù)功能：顯示多項(xiàng)式鏈表。在該函數(shù)中較復(fù)雜的是如何控制鏈表的輸出，尤其是第一項(xiàng)的輸出，同時還有符號的控制。在輸出第一項(xiàng)時要判斷是不是常數(shù)項(xiàng)，若是，則不要輸出字符

12、x。8. float valuepolyn(polyn pa,float x)該函數(shù)功能：求多項(xiàng)式在x處的值，對于指數(shù)小于0和大于0的多項(xiàng)式采用不同的算法，最后再把多項(xiàng)式的和輸出。9. polyn derivation(polyn head)該函數(shù)功能：對多項(xiàng)式求導(dǎo)，對指數(shù)和系數(shù)分別采用不同的算法，再把結(jié)點(diǎn)重新插入一個新的鏈表。4.2基本函數(shù)實(shí)現(xiàn)流程1.輸出多項(xiàng)式 假設(shè)指針p指向多項(xiàng)式的第一項(xiàng)1 p所指指數(shù)為0，則直接輸出系數(shù)2 p所指指數(shù)為1，如果系數(shù)即不為1，也不為0，則直接輸出系數(shù)；如果系數(shù)為-1，則輸出系數(shù)“-”，最后輸出“x”3 p所指指數(shù)即不為0，也不為1，如果系數(shù)為-1，則輸出“

13、-x”和指數(shù)，如果系數(shù)為1，則輸出“x”和指數(shù)，否則輸出系數(shù)、“x”及指數(shù) 流程圖如下圖：開始! nullp-expn若系數(shù)即不為1,也不為0,則直接輸出系數(shù);若系數(shù)為-1,則輸出系數(shù)“-”,最后輸出“x”01default直接輸出系數(shù)若系數(shù)為-1,則輸出“-x”和指數(shù),若系數(shù)為1則輸出“x”和指數(shù),否則輸出系數(shù)、“x”及指數(shù)輸出“+”1p系數(shù)0?p-expn01default直接輸出系數(shù)若系數(shù)為-1,則輸出“-x”和指數(shù),若系數(shù)為1則輸出“x”和指數(shù),否則輸出系數(shù)、“x”及指數(shù)若系數(shù)即不為1,也不為0,則直接輸出系數(shù);若系數(shù)為-1,則輸出系數(shù)“-”,最后輸出“x”! null0null返回o

14、ut結(jié)束p=p-next2.多項(xiàng)式相加根據(jù)一元多項(xiàng)式相加的運(yùn)算規(guī)則：對于兩個一元多項(xiàng)式中指數(shù)相同的項(xiàng)，對應(yīng)的系數(shù)相加，若之和不為零，則構(gòu)成“和多項(xiàng)式”中的一項(xiàng)；對于兩個一元多項(xiàng)式中指數(shù)不相同的項(xiàng)，則將指數(shù)小的添加到“和的多項(xiàng)式”中去，最后將還沒結(jié)束的多項(xiàng)式插入到和的多項(xiàng)式中去。開始流程圖如下圖：a=pa-nextb=pb-nextc=pc-nexta&b指數(shù)相同的項(xiàng)，對應(yīng)的系數(shù)相加，若之和不為零，則構(gòu)成“和多項(xiàng)式”中的一項(xiàng)指數(shù)不相同的項(xiàng)，則將指數(shù)小的添加到“和的多項(xiàng)式”中將還沒結(jié)束的多項(xiàng)式插入到和的多項(xiàng)式中結(jié)束3.多項(xiàng)式求值1 假設(shè)指針p指向多項(xiàng)式的第一項(xiàng)，sum2代表整個多項(xiàng)式的值（開始賦值

15、為0），sum1代表一項(xiàng)的值（開始賦值為1）2 每一項(xiàng)求法：指數(shù)為n，則x連乘n次，得到sum1,然后再用sum1乘系數(shù)最后將每一項(xiàng)加到sum2中。流程圖如下圖：p=pa-next開始sum1=每一項(xiàng)的值sum2+=sum1p=p-next返回sum2結(jié)束null! nullsum1=1p4.多項(xiàng)式求導(dǎo)1 假設(shè)p指向多項(xiàng)式a2 如果該多項(xiàng)式為常數(shù)，則p指向下一項(xiàng)3 否則系數(shù)=系數(shù)*指數(shù)，指數(shù)=指數(shù)-14 將產(chǎn)生的新的項(xiàng)插入到新的多項(xiàng)式b中，p指向下一項(xiàng)流程圖如下圖：開始term *p,*q,*xp=head-nextplp=p-next結(jié)束null! null0系數(shù)=系數(shù)*指數(shù),指數(shù)=指數(shù)-1

16、將產(chǎn)生的新的項(xiàng)插入到新的多項(xiàng)式b中,p指向下一項(xiàng)1p-expn=o5. 代碼與解析#include#includetypedef struct polynomial float coef; int expn; struct polynomial *next;*polyn,polynomial; /polyn為結(jié)點(diǎn)指針類型/*插入多項(xiàng)式中的因子*/void insert(polyn p,polyn h) if(p-coef=0) free(p); /系數(shù)為0的話釋放結(jié)點(diǎn) else polyn q1,q2; q1=h;q2=h-next; while(q2&p-expnexpn) /查找插入位置

17、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ù)為新時將結(jié)點(diǎn)插入 p-next=q2; q1-next=p; /insert/*建立多項(xiàng)式*/polyn createpolyn(polyn head,int m)/建立一個頭指針為head、項(xiàng)數(shù)為m的一元多項(xiàng)式 int i; polyn p; p=head=(polyn)malloc(sizeof(struct polyn

18、omial); head-next=null; for(i=0;icoef,&p-expn); insert(p,head); /調(diào)用insert函數(shù)插入結(jié)點(diǎn) return head;/createpolyn/*刪除多項(xiàng)式*/void destroypolyn(polyn p) polyn q1,q2; q1=p-next; q2=q1-next; while(q1-next) free(q1); q1=q2;/指針后移 q2=q2-next; /*輸出多項(xiàng)式*/void printpolyn(polyn p) polyn q=p-next; int flag=1;/項(xiàng)數(shù)計(jì)數(shù)器 if(!q)

19、/若多項(xiàng)式為空，輸出0 putchar(0); printf(n); return; while (q) if(q-coef0&flag!=1) 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); else if(q-expn) printf(x%d,q-expn); else if(q-coef=1) if(!q-expn) putchar(1); else if(q-expn=1) putchar(x); else printf(

20、x%d,q-expn); if(q-coef=-1) if(!q-expn) printf(-1); else if(q-expn=1) printf(-x); else printf(-x%d,q-expn); q=q-next; flag+; /while printf(n);/printpolynint compare(polyn a,polyn b) if(a&b) if(!b|a-expnb-expn) return 1; else if(!a|a-expnexpn) return -1; else return 0; else if(!a&b) return -1;/a多項(xiàng)式已空，

21、但b多項(xiàng)式非空 else return 1;/b多項(xiàng)式已空，但a多項(xiàng)式非空/compare/*多項(xiàng)式加法函數(shù)*/polyn addpolyn(polyn pa,polyn pb)/求解并建立多項(xiàng)式a+b，返回其頭指針 polyn qa=pa-next; polyn qb=pb-next; polyn headc,hc,qc; hc=(polyn)malloc(sizeof(struct polynomial);/建立頭結(jié)點(diǎn) hc-next=null; headc=hc; while(qa|qb) qc=(polyn)malloc(sizeof(struct polynomial); switc

22、h(compare(qa,qb) case 1: qc-coef=qa-coef; qc-expn=qa-expn; qa=qa-next; break; case 0: qc-coef=qa-coef+qb-coef; qc-expn=qa-expn; qa=qa-next; qb=qb-next; break; case -1: qc-coef=qb-coef; qc-expn=qb-expn; qb=qb-next; break; /switch if(qc-coef!=0) qc-next=hc-next; hc-next=qc; hc=qc; else free(qc);/當(dāng)相加系數(shù)

23、為0時，釋放該結(jié)點(diǎn) /while return headc;/addpolyn/*求多項(xiàng)式在x處的值*/float valuepolyn(polyn pa,float x)/求多項(xiàng)式a在x處的值polyn p;int i;float t;float sum=0; for(p=pa-next;p;p=p-next) t=1; for(i=p-expn;i!=0;) if(icoef*t; return sum; /*多項(xiàng)式求導(dǎo)函數(shù)*/polyn derivation(polyn head) /求解并建立導(dǎo)函數(shù)多項(xiàng)式，并返回其頭指針 polyn q=head-next,p1,p2,hd; hd=p

24、1=(polyn)malloc(sizeof(struct polynomial);/建立頭結(jié)點(diǎn) hd-next=null; while(q) if(q-expn!=0) /該項(xiàng)不是常數(shù)項(xiàng)時 p2=(polyn)malloc(sizeof(struct polynomial); p2-coef=q-coef*q-expn; p2-expn=q-expn-1; p2-next=p1-next; /連接結(jié)點(diǎn) p1-next=p2; p1=p2; q=q-next; return hd;/*主函數(shù)*/int main() int m,n,flag=0; float x,y; polyn pa=0,p

25、b=0,pc,pd;/定義各式的頭指針，pa與pb在使用前付初值null /輸出菜單 printf(歡迎使用一元多項(xiàng)式加法器n); printf(*n); printf(操作提示：nt1.輸入多項(xiàng)式a和bnt2.輸出多項(xiàng)式a和bnt3.輸出多項(xiàng)式a+bnt4.輸出多項(xiàng)式a在x處的值nt5.輸出多項(xiàng)式a的導(dǎo)函數(shù)n); printf(t6.退出n*n); for(;flag=0) printf(執(zhí)行操作(輸入16)：); scanf(%d,&flag); if(flag=1) printf(請輸入a的項(xiàng)數(shù):); scanf(%d,&m); pa=createpolyn(pa,m);/建立多項(xiàng)式a

26、printf(請輸入b的項(xiàng)數(shù):); scanf(%d,&n); pb=createpolyn(pb,n);/建立多項(xiàng)式b if(flag=2) printf(多項(xiàng)式a：);printpolyn(pa); printf(多項(xiàng)式b：);printpolyn(pb);continue; if(flag=3) pc=addpolyn(pa,pb); printf(輸出多項(xiàng)式a+b：);printpolyn(pc); destroypolyn(pc);continue; if(flag=4) printf(請輸入x的值： ); scanf(%f,&x); printf(所求多項(xiàng)式值為：%.3fn,valuepolyn(pa,x); continue; if(flag=5) pd=derivation(pa); printf(多項(xiàng)式a的導(dǎo)函數(shù)為：); printpolyn(pd); destroypolyn(pd); continue; if(flag=6) break; if(flag6) printf(error!n);continue; /for destroypolyn(pa); destroypolyn(pb); return 0;6 調(diào)試與操作說明6.1操作