数据结构课程设计-n元多项式乘法

数据结构课程设计报告——N元多项式乘法目录1课程设计内容------------------------------------------------------------------1-2课程设计分析------------------------------------------------------------------1-3思路原理-------------------------------------------------------------------------3-4程序简图-------------------------------------------------------------------------3-5算法（数据结构）描述-----------------------------------------------------4-6程序清单-------------------------------------------------------------------------5-6.1单链表表示----------------------------------------------------------------6-6.2数组表示------------------------------------------------------------------13-7运行与调试分析--------------------------------------------------------------14-8收获与体会---------------------------------------------------------------------15-9参考文献------------------------------------------------------------------------16--1-1课程设计内容功能：完成两个n元多项式作乘法，给出明确的等式形式。分步实施：1)初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2)完成最低要求：建立一个文件，实现两个一元二次多项式作乘法。3)进一步要求：实现三元二次多项式的乘法。有兴趣的同学可以自己扩充系统功能。2课程设计分析本程序用的存储方式是单链表，单链表在C语言中是一种非常常见的结构，而在C++中的实现却又有不同，在一些地方更简单，更严密。同时，由于C++的一些特点，使它具有C语言所不具有的“安全化”，所以本程序用C++。有了链表特定的数据类型Mulpoly，接下来就需要建立这个链表。这里定义了一个构造函数CreatePoly来构造链表。首先定义一个CreatePoly型的指针变量head作为头结点，存储多项式的信息（项数），为head分配存储空间建立一个头结点并为其数据域赋值，分配存储空间用c++语言中的malloc来实现；这时输入多项式的项数num，把它赋值给head的coef域，exp域赋值为1，此时再定义一个CreatePoly型的指针变量r指向head头结点。还要用类似的算法建立多项式的其它结点，剩余节点的插入用一个while循环来实现，while循环中的控制变量i从大于0的数n开始递增，直到到达num，此时while循环结束。While循环的循环体由两部分组成，第一部分是为指针变量s分配存储空间和为其数据域赋值，分配存储空间同样用c++语言中的malloc来实现；第二部分是节点的指针域转换过程，将r的指针域指向新生成的结点s，相当于将生成结点依次用指针连接，然后将最后一个结点的指针域设置为NULL，具体代码如下：MulPoly*CreatePoly(){MulPoly*head,*r,*s;intm,n,num,i=1;head=(MulPoly*)malloc(sizeof(MulPoly));cout请输入多项式的项数:endl;cinnum;head-coef=num;head-exp=1;r=head;while(i=num)//n不为0时建立多项式链表{s=(MulPoly*)malloc(sizeof(MulPoly));cout输入第i组系数和指数:endl;-2-cinnm;s-exp=m;s-coef=n;r-next=s;r=s;i++;}r-next=null;return(head);}在处理多项式相乘的问题时，定义一个PolyMulti函数实现，需要再建立一个MulPoly型的链表存储相乘之后的链表，定义结果链表的系数等于链表P1的系数乘以链表P2的系数：(p-coef)=(p1-coef)*(p2-coef)结果链表的指数等于链表P1的指数乘以链表P2的指数：(p-exp)=(p1-exp)+(p2-exp)。在整理之后可能出现零结点，那么就需要进行判断和删除操作同时释放零结点，这些操作是通过一个while循环来完成。具体代码如下：while(p!=q){s=q;q=q-next;}s-next=q-next;free(q);}还需要定义一个输出函数，在主函数中调用输出两个多项式相乘后的结果。程序的最终都是由主函数来实现。在主函数中通过对一些自定义函数的调用实现具体的操作。在此主函数调用了一个构建链表的函数CreatePoly、一个删除空结点的函数Delete和输出函数Print。在主函数的开始需要定义三个MulPoly型指针变量，分别用来存储调用CreatePoly函数和PolyMulti函数生成的链表和结果链表。在构建链表之前要给节点分配存储空间，s=(MulPoly*)malloc(sizeof(MulPoly));这条语句便可完成此操作。此条语句运用了c++语言库函数中的malloc函数，这个函数的作用是在内存的动态存储区中分配一个长度为sizeof(MulPoly)的内存空间。调用构建链表函数CreatePoly后链表Pl便构建完成。接下来需要执行m=PolyMulti(p,q);语句，这条语句的目的是把多项式P1和P2相乘的结果多项式存储在链表m当中，然后执行Print(m);语句显示输出。主函数的程序框架如下：intmain(){MulPoly*p,*q,*m;p=CreatePoly();q=CreatePoly();m=PolyMulti(p,q);Merge_Same(m);Print(m);system(pause);}程序的调试是程序顺利完成中非常关键的一步。通过程序的调试分析可以解决程序的运行错误也可以对程序的性能进行分析。这个多项式运算问题研究的程-3-序最重要的就是看输出的链表是否正确，是否带有空结点，合并是否完全。决定程序成功与否的第一步是定义的PolyMulti函数操作是否正确。如果这一步中出现错误，那么接下来的操作可以说是错上加错。在调试的时候可以在程序中加入删除、释放空结点操作，此操作便是由Delete函数完成的，若输出的多项式没有空结点说明函数正确，可以继续向下进行。接下来就是相乘后的合并同类项，控制此操作的关键是一个Merge_Same函数，调用Delete函数是决定成功与否的关键。可以先在本上写出两个正确的简单的多项式，使其具有相加后出现空结点的特点，然后变换循环变量的范围，当输出吻合时则说明操作正确。各个关键部分都已检查完毕，剩下的就是对程序的进一步细心的完善直到满足要求。下面分析一下程序的性能。在主函数中，首先调用的是构造单链表函数CreatePoly，在这个函数中需要通过一个for循环为每个结点分配存储空间，变换节点的next域，时间复杂度为O（n）。接下来执行一个双重for循环，在内部的for循环中是对结点的相加、相乘操作，因为是按着指针的方向就可以对结点进行相加、相乘操作，所以每个结点的操作都需要m次，共n个结点，则需要𝑚𝑛次操作，时间复杂度为O（𝑛𝑛）。3思路原理先要设置两个单链表，每个单链表中可写入一个多项式。加法：取第两个链表中最高项和另一链表各项比指数，若不同则放在第三个空链表里作为第一项，若相同则系数相加指数不变，放在第三个空链表里作为第一项，并且要删除两链表里此指数项。取第两个链表中最高项和另一链表各项比指数，以此类推。乘法：取第一个链表第一项和第二链表的每一项相乘，系数相乘，指数相加，作为一个新链表。取第一个链表第二项和第二链表的每一项相乘.......最后再把每个新链表做加法。最后显示答案。4程序简图-4-5算法（数据结构）描述定义单链表的抽象数据类型：ADTLinkList{数据对象：D={ai|ai∈ElemSet,i=1,2,3,…，n=0}数据关系：R={ai,ai+1|ai,ai+1∈D}//----------------------线性表的单链表基本操作---------------------//LinkListInitList(void);构造一个空的线性表voidDestroyList(LinkList*L);初始条件：线性表L已存在。操作结果：销毁线性表L。LinkListMakeEmpty(LinkListL)‘初始条件：线性表L已存在。操作结果：将线性表L重置为空表。intIsEmpty(LinkListL);初始条件：线性表L已存在。操作结果：判断线性表是否为空表。intListLength(LinkListL);初始条件：线性表L已存在。操作结果：返回线性表L结点的个数。LNodeIsLast(LinkListL);初始条件：线性表L已存在。操作结果：返回线性表L的最后一个结点（尾结点）。LNodeNewLNode(ElemTypeX);-5-构造一个数据域为X的新结点LNodeFindPrefious(ElemTypeX,LinkListL);初始条件：线性表L已存在。操作结果：在线性表L中寻找值为X的结点，若找到则返回该结点的前驱，否则返回NULL。voidListDelete(LNodePre);初始条件：线性表L中结点P已找到。操作结果：删除该结点。链表的结点结构:┌──┬──┐│data│next│└──┴──┘data域--存放结点值的数据域next域--存放结点的直接后继的地址（位置）的指针域（链域）此题定义系数和指数结构如下：coefexpnext//----------------------线性表的单链表存储结构---------------------//TypedefstructLnode{ElemTypedata;//结点的数据域StructLnode*next;//结点的指针域}Lnode,*LinkList;//-----------------------------基本操作----------------------------//InitArray(&A,n,bound1,...,boundn)操作结果：若维数n和各维长度合法则构造相应数组A。DestroyArray(&A)初始条件：数组A已经存在。操作结果：销毁数组A。Value(A,&e,index1,...,indexn)初始条件：A是n维数组，e为元素变量，n个下标值。操作结果：若各下标不超界，则e赋值为所指定的A的元素值，并返回OK。Assign(&A,e,index1,...,indexn)初始条件：A是n维数组，e为元素变量，n个下标值。操作结果：若下标不超界，则将e的值赋给A中指定下标的元素。}ADTArray6程序清单-6-6.1单链表表示/*程序源代码：*/#includestdlib.h#includestdio.h#includectype.h#includeiostream#definenull0usingnamespacestd;typedefstructterm{//项的表示，多项式的项作为Link