1、1.5一元稀疏多項式計算器實習報告一、 需求分析 1輸入并建立多項式；2輸出多項式，輸出形式為整數序列：n，c1，e1，c2，e2，cn，en，其中n是多項式的項數，ci和ei分別是第i項的系數和指數，序列按指數降序排列；3多項式a和b相加，建立多項式ab；4多項式a和b相減，建立多項式ab；5多項式a和b相乘，建立多項式a×b；6計算多項式在x處的值；7求多項式P的導函數P'；8.多項式的輸出形式為類數學表達式；9.做出計算器的仿真界面；10. 測試數據：（1） (2x+5x8-3.1x11)+(7-5x8+11x9)=(-3.1x11+11x9+2x+7)（2） (6x-

2、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）互換上述測試數據中的前后兩個多項式二、 概要設計1. 鏈表的抽象數據類型定義為：ADT LinkList 數據對象：D ai | aiElemSet, i=1,2,.,n, n0 數據關系：R1 <ai

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

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

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

6、回-1，0，1。 ADT LinkList2.一元多項式的抽象數據類型定義為：ADT Polynomial數據對象：D ai | aiTermSet, i=1,2,.,m, m0 TermSet中的每個元素包含一個表示系數的實數和表示指數的整數數據關系：R1 <ai-1, ai>|ai-1, aiD, 且ai-1中的指數值<ai中的指數值，i=2，n基本操作：CreatPolyn（&P，m）操作結果：輸入m項的系數和指數，建立一元多項式P。DestroyPolyn（&P）初始條件：一元多項式P已存在。操作結果：銷毀一元多項式P。AddPolyn（&Pa

7、，&Pb）初始條件：一元多項式Pa和Pb已存在。操作結果：完成多項式相加運算，即：Pa=Pa+Pb，并銷毀一元多項式Pb。SubtractPolyn(&Pa,&Pb)初始條件：一元多項式Pa和Pb已存在。操作結果：完成多項式相減運算，即：Pa=Pa-Pb，并銷毀一元多項式Pb。MultiplyPolyn(&Pa,&Pb)初始條件：一元多項式Pa和Pb已存在。操作結果：完成多項式相乘運算，即：Pa=Pa×Pb，并銷毀一元多項式Pb。DerivPolyn(&Pa)初始條件：一元多項式Pa已存在。操作結果：多項式求導。CalPolyn(Pa

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

9、 0;(2)一元多項式單元模塊實現一元多項式的抽象數據類型；（3）鏈表單元模塊實現鏈表的抽象數據類型；(4)結點結構單元模塊定義鏈表的節點結構。各模塊之間的調用關系如下：主程序模塊 一元多項式單元模塊 鏈表單元模塊結點結構單元模塊三、 詳細設計1.設計好的數據類型：typedef struct /項的表示，多項式的項作為Linklist的數據元素float coef; /系數int expn;/指數 term, ElemType;/兩個類名：term用于本ADT，ElemType為Linklist的數據對象名typedef struct LNode /結點類型 ElemType data; s

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

11、;p);/構造一個空的線性鏈表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中頭結點的位置。Position GetHead(LinkList &L);/已知p指向線性鏈表L中的一個結點，返回p所指結點的直接后驅的位置/若無后繼，返回NULLPosition Nextpos(LinkList &L,Link p);/已知p指向線性表L中的一個結

12、點,返回p所指結點中數據元素的值。ElemType GetCurElem(Link p);/已知p指向線性鏈表L中的一個結點,用e更新p所指結點中數據元素的值。Status SetCurElem(Link &p,float e); /已知h指向線性鏈表的某個結點,將q所指的結點插入在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指向線性鏈表的頭結點,刪除線性鏈表第一個指結點并以q返回Statu

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

14、;next=q; L.tail=p; L.len+=i; return OK;/判斷已知鏈表中，是否存在相同的元素e，若存在返回TURE，且q指示L中第一個與e相同的結點元素；/否則返回FALSE,并q指示L中第一個稍大于e的元素的直接前驅的位置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 FALSE;/整表刪除v

15、oid 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的指數值<（或=）(或>）b的指數數值，分別返回-1，0，+1int cmp(term a, term b) ; if(a.expn<b.expn) return -1; if(a.expn=b.expn) re

16、turn 0; if(a.expn>b.expn) return 1;3.基于多項式的操作（部分偽碼如下）/輸入m項的系數和指數，建立表示一元多項式的有序鏈表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<<"項的系數和指數（按指數降序）：" cin>>e.coef

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

18、;/打印輸出一元多項式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;/打印輸出一元多項式的類數學表達式void Expression(polynomial p,int m);/

19、完成多項式的相加運算，即：Pa=Pa+Pb，并銷毀一元多項式Pbvoid AddPolyn(polynomial &Pa ,polynomial &Pb); ha = GetHead(Pa);hb = GetHead(Pb);/ha和hb分別指向pa和pb的頭節點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為兩表比較元數case -1: /a的指數小于b的指數

20、DelFirst(Pb, hb, qb);InsFirst(Pa, ha, qb);qb = NextPos(Pb, hb);ha = NextPos(Pa, ha);break;case 0: /a的指數等于b的指數a.coef = a.coef + b.coef;if (a.coef != 0.0) /修改多項式Pa中當前結點的系數SetCurElem(qa, a);ha = qa;else /刪除多項式Pa中當前結點DelFirst(Pa, ha, qa);FreeNode(qa);DelFirst(Pb, hb, qb);FreeNode(qb);qb=NextPos(Pb,hb);q

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

22、l &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=NextPos(Pc,qc);

23、qb=qb->next; qa=qa->next; DestroyPolyn(Pb); ClearList(Pa); Pa.head=Pc.head; Pa.tail=Pc.tail; Pa.len=Pc.len;/計算多項式在x處的值double Evaluation(double x, polynomial p);/計算多項式P的導函數P'void Derivative( polynomial &p ); InitList(Pb); qa=GetHead(Pa); qa=qa->next; hb=GetHead(Pb); while(qa) a=GetCu

24、rElem(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.主函數和其他函數的偽碼算法int main() Initialization();ReadCommand(cmd);while (cmd != 'q' &a

25、mp;& 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 ->' a-b >'

26、;' 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) /解釋執行操作命令cmdswitch

27、(cmd)case '1':ClearList(La);cout << "請輸入第一個一元多項式的項數"cin >> n; cout << endl;CreatPolyn(La, n);/輸入多項式SortPolyn(La);break;case '2':ClearList(Lb);cout << endl << "請輸入第二個一元多項式的項數"cin >> m; cout << endl;CreatPolyn(Lb, m);/輸入多項式S

28、ortPolyn(Lb);break;case '+':cout << endl << "兩多項式相加的結果："AddPolyn(La, Lb);PrintPolyn(La, La.len);Expression(La,La.len);getchar();getchar();break;case '-':cout << endl << "兩多項式相減的結果："SubtractPolyn(La, Lb);PrintPolyn(La, La.len);Expression(La,

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

30、lt; "多項式a在" << x << "處的值為" << CalPolyn(La, x);getchar();getchar();break;case 'd':case 'D':DerivPolyn(La);cout << "求導結果為"PrintPolyn(La, La.len);Expression(La,La.len);getchar();getchar();default:cout << "輸入錯誤" << endl; 5.函數的調用關系圖反映了演示程序的層次結構四、 調試分析1. 一開始寫求導部分代碼時沒有