一元稀疏多項(xiàng)式計(jì)算器數(shù)據(jù)結(jié)構(gòu)

1、院 系： 計(jì)算機(jī)科學(xué)學(xué)院 專 業(yè)： 軟件工程 年 級(jí)： 2013級(jí) 課程名稱： 數(shù)據(jù)結(jié)構(gòu) 姓 名： 韋宜（201321092034）指導(dǎo)教師： 宋中山 2015年 12 月 15日題目：設(shè)計(jì)一個(gè)一元稀疏多項(xiàng)式簡(jiǎn)單計(jì)算器班級(jí)：軟件工程1301 姓名：韋宜 學(xué)號(hào)：201321092034 完成日期：12月15日1、 需求分析問題描述：設(shè)計(jì)一個(gè)一元多項(xiàng)式加法器基本要求：輸入并建立多項(xiàng)式；(2)兩個(gè)多項(xiàng)式相加；(3)輸出多項(xiàng)式：n, c1, e1, c2, e2, cn , en, 其中，n是多項(xiàng)式項(xiàng)數(shù)，ci和ei分別是第 i 項(xiàng)的系數(shù)和指數(shù)，序列按指數(shù)降序排列。(4)計(jì)算多項(xiàng)式在x處的值；(5)求多

2、項(xiàng)式的導(dǎo)函數(shù)。軟件環(huán)境：Windows，UNIX，Linux等不同平臺(tái)下的Visual C+ 6.0硬件環(huán)境: 512MB內(nèi)存,80Gb硬盤,Pentium4 CPU,CRT顯示器。2、 概要分析本程序有五個(gè)函數(shù)：PolyNode *Input()(輸入函數(shù))；PolyNode *Deri(PolyNode *head)（求導(dǎo)函數(shù)）；PolyNode * Plus(PolyNode *A,PolyNode *B)（求和函數(shù)）；void Output(PolyNode*head)（輸出函數(shù)）；int main()（主函數(shù)）本程序可使用帶有附加頭結(jié)點(diǎn)的單鏈表來(lái)實(shí)現(xiàn)多項(xiàng)式的鏈表表示，每個(gè)鏈表結(jié)點(diǎn)表示

3、多項(xiàng)式的一項(xiàng)，命名為node，它包括兩個(gè)數(shù)據(jù)成員：系數(shù)coef和指數(shù)exp，他們都是公共數(shù)據(jù)成員，*next為指針域，用鏈表來(lái)表示多項(xiàng)式。適用于不定的多項(xiàng)式，特別是對(duì)于項(xiàng)數(shù)再運(yùn)算過程中動(dòng)態(tài)增長(zhǎng)的多項(xiàng)式，不存在存儲(chǔ)溢出的問題。其次，對(duì)于某些零系數(shù)項(xiàng)，在執(zhí)行加法運(yùn)算后不再是零系數(shù)項(xiàng)，這就需要在結(jié)果多項(xiàng)式中增添新的項(xiàng)；對(duì)于某些非零系數(shù)項(xiàng)，在執(zhí)行加法運(yùn)算后可能是零系數(shù)項(xiàng)，這就需要在結(jié)果多項(xiàng)式中刪去這些項(xiàng)，利用鏈表操作，可以簡(jiǎn)單的修改結(jié)點(diǎn)的指針以完成這種插入和刪除運(yùn)算（不像在順序方式中那樣，可能移動(dòng)大量數(shù)據(jù)項(xiàng)）運(yùn)行效率高。3、 詳細(xì)設(shè)計(jì)（1）主函數(shù)：int main()PolyNode *head_a,

4、*head_b;int choice;head_a=new PolyNode;head_a->next=NULL;do system("cls");/清屏函數(shù) Output(head_a); cout<<" _n" cout<<"|-1.輸入公式-|n" cout<<"|-2.求 導(dǎo)-|n" cout<<"|-3.兩式求和-|n" cout<<"|-4.退出程序-|n" cout<<" n

