《一元多项式乘法.doc》由会员分享，可在线阅读，更多相关《一元多项式乘法.doc（19页珍藏版）》请在金锄头文库上搜索。
1、学 号 11710201数据结构A课程设计设计说明书一元多项式乘法起止日期： 2013年 12月30 日 至 2014 年 1月3日学生姓名班级成绩指导教师(签字)计算机系2014年1 月 3 日天津城建大学课程设计任务书20132014学年第1学期 计算机 系 11计算机 专业 11计算机2 班级课程设计名称： 数据结构课程设计 设计题目： 一元多项式乘法 完成期限：自 2013 年 12 月 30 日至 2014 年 1 月 3 日共 1 周设计依据、要求及主要内容（可另加附页）：1、一元多项式乘法1) 问题描述已知A(x)=a0+a1x+a2x2+anxn和B(x)=b0+b1x+b2x
2、2+bmxm，并且在A(x)和B(x)中指数相差很多，求A(x)=A(x)*B(x)。2) 基本要求(1)设计存储结构表示一元多项式；(2)设计算法实现一元多项式乘法；(3)分析算法的时间复杂度和空间复杂度。指导教师（签字）：教研室主任（签字）：郝琨批准日期：2013年12月30日 目录一、设计目的1二、设计要求1三、设计内容13.1需求分析13.2问题求解23.3总体设计23.4 详细设计3四、核心源程序清单和执行结果44.1 源程序44.2 运行结果12五、总结14六、参考文献15一、设计目的 将理论教学中涉及到的知识点贯穿起来，对不同的数据类型、程序控制结构、数据结构作一比较和总结，结合
3、设计题目进行综合性应用，对所学知识达到融会贯通的程度。通过课程设计，学生在下述各方面的能力应该得到锻炼： （1）进一步巩固、加深学生所学专业课程C+语言教程的基本理论知识，理论联系实际，进一步培养学生综合分析问题，解决问题的能力。 （2）全面考核学生所掌握的基本理论知识及其实际业务能力，从而达到提高学生素质的最终目的。 （3）利用所学知识，开发小型应用系统，掌握运用C+语言编写调试应用系统程序，训练独立开发应用系统，进行数据处理的综合能力。 （4）对于给定的设计题目，如何进行分析，理清思路，并给出相应的数学模型。 （5）掌握自顶而下的设计方法，将大问题进行模块化，领会结构化程序设计的方法。 （
4、6）熟练掌握C+语言的基本语法，灵活运用各种数据类型。 （7）进一步掌握在集成环境下如何调试程序（单步调试，设置断点、观察表达式，分块调试）和修改程序。二、设计要求 在本课程设计过程中要求学生：（1）重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务；（2）按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩。（3）学生在接受设计任务后，首先要按设计任务书的要求编写设计进程表。（4）认真编写课程设计报告。三、设计内容3.1需求分析程序是要完成两个一元多
5、项式乘法的功能。要求输入两个多项式中每个数据项的系数和指数，从而得到一个新的多项式，这个多项式是输入的两个多项式的乘积。3.2问题求解用数据结构来解决这个问题的话，首先要设计多项式的存储结构，然后设计算法，这个时候要注意的就是算法的时间复杂度和空间复杂度。3.3总体设计开始输入A,B式子值进行计算输出结果值对A,B进行一次判断(稀?疏?)结束3.4 详细设计1、数据结构的设计 在该程序中分别分为顺序存储和链式存储结构。2、算法的设计本程序主要分为四大模块主程序模块输入模块：通过main函数输入输出模块（升幂降幂）：PrintPolyn函数实现输出数据处理模块（多项式的乘法）：通过一元多项式的P
6、olynomial基本操作实现3、抽象数据类型的设计一元多项式抽象数据类型的定义;抽象数据类型Polynomial的定义。 四、核心源程序清单和执行结果4.1 源程序#includeusing namespace std;struct term/顺序表和链表的的定义float xishu; /系数int zhishu; /指数;struct LNode term data; /term多项式值struct LNode *next;typedef LNode* polynomail;/*合并同类项*/polynomail hebing(polynomail Head)polynomail r,q
7、,p,Q;for(q=Head-next;q!=NULL;q=q-next)/合并同类项for(p=q-next,r=q;p!=NULL;)if(q-data.zhishu=p-data.zhishu)/指数相等 系数相加 q-data.xishu=q-data.xishu+p-data.xishu;r-next=p-next;Q=p;p=p-next;delete Q;/释放pelser=r-next;p=p-next;return Head;/得到不含同类项的多项式/*又小到大排列*/void arrange1(polynomail pa)polynomail h=pa,p,q,r;for
8、(p=pa;p-next!=NULL;p=p-next);r=p;/r指向参与比较的最后一个while(h-next!=r)/大的沉底for(p=h;p-next!=r&p!=r;p=p-next)if(p-next-data.zhishup-next-next-data.zhishu)/比较指数的大小q=p-next-next;p-next-next=q-next;/指数大的向前移动q-next=p-next;p-next=q;r=p;/r指向参与比较的最后一个，不断向前移动 /*由大到小排序*/void arrange2(polynomail pa) polynomail h=pa,p,q
9、,r;for(p=pa;p-next!=NULL;p=p-next); r=p;while(h-next!=r)/小的沉底for(p=h;p-next!=r&p!=r;p=p-next)if(p-next-data.zhishunext-next-data.zhishu)/指数比较大小 q=p-next-next;p-next-next=q-next;/指数小的向后移动q-next=p-next;p-next=q;r=p;/r指向参与比较的最后一个，不断向前移动 /*判断多项式的稀疏 */bool judge(polynomail Head)/逻辑变量字符boolarrange2(Head);
10、polynomail p;p=Head-next;bool xi=false;while(p!=NULL&p-next!=NULL&!xi)if(p-data.zhishu-p-next-data.zhishu1)xi=true;p=p-next;return xi;/*打印多项式,求项数*/void printpolyn(polynomail P)int i;polynomail q;if(P=NULL)cout无项next=NULL)coutY=0endl;elsecoutnext;i=1;if(q-data.xishu!=0&q-data.zhishu!=0)coutdata.xishu
11、Xdata.zhishu;i+; if(q-data.zhishu=0&q-data.xishu!=0)coutdata.xishu;/打印第一项q=q-next;if(q=NULL)coutdata.xishu!=0&q-data.zhishu!=0)if(q-data.xishu0) cout+;coutdata.xishuXdata.zhishu;i+;if(q-data.zhishu=0&q-data.xishu!=0) if(q-data.xishu0) cout+;coutdata.xishu;q=q-next;if(q=NULL)coutendl;break; /*1、创建并初始化多项式链表*/polynomail creatpolyn(int m)polynomail Head,r,s;int i;Head=new LNode;r=Head;for(i=0;im;i+) s=new LNode;cout请输入第i+1s-data.xishus-data.zhishu;r-next=s; r=s;r-next=NULL;if(m1)Head=hebing(H
