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

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

2、臺(tái)下的 Visual C+ 6.0硬件環(huán)境：512MB內(nèi)存，80Gb硬盤,Pentium4 CPU,CRT顯示器。4 / 16二、概要分析本程序有五個(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)的單鏈表來實(shí)現(xiàn)多項(xiàng)式的鏈表表示， 每個(gè)鏈表結(jié)點(diǎn)表示多項(xiàng)式 的一項(xiàng)，命名為 node,

3、它包括兩個(gè)數(shù)據(jù)成員：系數(shù)coef和指數(shù)exp，他們都是公共數(shù)據(jù)成員， *next 為指針域，用鏈表來表示多項(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)行效率高。三、詳細(xì)設(shè)計(jì)1）主函數(shù)： int main()PolyNode *head_a,*

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

5、in>>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ì)。所以下面著重介紹下求和函數(shù)和求

6、導(dǎo)函數(shù)。PolyNode *Deri(PolyNode *head) (求導(dǎo)函數(shù)) 流程圖如下：5 / 16求導(dǎo)函數(shù)部分代碼：PolyNode *Deri(PolyNode *head) / 求導(dǎo)PolyNode *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ì)

7、輸入的多項(xiàng)式進(jìn)行求導(dǎo)， 求導(dǎo)在鏈表內(nèi)進(jìn)行計(jì)算， 即運(yùn)算完成鏈表的值改變， 指針。PolyNode * Plus(PolyNode *A,PolyNode *B) (求和函數(shù)) 流程圖如下：7 / 16PolyNode *Plus(PolyNode*A,PolyNode *B)A為空Y將B接到p后面B為空Y將A接到p后面YN合并相同系數(shù)相同 項(xiàng)，連接到新鏈表后 面互為倒數(shù)AB指數(shù)相等A、B的系數(shù)N將A的當(dāng)前接點(diǎn)接到 新鏈表后面，A后指4A、B均后指B的指數(shù)-A的指數(shù)大于將B的當(dāng)前接點(diǎn)接到 新鏈表后面，B后指start建立鏈表 head, p=head，兩頭指針B均指向各自的next8 / 16本

8、函數(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)。經(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;if(B=NULL) p->

9、;next=A; break; if(A->exp=B->exp)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;循環(huán)if(A->exp > B->exp)相加/ 如果 A 空，把 B 后面的所有接點(diǎn)接到 p 之后 / 如果 B 空，把 A 后面的所有接點(diǎn)接到 p 之后 /如果兩指數(shù)數(shù)相等，相加/如果

10、兩系數(shù)互為倒數(shù)，不保存，后指，繼續(xù)/A 的指數(shù)大于 B 的指數(shù)15 / 16p->next=new PolyNode;p=p->next; p->exp=A->exp; p->coef=A->coef;/ 將 A 的當(dāng)前接點(diǎn)接到新鏈表后面， A 后指A=A->next; continue;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&

11、&B=NULL） /如果 A B 都為空 p->next=NULL;return head;/返回頭指針（3）其他函數(shù)（同組的成員設(shè)計(jì)）#include <iostream>#include <process.h>using namespace std; typedef struct node float coef;int exp;struct node *next;/系數(shù)/指數(shù)/指針域 指向下一個(gè)系數(shù)不為 0 的子項(xiàng) PolyNode;PolyNode *Input()/輸入函數(shù)float c;/ 系數(shù)域int e;/指數(shù)域PolyNode *p,*q,

12、*r,*head; cout<<" 請(qǐng)輸入多項(xiàng)式 :n"cout<<" 形式：系數(shù) 1 指數(shù) 1 系數(shù) 2 指數(shù) 2 系數(shù) 3 指數(shù) 30 0： n"head=new PolyNode; / 建立頭接點(diǎn)p=head;p->next=NULL;for (;)cin>>c>>e;if(c=0&&e=0) break; if(c=0) continue; if(head->next=NULL) /結(jié)束輸入/從新輸入，不保存/輸入第一個(gè)接點(diǎn)p->next=new PolyNode;

13、 p=p->next; p->coef=c,p->exp=e; p->next=NULL;continue; p=head;while(p->next!=NULL && e<=p->next->exp) p=p->next; 下一個(gè)接點(diǎn)， p 向后指if (e=p->exp) p->coef+=c;continue;/如果輸入的指數(shù)小于 p 的/如果相等，直接加上去，繼續(xù)循環(huán)/如果 p 的后繼接點(diǎn)的指數(shù)q=new PolyNode; q->coef=c,q->exp=e; if (p->next

14、!=NULL&&e>p->next->exp) 小于輸入的指數(shù)，插入到 p 的當(dāng)前接點(diǎn)之后r=p->next;p->next=q;q->next=r; continue;/如 果輸入 的值小 于 p->next=q;所有接點(diǎn)，接在最后一個(gè)接點(diǎn)之后p=p->next; p->next=NULL;return head;輸出函數(shù)void Output(PolyNode*head) / 輸出PolyNode*p;p=head->next;1 輸入！ n" return;if(p=NULL) cout<<

15、" 當(dāng)前沒有公式或計(jì)算結(jié)果為0，請(qǐng)選if(p!=NULL)cout<<" 計(jì)算結(jié)果： n" cout<<p->coef<<"X"<<p->exp;p=p->next;while(p!=NULL) cout<<"+"<<p->coef<<"X"<<p->exp; p=p->next;cout<<endl;cout<<"如果想重新輸入公式，請(qǐng)選

16、1輸入！ ！ nn"四、調(diào)試分析與操作說明（1）當(dāng)程序運(yùn)行時(shí)，進(jìn)入主界面。如圖：-_ _ _式導(dǎo)利序公S入式出舉兩退-此時(shí)輸入1-4選擇操作(2) 輸入1后按回車出現(xiàn):輸入 1 2 3 4 5 6 0 0后按回車之后會(huì)出現(xiàn)界面:g "I; Debugll llxc"如杲想重新輸入公式，請(qǐng)選i輸入1111遴入蠱式2 求 導(dǎo)3.4 ，迫出翟岸ZJWkHVJUWAriUVWAMVfUUUWiWUTWnriVHJmWAfJUWAmrEfUJV(3) 求導(dǎo)：輸入2求導(dǎo)后按回車會(huì)出現(xiàn)結(jié)果:FT算結(jié)果=如杲想重新輸入公式，請(qǐng)選丄輸入！式導(dǎo)和序 ®番 入式出 泉兩退 - 12 3 4卜結(jié)果正確。(4)求和：如果進(jìn)入圖 4.3后輸入3后按回車會(huì)出現(xiàn)界面:圖4.5求和界面輸入2 2 4 4 6 6 0 0后結(jié)果會(huì)出來：c' "I:OebugM 11klK&*?X*3X2亦果想重新輸入公式,請(qǐng)選1輸入I丨！式導(dǎo)和序