《一元多项式的表示及其运算的研究_课程设计》由会员分享，可在线阅读，更多相关《一元多项式的表示及其运算的研究_课程设计（26页珍藏版）》请在金锄头文库上搜索。
1、 课程设计 一元多项式的表示及其运算的研究与实现 第 1 页/共 26 页一元多项式的表示及其运算的研究与实现一元多项式的表示及其运算的研究与实现学生姓名：学生姓名： 指导老师：指导老师： 摘摘 要要 一元多项式计算是用 C 语言设计一个一元多项式简单计算器。它能够实现按指数降序排列建立并输出多项式，并且能够完成两个多项式的相加，相减的运算和将其结果输出的功能。通过一元多项式可以体会链式存存储结构的优缺点和适用性。了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技术提高综合运用所学的理论知识和方法独立分析和解
2、决问题的能力； 关键词关键词 C 语言；一元多项式；链式存存储结构；指数降序排列课程设计 一元多项式的表示及其运算的研究与实现 第 2 页/共 26 页1 1 引言引言本课程设计主要研究线性表的存储结构及其基本操作的实现，并在此基础上研究一元多项式的表示及一元多项式加、减法运算的实现方法，并对相关算法进行分析。1.11.1 课程设计背景课程设计背景为更好学习数据结构这一门理论和实践性均较强的基础课程，熟练掌握理论知识的同时更需要加强上机实践。本课程设计就是要达到理论与实际应用相结合，培养学生的动手能力，在实践理解各种算法，在创作中提升，使同学们能够根据数据对象的特性，学会数据组织的方法。1.1
3、1.1 课程设计目的课程设计目的为了更好的学习数据结构，深刻理解数据结构在解决实际问题中的应用，体会其重要性，熟练掌握线性表、栈和队列、串、数组、树、图等常用的数据结构，熟悉各自的特点和应用场合。同时，锻炼自己独立分析理解问题的能力，学会根据不同的问题选择合适的数据结构，然后结合适当的算法解决问题。锻炼自己的设计和编写程序的技巧，进一步调试和测试自己所写的程序，使其功能更加完善，养成较好的编写程序习惯。提高综合运用所学的理论知识和方法独立分析和解决问题的能力1，训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 。数据结构是一门理论实践性较强的软件基
4、础课程，为了学好这门课程，必须在掌握理论知识，理解各种算法思想的同时，加强上机实践。本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。课程设计 一元多项式的表示及其运算的研究与实现 第 3 页/共 26 页1.21.2 课程设计内容课程设计内容本课程设计的主要内容是用 C 语言设计一个一元多项式简单计算器。它能够实现按指数降序排列建立并输出多项式，并且能够完成两个多项式的相加，相减的运算和将其结果输出的功能。通过实际项目的分析、设计、编码、测试等工作，体会数据结构在
5、软件工程中的重要作用，并初步学会用 C 语言（或 VC+、VB、JAVA 等程序设计语言）开发和维护软件的基本方法。掌握算法的编写方法。同时按要求撰写课程设计报告书，并能正确编写分析、设计、编码、测试等技术文档。掌握类 C 语言的算法转换成 C 程序并上机调试的基本方法。设计一个 C 语言程序，该程序具能够实现以下的功能（1）能够按照多项式变量的指数降序创建一个多项式；（2）能够对已创建的多项式进行显示；（3）能够对已创建的多项式之间的加法运算；（4）能够对已创建的多项式之间的减法运算；（5）能够对已创建的多项式进行删除；（6）能够实现计算器退出操作。课程设计 一元多项式的表示及其运算的研究与
6、实现 第 4 页/共 26 页2 2 设计内容设计内容设计运行一元多项式计算器程序的主要思路与方案，同时设计出完成设计思路的系框架流程图2.12.1 问题描述问题描述用 C 语言编写一段程序，该程序的功能相当于一个一元多项式计算器。它能够实现按照指数降序排列建立并输出多项式，并且能够完成两个多项式的相加、相减的运算和将其结果输入的功能。2.22.2 设计思路与方案设计思路与方案一元多项式算法程序的数据结构是选择用带头结点的单链表存储多项式。虽然一元多项式可以用顺序和链式两种存储结果表示，但顺序结构的最大长度很难确定。比如当多项式的系数较大时，此时就会浪费巨大的存储空间，所以应该选择用链式存储结
7、构来存储一元多项式。单链表1的结构体可以用来存储多项式的系数，指数，下一个指针 3 个元素，这样便于实现任意多项式的加法，减法运算。掌握一元多项式的表示的基本思想，完成一元多项式表示的基本结构的定义，并对相关算法进行分析与设计，实现一元多项式的基本操作（包括一元多项式的输入与输出、一元多项式的加法等基本操作）的相关算法的编码、调试、测试等工作。一元多项式的表示在计算机内可以用链表来表示，为了节省存储空间，只存储多项式中系数非零的项。链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的指针。创建一元多项式链表，对一元多项式的运算中会出现
8、的各种可能情况进行分析，实现一元多项式的相加、相减操作。1 1 单连表的抽象数据类型定义：单连表的抽象数据类型定义：ADT List 数据对象：D=ai|aiElemSet,i=1,2,n,n0 数据关系：R1=| ai-1, aiD,i=2,n 课程设计 一元多项式的表示及其运算的研究与实现 第 5 页/共 26 页基本操作：InitList（L）/操作结果：构造一个空的线性表 CreatPolyn( void InitList(LinkList Polyn qb=pb-next;Polyn headc,hc,qc;hc=(Polyn)malloc(sizeof(struct Polynom
9、ial); hc-next=NULL;headc=hc;while(qa|qb)qc=(Polyn)malloc(sizeof(struct Polynomial);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;课程设计 一元多项式的表示及其运算的研究与实现
10、第 10 页/共 26 页qb=qb-next;break; /switchif(qc-coef!=0)qc-next=hc-next;hc-next=qc;hc=qc;else free(qc);/当相加系数为 0 时，释放该结点/whilereturn headc;/AddPolyn课程设计 一元多项式的表示及其运算的研究与实现 第 11 页/共 26 页3 33 3 一元多项式的减法一元多项式的减法（1）功能：将两多项式相减。（2）数据流入：调用输入函数。（3）数据流出：多项式相减后的结果。（4）程序流程图：多项式的减法流程图如图 3-3 所示。（5）测试要点：两多项式是否为空，为空则提
11、示重新输入，否则，进行运算。开始定义存储结果的空链 r是 否输出存储多项式的相减的链 r结束是否同指数项系数相加后存入 r 中把 p 中各项系数 改变符号后存入 r 中直接把 q 中 各项存入 r存储多项式 2 的 空链 Q 是否为空存储多项式 1 的空 链 P 是否为空合并同类项图图 3-33-3 一元多项式减法运算流程图一元多项式减法运算流程图课程设计 一元多项式的表示及其运算的研究与实现 第 12 页/共 26 页一元多项式减法程序：一元多项式减法程序：Polyn SubtractPolyn(Polyn pa,Polyn pb)/求解并建立多项式 a+b，返回其头指针Polyn h=pb
12、;Polyn p=pb-next;Polyn pd;while(p) /将 pb 的系数取反p-coef*=-1;p=p-next;pd=AddPolyn(pa,h);for(p=h-next;p;p=p-next) /恢复 pb 的系数p-coef*=-1;return pd;/SubtractPolyn3.43.4 详细设计详细设计1. 根据题目要求采用单连表存储结构根据题目要求采用单连表存储结构typedef struct LNode /定义单链表LNode,*LinkList;void InitList(LinkList Polyn(L1,L2); 3.3. 函数的调用关系层次结构函数
13、的调用关系层次结构多项式 Polyn 用单链表定义多项式 CreatPolyn 定义一个空表 InitList 显示输入的多项式 DispPolyn课程设计 一元多项式的表示及其运算的研究与实现 第 14 页/共 26 页4 4 调试及运行结果调试及运行结果通过以上数据对程序的测试分析可知，本程序较好的完成了题目的要求，能够完成两个多项式的排序，求值，相加，相减，相乘，并将结果输出。但在设计该算法时出现了一些问题，例如在建立链表时头指针的设立导致了之后运用到相关的指针时没能很好的移动指针，不能实现算法。为了是输入的数据按指数降序排列，可在数据的输入后做一个节点的排序函数，通过对链表排序后在进行
14、之后加减运算。该程序在 VC 6.0 中调试通过，没有错误和警告，运行结果经过检验为正确，以下几图即为该程序运行结果效果图。 程序成功运行后的情况如图 4-1 所示。图图 4-14-1 程序成功运行图程序成功运行图假设我们创建两个多项式，一个为 X2+2X3+3X4，如图 4-2 所示。图图 4-24-2 创建多项式创建多项式 X2+2X3+3X4X2+2X3+3X4课程设计 一元多项式的表示及其运算的研究与实现 第 15 页/共 26 页创建另一个多项式为 2X3+3X+4X2+4X3，如图 4-3 所示。图图 4-34-3 创建第二个多项式创建第二个多项式 2X3+3X+4X2+4X32X
15、3+3X+4X2+4X3此时，由程序界面可知，按 1 即输出多项式 a 和 b，按 2 即进行 a+b 的运算，按 3 即进行 a-b 的运算，我们首先进行输出多项式的操作，如图 4-4 所示。图图 4-4,4-4, 进行多项式输出进行多项式输出课程设计 一元多项式的表示及其运算的研究与实现 第 16 页/共 26 页然后我们再进行多项式的相加操作，如图 4-5 所示。图图 4-54-5 多项式的相加多项式的相加再进行多项式的相减操作，如图 4-6 所示。图图 4-64-6 多项式的相减多项式的相减最后进行退出操作，如图 4-7 所示。图图 4-74-7 进行退出操作进行退出操作课程设计 一元多项式的表示及其运算的研究与实现 第 17 页/共 26 页5 5 设计体会与总结设计体会与总结5.15.1 设计体会设计体会这次的课程设计是通过用我们所学过的带有头结点的单链表的数据结构为基础建立一元多项式。在进一步设计一个一元多项式简单计数器。该计数器能够按照指数降序排序建立并输出多项式，并且能够完成两个多项式的相加，相减，并输出结果。经过这次课程设计，我对数据结构这门课程有了进一步的理解，对也进一步了解了 C 语言的重要性，知道了其强大的功能。也提高了我分析问题、解决问题，从而运用所学知识解决实际问题的能力。另
