《数据结构课程设计一元稀疏多项式简单计数器.doc》由会员分享,可在线阅读,更多相关《数据结构课程设计一元稀疏多项式简单计数器.doc(18页珍藏版)》请在三一文库上搜索。
1、 数据结构 课程设计说明书题目: 一元稀疏多项式简单计数器学生姓名: 学 号: 院 (系): 理学院 专 业: 数学与应用数学 指导教师: 张洲平 2011年 12月23日陕 西 科 技 大 学 数据结构 课程设计任务书 理 学院 数学与应用数学 专业 班级 学生: 题目: 一元稀疏多项式简单计数器 课程设计从 2011 年 12 月 19 日起到 2011 年 12 月 23 日1、课程设计的内容和要求(包括原始数据、技术要求、工作要求等): 一元稀疏多项式简单计数器 (1) 输入并建立多项式 (2) 输出多项式,输出形式为整数序列:n,c1,e1,c2,e2cn ,en,其中n是多项式的项
2、数,ci,ei分别为第i项的系数和指数。序 列按指数降序排列。 (3) 多项式a和b相加,建立多项式a+b,输出相加的多项式。 (4) 多项式a和b相减,建立多项式a-b,输出相减的多项式。 用带头结点的单链表存储多项式。 2、对课程设计成果的要求包括图表、实物等硬件要求:1)根据课程设计题目要求编写所需程序代码 要求可以实现多项式的建立,以及两个多项式的相加、减,并且输出相加、减后所得的结果,同时用手算也可验证实验结果是否符合要求。 2)提交课程设计报告 按照具体要求完成课程设计报告,其中包括问题的描述、算法思想、程序实现结果、数据验证和实验总结等部分。 3、课程设计工作进度计划:时间设计任
3、务及要求1-10搜集学习相关资料,明确实验要求、目的1-11分析课题,理清编程思路1-12编写程序,修改程序1-13代入数据,进行整体调试,运行,再修改1-14性能分析,撰写设计说明书 指导教师: 日期: 2011-11-15 教研室主任: 日期: 目 录一、问题描述1二、算法思想2三、数据结构3四、设计模块划分4五、源程序5六、算法分析10七、运行结果11八、设计总结与体会13参考文献 141.问题描述:一元稀疏多项式简单计数器基本要求:(1) 输入并建立多项式(2) 输出多项式,输出形式为整数序列:n,c1,e1,c2,e2cn,en,其中n是多项式的项数,ci,ei分别为第i项的系数和指
4、数。序列按指数降序排列。(3) 多项式a和b相加,建立多项式a+b,输出相加的多项式。(4) 多项式a和b相减,建立多项式a-b,输出相减的多项式。用带头结点的单链表存储多项式。测试数据:(1)(2x+5x8-3.1x11)+(7-5x8+11x9)(2)(6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2+7.8x15)(3)(x+x2+x3)+0(4)(x+x3)-(-x-x-3)2.算法思想:(1)建立多项式一元多项式是由多个项的和组成的,将一元多项式的每个项用一结点表示,该结点中应包括该项的系数、该项的指数、指向下一项的指针,可以用线性表来依次输入各项结点,从而完成多项式
5、链表的建立,为了使原多项式各项顺序不变,故采用尾插法建表。(2)降幂输出多项式我们可以先设一个幂指数i为可输入的最大幂指数,然后从首元结点开始顺次查询每一结点的指数和i,若相等则输出该结点,否则,i-,继续从首元结点开始查询,重复上述过程,直到i为可输入的最小幂指数。这样,就按指数降幂输出了多项式。多项式的项数统计可以通过头结点的next来实现,若非空,count+,直到结点的指针域为空,这样,count就统计出了项数。(3) 多项式相加多项式的相加过程,其实就是相同指数的项的系数相加,不同指数的项复制到和多项式中,将结果用降幂输出函数输出。(4) 多项式相减多项式的相减过程,其实就是相同指数
6、的项的系数相减,对于不同指数的项,若是被减多项式,则将该结点复制输出,若是减多项式,则将该结点的系数变为原系数的相反数输出,将结果用降幂输出函数输出。3.数据结构:带头结点单链表抽象数据类型的结点结构定义如下:typedef struct Polynode /多项式结点int coef; /系数int exp; /指数Polynode *next;Polynode ,*Polylist;4.模块划分:(1) 带头结点的多项式的建立函数Polylist Polycreate()(2) 带头结点的多项式的降幂输出函数void printf(Polylist poly)(3) 带头结点的多项式的相加
7、函数Polylist Polyadd(Polylist a,Polylist b)(4) 带头结点的多项式的相减函数Polylist Polysub(Polylist a,Polylist b)(5) 主函数void main()5.源程序:#include#includetypedef struct Polyomial float coef; int expn; struct Polyomial *next;*Poly,Polyomial; /Poly为结点指针类型void Insert(Poly p,Poly h) if(p-coef=0) free(p); /系数为0时释放结点 else
8、 Poly q1,q2; q1=h;q2=h-next; while(q2&p-expnexpn) /查找插入位置 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; /InsertPoly CreatePoly(Poly head,int m)/建立一个头指针为head、项数为m的一元多项式 int i; Pol
9、y p; p=head=(Poly)malloc(sizeof(struct Polyomial); head-next=NULL; for(i=0;icoef,&p-expn); Insert(p,head); /调用Insert函数插入结点 return head;/CreatePolyvoid DestroyPoly(Poly p)/销毁多项式p Poly q1,q2; q1=p-next; q2=q1-next; while(q1-next) free(q1); q1=q2;/指针后移 q2=q2-next; void PrintPoly(Poly P) Poly q=P-next;
10、int flag=1;/项数计数器 if(!q) /若多项式为空,输出0 putchar(0); printf(n); return; while (q) if(q-coef0&flag!=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)
11、 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(-X%d,q-expn); q=q-next; flag+; /while printf(n);/PrintPolyint compare(Poly a,Poly b) if(a&b) if(!b|a-expnb-expn) return 1; else if(!a|a-expnexpn) return -1; else return 0; else if(!a
12、&b) return -1;/a多项式已空,但b多项式非空 else return 1;/b多项式已空,但a多项式非空/comparePoly AddPoly(Poly pa,Poly pb)/求解并建立多项式a+b,返回其头指针 Poly qa=pa-next; Poly qb=pb-next; Poly headc,hc,qc; hc=(Poly)malloc(sizeof(struct Polyomial);/建立头结点 hc-next=NULL; headc=hc; while(qa|qb) qc=(Poly)malloc(sizeof(struct Polyomial); switc
13、h(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; /switch if(qc-coef!=0) qc-next=hc-next; hc-next=qc; hc=qc; else free(qc);/当相加系数
14、为0时,释放该结点 /while return headc;/AddPolyPoly SubtractPoly(Poly pa,Poly pb) /求解并建立多项式a+b,返回其头指针 Poly h=pb; Poly p=pb-next; Poly pd; while(p) /将pb的系数取反 p-coef*=-1; p=p-next; pd=AddPoly(pa,h); for(p=h-next;p;p=p-next) /恢复pb的系数 p-coef*=-1; return pd;/SubtractPolyint main() int m,n,flag=0; float x; Poly pa
15、=0,pb=0,pc,pd,pe,pf;/定义各式的头指针,pa与pb在使用前付初值NULL printf(输入a的项数:); scanf(%d,&m); pa=CreatePoly(pa,m);/建立多项式a printf(输入b的项数:); scanf(%d,&n); pb=CreatePoly(pb,n);/建立多项式b for(;flag=0) printf(执行操作); scanf(%d,&flag); if(flag=1) printf(多项式a:);PrintPoly(pa); printf(多项式b:);PrintPoly(pb);continue; if(flag=2) pc
16、=AddPoly(pa,pb); printf(多项式a+b:);PrintPoly(pc); DestroyPoly(pc);continue; if(flag=3) pd=SubtractPoly(pa,pb); printf(多项式a-b:);PrintPoly(pd); DestroyPoly(pd);continue; if(flag=4) break; if(flag4) printf(Error!n);continue; /for DestroyPoly(pa); DestroyPoly(pb); return 0;6.算法分析建立多项式的时间复杂度为O(n),降幂输出多项式序列
17、算法,由于是对指数做的循环,每次循环都需要从首元结点查找到表尾,假设多项式开始为升幂排列,如x1+x2+x3+x4+xn,(这里n=20)其时间复杂度为n(n+1)/2,若指数不是连续的,则其时间复杂度加上O(n),所以此算法的时间复杂度为O(n2)。假设a有M项,b有N项,则加法和减法算法的时间复杂度度为M+N,算法中两多项式相加和相减时,a,b均需按升幂顺序输入结点。7.运行结果:(1)(2x+5x8-3.1x11)+(7-5x8+11x9)程序运行结果为:(2)(6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2+7.8x15)程序运行结果为:(3)(x+x2+x3)+0程
18、序运行结果为:(4) (x+x3)-(-x-x-3)程序运行结果为:8.设计体会与总结本次程序设计的总体思路明确,易懂,能够清楚的分辨出各模块的功能,利于用户的阅读、了解程序,该程序的执行过程是相当的易于读者使用,它会在每一步都提示用户接下来的输入数据。当然,本次课程设计还有许多的不足之处,在以后的不断学习当中我还会继续完善这个程序。在课程设计的过程中,深深地体会到了有算法思想和将此算法写成可执行程序,还是有一段距离的,程序出现错误并不可怕,只要我们肯耐心的去调试,去改进,最后一定会设计出一个比较好的程序。拿到课题后,我们首先要对要实现的功能以及数据结构有一个初步的规划,这样后边的工作才会顺利
19、进行。若是在编写或执行程序的过程中遇到了确实解决不了的问题,需要多和同学交流。通过做本次课程设计,使我收获了很多东西,知识这方面说起,以前觉得不管什么样的题还是编程,只要了解算法的思想就行了,到时候用的时候自然就会发挥出来,可这次的课程设计却告诉我并不是这样的,我在此次课程设计的编程的时候就遇到了这样的问题。觉得自己了解算法思想就一定能编出来,可是事实却不得不又拿起书来继续研究,继续查找一些相关的资料,与同学老师之间交流,互相学习之后,才将程序基本编写出来,但运行过程又出现了一些问题,需要不断调试,在老师和同学的帮助下,程序最终无误执行出来了。 总体来说,这次数据结构课设让我的编程能力有了进一步提高,我会继续努力提升自己的素养,为自己的未来做更多的积淀。当然,在以后的学习过程中我也会吸取前面的教训,在学习好课本知识的同时努力探索课外的相关知识,并且理论与实践结合起来,去检验对理论理解的不足之处,能够及时做到查漏补缺。还有在以后的学习生活中我会更注意与同学老师间的交流,拓展视野,互相学习,共同进步。参考文献:【1】数据结构C语言描述耿国华 高等教育出版社 2005年7月
链接地址:https://www.31doc.com/p-10033333.html