數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告一元多項(xiàng)式

1、 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 課 題: 一元多項(xiàng)式 姓 名： XX 學(xué) 號(hào)： 201417030218 專業(yè)班級(jí)： XXXX 指導(dǎo)教師： XXXX 設(shè)計(jì)時(shí)間： 2015年12月30日星期三 評閱意見：評定成績： 指導(dǎo)老師簽名： 年 月 日 目錄一、 任務(wù)目標(biāo) 3二、 概要設(shè)計(jì) 4三、 詳細(xì)設(shè)計(jì) 6四、 調(diào)試分析 8五、 源程序代碼 8六、 程序運(yùn)行效果圖與說明 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)式的輸出；

2、 c.計(jì)算兩個(gè)一元多項(xiàng)式的和并輸出結(jié)果； d.計(jì)算兩個(gè)一元多項(xiàng)式的差并輸出結(jié)果；除任務(wù)要求外新增乘法：計(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. 功能

3、：將要進(jìn)行運(yùn)算的二項(xiàng)式輸入輸出；b. 數(shù)據(jù)流入：要輸入的二項(xiàng)式的系數(shù)與指數(shù)；c. 數(shù)據(jù)流出：合并同類項(xiàng)后的二項(xiàng)式；d. 程序流程圖：二項(xiàng)式輸入流程圖；e. 測試要點(diǎn)：輸入的二項(xiàng)式是否正確，若輸入錯(cuò)誤則重新輸入。流程圖：開始申請結(jié)點(diǎn)空間輸入二項(xiàng)式各項(xiàng)的系數(shù) x, 指數(shù) y輸入二項(xiàng)式的項(xiàng)數(shù)輸出已輸入的二項(xiàng)式是否輸入正確合并同類項(xiàng)結(jié)束是否17三、詳細(xì)設(shè)計(jì)（1）：存儲(chǔ)結(jié)構(gòu) 一元多項(xiàng)式的表示在計(jì)算機(jī)內(nè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)式鏈表，對一

4、元多項(xiàng)式的運(yùn)算中會(huì)出現(xiàn)的各種可能情況進(jìn)行分析，實(shí)現(xiàn)一元多項(xiàng)式的相加、相減操作。（2）：數(shù)據(jù)鏈表由于采用鏈表的方法，我們可以建立3條鏈；一條用于存放多項(xiàng)式HA，一條用于存放多項(xiàng)式HB，還有一條用于存放新形成的HC。此外，我們的程序應(yīng)具備以下幾個(gè)功能：建立鏈表，撤銷鏈表，打印鏈表，按要求插入一個(gè)新的結(jié)點(diǎn)，復(fù)制鏈表；為了使上面程序結(jié)構(gòu)分析進(jìn)一步細(xì)化，為了使程序結(jié)構(gòu)更加清晰，我們可以把上面的內(nèi)容都編寫成函數(shù)形式。1、建立鏈表該程序建立鏈表的函數(shù)與大多數(shù)建立鏈表的操作基本一致，但是由于實(shí)體是一元多項(xiàng)式的關(guān)系。我們更希望，在處理客戶輸入的數(shù)據(jù)的同時(shí)，能對數(shù)據(jù)進(jìn)行適當(dāng)?shù)奶幚?。也就是?shù)學(xué)上所說的，“對一元多項(xiàng)

5、式進(jìn)行化簡，并按照降冪排序?！庇捎谠谇懊娴木毩?xí)中，我們得知，在鏈表中插入一個(gè)結(jié)點(diǎn)的函數(shù)，具有對鏈表的成員進(jìn)行排序與合并的功能。如此一來，我們可以巧妙地處理，在建立鏈表的同時(shí)，調(diào)用”在鏈表中插入一個(gè)結(jié)點(diǎn)的函數(shù)”，對新建立的鏈表進(jì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ù)與以往的不同，我們是通過假想有一條空鏈，不斷地調(diào)用insert函數(shù)來實(shí)現(xiàn)建立鏈表的功能。簡言之；鏈表中成員的鏈接全都靠insert

