數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-一元多項(xiàng)式_第1頁(yè)
數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-一元多項(xiàng)式_第2頁(yè)
數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-一元多項(xiàng)式_第3頁(yè)
已閱讀5頁(yè),還剩12頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、濟(jì)南鼻誰(shuí)總【寵數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告課 題:一元多項(xiàng)式姓 名:XX學(xué) 號(hào):8專(zhuān)業(yè)班級(jí):XXXX指導(dǎo)教師:XXXX設(shè)計(jì)時(shí)間: 2015年12月30日星期三評(píng)閱意見(jiàn):評(píng)定成績(jī):指導(dǎo)老師簽名:目錄一、任務(wù)目標(biāo)3二、概要設(shè)計(jì)4三、詳細(xì)設(shè)計(jì)6五、源程序代碼8六、程序運(yùn)行效果圖與說(shuō)明15七、本次實(shí)驗(yàn)小結(jié)16八、參考文獻(xiàn)16一'任務(wù)目標(biāo)分析(1) a.能夠按照指數(shù)降序排列建立并輸出多項(xiàng)式b. 能夠完成兩個(gè)多項(xiàng)式的相加,相減,并將結(jié)果輸入要求:程序所能達(dá)到的功能:a. 實(shí)現(xiàn)一元多項(xiàng)式的輸入;b. 實(shí)現(xiàn)一元多項(xiàng)式的輸出;c. 計(jì)算兩個(gè)一元多項(xiàng)式的和并輸出結(jié)果;d. 計(jì)算兩個(gè)一元多項(xiàng)式的差并輸出結(jié)果;除任務(wù)

2、要求外新增乘法:計(jì)算兩個(gè)一元多項(xiàng)式的乘積并輸出結(jié)果(2)輸入的形式和輸入值的圍:輸入要求:分行輸入,每行輸入一項(xiàng),先輸入多項(xiàng)式的指數(shù),再輸入多項(xiàng) 式的系數(shù),以0 0為結(jié)束標(biāo)志,結(jié)束一個(gè)多項(xiàng)式的輸入。輸入形式:2 3-1 23 01 20 0輸入值的圍:系數(shù)為int型,指數(shù)為float型(3)輸出的形式:第一行輸出多項(xiàng)式1;第二行輸出多項(xiàng)式2;第三行輸出多項(xiàng)式1與多項(xiàng)式2相加的結(jié)果多項(xiàng)式;第四行輸出多項(xiàng)式1與多項(xiàng)式2相減的結(jié)果多項(xiàng)式;第五行輸出多項(xiàng)式1與多項(xiàng)式2相乘的結(jié)果多項(xiàng)式二、概要設(shè)計(jì)程序?qū)崿F(xiàn)a. 功能:將要進(jìn)行運(yùn)算的二項(xiàng)式輸入輸出;b. 數(shù)據(jù)流入:要輸入的二項(xiàng)式的系數(shù)與指數(shù);c. 數(shù)據(jù)流出

3、:合并同類(lèi)項(xiàng)后的二項(xiàng)式;d. 程序流程圖:二項(xiàng)式輸入流程圖;e. 測(cè)試要點(diǎn):輸入的二項(xiàng)式是否正確,若輸入錯(cuò)誤則重新輸入。流程圖:三、詳細(xì)設(shè)計(jì)(1):存儲(chǔ)結(jié)構(gòu)一元多項(xiàng)式的表示在計(jì)算機(jī)可以用鏈表來(lái)表示,為了節(jié)省存儲(chǔ)空間, 只存儲(chǔ)多項(xiàng)式中系數(shù)非零的項(xiàng)。鏈表中的每一個(gè)結(jié)點(diǎn)存放多項(xiàng)式的一個(gè)系數(shù)非零 項(xiàng),它包含三個(gè)域,分別存放該項(xiàng)的系數(shù)、指數(shù)以及指向下一個(gè)多項(xiàng)式項(xiàng)結(jié)點(diǎn)的 指針。創(chuàng)建一元多項(xiàng)式鏈表,對(duì)一元多項(xiàng)式的運(yùn)算中會(huì)出現(xiàn)的各種可能情況進(jìn)行 分析,實(shí)現(xiàn)一元多項(xiàng)式的相加、相減操作。(2):數(shù)據(jù)鏈表由于采用鏈表的方法,我們可以建立3條鏈;一條用于存放多項(xiàng)式HA, 條用于存放多項(xiàng)式HB,還有一條用于存放新形成的

