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

《数据结构课程设计-n元多项式乘法.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计-n元多项式乘法.docx（19页珍藏版）》请在第一文库网上搜索。

1、数据结构课程设计报告N元多项式乘法目录1课程设计内容32课程设计分析33 思路原理54 程序简图55算法（数据结构）描述66程序清单74.1 单链表表示74.2 数组表示157运行与调试分析168 收获与体会179 参考文献181课程设计内容功能：完成两个n元多项式作乘法，给出明确的等式形式。分步实施：1)初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2)完成最低要求：建立一个文件，实现两个一元二次多项式作乘法。3)进一步要求：实现三元二次多项式的乘法。有兴趣的同学可以自己扩充系统功能。2课程设计分析本程序用的存储方式是单链表，单链表在C语言中是一种非常常见的结构，而在C+中的

2、实现却又有不同，在一些地方更简单，更严密。同时，由于C+的一些特点,使它具有C语言所不具有的“安全化”，所以本程序用C+。有了链表特定的数据类型MUIPOIy,接下来就需要建立这个链表。这里定义了一个构造函数CreatePo1y来构造链表。首先定义一个CreatePo1y型的指针变量head作为头结点，存储多项式的信息(项数)，为head分配存储空间建立一个头结点并为其数据域赋值，分配存储空间用c+语言中的maoc来实现；这时输入多项式的项数num,把它赋值给head的coef域，exp域赋值为1此时再定义一个CreatePo1y型的指针变量r指向head头结点。还要用类似的算法建立多项式的其

3、它结点，剩余节点的插入用一个whi1e循环来实现，whi1e循环中的控制变量i从大于0的数n开始递增，直到到达num,此时WhiIe循环结束。Whi1e循环的循环体由两部分组成，第一部分是为指针变量s分配存储空间和为其数据域赋值，分配存储空间同样用c+语言中的ma1hc来实现；第二部分是节点的指针域转换过程，将r的指针域指向新生成的结点s,相当于将生成结点依次用指针连接，然后将最后一个结点的指针域设置为NU11,具体代码如下：Mu1Po1y*CreatePo1yOMu1Po1y*head,*r,*s;intm,n,num,i=1;head=(Mu1Po1yma11oc(sizeof(Mu1Po

4、1y);COUt请输入多项式的项数,num;head-coef=num;head-exp=1;r=head;whi1e(i=num)/n不为0时建立多项式链表s=(Mu1Po1yma11oc(sizeof(Mu1Po1y);COUt输入第0i组系数和指数znm;s-exp=m;s-coef=n;r-next=s;r=s;1+；)r-next=nu11;return(head);)在处理多项式相乘的问题时，定义一个Po1yMUIti函数实现，需要再建立一个Mu1Po1y型的链表存储相乘之后的链表,定义结果链表的系数等于链表P1的系数乘以链表P2的系数：(p-coef)=(p1-COef)*(p2

5、-coef)结果链表的指数等于链表P1的指数乘以链表P2的指数：(p-exp)=(p1-exp)+(p2-exp)。在整理之后可能出现零结点，那么就需要进行判断和删除操作同时释放零结点，这些操作是通过一个WhiIe循环来完成。具体代码如下：whi1e(p!=q)s=q;q=q-next;s-next=q-next;free(q);还需要定义一个输出函数，在主函数中调用输出两个多项式相乘后的结果。程序的最终都是由主函数来实现。在主函数中通过对一些自定义函数的调用实现具体的操作。在此主函数调用了一个构建链表的函数CreatePo1y、一个删除空结点的函数DeIete和输出函数Print。在主函数的

6、开始需要定义三个MU1PO1y型指针变量，分别用来存储调用CreatePo1y函数和Po1yMu1ti函数生成的链表和结果链表。在构建链表之前要给节点分配存储空间，s=(Mu1Po1y*)ma11oc(Sizeof(Mu1Po1y);这条语句便可完成此操作。此条语句运用了c+语言库函数中的maoc函数，这个函数的作用是在内存的动态存储区中分配一个长度为SiZeof(MU1POIy)的内存空间。调用构建链表函数CreatePo1y后链表P1便构建完成。接下来需要执行m=Po1yMu1ti(p,q);语句，这条语句的目的是把多项式P1和P2相乘的结果多项式存储在链表m当中，然后执行Print(m)

7、;语句显示输出。主函数的程序框架如下：intmain()Mu1Po1y*p,*q,*m;P=CreatePo1yO；Q=CreatePo1yO；m=PoIyMu1ti(p,q);Merge_Same(m);Print(m);system(zzpausezz);)程序的调试是程序顺利完成中非常关键的一步。通过程序的调试分析可以解决程序的运行错误也可以对程序的性能进行分析。这个多项式运算问题研究的程序最重要的就是看输出的链表是否正确，是否带有空结点，合并是否完全。决定程序成功与否的第一步是定义的P。IyMU1ti函数操作是否正确。如果这一步中出现错误，那么接下来的操作可以说是错上加错。在调试的时候

8、可以在程序中加入删除、释放空结点操作,此操作便是由De1ete函数完成的，若输出的多项式没有空结点说明函数正确，可以继续向下进行。接下来就是相乘后的合并同类项，控制此操作的关键是一个Merge_Same函数，调用De1ete函数是决定成功与否的关键。可以先在本上写出两个-完整版学习资料分享-正确的简单的多项式，使其具有相加后出现空结点的特点，然后变换循环变量的范围，当输出吻合时则说明操作正确。各个关键部分都已检查完毕，剩下的就是对程序的进一步细心的完善直到满足要求。下面分析一下程序的性能。在主函数中，首先调用的是构造单链表函数CreatePo1y,在这个函数中需要通过一个for循环为每个结点分

9、配存储空间，变换节点的next域，时间复杂度为0(n)o接下来执行一个双重for循环，在内部的for循环中是对结点的相加、相乘操作，因为是按着指针的方向就可以对结点进行相加、相乘操作，所以每个结点的操作都需要m次，共n个结点，则需要M次操作，时间复杂度为。(胪)。3思路原理先要设置两个单链表，每个单链表中可写入一个多项式。加法：取第两个链表中最高项和另一链表各项比指数，若不同则放在第三个空链表里作为第一项，若相同则系数相加指数不变，放在第三个空链表里作为第一项，并且要删除两链表里此指数项。取第两个链表中最高项和另一链表各项比指数，以此类推。乘法：取第一个链表第一项和第二链表的每一项相乘，系数相

10、乘，指数相加，作为一个新链表。取第一个链表第二项和第二链表的每一项相乘最后再把每个新链表做加法。最后显75答案。4程序简图乘法)5算法(数据结构)描述定义单链表的抽象数据类型：ADT1ink1ist数据对象：D=aiIaiE1emSet,i=1,2,3,，n=0数据关系：R=)ai,ai+1D/线性表的单链表基本操作/1ink1istInit1ist(void);构造一个空的线性表voidDestroy1ist(1ink1ist*1);初始条件：线性表1已存在。操作结果：销毁线性表1。1ink1istMakeEmPty(1ink1iSt1)初始条件：线性表1已存在。操作结果：将线性表1重置为空