6、函數(shù)來實(shí)現(xiàn)，而該函數(shù)僅僅是不斷地提供建立鏈表所要的數(shù)據(jù)罷了。)若還要繼續(xù)插入結(jié)點(diǎn)，轉(zhuǎn)到步驟2繼續(xù)進(jìn)行；否則，程序結(jié)束，把頭指針返回主程序。2、撤銷鏈表撤銷鏈表是為了把鏈表所占用的地址回收起來，防止造成浪費(fèi)。我們該程序可以采用從鏈表的始端逐步銷去結(jié)點(diǎn)。在這個(gè)過程中，我們需要鏈表的頭地址作為形式參數(shù)，還需要建立一個(gè)指針用來指向新頭地址。該函數(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ì)思想也

7、明朗多了，由于建立的鏈表是有序的，并且需要合并指數(shù)相同的結(jié)點(diǎn)，所以要新結(jié)點(diǎn)需要按指數(shù)值降冪的順序插入鏈表中。判斷鏈表是否為空，如果為空則直接插入即可；否則按照要插入結(jié)點(diǎn)指數(shù)值的大小在鏈表中尋找他要插入的位置，對于插入位置有第一個(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é)束；否則，在鏈

8、表中尋找待插入結(jié)點(diǎn)的插入位置：1，若鏈表中存在著與“插入的結(jié)點(diǎn)”的指數(shù)相同的情況，我們依然插入鏈中，只是把該結(jié)點(diǎn)的系數(shù)修改為”0”，把鏈中的結(jié)點(diǎn)系數(shù)修改為”兩系數(shù)之和”。(為了方便，我們并沒有把結(jié)點(diǎn)進(jìn)行刪除的操作，只是在輸出的操作里加入權(quán)限設(shè)置。) 2，若鏈表中不存在著與“插入的結(jié)點(diǎn)”的指數(shù)相同的情況，我們正常地插入鏈中。返回插入結(jié)點(diǎn)后鏈表的頭地址，程序結(jié)束。4、主函數(shù)主函數(shù)主要負(fù)責(zé)輸出界面的指引語句，并合理地調(diào)用各個(gè)函數(shù)，還要有適當(dāng)?shù)难h(huán)操作以及停止循環(huán)的語句，以致可以方便地達(dá)到合并兩個(gè)一元多項(xiàng)式的功能。四、調(diào)試分析（1）調(diào)試過程中遇到的問題是如何解決的以及對設(shè)計(jì)與實(shí)現(xiàn)的回顧討論和分析:在輸

