數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)一元稀疏多項(xiàng)式簡(jiǎn)單計(jì)數(shù)器

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計(jì)說(shuō)明書(shū)題目： 一元稀疏多項(xiàng)式簡(jiǎn)單計(jì)數(shù)器學(xué)生姓名： 學(xué) 號(hào)： 院 （系）： 理學(xué)院 專 業(yè)： 數(shù)學(xué)與應(yīng)用數(shù)學(xué) 指導(dǎo)教師： 張洲平 2011年 12月23日陜 西 科 技 大 學(xué) 數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計(jì)任務(wù)書(shū) 理 學(xué)院 數(shù)學(xué)與應(yīng)用數(shù)學(xué) 專業(yè) 班級(jí) 學(xué)生： 題目： 一元稀疏多項(xiàng)式簡(jiǎn)單計(jì)數(shù)器 課程設(shè)計(jì)從 2011 年 12 月 19 日起到 2011 年 12 月 23 日1、課程設(shè)計(jì)的內(nèi)容和要求（包括原始數(shù)據(jù)、技術(shù)要求、工作要求等）： 一元稀疏多項(xiàng)式簡(jiǎn)單計(jì)數(shù)器 （1） 輸入并建立多項(xiàng)式 （2） 輸出多項(xiàng)式，輸出形式為整數(shù)序列：n，c1，e1，c2，e2cn ，en，其

2、中n是多項(xiàng)式的項(xiàng)數(shù)，ci，ei分別為第i項(xiàng)的系數(shù)和指數(shù)。序 列按指數(shù)降序排列。 （3） 多項(xiàng)式a和b相加，建立多項(xiàng)式a+b，輸出相加的多項(xiàng)式。 （4） 多項(xiàng)式a和b相減，建立多項(xiàng)式a-b，輸出相減的多項(xiàng)式。 用帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)多項(xiàng)式。 2、對(duì)課程設(shè)計(jì)成果的要求包括圖表、實(shí)物等硬件要求：1）根據(jù)課程設(shè)計(jì)題目要求編寫(xiě)所需程序代碼 要求可以實(shí)現(xiàn)多項(xiàng)式的建立，以及兩個(gè)多項(xiàng)式的相加、減，并且輸出相加、減后所得的結(jié)果，同時(shí)用手算也可驗(yàn)證實(shí)驗(yàn)結(jié)果是否符合要求。 2）提交課程設(shè)計(jì)報(bào)告 按照具體要求完成課程設(shè)計(jì)報(bào)告，其中包括問(wèn)題的描述、算法思想、程序?qū)崿F(xiàn)結(jié)果、數(shù)據(jù)驗(yàn)證和實(shí)驗(yàn)總結(jié)等部分。 3、課程設(shè)計(jì)工作進(jìn)度

3、計(jì)劃：時(shí)間設(shè)計(jì)任務(wù)及要求1-10搜集學(xué)習(xí)相關(guān)資料，明確實(shí)驗(yàn)要求、目的1-11分析課題，理清編程思路1-12編寫(xiě)程序，修改程序1-13代入數(shù)據(jù)，進(jìn)行整體調(diào)試，運(yùn)行，再修改1-14性能分析，撰寫(xiě)設(shè)計(jì)說(shuō)明書(shū) 指導(dǎo)教師： 日期： 2011-11-15 教研室主任： 日期： 目 錄一、問(wèn)題描述1二、算法思想2三、數(shù)據(jù)結(jié)構(gòu)3四、設(shè)計(jì)模塊劃分4五、源程序5六、算法分析10七、運(yùn)行結(jié)果11八、設(shè)計(jì)總結(jié)與體會(huì)13參考文獻(xiàn) 141.問(wèn)題描述：一元稀疏多項(xiàng)式簡(jiǎn)單計(jì)數(shù)器基本要求：（1） 輸入并建立多項(xiàng)式（2） 輸出多項(xiàng)式，輸出形式為整數(shù)序列：n，c1，e1，c2，e2cn，en，其中n是多項(xiàng)式的項(xiàng)數(shù)，ci，ei分別為

4、第i項(xiàng)的系數(shù)和指數(shù)。序列按指數(shù)降序排列。（3） 多項(xiàng)式a和b相加，建立多項(xiàng)式a+b，輸出相加的多項(xiàng)式。（4） 多項(xiàng)式a和b相減，建立多項(xiàng)式a-b，輸出相減的多項(xiàng)式。用帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)多項(xiàng)式。測(cè)試數(shù)據(jù)：（1）(2x+5x8-3.1x11)+(7-5x8+11x9)（2）(6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2+7.8x15)（3）(x+x2+x3)+0（4）(x+x3)-(-x-x-3)2.算法思想：（1）建立多項(xiàng)式一元多項(xiàng)式是由多個(gè)項(xiàng)的和組成的，將一元多項(xiàng)式的每個(gè)項(xiàng)用一結(jié)點(diǎn)表示，該結(jié)點(diǎn)中應(yīng)包括該項(xiàng)的系數(shù)、該項(xiàng)的指數(shù)、指向下一項(xiàng)的指針，可以用線性表來(lái)依次輸入各項(xiàng)結(jié)點(diǎn)

