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

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

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

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

4、第i項的系數(shù)和指數(shù)。序列按指數(shù)降序排列。（3） 多項式a和b相加，建立多項式a+b，輸出相加的多項式。（4） 多項式a和b相減，建立多項式a-b，輸出相減的多項式。用帶頭結(jié)點的單鏈表存儲多項式。測試數(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）建立多項式一元多項式是由多個項的和組成的，將一元多項式的每個項用一結(jié)點表示，該結(jié)點中應包括該項的系數(shù)、該項的指數(shù)、指向下一項的指針，可以用線性表來依次輸入各項結(jié)點

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

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

7、點的多項式的相加函數(shù)polylist polyadd(polylist a,polylist b)(4) 帶頭結(jié)點的多項式的相減函數(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é)點指針類型void insert(poly p,poly h) if(p-coef=0) free(p); /系數(shù)為0時釋

8、放結(jié)點 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é)點 q1-next=q2-next; free(q2); else /指數(shù)為新時將結(jié)點插入 p-next=q2; q1-next=p; /insertpoly createpoly(poly head,int m)/建立一個頭指針為head、項數(shù)為m的一元多項式 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é)點 return head;/createpolyvoid destroypoly(poly p)/銷毀多項式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;/項數(shù)計數(shù)器 if(!q) /若多項式為空，輸出0 putchar(0); printf(n); return; while (q) if(q-coef0&flag!=1) putchar(+); /系數(shù)大于0且不是第一項 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多項式已空，但b多項式非空 else return 1;/b多項式已空，但a多項式非空/comparepoly addpoly(poly pa,poly pb)/求解并建立多項式a+b，返回其頭指針 poly qa=pa-next; poly qb=pb-next; poly headc,hc,qc; hc=(poly)malloc(sizeof(struct polyomial);/建立頭結(jié)點 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、);/當相加系數(shù)為0時，釋放該結(jié)點 /while return headc;/addpolypoly subtractpoly(poly pa,poly pb) /求解并建立多項式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) /恢復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的項數(shù):); scanf(%d,&m); pa=createpoly(pa,m);/建立多項式a printf(輸入b的項數(shù):); scanf(%d,&n); pb=createpoly(pb,n);/建立多項式b for(;flag=0) printf(執(zhí)行操作); scanf(%d,&flag); if(flag=1) printf(多項式a：);printpoly(pa); printf(多項式b：);printpoly(pb);continue; if(fl

16、ag=2) pc=addpoly(pa,pb); printf(多項式a+b：);printpoly(pc); destroypoly(pc);continue; if(flag=3) pd=subtractpoly(pa,pb); printf(多項式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.算法分析建立多項式的時間復雜度為o(n),降

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

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