一元稀疏多項(xiàng)式計(jì)算器實(shí)現(xiàn)(完整實(shí)現(xiàn)版-詳細(xì)源碼)(共17頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上1.5一元稀疏多項(xiàng)式計(jì)算器實(shí)習(xí)報(bào)告一、 需求分析 1輸入并建立多項(xiàng)式；2輸出多項(xiàng)式，輸出形式為整數(shù)序列：n，c1，e1，c2，e2，cn，en，其中n是多項(xiàng)式的項(xiàng)數(shù)，ci和ei分別是第i項(xiàng)的系數(shù)和指數(shù)，序列按指數(shù)降序排列；3多項(xiàng)式a和b相加，建立多項(xiàng)式ab；4多項(xiàng)式a和b相減，建立多項(xiàng)式ab；5多項(xiàng)式a和b相乘，建立多項(xiàng)式a×b；6計(jì)算多項(xiàng)式在x處的值；7求多項(xiàng)式P的導(dǎo)函數(shù)P'；8.多項(xiàng)式的輸出形式為類數(shù)學(xué)表達(dá)式；9.做出計(jì)算器的仿真界面；10. 測試數(shù)據(jù)：（1） (2x+5x8-3.1x11)+(7-5x8+11x9)=(-3.1x11+11x9+

2、2x+7)（2） (6x-3-x+4.4x2-1.2x9+1.2x9)-(-6x-3+5.4x2-x2+7.8x15 )=(-7.8x15-1.2x9+12x-3-x);（3）(1+x+x2+x3+x4+x5)+(-x3-x4)=(1+x+x2+x5);（4）(x+x3)+(-x-x3)=0（5）(x+x100)+(x100+x200)=(x+2x100+x200)（6）(x+x2+x3)+0=x+x2+x3（7）互換上述測試數(shù)據(jù)中的前后兩個多項(xiàng)式二、 概要設(shè)計(jì)1. 鏈表的抽象數(shù)據(jù)類型定義為：ADT LinkList 數(shù)據(jù)對象：D ai | aiElemSet, i=1,2,.,n, n0 數(shù)