9、入諸如“0,3”，“2,0”時(shí)，程序無法正常運(yùn)行或總是出錯(cuò).解決：對指數(shù)或系數(shù)為0的情況應(yīng)單獨(dú)討論。為此，建立了delZeroCoef函數(shù)來解決問題。（2）算法的時(shí)間復(fù)雜度及改進(jìn)算法的時(shí)間復(fù)雜度：一元多項(xiàng)式的加法運(yùn)算的時(shí)間復(fù)雜度為O(m+n）,減法運(yùn)算的時(shí)間復(fù)雜度為O(m-n)，其中m，n分別表示二個(gè)一元多項(xiàng)式的項(xiàng)數(shù)。問題和改進(jìn)思想：在設(shè)計(jì)該算法時(shí)，出現(xiàn)了一些問題，例如在建立鏈表時(shí)頭指針的設(shè)立導(dǎo)致了之后運(yùn)用到相關(guān)的指針時(shí)沒能很好的移動(dòng)指針出現(xiàn)了數(shù)據(jù)重復(fù)輸出或是輸出系統(tǒng)缺省值，不能實(shí)現(xiàn)算法。實(shí)現(xiàn)加法時(shí)該鏈表并沒有向通常那樣通過建立第三個(gè)鏈表來存放運(yùn)算結(jié)果，而是再度利用了鏈表之一來進(jìn)行節(jié)點(diǎn)的比較插

10、入刪除等操作。為了使輸入數(shù)據(jù)按指數(shù)降序排列，可在數(shù)據(jù)的輸入后先做一個(gè)節(jié)點(diǎn)的排序函數(shù)，通過對鏈表排序后再進(jìn)行之后加減運(yùn)算。五、 源程序代碼#include #include #include typedef struct LNode float coef; int expn; struct LNode *next; LNode; LNode* InitPolyn(LNode *La,int n) if(n coef = 0.0; int i; printf(依次輸入%d個(gè)非零項(xiàng)（每項(xiàng)前一個(gè)為系數(shù)，后一個(gè)為指數(shù)）n,n); for (i = 1; i coef,&La-expn); if(La-c

11、oef) Lb = La; La = La-next = (LNode*)malloc(sizeof(LNode); Lb-next = NULL; free(La); return h; LNode* selsort(LNode *h) LNode *g, *La, *Lb; if(!h) return NULL; float f; int i, fini = 1; for(g = 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 expn)

12、 f = La-coef;i = La-expn; La-coef = Lb-coef;La-expn = Lb-expn; Lb-coef = f;Lb-expn = i; fini = 1; for(g = h,La = g-next;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 *

13、Lb = La; if(!Lb) putchar(0); return; if(Lb-coef!=1) printf(%g,Lb-coef); if(Lb-expn=1) putchar(X); else if(Lb-expn) printf(X%d,Lb-expn); else if(!Lb-expn) putchar(1); else if(Lb-expn=1) putchar(X); else printf(X%d,Lb-expn); Lb = Lb-next; while (Lb) if(Lb-coef 0) putchar(+); if(Lb-coef!=1) printf(%g,L

14、b-coef); if(Lb-expn=1) putchar(X); else if(Lb-expn) printf(X%d,Lb-expn); else if(!Lb-expn) putchar(1); else if(Lb-expn=1) putchar(X); else printf(X%d,Lb-expn); Lb = Lb-next; Compare(LNode *a, LNode *b) if (a-expn expn) return -1; if (a-expn b-expn) return 1; return 0; LNode* AddPolyn(LNode *Pa, LNod

15、e *Pb) LNode *h, *qa = Pa, *qb = Pb, *La, *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-next; break; case 0: sum = qa-coef + qb-coef; if (sum != 0.0) La-next = qa; qa-coef = sum; La = qa; qa = qa-

16、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-next = 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(%d,&n); Pb =

17、InitPolyn(Pb,n); Pb = selsort(Pb); PrintfPoly(Pa); if(Pb & Pb-coef0) printf( + ); PrintfPoly(Pb); Pa = AddPolyn(Pa,Pb); printf( = ); Pa = selsort(Pa); PrintfPoly(Pa); return Pa; LNode* SubtractPolyn(LNode *Pa, LNode *Pb) LNode *La = Pb; while(La) La-coef *= -1; La = La-next; return AddPolyn(Pa,Pb);

18、LNode* Subtract(LNode *Pa, LNode *Pb) int n; puts(n再輸入1個(gè)一元多項(xiàng)式的項(xiàng)數(shù)); scanf(%d,&n); Pb = InitPolyn(Pb,n); Pb = selsort(Pb); PrintfPoly(Pa); printf( - ); putchar();PrintfPoly(Pb);putchar(); Pa = SubtractPolyn(Pa,Pb); printf( = ); Pa = selsort(Pa); PrintfPoly(Pa); return Pa; LNode* MultiplyPolyn(LNode *P

19、a, LNode *Pb) if(!Pb) return NULL; LNode *pa = Pa, *p, *q, *r, *s, *t; r = p = (LNode*)malloc(sizeof(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)

20、q = s; s = s-next = (LNode*)malloc(sizeof(LNode); pa = pa-next; q-next = NULL; free(s); pa = Pa; while(pa) pa-coef *= Pb-coef; pa-expn += Pb-expn; pa = pa-next; Pb = Pb-next; while(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(

21、Pa,t); Pb = Pb-next; return Pa; LNode* Multiply(LNode *Pa, LNode *Pb) int n; puts(n再輸入1個(gè)一元多項(xiàng)式的項(xiàng)數(shù)); scanf(%d,&n); Pb = InitPolyn(Pb,n); Pb = selsort(Pb); putchar();PrintfPoly(Pa);putchar(); printf(); putchar();PrintfPoly(Pb);putchar(); printf( = ); Pa = MultiplyPolyn(Pa,Pb); Pa = selsort(Pa); PrintfP

22、oly(Pa); return Pa; void main() LNode *A,*B; char s2; int i,n; printf(tttOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOn); printf(ttt 一元多項(xiàng)式計(jì)算n ); printf(tttOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOn); printf(ttt # 王偉 #n);puts(n輸入1個(gè)一元多項(xiàng)式的項(xiàng)數(shù)); scanf(%d,&n); A = InitPolyn(A,n); A = selsort(A); PrintfPoly(A); p: puts(n1:加n2:減n3:乘n4:退出); getchar(); q: gets(s); if(s1!=0 | !isdigit(*s) puts