一元多项式计算 课程设计报告

1、课 程 设 计课程设计名称： 数据结构 专 业 班 级 ： 计科06级04班 学 生 姓 名 ： 宋庆伟 学 号 ： 20064140421 指 导 教 师 ： 白 浩 课程设计时间：2008.6.232008.6.29计算机科学与技术专业课程设计任务书学生姓名宋庆伟专业班级计科0604学号20064140421题 目一元多项式计算课题性质其它课题来源自拟课题指导教师白 浩同组姓名无主要内容顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现。 设有一元多项式am(x)和bn(x). am(x)=a0+a1x1+a2x2+a3x3+ +amxm bn(x)=b0+b1x1+b2x2+b

2、3x3+ +bnxn请实现求m(x)= am(x)+bn(x)、m(x)= am(x)-bn(x)和m(x)= am(x)bn(x)任务要求请设计一系统模拟动态地显示出上述过程，要求如下：1)首先判定多项式是否稀疏2)分别采用顺序和动态存储结构实现；3)结果m(x)中无重复阶项和无零系数项；4)要求输出结果的升幂和降幂两种排列情况 参考文献数据结构（c语言版） 严蔚敏 吴为民 清华大学出版社数据结构题集（c语言版） 严蔚敏 吴为民 米宁 清华大学出版社审查意见指导教师签字：教研室主任签字： 2008年 6 月 29 日 宋庆伟-20064140421-课程设计报告一 需求分析顺序结构、动态链表

3、结构下的一元多项式的加法、减法、乘法的实现。设有一元多项式am(x)和bn(x).am(x)=a0+a1x1+a2x2+a3x3+ +amxmbn(x)=b0+b1x1+b2x2+b3x3+ +bnxn 请实现求m(x)= am(x)+bn(x)、m(x)= am(x)-bn(x)和m(x)= am(x)bn(x)。要求： 1)首先判定多项式是否稀疏;2)分别采用顺序和动态存储结构实现;3)结果m(x)中无重复阶项和无零系数项；4)要求输出结果的升幂和降幂两种排列情况二 概要设计存储方式：动态链表存储。算法核心思想：建立俩个动态链表分别存储多项式m与n，有switch语句控制加法，减法与乘法的

4、运算选择，当用户选定所要做的运算时分别由a（） b（） c（）函数来调用各自的加法add()函数,加法reduce()函数和乘法multi()函数与此同时在各个运算被调用时分别对所输入地多项式进行排序以及合并同类项，最后由print()函数分别对已经做过运算且排好顺序（升幂和降幂）的多项式结果输出。流程图如下：m多项式 n多项式a( )b( )c( )add( )reduce()multi()sortlow()sorthigh()print()三 详细设计#include #include #include typedef struct term /项的表示，多项式的项作为linklist的数