3、據(jù)關(guān)系：R1 <ai-1, ai>|ai-1, aiD, i=2,.,n 基本操作： InitList(&L) 操作結(jié)果：構(gòu)造一個空的線性表L。 DestroyList(&L) 初始條件：線性表L已存在。 操作結(jié)果：銷毀線性表L。ClearList(*L) 初始條件：線性表L已存在。 操作結(jié)果：將線性表L重置為空表。 LocateElem(L, e, cmp() 初始條件：線性表L已存在，compare()是元素判定函數(shù)。 操作結(jié)果：返回L中第1個與e滿足關(guān)系cmp()的元素的位序。 若這樣的元素不存在，則返回值為0。 SetCurElem(&p, e) 初

4、始條件：線性表L已存在，且非空。操作結(jié)果：用元數(shù)e更新p所指結(jié)點(diǎn)中元數(shù)的值。GetCurElem(p)初始條件：線性表L已存在，且非空。操作結(jié)果：返回p所指結(jié)點(diǎn)中數(shù)據(jù)元數(shù)的值。InsFirst (&L, h, s) 初始條件：線性表L已存在，h結(jié)點(diǎn)在L中。 操作結(jié)果：在L的s所指結(jié)點(diǎn)插入在h結(jié)點(diǎn)之后，L的長度加1。 DelFirst (&L, h, q) 初始條件：線性表L已存在且非空，q結(jié)點(diǎn)在L中且不是尾結(jié)點(diǎn) 操作結(jié)果：刪除鏈表L中的h結(jié)點(diǎn)之后的結(jié)點(diǎn)q，L的長度減1。 MakeNode(&p, e)操作結(jié)果：創(chuàng)建了一個結(jié)點(diǎn)p，其data部分為e。FreeNode(&a

5、mp;p)初始條件：結(jié)點(diǎn)p存在且非空。操作結(jié)果：釋放結(jié)點(diǎn)p空間。Append(LinkList &L,Link s)初始條件：線性表L已存在。操作結(jié)果：s及s以后的結(jié)點(diǎn)鏈接到了原L之后，L的長度增加鏈上的結(jié)點(diǎn)數(shù)。ListEmpty(L)初始條件：線性表L已存在。操作結(jié)果：若線性鏈表L為空表，則返回TRUE,否則返回FALSE。GetHead(L)初始條件：線性表L已存在。操作結(jié)果：返回線性鏈表L中頭結(jié)點(diǎn)的位置。NextPos(L, p)初始條件：線性表L已存在。操作結(jié)果：返回p所指結(jié)點(diǎn)的直接后繼的位置，若沒后繼，則返回NULL。int cmp(a, b)初始條件：存在兩個元數(shù)。操作結(jié)果

6、：比較a，b的數(shù)值，分別返回-1，0，1。 ADT LinkList2.一元多項(xiàng)式的抽象數(shù)據(jù)類型定義為：ADT Polynomial數(shù)據(jù)對象：D ai | aiTermSet, i=1,2,.,m, m0 TermSet中的每個元素包含一個表示系數(shù)的實(shí)數(shù)和表示指數(shù)的整數(shù)數(shù)據(jù)關(guān)系：R1 <ai-1, ai>|ai-1, aiD, 且ai-1中的指數(shù)值<ai中的指數(shù)值，i=2，n基本操作：CreatPolyn（&P，m）操作結(jié)果：輸入m項(xiàng)的系數(shù)和指數(shù)，建立一元多項(xiàng)式P。DestroyPolyn（&P）初始條件：一元多項(xiàng)式P已存在。操作結(jié)果：銷毀一元多項(xiàng)式P。Add

7、Polyn（&Pa，&Pb）初始條件：一元多項(xiàng)式Pa和Pb已存在。操作結(jié)果：完成多項(xiàng)式相加運(yùn)算，即：Pa=Pa+Pb，并銷毀一元多項(xiàng)式Pb。SubtractPolyn(&Pa,&Pb)初始條件：一元多項(xiàng)式Pa和Pb已存在。操作結(jié)果：完成多項(xiàng)式相減運(yùn)算，即：Pa=Pa-Pb，并銷毀一元多項(xiàng)式Pb。MultiplyPolyn(&Pa,&Pb)初始條件：一元多項(xiàng)式Pa和Pb已存在。操作結(jié)果：完成多項(xiàng)式相乘運(yùn)算，即：Pa=Pa×Pb，并銷毀一元多項(xiàng)式Pb。DerivPolyn(&Pa)初始條件：一元多項(xiàng)式Pa已存在。操作結(jié)果：多項(xiàng)式求導(dǎo)

8、。CalPolyn(Pa , x)初始條件：一元多項(xiàng)式Pa已存在。操作結(jié)果：求多項(xiàng)式在x處的值。PrintPolyn(p, m) 初始條件：一元多項(xiàng)式p已存在，且已知多項(xiàng)式項(xiàng)數(shù)。 操作結(jié)果：打印輸出一元多項(xiàng)式p的項(xiàng)數(shù)、系數(shù)和指數(shù)。Expression(p, m)初始條件：一元多項(xiàng)式p已存在，且已知多項(xiàng)式項(xiàng)數(shù)。 操作結(jié)果：打印輸出一元多項(xiàng)式的類數(shù)學(xué)表達(dá)式。SortPolyn(&p)初始條件：一元多項(xiàng)式p已存在。 操作結(jié)果：對多項(xiàng)式p進(jìn)行排序ADT Polynomial3.本程序包含4個模塊：(1)主程序模塊：int main() 初始化； 接受命令； while（命令！=推出） 處理命令

9、； 接受命令；return 0;(2)一元多項(xiàng)式單元模塊實(shí)現(xiàn)一元多項(xiàng)式的抽象數(shù)據(jù)類型；（3）鏈表單元模塊實(shí)現(xiàn)鏈表的抽象數(shù)據(jù)類型；(4)結(jié)點(diǎn)結(jié)構(gòu)單元模塊定義鏈表的節(jié)點(diǎn)結(jié)構(gòu)。各模塊之間的調(diào)用關(guān)系如下：主程序模塊 一元多項(xiàng)式單元模塊 鏈表單元模塊結(jié)點(diǎn)結(jié)構(gòu)單元模塊三、 詳細(xì)設(shè)計(jì)1.設(shè)計(jì)好的數(shù)據(jù)類型：typedef struct /項(xiàng)的表示，多項(xiàng)式的項(xiàng)作為Linklist的數(shù)據(jù)元素float coef; /系數(shù)int expn;/指數(shù) term, ElemType;/兩個類名：term用于本ADT，ElemType為Linklist的數(shù)據(jù)對象名typedef struct LNode /結(jié)點(diǎn)類型 Ele

10、mType data; struct LNode *next; *Link, *Position;typedef struct/鏈表類型Link head,tail;/分別指向線性鏈表中的頭結(jié)點(diǎn)和最后一個結(jié)點(diǎn) int len;/指示線性鏈表中數(shù)據(jù)個數(shù) LinkList;typedef LinkList polynomial;/基于帶頭結(jié)點(diǎn)的線性鏈表定義的多項(xiàng)式數(shù)據(jù)類型2.基于鏈表、結(jié)點(diǎn)的操作(部分偽碼如下)/ 分配由p指向值為e的結(jié)點(diǎn),并返回OK,若分配失敗,則返回ERROR。Status MakeNode(Link &p, ElemType e);/釋放p所指結(jié)點(diǎn)void FreeN

11、ode(Link &p);/構(gòu)造一個空的線性鏈表LStatus InitList(LinkList &L); L.head=L.tail=(Link)malloc(sizeof(LNode); L.len=0; L.head->next=L.tail->next=NULL; return OK;/ 返回線性表L中頭結(jié)點(diǎn)的位置。Position GetHead(LinkList &L);/已知p指向線性鏈表L中的一個結(jié)點(diǎn)，返回p所指結(jié)點(diǎn)的直接后驅(qū)的位置/若無后繼，返回NULLPosition Nextpos(LinkList &L,Link p);/已

12、知p指向線性表L中的一個結(jié)點(diǎn),返回p所指結(jié)點(diǎn)中數(shù)據(jù)元素的值。ElemType GetCurElem(Link p);/已知p指向線性鏈表L中的一個結(jié)點(diǎn),用e更新p所指結(jié)點(diǎn)中數(shù)據(jù)元素的值。Status SetCurElem(Link &p,float e); /已知h指向線性鏈表的某個結(jié)點(diǎn),將q所指的結(jié)點(diǎn)插入在h之后。Status InsFirst(Link h,Link q); s->next=h->next; h->next=s; L.len+; if(!s->next) L.tail=s; return OK;/已知h指向線性鏈表的頭結(jié)點(diǎn),刪除線性鏈表第一個

13、指結(jié)點(diǎn)并以q返回Status DelFirst(Link h,Link &q);/若線性鏈表L為空,則返回TRUE,否則返回FALSE。Status ListEmpty(LinkList L); if(L.head=L.tail=NULL) return TRUE; else return FALSE;/將指針s所指的一連串結(jié)點(diǎn)連接在線性表L的最后一個結(jié)點(diǎn)之后,并改變鏈表L的尾指針指向新的尾結(jié)點(diǎn)。Status Append(polynomial &L,Link s); i=0; q=s; while(s) /找到新的tail，計(jì)數(shù)s長度 p=s; s=s->next; i

14、+; L.tail->next=q; L.tail=p; L.len+=i; return OK;/判斷已知鏈表中，是否存在相同的元素e，若存在返回TURE，且q指示L中第一個與e相同的結(jié)點(diǎn)元素；/否則返回FALSE,并q指示L中第一個稍大于e的元素的直接前驅(qū)的位置Status LocateElem(LinkList L,ElemType e,Position &q); p=L.head; while(p->next) s=p; p=p->next; m=p->data; if(cmp(e,m )=0) q=p; return TRUE; q=p; return

15、 FALSE;/整表刪除void ClearList(LinkList &L); if(L.head!=L.tail) p=q=L.head->next; L.head->next=NULL; while(p!=L.tail) p=q->next; free(q); q=p; free(q); L.tail=L.head; L.len=0; return OK;/依a的指數(shù)值<（或=）(或>）b的指數(shù)數(shù)值，分別返回-1，0，+1int cmp(term a, term b) ; if(a.expn<b.expn) return -1; if(a.ex

16、pn=b.expn) return 0; if(a.expn>b.expn) return 1;3.基于多項(xiàng)式的操作（部分偽碼如下）/輸入m項(xiàng)的系數(shù)和指數(shù)，建立表示一元多項(xiàng)式的有序鏈表Pvoid CreatPolyn(polynomial &p,int m);InitList(p);h=GetHead(p);e.coef=0.0;e.expn=-1;SetCurElem(h,e);for(int i=1;i<=m;i+) cout<<"請輸入第"<<i<<"項(xiàng)的系數(shù)和指數(shù)（按指數(shù)降序）：" cin&

17、gt;>e.coef>>e.expn; cout<<endl; if(!LocateElem(p,e,q)/當(dāng)前鏈表中不存在該指數(shù)項(xiàng) if(MakeNode(s,e) InsFirst(p,q,s);/生成節(jié)點(diǎn)并插入鏈表 else return; else q->data.coef+=e.coef; +c; m=m-c;/銷毀一元多項(xiàng)式Pvoid DestroyPolyn(polynomial &p); while(p.head ->next!=NULL) k=p.head; p.head =p.head ->next; free(k);

18、 free(&p);/打印輸出一元多項(xiàng)式Pvoid PrintPolyn(polynomial p);ha=GetHead(p);cout<<m<<', ' for(int i=1;i<=m;i+) qa=NextPos(p,ha); e=GetCurElem(qa); cout<<e.coef<<','<<e.expn<<', ' ha=qa; cout<<endl;/打印輸出一元多項(xiàng)式的類數(shù)學(xué)表達(dá)式void Expression(polynomi

19、al p,int m);/完成多項(xiàng)式的相加運(yùn)算，即：Pa=Pa+Pb，并銷毀一元多項(xiàng)式Pbvoid AddPolyn(polynomial &Pa ,polynomial &Pb); ha = GetHead(Pa);hb = GetHead(Pb);/ha和hb分別指向pa和pb的頭節(jié)點(diǎn)qa = NextPos(Pa, ha);qb = NextPos(Pb, hb);while (qa&&qb) /qa，qb均非空a = GetCurElem(qa);b = GetCurElem(qb);switch (cmp(a, b)/a和b為兩表比較元數(shù)case -1

20、: /a的指數(shù)小于b的指數(shù)DelFirst(Pb, hb, qb);InsFirst(Pa, ha, qb);qb = NextPos(Pb, hb);ha = NextPos(Pa, ha);break;case 0: /a的指數(shù)等于b的指數(shù)a.coef = a.coef + b.coef;if (a.coef != 0.0) /修改多項(xiàng)式Pa中當(dāng)前結(jié)點(diǎn)的系數(shù)SetCurElem(qa, a);ha = qa;else /刪除多項(xiàng)式Pa中當(dāng)前結(jié)點(diǎn)DelFirst(Pa, ha, qa);FreeNode(qa);DelFirst(Pb, hb, qb);FreeNode(qb);qb=Nex

21、tPos(Pb,hb);qa=NextPos(Pa,ha);break;case 1: /a的指數(shù)大于b的指數(shù)ha = qa;qa = NextPos(Pa, qa);break;if (!ListEmpty(Pb) Append(Pa, qb);/鏈接Pb中剩余結(jié)點(diǎn)FreeNode(hb);/釋放Pb的結(jié)點(diǎn)/完成多項(xiàng)式的相減運(yùn)算，即：Pa=Pa-Pb，并銷毀一元多項(xiàng)式Pbvoid SubtractPolyn(polynomial &Pa ,polynomial &Pb);/完成多項(xiàng)式的相減運(yùn)算，即：Pa=Pa×Pb，并銷毀一元多項(xiàng)式Pbvoid MultiplyPo

22、lyn(polynomial &Pa ,polynomial &Pb); InitList(Pc); qa=GetHead(Pa); qa=qa->next; hc=GetHead(Pc); while(qa) a=GetCurElem(qa); qb=GetHead(Pb); qb=qb->next; while(qb) b=GetCurElem(qb); c.coef=a.coef*b.coef; c.expn=a.expn+b.expn; MakeNode(qc,c); InsFirst(Pc,hc,qc); hc=NextPos(Pc,hc); qc=Nex

23、tPos(Pc,qc); qb=qb->next; qa=qa->next; DestroyPolyn(Pb); ClearList(Pa); Pa.head=Pc.head; Pa.tail=Pc.tail; Pa.len=Pc.len;/計(jì)算多項(xiàng)式在x處的值double Evaluation(double x, polynomial p);/計(jì)算多項(xiàng)式P的導(dǎo)函數(shù)P'void Derivative( polynomial &p ); InitList(Pb); qa=GetHead(Pa); qa=qa->next; hb=GetHead(Pb); whil

24、e(qa) a=GetCurElem(qa); b.coef=a.coef*a.expn; b.expn=a.expn-1; MakeNode(qb,b); InsFirst(Pb,hb,qb); hb=NextPos(Pb,hb); qb=NextPos(Pb,qb); qa=qa->next; qb=NULL; ClearList(Pa); Pa.head=Pb.head; Pa.tail=Pb.tail; Pa.len=Pb.len;4.主函數(shù)和其他函數(shù)的偽碼算法int main() Initialization();ReadCommand(cmd);while (cmd != &

25、#39;q' && cmd != 'Q')Interpret(cmd);display();ReadCommand(cmd); return 0;void Initialization()pre_cmd = ' 'cmd = ' 'InitList(La);InitList(Lb);void display()system("cls"); /清屏在屏幕上方顯示操作命令清單：CreatePolynomial_a ->1 CreatePolynomial_b ->2 a+b ->'

26、 a-b >'' a*b ->* Derivation of a ->d Calculate a in x ->c Quit ->q 在屏幕下方顯示操作命令提示框：Enter a operation code(1,2,+,_,*,c,d OR q): "void ReadCommand(char &cmd)/讀入操作命令符 顯示檢入操作命令符的提示信息；dodisplay();cin >> cmd; while (!strchr(cmdsets, cmd);void Interpret(char cmd) /解釋執(zhí)行操

27、作命令cmdswitch (cmd)case '1':ClearList(La);cout << "請輸入第一個一元多項(xiàng)式的項(xiàng)數(shù)"cin >> n; cout << endl;CreatPolyn(La, n);/輸入多項(xiàng)式SortPolyn(La);break;case '2':ClearList(Lb);cout << endl << "請輸入第二個一元多項(xiàng)式的項(xiàng)數(shù)"cin >> m; cout << endl;CreatPolyn(L

28、b, m);/輸入多項(xiàng)式SortPolyn(Lb);break;case '+':cout << endl << "兩多項(xiàng)式相加的結(jié)果："AddPolyn(La, Lb);PrintPolyn(La, La.len);Expression(La,La.len);getchar();getchar();break;case '-':cout << endl << "兩多項(xiàng)式相減的結(jié)果："SubtractPolyn(La, Lb);PrintPolyn(La, La.len);E

29、xpression(La,La.len);getchar();getchar();break;case '*':cout << endl << "兩多項(xiàng)式相乘的結(jié)果："MultiplyPolyn(La, Lb);PrintPolyn(La, La.len);Expression(La,La.len);getchar();getchar();break;case 'c':case 'C':cout << "請輸入x的值" << endl;cin >>

30、 x;cout << "多項(xiàng)式a在" << x << "處的值為" << CalPolyn(La, x);getchar();getchar();break;case 'd':case 'D':DerivPolyn(La);cout << "求導(dǎo)結(jié)果為"PrintPolyn(La, La.len);Expression(La,La.len);getchar();getchar();default:cout << "輸入錯誤" << endl; 5.函數(shù)的調(diào)用關(guān)系圖反映了演示程序的層次結(jié)構(gòu)四、 調(diào)試分析1. 一開始寫求導(dǎo)部分代碼時(shí)沒有考慮常數(shù)項(xiàng)求