数据结构课程设计报告设计一个一元多项式计算器

《数据结构课程设计报告设计一个一元多项式计算器》由会员分享，可在线阅读，更多相关《数据结构课程设计报告设计一个一元多项式计算器（22页珍藏版）》请在装配图网上搜索。

1、报告评分批改老师 数据结构课程设计报告 题 目 设计一个一元多项式计算器班 级 20090201 学生姓名 学 号 2009031327 专 业 电类强化班 指导教师 提交日期 2011/1/4 南京航空航天大学金城学院目录一、 题目要求及内容二、 函数模块及功能三、 技术要点四、 源代码五、 举例六、 调试心得一 题目要求及内容 1.题目：设计一个一元多项式计算器 2.要求 用带头结点的单链表存储多项式 Typedef struct lnode Float coef; Int expn; Struct lnode *next; lnode,*linklist; Typedef linklis

2、t polynominal; 输入时，构成的多项式链表按指数项大小递增有序排列 输出格式要求如： 3x2+6x8+7x12-9x15 3.基本功能输入并且建立一元多项式 输出多项式 多项式相加a+b 多项式相减a-b 多项式相乘a*b 二 函数模块及功能 1 void Insert( linklist p,linklist h)；链表插入 void Insert( linklist p,linklist h) if(p-coef=0) free(p);/系数为0的话释放结点 else linklist q1,q2; q1=h; q2=h-next; while(q2&p-expnq2-expn

3、) /查找插入位置 q1=q2; q2=q2-next; if(q2&p-expn=q2-expn) /将指数相同相合并 q2-coef+=p-coef; free(p); if(!q2-coef) /系数为0的话释放结点 q1-next=q2-next; free(q2); else/指数为新时将结点插入 p-next=q2; q1-next=p; 2linklist Createlinklist(linklist head)；创建链表 linklist Createlinklist(linklist head) /建立一个头指针为head的一元多项式 linklist p; float a

