《数据结构上机实习报告》由会员分享，可在线阅读，更多相关《数据结构上机实习报告（31页珍藏版）》请在金锄头文库上搜索。
1、数据结构上机实习报告实验题目：一元多项式班级：193121姓名：邹冠宏学号：20121002758指导老师：郭艳完成日期：2013/9/30一 问题分析1. 问题描述设计一个n元多项式程序，并完成多项式的加法，乘法运算。从实际的角度出发，这里设计的程序是基于一元n次多项式的数学模型。2、 功能需求1)构造一个空的多项式。2)多项式插入新的一项。3）计算多项式的值。4）打印多项式。5）多项式合并同类项。6）多项式加法。7）多项式乘法。8)多项式减法二、概要设计 1问题分析在数学上，一个一元多项式Pn(x)可按升幂写成：Pn(x)=a 0+a1 x+a2 x2 +an xn-1 .它由n+1个系数
2、惟一确定，因此，在计算机里，它可用一个线性表P来表示：Pn=(a0,a1,a2,an)每一项的指数i隐含在其系数ai的序号里。2数据模型设计一个单链表模型，动态分配空间，刻意随时插入新的一项多项式加法规则：两个具有相同指数的项合并，系数为0时把这一项省去，也就是删除了这一节点。多项式的乘法规则：多次运用单项式与多项式相乘的法则得到的计算时(a+b)(c+d)，把(c+d)看成一个单项式，(a+b) 是一个多项式，运用单项式与多项式相乘的法则，得到(a+b)(c+d)=a(c+d)+b(c+d),然后再次运用单项式与多项式相乘的法则。3 构造数据结构通过分析多项式的特征，不难看出多项式是由单项式
3、构成的，而每个单项式都具有系数和指数，当系数为0时，该项就失去了意义，在计算机内要表示一个多项式，至少以下数据信息：系数信息、指数信息和指向下一个单项式的指针。通过指针，我们就可以把多个单项式连接起来，形式一个多项式，基于以上的分析，我们定义多项式的数据结构为如下结构体形式：typedef struct Polynomial float coef;/系数 int expn;/指数 struct Polynomial *next;/指向下一个结点*Polyn,Polynomial; /Polyn为结点指针类型三、详细设计 1一元多项式运算程序具有以下基本功能：1）界面输出，提示如何输入数据。要求
4、先输入多项式的项数。2）创建多项式。接收输入的数据，并保存到链表中。3）显示程序的功能表，允许使用者选择运算类型。4）打印多项式。5）实现加法运算。7）实现乘法运算。6）清除内存内容，销毁创建的链表，退出程序。2功能算法描述与数据结构说明该多项式程序除了main()函数外，主要有以下函数：Polyn CreatePolyn(Polyn head,int m)void Insert(Polyn p,Polyn h)void PrintPolyn(Polyn P)int compare(Polyn a,Polyn b)Polyn AddPolyn(Polyn pa,Polyn pb)Polyn M
5、ultiplyPolyn(Polyn pa,Polyn pb)void DestroyPolyn(Polyn p)void CountPolyn(Polyn P,int k)3. 主要功能函数的详细设计1）.main（）函数main函数是用来实现提示使用者输入、显示功能列表、调用其他运算函数实现运算功能。在main（）函数中，定义m、n用来保存两个多项式的项数，pa、pb、pc、pd、pf定义程序所需链表的头指针。在程序开始要求输入两个多项式的项数，随后根据项数创建两个链表以保存多项式，再显示出功能列表后通过输入数字来选择来实现功能的选择，从而达到对整个程序流程进行控制。2）. Polyn C
6、reatePolyn(Polyn head,int m)该函数功能是创建新的多项式链表。int m保存的多项式的项数，使用for语句，控制输入多项式的每一项。若创建的链表长度为m时，将不再提示用户继续输入多项式的系数和指数。因为是从0项开始计算的。在该函数中要用到分配空间的函数malloc()为新建链表分配空间。而空间的长度要用sizeof（）。3）. void Insert(Polyn p,Polyn h)该函数功能：将新的节点p插入到现有链表的后面，并确保多项式的指数exp是升序。将s节点插入到head所指向的链表。在该函数的操作中，要注意指针是如何移动的。对插入的位置要分情况讨论。在头，
7、中，尾三处的插入。4）. int compare(Polyn a,Polyn b)该函数功能：判断两个多项式在同一指数下是否有其中一个为系数为0。根据不同情况来讨论多项式的指数，用来辅助加法和乘法运算。5）. Polyn AddPolyn(Polyn pa,Polyn pb)该函数功能：实现两个多项式pa、pb相加，并将计算结果存储于新建立的pc中，它的原理是将指数相同的单项式相加，系数相加后为0，则pa、pb的指针都后移。在加法计算中要求pa,与pb的幂次序都是升序，否则可能得到错误的结果。该函数调用了int compare(Polyn a,Polyn b)的结果，用来判断多项式在同一指数下
8、a、b是否有为系数为0。同样也使用了malloc()关键字，为新链表创建分配空间。6）. void PrintPolyn(Polyn P)该函数功能：显示多项式链表。在该函数中较复杂的是如何控制链表的输出，尤其是第一项的输出，同时还有符号的控制。在输出第一项时要判断是不是常数项，若是，则不要输出字符x。还有对系数的正负的判断，若是正就输出+，负则直接输出。7）. Polyn MultiplyPolyn(Polyn pa,Polyn pb)函数功能：实现两个多项式相乘，F(X) * H(x) 。计算时运用单项式与多项式相乘的法则，然后再次运用单项式与多项式相乘的法则。对得到多项式进行合并。8）P
9、olyn CountPolyn(Polyn p,int x) 此函数是用来输出多项式的计算结果，要给x赋值，当*next=Null时结束运算，输出结果9）. void DestroyPolyn(Polyn p)该函数的功能是销毁掉创建的两个链表，释放内存。以辅助退出程序。有利于空间空域，如果不释放没用的内存空间的话，内存会被占用，最后导致内存不足，甚至系统崩溃。4各函数的详细设计该程序实现了多项式的创建、多项式的加法、乘法运算以及多项式的清除。为完成这些功能，必须用到一些辅助函数。下面讨论一些重要函数具体实现过程及其参数的含义：1）. Polyn CreatePolyn(Polyn head,
10、int m)该函数的两个参数，head表示为创建的链表的头指针，m表示为链表的长度，即多项式的项数。定义int i计数，当inext=NULL; for(i=0;icoef,&p-expn); Insert(p,head); /调用Insert函数插入结点 return head;/CreatePolyn2). void Insert(Polyn p,Polyn h) 该函数具有两个参数，用来实现链表的顺序排列和合并相同的项。以下是实现插入的关键代码： void Insert(Polyn p,Polyn h) if(p-coef=0) free(p); /系数为0的话释放结点 else/如果系
11、数不为0 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; /Insert3). int compare(Polyn a,Polyn b)此函数是用来比较两个多项式之间的系数大小。 int compa
12、re(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多项式非空/compare4）. Polyn AddPolyn(Polyn pa,Polyn pb) 该函数有两个参数，其类型均为polyn，分别表示要相加的两个不同的多项式。其计算的结果存放在新建的pc所指向的链表中。函数中调用了int compare(P
13、olyn a,Polyn b)的结果。下面是实现加法的关键代码：Polyn 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
