一元稀疏多項式簡單計數(shù)器論文完整版

1、學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計論文一元稀疏多項式簡單計數(shù)器學(xué)生姓名： 學(xué)生學(xué)號： 院（系）： 計算機 年級專業(yè)： 指導(dǎo)教師： 二一年十二月學(xué)院本科學(xué)生課程設(shè)計任務(wù)書題目設(shè)計一元稀疏多項式簡單計數(shù)器1、課程設(shè)計的目的培養(yǎng)學(xué)生用學(xué)到的書本知識解決實際問題的能力；培養(yǎng)實際工作所需要的動手能力；培養(yǎng)學(xué)生以科學(xué)理論和工程上能力的技術(shù)，規(guī)范地開發(fā)大型、復(fù)雜、高質(zhì)量的應(yīng)用軟件和系統(tǒng)軟件具有關(guān)鍵性作用；通過課程設(shè)計的實踐，學(xué)生可以在程序設(shè)計方法、上機操作等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)和嚴(yán)格的訓(xùn)練。2、課程設(shè)計的內(nèi)容和要求（包括原始數(shù)據(jù)、技術(shù)要求、工作要求等）基本功能要求：（1） 輸入并建立多項式（2） 輸出多項式

2、，輸出形式為整數(shù)序列：n，c1，e1，c2，e2cn，en，其中n是多項式的項數(shù)，ci，ei分別為第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)3、主要參考文獻1數(shù)據(jù)結(jié)構(gòu)（C語言版），嚴(yán)蔚敏，清華大學(xué)出版社，20032數(shù)據(jù)

3、結(jié)構(gòu)題集，嚴(yán)蔚敏，清華大學(xué)出版社，20053數(shù)據(jù)結(jié)構(gòu)（C語言版），劉大有，高等教育出版社，20044Data Structure with C+，William FordWilliam Topp，清華大學(xué)出版社，20034、課程設(shè)計工作進度計劃第1天 完成方案設(shè)計與程序框圖 第2、3天 編寫程序代碼第4天 程序調(diào)試分析和結(jié)果第5天 課程設(shè)計報告和總結(jié)指導(dǎo)教師（簽字）日期年 月 日教研室意見：年 月 日學(xué)生（簽字）： 接受任務(wù)時間： 年 月 日注：任務(wù)書由指導(dǎo)教師填寫。課程設(shè)計（論文）指導(dǎo)教師成績評定表題目名稱設(shè)計一元稀疏多項式簡單計數(shù)器評分項目分值得分評價內(nèi)涵工作表現(xiàn)20%01學(xué)習(xí)態(tài)度6遵守各

4、項紀(jì)律，工作刻苦努力，具有良好的科學(xué)工作態(tài)度。02科學(xué)實踐、調(diào)研7通過實驗、試驗、查閱文獻、深入生產(chǎn)實踐等渠道獲取與課程設(shè)計有關(guān)的材料。03課題工作量7按期圓滿完成規(guī)定的任務(wù)，工作量飽滿。能力水平35%04綜合運用知識的能力10能運用所學(xué)知識和技能去發(fā)現(xiàn)與解決實際問題，能正確處理實驗數(shù)據(jù)，能對課題進行理論分析，得出有價值的結(jié)論。05應(yīng)用文獻的能力5能獨立查閱相關(guān)文獻和從事其他調(diào)研；能提出并較好地論述課題的實施方案；有收集、加工各種信息及獲取新知識的能力。06設(shè)計（實驗）能力，方案的設(shè)計能力5能正確設(shè)計實驗方案，獨立進行裝置安裝、調(diào)試、操作等實驗工作，數(shù)據(jù)正確、可靠；研究思路清晰、完整。07計算

5、及計算機應(yīng)用能力5具有較強的數(shù)據(jù)運算與處理能力；能運用計算機進行資料搜集、加工、處理和輔助設(shè)計等。08對計算或?qū)嶒灲Y(jié)果的分析能力（綜合分析能力、技術(shù)經(jīng)濟分析能力）10具有較強的數(shù)據(jù)收集、分析、處理、綜合的能力。成果質(zhì)量45%09插圖（或圖紙）質(zhì)量、篇幅、設(shè)計（論文）規(guī)范化程度5符合本專業(yè)相關(guān)規(guī)范或規(guī)定要求；規(guī)范化符合本文件第五條要求。10設(shè)計說明書（論文）質(zhì)量30綜述簡練完整，有見解；立論正確，論述充分，結(jié)論嚴(yán)謹(jǐn)合理；實驗正確，分析處理科學(xué)。11創(chuàng)新10對前人工作有改進或突破，或有獨特見解。成績指導(dǎo)教師評語指導(dǎo)教師簽名： 年月日摘要 數(shù)據(jù)結(jié)構(gòu)在計算機科學(xué)中一門綜合性的專業(yè)基礎(chǔ)課，不僅是一般程序