4、;int b; p=head=(linklist)malloc(sizeof(struct lnode); p-next=NULL; scanf(%f %d,&a,&b); while(a!=0 | b!=0) /当输入为0 0时停止输入 p=(linklist)malloc(sizeof(struct lnode); p-coef=a; p-expn=b; Insert(p,head); /调用Insert函数插入结点 scanf(%f %d,&a,&b); return head; 3void Destroylinklist(linklist p)；销毁链表 void Destroylin

5、klist(linklist p) /销毁多项式linklist linklist q1,q2; q1=p-next; q2=q1-next; while(q2) free(q1); q1=q2; q2=q2-next; 4void Printlinklist(linklist P)；打印链表 void Printlinklist(linklist P) linklist q=P-next; int flag=1;/项数计数器 if(!q) /若多项式为空，输出0 putchar(0); printf(n); return; while(q) if(q-coef0&flag!=1) putch

6、ar(+); /系数大于0且不是第一项 if(q-coef!=1&q-coef!=-1)/系数非1或-1的普通情况 printf(%g,q-coef); if(q-expn=1) putchar(X); else 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

7、); else printf(-X%d,q-expn); q=q-next; flag+; printf(n); 5int compare(linklist a,linklist b)；链表非空判断int compare(linklist a,linklist b) if(a&b) if(!b|a-expnb-expn) return -1; else if(!a|a-expnexpn) return 1; else return 0; else if(!a&b) return -1;/a多项式已空，但b多项式非空 else return 1;/b多项式已空，但a多项式非空6linklist

8、Addlinklist(linklist pa,linklist pb)；链表合并多项式相加linklist Addlinklist(linklist pa,linklist pb)/求解并建立多项式a+b，返回其头指针 linklist qa=pa-next; linklist qb=pb-next; linklist headc,hc,qc; hc=(linklist)malloc(sizeof(struct lnode);/建立头结点 hc-next=NULL; headc=hc; while(qa|qb) qc=(linklist)malloc(sizeof(struct lnode)

9、; switch(compare(qa,qb) case 1: 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-next; hc-next=qc; hc=qc; else free(qc);/当相加系数为

10、0时，释放该结点 return headc; 7linklist Subtractlinklist(linklist pa,linklist pb)；链表合并 多项式相减 linklist Subtractlinklist(linklist pa,linklist pb)/求解并建立多项式a-b，返回其 头指针 linklist h=pb; linklist p=pb-next; linklist pd; while(p) /将pb的系数取反 p-coef*=-1; p=p-next; pd=Addlinklist(pa,h); for(p=h-next;p;p=p-next) /恢复pb的系

11、数 p-coef*=-1; return pd; 8linklist Multiplylinklist(linklist pa,linklist pb)；多项式相乘 linklist Multiplylinklist(linklist pa,linklist pb) /求解并建立多项式a*b，返回其头指针 linklist hf,pf; linklist qa=pa-next; linklist qb=pb-next; hf=(linklist)malloc(sizeof(struct lnode);/建立头结点 hf-next=NULL; for(;qa;qa=qa-next) for(qb

12、=pb-next;qb;qb=qb-next) pf=(linklist)malloc(sizeof(struct lnode); pf-coef=qa-coef*qb-coef; pf-expn=qa-expn+qb-expn; Insert(pf,hf);/调用Insert函数以合并指数相同的项 return hf; 9int Valuelinklist(linklist head,int x)；多项式带值函数 int Valuelinklist(linklist head,int x)/输入x值，计算并返回多项式的值 linklist p; int i; int sum=0;int t;

13、 for(p=head-next;p;p=p-next) t=1; for(i=p-expn;i!=0;) if(icoef)*t; return sum; 10void main（）；主函数 void main() int s,x; char flag; linklist pa=0,pb=0,pc; printf( 欢迎使用多项式操作程序nn); /输出菜单 printf( *n); printf( * 一元多项式操作程序 *n); printf( * *n); printf( * *n); printf( * 1:输入多项式a 2:输入多项式b *n); printf( * *n); pr

14、intf( * *n); printf( * a:输出多项式a b:输出多项式b *n); printf( * *n); printf( * *n); printf( * c:代入x的值计算a d:代入x的值计算b *n); printf( * *n); printf( * *n); printf( * +:输出a+b -:输出a-b *n); printf( * *n); printf( * *n); printf( * *:输出a*b q:退出程序 *n); printf( * *n); printf( *n); printf(n 请选择操作：); while(s) scanf( %c,&

15、flag);/空格符号一定要注意 switch(flag) case 1: printf(请输入多项式a各项系数和指数（系数，指数）输入0 0为结束:); pa=Createlinklist(pa);/建立多项式a printf( n); printf(请继续操作: ); break; case 2: printf(请输入多项式b各项系数和指数（系数，指数）输入0 0为结束: ); pb=Createlinklist(pb);/建立多项式b printf( n); printf(请继续操作: ); break; casea: printf(n 多项式a=); Printlinklist(pa)

16、; break; caseb: printf(n 多项式b=); Printlinklist(pb); break; casec: printf(输入x的值：x=); scanf(%d,&x); printf(n x=%d时，a=%dn,x,Valuelinklist(pa,x); break; cased: printf(输入x的值：x=); scanf(%d,&x); printf(n x=%d时，b=%dn,x,Valuelinklist(pb,x); break; case+: pc=Addlinklist(pa,pb); printf(n a+b=); Printlinklist(p

17、c); break; case-: pc=Subtractlinklist(pa,pb); printf(n a-b=); Printlinklist(pc); break; case*: pc=Multiplylinklist(pa,pb); printf(n a*b=); Printlinklist(pc); break; caseq: printf(n 感谢使用此程序！n); Destroylinklist(pa); Destroylinklist(pb); s=0; break; default: printf(n 操作错误，请重新选择! n); 三 技术要点这两个链表的交叉合并运算主

18、要用到的是链表的基本操作，定义节点，将链表的创建（输入0 0为结束）、链表的交叉组合、链表内容升序排列、销毁链表、多项式的插入、多项式相加、多项式相减、多项式相乘、以及带值计算多项式等算法写成独立函数，通过主函数调用。这样大大精简了主函数的操作。而且在主函数中创建菜单，用了switch语句比if语句和while语句简洁明了得多。四 源代码#include#include#include/定义多项式的项typedef struct lnode float coef; int expn; struct lnode *next;lnode,*linklist;typedef linklist pol

19、ynominal;void Insert( linklist p,linklist h) if(p-coef=0) free(p);/系数为0的话释放结点 else linklist q1,q2; q1=h; q2=h-next; while(q2&p-expnq2-expn) /查找插入位置 q1=q2; q2=q2-next; if(q2&p-expn=q2-expn) /将指数相同相合并 q2-coef+=p-coef; free(p); if(!q2-coef) /系数为0的话释放结点 q1-next=q2-next; free(q2); else /指数为新时将结点插入 p-next

20、=q2; q1-next=p; linklist Createlinklist(linklist head)/建立一个头指针为head的一元多项式linklist p;float a;int b; p=head=(linklist)malloc(sizeof(struct lnode); p-next=NULL; scanf(%f %d,&a,&b); while(a!=0 | b!=0) /当输入为0 0时停止输入 p=(linklist)malloc(sizeof(struct lnode); p-coef=a; p-expn=b; Insert(p,head); /调用Insert函数插

21、入结点 scanf(%f %d,&a,&b);return head;void Destroylinklist(linklist p)/销毁多项式linklist linklist q1,q2; q1=p-next; q2=q1-next; while(q2) free(q1); q1=q2; q2=q2-next; void Printlinklist(linklist P) linklist q=P-next; int flag=1;/项数计数器 if(!q) /若多项式为空，输出0 putchar(0); printf(n); return; while(q) if(q-coef0&fl

22、ag!=1) putchar(+); /系数大于0且不是第一项 if(q-coef!=1&q-coef!=-1)/系数非1或-1的普通情况 printf(%g,q-coef); if(q-expn=1) putchar(X); else 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=

23、1) printf(-X); else printf(-X%d,q-expn); q=q-next; flag+; printf(n);int compare(linklist a,linklist b) if(a&b) if(!b|a-expnb-expn) return -1; else if(!a|a-expnexpn) return 1; else return 0; else if(!a&b) return -1;/a多项式已空，但b多项式非空 else return 1;/b多项式已空，但a多项式非空linklist Addlinklist(linklist pa,linklist

24、 pb)/求解并建立多项式a+b，返回其头指针 linklist qa=pa-next; linklist qb=pb-next; linklist headc,hc,qc; hc=(linklist)malloc(sizeof(struct lnode);/建立头结点 hc-next=NULL; headc=hc; while(qa|qb) qc=(linklist)malloc(sizeof(struct lnode); switch(compare(qa,qb) case 1: qc-coef=qa-coef; qc-expn=qa-expn; qa=qa-next; break; ca

25、se 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-next=qc; hc=qc; else free(qc);/当相加系数为0时，释放该结点 return headc;linklist Subtractlinklist(linklist pa,linklist pb)/求解并建立多项式a-b，返回

26、其头指针 linklist h=pb; linklist p=pb-next; linklist pd; while(p) /将pb的系数取反 p-coef*=-1; p=p-next; pd=Addlinklist(pa,h); for(p=h-next;p;p=p-next) /恢复pb的系数 p-coef*=-1; return pd;linklist Multiplylinklist(linklist pa,linklist pb)/求解并建立多项式a*b，返回其头指针 linklist hf,pf; linklist qa=pa-next; linklist qb=pb-next;

27、hf=(linklist)malloc(sizeof(struct lnode);/建立头结点 hf-next=NULL; for(;qa;qa=qa-next) for(qb=pb-next;qb;qb=qb-next) pf=(linklist)malloc(sizeof(struct lnode); pf-coef=qa-coef*qb-coef; pf-expn=qa-expn+qb-expn; Insert(pf,hf);/调用Insert函数以合并指数相同的项 return hf;int Valuelinklist(linklist head,int x)/输入x值，计算并返回多项

28、式的值 linklist p; int i; int sum=0;int t; for(p=head-next;p;p=p-next) t=1; for(i=p-expn;i!=0;) if(icoef)*t; return sum;void main() int s,x; char flag; linklist pa=0,pb=0,pc; printf( 欢迎使用多项式操作程序nn); /输出菜单printf( *n);printf( * 一元多项式操作程序 *n);printf( * *n);printf( * *n); printf( * 1:输入多项式a 2:输入多项式b *n); p

29、rintf( * *n);printf( * *n);printf( * a:输出多项式a b:输出多项式b *n);printf( * *n);printf( * *n);printf( * c:代入x的值计算a d:代入x的值计算b *n);printf( * *n); printf( * *n); printf( * +:输出a+b -:输出a-b *n);printf( * *n); printf( * *n); printf( * *:输出a*b q:退出程序 *n);printf( * *n);printf( *n); printf(n 请选择操作：);while(s) scanf

30、( %c,&flag);/空格符号一定要注意 switch(flag) case 1: printf(请输入多项式a各项系数和指数（系数，指数）输入0 0为结束:); pa=Createlinklist(pa);/建立多项式aprintf( n);printf(请继续操作: ); break; case 2: printf(请输入多项式b各项系数和指数（系数，指数）输入0 0为结束: ); pb=Createlinklist(pb);/建立多项式b printf( n);printf(请继续操作: ); break; casea: printf(n 多项式a=); Printlinklist(

31、pa); break; caseb: printf(n 多项式b=); Printlinklist(pb); break; casec: printf(输入x的值：x=); scanf(%d,&x); printf(n x=%d时，a=%dn,x,Valuelinklist(pa,x); break; cased: printf(输入x的值：x=); scanf(%d,&x); printf(n x=%d时，b=%dn,x,Valuelinklist(pb,x); break; case+: pc=Addlinklist(pa,pb); printf(n a+b=); Printlinklis

32、t(pc); break; case-: pc=Subtractlinklist(pa,pb); printf(n a-b=); Printlinklist(pc); break; case*: pc=Multiplylinklist(pa,pb); printf(n a*b=); Printlinklist(pc); break; caseq: printf(n 感谢使用此程序！n); Destroylinklist(pa); Destroylinklist(pb); s=0; break; default: printf(n 操作错误，请重新选择! n); 五 以多项式 x2-2x3和2x

33、+3x2为例欢迎进入界面输入与输出带X值计算多项式多项式加减乘计算 六 调试心得1） 调试情况建立链表时运用尾插法，要将新申请的结点接到所有结点之后。再用一while语句使得输入为0 0时停止输入。多项式相减时，先将多项式b每项的系数取反（p-coef*=-1; p=p-next;）再调用多项式加法函数。并注意恢复pb的系数（for(p=h-next;p;p=p-next) p-coef*=-1; ）以便不影响接下来的操作。多项式相乘时，注意要将多项式每项的系数相（pf-coef=qa-coef*qb-coef;）、指数相加（ pf-expn=qa-expn+qb-expn;）。并创建一个新的链表，再调用Insert函数以合并指数相同的项。带值计算多项式时，不仅要注意给求和进行强制类型转（sum+=int(p-coef)*t;），还要注意指数小于0，进行除法（if(i0)t/=x;i+;）指数大于0，进行乘法（elset*=x;i-;）。主函数中建立菜单，选择使用switch语句方便选择操作 2） 心得体会此次课程设计让我了解到了如何建立链表和删除链表结点。如何灵活运用链表升序建立多项式，以及多项式的相加、相减、相乘、带值运算。体会到了链表的深刻内涵。