4、HC。此外,我們的程序應(yīng)具 備以下幾個(gè)功能:建立鏈表,撤銷(xiāo)鏈表,打印鏈表,按要求插入一個(gè)新的結(jié)點(diǎn), 復(fù)制鏈表;為了使上面程序結(jié)構(gòu)分析進(jìn)一步細(xì)化,為了使程序結(jié)構(gòu)更加清晰,我 們可以把上面的容都編寫(xiě)成函數(shù)形式。1、建立鏈表該程序建立鏈表的函數(shù)與大多數(shù)建立鏈表的操作基本一致,但是由于實(shí)體 是一元多項(xiàng)式的關(guān)系。我們更希望,在處理客戶輸入的數(shù)據(jù)的同時(shí),能對(duì)數(shù)據(jù)進(jìn) 行適當(dāng)?shù)奶幚?。也就是?shù)學(xué)上所說(shuō)的,“對(duì)一元多項(xiàng)式進(jìn)行化簡(jiǎn),并按照降幕排 序。”由于在前面的練習(xí)中,我們得知,在鏈表中插入一個(gè)結(jié)點(diǎn)的函數(shù),具有對(duì) 鏈表的成員進(jìn)行排序與合并的功能。如此一來(lái),我們可以巧妙地處理,在建立鏈 表的同時(shí),調(diào)用”在鏈表中插入

5、一個(gè)結(jié)點(diǎn)的函數(shù)”,對(duì)新建立的鏈表進(jìn)行化簡(jiǎn)。該函數(shù)的算法描述如下;聲明指針變量,并作為頭指針的指針變量賦初值NULL;創(chuàng)建一個(gè)新的結(jié)點(diǎn),并輸入鏈表的信息;若輸入的系數(shù)值與函數(shù)值同不為0時(shí),調(diào)用”在鏈表中插入一個(gè)結(jié)點(diǎn)的 insert函數(shù)”,將結(jié)點(diǎn)插入鏈表中;(注:這里建立鏈表的函數(shù)與以往的不同, 我們是通過(guò)假想有一條空鏈,不斷地調(diào)用insert函數(shù)來(lái)實(shí)現(xiàn)建立鏈表的功能。 簡(jiǎn)言之;鏈表中成員的全都靠insert函數(shù)來(lái)實(shí)現(xiàn),而該函數(shù)僅僅是不斷地提供 建立鏈表所要的數(shù)據(jù)罷了。)若還要繼續(xù)插入結(jié)點(diǎn),轉(zhuǎn)到步驟2繼續(xù)進(jìn)行;否則,程序結(jié)束,把頭指針?lè)祷刂鞒绦颉?、撤銷(xiāo)鏈表撤銷(xiāo)鏈表是為了把鏈表所占用的地址回收起來(lái)

6、,防止造成浪費(fèi)。我們?cè)摮?序可以采用從鏈表的始端逐步銷(xiāo)去結(jié)點(diǎn)。在這個(gè)過(guò)程中,我們需要鏈表的頭地址 作為形式參數(shù),還需要建立一個(gè)指針用來(lái)指向新頭地址。該函數(shù)的算法描述如下:指針變量;并把頭地址指針賦給新指針變量;把頭地址指針指向下一個(gè)結(jié)點(diǎn);刪除新指針變量;若還要繼續(xù)刪除結(jié)點(diǎn),轉(zhuǎn)到步驟1繼續(xù)執(zhí)行;否則,結(jié)束程序。3、按要求插入一個(gè)新的結(jié)點(diǎn)由于前面的建立鏈表的creat函數(shù),調(diào)用了該函數(shù),所以我們這個(gè)函數(shù)的 設(shè)計(jì)思想也明朗多了,由于建立的鏈表是有序的,并且需要合并指數(shù)相同的結(jié)點(diǎn), 所以要新結(jié)點(diǎn)需要按指數(shù)值降無(wú)的順序插入鏈表中。判斷鏈表是否為空,如果為 空則直接插入即可;否則按照要插入結(jié)點(diǎn)指數(shù)值的大小