11、表。intIsEmpty(1ink1ist1);初始条件：线性表1已存在。操作结果：判断线性表是否为空表。int1ist1ength(1ink1ist1);初始条件：线性表1已存在。操作结果：返回线性表1结点的个数。1NodeIs1ast(1ink1ist1);初始条件：线性表1已存在。操作结果：返回线性表1的最后一个结点(尾结点)。1NodeNew1Node(E1emTypeX);构造一个数据域为X的新结点1NodeFindPrefious(E1emTypeX,1ink1ist1);初始条件：线性表1已存在。操作结果：在线性表1中寻找值为X的结点，若找到则返回该结点的前驱，否则返回NU11。

12、void1istDe1ete(1NodePre);初始条件：线性表1中结点P已找到。操作结果：删除该结点。链表的结点结构：IdataInextdata域一存放结点值的数据域next域一存放结点的直接后继的地址(位置)的指针域(链域)此题定义系数和指数结构如下：coefexpnext/线性表的单链表存储结构/Typedefstruct1nodeE1emTypedata;/结点的数据域Struct1node*next;结点的指针域1node,*1ink1ist;/基本操作/InitArray(&A,n,bound1,.,boundn)操作结果：若维数n和各维长度合法则构造相应数组AoDestroy

13、Array(&A)初始条件：数组A已经存在。操作结果：销毁数组AoVa1ue(A,&e,index1,.,indexn)初始条件：A是n维数组，e为元素变量，n个下标值。操作结果：若各下标不超界，则e赋值为所指定的A的元素值，并返回OkAssign(&A,e,index1,.,indexn)初始条件：A是n维数组，e为元素变量，n个下标值。操作结果：若下标不超界，则将e的值赋给A中指定下标的元素。ADTArray6程序清单6.1单链表表示/*程序源代码：*/#inc1udettinc1ude#inc1ude#inc1ude#definenu110usingnamespacestd;typede

14、fstructterm/项的表示，多项式的项作为1ink1iSt的数据元素f1oatcoef;/系数intexpn;/指数structterm*next;term;intEmpty(term*1)if(1-next!=nu11)return1;return0;)termCreatePo1y()termead,*r,*s;intm,n,num,i=1;head=(term*)ma11oc(sizeof(term);建立一个头结点coutnum;head-coef=num;head-expn=1;r=head;whi1e(i=num)n不为0时建立多项式链表s=(term*)maoc(sizeof(term);/建立一个新结点COUt输入第inm;s-expn=m;s-coef=n;r-next=S;r=s;i+；)r-next=nu11;return(head);)term*Po1yMu1ti(term*f,term*g)term*p1,*p2,*p,*r,*head;=WORD完整版一可编辑.专业资料分享=head=(term)ma11oc(sizeof(term);head-coef=nu11;head-expn=nu1