5、据元素 float coef; /系数 int expn; /指数struct term *next; term; term* creat(term *p,int m) / 输入m项的系数和指数，建立表示一元多项式的有序链表p term* h;term* p;term* q;int i=0; if(m coef = 0.0; printf(依次输入%d个非零项(即系数值+空格+指数值)n,m); for (i = 1; i coef,&p-expn); if(p-coef) q = p; p = p-next = (term*)malloc(sizeof(term); q-next = nul

6、l; free(p); return h; / 创建一个多项式term* sortlow(term *h) term *g, *p, *q; int i, fini = 1;float f; if(!h) return null; for(g = h;g-next&fini;g = g-next) fini = 0; for(p = h,q = h-next;q;p = p-next,q = q-next) if (p-expn expn) f = p-coef;i = p-expn; p-coef = q-coef;p-expn = q-expn; q-coef = f;q-expn = i

7、; fini = 1; for(g = h,p = g-next;p;) if(g-expn=p-expn) g-coef += p-coef; g-next = p-next; q = p; p = p-next; free(q); else if(g-next) g = g-next; p = p-next; return h; term* sorthigh(term *h) term *g, *p, *q; int i, fini = 1;float f; if(!h) return null; for(g = h;g-next&fini;g = g-next) fini = 0; fo

8、r(p = h,q = h-next;q;p = p-next,q = q-next) if (p-expn q-expn) f = p-coef;i = p-expn; p-coef = q-coef;p-expn = q-expn; q-coef = f;q-expn = i; fini = 1; for(g = h,p = g-next;p;) if(g-expn=p-expn) g-coef += p-coef; g-next = p-next; q = p; p = p-next; free(q); else if(g-next) g = g-next; p = p-next; pr

9、intf(以上结果为降幂排列!);printf(n);printf(结果升幂排列顺序如下：);return h; void print(term *p) term *q = p; if(!q) putchar(0); return; if(q-coef!=1) printf(%f,q-coef); if(q-expn=1) putchar(x); else if(q-expn) printf(x%d,q-expn); else if(!q-expn) putchar(1); else if(q-expn=1) putchar(x); else printf(x%d,q-expn); q = q

10、-next; while (q) if(q-coef 0) putchar(+); if(q-coef!=1) printf(%f,q-coef); if(q-expn=1) putchar(x); else if(q-expn) printf(x%d,q-expn); else if(!q-expn) putchar(1); else if(q-expn=1) putchar(x); else printf(x%d,q-expn); q = q-next; int compare(term *a, term *b) if (a-expn expn) return -1; if (a-expn

11、 b-expn) return 1; return 0; term* add(term *pa, term *pb) / 多项式加法：pa = papb，利用两个多项式的结点构成和多项式。 term *h, *qa = pa, *qb = pb, *p, *q; float sum; h = p = (term*)malloc(sizeof(term); p-next = null; while (qa & qb) / pa和pb均非空 switch (compare(qa,qb) case -1: / 多项式pa中当前结点的指数值小 ，后移p-next = qb; p = qb; qb =

12、qb-next; break; case 0: / 两者的指数值相等 ,系数直接相加sum = qa-coef + qb-coef; if (sum != 0.0) / 修改多项式pa中当前结点的系数值 p-next = qa; qa-coef = sum; p = qa; qa = qa-next; else / 删除多项式pa中当前结点 q = qa; qa = qa-next; free(q); q = qb; qb = qb-next; free(q); break; case 1: / 多项式pb中当前结点的指数值小 p-next = qa; p = qa; qa = qa-next

13、; break; / switch 语句控制 / while 循环if (pa) p-next = qa; / 如果有剩余则链接pa中剩余结点 if (pb) p-next = qb; / 链接pb中剩余结点 q = h; h = h-next; free(q); return h; / addterm* a(term *pa, term *pb) int n; puts(请再输入一一元多项式的项数); scanf(%d,&n); pb = creat(pb,n); pb = sortlow(pb); print(pb);printf(n);print(pa); if(pb & pb-coef

14、0) printf( + ); print(pb); pa = add(pa,pb); printf( =n); pa = sortlow(pa); print(pa);printf(n);pa=sorthigh(pa); print(pa);return pa; term* reduce(term *pa, term *pb) / 多项式减法：pa = pa-pb，利用两个多项式的结点构成差多项式。 term *p = pb; while(p) p-coef *= -1; p = p-next; return add(pa,pb); / reduceterm* b(term *pa, ter

15、m *pb) int n; puts(再输入一一元多项式的项数); scanf(%d,&n); pb = creat(pb,n); pb = sortlow(pb); print(pb);printf(n);print(pa); printf( - ); putchar();print(pb);putchar(); pa = reduce(pa,pb); printf( = ); pa = sortlow(pa); print(pa);printf(n);pa=sorthigh(pa); print(pa);return pa; term* multi(term *pa, term *pb)

16、/ 多项式乘法：pa = pa*pb，利用两个多项式的结点构成积多项式。term *pa = pa, *p, *q, *r, *s, *t;if(!pb) return null; pa = pa, *p, *q, *r, *s, *t; r = p = (term*)malloc(sizeof(term); while(pa) p-coef = pa-coef; p-expn = pa-expn; q = p; p = p-next = (term*)malloc(sizeof(term); pa = pa-next; q-next = null; free(p); pa = pa; t =

17、 s = (term*)malloc(sizeof(term); while(pa) q = s; s = s-next = (term*)malloc(sizeof(term); pa = pa-next; q-next = null; free(s); pa = pa; while(pa) pa-coef *= pb-coef; pa-expn += pb-expn; pa = pa-next; pb = pb-next; while(pb) p = r; s = t; while(p) s-coef = p-coef * pb-coef; s-expn = p-expn + pb-exp

18、n; p = p-next; s = s-next; pa = add(pa,t); pb = pb-next; return pa; / multiterm* c(term *pa, term *pb) int n; printf(再输入一一元多项式的项数); scanf(%d,&n); pb = creat(pb,n); pb = sortlow(pb); putchar();print(pa);putchar(); printf( * ); putchar();print(pb);putchar(); printf( = ); pa = multi(pa,pb); pa = sortlo

19、w(pa); print(pa); printf(n);pa=sorthigh(pa); print(pa);return pa; void main() term *m,*n; char s2; int i,n; printf(*n);puts(一元多项式计算系统-计科-0604-宋庆伟 学号:20064140421n); printf(*n);printf(请输入第一个一元多项式的项数:n);scanf(%d,&n); m = creat(m,n); m = sortlow(m); print(m); p:printf(n1:加n2:减n3:乘n4:退出n); getchar(); q: gets(s); if(s1!=0 | !isdigit(*s) printf(输入有误,请重新输入!);goto q; i = *s-48;