5、" cin>>choice; if (choice=1) head_a=Input(); else if (choice=2) head_a=Deri(head_a); /求導(dǎo) else if (choice=3) head_b=Input();head_a=Plus(head_a,head_b);/求和 else if (choice=4) break; else cout<<"輸入錯(cuò)誤，重新輸入：n"while(choice!=5);return 0;（2）由于此程序是二人合作完成，我在此程序中主要是完成求和和求導(dǎo)函數(shù)的設(shè)計(jì)。所以下面著

6、重介紹下求和函數(shù)和求導(dǎo)函數(shù)。PolyNode *Deri(PolyNode *head)（求導(dǎo)函數(shù)）：流程圖如下：NNYstart建立以head1為頭指針的空鏈表，A指向后一接點(diǎn)建立以head2為頭指針的空鏈表，p=head2q=B的第一個(gè)接點(diǎn)返回指針head1調(diào)用求和函數(shù)head1=head1+head2A指向后一接點(diǎn)q指向的接點(diǎn)與A指向的接點(diǎn)相乘，結(jié)果保存到head2后面，q指向后一接點(diǎn)A!=NULLq!=NULLYENDPolyNode* Mul(PolyNode*A,PolyNode *B) 求導(dǎo)函數(shù)部分代碼：PolyNode *Deri(PolyNode *head) /求導(dǎo)Poly

7、Node *p=head;while (p->next!=NULL)if(p->next->exp=0) p->next=NULL; /指數(shù)為零返回else p->next->coef*=p->next->exp; /系數(shù)乘以指數(shù)p->next->exp-; /指數(shù)減一p=p->next;return head;用于對(duì)輸入的多項(xiàng)式進(jìn)行求導(dǎo)，求導(dǎo)在鏈表內(nèi)進(jìn)行計(jì)算，即運(yùn)算完成鏈表的值改變，返回頭指針。PolyNode * Plus(PolyNode *A,PolyNode *B)（求和函數(shù)）：流程圖如下：startNYNYNYYNN

8、YNYNY建立鏈表head，p=head，兩頭指針A、B均指向各自的nextA、 B為空A的指數(shù)大于B的指數(shù)A、B的系數(shù)互為倒數(shù)AB指數(shù)相等B為空A為空p->next=NULL將A的當(dāng)前接點(diǎn)接到新鏈表后面，A后指A、B均后指將B接到p后面合并相同系數(shù)相同項(xiàng)，連接到新鏈表后面將A接到p后面將B的當(dāng)前接點(diǎn)接到新鏈表后面，B后指如果AB都為空返回頭指針ENDPolyNode*Plus(PolyNode*A,PolyNode *B) 本函數(shù)用于對(duì)多項(xiàng)式進(jìn)行加法計(jì)算，需要運(yùn)用存有兩個(gè)多項(xiàng)式的頭指針，前一頭指針可是前一計(jì)算的計(jì)算結(jié)果，也可是調(diào)用輸入函數(shù)，后一頭指針是調(diào)用輸入函數(shù)輸入的多項(xiàng)式的頭接點(diǎn)。

9、經(jīng)過計(jì)算得到一個(gè)新的鏈表，函數(shù)返回鏈表的頭指針。求和函數(shù)部分代碼PolyNode * Plus(PolyNode *A,PolyNode *B)/相加PolyNode *head,*p;head=new PolyNode;p=head;A=A->next;B=B->next; while(A!=NULL|B!=NULL)if(A=NULL) p->next=B; break; /如果A空，把B后面的所有接點(diǎn)接到p之后if(B=NULL) p->next=A; break; /如果B空，把A后面的所有接點(diǎn)接到p之后 if(A->exp=B->exp) /如果兩

