數(shù)據(jù)結構課程設計---一元稀疏多項式計算器(報告+代碼)--完整(共13頁)

1、精選優(yōu)質文檔-傾情為你奉上學院計算機與信息工程系數(shù)據(jù)結構課程設計設計題目：一元稀疏多項式計算器 專 業(yè) 班 級 學 號 姓 名 指導教師 2010 年 12 月 20 日目錄一、 課程題目1二、 需求分析1三、 測試數(shù)據(jù)2四、 概要設計2五、 調用關系圖3六、 程序代碼3七、 測試結果11八、 心得體會及總結12數(shù)據(jù)結構課程設計一、課程題目 一元稀疏多項式計算器二、 需求分析1、一元稀疏多項式簡單計算器的功能是：1.1 輸入并建立多項式；1.2 輸出多項式，輸出形式為整數(shù)序列：n，c1,e1,c2,e2,cn,en,其中n是多項式的項數(shù)，ci和ei分別是第i項的系數(shù)和指數(shù)，序列按指數(shù)降序排列；

2、 1.3 求多項式a、b的導函數(shù)；1.4 計算多項式在x處的值；1.5多項式a和b相加，建立多項式a+b；1.6 多項式a和b相減，建立多項式a-b。2、設計思路:2.1 定義線性表的動態(tài)分配順序存儲結構；2.2 建立多項式存儲結構，定義指針*next2.3利用鏈表實現(xiàn)隊列的構造。每次輸入一項的系數(shù)和指數(shù)，可以輸出構造的一元多項式2.4演示程序以用戶和計算機的對話方式執(zhí)行，即在計算機終站上顯示“提示信息”之后，由用戶在鍵盤上輸入演示程序中規(guī)定的運行命令；最后根據(jù)相應的輸入數(shù)據(jù)（濾去輸入中的非法字符）建立的多項式以及多項式相加的運行結果在屏幕上顯示。多項式顯示的格式為：c1xe1+c2xe2+c

3、nxen3、設計思路分析要解決多項式相加，必須要有多項式，所以必須首先建立兩個多項式，在這里采用鏈表的方式存儲鏈表，所以我將結點結構體定義為序數(shù)coef指數(shù)expn指針域next運用尾插法建立兩條單鏈表，以單鏈表polyn p和polyn h分別表示兩個一元多項式a和b，a+b的求和運算等同于單鏈表的插入問題（將單鏈表polyn p中的結點插入到單鏈表polyn h中），因此“和多項式”中的結點無須另生成。為了實現(xiàn)處理，設p、q分別指向單鏈表polya和polyb的當前項，比較p、q結點的指數(shù)項，由此得到下列運算規(guī)則： 若p->expn<q->expn，則結點p所指的結點應是