7、在鏈表中尋找他要插入的 位置,對(duì)于插入位置有第一個(gè)節(jié)點(diǎn)、最后一個(gè)結(jié)點(diǎn)和鏈表中間這三種情況分別進(jìn) 行處理。函數(shù)的形式參數(shù):鏈表的頭地址,指向要插入結(jié)點(diǎn)的指針;返回結(jié)果:插入結(jié)點(diǎn)后新鏈表的頭地址。該函數(shù)的算法描述如下:聲明指針變量并令它指向連頭結(jié)點(diǎn);判斷指向要插入結(jié)點(diǎn)的指針是否為空;如果是,則不需要插入新結(jié)點(diǎn),直接返回頭地址,程序結(jié)束;否則再判斷鏈表是否為空;如果是,則直接插入結(jié)點(diǎn),然后返回鏈表的頭地址,程序結(jié)束;否則,在鏈表中尋找待插入結(jié)點(diǎn)的插入位置:1,若鏈表中存在著與“插入的結(jié)點(diǎn)"的指數(shù)相同的情況,我們依然插入鏈中,只是把該結(jié)點(diǎn)的系數(shù)修改為” 0”,把鏈中的結(jié)點(diǎn)系數(shù)修改為”兩系數(shù)之

8、 和”。(為了方便,我們并沒(méi)有把結(jié)點(diǎn)進(jìn)行刪除的操作,只是在輸出的操作里加 入權(quán)限設(shè)置。)2,若鏈表中不存在著與“插入的結(jié)點(diǎn)”的指數(shù)相同的情況,我們 正常地插入鏈中。返回插入結(jié)點(diǎn)后鏈表的頭地址,程序結(jié)束。4、主函數(shù)主函數(shù)主要負(fù)責(zé)輸出界面的指引語(yǔ)句,并合理地調(diào)用各個(gè)函數(shù),還要有適 當(dāng)?shù)难h(huán)操作以及停止循環(huán)的語(yǔ)句,以致可以方便地達(dá)到合并兩個(gè)一元多項(xiàng)式的 功能。四、調(diào)試分析(1) 調(diào)試過(guò)程中遇到的問(wèn)題是如何解決的以及對(duì)設(shè)計(jì)與實(shí)現(xiàn)的回顧討論和 分析:在輸入諸如"0,3”,“2,0”時(shí),程序無(wú)常運(yùn)行或總是出錯(cuò).解決:對(duì)指數(shù)或系數(shù)為0的情況應(yīng)單獨(dú)討論。為此,建立了 delZeroCoef 函數(shù)來(lái)解

9、決問(wèn)題。(2) 算法的時(shí)間復(fù)雜度及改進(jìn)算法的時(shí)間復(fù)雜度:一元多項(xiàng)式的加法運(yùn)算的時(shí)間復(fù)雜度為0(m+n),減法 運(yùn)算的時(shí)間復(fù)雜度為0(m-n),其中ni, n分別表示二個(gè)一元多項(xiàng)式的項(xiàng)數(shù)。問(wèn)題和改進(jìn)思想:在設(shè)計(jì)該算法時(shí),出現(xiàn)了一些問(wèn)題,例如在建立鏈表時(shí) 頭指針的設(shè)立導(dǎo)致了之后運(yùn)用到相關(guān)的指針時(shí)沒(méi)能很好的移動(dòng)指針出現(xiàn)了數(shù)據(jù) 重復(fù)輸出或是輸出系統(tǒng)缺省值,不能實(shí)現(xiàn)算法。實(shí)現(xiàn)加法時(shí)該鏈表并沒(méi)有向通常 那樣通過(guò)建立第三個(gè)鏈表來(lái)存放運(yùn)算結(jié)果,而是再度利用了鏈表之一來(lái)進(jìn)行節(jié)點(diǎn) 的比較插入刪除等操作。為了使輸入數(shù)據(jù)按指數(shù)降序排列,可在數(shù)據(jù)的輸入后先 做一個(gè)節(jié)點(diǎn)的排序函數(shù),通過(guò)對(duì)鏈表排序后再進(jìn)行之后加減運(yùn)算。五、

