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

1、目錄1.緒論21.1 前言21.2 問題的提出22.課程設(shè)計(jì)目的33.需求分析43.1 功能分析43.2 設(shè)計(jì)思路44.概要設(shè)計(jì)54.1數(shù)據(jù)結(jié)構(gòu)的選用54.2多項(xiàng)式的輸入54.3主函數(shù)和其它函數(shù)55.流程圖設(shè)計(jì)65.1函數(shù)調(diào)用關(guān)系65.2程序流程圖76.程序代碼87.調(diào)試運(yùn)行158.總結(jié)17參考文獻(xiàn)18 摘要在計(jì)算機(jī)科學(xué)中，數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象（數(shù)據(jù)元素）以及它們之間的關(guān)系和運(yùn)算等的學(xué)科，而且確保經(jīng)過這些運(yùn)算后所得到的新結(jié)構(gòu)仍然是原來的結(jié)構(gòu)類型。在許多類型的程序的設(shè)計(jì)中，數(shù)據(jù)結(jié)構(gòu)的選擇是一個(gè)基本的設(shè)計(jì)考慮因素。許多大型系統(tǒng)的構(gòu)造經(jīng)驗(yàn)表明，系統(tǒng)實(shí)現(xiàn)的困難程

2、度和系統(tǒng)構(gòu)造的質(zhì)量都嚴(yán)重的依賴于是否選擇了最優(yōu)的數(shù)據(jù)結(jié)構(gòu)。許多時(shí)候，確定了數(shù)據(jù)結(jié)構(gòu)后，算法就容易得到了。有些時(shí)候事情也會(huì)反過來，我們根據(jù)特定算法來選擇數(shù)據(jù)結(jié)構(gòu)與之適應(yīng)。不論哪種情況，選擇合適的數(shù)據(jù)結(jié)構(gòu)都是非常重要的。選擇了數(shù)據(jù)結(jié)構(gòu)，算法也隨之確定，是數(shù)據(jù)而不是算法是系統(tǒng)構(gòu)造的關(guān)鍵因素。這種洞見導(dǎo)致了許多種軟件設(shè)計(jì)方法和程序設(shè)計(jì)語(yǔ)言的出現(xiàn)，面向?qū)ο蟮某绦蛟O(shè)計(jì)語(yǔ)言就是其中之一。經(jīng)過一學(xué)期的學(xué)習(xí)我對(duì)數(shù)據(jù)結(jié)構(gòu)的知識(shí)有所了解，運(yùn)用我所學(xué)的知識(shí)來完成這個(gè)課程設(shè)計(jì)。采用c語(yǔ)言編寫，在對(duì)于多項(xiàng)式的存儲(chǔ)和計(jì)算操作中大量依賴于指針和結(jié)構(gòu)體。通過尾插法建立鏈表，指數(shù)的比較來實(shí)現(xiàn)結(jié)點(diǎn)元素的相加減。關(guān)鍵字 數(shù)據(jù)結(jié)構(gòu) 多

3、項(xiàng)式 鏈表 指針 結(jié)構(gòu)體 1.緒論1.1 前言 算機(jī)的應(yīng)用已滲透到社會(huì)的各個(gè)領(lǐng)域，正在改變著人們的工作、學(xué)習(xí)和生活的方式，推動(dòng)著社會(huì)的發(fā)展。歸納起來可分為以下幾個(gè)方面：如科學(xué)計(jì)算(數(shù)值計(jì)算)、數(shù)據(jù)處理(信息處理)、自動(dòng)控制、計(jì)算機(jī)輔助、人工智能、多媒體應(yīng)用、計(jì)算機(jī)網(wǎng)絡(luò)本系統(tǒng)用c語(yǔ)言作為程序語(yǔ)言，設(shè)計(jì)出的系統(tǒng)功能完善，操作方便靈活。1.2 問題的提出 一元稀疏多項(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分別為第i項(xiàng)的系數(shù)和指數(shù)。序列按指數(shù)降序排列。(3)多項(xiàng)式a和b相加，建立多項(xiàng)式

4、a+b，輸出相加的多項(xiàng)式。(4)多項(xiàng)式a和b相減，建立多項(xiàng)式a-b，輸出相減的多項(xiàng)式。用帶表頭結(jié)點(diǎn)的單鏈表存儲(chǔ)多項(xiàng)式。2.課程設(shè)計(jì)目的使我們進(jìn)一步理解和掌握課堂上所學(xué)各種基本抽象數(shù)據(jù)類型的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和操作實(shí)現(xiàn)算法，以及它們?cè)诔绦蛑械氖褂梅椒?。使我們掌握軟件設(shè)計(jì)的基本內(nèi)容和設(shè)計(jì)方法，并培養(yǎng)學(xué)生進(jìn)行規(guī)范化軟件設(shè)計(jì)的能力。使我們掌握使用各種計(jì)算機(jī)資料和有關(guān)參考資料，提高學(xué)生進(jìn)行程序設(shè)計(jì)的基本能力。熟練掌握數(shù)據(jù)結(jié)構(gòu)這門課程，掌握線性表、棧、隊(duì)列、串、數(shù)組、廣義表、樹和二叉樹以及圖等基本類型的數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用.進(jìn)一步熟悉抽象數(shù)據(jù)類型的定義和實(shí)現(xiàn)、如何利用數(shù)組的動(dòng)態(tài)分酚實(shí)現(xiàn)順序結(jié)構(gòu)、繼承的實(shí)現(xiàn)方式