4、“和多項式”中的一項，令指針p后移。 若p->expn=q->expn，則將兩個結點中的系數(shù)相加，當和不為0時修改結點p的系數(shù)。 若p->expn>q->expn，則結點q所指的結點應是“和多項式”中的一項，將結點q插入在結點p之前，且令指針q在原來的鏈表上后移。三、測試數(shù)據(jù)：1、(2x+5x8-3.1x11)+(7-5x8+11x9)=(-3.1x11+11x9+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

5、)+(-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.四、概要設計 1、元素類型、結點類型和指針類型：typedef struct Polynomial float coef; /系數(shù) int expn; /指數(shù) struct Polynomial *next;*Polyn,Polynomial;2、建立一個頭指針為head、項數(shù)為m的一元多項式, 建立新結點以接收數(shù)據(jù), 調用Insert函數(shù)插入結點: Polyn CreatePolyn(Pol

6、yn head,int m) int i; Polyn p; p=head=(Polyn)malloc(sizeof(struct Polynomial); head->next=NULL; for(i=0;i<m;i+) p=(Polyn)malloc(sizeof(struct Polynomial); printf("請輸入第%d項的系數(shù)與指數(shù):",i+1); scanf("%f %d",&p->coef,&p->expn); Insert(p,head); return head;3、主函數(shù)和其他函數(shù)：vo

7、id main() int m,n,a,x; char flag; Polyn pa=0,pb=0,pc; float ValuePolyn(Polyn head,int x) /輸入x值，計算并返回多項式的值五、調用關系圖（圖1）六、程序代碼：#include<stdio.h>#include<stdlib.h> /定義多項式的項typedef struct Polynomial float coef; /系數(shù) int expn; /指數(shù) struct Polynomial *next;*Polyn,Polynomial;void Insert(Polyn p,Pol

8、yn h) if(p->coef=0) free(p); /系數(shù)為0的話釋放結點 else Polyn q1,q2; q1=h;q2=h->next; while(q2&& p->expn < q2->expn) /查找插入位置 q1=q2; q2=q2->next; if(q2&& p->expn = q2->expn) /將指數(shù)相同相合并 q2->coef += p->coef; free(p); if(!q2->coef) /系數(shù)為0的話釋放結點 q1->next=q2->nex

9、t; free(q2); else /指數(shù)為新時將結點插入 p->next=q2; q1->next=p;Polyn CreatePolyn(Polyn head,int m) /建立一個頭指針為head、項數(shù)為m的一元多項式 int i; Polyn p; p=head=(Polyn)malloc(sizeof(struct Polynomial); head->next=NULL; for(i=0;i<m;i+) p=(Polyn)malloc(sizeof(struct Polynomial); /建立新結點以接收數(shù)據(jù) printf("請輸入第%d項的系

10、數(shù)與指數(shù):",i+1); scanf("%f %d",&p->coef,&p->expn); Insert(p,head); /調用Insert函數(shù)插入結點 return head;void DestroyPolyn(Polyn p) /銷毀多項式p Polyn q1,q2; q1=p->next; q2=q1->next; while(q1->next) free(q1); q1=q2; q2=q2->next;void PrintPolyn(Polyn P)Polyn q=P->next; int fl

11、ag=1; /項數(shù)計數(shù)器 if(!q) /若多項式為空，輸出0 putchar('0'); printf("n"); return; while(q) if(q->coef>0&& flag!=1) putchar('+'); /系數(shù)大于0且不是第一項 if(q->coef!=1&&q->coef!=-1) /系數(shù)非1或-1的普通情況 printf("%g",q->coef); if(q->expn=1) putchar('X'); els

12、e if(q->expn) printf("X%d",q->expn); else if(q->coef=1) if(!q->expn) putchar('1'); else if(q->expn=1) putchar('X'); else printf("X%d",q->expn); if(q->coef=-1) if(!q->expn) printf("-1"); else if(q->expn=1) printf("-X")

13、; else printf("-X%d",q->expn); q=q->next; flag+; printf("n");int compare(Polyn a,Polyn b) if(a&&b) if(!b|a->expn>b->expn) return 1; else if(!a|a->expn<b->expn) return -1; else return 0; else if(!a&&b) return -1; /a多項式已空，但b多項式非空 else return

14、1; /b多項式已空，但a多項式非空Polyn AddPolyn(Polyn pa,Polyn pb) /求解并建立多項式a+b，返回其頭指針 Polyn qa=pa->next; Polyn qb=pb->next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial); /建立頭結點 hc->next=NULL; headc=hc; while(qa|qb) qc=(Polyn)malloc(sizeof(struct Polynomial); switch(compare(qa,qb) case 1:

15、 qc->coef=qa->coef; qc->expn=qa->expn; qa=qa->next; break; case 0: qc->coef=qa->coef+qb->coef; qc->expn=qa->expn; qa=qa->next; qb=qb->next; break; case -1: qc->coef=qb->coef; qc->expn=qb->expn; qb=qb->next; break; if(qc->coef!=0) qc->next=hc-&

16、gt;next; hc->next=qc; hc=qc; else free(qc); /當相加系數(shù)為0時，釋放該結點 return headc;Polyn SubtractPolyn(Polyn pa,Polyn pb) /求解并建立多項式a-b，返回其頭指針 Polyn h=pb; Polyn p=pb->next; Polyn pd; while(p) /將pb的系數(shù)取反 p->coef*=-1; p=p->next; pd=AddPolyn(pa,h); for(p=h->next;p;p=p->next) /恢復pb的系數(shù) p->coef*=

17、-1; return pd;float ValuePolyn(Polyn head,int x) /輸入x值，計算并返回多項式的值Polyn p; int i,t;float sum=0; for(p=head->next;p;p=p->next) t=1; for(i=p->expn;i!=0;) if(i<0)t/=x;i+; /指數(shù)小于0，進行除法 elset*=x;i-; /指數(shù)大于0，進行乘法 sum+=p->coef*t; return sum;Polyn Derivative(Polyn head) /求解并建立導函數(shù)多項式，并返回其頭指針 Poly

18、n q=head->next,p1,p2,hd; hd=p1=(Polyn)malloc(sizeof(struct Polynomial);/建立頭結點 hd->next=NULL; while(q) if(q->expn!=0) /該項不是常數(shù)項時 p2=(Polyn)malloc(sizeof(struct Polynomial); p2->coef=q->coef*q->expn; p2->expn=q->expn-1; p2->next=p1->next; /連接結點 p1->next=p2; p1=p2; q=q-&

19、gt;next; return hd;Polyn MultiplyPolyn(Polyn pa,Polyn pb) /求解并建立多項式a*b，返回其頭指針 Polyn hf,pf; Polyn qa=pa->next; Polyn qb=pb->next; hf=(Polyn)malloc(sizeof(struct Polynomial);/建立頭結點 hf->next=NULL; for(;qa;qa=qa->next) for(qb=pb->next;qb;qb=qb->next) pf=(Polyn)malloc(sizeof(struct Poly

20、nomial); pf->coef=qa->coef*qb->coef; pf->expn=qa->expn+qb->expn; Insert(pf,hf); /調用Insert函數(shù)以合并指數(shù)相同的項 return hf;void main() int m,n,a,x;char flag; Polyn pa=0,pb=0,pc;printf(" -n");printf(" | *班 * * |n");printf(" -n");printf(" 歡迎使用多項式操作程序n"); p

21、rintf("請輸入a的項數(shù):"); scanf("%d",&m); pa=CreatePolyn(pa,m); /建立多項式a printf("請輸入b的項數(shù):"); scanf("%d",&n); pb=CreatePolyn(pb,n); /建立多項式b /輸出菜單printf(" *n"); printf(" * 多項式操作程序 *n");printf(" * *n");printf(" * A:輸出多項式a B:輸出多項

22、式b *n");printf(" * *n");printf(" * C:輸出a的導數(shù) D:輸出b的導數(shù) *n");printf(" * *n");printf(" * E:代入x的值計算a F:代入x的值計算b *n");printf(" * *n");printf(" * G:輸出a+b H:輸出a-b *n");printf(" * *n"); printf(" * I:輸出a*b J:退出程序 *n");printf(

23、" * *n"); printf(" *n");while(a) printf("n請選擇操作："); scanf(" %c",&flag); switch(flag) case'A': case'a': printf("n 多項式a="); PrintPolyn(pa); break; case'B':case'b': printf("n 多項式b="); PrintPolyn(pb); break;

24、case'C': case'c': pc=Derivative(pa); printf("n 多項式a的導函數(shù)為：a'="); PrintPolyn(pc); break; case'D':case'd': pc=Derivative(pb); printf("n 多項式b的導函數(shù)為：b'="); PrintPolyn(pc); break; case'E':case'e': printf("輸入x的值：x="); scanf("%d",&x); printf("n x=%d時，a=%.3fn",x,ValuePolyn(pa,x); break; case'F':case'f': printf("輸入x的值：x="); scanf("%d