實(shí)習(xí)一 【一元稀疏多項(xiàng)式簡單計算器】.doc

實(shí)習(xí)一1 需求分析：【問題描述】：設(shè)計一個一元稀疏多項(xiàng)式簡單計算器?！净疽蟆浚海?）輸入并建立兩個多項(xiàng)式；（2）多項(xiàng)式a與b相加，建立和多項(xiàng)式c；（3）多項(xiàng)式a與b相減，建立和多項(xiàng)式d；（4）輸出多項(xiàng)式a,b,c,d。輸出格式：比如多項(xiàng)式a為： ，其中，和分別為第i項(xiàng)的系數(shù)和指數(shù)，且各項(xiàng)按指數(shù)的升冪排列，即0?！鹃_發(fā)環(huán)境】：系統(tǒng)：windows7編程軟件：VC+6.0 2.設(shè)計：在數(shù)學(xué)上，一個n次一元多項(xiàng)式可表示為=+它由(n+1)個系數(shù)序列、唯一確定。因此，在計算機(jī)中，可用一個線性表P表示：P=(,)其中，代表中的i次項(xiàng)系數(shù)。一般情況下，一元n次多項(xiàng)式寫成：其中，0且,記作線性表P=（(,),(,)()）其中，元素為二元組（系數(shù)，指數(shù)）多項(xiàng)式的單鏈表示意圖:圖示分別為多項(xiàng)式A(x)=7+3x+9x8+5x17B(x)=8x+22x7-9x8 兩個多項(xiàng)式相加運(yùn)算規(guī)則：兩個多項(xiàng)式中所有指數(shù)相同的項(xiàng)的對應(yīng)系數(shù)相加，若和不為零，則構(gòu)成“和多項(xiàng)式”中的一項(xiàng)；所有指數(shù)不相同的項(xiàng)均復(fù)制到“和多項(xiàng)式”中。 兩個多項(xiàng)式相減運(yùn)算規(guī)則：兩個多項(xiàng)式中所有指數(shù)相同的項(xiàng)對應(yīng)系數(shù)相減，若差不為零，則構(gòu)成“減多項(xiàng)式”中的一項(xiàng)；對于指數(shù)不同的項(xiàng)，A中項(xiàng)復(fù)制到“減多項(xiàng)式”中，B中各項(xiàng)符號變化（原來為“+”的項(xiàng)符號變?yōu)椤?”；為“-”的項(xiàng)符號變?yōu)椤?”）復(fù)制到“減多項(xiàng)式”中。模塊圖：具體思想：設(shè)p和q分別指示多項(xiàng)式A和B中某一結(jié)點(diǎn)，當(dāng)p和q均非空時，比較p-exp與q-exp：若p-expexp，加法則p所指結(jié)點(diǎn)是“和多項(xiàng)式”中的一項(xiàng)，令指針p后移；減法則p所指結(jié)點(diǎn)是“減多項(xiàng)式”中的一項(xiàng)，令指針p后移。若p-expq-exp，加法則q所指結(jié)點(diǎn)是“和多項(xiàng)式”中的一項(xiàng)，將結(jié)點(diǎn)q插入在結(jié)點(diǎn)p之前，且令指針q在原來的鏈表上后移；減法則將q-coef=-q-coef,將q其插入結(jié)點(diǎn)p之前，且令指針q在原來的鏈表上后移。若p-exp=q-exp，加法則將兩個結(jié)點(diǎn)中的系數(shù)相加，當(dāng)和不為零時修改結(jié)點(diǎn)p的系數(shù)域，釋放q結(jié)點(diǎn)；若和為零，則和多項(xiàng)式中無此項(xiàng)，從A中刪去p結(jié)點(diǎn)，同時釋放p和q結(jié)點(diǎn)。減法則將兩個結(jié)點(diǎn)中的系數(shù)相減，當(dāng)和不為零時修改結(jié)點(diǎn)p的系數(shù)域，釋放q結(jié)點(diǎn)；若和為零，則和多項(xiàng)式中無此項(xiàng)，從A中刪去p結(jié)點(diǎn)，同時釋放p和q結(jié)點(diǎn)。if (q=null) A即為“和多項(xiàng)式”結(jié)果（加法）；A即為“減多項(xiàng)式”結(jié)果（減法）。if (p=null)（加法）將剩余的q表全部鏈接至原A最后一個結(jié)點(diǎn)的后繼；（減法）將剩余的q并且令q-coef=-q-coef全部鏈接至原A最后一個結(jié)點(diǎn)的后繼。其中結(jié)點(diǎn)結(jié)構(gòu)體定義如下：typedef struct Linklistomial float coef; int expn; struct Linklistomial *next;*Linklist;建立鏈表函數(shù)如下：void Insert(Linklist p,Linklist h) if(p-coef=0) free(p);/系數(shù)為0的話釋放結(jié)點(diǎn) else Linklist q1,q2; q1=h; q2=h-next; while(q2&p-expnq2-expn) /查找插入位置 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ù)為新時將結(jié)點(diǎn)插入 p-next=q2; q1-next=p; Linklist CreateLinklist(Linklist head,int m) /建立一個頭指針為head、項(xiàng)數(shù)為m的一元多項(xiàng)式 int i; Linklist p; head=(Linklist)malloc(sizeof(struct Linklistomial); head-next=NULL; for(i=0;icoef,&p-expn); Insert(p,head); /調(diào)用Insert函數(shù)插入結(jié)點(diǎn) return head;3. 調(diào)試分析1.一元稀疏多項(xiàng)式計算器在調(diào)試時，問題主要出現(xiàn)在多項(xiàng)式相加和相減后所建立的多項(xiàng)式，將其輸出時，符號和系數(shù)的錯誤,即PrintLinklist函數(shù)有問題。在進(jìn)行相加減時要考慮第一項(xiàng)的系數(shù)，第一項(xiàng)的系數(shù)為正數(shù)時不需要+，而為負(fù)數(shù)數(shù)時，則需要加上，系數(shù)為零時，將其釋放掉；系數(shù)為1時，也不需要將其顯示出來。經(jīng)過反復(fù)調(diào)試，最終解決了這些問題。 2. 算法的時空分析：對多項(xiàng)式進(jìn)行加減運(yùn)算的空間復(fù)雜度和時間復(fù)雜度都是O(n)。4.用戶手冊運(yùn)行程序后，上面會提示你輸入所建多項(xiàng)式a的項(xiàng)數(shù)，每次輸入兩個數(shù)，一個為系數(shù)，另一個為指數(shù)，多項(xiàng)式a建立完成后，然后再建多項(xiàng)式b，最后出現(xiàn)一個相當(dāng)于菜單的框，輸入前面的字母就會顯示所得結(jié)果。5.測試結(jié)果6.源代碼.cal.h.typedef struct Linklistomial float coef; int expn; struct Linklistomial *next;*Linklist;void Insert(Linklist p,Linklist h) if(p-coef=0) free(p);/系數(shù)為0的話釋放結(jié)點(diǎn) else Linklist q1,q2; q1=h; q2=h-next; while(q2&p-expnq2-expn) /查找插入位置 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ù)為新時將結(jié)點(diǎn)插入 p-next=q2; q1-next=p; Linklist CreateLinklist(Linklist head,int m) /建立一個頭指針為head、項(xiàng)數(shù)為m的一元多項(xiàng)式 int i; Linklist p; head=(Linklist)malloc(sizeof(struct Linklistomial); head-next=NULL; for(i=0;icoef,&p-expn); Insert(p,head); /調(diào)用Insert函數(shù)插入結(jié)點(diǎn) return head;void DestroyLinklist(Linklist p) /銷毀多項(xiàng)式p Linklist q1,q2; q1=p-next; q2=q1-next; while(q1-next) free(q1); q1=q2; q2=q2-next; void PrintLinklist(Linklist p) Linklist q=p-next; int flag=1; /項(xiàng)數(shù)計數(shù)器 if(!q) /若多項(xiàng)式為空，輸出0printf(0); printf(n); while(q) if(q-coef0&flag!=1) printf(+); /系數(shù)大于0且不是第一項(xiàng) if(q-coef!=1&q-coef!=-1) /系數(shù)非1或-1的普通情況 printf(%g,q-coef); if(q-expn=1) printf(X); else if(q-expn) printf(X%d,q-expn); else if(q-coef=1) if(!q-expn)printf(1); else if(q-expn=1) printf(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+; printf(n);int compare(Linklist a,Linklist b) if(a&b) if(!a|a-expnexpn) return 1; else if(!b|a-expnb-expn) return -1; else return 0; else if(!a&b) return -1;/a多項(xiàng)式已空，但b多項(xiàng)式非空 else return 1;/b多項(xiàng)式已空，但a多項(xiàng)式非空Linklist AddLinklist(Linklist pa,Linklist pb)/求解并建立多項(xiàng)式a+b，返回其頭指針 Linklist qa=pa-next; Linklist qb=pb-next; Linklist headc,hc,qc; hc=(Linklist)malloc(sizeof(struct Linklistomial);/建立頭結(jié)點(diǎn) hc-next=NULL; headc=hc; while(qa|qb) qc=(Linklist)malloc(sizeof(struct Linklistomial); switch(compare(qa,qb) 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; if(qc-coef!=0) qc-next=hc-next; hc-next=qc; hc=qc; else free(qc);/當(dāng)相加系數(shù)為0時，釋放該結(jié)點(diǎn) return headc;Linklist SubLinklist(Linklist pa,Linklist pb)/求解并建立多項(xiàng)式a-b，返回其頭指針 Linklist qa=pa-next; Linklist qb=pb-next; Linklist headd,hd,qd; hd=(Linklist)malloc(sizeof(struct Linklistomial);/建立頭結(jié)點(diǎn) hd-next=NULL; headd=hd; while(qa|qb) qd=(Linklist)malloc(sizeof(struct Linklistomial); switch(compare(qa,qb) case 1: qd-coef=qa-coef; qd-expn=qa-expn; qa=qa-next; break; case 0: qd-coef=qa-coef-qb-coef; qd-expn=qa-expn; qa=qa-next; qb=qb-next; break; case -1: qd-coef=-qb-coef; qd-expn=qb-expn; qb=qb-next; break; if(qd-coef!=0) qd-next=hd-next; hd-next=qd; hd=qd; else free(qd);/當(dāng)相加系數(shù)為0時，釋放該結(jié)點(diǎn) return headd;.main.cpp.#include#include#includecal.h#define maxlen 10#define large 999void main() int m,n,a; char flag; Linklist pa=0,pb=0,pc; printf( 歡迎使用多項(xiàng)式操作程序nn); printf(請輸入a的項(xiàng)數(shù):); scanf(%d,&m); pa=CreateLinklist(pa,m);/建立多項(xiàng)式a printf(請輸入b的項(xiàng)數(shù):); scanf(%d,&n); pb=CreateLinklist(pb,n);/建立多項(xiàng)式 /輸出菜單 printf( *n); printf( * 多項(xiàng)式操作程序 *n); printf( * *n); printf( * A:輸出多項(xiàng)式a B:輸出多項(xiàng)式b *n); printf( * *n); printf( * C: 輸出a+b D:輸出a-b *n); printf( * *n); printf( * E: 返回主菜單 *n);printf( * *n); printf( *n); while(a) printf(n請選擇操作：); scanf( %c,&flag); switch(flag) caseA: casea: printf(n 多項(xiàng)式a=); PrintLinklist(pa); break; caseB: caseb: printf(n 多項(xiàng)式b=); PrintLinkl