數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)一元稀疏多項(xiàng)式計(jì)算器報(bào)告代碼完整

1、學(xué)院計(jì)算機(jī)與信息工程系數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)設(shè)計(jì)題目：一元稀疏多項(xiàng)式計(jì)算器 專 業(yè) 班 級(jí) 學(xué) 號(hào) 姓 名 指導(dǎo)教師 2010 年 12 月 20 日目錄一、 課程題目1二、 需求分析1三、 測試數(shù)據(jù)2四、 概要設(shè)計(jì)2五、 調(diào)用關(guān)系圖3六、 程序代碼3七、 測試結(jié)果11八、 心得體會(huì)及總結(jié)12數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)一、課程題目 一元稀疏多項(xiàng)式計(jì)算器二、 需求分析1、一元稀疏多項(xiàng)式簡單計(jì)算器的功能是：1.1 輸入并建立多項(xiàng)式；1.2 輸出多項(xiàng)式，輸出形式為整數(shù)序列：n，c1,e1,c2,e2,cn,en,其中n是多項(xiàng)式的項(xiàng)數(shù)，ci和ei分別是第i項(xiàng)的系數(shù)和指數(shù)，序列按指數(shù)降序排列； 1.3 求多項(xiàng)式a、b的

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

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

4、針p后移。 若p->expn=q->expn，則將兩個(gè)結(jié)點(diǎn)中的系數(shù)相加，當(dāng)和不為0時(shí)修改結(jié)點(diǎn)p的系數(shù)。 若p->expn>q->expn，則結(jié)點(diǎn)q所指的結(jié)點(diǎn)應(yīng)是“和多項(xiàng)式”中的一項(xiàng)，將結(jié)點(diǎn)q插入在結(jié)點(diǎn)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)+(-x3-x4)=(1

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

6、) 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("請(qǐng)輸入第%d項(xiàng)的系數(shù)與指數(shù):",i+1); scanf("%f %d",&p->coef,&p->expn); Insert(p,head); return head;3、主函數(shù)和其他函數(shù)：void main() int

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

8、t;coef=0) free(p); /系數(shù)為0的話釋放結(jié)點(diǎn) 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的話釋放結(jié)點(diǎn) q1->next=q2->next; free(q2);

9、else /指數(shù)為新時(shí)將結(jié)點(diǎn)插入 p->next=q2; q1->next=p;Polyn CreatePolyn(Polyn head,int m) /建立一個(gè)頭指針為head、項(xiàng)數(shù)為m的一元多項(xiàng)式 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); /建立新結(jié)點(diǎn)以接收數(shù)據(jù) printf("請(qǐng)輸入第%d項(xiàng)的系數(shù)與指數(shù):",i

10、+1); scanf("%f %d",&p->coef,&p->expn); Insert(p,head); /調(diào)用Insert函數(shù)插入結(jié)點(diǎn) return head;void DestroyPolyn(Polyn p) /銷毀多項(xiàng)式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 flag=1; /項(xiàng)數(shù)計(jì)數(shù)器

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

12、pn) 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"); else printf

13、("-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多項(xiàng)式已空，但b多項(xiàng)式非空 else return 1; /b多項(xiàng)式已空，但a

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

15、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->next; hc-&

16、gt;next=qc; hc=qc; else free(qc); /當(dāng)相加系數(shù)為0時(shí)，釋放該結(jié)點(diǎn) return headc;Polyn SubtractPolyn(Polyn pa,Polyn pb) /求解并建立多項(xiàng)式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) /恢復(fù)pb的系數(shù) p->coef*=-1; return pd

17、;float ValuePolyn(Polyn head,int x) /輸入x值，計(jì)算并返回多項(xiàng)式的值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，進(jìn)行除法 elset*=x;i-; /指數(shù)大于0，進(jìn)行乘法 sum+=p->coef*t; return sum;Polyn Derivative(Polyn head) /求解并建立導(dǎo)函數(shù)多項(xiàng)式，并返回其頭指針 Polyn q=head->

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

19、rn hd;Polyn MultiplyPolyn(Polyn pa,Polyn pb) /求解并建立多項(xiàng)式a*b，返回其頭指針 Polyn hf,pf; Polyn qa=pa->next; Polyn qb=pb->next; hf=(Polyn)malloc(sizeof(struct Polynomial);/建立頭結(jié)點(diǎn) hf->next=NULL; for(;qa;qa=qa->next) for(qb=pb->next;qb;qb=qb->next) pf=(Polyn)malloc(sizeof(struct Polynomial); pf-&

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

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

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

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

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