5、，從而完成多項(xiàng)式鏈表的建立，為了使原多項(xiàng)式各項(xiàng)順序不變，故采用尾插法建表。（2）降冪輸出多項(xiàng)式我們可以先設(shè)一個(gè)冪指數(shù)i為可輸入的最大冪指數(shù)，然后從首元結(jié)點(diǎn)開(kāi)始順次查詢每一結(jié)點(diǎn)的指數(shù)和i，若相等則輸出該結(jié)點(diǎn)，否則，i-,繼續(xù)從首元結(jié)點(diǎn)開(kāi)始查詢，重復(fù)上述過(guò)程，直到i為可輸入的最小冪指數(shù)。這樣，就按指數(shù)降冪輸出了多項(xiàng)式。多項(xiàng)式的項(xiàng)數(shù)統(tǒng)計(jì)可以通過(guò)頭結(jié)點(diǎn)的next來(lái)實(shí)現(xiàn)，若非空，count+,直到結(jié)點(diǎn)的指針域?yàn)榭眨@樣，count就統(tǒng)計(jì)出了項(xiàng)數(shù)。（3） 多項(xiàng)式相加多項(xiàng)式的相加過(guò)程，其實(shí)就是相同指數(shù)的項(xiàng)的系數(shù)相加，不同指數(shù)的項(xiàng)復(fù)制到和多項(xiàng)式中，將結(jié)果用降冪輸出函數(shù)輸出。（4） 多項(xiàng)式相減多項(xiàng)式的相減過(guò)程，

6、其實(shí)就是相同指數(shù)的項(xiàng)的系數(shù)相減，對(duì)于不同指數(shù)的項(xiàng)，若是被減多項(xiàng)式，則將該結(jié)點(diǎn)復(fù)制輸出，若是減多項(xiàng)式，則將該結(jié)點(diǎn)的系數(shù)變?yōu)樵禂?shù)的相反數(shù)輸出，將結(jié)果用降冪輸出函數(shù)輸出。3.數(shù)據(jù)結(jié)構(gòu)：帶頭結(jié)點(diǎn)單鏈表抽象數(shù)據(jù)類型的結(jié)點(diǎn)結(jié)構(gòu)定義如下：typedef struct polynode /多項(xiàng)式結(jié)點(diǎn)int coef; /系數(shù)int exp; /指數(shù)polynode *next;polynode ,*polylist;4.模塊劃分：(1) 帶頭結(jié)點(diǎn)的多項(xiàng)式的建立函數(shù)polylist polycreate()(2) 帶頭結(jié)點(diǎn)的多項(xiàng)式的降冪輸出函數(shù)void printf(polylist poly)(3) 帶頭結(jié)

7、點(diǎn)的多項(xiàng)式的相加函數(shù)polylist polyadd(polylist a,polylist b)(4) 帶頭結(jié)點(diǎn)的多項(xiàng)式的相減函數(shù)polylist polysub(polylist a,polylist b)(5) 主函數(shù)void main()5.源程序：#include#includetypedef struct polyomial float coef; int expn; struct polyomial *next;*poly,polyomial; /poly為結(jié)點(diǎn)指針類型void insert(poly p,poly h) if(p-coef=0) free(p); /系數(shù)為0時(shí)釋

8、放結(jié)點(diǎn) else poly q1,q2; q1=h;q2=h-next; while(q2&p-expnexpn) /查找插入位置 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; /insertpoly createpoly(poly head,int m)/建立一個(gè)頭指針為head、項(xiàng)數(shù)為m的一元多項(xiàng)式 in