5、。學(xué)會(huì)分析研究計(jì)算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、想念結(jié)構(gòu)及基相應(yīng)的算法并初步掌握算法的時(shí)間分析和空間分析的技術(shù)。基本掌握程序設(shè)計(jì)的基本思路和方法。利用所學(xué)的基本知識(shí)和技能，解決簡(jiǎn)單的程序設(shè)計(jì)問題各算法描述培養(yǎng)我們的數(shù)據(jù)抽象能力。3.需求分析3.1 功能分析 本程序要求輸入并建立多項(xiàng)式，能夠降冪顯示出多項(xiàng)式，實(shí)現(xiàn)多項(xiàng)式相加相減的計(jì)算問題，輸出結(jié)果。3.2 設(shè)計(jì)思路采用鏈表的方式存儲(chǔ)鏈表，定義結(jié)點(diǎn)結(jié)構(gòu)體。運(yùn)用尾差法建立兩條單鏈表，以單鏈表polyn p和polyn h分別表示兩個(gè)一元多項(xiàng)式a和b。為實(shí)現(xiàn)處理，社p、q分別指向單鏈表polya和polyb的當(dāng)前項(xiàng)，比

6、較p、q結(jié)點(diǎn)的指數(shù)項(xiàng)。 若p-expnexpn，則結(jié)點(diǎn)p所指的結(jié)點(diǎn)應(yīng)是“和多項(xiàng)式”中的一項(xiàng)，令指針p后移。 若p-expn=q-expn，則將兩個(gè)結(jié)點(diǎn)中的系數(shù)相加，當(dāng)和不為0時(shí)修改結(jié)點(diǎn)p的系數(shù)。 若p-expnq-expn，則結(jié)點(diǎn)q所指的結(jié)點(diǎn)應(yīng)是“和多項(xiàng)式”中的一項(xiàng)，將結(jié)點(diǎn)q插入在結(jié)點(diǎn)p之前，且令指針q在原來的鏈表上后移。4.概要設(shè)計(jì)4.1數(shù)據(jù)結(jié)構(gòu)的選用typedef struct polynomial float coef; /系數(shù) int expn; /指數(shù) struct polynomial *next;*polyn,polynomial;4.2多項(xiàng)式的輸入 polyn createpo