6、設(shè)計的基礎(chǔ)，而且是設(shè)計和實現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其他系統(tǒng)程序的重要基礎(chǔ)。經(jīng)過一學(xué)期的學(xué)習(xí)和幾周的實驗課。對知識的把握還需要從更為有目的性的程序設(shè)計來考驗。本設(shè)計的設(shè)計是為了解決數(shù)學(xué)算數(shù)中多項式的相加相減問題。當(dāng)然這相比于復(fù)雜的數(shù)學(xué)計算簡單至極。但對于數(shù)據(jù)結(jié)構(gòu)知識的鞏固卻很為重要。設(shè)計中主要涉及到帶頭指針的單鏈表存儲的的知識。采用C語言編寫，在對于多項式的存儲和計算操作中大量依賴于指針和結(jié)構(gòu)體。通過尾插法建立鏈表，指數(shù)的比較來實現(xiàn)結(jié)點元素的相加減。關(guān)鍵字 數(shù)據(jù)結(jié)構(gòu) 多項式 單鏈表 指針 結(jié)構(gòu)體 目錄摘要I目錄21.緒論11.1 前言11.2 問題的提出12.課程設(shè)計目的23.需求分析

7、33.1 功能分析33.2 設(shè)計思路34.概要設(shè)計44.1數(shù)據(jù)結(jié)構(gòu)的選用44.2多項式的輸入44.3主函數(shù)和其它函數(shù)45.流程圖設(shè)計65.1函數(shù)調(diào)用關(guān)系65.2程序流程圖76.程序代碼87.調(diào)試運行157.1運行程序操作平臺：157.2程序的載入157.3程序的編譯157.4程序運行測試數(shù)據(jù)158.總結(jié)181.緒論1.1 前言 計算機是隨著社會的發(fā)展應(yīng)運而生，它貫穿了人們生活的方方面面。其中，在科學(xué)計算方面，由于算法的高精確和高復(fù)雜度，對于計算機的依賴不可言喻。在這里，我設(shè)計了一個一元稀疏多項式簡單計數(shù)器，科學(xué)計算算不上，但作為學(xué)習(xí)性的實踐，對自己卻很重要。當(dāng)前計算機軟件技術(shù)和網(wǎng)絡(luò)技術(shù)飛速發(fā)展

8、，軟件系統(tǒng)日趨大型化、復(fù)雜化。因此社會對軟件開發(fā)者日出了比以往更高的要求。相應(yīng)的系統(tǒng)要求也有了很大的提高。本系統(tǒng)用C語言作為程序語言，設(shè)計出的系統(tǒng)功能完善，操作方便靈活。1.2 問題的提出 一元稀疏多項式簡單計數(shù)器基本功能要求：(1)輸入并建立多項式(2)輸出多項式，輸出形式為整數(shù)序列：n，c1，e1，c2，e2cn，en，其中n是多項式的項數(shù)，ci，ei分別為第i項的系數(shù)和指數(shù)。序列按指數(shù)降序排列。(3)多項式a和b相加，建立多項式a+b，輸出相加的多項式。(4)多項式a和b相減，建立多項式a-b，輸出相減的多項式。用帶表頭結(jié)點的單鏈表存儲多項式。2.課程設(shè)計目的使我們進一步理解和掌握課堂上

9、所學(xué)各種基本抽象數(shù)據(jù)類型的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和操作實現(xiàn)算法，以及它們在程序中的使用方法。使我們掌握軟件設(shè)計的基本內(nèi)容和設(shè)計方法，并培養(yǎng)學(xué)生進行規(guī)范化軟件設(shè)計的能力。使我們掌握使用各種計算機資料和有關(guān)參考資料，提高學(xué)生進行程序設(shè)計的基本能力。熟練掌握數(shù)據(jù)結(jié)構(gòu)這門課程，掌握線性表、棧、隊列、串、數(shù)組、廣義表、樹和二叉樹以及圖等基本類型的數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用。 進一步熟悉抽象數(shù)據(jù)類型的定義和實現(xiàn)、如何利用數(shù)組的動態(tài)分酚實現(xiàn)順序結(jié)構(gòu)、繼承的實現(xiàn)方式。學(xué)會分析研究計算機加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、想念結(jié)構(gòu)及基相應(yīng)的算法并初步掌握算法的時間分析和空間分析的技術(shù)?；菊莆粘绦蛟O(shè)