10、源程序代碼#include<stdlib. h>#includestdio h>#includectype h>typedef struct LNode float coef;int expn;struct LNode *next;LNode;LNode* InitPolyn(LNode *La,int n) if(n <= 0) return NULL;LNode *h = La = (LNode*)malloc(sizeof(LNode), *Lb;La->coef = 0. 0;int i;printf (,r依次輸入呦 個(gè)非零項(xiàng)(每項(xiàng)前一個(gè)為系數(shù),后

11、一個(gè)為指數(shù))n'n);for (i = 1; i <= n; +i) scanf (,r%f%d", &La->coef T &La->expn);if(La>coef)Lb = La;La = La->next = (LNode*)malloc(sizeof(LNode):Lb->next = NULL;free(La);return h;LNode* seisort(LNode *h) LNode *g, *Lat *Lb;if(!h) return NULL;float f;int i, fini = 1:for(g

12、= h;g->next&&fini;g = g->next) fini = 0;for(La = h,Lb = h->next;Lb;La = La->next,Lb = Lb->next) if (La->expn < Lb->expn) f = La->coef;i = La->expn;La->coef = Lb->coef:La->expn = Lb->expn;Lb->coef = f;Lb->expn = i;fini = 1;for(g = htLa = g->n

13、ext;La;)if (g->expn=La->expn) g->coef += La->coef;g->next = La->next;Lb = La;La = La->next;free (Lb);else if(g->next) g = g->next;La = La->next;return h;void PrintfPoly(LNode *La) LNode *Lb = La;if(!Lb) putchar (r0F); return;if(Lb->coef!=l) printf(w%gtt,Lb->coef);

