數(shù)據(jù)結構實驗報告-一元多項式

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

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

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

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

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

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

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

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

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

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依次輸入呦 個非零項(每項前一個為系數(shù)，后

11、一個為指數(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門二二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個一元多項式的項數(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個一元多項式的項數(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個一元多項式的項數(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元多項式計算n ”)；printf('fttt ()()()()()()00()()()()()()()0()()()()()()()0()()()()()()n,r): printf(,rttt # 王偉 #n")； puts(,fn輸入1個

25、一元多項式的項數(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,請重新輸入! ,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 請重新輸入！ ”); goto q；六、程序運行效果圖與說明0000000000000000000000一元多項式計算0000000000