10、計的基本思路和方法。利用所學(xué)的基本知識和技能，解決簡單的程序設(shè)計問題各算法描述培養(yǎng)我們的數(shù)據(jù)抽象能力。3.需求分析3.1 功能分析 本程序要求輸入并建立多項式，能夠降冪顯示出多項式，實現(xiàn)多項式相加相減的計算問題，輸出結(jié)果。3.2 設(shè)計思路采用鏈表的方式存儲鏈表，定義結(jié)點結(jié)構(gòu)體。運用尾差法建立兩條單鏈表，以單鏈表polyn p和polyn h分別表示兩個一元多項式a和b。為實現(xiàn)處理，社p、q分別指向單鏈表polya和polyb的當(dāng)前項，比較p、q結(jié)點的指數(shù)項。 若p->expn<q->expn，則結(jié)點p所指的結(jié)點應(yīng)是“和多項式”中的一項，令指針p后移。 若p->expn=

11、q->expn，則將兩個結(jié)點中的系數(shù)相加，當(dāng)和不為0時修改結(jié)點p的系數(shù)。 若p->expn>q->expn，則結(jié)點q所指的結(jié)點應(yīng)是“和多項式”中的一項，將結(jié)點q插入在結(jié)點p之前，且令指針q在原來的鏈表上后移。4.概要設(shè)計4.1數(shù)據(jù)結(jié)構(gòu)的選用typedef struct Polynomial float coef; /系數(shù) int expn; /指數(shù) struct Polynomial *next;*Polyn,Polynomial;4.2多項式的輸入 Polyn CreatePolyn(Polyn head,int m) . for(i=0;i<m;i+) p=(

12、Polyn)malloc(sizeof(struct Polynomial); printf("請輸入第%d項的系數(shù)與指數(shù):",i+1); scanf("%f %d",&p->coef,&p->expn); Insert(p,head); return head;4.3主函數(shù)和其它函數(shù) void main() int m,n,a,x; char flag; Polyn pa=0,pb=0,pc; void DestroyPolyn(Polyn p) void PrintPolyn(Polyn P)int compare(Pol

13、yn a,Polyn b)Polyn AddPolyn(Polyn pa,Polyn pb)Polyn SubtractPolyn(Polyn pa,Polyn pb)5.流程圖設(shè)計5.1函數(shù)調(diào)用關(guān)系5.2程序流程圖6.程序代碼include<stdio.h>#include<malloc.h>typedef struct Polynomial/項的表示 float coef; /系數(shù) int expn; /指數(shù) struct Polynomial *next; /指針域*Polyn,Polynomial; /Polyn為結(jié)點指針類型void Insert(Polyn

14、p,Polyn h) /插入或者合并 if(p->coef=0) free(p); /系數(shù)為0的話釋放結(jié)點 else Polyn q1,q2; q1=h;q2=h->next; while(q2&&p->expn<q2->expn) /查找插入位置p與h項一次比較指數(shù) 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->