14、if(Lb->expn=l) putchar('X');else if(Lb->expn) printf,Lb->expn); else if (!Lb->expn) putchar(F T);else if(Lb->expn=l) putchar('X');else printf,Lb->expn);Lb = Lb-next;wh訂e (Lb) if(Lb->coef > 0) putchar('+'); if(Lb->coef!=l) printf("%g",Lb-&g

15、t;coef); if(Lb->expn=l) putchar('X'); else if (Lb->expn) printf (,fX %d, Lb->expn); else if (!Lb->expn) putchar(r T);else if(Lb->exp門(mén)二二1) putchar('X');else printf ("X"%d",Lb->expn);Lb = Lb->next;Compare(LNode *a, LNode *b) if (a->expn < b->

16、;expn) return T;if (a->expn > b->expn) return 1;return 0;LNode* AddPolyn (LNode *Pa, LNode *pb) LNode *ht *qa = Pa, *qb = Pb, *Lat *Lb; float sum;h = La = (LNode*)malloc(sizeof(LNode): La->next = NULL;while (qa && qb) switch (Compare(qa,qb) case -1:La-next = qb;La = qb;qb = qb-&g

17、t;next;break;case 0:sum = qa->coef + qb->coef;if (sum != 0. 0) La->next = qa;qa->coef = sum;La = qa;qa = qa->next;else Lb = qa;qa = qa>next;free (Lb);Lb = qb;qb = qb->next;free(Lb);break;case 1:La-next = qa;La = qa;qa = qa->next;break;if (Pa) La->next = qa;if (Pb) La->n

18、ext = qb;Lb = h;h = h->next;free (Lb);return h;LNode* Add(LNode *Pa, LNode *Pb) int n;puts("再輸入1個(gè)一元多項(xiàng)式的項(xiàng)數(shù)"); scanf (,r%d,r,&n);Pb = InitPolyn(Pb,n):Pb = seisort(Pb);PrintfPoly(Pa);if(Pb && Pb->coef>0) printf(ff + ");PrintfPoly(Pb);Pa = AddPolyn(PatPb): printf (,r

19、= ”);Pa = seisort(Pa):PrintfPoly(Pa);return Pa;LNode* SubtractPolyn(LNode *Pa, LNode *Pb)LNode *La = Pb;wh 訂 e(La) La->coef *二-1;La = La->next;return AddPolyn(Pa,Pb):LNode* Subtract (LNode *Pat LNode *Pb) int n;puts('rn再輸入1個(gè)一元多項(xiàng)式的項(xiàng)數(shù)"); scanf("%d",&n);Pb = InitPolyn(Pb,n)

20、:Pb = seisort(Pb):PrintfPoly(Pa);printf(w - ”); putchar(r (r):PrintfPoly(Pb):putchar(r)');Pa = SubtractPolyn(Pa,Pb): printf (,r = ”);Pa = seisort(Pa):PrintfPoly(Pa);return Pa;LNode* Mu11 i p1yPo1yn(LNode *Pa, LNode *Pb) if(!Pb) return NULL;LNode *pa = Pa, *q, *rt *s, *t;r = p = (LNode*)malloc(si

21、zeof(LNode):while (pa) p->coef = pa->coef:p->expn = pa->expn;Q = P;p = p->next = (LNode*)malloc(sizeof(LNode): pa = pa->next;q->next = NULL;free(p);pa = Pa;t = s = (LNode*)malloc(sizeof(LNode):while (pa) q = s;s = s>next = (LNode*)malloc(sizeof(LNode): pa = pa->next;q->

22、next = NULL;free(s);pa = Pa;while (pa) pa->coef *= Pb->coef;pa->expn += Pb->expn;pa = pa->next;Pb = Pb->next;wh訂e (Pb) p = r;s = t;while(p) s>coef = p->coef * Pb->coef;s->expn = p->expn + Pb>expn;p = p->next;s = s->next;Pa = AddPolyn(Pat t):Pb = Pb->next;

23、return Pa;LNode* Multiply(LNode *pa, LNode *Pb) int n;puts('rn再輸入1個(gè)一元多項(xiàng)式的項(xiàng)數(shù)");scanf (w%dw,&n);Pb = InitPolyn(Pb,n):Pb = seisort(Pb):putchar(r (r):PrintfPoly(Pa):putchar(r)'); printf (,r X ");putchar(r (f):PrintfPoly(Pb):putchar(F)9); printf (,r = ”);Pa = MultiplyPolyn(Pat Pb):P

24、a = seisort (Pa):PrintfPoly(Pa);return Pa;void main() LNode *A,*B;char s2j;int irn;pr intf (,r tt t()()()0()0()()()()()0()0()()()()()0()0()()()()()0()0n,r); printf(,rttt元多項(xiàng)式計(jì)算n ”);printf('fttt ()()()()()()00()()()()()()()0()()()()()()()0()()()()()()n,r): printf(,rttt # 王偉 #n"); puts(,fn輸入1個(gè)

25、一元多項(xiàng)式的項(xiàng)數(shù)”);scanf (w%d,r»&n);A = InitPolyn(A,n);A = seisort(A);PrintfPoly(A);p: puts (,rnl :加n2:減n3:乘n4:退出");getchar ();q: gets(s):if(sl!=,0, | 1isdigit(*s) puts(,rError,請(qǐng)重新輸入! ,r);goto q; i = *s-48;switch(i) case 1:A = Add(AtB):goto p;:case 2:A = Subtract(A,B):goto p;:case 3:A = Multiply(A,B):goto p;case 4:break;default: puts (,F(xiàn)Errort 請(qǐng)重新輸入! ”); goto q;六、程序運(yùn)行效果圖與說(shuō)明0000000000000000000000一元多項(xiàng)式計(jì)算0000000000

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論