一元多项式的表示及其运算的研究_课程设计.doc

文晨宇 课程设计 一元多项式的表示及其运算的研究与实现 一元多项式的表示及其运算的研究与实现学生姓名：文晨宇 指导老师：乐晓波摘 要 一元多项式计算是用C语言设计一个一元多项式简单计算器。它能够实现按指数降序排列建立并输出多项式，并且能够完成两个多项式的相加，相减的运算和将其结果输出的功能。通过一元多项式可以体会链式存存储结构的优缺点和适用性。了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技术提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 关键词 C语言；一元多项式；链式存存储结构；指数降序排列1引言本课程设计主要研究线性表的存储结构及其基本操作的实现，并在此基础上研究一元多项式的表示及一元多项式加、减法运算的实现方法，并对相关算法进行分析。1.1课程设计背景为更好学习数据结构这一门理论和实践性均较强的基础课程，熟练掌握理论知识的同时更需要加强上机实践。本课程设计就是要达到理论与实际应用相结合，培养学生的动手能力，在实践理解各种算法，在创作中提升，使同学们能够根据数据对象的特性，学会数据组织的方法。1.1课程设计目的为了更好的学习数据结构，深刻理解数据结构在解决实际问题中的应用，体会其重要性，熟练掌握线性表、栈和队列、串、数组、树、图等常用的数据结构，熟悉各自的特点和应用场合。同时，锻炼自己独立分析理解问题的能力，学会根据不同的问题选择合适的数据结构，然后结合适当的算法解决问题。锻炼自己的设计和编写程序的技巧，进一步调试和测试自己所写的程序，使其功能更加完善，养成较好的编写程序习惯。提高综合运用所学的理论知识和方法独立分析和解决问题的能力1，训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。数据结构是一门理论实践性较强的软件基础课程，为了学好这门课程，必须在掌握理论知识，理解各种算法思想的同时，加强上机实践。本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。1.2课程设计内容本课程设计的主要内容是用C语言设计一个一元多项式简单计算器。它能够实现按指数降序排列建立并输出多项式，并且能够完成两个多项式的相加，相减的运算和将其结果输出的功能。通过实际项目的分析、设计、编码、测试等工作，体会数据结构在软件工程中的重要作用，并初步学会用C语言（或VC+、VB、JAVA等程序设计语言）开发和维护软件的基本方法。掌握算法的编写方法。同时按要求撰写课程设计报告书，并能正确编写分析、设计、编码、测试等技术文档。掌握类C语言的算法转换成C程序并上机调试的基本方法。设计一个C语言程序，该程序具能够实现以下的功能 （1）能够按照多项式变量的指数降序创建一个多项式； （2）能够对已创建的多项式进行显示； （3）能够对已创建的多项式之间的加法运算； （4）能够对已创建的多项式之间的减法运算； （5）能够对已创建的多项式进行删除； （6）能够实现计算器退出操作。2 设计内容 设计运行一元多项式计算器程序的主要思路与方案，同时设计出完成设计思路的系框架流程图2.1问题描述 用C语言编写一段程序，该程序的功能相当于一个一元多项式计算器。它能够实现按照指数降序排列建立并输出多项式，并且能够完成两个多项式的相加、相减的运算和将其结果输入的功能。2.2设计思路与方案一元多项式算法程序的数据结构是选择用带头结点的单链表存储多项式。虽然一元多项式可以用顺序和链式两种存储结果表示，但顺序结构的最大长度很难确定。比如当多项式的系数较大时，此时就会浪费巨大的存储空间，所以应该选择用链式存储结构来存储一元多项式。单链表1的结构体可以用来存储多项式的系数，指数，下一个指针3个元素，这样便于实现任意多项式的加法，减法运算。掌握一元多项式的表示的基本思想，完成一元多项式表示的基本结构的定义，并对相关算法进行分析与设计，实现一元多项式的基本操作（包括一元多项式的输入与输出、一元多项式的加法等基本操作）的相关算法的编码、调试、测试等工作。一元多项式的表示在计算机内可以用链表来表示，为了节省存储空间，只存储多项式中系数非零的项。链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的指针。创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加、相减操作。1 单连表的抽象数据类型定义： ADT List 数据对象：D=ai|aiElemSet,i=1,2,n,n0 数据关系：R1=| ai-1, aiD,i=2,n 基本操作： InitList（L） /操作结果：构造一个空的线性表 CreatPolyn(&L) /操作结果：构造一个以单连表存储的多项试 DispPolyn(L) /操作结果：显示多项试 Polyn(&pa,&pb) /操作结果：显示两个多项试相加，相减的结果 ADT List 2 本程序包含模块： typedef struct LNode /定义单链表 LNode,*LinkList; void InitList(LinkList &L) /定义一个空表 void CreatPolyn(LinkList &L) /用单链表定义一个多项式 void DispPolyn(LinkList L) /显示输入的多项式 void Polyn(LinkList &pa,LinkList &pb) void main() /定义一个单连表； coutendl *欢迎来到一元多项式计算程序 * next; Polyn qb=pb-next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial); 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; qb=qb-next; break; /switch if(qc-coef!=0) qc-next=hc-next; hc-next=qc; hc=qc; else free(qc);/当相加系数为0时，释放该结点 /while return headc;/AddPolyn33一元多项式的减法（1）功能：将两多项式相减。（2）数据流入：调用输入函数。（3）数据流出：多项式相减后的结果。（4）程序流程图：多项式的减法流程图如图3-3所示。（5）测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运图3-3 一元多项式减法运算流程图算。开始定义存储结果的空链 r是 否输出存储多项式的相减的链r结束是否同指数项系数相加后存入r中把p中各项系数改变符号后存入r中直接把q中各项存入r存储多项式2的空链Q是否为空存储多项式1的空链P是否为空合并同类项一元多项式减法程序：Polyn SubtractPolyn(Polyn pa,Polyn pb)/求解并建立多项式a+b，返回其头指针 Polyn h=pb; 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.4详细设计1. 根据题目要求采用单连表存储结构 typedef struct LNode /定义单链表 LNode,*LinkList; void InitList(LinkList &L) /定义一个空表 void CreatPolyn(LinkList &L) /用单链表定义一个多项式 void DispPolyn(LinkList L) /显示输入的多项式 void Polyn(LinkList &pa,LinkList &pb) 2主函数 main void main() LNode *L1,*L2; Polyn(L1,L2); 3. 函数的调用关系层次结构多项式 Polyn 用单链表定义多项式 CreatPolyn 定义一个空表 InitList 显示输入的多项式 DispPolyn4 调试及运行结果 通过以上数据对程序的测试分析可知，本程序较好的完成了题目的要求，能够完成两个多项式的排序，求值，相加，相减，相乘，并将结果输出。但在设计该算法时出现了一些问题，例如在建立链表时头指针的设立导致了之后运用到相关的指针时没能很好的移动指针，不能实现算法。为了是输入的数据按指数降序排列，可在数据的输入后做一个节点的排序函数，通过对链表排序后在进行之后加减运算。该程序在VC 6.0中调试通过，没有错误和警告，运行结果经过检验为正确，以下几图即为该程序运行结果效果图。 程序成功运行后的情况如图4-1所示。 图4-1 程序成功运行图假设我们创建两个多项式，一个为X2+2X3+3X4，如图4-2所示。 图4-2 创建多项式X2+2X3+3X4创建另一个多项式为2X3+3X+4X2+4X3，如图4-3所示。图4-3创建第二个多项式2X3+3X+4X2+4X3此时，由程序界面可知，按1即输出多项式a和b，按2即进行a+b的运算，按3即进行a-b的运算，我们首先进行输出多项式的操作，如图4-4所示。图4-4, 进行多项式输出然后我们再进行多项式的相加操作，如图4-5所示。图4-5 多项式的相加再进行多项式的相减操作，如图4-6所示。图4-6 多项式的相减最后进行退出操作，如图4-7所示。图4-7 进行退出操作5 设计体会与总结5.1设计体会这次的课程设计是通过用我们所学过的带有头结点的单链表的数据结构为基础建立一元多项式。在进一步设计一个一元多项式简单计数器。该计数器能够按照指数降序排序建立并输出多项式，并且能够完成两个多项式的相加，相减，并输出结果。经过这次课程设计，我对数据结构这门课程有了进一步的理解，对也进一步了解了C语言的重要性，知道了其强大的功能。也提高了我分析问题、解决问题，从而运用所学知识解决实际问题的能力。另外通过这次课程设计练习，使我更深刻地理解了语言的精髓-指针的使用。完成整个程序设计使我对指针掌握的更加熟练。同时通过直接对链表的操作，加深了对数据结构的理解和认识。在完成课程设计的过程，我主动查阅了相关资料，学到了不少课本上没有的技术知识。我也深刻认识到算法在程序设计中的重要性，一个完整的程序总是由若干个函数构成的，这些相应的函数体现了算法的基本思想。通过这次课程设计，我发现了自己平时学数据结构这门课还有很多没有注意到的地方。虽然说这次的课题顺利完成了，但我对数据结构这门课的学习还没有完成，以后还必须对数据结构进行复习巩固。以前在数据结构这门课上，我学到的仅仅是理论知识，但这次的课程设计让我感受到课上的东西用到实际问题的难处。在今后对计算机方面知识的学习中，我要注意理论联系实际，这样才可以把学到的东西运用出来，真正的做到学以致用！5.2总结这次课程设计对我来说是印象十分深刻的，在这次课程设计中，我遇到了不少困难，但是在我的坚持和虚心请教中得到了顺利解决。在这次课程设计中，我发现理论必须和实践相结合，才能真正学会课程设计，才能完成一个课题。在这次设计中我参考了不少书籍，从中学到了课程中无法学到的许多东西，对此我感到很兴奋。原来不断的学习，不断的探索是苦中带着甜，虽然经历不少弯曲，经历了不少挫折，但当程序调试成功后，当运行能达到要求后，我感到十二分的成就感。在这个设计过程中，不懂的可以虚心学习与同学交流。态度是成功的试金石。编程是一件枯燥乏味工作，但是只要认真专研，我们会从中学到很多在课本上学不到或者无法在课堂上掌握的知识，同时也能从中感受到编程的乐趣。兴趣是可以培养的，只要坚持下去，面对困难我们总能够找到解决问题的方法。一元多项式的加、减法有关算法，程序虽然不是很大，这次我还是完成了这一任务。在这次课程设计中，使我充分认识到课程设计在开发软件过程中的重要性。最后我想感谢老师能给我们这次实践的机会，让我能学到这么多，不仅仅是课本上的知识学到了书本上的知识，还加强了动手能力和独立思考的能力，更学会了团结协作的重要性。我相信，这次的课程设计经历会让我们在未来的发展中起到重要的导向作用，能让我们在社会中不管遇到什么样的困难都能够通过自己的努力，队伍的合作去克服它，让我们在今后的社会中勇往直前，所以我希望在今后的学习中，老师能给于我们更多的动手机会，让我们能在动手中学到更多的知识。参考文献 1谭浩强.C语言程序设计（第3版）M.北京：清华大学出版社，2005 2严蔚敏，吴伟明.数据结构（C语言版）M.北京：清华大学出版社,2003 3赵文静. 数据结构与算法M. 北京:科学出版社，2005.8：41-654 F.Brokken and K.Kubat. C+ Annotations J. ICCE，University of Groningen 2011, 33(3): 62 67.附录：源程序清单#include#includetypedef struct Polynomial float coef; int expn; struct Polynomial *next;*Polyn,Polynomial; /Polyn为结点指针类型void Insert(Polyn p,Polyn h) if(p-coef=0) free(p); /系数为0的话释放结点 else Polyn 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; /InsertPolyn CreatePolyn(Polyn head,int m)/建立一个头指针为head、项数为m的一元多项式 int i; Polyn p; p=head=(Polyn)malloc(sizeof(struct Polynomial); head-next=NULL; for(i=0;icoef,&p-expn); Insert(p,head); /调用Insert函数插入结点 return head;/CreatePolynvoid DestroyPolyn(Polyn p)/销毁多项式p Polyn q1,q2; q1=p-next; q2=q1-next; while(q1-next) free(q1); q1=q2;/指针后移 q2=q2-next; void PrintPolyn(Polyn P) Polyn q=P-next; 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) 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);/PrintPolynint compare(Polyn a,Polyn b) if(a&b) if(!b|a-expnb-expn) return 1; else if(!a|a-expnexpn) return -1; else return 0; else if(!a&b) return -1;/a多项式已空，但b多项式非空 else return 1;/b多项式已空，但a多项式非空/comparePolyn AddPolyn(Polyn pa,Polyn pb)/求解并建立多项式a+b，返回其头指针 Polyn qa=pa-next; Polyn qb=pb-next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial);/建立头结点 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; qb=qb-next; break; /switch if(qc-coef!=0) qc-next=hc-next; hc-next=qc; hc=qc; else free(qc);/当相加系数为0时，释放该结点 /while return headc;/AddPolynPolyn SubtractPolyn(Polyn pa,Polyn pb)/求解并建立多项式a+b，返回其头指针 Polyn h=pb; Polyn p=pb-