15、next=q2->next; free(q2); else /指數(shù)為新時將結(jié)點插入即p->expn>q2expn情況 p->next=q2; q1->next=p; /InsertPolyn CreatePolyn(Polyn head,int m)/建立一個頭指針為head、項數(shù)為m的一元多項式 int i; Polyn p; p=head=(Polyn)malloc(sizeof(struct Polynomial); head->next=NULL; for(i=0;i<m;i+) p=(Polyn)malloc(sizeof(struct Po

16、lynomial); /建立新結(jié)點以接收數(shù)據(jù) printf("請輸入第%d項的系數(shù)與指數(shù):",i+1); scanf("%f %d",&p->coef,&p->expn); Insert(p,head); /調(diào)用Insert函數(shù)插入結(jié)點 return head;/CreatePolynvoid DestroyPolyn(Polyn p) /銷毀多項式p Polyn q1,q2; q1=p->next; q2=q1->next; while(q1->next) free(q1); /釋放q1 q1=q2;/指針

17、后移，循環(huán)繼續(xù)釋放，直至銷毀 q2=q2->next; void PrintPolyn(Polyn P) /輸出多項式 Polyn q=P->next; int flag=1; /項數(shù)計數(shù)器 if(!q) /若多項式為空，輸出0 putchar('0'); printf("n"); return; while (q) if(q->coef>0&&flag!=1) putchar('+'); /系數(shù)大于0且不是第一項 if(q->coef!=1&&q->coef!=-1)/系數(shù)

18、非1或-1的普通情況 printf("%g",q->coef); if(q->expn=1) putchar('X');/系數(shù)為1的情況 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("X%d",q->expn); if(q-&

19、gt;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->expn>b->expn) return 1; else if(!

20、a|a->expn<b->expn) return -1; else return 0; else if(!a&&b) return -1;/a多項式已空，但b多項式非空 else return 1;/b多項式已空，但a多項式非空/comparePolyn AddPolyn(Polyn pa,Polyn pb)/求解并建立多項式a+b，返回其頭指針 Polyn qa=pa->next; Polyn qb=pb->next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial);/

21、建立頭結(jié)點 hc->next=NULL; headc=hc; while(qa|qb) qc=(Polyn)malloc(sizeof(struct Polynomial); switch(compare(qa,qb)/調(diào)用compare返回值 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-&

22、gt;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ù)為0時，釋放該結(jié)點 /while return headc;/AddPolynPolyn SubtractPolyn(Polyn pa,Polyn pb)/求解并建立多項式a-b，返回其頭指針 Polyn h=pb

23、; Polyn p=pb->next; Polyn pd; while(p) /將pb的系數(shù)取反 p->coef*=-1; p=p->next; pd=AddPolyn(pa,h); for(p=h->next;p;p=p->next) /恢復(fù)pb的系數(shù) p->coef*=-1; return pd;/SubtractPolynint main()/主函數(shù) int m,n,flag=0; float x; Polyn pa=0,pb=0,pc,pd,pe,pf;/定義各式的頭指針，pa與pb在使用前付初值NULL printf("請輸入a的項數(shù):&

24、quot;); scanf("%d",&m); pa=CreatePolyn(pa,m);/建立多項式a printf("請輸入b的項數(shù):"); scanf("%d",&n); pb=CreatePolyn(pb,n);/建立多項式a /輸出菜單 printf("*n"); printf("操作提示：nt1.輸出多項式a和bnt2.建立多項式a+bnt3.建立多項式a-bnt4.退出n"); for(;flag=0) printf("執(zhí)行操作"); scanf

25、("%d",&flag); if(flag=1)/輸出多項式 printf("多項式a：");PrintPolyn(pa); printf("多項式b：");PrintPolyn(pb);continue; if(flag=2)/多項式相加 pc=AddPolyn(pa,pb); /調(diào)用函數(shù)，實現(xiàn)相加 printf("多項式a+b：");PrintPolyn(pc); DestroyPolyn(pc);continue; if(flag=3)/多項式相減 pd=SubtractPolyn(pa,pb); p

26、rintf("多項式a-b：");PrintPolyn(pd); DestroyPolyn(pd);continue; if(flag=4) break; /結(jié)束循環(huán)，退出 DestroyPolyn(pa);/銷毀多項式，釋放內(nèi)存 DestroyPolyn(pb); return 0; 7.調(diào)試運行7.1運行程序操作平臺：硬件要求：PC機一臺軟件要求：windows XP以上操作系統(tǒng) VC+軟件7.2程序的載入7.3程序的編譯7.4程序運行測試數(shù)據(jù)(1) (2x+5x8-3.1x11)+(7-5x8+11x9)(2) (6x-3-x+4.4x2-1.2x9)-(-6x-3+

27、5.4x2+7.8x15)(3)(x+x2+x3)+0(4)(x+x3)-(-x-x-3)8.總結(jié) 這次課程設(shè)計是對數(shù)據(jù)結(jié)構(gòu)掌握的一次很有分量的測試。確實自己在這次課程設(shè)計中認(rèn)識到自己很多的不足。想了很多，思考了很多。對于知識的把握和編程的經(jīng)驗自己真的是差的太遠。 編程是個細(xì)致活。不溫不火，不急不躁。在五天的編程過程中，這點深有體會。想法太成熟，筆快容易失誤；知識太生疏，筆慢錯誤多。當(dāng)然，不能強求不出現(xiàn)錯誤。在編程過程要善于發(fā)現(xiàn)程序中的錯誤，并且能很快地排除這些錯誤，使程序能正確運行。經(jīng)驗豐富的人在錯誤出現(xiàn)時，能很快的判斷出錯誤的所在，并改之；經(jīng)驗少的人，則往往要花費大量的時間和氣力。我相信老師說的，很多程序的編寫都有靈感的參與，下次再次看自己程序的時候，也許不能很好的明白當(dāng)初某些地方的初衷。因此，在編程中，在思想靈感爆發(fā)的時候，最好的做法就是在旁邊寫上注釋。這次設(shè)計自己就走了很多彎路，程序一