课程设计一元多项式.doc

数据结构课程设计设计说明书一元多项式求值算法的实现学生姓名 姚伟凡 学 号 1418014074 班 级 计算机1403班 成 绩 指导教师申静 数学与计算机科学学院2016年1月4日 课程设计任务书20152016学年第一学期课程设计名称： 数据结构课程设计 课程设计题目： 一元多项式求值算法的实现 完 成 期 限：自 2015年 12 月21日至 2016年 1 月 4 日共 2 周设计内容：1.任务说明(1)输入并建立多项式；(2)输出多项式；(3)两个多项式相加，建立并输出和多项式；(4)两个多项式相减，建立并输出差多项式。2.要求1）问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？ 2）逻辑设计：写出抽象数据类型的定义，各个主要模块的算法，并画出模块之间的调用关系图；3）详细设计：定义相应的存储结构并写出各函数的伪码算法。4）程序编码：把详细设计的结果进一步求精为程序设计语言程序。5）程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。6）结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析；7）编写课程设计报告；3.参考资料指导教师：申静 教研室负责人：李婧 课程设计评阅评语： 指导教师签名： 年 月 日摘 要一元多项式计算是用C语言设计一个一元多项式简单计算器。它能够实现按指数降序排列建立并输出多项式，并且能够完成两个多项式的相加，想减的运算和将其结果输入的功能。体会链式存存储结构的优缺点和适用性。了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技提高综合运用所学的理论知识和方法独立分析和解决问题的能力；加深对常用数据结构的理解，强化学生的逻辑思维能力和动手能力，巩固良好的编程习惯，掌握工程软件设计的基本方法，为后续课程的学习打下坚实基础。关键词：一元多项式；运算；输入；C+ 目 录1.课题描述12. 需求分析23.概要设计34.详细设计45.程序编码-78.总结14参考文献151.课题描述 这个程序设计了对一元多项式的加减乘法运算，输入和输出一元多项式，运算一元多项式的和以及一元多项式的差还有一元多项式的乘积并输出。一元多项式的表示在计算机内可以用链表来表示，链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的指针。创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加、相减，相乘操作。2. 需求分析一元多项式算法程序主要从技术的角度来分析可行性。技术上的可行性研究要分析技术条件能否顺利完成开发工作，硬、软件能否满足开发者的需要等。该系统采用了WindowsXP操作系统结合VisualC+6.0、TC2.0等软件开发平台已成熟可行。硬件方面，科技飞速发展的今天，硬件更新的速度越来越快，容量越来越大，可靠性越来越高，其硬件平台也比较能满足此系统的需要。此外，还有经济可行性，用户使用可行性，法律可行性等可行性研究，这里从简省去。3.概要设计一元多项式的表示在计算机内可以用链表来表示，为了节省存储空间，只存储多项式中系数非零的项。链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的指针。创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加、相减操作。 4.详细设计一元多项式的创建建立一元多项式的链表，按程序提示输入一元多项式的项数，以及一元多项式的系数与指数，对一元多项式中会出现的各种情况进行分析，实现对一元多项式的加减法操作。开始 申请结点空间num输入多项式的项数指针数组tempi中（i=1num）输入多项式各项的系数 x, 指数 y输出已输入的多项式 合并同类项结束否是 是否输入正确 一元多项式的创建流程图一元多项式的加法对于一元多项式中指数相同的项，对应系数相加，若得到的和不为0，则作为“和多项式”中的一项，对于两个一元多项式所有指数不相同的项，直接复抄到“和多项式”中。开始定义存储结果的空链 r是 否输出存储多项式的和的链r结束是否同指数项系数相加后存入r中直接把p中各项存入r中直接把q中各项存入r存储多项式2的空链Q是否为空存储多项式1的空链P是否为空合并同类项 一元多项式加法流程图 一元多项式的减法对于一元多项式中指数相同的项，对应系数相减，若得到的差不为0，则作为“和多项式”中的一项，对于一元多项式指数不相同的项，按减法法则直接复抄到“和多项式”中。开始定义存储结果的空链 r是 否输出存储多项式的和的链r结束是否同指数项系数相加后存入r中把p中各项系数改变符号后存入r直接把q中各项存入r存储多项式2的空链Q是否为空存储多项式1的空链P是否为空合并同类项 一元多项式减法流程图5.程序编码 对于一元多项式的编码实现，首先实现一元多项式的建立，输入，输出，求和，求差，求积的算法，最后用主函数调用子函数，实现完整编码。#include#includeusing namespace std;#define N 1000#define INF 65535typedef struct int aN;/记录多项式 int len;/记录多项式的长度Ploy; void ADD(Ploy A,Ploy B,Ploy *M)/*多项式A与多项式B相加，得到多项式M*/ int la=A.len,lb=B.len; int i; M-len=lalb?la:lb;/若lalb则输出la否则输出lb for(i=0;i=la&iai=A.ai+B.ai; while(iai=A.ai;i+; while(iai=B.ai;i+; return ;void SUB(Ploy A,Ploy B,Ploy *M)/*多项式A与多项式B相减（A-B），得到多项式M*/ int la=A.len,lb=B.len,i; M-len=lalb?la:lb; for(i=0;i=la&iai=A.ai-B.ai; while(iai=A.ai;i+; while(iai=0-B.ai;i+; return ; void MUL(Ploy A,Ploy B,Ploy *M)/*多项式A与多项式B相乘，得到多项式M*/ int i,j; for(i=0;iai=0; for(i=0;i=A.len;i+) for(j=0;jai+j+=A.ai*B.aj; M-len=A.len+B.len; return ;void GetPloy(Ploy *A)/输入建立多项式 int i,coef,expn; int maxe=0; char ch; printf(请输入每个项的系数及对应的指数，指数为负数时标志输入结束！n); for(i=0;iai=0; scanf(%d%d,&coef,&expn); while(expn=0) if(expnmaxe) maxe=expn; if(A-aexpn!=0) printf(你输入的项已经存在，是否更新原数据？（Y/N）); cinch; if(ch=Y|ch=y) A-aexpn=coef;printf(更新成功，请继续输入！n); else printf(请继续输入！n); else A-aexpn=coef; scanf(%d%d,&coef,&expn); A-len=maxe; return ;void PrintPloy(Ploy A)/按降幂排序输出多项式 int i; printf( %dx%d ,A.aA.len,A.len); for(i=A.len-1;i=1;i-) if(A.ai=0) ; else if(A.ai=1) printf( + x%d ,i); else if(A.ai=-1) printf( - x%d ,i); else if(A.ai0) printf(+ %dx%d ,A.ai,i); else printf(- %dx%d ,-A.ai,i); if(A.a0=0) ; else if(A.a00) printf( + %d,A.a0);/打印x的0次项 else printf( - %d,-A.a0); printf(n); return ; void Menu() printf(n*1、多项式相加); printf(n*2、多项式相减); printf(n*3、多项式相乘); printf(n*4、退出 *n); printf(请输入您需要的操作n); return ; int main() Ploy A,B,M; char n,ch,sh; printf(请输入多项式A：n); GetPloy(&A); printf(请输入多项式B：n); GetPloy(&B); while(1) Menu(); cinn; while(2) if(n=1) ADD(A,B,&M); PrintPloy(M); break; else if(n=2) SUB(A,B,&M); PrintPloy(M); break; else if(n=3) MUL(A,B,&M);PrintPloy(M); break; else if(n=4) break; else printf(输入的选项号不对，请重新输入n); break; return 0; 6.程序结果 一元多项式建立与相加输出结果展 一元多项式相减并输出结果展示图 一元多项式相乘并输出结果展示图7.结果分析问题和改进思想：在开始设计程序的时候，输出结果很乱，并且容易出现逻辑错误。然后在编写输出多项式的函数时，建立了一个按升序输出的函数，才把程序改好。建立输入多项式的函数时，以指数为负数标志输出结束。建立时还会出现一个问题，就是输入时会输入重复的指数的项，这时计算机就会提醒用户是否更新数据。开始的时候没有注意这个问题，输入数据时会出错，导致程序运行时会出现逻辑混乱错误。后来才改好了。以后会多注意这些问题。8.总结在此次课程设计中，运用VC+软件编程，学习到了很多知识，不仅巩固了以前的知识，还掌握了一些新的知识。这次的设计题目是一元多项式的加法，减法，乘法运算的实现，包括一元多项式的建立以及运算后结果的输出，完成这次的题目