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

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

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

3、多項式的一項，命名為node，它包括兩個數(shù)據(jù)成員：系數(shù)coef和指數(shù)exp，他們都是公共數(shù)據(jù)成員，*next為指針域，用鏈表來表示多項式。適用于不定的多項式，特別是對于項數(shù)再運算過程中動態(tài)增長的多項式，不存在存儲溢出的問題。其次，對于某些零系數(shù)項，在執(zhí)行加法運算后不再是零系數(shù)項，這就需要在結(jié)果多項式中增添新的項；對于某些非零系數(shù)項，在執(zhí)行加法運算后可能是零系數(shù)項，這就需要在結(jié)果多項式中刪去這些項，利用鏈表操作，可以簡單的修改結(jié)點的指針以完成這種插入和刪除運算（不像在順序方式中那樣，可能移動大量數(shù)據(jù)項）運行效率高。3、 詳細設(shè)計（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.求 導-|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); /求導 else if (choice=3) head_b=Input();head_a=Plus(head_a,head_b);/求和 else if (choice=4) break; else cout<<"輸入錯誤，重新輸入：n"while(choice!=5);return 0;（2）由于此程序是二人合作完成，我在此程序中主要是完成求和和求導函數(shù)的設(shè)計。所以下面著

6、重介紹下求和函數(shù)和求導函數(shù)。PolyNode *Deri(PolyNode *head)（求導函數(shù)）：流程圖如下：NNYstart建立以head1為頭指針的空鏈表，A指向后一接點建立以head2為頭指針的空鏈表，p=head2q=B的第一個接點返回指針head1調(diào)用求和函數(shù)head1=head1+head2A指向后一接點q指向的接點與A指向的接點相乘，結(jié)果保存到head2后面，q指向后一接點A!=NULLq!=NULLYENDPolyNode* Mul(PolyNode*A,PolyNode *B) 求導函數(shù)部分代碼：PolyNode *Deri(PolyNode *head) /求導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;用于對輸入的多項式進行求導，求導在鏈表內(nèi)進行計算，即運算完成鏈表的值改變，返回頭指針。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的當前接點接到新鏈表后面，A后指A、B均后指將B接到p后面合并相同系數(shù)相同項，連接到新鏈表后面將A接到p后面將B的當前接點接到新鏈表后面，B后指如果AB都為空返回頭指針ENDPolyNode*Plus(PolyNode*A,PolyNode *B) 本函數(shù)用于對多項式進行加法計算，需要運用存有兩個多項式的頭指針，前一頭指針可是前一計算的計算結(jié)果，也可是調(diào)用輸入函數(shù)，后一頭指針是調(diào)用輸入函數(shù)輸入的多項式的頭接點。

9、經(jīng)過計算得到一個新的鏈表，函數(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后面的所有接點接到p之后if(B=NULL) p->next=A; break; /如果B空，把A后面的所有接點接到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的當前接點接到新鏈表后面，A后指p->next=new PolyNode;p=p->next;p->exp=B->exp;p->coef=B->coef;B=B->next; /將B的當前接點接到新鏈表后面，B后指if (A=NULL&&B=NULL) /如果A B 都為空p->next=NULL;return head; /返回頭指針（3）其他函數(shù)（同組的成員設(shè)計）#include <iostream>#include <process.h&

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

13、頭接點p=head;p->next=NULL;for (;)cin>>c>>e;if(c=0&&e=0) break; /結(jié)束輸入if(c=0) continue; /從新輸入，不保存if(head->next=NULL) /輸入第一個接點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的下一個接點，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的后繼接點的指數(shù)小于輸入的指數(shù)，插入到p的當前接點之后r=p->next;p->next=q;q->next=r;continue;p->next=q;/如果輸入的值小于所有接點，接在最后一個接點之

15、后p=p->next; p->next=NULL;return head;輸出函數(shù)void Output(PolyNode*head) /輸出PolyNode*p;p=head->next;if(p=NULL) cout<<"當前沒有公式或計算結(jié)果為0，請選1輸入！n" return;if(p!=NULL)cout<<"計算結(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<<"如果想重新輸入公式，請選1輸入！nn"4、 調(diào)試分析與操作說明（1）當程序運行時，進入主界面。如圖： 此時輸入1-4選擇操作（2）輸入1后按回車出現(xiàn)： 輸入1 2 3 4 5 6 0 0后按回車之后 會出現(xiàn)界面： （3）求導：輸入2求導后按回車會出現(xiàn)結(jié)果： 結(jié)果正確。（4）求和：如果進入圖4.3后輸入3后按回車會出現(xiàn)界面： 圖4.5求和界面輸入2 2 4 4 6 6 0