7、lyn(polyn head,int m) . for(i=0;icoef,&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(polyn a,polyn b)polyn addpolyn(polyn pa,polyn pb)polyn subtractpolyn(polyn pa,polyn pb)5.流程圖設(shè)

8、計(jì)5.1函數(shù)調(diào)用關(guān)系5.2程序流程圖6.程序代碼#include#includetypedef struct polynomial/項(xiàng)的表示 float coef; /系數(shù) int expn; /指數(shù) struct polynomial *next; /指針域*polyn,polynomial; /polyn為結(jié)點(diǎn)指針類型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) /查找插入位置p與h項(xiàng)一

9、次比較指數(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é)點(diǎn) q1-next=q2-next; free(q2); else /指數(shù)為新時(shí)將結(jié)點(diǎn)插入即p-expnq2expn情況 p-next=q2; q1-next=p; /insertpolyn createpolyn(polyn head,int m)/建立一個(gè)頭指針為head、項(xiàng)數(shù)為m的一元多項(xiàng)式 int i; polyn p; p=head=(polyn)malloc(sizeof(

10、struct polynomial); head-next=null; for(i=0;icoef,&p-expn); insert(p,head); /調(diào)用insert函數(shù)插入結(jié)點(diǎn) return head;/createpolynvoid destroypolyn(polyn p) /銷毀多項(xiàng)式p polyn q1,q2; q1=p-next; q2=q1-next; while(q1-next) free(q1); /釋放q1 q1=q2;/指針后移，循環(huán)繼續(xù)釋放，直至銷毀 q2=q2-next; void printpolyn(polyn p) /輸出多項(xiàng)式 polyn q=p-next

11、; 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);/系數(shù)為1的情況 else if(q-expn) printf(x%d,q-expn); else if(q-coef=1) if(!q-expn) putchar(1); else i

12、f(q-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);/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

13、 0; else if(!a&b) return -1;/a多項(xiàng)式已空，但b多項(xiàng)式非空 else return 1;/b多項(xiàng)式已空，但a多項(xiàng)式非空/comparepolyn 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(

14、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-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; h

15、c-next=qc; hc=qc; else free(qc);/當(dāng)相加系數(shù)為0時(shí)，釋放該結(jié)點(diǎn) /while return headc;/addpolynpolyn subtractpolyn(polyn pa,polyn pb)/求解并建立多項(xiàng)式a-b，返回其頭指針 polyn h=pb; 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;/subtractp

16、olynint main()/主函數(shù) int m,n,flag=0; float x; polyn pa=0,pb=0,pc,pd,pe,pf;/定義各式的頭指針，pa與pb在使用前付初值null printf(請(qǐng)輸入a的項(xiàng)數(shù):); scanf(%d,&m); pa=createpolyn(pa,m);/建立多項(xiàng)式a printf(請(qǐng)輸入b的項(xiàng)數(shù):); scanf(%d,&n); pb=createpolyn(pb,n);/建立多項(xiàng)式a /輸出菜單 printf(*n); printf(操作提示：nt1.輸出多項(xiàng)式a和bnt2.建立多項(xiàng)式a+bnt3.建立多項(xiàng)式a-bnt4.退出n); for

17、(;flag=0) printf(執(zhí)行操作); scanf(%d,&flag); if(flag=1)/輸出多項(xiàng)式 printf(多項(xiàng)式a：);printpolyn(pa); printf(多項(xiàng)式b：);printpolyn(pb);continue; if(flag=2)/多項(xiàng)式相加 pc=addpolyn(pa,pb); /調(diào)用函數(shù)，實(shí)現(xiàn)相加 printf(多項(xiàng)式a+b：);printpolyn(pc); destroypolyn(pc);continue; if(flag=3)/多項(xiàng)式相減 pd=subtractpolyn(pa,pb); printf(多項(xiàng)式a-b：);printpol

18、yn(pd); destroypolyn(pd);continue; if(flag=4) break; /結(jié)束循環(huán)，退出 destroypolyn(pa);/銷毀多項(xiàng)式，釋放內(nèi)存 destroypolyn(pb); return 0; 7.調(diào)試運(yùn)行 (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)8.總結(jié)我覺得寫程序，應(yīng)該先找到該程序中的核心地方，用多種方法來實(shí)現(xiàn)該核心，這才可能避免邏輯上或者編譯器不支持上的錯(cuò)誤。這樣花費(fèi)大量時(shí)間在改程序上是很不值得的。實(shí)踐是檢驗(yàn)真理的唯一標(biāo)準(zhǔn)，這句話很正確，如果沒有實(shí)踐，就不會(huì)發(fā)現(xiàn)和深刻體會(huì)它的真實(shí)所在。只有通過檢驗(yàn)的真理，在自己的心里，才會(huì)認(rèn)可它的真實(shí)性。面向?qū)ο蟪绦蛟O(shè)計(jì)的完成，使我們懂得了真理的重要性，理論和實(shí)際的相結(jié)合，才能真正把握所學(xué)和所掌握的知識(shí)。埋頭苦干的過程是苦澀的，在書山中查找資料的過程是疲倦的，但當(dāng)課程設(shè)計(jì)完成時(shí)，那感覺是甜蜜的，沒有耕耘，哪來得收