10、指數(shù)數(shù)相等，相加if(A->coef+B->coef!=0) p->next=new PolyNode; p=p->next; p->exp=A->exp; p->coef=A->coef+B->coef;A=A->next;B=B->next; continue; /如果兩系數(shù)互為倒數(shù)，不保存，后指，繼續(xù)循環(huán)if(A->exp > B->exp) /A的指數(shù)大于B的指數(shù)p->next=new PolyNode;p=p->next;p->exp=A->exp;p->coef=A-&

11、gt;coef;A=A->next; continue; /將A的當(dāng)前接點(diǎn)接到新鏈表后面，A后指p->next=new PolyNode;p=p->next;p->exp=B->exp;p->coef=B->coef;B=B->next; /將B的當(dāng)前接點(diǎn)接到新鏈表后面，B后指if (A=NULL&&B=NULL) /如果A B 都為空p->next=NULL;return head; /返回頭指針（3）其他函數(shù)（同組的成員設(shè)計(jì)）#include <iostream>#include <process.h&

12、gt;using namespace std;typedef struct node float coef; /系數(shù) int exp; /指數(shù) struct node *next; /指針域 指向下一個(gè)系數(shù)不為0的子項(xiàng) PolyNode;PolyNode *Input() /輸入函數(shù)float c; /系數(shù)域int e; /指數(shù)域PolyNode *p,*q,*r,*head;cout<<"請(qǐng)輸入多項(xiàng)式:n"cout<<"形式：系數(shù)1 指數(shù)1 系數(shù)2 指數(shù)2 系數(shù)3 指數(shù)3.0 0：n"head=new PolyNode; /建立

13、頭接點(diǎn)p=head;p->next=NULL;for (;)cin>>c>>e;if(c=0&&e=0) break; /結(jié)束輸入if(c=0) continue; /從新輸入，不保存if(head->next=NULL) /輸入第一個(gè)接點(diǎn)p->next=new PolyNode;p=p->next;p->coef=c,p->exp=e;p->next=NULL;continue;p=head;while(p->next!=NULL && e<=p->next->exp)

14、p=p->next;/如果輸入的指數(shù)小于p的下一個(gè)接點(diǎn)，p向后指if (e=p->exp) p->coef+=c;continue;/如果相等，直接加上去，繼續(xù)循環(huán)q=new PolyNode;q->coef=c,q->exp=e;if (p->next!=NULL&&e>p->next->exp)/如果p的后繼接點(diǎn)的指數(shù)小于輸入的指數(shù)，插入到p的當(dāng)前接點(diǎn)之后r=p->next;p->next=q;q->next=r;continue;p->next=q;/如果輸入的值小于所有接點(diǎn)，接在最后一個(gè)接點(diǎn)之

15、后p=p->next; p->next=NULL;return head;輸出函數(shù)void Output(PolyNode*head) /輸出PolyNode*p;p=head->next;if(p=NULL) cout<<"當(dāng)前沒有公式或計(jì)算結(jié)果為0，請(qǐng)選1輸入！n" return;if(p!=NULL)cout<<"計(jì)算結(jié)果：n"cout<<p->coef<<"X"<<p->exp;p=p->next;while(p!=NULL)cou

16、t<<"+"<<p->coef<<"X"<<p->exp;p=p->next; cout<<endl;cout<<"如果想重新輸入公式，請(qǐng)選1輸入！nn"4、 調(diào)試分析與操作說明（1）當(dāng)程序運(yùn)行時(shí)，進(jìn)入主界面。如圖： 此時(shí)輸入1-4選擇操作（2）輸入1后按回車出現(xiàn)： 輸入1 2 3 4 5 6 0 0后按回車之后 會(huì)出現(xiàn)界面： （3）求導(dǎo)：輸入2求導(dǎo)后按回車會(huì)出現(xiàn)結(jié)果： 結(jié)果正確。（4）求和：如果進(jìn)入圖4.3后輸入3后按回車會(huì)出現(xiàn)界面： 圖4.5求和界面輸入2 2 4 4 6 6 0