一元多项式的表示及其运算的研究 课程设计
一元多项式的表示及其运算的研究与实现
学生姓名：文晨宇指导老师：乐晓波
摘要一元多项式计算是用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|ai∈ElemSet,i=1,2,…,n,n≥0} 数据关系：R1={
基本操作：
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()
{
//定义一个单连表；
cout< LNode *L1,*L2; Polyn(L1,L2); } 2.3系统框架的设计 程序运行后，各模块之间的调用关系如下图2-1所示。 图2-1 系统框架图 用户菜单 多项式链表 各函数 退出 指针数组 主函数 3 程序设计 程序为了实现了多项式的创建、多项式的加法、减法运算以及多项式的清除。为完成这些功能，还用到了一些辅助函数： ： 3．1、输入输出 （1）功能：将要进行运算的多项式输入输出。 （2）数据流入：要输入的多项式的系数与指数。 （3）数据流出：合并同类项后的多项式。 （4）程序流程图：多项式输入流程图如图3.-1所示。 （5）测试要点：输入的多项式是否正确，若输入错误则重新输入 开始 申请结点空间 输入多项式的项数 输入多项式各项的系数x, 指数y 输出已输入的多项式 否 是否输入正确 是 合并同类项 结束 图3-1 输入输出流程图 3.2 一元多项式的加法运算 （1）功能：将两多项式相加。 （2）数据流入：输入函数。 （3）数据流出：多项式相加后的结果。 （4）程序流程图：多项式的加法流程图如图3-2所示。 （5）测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运算。 图3-2 一元多项式的加法运算 一元多项式加法运算程序： Polyn AddPolyn(Polyn pa,Polyn pb){ 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; }//AddPolyn 3．3一元多项式的减法 （1）功能：将两多项式相减。 （2）数据流入：调用输入函数。 （3）数据流出：多项式相减后的结果。 （4）程序流程图：多项式的减法流程图如图3-3所示。 （5）测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运 算。 开始 定义存储结果的空链 r 是 否 输出存储多项式的相减的链r 结束 是 否 同指数项系数相加后存入r 中 把p 中各项系数改变符号后存入r 直接把q 中各项存入r 存储多项式2的空链Q 是否为空 存储多项式1的空链P 是否为空 合并同类项 图3-3 一元多项式减法运算流程图 一元多项式减法程序： 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; }//SubtractPolyn 3.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 显示输入的多项式DispPolyn 4 调试及运行结果 通过以上数据对程序的测试分析可知，本程序较好的完成了题目的要求，能够完成两个多项式的排序，求值，相加，相减，相乘，并将结果输出。但在设计该算法时出现了一些问题，例如在建立链表时头指针的设立导致了之后运用到相关的指针时没能很好的移动指针，不能实现算法。为了是输入的数据按指数降序排列，可在数据的输入后做一个节点的排序函数，通过对链表排序后在进行之后加减运算。该程序在VC 6.0中调试通过，没有错误和警告，运行结果经过检验为正确，以下几图即为该程序运行结果效果图。程序成功运行后的情况如图4-1所示。 图4-1 程序成功运行图 假设我们创建两个多项式，一个为X^2+2X^3+3X^4，如图4-2所示。 图4-2 创建多项式X^2+2X^3+3X^4 创建另一个多项式为2X^3+3X+4X^2+4X^3，如图4-3所示。 图4-3创建第二个多项式2X^3+3X+4X^2+4X^3 此时，由程序界面可知，按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-65 [4] F.Brokken and K.Kubat. C++ Annotations [J].ICCE，University of Groningen 2011, 33(3): 62 – 67. 附录：源程序清单 #include #include typedef 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->expn 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; 1.1设计内容及要求 1)设计内容 （1）使用顺序存储结构实现多项式加、减、乘运算。 例如： 10321058)(2456+-+-+=x x x x x x f ,x x x x x x g +--+=23451020107)( 求和结果：102220128)()(2356++-+=+x x x x x g x f （2）使用链式存储结构实现多项式加、减、乘运算， 10305100)(1050100+-+=x x x x f ，x x x x x x g 320405150)(10205090+++-= 求和结果：1031040150100)()(102090100++-++=+x x x x x x g x f 2）设计要求 （1）用C 语言编程实现上述实验内容中的结构定义和算法。 （2）要有main()函数，并且在main()函数中使用检测数据调用上述算法。 （3）用switch 语句设计如下选择式菜单。 ***************数据结构综合性实验**************** *******一、多项式的加法、减法、乘法运算********** ******* 1.多项式创建 ********** ******* 2.多项式相加 ********** ******* 3.多项式相减 ********** ******* 4.多项式相乘 ********** ******* 5.清空多项式 ********** ******* 0.退出系统 ********** ******* 请选择（0—5） ********** ************************************************* *请选择（0-5）: 1.2数据结构设计 根据下面给出的存储结构定义： #define MAXSIZE 20 //定义线性表最大容量 中国计量学院实验报告 实验课程：算法与数据结构实验名称：一元二项式班级：学号： 姓名：实验日期： 2013-5-7 一．实验题目： ①创建2个一元多项式 ②实现2个多项式相加 ③实现2个多项式相减 ④实现2个多项式相乘 ⑤实现2个多项式相除 ⑥销毁一元多项式 实验成绩：指导教师： 二．算法说明 ①存储结构：一元多项式的表示在计算机内可以用链表来表示，为了节省存储 空间，只存储多项式中系数非零的项。链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的指针。创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加、相减操作。 ②加法算法 三．测试结果 四．分析与探讨 实验数据正确，部分代码过于赘余，可以精简。 五．附录：源代码#include<> #include<> #include<> typedef struct Polynomial { float coef; int expn; struct Polynomial *next; }*Polyn,Polynomial; 出多项式a和b\n\t2.多项式相加a+b\n\t3.多项式相减a-b\n"); printf("\t4.多项式相除a*b\n\t5.多项式相除a/b\n\t6.销毁多项式\n"); printf("\t7.退出 \n*********************************** ***********\n"); printf("执行:"); scanf("%d",&flag); switch(flag) { case(1): printf("多项式a：");PrintPolyn(pa); printf("多项式b：");PrintPolyn(pb);break; case(2): pc=AddPolyn(pa,pb); printf("多项式a+b：");PrintPolyn(pc); DestroyPolyn(pc);break; case(3): pd=SubtractPolyn(pa,pb); printf("多项式a-b：");PrintPolyn(pd); DestroyPolyn(pd);break; case(4): pf=MultiplyPolyn(pa,pb); printf("多项式a*b：");PrintPolyn(pf); DestroyPolyn(pf);break; case(5): DevicePolyn(pa,pb); break; case(6): DestroyPolyn(pa); DestroyPolyn(pb); printf("成功销毁2个一元二项式\n"); printf("\n接下来要执行的操作:\n1 重新创建2个一元二项式 \n2 退出程序\n"); printf("执行:"); scanf("%d",&i); if(i==1) { // Polyn pa=0,pb=0,pc,pd,pf;//定义各式的头指针，pa与pb在使用前付初值NULL printf("请输入a的项数:"); scanf("%d",&m); pa=CreatePolyn(pa,m);// 建立多项式a printf("请输入b的项 将一元多项式存储为链式结构的线性表，表中数据元素存储有两个数据项（系数项和指数项）。其中，线性表按照指数升序存储。分别用Pa和Pb表示两个一元多项式。Pa=Pa+Pb，“和多项式”链表中的结点无需另生成，而应该是从两个多项式的链表中摘取。其运算规则如下：假设指针qa和qb分别指向A，两个多项式中当前进行比较的某个结点，则比较两个结点中的指数项，有下列3种情况：1指针qa所指结点的指数值小于指针qb所指结点的指数值，则应摘取qa所指的结点插入到“和多项式”链表中去；2指针qa所指结点的指数值大于指针qb所指结点的指数值，则应摘取qb所指的结点插入到“和多项式”链表中去；3指针qa所指结点的指数值等于指针qb所指结点的指数值，则应将两个结点的系数项相加，若和数不等于零，则修改qa所指结点的系数值，同时释放qb所指的结点，反之，从多项式A的链表中删除相应的结点，并且释放qa,qb所指结点。具体代码如下： typedef struct { float coef; int expn; }term,ElemType; typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList; typedef LinkList polynomial; Status InitList(LinkList &L){ L=(LinkList)malloc(sizeof(LNode)); if(!L) return ERROR; L->data.coef=0.0; L->data.expn=-1; L->next=NULL; return OK; } LinkList Get head(LinkList L){ return L; } void SetCurElem(LNode* &NodeAdd,ElemType e){ 数据结构中实现一元多项式简单计算： 设计一个一元多项式简单的计算器。 基本要求： 一元多项式简单计算器的基本功能为： （1）输入并建立多项式； （2）输出多项式； （3）两个多项式相加，建立并输出和多项式； （4）两个多项式相减，建立并输出差多项式； #include 课程设计成果 学院: 计算机工程学院班级: 13计科一班 学生姓名: 学号: 设计地点（单位）： 设计题目：一元多项式的计算 完成日期：年月日 成绩(五级记分制): _________________ 教师签名:_________________________ 目录 1 需求分析 ......................................................................... 错误!未定义书签。 2 概要设计 ......................................................................... 错误!未定义书签。 2.1一元多项式的建立 ............................................................... 错误!未定义书签。 2.2显示一元多项式 ................................................................... 错误!未定义书签。 2.3一元多项式减法运算 ........................................................... 错误!未定义书签。 2.4一元多项式加法运算 ........................................................... 错误!未定义书签。 2.5 设计优缺点.......................................................................... 错误!未定义书签。3详细设计 .......................................................................... 错误!未定义书签。 3.1一元多项式的输入输出流程图........................................... 错误!未定义书签。 3.2一元多项式的加法流程图................................................... 错误!未定义书签。 3.3一元多项式的减法流程图.................................................. 错误!未定义书签。 3.4用户操作函数....................................................................... 错误!未定义书签。4编码 .................................................................................. 错误!未定义书签。5调试分析 .......................................................................... 错误!未定义书签。4测试结果及运行效果...................................................... 错误!未定义书签。5系统开发所用到的技术.................................................. 错误!未定义书签。参考文献 ............................................................................. 错误!未定义书签。附录全部代码................................................................... 错误!未定义书签。 一元多项式的计算—加，减 摘要(题目)一元多项式计算 任务：能够按照指数降序排列建立并输出多项式； 能够完成两个多项式的相加、相减，并将结果输入； 目录 1.引言 2.需求分析 3.概要设计 4.详细设计 5.测试结果 6.调试分析 7.设计体会 8.结束语 一:引言: 通过C语言使用链式存储结构实现一元多项式加法、减法和乘法的运算。按指数 降序排列。 二：需求分析 建立一元多项式并按照指数降序排列输出多项式，将一元多项式输入并存储在内存中，能够完成两个多项式的加减运算并输出结果 三：概要设计 存储结构：一元多项式的表示在计算机内可以用链表来表示，为了节省存储空间，只存储多项式中系数非零的项。链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的指针。创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加、相减操作。 1．单连表的抽象数据类型定义： ADT List{ 数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0} 数据关系：R1={ 项目一一元多项式的计算问题 1.1设计题目与要求 1.1.1设计题目 1）一元多项式计算 任务：能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输入； 基本要求：在上交资料中请写明：存储结构、多项式相加的基本过程的算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；本程序关键点是如何将输入的两个多项式相加、相减操作。 ①如何将输入的一元多项式按指数的降序排列 ②如何确定要输入的多项式的项数； ③如何将输入的两个一元多项式显示出来。 ④如何将输入的两个一元多项式进行相加操作。 ⑤如何将输入的两个一元多项式进行相减操作。 本程序是通过链表实现一元多项式的相加减操作。 1.1.2、任务定义 此程序需要完成如下的要求：将多项式按照指数降序排列建立并输出，将两个一元多项式进行相加、相减操作，并将结果输入。 a：输入多项式的项数并建立多项式； b：输出多项式，输出形式分别为浮点和整数序列，序列按指数升序排列； c：多项式a和b相加，建立多项式a+b； d：多项式a和b相减，建立多项式a-b。 e：多项式的输出。 1.2 数据结构的选择和概要设计： 1.2.1数据结构的选用 A:基于链表中的节点可以动态生成的特点，以及链表可以灵活的添加或删除节点的数据结构，为了实现任意多项式的加法，减法，因此选择单链表的结构体，它有一个系数，指数，下一个指针3个元属；例如，图1中的两个线性链表分别表示一元多项式 和一元多项式。从图中可见，每个结点表示多项式中的一项。 图1 多项式表的单链存储结构 B：本设计使用了以下数据结构： typedef struct node{ int xs; /*系数*/ int zs; /*指数*/ struct node * next; /*next指针*/ }Dnode,* Dnodelist; C：设计本程序需用到八个模块，用到以下八个子函数如下： 1.Dnodelist Creat_node(void) /*链表初始化*/ 2.int Insert_node(Dnodelist D,int xs,int zs) /*插入函数*/ 3.Dnodelist Creat_Dmeth(int length) /*创建多项式*/ 4.Dnodelist Addresult(Dnodelist D1,Dnodelist D2) /*多项式相加*/ 5.Dnodelist Subresult(Dnodelist D1,Dnodelist D2) /*多项式相减*/ 6.Dnodelist select(Dnodelist D1,Dnodelist D2) /*选择函数*/ 7void Show(Dnodelist D) /*显示（输出）函数*/ 8void main()主程序模块调用链一元多项式的各种基本操作模块。 1.2.2 多项式的输入 先输入多项式的项数，采用尾插法的方式，输入多项式中一个项的系数和指数，就产生一个新的节点，建立起它的右指针，并用头节点指向它； 1.2.3 两个多项式的加法 “和多项式”链表中的结点无需另生成，而应该从两个多项式的链表中摘取。其运算规则如下： 假设指针A和B分别指向多项式a和多项式b中当前进行比较的某个结点，则比较两个结点中的指数项，有下列3种情况： ①指针A所指结点的指数值<指针B所指结点的指数值，则应摘取A指针所指结点插入到“和多项式”链表中去； ②指针A所指结点的指数值>指针B所指结点的指数值，则应摘取指针A所指结点插入到“和多项式”链表中去； ③指针A所指结点的指数值=指针B所指结点的指数值，则将两个结点中的系数相加， 若和数不为零，则修改A所指结点的系数值，同时释放B所指结点；反之，从多项式A的链表中删除相应结点，并释放指针A和B所指结点。例如，由图2中的两个链表表示的多项式相加得到的“和多项式”链表如图2所示，图中的长方框表示已被释放的结点。 C语言一元多项式计算集团标准化工作小组 #Q8QGGQT-GX8G08Q8-GNQGJ8-MHHGN# #include <> #include <> #include <> #define LEN sizeof(node) //结点构造 typedef struct polynode { int coef; //系数 int exp; //指数 struct polynode *next; }node; node * create(void) { node *h,*r,*s; int c,e; h=(node *)malloc(LEN); r=h; printf("系数："); scanf("%d",&c); printf("指数："); scanf("%d",&e); while(c!=0) { s=(node *)malloc(LEN); s->coef=c; s->exp=e; r->next=s; r=s; printf("系数："); scanf("%d",&c); printf("指数："); scanf("%d",&e); } r->next=NULL; return(h); } void polyadd(node *polya, node *polyb) { node *p,*q,*pre,*temp; int sum; p=polya->next; q=polyb->next; pre=polya; while(p!=NULL&&q!=NULL) { if(p->exp>q->exp) { pre->next=p; pre=pre->next; p=p->next; } else if(p->exp==q->exp) { sum=p->coef+q->coef; if(sum!=0) { p->coef=sum; pre->next=p;pre=pre->next;p=p->next; temp=q;q=q->next;free(temp); } else { temp=p->next;free(p);p=temp; temp=q->next;free(q);q=temp; } } else { pre->next=q; pre=pre->next; q=q->next; } } if(p!=NULL) pre->next=p; else pre->next=q; } void print(node * p) { 数据结构课程设计实验报告 专业班级： 学号： 姓名： 2011年1月1日 题目：一元多项式的运算 1、题目描述 一元多项式的运算在此题中实现加、减法的运算，而多项式的减法可以通过加法来实现（只需在减法运算时系数前加负号）。 在数学上，一个一元n次多项式P n(X)可按降序写成： P n(X)= P n X^n+ P(n-1)X^(n-1)+......+ P1X+P0 它由n+1个系数惟一确定，因此，在计算机里它可以用一个线性表P来表示： P=(P n，P(n-1)，......，P1，P0) 每一项的指数i隐含在其系数P i的序号里。 假设Q m(X)是一元m次多项式，同样可以用一个线性表Q来表示： Q=(q m,q(m-1)，.....，q1，q0) 不是一般性，假设吗吗m 数据结构课程设计报告 课题: 一元多项式 姓名： XX 学号： 201417030218 专业班级： XXXX 指导教师： XXXX 设计时间： 2015年12月30日星期三 目录 一、任务目标 (3) 二、概要设计 (4) 三、详细设计 (6) 四、调试分析 (8) 五、源程序代码 (8) 六、程序运行效果图与说明 (15) 七、本次实验小结 (16) 八、参考文献 (16) 一丶任务目标 分析 (1) a.能够按照指数降序排列建立并输出多项式 b.能够完成两个多项式的相加，相减，并将结果输入 要求：程序所能达到的功能： a.实现一元多项式的输入； b.实现一元多项式的输出； c.计算两个一元多项式的和并输出结果； d.计算两个一元多项式的差并输出结果； 除任务要求外新增乘法： 计算两个一元多项式的乘积并输出结果 （2）输入的形式和输入值的范围： 输入要求：分行输入，每行输入一项，先输入多项式的指数，再输入多项式的系数，以0 0为结束标志，结束一个多项式的输入。 输入形式： 2 3 -1 2 3 0 1 2 0 0 输入值的范围：系数为int型，指数为float型 （3）输出的形式： 第一行输出多项式1； 第二行输出多项式2； 第三行输出多项式1与多项式2相加的结果多项式； 第四行输出多项式1与多项式2相减的结果多项式； 第五行输出多项式1与多项式2相乘的结果多项式 二、概要设计 程序实现 a. 功能：将要进行运算的二项式输入输出； b. 数据流入：要输入的二项式的系数与指数； c. 数据流出：合并同类项后的二项式； d. 程序流程图：二项式输入流程图； e. 测试要点：输入的二项式是否正确，若输入错误则重新输入。 长沙学院课程设计说明书 题目一元多项式计算问题系(部) 计算机系 专业(班级) 10级软件D班 姓名向栋良 学号2010022D08 指导教师邓旭东 起止日期2011.9.4-2011.9.8 课程设计任务书 课程名称：数据结构与算法 设计题目：一元多项式计算问题 已知技术参数和设计要求： 问题描述： 设计一个稀疏多项式简单计算器 基本要求： (1)输入并分别建立多项式A和B (2)输入输出多项式，输出形式为整数序列：n,c1,e1,c2,e2……，其中n是多项式的项数，ci和ei是第i项的系数和指数，序列按指数降序排列 (3)完成两个多项式的相加、相减，并将结果输出； 测试数据： (1) A+B A= 3x14-8x8+6x2+2 B=2x10+4x8+-6x2 (2) A-B A=11x14+3x10+2x8+10x6+5 B=2x14+3x8+5x6+7 (3) A+B A=x3+x1B=-x3-x1 (4) A+B A=0 B=x7+x5+x3+x1 (5) A-B A=100x100+50x50+20x20+x B=10x100+10x50+10x20+x 选作内容： （1）.多项式在x=1时的运算结果 （2）求多项式A和B的乘积 设计工作量： 40课时 日期节次地点设计方式9月4日（周日）1-4 科1408 讲授内容 9月4日（周日）5-8 科1608 答疑 9月5日（周一）1-4科1408上机调试 9月5日（周一）5-8 科1608 答疑 9月6日（周二）1-4科1408上机调试 9月6日（周二）5-8 科1608 答疑 9月7日（周三）1-4科1408上机调试 9月7日（周三）5-8 科1608 答疑 9月8日（周四）1-4科1608答疑 9月8日（周四）5-8 科1408 答辩 一元多项式计算器 目录 摘要 (1) 1绪论 (1) 2系统分析 (1) 2.1功能需求 (1) 2.2数据需求 (1) 2.3性能需求 (1) 3总体设计 (2) 3.1系统设计方案 (2) 3.2功能模块设计 (2) 4详细设计 (3) 4.1建立多项式 (4) 4.2多项式相加 (4) 4.3多项式相减 (5) 4.4多项式相乘 (5) 4.5计算器主函数 (6) 5调试与测试 (7) 5.1调试 (7) 5.2测试 (8) 6结论 (9) 结束语 (9) 参考文献 (9) 附录1－用户手册 (10) 附录2－源程序 (12) 摘要 随着生活水平的提高，现代科技也日益发达。日常生活中多位计算再所难免，因此设计一个简单计算器可解决许多不必要的麻烦。 开发这样一个程序主要运用了C的结点，链表等方面知识。系统主要实现了多项式的建立，多项式的输入输出，以及多项式加减乘等运算。 报告主要从计算器的程序段，对输入输出数据的要求，计算器的性能，以及总体的设计来介绍此计算器程序的实现过程。 关键词：多项式；链表；结点 1绪论 随着日益发达的科技，计算器已应用于各行各业。设计一个计算器需要运用C中多方面知识，更是以多项式的建立，输入输出，以及结点，链表为主。（扩充） 任务书。。。。。 2系统分析 2.1 功能需求 多项式的建立多项式输入输出多项式加减乘等运算 2.2数据需求 在输入过程中，首先要确定输入的数据，数据不能是字母，只能是数字。不能连续输入数据，必须按要求配以空格输入要计算的数据。 (1) 链节节点数字 (2) 数字 2.3 性能需求 系统必须安全可靠，不会出现无故死机状态，速度不宜过慢。 习 题 一 A 组 1. 判别 {} ,a a b =+∈Q Q 是否为数域 解 是． 2. 设32()1f x x x x =+++，2()32g x x x =++，求()()f x g x +，()()f x g x -，()()f x g x ． 解 32()()243f x g x x x x +=+++， 3()()21f x g x x x -=--， 5432()()46652f x g x x x x x x =+++++． 3．设19932199431995()(54)(421)(8112)f x x x x x x =----+，求()f x 的展开式中各项系数的和． 解 由于()f x 的各项系数的和等于(1)f ，所以 199319941995(1)(54)(421)(8112)1f =----+=-． 4. 求()g x 除以()f x 的商()q x 与余式()r x ． (1) 322()31, ()321f x x x x g x x x =---=-+； (2) 42()25,()2f x x x g x x x =-+=-+． 解 (1) 用多项式除法得到 2323222732131 3923374133 7147399 26299x x x x x x x x x x x x x x -+----- +----+--- 所以，17262(),()3999 q x x r x x =-=--． (2) 用多项式除法得到 242432 3232222251 2225 245 2 57 x x x x x x x x x x x x x x x x x x x x -+-++--+--+-+--+-+--+ 所以，2()1,()57q x x x r x x =+-=-+． 5．设,a b 是两个不相等的常数，证明多项式()f x 除以()()x a x b --所得余式为 ()()()() f a f b af b bf a x a b a b --+--． 证明 依题意可设()()()()f x x a x b q x cx d =--++，则 (), ().f a ca d f b cb d =+??=+? 解得 ()()()()(), ()()).c f a f b a b d af b bf a a b =--???=--?? 故所得余式为 ()()()() f a f b af b bf a x a b a b --+--． 6. 问,,m p q 适合什么条件时，()f x 能被()g x 整除 (1) 3()f x x px q =++，2()1g x x mx =+-； (2) 42()f x x px q =++，2()1g x x mx =++． 解 (1) 由整除的定义知，要求余式()0r x =．所以先做多项式除法， 233222221(1)(1)() x mx x px q x m x mx x mx p x q mx m x m p m x q m +-++-+--+++--++++- 要求2()(1)()0r x p m x q m =+++-=， 所以2(1)0,0p m q m ++=-=．即21, p m q m =--=时， 可以整除． (2) 方法同上．先做多项式除法，所得余式为 一元多项式计算(数据结构课程设计) 一、系统设计 1、算法思想 根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应指数相加（减），若其和（差）不为零，则构成“和（差）多项式”中的一项；对于两个一元多项式中所有指数不相同的项，则分别写到“和（差）多项式”中去。 因为多项式指数最高项以及项数是不确定的，因此采用线性链表的存储结构便于实现一元多项式的运算。为了节省空间，我采用两个链表分别存放多项式a 和多项式b，对于最后计算所得的多项式则利用多项式a进行存储。主要用到了单链表的插入和删除操作。 (1)一元多项式加法运算 它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果指数相等的话，系数就应该相加；相加的和不为零的话，用头插法建立一个新的节点。P 的指数小于q的指数的话就应该复制q的节点到多项式中。P的指数大于q的指数的话，就应该复制p节点到多项式中。当第二个多项式空，第一个多项式不为空时，将第一个多项式用新节点产生。当第一个多项式空，第二个多项式不为空时，将第二个多项式用新节点产生。 (2)一元多项式的减法运算 它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果指数相等的话，系数就相减；相加的和不为零的话，用头插法建立一个新的节点。p的指数小于q的指数的话，就应该复制q的节点到多项式中。P的指数大于q的指数的话就应该复制p的节点到多项式中，并且建立的节点的系数为原来的相反数；当第二个多项式空，第一个多项式不为空时，将第一个多项式用新节点产生。当第一个多项式空，第二个多项式不为空时，将第二个多项式用新节点产生，并且建立的节点的系数为原来的相反数。 2、概要设计 (1)主函数流程图： （注：a代表第一个一元二次方程，b代表第二个一元二次方程） 计算机学院 工程实践 一元多项式的计算总报告 小组序号： 编撰人： 年级班级： 指导教师： 提交日期： 1. 项目组成员分工 表 1 项目组成员分工 2. 程序功能 (程序实现的功能，功能结构图) 实现功能：一元多项式的加、减、乘运算 功能结构图： 乘 减加创建多项式 开始 保存 结束 3. 程序设计简介 (包括：类及其属性和方法、类之间关系、关键代码等的说明) 1. class Node { public: Node(); Node(float c, int e, Node* next); ~Node(){}; float coef; //系数 int exp; //指数 Node* Next; //指向下一项的指针 friend class Polynominal; }; 节点类，储存一元多项式每一项的信息。该内含有两个构造函数，一个析构函数及存储系数、指数和Next指针等成员变量。与Polynominal是友元关系，允许Polynominal的访问。 具体成员函数如下： 1) Node::Node(){} 默认构造函数。 2) Node::Node(float c, int e, Node* next){ coef = c; exp = e; Next = next; } 重载的自定义构造函数，用于给成员变量coef、exp和Next存入数据，Next指向传参来的next指针指向的地址，用于构造链表。 2. class Polynominal{ public: Polynominal(); Polynominal(Polynominal &a); //拷贝构造函数 void GetMSG(CString TempPloy); //获取由对话框输入的字符串并处理 CString Output_Node(); //输出最后结果 void PolyAdd(Polynominal &a, Polynominal &b); //加法 void PolySubtract(Polynominal &a, Polynominal &b); //减法 void PolyMultiply(Polynominal &a, Polynominal &b); //乘法 void PolySort(); //排序函数，用于乘法之后的按指数排序 void OutFile(); //文本输出函数 池州学院 CHIZHOU COLLEGE 《数据结构》 课程设计报告 学号：57 54 39 37 20 25 27 姓名：周田张永鹏武警温凯侨李坤 米昌华阮健健 班级：10计算机科学与技术（2）班 指导教师： 成绩： 数学与计算机科学系 一、课程设计基本情况 1、设计名称 一元多项式计算 2、主要功能 能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输出； 3、设计平台 电脑、Visual c++ 6.0 二、系统设计 1、算法思想 根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应指数相加（减），若其和（差）不为零，则构成“和（差）多项式”中的一项；对于两个一元多项式中所有指数不相同的项，则分别写到“和（差）多项式”中去。 因为多项式指数最高项以及项数是不确定的，因此采用线性链表的存储结构便于实现一元多项式的运算。为了节省空间，我采用两个链表分别存放多项式a 和多项式b，对于最后计算所得的多项式则利用多项式a进行存储。主要用到了单链表的插入和删除操作。 (1)一元多项式加法运算 它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果指数相等的话，系数就应该相加；相加的和不为零的话，用头插法建立一个新的节点。P的指数小于q的指数的话就应该复制q的节点到多项式中。P的指数大于q的指数的话，就应该复制p节点到多项式中。当第二个多项式空，第一个多项式不为空时，将第一个多项式用新节点产生。当第一个多项式空，第二个多项式不为空时，将第二个多项式用新节点产生。 (2)一元多项式的减法运算 它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果指数相等的话，系数就相减；相加的和不为零的话，用头插法建立一个新的节点。p的指数小于q的指数的话，就应该复制q的节点到多项式中。P的指数大于q的指数的话就应该复制p的节点到多项式中，并且建立的节点的系数为原来的相反数；当第二个多项式空，第一个多项式不为空时，将第一个多项式用新节点产生。当第一个多项式空，第二个多项式不为空时，将第二个多项式用新节点产生，并且建立的节点的系数为原来的相反数。 2、概要设计 (1)主函数流程图： （注：a代表第一个一元二次方程，b代表第二个一元二次方程） 合肥学院 计算机科学与技术系 课程设计报告 2008～2009学年第二学期 课程程序设计语言Ⅱ课程设计 课程设计名称多项式的计算 学生姓名王建敏 学号0804013029 专业班级计算机科学与技术（3）班 指导教师张贯虹汪彩梅 2009年6月 一、课程设计题目：多项式（单项链表的应用） 二、分析与设计 1．程序的基本功能 （1）建立多项式 （2）输出多项式 （3）删除多项式以释放空间 （4）删除多项式中的某一项 （5）将多项式合并同类项 （6）拷贝多项式 （7）将多项式按指数升序排列 （8）判断两多项式是否相等 （9）两个多项式相加，建立并输出和多项式 （10）两个多项式相减，建立并输出差多项式 （11）两个多项式相乘，建立并输出积多项式 （12）两个多项式相除，建立并输出商多项式 2．算法设计 本程序主要应用了链表，结构体和类模板。用结构体来定义多项式的结点（即每一项），它包含三个域，分别存放该项的系数、指数以及指向下一项结点的指针；用链表来存储多项式，为了节省空间，只存储多项式中系数非0 的项，用多项式链表类来实现设定的程序的基本功能。 涉及的主要算法有： （1）使用尾插法创建多项式，即从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据域中,然后将新结点插入到当前链表的表尾上,直到读入结束标志（某一项的系数为零）为止。 （2）输出一个非空的多项式链表，不要输出最后一项，即输入系数为零的结束项，用if……else语句判断。 （3）删除整个多项式是一项一项的删，使用链表删除其结点的方法，使用free（）函数释放存储空间。在删除非空的多项式的某一项时，定义k来找到要删除的那一项的位置，再使用delete 将其删除。 （4）在对多项式合并同类项时，主要有两点，一是看两项指数是否相等，若相等则合并成一项，二是看两项系数和是否为零，若为零则去掉这两项。在对多项式排序时，先合并同类项，再按指数值从小到大排序。 （5）在拷贝多项式时使用重载函数，将系数和指数都拷贝给新的多项式。 （6）在判断两多项式是否相等时，先分别对两多项式进行排序，再从头项开始，一项一项的比较其系数和指数，一旦有一个不相等就结束，即这两多项式不相等，否则相等。 （7）计算多项式加减，其算法思想是相同的。以多项式加法为例，先对两多项式排序，再将两多项式的每一项逐项相加，在相加之前，先比较两项的指数是否相等，若相等则将系数相加，再判断系数是否为零，若为零则删除，否则存储在和多项式中。若两项指数不相等，当多项式pa 指数大于多项式pb指数时，则将pa结点副本插入到和多项式PolyC尾部；当pa指数小于pb指数时，则将pb结点副本插入到和多项式PolyC尾部，最后插入剩余结点。 <数据结构>课程设计 题目:（1.2）一元多项式的操作 班级: 姓名:XXX 学号: 完成日期:2014/12/6 一元多项式的操作。(任意选择三项要求) 问题描述：设计一个一元稀疏多项式简单计算器。 要求： （1）输入并建立多项式。 （2）输出多项式，输出形式为整数序列：n，c1，e1，，c2，e2，…，cn，en，其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列。 （3）多项式a和b相加，建立多项式a+b。 （4）多项式a和b相减，建立多项式a-b。 （5）计算多项式在x处的值。 （6）求多项式a的导函数。 （7）多项式a和b相乘，建立多项式a*b。 1、需求分析： (1).输入形式： 函数名+'('+表达式名或表达式或不加任何东西+')'+';' 再按回车; 其中大写字母开头为表达式名,变量名只能为'x'; 如： Create(A,2x); Show(*); Add(A,A,3); Show(A); Cal(A,2); Delete(A); Quit(); 数值类型： 表达式：A=coef*x^expn; 其中：coef为x的系数，为浮点型；expn为x的指数，为整型 即;A=0.2x^-3; (2).输出型式： Error::…. Create OK!; A=2x+3; Delete OK! A(x=2)=7; （3）程序所能达到的功能。 表达式的创建、删除、显示、以及表达式的加、减、乘运算，以及给x赋值，计算出表达式相应的值。 （4）测试数据。 Create(A,2x); Show(*); Add(A,A,3); Show(A); Cal(A,2); Delete(A); Quit(); 2、概要设计 图1 表达式结构设计 3、详细设计 （1）基本操作： 创建表达式： void CreatList_NULL(LinkList *L)；创建空链表 int createByName(char* name)；顺序链式一元多项式加法、减法、乘法运算的实现
一元多项式加减乘除运算
一元多项式的基本操作
数据结构中实现一元多项式简单计算
数据结构一元多项式的计算
一元多项式的计算数据结构课程设计
数据结构 一元多项式的计算
C语言一元多项式计算
一元多项式的运算
数据结构实验报告-一元多项式
一元多项式计算问题课程设计
一元多项式计算器
第一章一元多项式习题及解答
一元多项式计算(数据结构课程设计)
一元多项式的计算实验报告
一元多项式计算数据结构课程设计
一元多项式的计算课程设计报告
一元多项式的操作