9、t i; poly p; p=head=(poly)malloc(sizeof(struct polyomial); head-next=null; for(i=0;icoef,&p-expn); insert(p,head); /調(diào)用insert函數(shù)插入結(jié)點(diǎn) return head;/createpolyvoid destroypoly(poly p)/銷毀多項(xiàng)式p poly q1,q2; q1=p-next; q2=q1-next; while(q1-next) free(q1); q1=q2;/指針后移 q2=q2-next; void printpoly(poly p) poly q=

10、p-next; int flag=1;/項(xiàng)數(shù)計(jì)數(shù)器 if(!q) /若多項(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

11、-expn=1) putchar(x); else printf(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);/printpolyint compare(poly a,poly b) if(a&b) if(!b|a-expnb-expn) return 1; else if(!a|a-expnexpn) return -1; else return 0; el

12、se if(!a&b) return -1;/a多項(xiàng)式已空，但b多項(xiàng)式非空 else return 1;/b多項(xiàng)式已空，但a多項(xiàng)式非空/comparepoly addpoly(poly pa,poly pb)/求解并建立多項(xiàng)式a+b，返回其頭指針 poly qa=pa-next; poly qb=pb-next; poly headc,hc,qc; hc=(poly)malloc(sizeof(struct polyomial);/建立頭結(jié)點(diǎn) hc-next=null; headc=hc; while(qa|qb) qc=(poly)malloc(sizeof(struct polyomial

13、); switch(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

14、);/當(dāng)相加系數(shù)為0時(shí)，釋放該結(jié)點(diǎn) /while return headc;/addpolypoly subtractpoly(poly pa,poly pb) /求解并建立多項(xiàng)式a+b，返回其頭指針 poly h=pb; poly p=pb-next; poly pd; while(p) /將pb的系數(shù)取反 p-coef*=-1; p=p-next; pd=addpoly(pa,h); for(p=h-next;p;p=p-next) /恢復(fù)pb的系數(shù) p-coef*=-1; return pd;/subtractpolyint main() int m,n,flag=0; float x;

15、 poly pa=0,pb=0,pc,pd,pe,pf;/定義各式的頭指針，pa與pb在使用前付初值null printf(輸入a的項(xiàng)數(shù):); scanf(%d,&m); pa=createpoly(pa,m);/建立多項(xiàng)式a printf(輸入b的項(xiàng)數(shù):); scanf(%d,&n); pb=createpoly(pb,n);/建立多項(xiàng)式b for(;flag=0) printf(執(zhí)行操作); scanf(%d,&flag); if(flag=1) printf(多項(xiàng)式a：);printpoly(pa); printf(多項(xiàng)式b：);printpoly(pb);continue; if(fl

16、ag=2) pc=addpoly(pa,pb); printf(多項(xiàng)式a+b：);printpoly(pc); destroypoly(pc);continue; if(flag=3) pd=subtractpoly(pa,pb); printf(多項(xiàng)式a-b：);printpoly(pd); destroypoly(pd);continue; if(flag=4) break; if(flag4) printf(error!n);continue; /for destroypoly(pa); destroypoly(pb); return 0;6.算法分析建立多項(xiàng)式的時(shí)間復(fù)雜度為o(n),降

17、冪輸出多項(xiàng)式序列算法，由于是對(duì)指數(shù)做的循環(huán)，每次循環(huán)都需要從首元結(jié)點(diǎn)查找到表尾，假設(shè)多項(xiàng)式開(kāi)始為升冪排列，如x1+x2+x3+x4+xn,（這里n=20）其時(shí)間復(fù)雜度為n(n+1)/2,若指數(shù)不是連續(xù)的，則其時(shí)間復(fù)雜度加上o(n),所以此算法的時(shí)間復(fù)雜度為o（n2）。假設(shè)a有m項(xiàng)，b有n項(xiàng)，則加法和減法算法的時(shí)間復(fù)雜度度為m+n，算法中兩多項(xiàng)式相加和相減時(shí)，a,b均需按升冪順序輸入結(jié)點(diǎn)。7.運(yùn)行結(jié)果：（1）(2x+5x8-3.1x11)+(7-5x8+11x9)程序運(yùn)行結(jié)果為：（2）(6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2+7.8x15)程序運(yùn)行結(jié)果為：（3）(x+x

18、2+x3)+0程序運(yùn)行結(jié)果為：(4) (x+x3)-(-x-x-3)程序運(yùn)行結(jié)果為：8.設(shè)計(jì)體會(huì)與總結(jié)本次程序設(shè)計(jì)的總體思路明確，易懂，能夠清楚的分辨出各模塊的功能，利于用戶的閱讀、了解程序，該程序的執(zhí)行過(guò)程是相當(dāng)?shù)囊子谧x者使用，它會(huì)在每一步都提示用戶接下來(lái)的輸入數(shù)據(jù)。當(dāng)然，本次課程設(shè)計(jì)還有許多的不足之處，在以后的不斷學(xué)習(xí)當(dāng)中我還會(huì)繼續(xù)完善這個(gè)程序。在課程設(shè)計(jì)的過(guò)程中，深深地體會(huì)到了有算法思想和將此算法寫(xiě)成可執(zhí)行程序，還是有一段距離的，程序出現(xiàn)錯(cuò)誤并不可怕，只要我們肯耐心的去調(diào)試，去改進(jìn)，最后一定會(huì)設(shè)計(jì)出一個(gè)比較好的程序。拿到課題后，我們首先要對(duì)要實(shí)現(xiàn)的功能以及數(shù)據(jù)結(jié)構(gòu)有一個(gè)初步的規(guī)劃，這樣后邊的工作才會(huì)順利進(jìn)行。若是在編寫(xiě)或執(zhí)行程序的過(guò)程中遇到了確實(shí)解決不了的問(wèn)題，需要多和同學(xué)交流。通過(guò)做本次課程設(shè)計(jì)，使我收獲了很多東西，知識(shí)這方面說(shuō)起，以前覺(jué)得不管什么樣的題還是編程，只要了解算法的思想就行了，到時(shí)候用的時(shí)候自然就會(huì)發(fā)揮出來(lái)，可這次的課程設(shè)計(jì)卻告訴我并不是這樣的，我在此次課程設(shè)計(jì)的編程的時(shí)候就遇到了這樣的問(wèn)題。覺(jué)得自己了解算法思想就一定能編出來(lái)，可是事實(shí)卻不得不又拿起書(shū)來(lái)繼續(xù)研究，繼續(xù)查找一些相